СитиГИД перешел на новые алгоритмы обработки информации о пробках

[svlad2012]

Про расход бензина - хорошая ведь идея: это была бы та самая золотая середина между временем и пространством. Я когда эту тему про тип маршрута Экономичный здесь откопал и написал в ее защиту, мне тупо поставили минус и проигнорили. Вот чем плоха? Тем, что у всех расход разный? Так взять усредненный, главное, чтоб "мифических" перепробегов стало меньше

Поправлено с моего GT-N7000 при помощи T9

В моем гармине есть такой режим, правда там всё просто - задается расход топлива для трассы и для города и считается, что пробок вообще не бывает в жизни.

Вообще-то, на мой взгляд, такой режим сделать не сложно, а то, что расход у всяких машин+стиль езды разный, так пусть эти коэффициенты будут индивидуальны для каждого. Заодно их можно будет корректировать по своей статистике (хотя бы по файлам треков).

 

Что касается "перепробегов" -  будет не всё так очевидно. Хотя бы из этого Оценка зависимости среднего расхода топлива.pdf видно, что для минимального расхода топлива существует некоторая оптимальная скорость, выше и ниже которой расход увеличивается.

Следовательно, снова найдутся недовольные, которые будут возмущаться: "ИМХО, надо предлагать выбор из нескольких маршрутов. Не дело, когда из-за экономии 50 г бензина СГ предлагает путь на 20 км длиннее".

 

На мой взгляд, такой режим не помешал бы, если, конечно, СГ не позиционируется как исключительно "городской антипробочный" навигатор.

[Dmitrii]

Это вы про что?

Пример:

Построен маршрут: длительность 15 км время 40 минут

Вдруг СитиГид перестраивает маршрут: длительность 30 км время 39 минут.

Налицо увеличение протяженности маршрута на 100% ради выгоды во времени на 3%.

Это и есть относительные показатели - 100% и 3%. Вот они должны быть сопоставимыми. Я бы согласился на увеличение протяженности маршрута на 100%, если бы это давало преимущество хотя бы на 15-20%, но ни как не на 3%.

Не говоря уже о том, что всё что менее 10% вообще укладывается в погрешность расчетов и изменений дорожной обстановки, которые СитиГид учесть не может (быстроустаревающие пробкоданные, моя личная везучесть/невезучесть или нерасторопность и т.п.)

[Dmitrii]

Вообще-то, на мой взгляд, такой режим сделать не сложно, а то, что расход у всяких машин+стиль езды разный, так пусть эти коэффициенты будут индивидуальны для каждого.

А нафиг коэффициенты какие-то?

Крейсерские скорости (максимальная скорость при минимальных энергозатратах) у всех легковых автомобилей примерно одинаковы - это ~30-40 км/ч и 90-100 км/ч. На таких скоростях автомобиль тратит на 100 км пути меньше всего топлива. Зная скорость на каждом отдельном участке (ребре) пути, несложно рассчитать некий показатель расхода для всего маршрута. И этот показатель будет абсолютно одинаков что для малолитражки, что для какого-нибудь полноприводного джипа. Хотя точным он всё равно не будет, т.к. средняя скорость, как правило, не является реальной - ведь на ребре со средней скоростью 10 км/ч можно реально ехать с постоянными ускорениями/замедлениями от 0 км/ч до 60 км/ч (а то и больше), а можно реально ехать почти весь кусок со скоростью 10км/ч.

[arctec]

Следовательно, снова найдутся недовольные, которые будут возмущаться: "ИМХО, надо предлагать выбор из нескольких маршрутов.

Вот и вырисовывается набор из трех вариантов маршрута на выбор: оптимальный (он же быстрейший), экономичный и кратчайший

[IШIN]

Пример:Построен маршрут: длительность 15 км время 40 минутВдруг СитиГИД перестраивает маршрут: длительность 30 км время 39 минут.Налицо увеличение протяженности маршрута на 100% ради выгоды во времени на 3%.

