Оптимальная карта маршрутизации с Google Maps

Question

Есть ли способ с помощью API Карт Google вернуть «оптимизированный» маршрут с заданным набором точек (другими словами, «достаточно хорошее» решение проблемы коммивояжера), или он всегда возвращает маршрут с точками в указанном порядке?

Answer 1

В Google Maps API есть опция optimizeWaypoints, которая должна делать то, что вы хотите. Это может обрабатывать только до 8 путевых точек.

Кроме того, существует библиотека с открытым исходным кодом (лицензия MIT), которую можно использовать с API Карт Google для получения оптимального (до 15 местоположений) или довольно близкого к оптимальному (до 100 местоположений) маршрута.

См. http://code.google.com/p/google-maps-tsp-solver/

Вы можете увидеть библиотеку в действии на www.optimap.net

Answer 2

Это всегда приводит их в порядок.

Так что я думаю, вам нужно будет найти расстояние (или время) между каждой парой точек, по одному, а затем решить проблему коммивояжера самостоятельно. Может быть, вы могли бы убедить Google Maps добавить эту функцию, хотя. Я полагаю, что «достаточно хорошее» решение зависит от того, что вы делаете, и от того, насколько быстрым оно должно быть.

Answer 3

Только что нашел http://gebweb.net/optimap/ Выглядит красиво и просто. Онлайн версия с использованием карт Google.

Answer 4

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

Чтобы рассчитать маршрут TSP, сначала нужно попросить Google рассчитать парное расстояние между каждым узлом на графике. Я думаю, что это требует n * (n-1) / 2 Calcs. Затем можно взять эти расстояния и выполнить оптимизацию TSP на них.

OpenStreetMaps.org имеет Java WebStart приложение, которое может делать то, что вы хотите. Конечно расчеты ведутся на стороне клиента. Проект с открытым исходным кодом, и, возможно, стоит посмотреть.

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

Answer 5

У Google есть готовое решение для задачи Travel Travelman. Это OR-Tools (инструменты исследования операций Google), которые вы можете найти здесь: https://developers.google.com/optimization/routing/tsp

В основном вам нужно сделать 2 вещи:

• Получите расстояния между каждыми двумя точками, используя Google Maps API: https://developers.google.com/maps/documentation/distance-matrix/start

• Затем вы передадите расстояния в массиве в OR-Tools , и он найдет для вас очень хорошее решение (Для определенных случаев с миллионами узлов были найдены решения). гарантированно будет в пределах 1% от оптимального тура).

Вы также можете отметить, что:

В дополнение к поиску решений для классического коммивояжера Проблема, OR-Tools также предоставляет методы для более общих типов TSP, в том числе:

• Проблемы с асимметричной стоимостью. Традиционный TSP является симметричным: расстояние от точки A до точки B равно расстоянию от точки B до точка А. Однако стоимость доставки предметов из пункта А в пункт Б может не равняться стоимости их доставки из пункта B в пункт A. OR-Tools также может решать проблемы, которые имеют асимметричные затраты.

• TSP, собирающие призы, где выгоды от посещения узлов

• TSP с временными окнами

Дополнительные ссылки:

• OR-инструменты на Github: https://github.com/google/or-tools
• Начало работы: https://developers.google.com/optimization/introduction/get_started