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

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

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

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

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

Он всегда дает их по порядку.

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

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

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

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

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

У 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, включая следующие:

• #P7#

• #P8#

• #P9#

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

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

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