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

[Apocalipsis]

Пример прикольный, мне понарвилось. Здесь понятна проблема короткого ребра. И потому вопрос. А там точно промежуточна точка 1 не попадает до перекрестка на перпендикулярной улице? Может он и без пробок так проложит маршрут. Для подтверждения нужен более точный скрин.

вот скрин сегодня сделал.... точка ставится через поиск перекрестка. так что в обоих случаях она стоит в одном и том же месте...

P.S. карта если память не изменяет для предыдущего поста была объединенная СПб+ЛО версия 1.2, поэтому этот скрин сделал на той же карте!

[Vodolazz]

вот скрин сегодня сделал.... точка ставится через поиск перекрестка. так что в обоих случаях она стоит в одном и том же месте...

P.S. карта если память не изменяет для предыдущего поста была объединенная СПб+ЛО версия 1.2, поэтому этот скрин сделал на той же карте!

СГ выбрал такой маршрут только если скорость поворота направо на этом ребре должна составлять раз 30 меньше скорости предложенной по маршруту, т.е. около 1-2 км/ч. Судя по скрину в обоих случаях используется статистики или скорость зашитая в карту.

[Apocalipsis]

СГ выбрал такой маршрут только если скорость поворота направо на этом ребре должна составлять раз 30 меньше скорости предложенной по маршруту, т.е. около 1-2 км/ч. Судя по скрину в обоих случаях используется статистики или скорость зашитая в карту.

я догадываюсь почему СГ так себя повел, это просто наглядная иллюстрация из боевых условий, о том как влияют короткие ребра на прокладку маршрута... там ребро то 100 метров, а объезд почти 2,3 км... с разворотом и тремя светофорами :-)

P.S. на этом ребре всегда низкая скорость из-за не очень удачного режима работы светофора...

Изменено 2 ноября, 2011 пользователем Apocalipsis

[OlegCh]

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

[Vodolazz]

я догадываюсь почему СГ так себя повел, это просто наглядная иллюстрация из боевых условий, о том как влияют короткие ребра на прокладку маршрута... там ребро то 100 метров, а объезд почти 2,3 км... с разворотом и тремя светофорами :-)

P.S. на этом ребре всегда низкая скорость из-за не очень удачного режима работы светофора...

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

Согласен c OlegCh. Если при таком маршруте выигрыш во времени более 5 минут, то почему и не поехать. Были предложения по разбивке вида маршрута Оптимальный на два вида. А если мы уберем это ребро, как мы будем считать время проезда с разворотом? Что такое длина ребра:

Убирать ребра с возможностью маневра, значит убирать возможность совершения маневра.

[zoran]

Надо сделать алгоритм самообучаемым.

Кто то поехал не по предложенному маршруту быстрее, это повторяется- прокладывать маршрут по этой статистике.

кто то проехал по маршруту дольше намеченного, есть статистика- меняем маршрут.

Боюсь, что это возможно только на стороне сервера...

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

[Joss]

Неплохо подумать над идеей автоматически собрать с пользователей дворовые проезды

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

[zoran]

По моему любимому двору довольно точно показывает.

[Zvezdochet]

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

если проехаться раз 100, думаю будет достаточно точно :unsure:

[OlegCh]

если проехаться раз 100, думаю будет достаточно точно

Да и четырехполосные дворовые проезды тоже неплохо! ;)

[Scientist]

Все-таки хотелось бы понять, как работает статистика при прокладке длинных маршрутов.

Например, вчера ехал с пл. Мужества на Волхонку. Выехал около 8 утра, маршрут проложился через город, видимо, по статистике ночного времени. Предполагаемое время - 47 минут. Но понятно, что через полчаса, когда я въеду в центр, это будет уже неоптимально. Так и случилось. Доехал до Лесной, предсказанное время стало быстро расти, но на кольцо съезжать уже смысла не было - до него еще доехать надо. В результате ехал примерно 1:20. Что почти вдвое дольше. Если бы при прокладке маршрута использовалась статистика на то время, когда я подъеду к определенным точкам, СГ наверняка бы предложил ехать по кольцу, и заняло бы это минут 50.

[OlegCh]

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

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

[IШIN]

