Optimal mapear roteamento com o Google Maps

Question

Existe uma maneira usando a API do Google Maps para obter de volta uma rota "otimizado" dado um conjunto de waypoints (em outras palavras, uma solução "suficientemente bom" para o problema do caixeiro viajante), ou ele sempre retornará o rota com os pontos na ordem especificada?

Answer 1

Ele sempre dá-los em ordem.

Então, eu acho que você tem que saber a distância (ou tempo) entre cada par de pontos, um de cada vez, em seguida, resolver o problema do caixeiro viajante si mesmo. Talvez você possa convencer o Google Maps para adicionar esse recurso embora. Eu acho que o que constitui uma solução "suficientemente bom" depende do que você está fazendo e quão rápido ele precisa ser.

Answer 2

Existe uma opção no Google Maps API DirectionsRequest chamado optimizeWaypoints, que deve fazer o que quiser. Isso só pode lidar com até 8 pontos de interesse, no entanto.

Como alternativa, existe uma fonte aberta (licença MIT) biblioteca que você pode usar com a API do Google Maps para obter uma óptima (até 15 locais) ou muito perto de ideal (até 100 locais) rota.

http://code.google.com/p/google- mapas-tSP-solver /

Você pode ver a biblioteca em ação em www.optimap.net

Answer 3

Em um problema TSP típico, o pressuposto é um pode viajar directamente entre dois pontos quaisquer. Para estradas de superfície, isso nunca é o caso. Quando o Google calcula uma rota entre dois pontos, ele faz uma otimização Spanning Tree heurística, e normalmente vem com um bastante perto de caminho ideal.

Para calcular uma rota TSP, um primeiro teria que pedir ao Google para calcular a distância de pares entre cada nó no gráfico. Eu acho que isso requer n * (n-1) / 2 calcs. Pode-se, em seguida, tomar essas distâncias e realizar uma otimização TSP sobre eles.

OpenStreetMaps.org tem um Java WebStart aplicação que pode fazer o que quiser. É claro que os cálculos estão sendo lado do cliente prazo. O projeto é de código aberto, e pode valer a pena dar uma olhada.

Você está tentando encontrar um caminho linear ideal entre locais, ou a melhor rota dirigindo? Se você quiser apenas para ordenar os pontos, se você pode obter as coordenadas GPS, torna-se um problema muito fácil.

Answer 4

Apenas encontrada http://gebweb.net/optimap/ Parece bom e fácil. versão on-line usando o google maps.

Answer 5

O Google tem uma solução pronta para Salesman viagem Problema. É OU-Tools (ferramentas de Operações de Pesquisa do Google) que você pode encontrar aqui: https: // desenvolvedores .google.com / optimização / routing / tSP

O que você precisa fazer é basicamente 2 coisas:

• Obter as distâncias entre cada dois pontos usando o Google Maps API: https://developers.google.com/maps/documentation/distance-matrix/start

• Em seguida, você vai alimentar as distâncias em uma matriz para a OR-Ferramentas e vai encontrar um muito-boa solução para você (para certos casos, com milhões de nós, foram encontradas soluções a garantia de ser dentro de 1% de um óptimo tour).

Você também pode notar que:

Além de encontrar soluções para o Caixeiro Viajante clássico Problema, OR-Tools também fornece métodos para tipos mais gerais de TSPs, incluindo o seguinte:

• problemas de custos assimétricas - O tradicional TSP é simétrica: a distância do ponto A ao ponto B é igual à distância do ponto B para ponto A. No entanto, o custo do transporte de itens de ponto A ao ponto B pode não ser igual ao custo de enviá-las do ponto B para o ponto A. OU-Tools também pode lidar com problemas que têm custos assimétricos.

• TSPs, onde os benefícios revertem a partir dos nós que visitam Prêmio coleta

• TSP com janelas de tempo

Outras ligações:

• OR-ferramentas no Github: https://github.com/google/or-tools
• Get Started: https://developers.google.com/optimization/introduction/get_started