А с другой стороны - провести в машине 40 минут со средней скоростью 22км/ч или 45км/ч - я бы подумал.

22 - это значит непрерывно дергаться, а 45 - то ползти, то ехать.

[Евгений Ш]

22 - это значит непрерывно дергаться

Да ничего подобного. Нажал тормоз - отпустил тормоз

[Artur273]

Желательно помучиться... (с)

В общем, хотелось бы посмотреть

Конечно не совсем очевидно, что ни один из маршрутов не является кратчайшим, но это на мой взгляд так.

[WhiteUnicorn]

Пример:

Построен маршрут: длительность 15 км время 40 минут

Вдруг СитиГИД перестраивает маршрут: длительность 30 км время 39 минут.

Налицо увеличение протяженности маршрута на 100% ради выгоды во времени на 3%.

Это и есть относительные показатели - 100% и 3%. Вот они должны быть сопоставимыми. Я бы согласился на увеличение протяженности маршрута на 100%, если бы это давало преимущество хотя бы на 15-20%, но ни как не на 3%.

Не говоря уже о том, что всё что менее 10% вообще укладывается в погрешность расчетов и изменений дорожной обстановки, которые СитиГИД учесть не может (быстроустаревающие пробкоданные, моя личная везучесть/невезучесть или нерасторопность и т.п.)

 

Знаете, я постоянно об этом думаю Надо же чем то себя развлечь в пробках. В частности о том, согласна ли я пожертвовать временем перепрокладки маршрута ради вот этих сравнений.

 

С одной стороны - да, было бы очень разумно, чтобы "придумав" новый маршрут СГ сравнил время1/время2 и пробег1/пробег2, после чего принял бы решение - предлагать новый маршрут или нет. Все 4 числа ему известны на момент вопля "Маршрут изменился!" Можно даже было бы в настройках (хотя бы через конфиг) сделать задание коэффициента, при котором принимается решение "Да".

 

С другой стороны, можно придумать очень много полезных и хороших вещей, которые полезно и хорошо учитывать при прокладке маршрутов. И каждая из них сама по себе вряд ли займет много доп.времени. Однако надо понимать, что время они ЗАЙМУТ. И постепенно-постепенно, плавно-плавно мы получим замедление работы программы в целом и увеличение времени пересчета маршрута в частности. 

 

Глядя на эти "с одной" и "с другой" стороны я начинаю думать, что моя голова, которая освобождена программой навигации от непосредственно прокладки маршрута и поиска визуальных ориентиров для его соблюдения, вполне может поработать доп.компьютером, который как раз и занимается этими вот коэффициентами. Не знаю, кто как, а я так все время смотрю и на время и расстояние. Если после изменения маршрута я вижу, что пробег увеличился в два раза, а время уменьшилось на 1 минуту, то я с большой вероятностью забью на это изменение и поеду так, как СГ говорил до того. И он спокойно мне вернет старый маршрут. 

 

Причем такой вариант позволяет мне автоматически учесть собственные предпочтения. Я могу радостно согласиться на какой-то любимый вариант маршрута, даже если он вроде бы неоптимален по соотношениям время и пробег. Или наоборот отказаться от вроде бы адекватного маршрута, если я точно знаю, что какой-то перекресток я жуть, как не люблю.

 

Что, на мой взгляд, сделать действительно нужно - это учет пробок по статистике. Об этом уже много писали, но я таки скажу еще раз Потому что когда я еду в знакомых местах. я могу понять, что если мы поедем вот этим более длинным маршрутом, то стопудов в середине мы приедем аккурат к пробке. А если поедем вон тем, который короче, но по времени СЕЙЧАС длиннее - то мы его проскочим до окончательного закупоривания. В незнакомых же местах я этого не знаю, поэтому еду, как велят и таки приезжаю в пробку по расписанию

