«Это получается переборный алгоритм. Я думаю, что вы не хотите, чтобы время построения маршрута увеличилось в 10 раз.»
Какой же это переборный алгоритм, если выбор всего из 3-4 вариантов? И время построения маршрута почти не изменится, поскольку разные варианты вычисляются параллельно.
Но ресурсоемкость увеличиться в эти 3-4 раза — вполне можно попробовать в качестве лабораторного эксперимента, чтобы понять велики ли получаемые преимущества в виде большей полноты и точности результатов. Если эффект будет заметен — тогда уже может встать вопрос ресурсов, оптимизации и т.п. (например, для «ночного» маршрута можно исключить из графа мелкие дороги)
Да, я имел ввиду сильно отличающиеся маршруты, например поехать через 3 кольцо или через МКАД, проехать по МКАД лишний участок и въехать в город по другому шоссе — такие варианты регулярно предлагает ваш маршрутизатор. При относительно длинном маршруте и наличии крупных магистралей — источником маршрутов являются треки самих пользователей, если уметь их выделять. Также и время движения по треку точнее определять интегрально, по живым трекам, а не усредняя короткие зашумленные участки.
Источником альтернативных значительно отличающихся маршрутов может быть ваш маршрутизатор запущенный на исторических данных за разные периоды времени (ночью, в выходной, в час пик, ...) — если получатся разные маршруты — каждый из них можно пересчитать для текущего прогноза скоростей и потом уже выбрать наилучший, или даже предложить пользователю пару вариантов, если он хочет. Маршрут проложенный по пустым дорогам, по-видимому, будет содержаться в большом количестве живых треков в любое время суток, и его надо всегда держать на готове в качестве альтернативы вычисленному.
Отдельное замечание по поводу маршрутов прокладываемых через МКАД — там если уж застрял то все, ни съехать ни объехать, в отличие от большинства внутригородских дорог. Для пользователя было бы полезно знать не только оценку времени движения, но и доверительный интервал такой оценки. Очевидно на разных маршрутах он разный, хоть какую-то грубую оценку хотелось бы уметь учитывать.
Почему же? Совсем честно учитывать прогноз при построении маршрута очень сложно, но ведь можно сделать постпроцессинг: для нескольких локально минимальных маршрутов которые выдал маршрутизатор на момент NOW — вычислить время в пути с учетом прогноза (прогноза скоростей на участках маршрута, в то время когда мы там окажемся), и выбрать лучший маршрут. Честно говоря, я думал что так и делается.
Как устроен краткосрочный прогноз на Яндекс.Пробках
Какой же это переборный алгоритм, если выбор всего из 3-4 вариантов? И время построения маршрута почти не изменится, поскольку разные варианты вычисляются параллельно.
Но ресурсоемкость увеличиться в эти 3-4 раза — вполне можно попробовать в качестве лабораторного эксперимента, чтобы понять велики ли получаемые преимущества в виде большей полноты и точности результатов. Если эффект будет заметен — тогда уже может встать вопрос ресурсов, оптимизации и т.п. (например, для «ночного» маршрута можно исключить из графа мелкие дороги)
Как устроен краткосрочный прогноз на Яндекс.Пробках
Источником альтернативных значительно отличающихся маршрутов может быть ваш маршрутизатор запущенный на исторических данных за разные периоды времени (ночью, в выходной, в час пик, ...) — если получатся разные маршруты — каждый из них можно пересчитать для текущего прогноза скоростей и потом уже выбрать наилучший, или даже предложить пользователю пару вариантов, если он хочет. Маршрут проложенный по пустым дорогам, по-видимому, будет содержаться в большом количестве живых треков в любое время суток, и его надо всегда держать на готове в качестве альтернативы вычисленному.
Отдельное замечание по поводу маршрутов прокладываемых через МКАД — там если уж застрял то все, ни съехать ни объехать, в отличие от большинства внутригородских дорог. Для пользователя было бы полезно знать не только оценку времени движения, но и доверительный интервал такой оценки. Очевидно на разных маршрутах он разный, хоть какую-то грубую оценку хотелось бы уметь учитывать.
Как устроен краткосрочный прогноз на Яндекс.Пробках