Traveling Salesman Problem e la sua applicazione nella logistica

Traveling Salesman Problem si riferisce a una delle questioni più comuni nella logistica. Ma cos’è il problema del commesso viaggatore?

Traveling Salesman Problem: cos’è?

Il problema del commesso viaggatore rientra nel campo della ricerca operativa e dell'informatica. Il suo obiettivo è selezionare l’itinerario più efficiente per visitare una serie di destinazioni una sola volta. In questo modo si può ottenere il massimo risparmio di risorse al momento di effettuare una consegna di merci o si va, ad esempio, a visitare un cliente.

Gli algoritmi del Traveling Salesman Problem vengono impiegati nella pianificazione dei percorsi e nell'ottimizzazione dei servizi dei corrieri. Questo si deve al suo potenziale di incrementare la redditività e la sostenibilità delle imprese percorrendo distanze più brevi, riducendo anche le emissioni di gas serra.

Il problema del commesso viaggiatore ha attirato molto l’attenzione dell'informatica teorica nel corso degli anni perché, sebbene semplice da descrivere, è difficile da risolvere. Il numero di sequenze che potrebbero risolverlo cresce esponenzialmente con il numero di città o punti di consegna da visitare, motivo per cui gli informatici utilizzano algoritmi di approssimazione per trovare il tragitto più breve e con il costo più basso. Condivideremo più avanti alcuni dei metodi più usati.

Origine del Traveling Salesman Problem

La storia più recente del problema del commesso viaggiatore è iniziata nel XX secolo con Karl Menger. L’economista austriaco presentò il problema al matematico Hassler Whitney, che anni dopo lo avrebbe presentato all’Università di Princeton (Stati Uniti). Lì, A.W. Tucker e Merril Flood discussero la sua applicabilità nel contesto del trasporto scolastico del New Jersey.

Come risolvere il problema del commesso viaggiatore?

Esistono due modi principali per rispondere alla domanda posta dal problema del commesso viaggiatore attraverso l’uso di algoritmi:

1. Algoritmi esatti. Questo approccio ricerca la soluzione in maniera esaustiva. Tuttavia, spesso non è fattibile a causa del lungo tempo di calcolo richiesto.
2. Algoritmi euristici. Questi metodi possono ottenere risposte approssimative in meno tempo.

Dettagliamo di seguito gli algoritmi euristici.

Metodo della forza bruta

Consiste nel calcolare e confrontare tutti gli itinerari possibili per poi scegliere quello più breve e conveniente. È utile solo in scenari semplici.

Sistema branch and bound

La tecnica branch and bound (in italiano ramificare e limitare) comincia con la scelta di un percorso iniziale per poi analizzarne sistematicamente le variazioni e, ogni volta che viene aggiunto un nodo all’itinerario, l'algoritmo calcola la distanza da percorrere e la confronta con l'opzione precedente. Se il tragitto totale si allunga, questa alternativa viene eliminata dal sistema di ramificazione e non è più considerata una soluzione fattibile.

Pertanto, l’algoritmo scarta diverse possibilità e si avvicina a quella più redditizia per l’azienda di trasporti o il team commerciale che viaggerà. Il processo continua finché tutti i percorsi non vengono esaminati e quello più breve viene identificato come ottimale.

Metodo del vicino più prossimo

L'implementazione di questo algoritmo inizia in un luogo casuale. Da lì, si trova il nodo più vicino e si aggiunge al sequenziamento. Questa azione viene ripetuta dal nodo successivo finché tutte le città o destinazioni non vengono incluse nell'itinerario. Dopo di che, si torna al punto di partenza per chiudere il ciclo. Sebbene possa sembrare il modo più semplice per risolvere il problema del commesso viaggiatore, questo approccio non è sempre il più appropriato.

Applicazioni del Traveling Salesman Problem

Anche se trovare la risposta più adeguata può essere complicato, gli approcci al problema del commesso viaggiatore vengono impiegati in tutti i tipi di settori:

1. Robotica e automazione. Razionalizzare i movimenti di robot e macchine aiuta a diminuire il consumo delle batterie e a migliorarne l’efficienza. Ad esempio, il software per la gestione delle flotte degli AMR, o robot mobili autonomi, rileva quale robot è più vicino al punto di origine del movimento da effettuare per ridurre al minimo i tempi di esecuzione e aumentare la durata delle batterie.
2. Fabbricazione e pianificazione della produzione. Questa tecnica può essere applicata anche ad ambienti produttivi, dove il tragitto più breve potrebbe consentire di verificare tutte le macchine per completare le attività di manutenzione con un impatto minimo sul piano della produzione.
3. Logistica e trasporti. Esistono molteplici applicazioni del problema del commesso viaggiatore nella logistica:
   • Trasporto della merce. Un'azienda di trasporti utilizza il Traveling Salesman Problem per raggiungere tutte le città dove un camion deve effettuare le consegne nel più breve tempo possibile. Di conseguenza, finisce prima e può fare più viaggi.
   • Trasporto di passeggeri. Allo stesso modo, le compagnie di autobus o altri mezzi di trasporto possono trovare l'opzione più rapida per completare un viaggio, offrirla ai propri clienti e soddisfare le loro aspettative.
   • Assistenza tecnica. Le aziende di servizi possono generare il percorso che copre tutte le installazioni da controllare, ottimizzando i tempi dei propri tecnici.

Altri fattori che influiscono sul Traveling Salesman Problem

Trovare un algoritmo che risolva tutti i problemi del commesso viaggiatore è difficile, poiché esistono alcune limitazioni. Ad esempio, questo metodo non considera eventi imprevisti come:

• Visite programmate ad un orario specifico o accordate all'ultimo minuto
• Ingorghi causati dal traffico
• Orari restrittivi in alcune destinazioni
• Modifiche del tragitto dovute a cause di forza maggiore

Traveling Salesman Problem nel magazzino

Oltre che per velocizzare i viaggi su strada, il problema del commesso viaggiatore trova applicazione anche all’interno dei magazzini e dei centri di distribuzione. È così possibile perfezionare le operazioni di picking affinché gli operatori effettuino il minor numero di movimenti preparando il maggior numero di ordini. Un software di gestione magazzino controlla e coordina i movimenti e i processi per moltiplicare la redditività.

Se desideri ottimizzare la tua logistica, in Mecalux possiamo aiutarti. Abbiamo sviluppato Easy WMS per potenziare le prestazioni dei magazzini manuali e automatici e centinaia di clienti lo usano già ogni giorno nei loro cicli operativi. Le sue funzionalità sono vitali per il magazzino. Contattaci e ti consiglieremo le soluzioni di stoccaggio più adatte alla tua attività.