Но честно говоря я плохо представляю, как такой алгоритм реализовать.

 

Кстати, таки СГ вычисляет маршрут, выращивая его на манер дерева, т.е. принимая решения на каждом перекрестке или он обсчитывает несколько вариантов маршрута и выбирает среди них лучший по заданному критерию?

[/DiOs]

Все 4 числа ему известны на момент вопля "Маршрут изменился!"

Нет. Он не знает времени на прежнем маршруте. Он знает некую оценку, которой пользователи постоянно недовольны и которой, собственно, и было посвящено открытие топика. Это не такое же расчётное время прежнего маршрута, как определённое для нового.

 

И он спокойно мне вернет старый маршрут. 

Это заблуждение, которое изредка бывает истинным. При наличии подходящих условий СГ будет достаточно долго и упорно тянуть вас на вновь проложенный маршрут до тех пор, пока новый расчётный в какой-то части не совпадёт с тем, который вы называете "старый". В частности потому, что см. выше.

 

Но честно говоря я плохо представляю, как такой алгоритм реализовать.

Он давно реализован в СГ. Только вот по целому ряду причин работает от "сносно" до "отвратительно". И одна из этих причин -- принцип хранения статистики, превращающий её в "статистику". "Когда великий Мохаммед писал свои скрижали, он ешё не знал, что дороги будут минировать".

 

Кстати, таки СГ вычисляет маршрут, выращивая его на манер дерева, т.е. принимая решения на каждом перекрестке или он обсчитывает несколько вариантов маршрута и выбирает среди них лучший по заданному критерию?

Он делает это по алгоритму, который у каждой навикомпании является чуть ли не самой основной коммерческой тайной.

[svlad2012]

Кстати, таки СГ вычисляет маршрут, выращивая его на манер дерева, т.е. принимая решения на каждом перекрестке или он обсчитывает несколько вариантов маршрута и выбирает среди них лучший по заданному критерию?

 

Одним из алгоритмов построения маршрута может быть алгоритм Дейкстры:

http://ru.wikipedia.org/wiki/%C0%EB%E3%EE%F0%E8%F2%EC_%C4%E5%E9%EA%F1%F2%F0%FB

 

А как фактически рассчитывает СГ - очень подробно ответил /DiOs )

[IШIN]

Судя по виду ссылки, этот алгоритм тоже засекречен.

-----

За ашыпки прашю винить TapaTalk

[svlad2012]

uploadfromtaptalk1386178816145.jpg

Судя по виду ссылки, этот алгоритм тоже засекречен.

-----

За ашыпки прашю винить TapaTalk

Это я поблагодарил  за подробный и обстоятельный ответ по поводу алгоритма СГ

 

Что-то здесь нечисто  - эта "благодарность" в сообщении не видна (на компе), но иногда и видна  .

Думаю, всё дело в палке перед ДиОсом...

 

****

Не, не палка оказалась... Вставляю в сообщение ссылку и всё -сообщения не видно

Попробую просто текстом: ru.wikipedia.org/wiki/%C0%EB%E3%EE%F0%E8%F2%EC_%C4%E5%E9%EA%F1%F2%F0%FB

Изменено 4 декабря, 2013 пользователем svlad2012

[IШIN]

Да, она работает. И на компе показывается нормально. Но на компе не виден реверанс в сторону /DiOsа.

Он появляется только при попытке ответа с цитированием...

А вот в тапаталке сообщение показалось вместе с реверансом, но зато Вики-ссылка как-то украсилась для нагнетания секретности...

В общем, в тапке все не как у людей.

 

 

 

Думаю, всё дело в палке перед ДиОсом...

А вот махать палкой перед ДиОсом я бы вообще не рискнул.

Изменено 4 декабря, 2013 пользователем IШIN

[leshiy2k]

Одним из алгоритмов построения маршрута может быть алгоритм Дейкстры:

 

