Блог

Главная - Вопросы по программированию - Каково практическое решение проблемы коммивояжера с использованием Карт Google?

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

#algorithm #google-maps #traveling-salesman

#алгоритм #google-карты #коммивояжер

Вопрос:

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

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

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

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

Комментарии:

1. Какое отношение к этому имеет Google Maps?

2. @Lior — у них может быть API, о котором я не знаю.

3. @Bart — вы прокомментировали, когда я редактировал — мой первый удар заключался в том, что это было O (N ^ 2), но O (N ^ 2) ! = N ^ 2.

4. @chrisdew, да, я только что видел твою правку. 🙂

5. @chrisdew, ты уже пробовал искать ключевые "tsp fast approximation" слова? Я создал несколько хороших статей.

Ответ №1:

Существует этот проект TSP, реализованный на JS http://code.google.com/p/google-maps-tsp-solver /

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

Ответ №2:

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

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

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

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

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

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

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

Ответ №3:

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

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

однако эти методы не являются точными на 100%.

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

Комментарии:

1. Я должен добавить, что со временем может потребоваться масштабирование до нескольких сотен мест.

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

Ответ №4:

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

Комментарии:

1. Спасибо, это выглядит полезным. Можно ли считать мою проблему евклидовой? Четыре точки в квадрате: время в пути между противоположными углами может быть больше, чем время в пути вдоль двух сторон. (например, вдоль этих двух краев проходит автомагистраль.)

2. Поскольку вы все равно ищете приближение, я считаю, что такими соображениями обычно пренебрегают. Если нет — ищите асимметричный TSP.

3. Спасибо, я собираюсь пойти с en.wikipedia.org/wiki /… сначала я рассматриваю более академические (пугающие) подходы, если это не работает достаточно хорошо.