Il Problema del Commesso Viaggiatore: Algoritmi di Soluzione e Applicazioni

Il Traveling Salesman Problem (TSP), noto in italiano come problema del commesso viaggiatore, rappresenta una delle sfide più comuni nel campo della logistica. Questo problema rientra nell'ambito della ricerca operativa e dell'informatica, con l'obiettivo di individuare l'itinerario più efficiente per visitare una serie di destinazioni una sola volta.

Il problema del commesso viaggiatore ha attirato molta attenzione da parte dell'informatica teorica nel corso degli anni. La ragione risiede nella sua apparente semplicità nella descrizione, che contrasta con la difficoltà intrinseca nella sua risoluzione. Il numero di sequenze che potrebbero potenzialmente risolverlo cresce esponenzialmente con l'aumentare del numero di città o punti di consegna da visitare. Per questo motivo, gli informatici ricorrono ad algoritmi di approssimazione per individuare il percorso più breve e con il costo più basso.

Storia del Problema del Commesso Viaggiatore

La storia più recente del problema del commesso viaggiatore ha avuto inizio nel XX secolo grazie a 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'espressione "traveling salesman problem" apparve per la prima volta nel 1949 in un articolo della matematica americana Julia Robinson. Da quel momento, il TSP è diventato uno dei problemi più studiati nella ricerca operativa, venendo riformulato come problema di programmazione lineare da George Dantzig, Delbert Ray Fulkerson e Selmer Johnson.

Formulazione Matematica del Problema

Una possibile formulazione del problema è la seguente: un rappresentante di pellame deve spostarsi tra \(n\) città per vendere la sua merce. Partendo da una delle città, il commesso viaggiatore deve visitarle tutte una ed una sola volta per poi tornare al punto di partenza. Conoscendo le distanze tra le città, qual è la strada che minimizza i chilometri percorsi dal commesso?

Siamo portati ingenuamente a risolverlo elencando tutti i possibili percorsi. A questo punto confrontiamo le distanze ed otteniamo la più breve. Ma facciamo due conti. Partiamo da n città. Quindi la città di partenza può essere scelta tra tutte le \(n\) da visitare. Fissata questa prima, la seconda città può essere scelta tra le \(n-1\) restanti, la terza tra le \(n-2\) restanti. Così procedendo, abbiamo un’unica città per l’ultima scelta. Tutto risolto? In apparenza sì. Purtroppo la funzione fattoriale cresce più velocemente di qualsiasi esponenziale. Quindi un algoritmo che risolve il problema del commesso viaggiatore seguendo questa strategia avrebbe una durata più che esponenziale. Si tratta di tempi lunghissimi. In sostanza non otterremo mai la risposta.

Leggi anche: Il dramma di Willy Loman spiegato

Supponiamo che ogni tentativo duri \(1\) millesimo di secondo. Per \(7\) città abbiamo bisogno di \(5\) secondi per verificare tutti i possibili percorsi. Già con \(10\) abbiamo bisogno di più di un’ora. E se le città sono \(20\) servono \(77\) milioni di anni. E se consideriamo un supercomputer che valuta ogni percorso in \(10^-{12}\) secondi?

Algoritmi di Soluzione

Esistono diverse tipologie di algoritmi per affrontare il problema del commesso viaggiatore:

Algoritmi esatti: Questo approccio ricerca la soluzione in maniera esaustiva. Consiste nel calcolare e confrontare tutti gli itinerari possibili per poi scegliere quello più breve e conveniente.
Algoritmi euristici: 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.

Tecniche di Ottimizzazione

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. Pertanto, l’algoritmo scarta diverse possibilità e si avvicina a quella più redditizia per l’azienda di trasporti o il team commerciale che viaggerà.

L’algoritmo di Held-Karp (1962) descrive il percorso più breve in un tempo esponenziale compreso tra \(2^n\) e \(3^n\). A livello computazionale sono stati risolti anche problemi più grandi utilizzando, tra gli altri, l’algoritmo di Christofides. Ci sono classi di algoritmi che scartano alcuni percorsi apriori a causa della loro non-ottimalità. È il caso degli algoritmi di branch and bound e degli algoritmi di branch and cut. In un lavoro del 2014 è risolto il problema TSP con \(100.000\) città.

Applicazioni del Problema del Commesso Viaggiatore

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. Gli algoritmi del Traveling Salesman Problem vengono impiegati nella pianificazione dei percorsi e nell'ottimizzazione dei servizi dei corrieri.

Le applicazioni del TSP sono molteplici e riguardano diversi settori:

Logistica e trasporti: 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.
Robotica e automazione: Razionalizzare i movimenti di robot e macchine aiuta a diminuire il consumo delle batterie e a migliorarne l’efficienza.
Fabbricazione e pianificazione della produzione.
Trasporto di passeggeri.
Assistenza tecnica.

Esempio di Ciclo Hamiltoniano

commesso viaggiatore, problema del (in inglese Travelling Salesman Problem, o più brevemente tsp) problema che consiste nella ricerca su un grafo di un particolare ciclo hamiltoniano che rende minimo un determinato parametro. Il problema è proposto come ricerca del percorso di minimo costo in un insieme di città e di vie di comunicazione che le collegano, rappresentate rispettivamente come nodi e archi di un grafo; assegnato a ciascun arco un costo di percorrenza, si chiede di trovare il ciclo hamiltoniano di costo complessivo minimo.

Un altro ciclo hamiltoniano di lunghezza 7 è dato da A, D, B, C, A. L’algoritmo per la risoluzione del problema è un cosiddetto algoritmo a esaurimento perché deve esaminare tutte le possibili scelte: le successioni di scelte via via costruite sono successioni di nodi adiacenti diversi tra loro; la successione è un ciclo hamiltoniano se contiene tutti i nodi del grafo e l’ultimo nodo coincide con il primo; tra questi va poi scelto quello o quelli di peso minimo.

La ricerca dei cicli hamiltoniani attraverso tutte le possibili permutazioni dei nodi del grafo può essere realizzata attraverso una procedura ricorsiva; è una ricerca esaustiva, ma può richiedere enormi risorse in termini di tempo di calcolo.

Sfide e Limiti

Trovare un algoritmo che risolva tutti i problemi del commesso viaggiatore è difficile, poiché esistono alcune limitazioni.

Ottimizzazione Logistica con Easy WMS

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.

Il Futuro del Problema del Commesso Viaggiatore

Il problema del commesso viaggiatore continua ad impegnare i matematici ed informatici. Non possiamo sapere se ci sarà mai un algoritmo efficienti o se questo algoritmo semplicemente non esiste. La risoluzione del problema avrebbe grosse ricadute, basta pensare ai problemi di logistica dei nostri tempi.

TAG: #Viaggi #Viaggiatore