Мне там понравилась ошибка в примере Треугольник 1-3-6 не существует, так как не выполняется условие, что сумма 2 любых сторон треугольника должна быть больше длины третьей стороны: там стороны 9, 2 и 14 Но это уже детали

Изменено 5 декабря, 2013 пользователем leshiy2k

[svlad2012]

Треугольник 1-3-6 не существует, так как не выполняется условие, что сумма 2 любых сторон треугольника должна быть больше длины третьей стороны: там стороны 9, 2 и 14 Но это уже детали

Так то не геометрия, а ребра графа. А если 9, 2, 14 - это не длины, а время или скорость?

Даже, если это длина, то 14 может соответствовать очень кривой улице, когда 2 и 9 - прямым улицам.

[IШIN]

алгоритм Дейкстры: http://ru.wikipedia....rg/wiki/

Господи, как все, оказывается просто!

Особенно

скрытые константы в асимптотических оценках трудоемкости велики и использование фибоначчиевых куч редко оказывается целесообразным: обычные двоичные кучи на практике эффективнее.
Альтернативами им служат толстые кучи, тонкие кучи и кучи Бродала, обладающие теми же асимптотическими оценками, но меньшими константами.

И чего там МИТ не может сделать расчет 3х разных маршрутов на мощном железе с 64 МБ памяти под ВинСЕ...

[eklmn]

Не, ну с кучами Бродала и так всё понятно на интуитивном уровне... 

[svlad2012]

Конечно не совсем очевидно, что ни один из маршрутов не является кратчайшим, но это на мой взгляд так.

Дf! Это оказался не самый короткий маршрут! Тем не менее:

При прокладке этого маршрута на ЯК без пробок он пошел через закрытый НовоКалинкин мост. Пришлось ставить промежуточную точку, как в вашем скриншоте. На мой взгляд, получился тот же самый маршрут:

 

Однако всплыла одна фишка. Если промежуточную точку поставить на ул.Шкапина, то и получиться тот же маршрут, а если эту точку перенести на мост, то маршрут построится "в обход" и будет длиннее на 700 м

       

Если же заставить проложить маршрут по Говорова, то он станет короче на 500 м   (СГ короткий маршрут строит именно по Говорова)

 

Т.о. я делаю вывод:

1) альтернативный маршрут у ЯН не является самым коротким. Вероятно - это короткий, построенный с учетом "ширины дорог", м.б. еще с чем-нибудь, типа ограничения левых поворотов и т.п.

2) альтернативный маршрут у ЯН строится без учета пробок   (хотя время маршрута показывается с учетом пробочной информации)

3) подтверждается моё мнение, что ни один навигатор на сегодняшний день не предлагает альтернативного маршрута типа "помедленнее на хх мин, но по короче на уу км", а предлагаются только разного типа - "быстрый" и "короткий", или с разным графом дорог - без/с платных дорог, без/с автомагистрали и т.п.

 

Вот так то так

[IШIN]

При прокладке этого маршрута на ЯК без пробок он пошел через закрытый НовоКалинкин мост.

 

Однако всплыла одна фишка. Если промежуточную точку поставить на ул.Шкапина, то и получится тот же маршрут, а если эту точку перенести на мост, то маршрут построится "в обход" и будет длиннее на 700 м 

Если же заставить проложить маршрут по Говорова, то он станет короче на 500 м 

1. Ново-Калинкин мост открыт. Закрыт Старо-Калинкин.

2. По-моему (судя по клетчатому флажку), artur_nexia клал маршрут в обратную сторону (типа "с Васьки сюда ко мне"), соответственно, не по Шкапина, а по Ивана Черных (а дальше - по Говорова или по Стачек). То есть сравнивать ваши с ним два эксперимента не стоит.

[/DiOs]

И чего там МИТ не может сделать расчет 3х разных маршрутов на мощном железе с 64 МБ памяти под ВинСЕ...

Именно потому я и написАл ту фразу, над которой изгаляется svlad2012, тыча палкой в мою харю!

