Алгоритмы расчета и прокладки маршрутов

[vovicom]

Не по летней, а по весенней.

ну почему все такие умные?!:)

[ERER]

ну почему все такие умные?!

Написать то можно все, что угодно.

Но новость от 17 июня, а это 1/6 календарного лета. Т.ч. или это еще несуществующая статистика или, в лучшем случае, прошлогодняя

[Joss]

ERER,

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

[ERER]

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

Ну критерий-то ясный.

А в описываемых случаях СГ явно должен вести себя так же, как при движении в тупик, т.е. (для версии 5.1 под Андроид) не перепрокладывать маршрут вообще, раз не может предложить разворот.

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

[ERER]

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

Т.о. получается, что используется прошлогодняя летняя статистика? А на зимнее-весеннюю забивается? Просто интересно.

Я сейчас второй день, интереса ради, катаюсь без пробок, исключительно по статистике.

Как ни странно, но ничего так. ИМХО при небольших доработках было бы намного удобнее, чем с полными пробочными данными.

А если еще статистику обновлять online хотя бы раз в неделю, то ...

[bushmen]

А если еще статистику обновлять online хотя бы раз в неделю, то ...

Да, на мой взгляд, это было бы замечательно :)

[stroncium90]

Даже если она весит больше 10 мбайт на одну карту? :blink:

[bushmen]

Даже если она весит больше 10 мбайт на одну карту?

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

[ERER]

Даже если она весит больше 10 мбайт на одну карту?

Тест показал, что для upgrade-а 11.5Мб-овой статистики карты Питера с версии 27.2 до верси 28.2 достаточно максимум ~5Мб. Для еженедельного должно быть намного (в разы) меньше КМК.

Изменено 11 октября, 2011 пользователем ERER

[Joss]

Процесс сбора и обработки статистики довольно трудоемкая задача, занимающая не один день. Так что не будет "раз в неделю".

[Gonza]

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

Дык тем же, чем двор отличается от квартала. Площадью. ;)

[Vodolazz]

Дык тем же, чем двор отличается от квартала. Площадью.

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

[OlegCh]

Процесс сбора и обработки статистики довольно трудоемкая задача, занимающая не один день. Так что не будет "раз в неделю".

Надеюсь, это не "вручную" происходит? Тогда в чем ее трудоемкость?

[IШIN]

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

Дык тем же, чем двор отличается от квартала. Площадью.

Ой не факт. Это как переулок и проспект. Для сравнения - на Петроградке переулок Вяземский (в каждую сторону по 2 полосы + рельсы) и Аптекарский проспект - 1+1 полоса.

[Joss]

Надеюсь, это не "вручную" происходит? Тогда в чем ее трудоемкость?

Я не буду вдаваться в подробности, суть в том, что обновление статистики раз в неделю точно не будет.

[Gonza]

Это как переулок и проспект. Для сравнения

Чуть-чуть некорректное сравнение.

Квартал, как правило, состоит из дворов. Что нельзя, в том же контексте, сказать о проспекте и переулке.

Тем самым, можно утверждать, что внутридворовые проезды - они же и внутриквартальные. Дело в терминах.

[timvetrov]

Квартал, как правило, состоит из дворов. Что нельзя, в том же контексте, сказать о проспекте и переулке. Тем самым, можно утверждать, что внутридворовые проезды - они же и внутриквартальные. Дело в терминах.

А я думал, что внутридворовые проезды - это внутри дворов, а внутриквартальные - это более крупные, как-бы "между" дворов...

[Евгений Ш]

Предлагаю во избежание споров считать проездами то, что СГ показывает как проезды. А что не показывает - дворовыми территориями. Других объективных критериев, типа есть название/нет названия, не вижу. Как пример (правда, ИМХО, в тех краях кто-то из команды СГ живёт ) скриншот. Кто бывал в тех краях, знает, что там, где цифра "1" - реальная дорога, её и проездом-то назвать язык не повернётся.

[ERER]

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

Поэтому просто мысли вслух.