Очень уж итерационный процесс получается. Надо брать статистику для ближайшего района текущую, для ближайшего куска КАД - на 15 минут вперед, для дальнего куска КАД - на полчаса вперед, для противоположного района города на час вперед... Потом понимаем, что так получается долго, и начинаем искать другой маршрут, но с другими статичстическими данными, и т.д. А в финале пробка, которая обычно за час рассасывалась, именно сегодня будет на час дольше. И мы будем вопить "Он же видел пробку! Какого черта вел туда! Мало ли что там обычно бывает!"

А обладатели наиболее быстрых девайсов и больших экранов скажут "Надо дать выбор юзеру. Пусть будет галка в меню - считать пробки на текущий момент или на время проезда ребра. А лучше плавную регулировку - при прогнозе менее N минут в пути игнорировать статистику, а больше - учитывать. А лучше - десять движков, типа эквалайзер!"

"Вечная история. Банк Империал".

[zoran]

Это, если маршрут на устройстве строить. А если маршрут на сервере строить, то вполне подъемная задача получается.

При этом никто не мешает оставить в устройстве "примитивный" (как сейчас) алгоритм на случай оффлайна.

[OlegCh]

Очень уж итерационный процесс получается...

И это тоже правильно

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

Вот поэтому я последние несколько месяцев езжу вообще без навигатора или с выключенными пробками, если дороги не знаю (((((

[IШIN]

Я как раз хотел ответить zoran-у, что непонятно, есть ли смысл городить два расчета маршрута (на серваке и на навике), сопрягать их между собой (чтобы не было резкой смены маршрута вдруг) и т.д., если движение с учетом пробок и без такового имеют разницу в 10-20 минут (и еще не факт, в чью пользу) на 3-часовом маршруте. (вспоминаем тесты от GPS-Club и тест AlexeyT4-Joss_etc.)

Можно просто отключить пробки.

Изменено 17 января, 2012 пользователем IШIN

[zoran]

Сделать два варианта по выбору и не будет никаких сложностей.

Будущее все равно за маршрутизацией на стороне сервера, Тогда можно будет в некоторой степени управлять потоками, точно знать кто куда поедет и сколько примерно машин будет в каждом конкретном месте и в конкретное будущее время.

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

Изменено 17 января, 2012 пользователем zoran

[Vodolazz]

Вот поэтому я последние несколько месяцев езжу вообще без навигатора или с выключенными пробками, если дороги не знаю (((((

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

[Vodolazz]

Сделать два варианта по выбору и не будет никаких сложностей.

Будущее все равно за маршрутизацией на стороне сервера, Тогда можно будет в некоторой степени управлять потоками, точно знать кто куда поедет и сколько примерно машин будет в каждом конкретном месте и в конкретное будущее время.

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

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

Я вижу только возможность использования статистики на опережение только для определенных "горячих" точек маршрута (развязки МКАД, ТТК, пересечение проспектов итд).

[zoran]

Под словом "сервер" я не имел ввиду железный сервер.

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

Я думаю, что это будущее, причем ближайшее.

[k1sa1974]

Под словом "сервер" я не имел ввиду железный сервер.

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

Я думаю, что это будущее, причем ближайшее.

И тогда в этом будущем будет введена абонентная плата на СГ . Содержание ЦОД - удовольствие не из дешевых.

[zoran]

Нет ничего зазорного, в том, что хороший сервис стоит денег. Но это тупиковый путь. Деньги надо щарабатывать как Гугл.

[Евгений Ш]

будет введена абонентная плата на СГ

Хм... А почему бы и не платить разумные деньги понятно за что?

[zoran]

В общем да. Если это поможет сделать программу хотябы с нормальным интерфейсом (7ю версию не видел), то почему нет?

[sergges]

Вот поэтому я последние несколько месяцев езжу вообще без навигатора или с выключенными пробками, если дороги не знаю (((((

навигатор с пробками абсолютно точно помогает и сокращает время проезда, тут без вариантов. Если еще и голову иногда включать, вообще замечательно. Конечно иногда возникают исключения, но тут ничего не поделать и ничего страшного. Девять раз помог- один не смог, меня устраивает такая помощь.

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