Una delle attività di ottimizzazione più comuni è il percorso dei veicoli, in cui l'obiettivo è trovare i percorsi migliori per un parco veicoli che visitano una serie di località. Di solito, "migliori" significa i percorsi con la distanza totale o il costo minimo. Ecco alcuni esempi di problemi di routing:
- Una società di consegna pacchi vuole assegnare percorsi ai conducenti che devono effettuare le consegne.
- Una società di TV via cavo vuole assegnare percorsi ai tecnici per effettuare chiamate di servizi residenziali.
- Una società di ride sharing vuole assegnare ai conducenti dei percorsi per far salire e scendere i passeggeri.
Il più famoso problema di percorso è il Traveling Commercial Problem (TSP): trova il percorso più breve per un venditore che deve visitare i clienti in luoghi diversi e tornare al punto di partenza. Un TSP può essere rappresentato da un grafico, in cui i nodi corrispondono alle posizioni e i bordi (o archi) indicano un viaggio diretto tra le posizioni. Ad esempio, il grafico qui sotto mostra un TSP con solo quattro sedi, etichettate A, B, C e D. La distanza tra due posizioni qualsiasi è data dal numero accanto al bordo che le unisce.
Calcolando le distanze di tutti i percorsi possibili, puoi vedere che il
percorso più breve è ACDBA, per il quale la distanza totale è 35 + 30 + 15 + 10 = 90.
Il problema si fa più difficile quando ci sono più località. Nell'esempio precedente, ci sono solo sei route. Se invece ci sono dieci località (senza contare il punto di partenza), il numero di route sarà 362880. Per 20 località, il numero passa a 2432902008176640000. Una ricerca esaustiva di tutte le route possibili è garantita per trovare quella più breve, ma questo non è trattabile dal punto di vista computazionale per tutte le località tranne per i piccoli gruppi. Per i problemi più grandi, sono necessarie tecniche di ottimizzazione per cercare in modo intelligente lo spazio delle soluzioni e trovare una soluzione ottimale (o quasi ottimale).
Una versione più generale del TSP è la VRP, in cui esistono più veicoli. Nella maggior parte dei casi, i VRP hanno dei vincoli: ad esempio, i veicoli possono avere capacità per il peso o il volume massimi di articoli che possono trasportare oppure i conducenti potrebbero dover visitare le sedi durante gli intervalli di tempo specificati richiesti dai clienti.
OR-Tools è in grado di risolvere molti tipi di VRP, tra cui:
- "Traveling Commercial Problem" (Problema con il venditore in viaggio) è il classico problema dei percorsi in cui è presente un solo veicolo.
- Problema di routing dei veicoli, una generalizzazione del TSP con più veicoli.
- VRP con limiti di capacità, in cui i veicoli hanno la capacità massima per gli articoli che possono trasportare.
- VRP con finestre temporali, in cui i veicoli devono visitare le località negli intervalli di tempo specificati.
- VRP con vincoli di risorse, ad esempio spazio o personale per caricare e scaricare i veicoli nel deposito (il punto di partenza dei percorsi).
- VRP con visite diminuite, in cui i veicoli non devono visitare tutte le località, ma devono pagare una penalità per ogni visita che viene ignorata.
Limitazioni alla risoluzione dei problemi relativi ai percorsi dei veicoli
I problemi di percorso dei veicoli sono intrinsecamente intrattabili: il tempo necessario per risolverli cresce in modo esponenziale insieme alle dimensioni del problema. Per problemi sufficientemente grandi, potrebbero essere necessari anni con OR-Tools (o qualsiasi altro software di routing) per trovare la soluzione ottimale. Di conseguenza, OR-Tools a volte restituisce soluzioni buone, ma non ottimali. Per trovare una soluzione migliore, modifica le opzioni di ricerca del risolutore. Per un esempio, consulta Modifica della strategia di ricerca.