1. Не использовать, т.е. не собирать, не рассылать и само-собой не отображать пробочную информацию на очень коротких ребрах. Ее ценность минимальна, а на прокладку маршрута частенько влияет. Плюс захламляет карту. В случае необходимости для “хранения” пробочных скоростей П2 использовать длинные ребра предстоящие данным ребрам. Естественно могут быть исключения.

2. Отображать и использовать в прокладчике только пробочные данные о скоростях менее 10 км/ч или величиной менее примерно 30% от статистической скорости на данном ребре.

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

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

Но тут мы имеем первую проблему. Для такой работы нужно обновлять статистику. Желательно где-то раз в неделю, максиму в раз в две. Но как было “официально” сказано, такого не будет, т.к. подготовка статистики занимает очень много времени, и такое частое обновление статистики невозможно. Честно говоря, я был удивлен, единственное, что приходит на ум - ручной труд.

3. Светофоры. Для нейтрализации влияния светофоров, которое мы имеем сейчас, и которое особенно будет иметь место при реализации п.2., необходимо каждое ребро, оканчивающееся светофором (а может и вообще каждое ребро) разбить на два неравных отрезка. Меньший отрезок длинной около 50 метров должен располагаться около светофора и согласно п.1 пробочные данные с него не получаются и на него не передаются. Вместо этого он использует данные длинного отрезка. Т.о. практически полностью нивелируется неравномерность скоростей из-за фаз светофоров. При образовании реального затора, мы получим данные от длинного отрезка. И если скорость упадет до величин, указанных в п.2 эта скорость начнет использоваться прокладчиком.

Т.о. опять получается более стабильный маршрут, не теряющий при этом оптимальности.

Но тут возникает вторя проблема. ЕМНИП в существующем алгоритме быстрой прокладки маршрута имеется ограничение на количество ребер.

Обменяемся мнениями по всему вышеизложенному?

Изменено 18 октября, 2011 пользователем ERER

[Joss]

ERER

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

[andrej]

3. Светофоры. ...

Обменяемся мнениями по всему вышеизложенному?

Что касается светофоров и "быстрых" переездов, для которых нет расписания.

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

[ERER]

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

Можно попробовать.

[ERER]

andrej, по светофора я имел в виду не расчет статистики, а убирание "неправильных" скоростей, когда датчик просто остановился на красной фазе светофора, в результате чего на ребро установилась низкая скорость, и маршрут прокладывается в объезд, хотя в реальности ребро совершенно пустое.

[andrej]

andrej, по светофору я имел в виду не расчет статистики...

И я имел в виду именно расчёт пробкоданных (не статистики) для предшествующего светофору ребра. Считать не по проезду последнего датчика, а усреднять до среднего медианального за несколько циклов. Т.е. просто от очередного изменения фазы светофора (и соответственно от проезда/остановки датчиков) пробкоданные меняться не должны. Т.е. это не стандартный, а "светофорный" алгоритм усреднения. Считать естественно отдельно для каждого направления проезда светофорного узла.

Описывая свой вариант, Вы практически предлагали из пробкоданных брать не текущие скорости, а только оперативную информацию о глухой пробке, чтобы вовремя запирать ребро. А в отсутствии глухой пробки Вы предлагаете пользоваться статистикой, но почаще её обновлять.

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

Изменено 19 октября, 2011 пользователем andrej

[OlegCh]

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

Я недавно столкнулся с неадекватным поведением программы при проезде туннелей. В Москве есть довольно длинные туннели на ТТК, на Ленинградке и Волоколамке. Если туннель проскакиваешь быстро, то вроде все неплохо - за тобой рисуется зеленая линия. Но стоит попасть в пробку как сигнал GPS пропадает, дельтаплан начинает прыгать туда-сюда, информация о пробке не передается и пробки в туннеле, получается, нет.

В то же время штатная бмв-шная навигация в машине прекрасно ведет в туннеле даже при отсутствии GPS сигнала.

Надо подправить алгоритм работы при проезде туннелей.

Изменено 19 октября, 2011 пользователем OlegCh