Instradamento ottimale delle mappe con Google Maps

Question

Esiste un modo per utilizzare l'API di Google Maps per recuperare un "ottimizzato" rotta data una serie di waypoint (in altre parole, una soluzione "abbastanza buona" al problema del venditore ambulante), oppure restituisce sempre la rotta con i punti nell'ordine specificato?

Answer 1

Li dà sempre in ordine.

Quindi penso che dovresti trovare la distanza (o il tempo) tra ogni coppia di punti, uno alla volta, quindi risolvere tu stesso il problema del commesso viaggiatore. Forse potresti convincere Google Maps ad aggiungere quella funzione però. Immagino che cosa costituisce un "abbastanza buono" la soluzione dipende da cosa stai facendo e da quanto deve essere veloce.

Answer 2

Esiste un'opzione nelle indicazioni API API di Google Maps, denominata optimWaypoints, che dovrebbe fare ciò che desideri. Tuttavia, può gestire solo fino a 8 waypoint.

In alternativa, esiste una libreria open source (licenza MIT) che puoi utilizzare con l'API di Google Maps per ottenere un percorso ottimale (fino a 15 posizioni) o abbastanza vicino a ottimale (fino a 100 posizioni).

Vedi http://code.google.com/p/google- mappe-tSP-solver /

Puoi vedere la libreria in azione su www.optimap.net

Answer 3

In un tipico problema TSP, si presume che si possa viaggiare direttamente tra due punti qualsiasi. Per le strade di superficie, questo non è mai il caso. Quando Google calcola un percorso tra due punti, esegue un'ottimizzazione euristica dello spanning tree e di solito si presenta con un percorso abbastanza vicino al percorso ottimale.

Per calcolare un percorso TSP, si dovrebbe prima chiedere a Google di calcolare la distanza in coppia tra ogni nodo nel grafico. Penso che questo richieda n * (n-1) / 2 calc. Si potrebbero quindi prendere quelle distanze ed eseguire un'ottimizzazione TSP su di esse.

OpenStreetMaps.org ha un'applicazione Java WebStart che può fare quello che vuoi. Naturalmente i calcoli vengono eseguiti sul lato client. Il progetto è open source e potrebbe valere la pena dare un'occhiata.

Stai cercando di trovare un percorso rettilineo ottimale tra le posizioni o il percorso di guida ottimale? Se vuoi solo ordinare i punti, se riesci a ottenere le coordinate GPS, diventa un problema molto semplice.

Answer 4

Appena trovato http://gebweb.net/optimap/ Sembra carino e facile. Versione online utilizzando google maps.

Answer 5

Google ha una soluzione pronta per il problema del venditore di viaggi. È OR-Tools (strumenti per la ricerca operativa di Google) che puoi trovare qui: https: // developers .google.com / ottimizzazione / routing / cucchiaino

Quello che devi fare sostanzialmente sono 2 cose:

• Ottieni le distanze tra i due punti usando l'API di Google Maps: https://developers.google.com/maps/documentation/distance-matrix/start

• Quindi fornirai le distanze in un array al OR-Tools e troverà un'ottima soluzione per te (per alcuni casi con milioni di nodi, le soluzioni sono state garantite entro l'1% di un tour ottimale).

Puoi anche notare che:

  

Oltre a trovare soluzioni per il commesso viaggiatore classico   Problema, OR-Tools fornisce anche metodi per tipi più generali di   TSP, tra cui:

•   

  Problemi di costo asimmetrici & # 8212; Il TSP tradizionale è simmetrico: la distanza dal punto A al punto B è uguale alla distanza dal punto B a   punto A. Tuttavia, il costo della spedizione degli articoli dal punto A al punto B   potrebbe non essere uguale al costo della spedizione dal punto B al punto A.   OR-Tools può anche gestire problemi con costi asimmetrici.

•   

  TSP di raccolta premi, in cui i vantaggi derivano dai nodi di visita

•   

  TSP con finestre temporali

Collegamenti aggiuntivi:

• Strumenti OR su Github: https://github.com/google/or-tools
• Inizia: https://developers.google.com/optimization/introduction/get_started