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

[timvetrov]

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

Возможно, она знает про скорость автомобиля, так сказать, из первых рук?

[OlegCh]

Возможно, она знает про скорость автомобиля, так сказать, из первых рук?

Ну разумеется, что-то там такое используется - значение скорости со спидометра, возможно даже положение колес. Я про то, что СГ тоже должен что-то придумать - например, фиксировать время перед въездом в туннель, затем перестать использовать данные GPS чтобы не получалось ложного положения, а при выезде из туннеля когда сигнал GPS восстанавливается снова фиксировать время и на основе этих данных делать вывод о пробочной ситуации в туннеле.

[Vodolazz]

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

1. А насколько и как влияет? Поясните, пожалуйста. А если таких коротких ребер на протяжении маршрута 10 шт. Это как в анекдоте про Раскольникова, 5 бабушек уже рубль.

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

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

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

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

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

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

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

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

Предпологается в Пробки-3 реализовать прокладку маршрутов с учетом работы светофоров. КМК влияние на стояние на красный свет не очень большое. И если убрать влияние на простой на красном свете это может повлиять на статистику на проезд в непробочное время. Но надо посмотреть на практике может и правда надо убирать 50 м перед светофором.

[Vodolazz]

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

Предлагаю открыть новую тему, а то она здесь затеряется.

[OlegCh]

Предлагаю открыть новую тему, а то она здесь затеряется.

Открыл.

[ERER]

1. А насколько и как влияет? Поясните, пожалуйста. А если таких коротких ребер на протяжении маршрута 10 шт. Это как в анекдоте про Раскольникова, 5 бабушек уже рубль.

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

[ERER]

Но предлагаю все таки использовать пороговое значение менее примерно 30% от статистической скорости на данном ребре.

Да нет. КМК статистическая скорость на большинстве внутригородских ребрах колеблется в районе 40 км/ч, не больше. Много где и существенно меньше. Т.о. при статистической скорости в 40 км/ч, отображение скорости датчика начнется только в том случае, если он проехал ребро со скоростью не быстрее 12 км/ч.

КМК влияние на стояние на красный свет не очень большое. И если убрать влияние на простой на красном свете это может повлиять на статистику на проезд в непробочное время. Но надо посмотреть на практике может и правда надо убирать 50 м перед светофором.

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

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

[ERER]

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

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

Это все хорошо, если есть датчики за это время. А если он единственный?

[Vodolazz]

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

Т. е. Вы бы развернулись быстрее? Я думаю что надо рассматривать только влияние которое не соответствует средней скорости прохождения определенного маршрута. А если там человек провел 5 мин на ребре длиною 100 м, и мы не будем учитывать эти 5 простоя (которые могут в нарастающий час пик могут привести к дополнительным 20 мин.), то это неверное использование данных. И так из-за плохого мобильного интернета данные датчиков по городу пунктирами идут. В Москве так вообще датчиков не так много. Так что любыми данными пренебрегать не стоит, просто надо их правильно обрабатывать. Что бы сейчас точно рассуждать как влияют короткие ребра на прокладку маршрута, надо знать точный алгорити расчета маршрута, а это коммерческая тайна, я пытался настойчиво здесь это выяснить, так мне репутацию занизили .

[andrej]

Это все хорошо, если есть датчики за это время. А если он единственный?

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

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

Проблема, которую решает Ваше предложение, больше связана с обилием датчиков (красные следы перед светофором), чем с их отсутствием.

[Vodolazz]

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

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

[ERER]

Т. е. Вы бы развернулись быстрее?

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

[ERER]

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

Простой светофор, который еще и находится на конце относительно короткого ребра. Датчик подъезжает к мигающему зеленому и останавливается на полную фазу красного. В результате скорость ребра 15 км/ч. Второй датчик подъезжает к концу красной фазы и чуть притормозив, без остановки проезжает перекресток. Скорость на ребре 55 км/ч. Разница существенна.

[Vodolazz]

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

