Клуб API Карт

Клуб API Карт

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

Пост в архиве.

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

 

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

7 комментариев
Авторизуйтесь, чтобы оставить комментарий
dimik
28 января 2016, 00:57

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

eugeny.shiryaev
28 января 2016, 00:57

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

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

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

thekashey
28 января 2016, 00:57

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

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

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

eugeny.shiryaev
28 января 2016, 00:57

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

thekashey
28 января 2016, 00:57

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

dimik
28 января 2016, 00:57

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

thekashey
28 января 2016, 00:57

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

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

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