Какое практическое решение проблемы коммивояжера с помощью Google Maps?

Question

Какое практическое решение проблемы коммивояжера с использованием Google Maps / геолокации / поиска маршрута?

Мне не нужно лучшее решение, в пределах 5% было бы хорошо.

Например, у меня есть 20 мест в Великобритании для посещения, в любом порядке.Это может потребовать масштабирования до сотен местоположений.

Какой алгоритм я могу использовать, учитывая, что я могу искать расстояния (но не хочу искать сотни расстояний)?

Answer 1

Этот проект TSP реализован в JS http://code.google.com/p/google-maps-tsp-solver/

Демонстрацию вы можете посмотреть здесь http://gebweb.net/optimap/

Answer 2

У Google действительно есть параметр в API их направлений, который оптимизирует маршрут как проблему коммивояжера:

• Документация по API: Использование путевых точек в маршрутах
• Введение и демонстрационный пост в блоге

Из документации (ключевая часть &waypoints=optimize:true|...):

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

http://maps.googleapis.com/maps/api/directions/json?origin=Adelaide,SA
  &destination=Adelaide,SA
  &waypoints=optimize:true|Barossa+Valley,SA|Clare,SA|Connawarra,SA|McLaren+Vale,SA
  &sensor=false

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

"waypoint_order": [ 1, 0, 2, 3 ]

Для одноразового использования, вероятно, проще использовать OptiMap в соответствии с рекомендациями @ Kunukn

Answer 3

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

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

эти методы не на 100% точны.

И даже если вы ищите все пути, у вас должно получиться не более 190 поисков.

Answer 4

Если вы ищете полиномиальное приближение для евклидова ТСП, было предложено несколько алгоритмов. Посмотрите здесь .