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