[Artur273]

Дf! Это оказался не самый короткий маршрут! Тем не менее:

При прокладке этого маршрута на ЯК без пробок он пошел через закрытый НовоКалинкин мост. Пришлось ставить промежуточную точку, как в вашем скриншоте. На мой взгляд, получился тот же самый маршрут:

YK1.png

 

Однако всплыла одна фишка. Если промежуточную точку поставить на ул.Шкапина, то и получиться тот же маршрут, а если эту точку перенести на мост, то маршрут построится "в обход" и будет длиннее на 700 м

YK2.png        YK3.png

Если же заставить проложить маршрут по Говорова, то он станет короче на 500 м   (СГ короткий маршрут строит именно по Говорова)

YK4.png

 

Т.о. я делаю вывод:

1) альтернативный маршрут у ЯН не является самым коротким. Вероятно - это короткий, построенный с учетом "ширины дорог", м.б. еще с чем-нибудь, типа ограничения левых поворотов и т.п.

2) альтернативный маршрут у ЯН строится без учета пробок   (хотя время маршрута показывается с учетом пробочной информации)

3) подтверждается моё мнение, что ни один навигатор на сегодняшний день не предлагает альтернативного маршрута типа "помедленнее на хх мин, но по короче на уу км", а предлагаются только разного типа - "быстрый" и "короткий", или с разным графом дорог - без/с платных дорог, без/с автомагистрали и т.п.

 

Вот так то так

вынужден возразить, причем, что характерно, не из вредности , возможно маршрут строится и не с учетом пробок, полностью я отрицать не учет пробок не могу, с явным учетом, поскольку на ряде маршрутов, причем длинных, альтернативы не предлагаются.

касательно пром точки, пром точка мной не фиксировалась, она просто обозначена, аля - "мил друг, если тебе надо через что-то проехать то тянуть надо эту фигню", соответственно я ее не сдвигал.

и верно предположение IШIN, что маршрут на скриншоте с васьки в автово а не наоборот.

добавлено: нет, видимо альтернативный маршрут все-таки кратчайщий туше но предлагается он только если отличие от оптимального не более некоей величины.

Изменено 5 декабря, 2013 пользователем artur_nexia

[alexeyT4]

Вот сегодня варианты прокладки маршрута.

53км за1:05

Или

32км за 1:15.

Есть ли смысл ехать лишних 20км из-за сомнительных10 минут выигрыша.

Прибытие по короткому маршруту получилось

19:55. На 15 минут раньше поогноза.

Отправлено с моего GT-I9100 через Tapatalk

[leshiy2k]

53км за1:05

Или

32км за 1:15.

Есть ли смысл ехать лишних 20км из-за сомнительных10 минут выигрыша.

Ну вот смотри. Первый вариант - средняя скорость 49 км/ч, второй вариант - 25 км/ч. И тут уже кому как, но я поехал бы лишние 20 км, чтобы ехать с бОльшей скоростью, чем толкаться, но на 20 км меньше. Именно потому и нельзя однозначно переделывать алгоритмы: то, что хорошо для меня, не подойдет тебе, и наоборот.

[ERER]

Ну вот смотри. Первый вариант - средняя скорость 49 км/ч, второй вариант - 25 км/ч. И тут уже кому как, но я поехал бы лишние 20 км, чтобы ехать с бОльшей скоростью, чем толкаться, но на 20 км меньше. Именно потому и нельзя однозначно переделывать алгоритмы: то, что хорошо для меня, не подойдет тебе, и наоборот.

И именно поэтому при первой прокладке нужно предлагать варианты, если они есть. А после выбора пользователем все дальнейшие перепрокладки делаются с учетом этого выбора.

[arctec]

И именно поэтому при первой прокладке нужно предлагать варианты, если они есть.

и при выдаче вариантов указать среднюю скорость на каждом и количество маневров