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

Question

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

Answer 1

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

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

Answer 2

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

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

См. http://code.google.com/p/google-. карт-ч.л. решатель /

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

Answer 3

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

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

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

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

Answer 4

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

Answer 5

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

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

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

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

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

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

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

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

• Чайная ложка с временными интервалами

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

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