Храним на сервере для одного направления проезда светофора например 7 скоростей (или времён) проезда по порядку появления.

Это будут неточные данные. В часы пик скорость потока меняется в лучшем случае каждые 15 минут как в сторону уменьшения и увеличения. Сравнивать данные проезда вне этого интервала не корректно, особенно на стыке перед часом пик. По моему мнению, достаточно хранить статистику по следующим признакам:

1. Время года (лучше месяц);

2. День недели или выходной праздничный день;

3. Ночь (с 23-00 до 6-00), утро (каждые 15 минут с 6-00 до 10-00), день (с 10-00 до 17-00), вечер (каждые 15 минут с 17-00 до 22-00).

Только конечно такая статистика должна быть вместе с картой. Но вот только как технически это сложно реализовать?

[Vodolazz]

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

Простой светофор, который еще и находится на конце относительно короткого ребра. Датчик подъезжает к мигающему зеленому и останавливается на полную фазу красного. В результате скорость ребра 15 км/ч. Второй датчик подъезжает к концу красной фазы и чуть притормозив, без остановки проезжает перекресток. Скорость на ребре 55 км/ч. Разница существенна.

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

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

[Joss]

По-моему в форуме писали, что СГ использует показания датчика проехавшего последним по ребру

Кто писал? Если есть информация от нескольких датчиков, СГ учитывает не только единичные данные от крайнего.

[IШIN]

Если есть информация от нескольких датчиков, СГ учитывает не только единичные данные от крайнего.

Ага. Спасибо за этот маленький вброс информации. Это радует.

[niber]

Ага. Спасибо за этот маленький вброс информации. Это радует.

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

[Vodolazz]

Кто писал? Если есть информация от нескольких датчиков, СГ учитывает не только единичные данные от крайнего.

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

Спасибо, запомню и буду учитывать эту информацию в дальнейшем.

[alexeyT4]

3. Ночь (с 23-00 до 6-00), утро (каждые 15 минут с 6-00 до 10-00), день (с 10-00 до 17-00), вечер (каждые 15 минут с 17-00 до 22-00). Только конечно такая статистика должна быть вместе с картой. Но вот только как технически это сложно реализовать?

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

Это одно из важнейших условий прокладки оптимального маршрута.

Зачем мне прокладывать маршрут через улицу на которой через 15 минут будет пробка, если мне до ней ехать 20мин.

Или зачем объезжать улицу на которой через 15 мин пробка исчезнет и ехать до нее те же 20 мин.

Таких мест, кстати немало.(не говоря уже о переездах и мостах)

[Vodolazz]

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

Это одно из важнейших условий прокладки оптимального маршрута.

Зачем мне прокладывать маршрут через улицу на которой через 15 минут будет пробка, если мне до ней ехать 20мин.

Или зачем объезжать улицу на которой через 15 мин пробка исчезнет и ехать до нее те же 20 мин.

Таких мест, кстати немало.(не говоря уже о переездах и мостах)

Полностью с Вами согласен. А сейчас СГ учитывает при прокладке маршрута время доезда при прокладке маршрута?

[s35]

Ну вы меня удивляете! Ну откуда СГ может узнать,что будет через 15 минут?

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

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

[bushmen]

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

Это одно из важнейших условий прокладки оптимального маршрута.

Зачем мне прокладывать маршрут через улицу на которой через 15 минут будет пробка, если мне до ней ехать 20мин.

Или зачем объезжать улицу на которой через 15 мин пробка исчезнет и ехать до нее те же 20 мин.

Таких мест, кстати немало.(не говоря уже о переездах и мостах)

Интересно, если скажем в том месте есть пробка, а по статистике ее там не бывает и Вы в нее попадаете, то на форуме появится гневный отзыв от Вас, что СГ заводит в пробки? :)

[Vodolazz]

Ну откуда СГ может узнать,что будет через 15 минут?

Из статистики для каждых 15 минут часа пик.

[bushmen]

Из статистики для каждых 15 минут часа пик.

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