Клуб API Карт

Построение маршрута "Кратчайший путь объехать несколько точек"

MurzNN
1 марта 2013, 10:51

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

Например машина выезжает со склада и должна привезти товар в 5 разных точек в любом порядке.

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

Существует ли какой-то способ вывести в Яндекс.Картах машрут объезда всех этих точек в оптимальном порядке, чтобы был наиболее кратчайший путь всего маршрута?

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

Присоединяюсь к вопросу. Для 5ти точек - это уже 120 вариантов маршрута. А если точек становится больше, то кол-во маршрутов становится запредельным, а следовательнг и кол-во запросов к яндесу.

Готового решения для этого нет. Может быть идеей подклитесь, чтобы перебором не заниматься.

Эта задача известна как "задача коммивояжера" и относится к классу NP-полных. при кол-ве городов > 18 кол-во вариантов будет порядка нескольких миллиардов. Так что если у вас есть парочка суперкомпьютеров, можно попробовать перебор

В идеальном случае конечно да, нужно много мощностей чтобы всё это перебирать и считать, особенно если прокладывать маршут и высчитывать всё до километра.

 

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

 

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

Кстати, ведь при просчете кратчайшего машрута от 1 точки к другой Яндекс также перебирает кучу возможных вариантов проезда среди тысячи возможных чтобы найти кратчайший, это же он сделать успевает довольно быстро ;)

Посмотрел тут как дела у навигаторов, и выяснил что Garmin эту задачу как-то уже умеет решать:

http://www.gps-piter.ru/description/nuvi700.htm

- решение "задачи коммивояжера" (до 200 пунктов назначения в одном маршруте)

и это всё на довольно дохленьком процессоре 2007 года.

Спасибо. Есть над чем подумать.

Вот тут все просто: http://poncy.ru/logist/

Супер, то что надо!! Благодарю за ссыку, добавил фзакладке =)

 

Еще один полезный сервис по оптимизации маршрутов - http://zig-zag.org/

Хотим поделится с вами нашими методами оптимизации маршрута с помощью навигатора  http://courieru.ru/optimizatsiya-marshruta/optimizatsiya-marshruta-v-yandeks-navigatore.html
Обновлено 20 января, 01:30