API di Ottimizzazione Percorso

La navigazione curva per curva (l'API Directions) calcola il percorso più veloce tra le tappe nell'ordine specificato. L'ottimizzazione del percorso riordina queste tappe per trovare la sequenza che minimizza il tempo di viaggio o la distanza totale. Usare prima l'API Optimize Route per ottenere il miglior ordine delle tappe, poi passare quella lista ordinata all'API Directions per le istruzioni di navigazione dettagliate.

L'API supporta fino a 200 tappe per richiesta di ottimizzazione. Per la maggior parte degli scenari di consegna last-mile e servizio sul campo questo è più che sufficiente. Le richieste con meno di 20 tappe tipicamente restituiscono risultati in meno di 100 ms. I lavori più grandi con 100-200 tappe vengono completati entro 1-2 secondi.

Una finestra temporale è un vincolo di consegna o servizio che specifica l'orario più presto e più tardi in cui una tappa deve essere visitata. Ad esempio, un cliente disponibile dalle 09:00 alle 12:00. L'ottimizzatore rispetta tutte le finestre temporali minimizzando comunque la distanza totale del percorso. Le tappe che non possono essere raggiunte entro la loro finestra temporale vengono segnalate nella risposta per poterle riassegnare o riprogrammare.

Sì. Passare un elenco di veicoli, ognuno con la propria posizione di partenza, capacità e orari di turno. L'ottimizzatore distribuisce le tappe sull'intera flotta, bilanciando il carico di lavoro e minimizzando la distanza totale della flotta. È possibile combinare tipi di veicoli con capacità diverse nella stessa richiesta.

Sì. Specificare un deposito fisso o una posizione di partenza per veicolo. È anche possibile impostare una posizione di arrivo fissa, oppure permettere all'ottimizzatore di terminare all'ultima tappa per minimizzare i chilometri a vuoto verso la base. I percorsi di andata e ritorno che iniziano e terminano nello stesso deposito sono anch'essi supportati.

L'API usa una combinazione di euristiche di costruzione e metaeuristiche di ricerca locale per risolvere il Problema di Instradamento dei Veicoli (VRP), una generalizzazione del Problema del Commesso Viaggiatore. Per dimensioni pratiche della flotta, la qualità della soluzione è entro l'1-3 percento dall'ottimo teorico, restituita in tempi di risposta inferiori al secondo.