Клуб API Карт

А можно ли задав несколько адресов, получить наиболее оптимальный маршрут по ним?

eugeny.shiryaev
18 декабря 2013, 20:03

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

 

Если это возможно, то каким образом?

7 комментариев
Подписаться на комментарии к посту

Такое можно сделать имея пару сотню супер-компьютеров.

А действительно ли нужны такие ресурсы?

Вчера через поиск нашел тему, где автор говорил, что сделал следующим образом - он ставил исходную точку, далее искал ближайшую к ней (по маршруту авто с учетом пробок). Вот эта тема - http://clubs.ya.ru/mapsapi/replies.xml?item_no=40892. Сдается мне он сделал это без сотен супер-компьютеров.

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

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

В частности проблема только в выборе первой точке - потом всегда можно выбирать точки из _нескольких_ ближайших, и начинать ветвление.

Если курьер в день должен посетить 10-20 мест - расчет пути займет максимум секунд 10, а по факту может и меньше одной.

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

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

там вроде после 18-й количество вариантов для перебора очень сильно возрастает

В общем случае на каждом этапе у тебя есть примерно три варианта. И чем "дальше" тем быстрее сходиться.

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

Ее можно вообще через r-tree решить - там "из коробки" близкие маршруты закластеризуются.