Immaginate un centro di distribuzione molto frequentato, in cui le macchine e i lavoratori si muovono in modo ottimale tra le varie postazioni di lavoro e di stoccaggio. I percorsi devono essere ben pianificati per rispettare i limiti di tempo e mantenere bassi i costi e altri fattori. Questa sfida è il cuore del cosiddetto problema del commesso viaggiatore (TSP). Non si tratta solo di applicazioni logistiche. Questo articolo esplora come il problema del commesso viaggiatore possa essere utilizzato nella vita reale e nella produzione. Si esamina come si possa migliorare la pianificazione dei percorsi in tutti i settori industriali.
Mentre questo problema è un classico della matematica pura e degli studi algoritmici, studiato anche nella logistica con un approccio più pratico, è quasi sconosciuto in altri settori industriali e produttivi.
Questo post si concentra in particolare su un algoritmo del nostro post "I 10 principali algoritmi e metodologie da conoscere in ingegneria".
Punti Chiave
- Il problema del commesso viaggiatore (TSP) consiste nel trovare il percorso più ottimizzato tra diversi punti.
- Questo problema ha iniziato a suscitare interesse negli anni 1930-1940.
- Aiuta le organizzazioni a migliorare l'efficienza e a ridurre i costi operativi, a limitare le risorse e a migliorare l'erogazione dei servizi.
- Il problema è ampiamente applicabile in diversi settori e industrie, non solo nella logistica e nei trasporti.
- Non appena i punti sono più di 12-20, il problema diventa troppo complesso per calcolare una soluzione perfetta.
- Sono stati inventati diversi algoritmi per trovare buone approssimazioni, quindi non quella perfetta.
Che cos'è il problema del commesso viaggiatore?
Il problema del commesso viaggiatore: trovare il modo più efficiente per un venditore di visitare varie città e tornare alla partenza. Deve visitare ogni città una sola volta, con l'obiettivo di ridurre la distanza totale al minimo possibile.
Per comprendere la definizione di TSP, è necessario sapere che il numero di percorsi cresce con l'aggiunta di altre città. Ad esempio, quattro città significano 24 percorsi possibili. L'aggiunta di altre città aumenta la sfida, portando a un numero eccessivo di potenziali percorsi da considerare.
Molte aziende, come quelle che operano nel settore della logistica, delle telecomunicazioni e della produzione, si trovano spesso ad affrontare questo problema. Una buona soluzione al problema del commesso viaggiatore potrebbe far risparmiare denaro e aumentare l'efficienza. Mostra come la ricerca teorica sulla matematica aiuti a risolvere i problemi della vita reale.
Perché è un problema?
Se ci sono n città, ci sono (n-1)!/2 tour unici (il /2 viene se il tour è un ciclo e le direzioni non contano).
Inoltre, lievi cambiamenti negli input (ad esempio, distanze o nuove città) alterano completamente il percorso ottimale, rendendo il problema molto sensibile e complesso da risolvere. | Città visitate | Possibili percorsi / combinazioni |
| 3 | 6 | |
| 4 | 24 | |
| 5 | 120 | |
| 6 | 720 | |
| 7 | 5040 | |
| ... | ... | |
| 20 | 6 × 1016 (quasi 2 millenni se il calcolo di ogni percorso richiedesse un microsecondo) | |
| 25 | più dell'età del nostro universo se il calcolo di ogni percorso richiedesse un microsecondo. |
Storia del problema del commesso viaggiatore

Il problema del commesso viaggiatore è nato all'inizio del 1900, grazie ad alcuni matematici intelligenti. William Rowan Hamilton e Karl Menger erano nomi importanti che ci hanno aiutato a capire come navigare in percorsi complessi. Si sono concentrati sul rendere più semplice la ricerca del percorso migliore.
Negli anni '30 si cominciò a definire più chiaramente il PST. Studiosi di Vienna e Harvard lavorarono insieme su questo tema. Cominciarono a vedere come poteva risolvere problemi reali, come migliorare i percorsi degli autobus scolastici. Questo ha fatto sì che un numero maggiore di persone si interessasse alla soluzione del PST.
Il TSP divenne utilissimo per le aziende, in particolare per quelle che si occupavano di spedizioni e trasporti. Negli anni '50 e '60, la RAND Corporation si fece avanti. Ha ideato modi intelligenti per affrontare il TSP, che sono diventati una parte fondamentale per rendere la logistica più fluida.
The rest of this article is reserved for members
To limit scraping bots (currently 40,000 hits per day!),
we had to restrict access to full articles and tools to registered members only.
to access all the rest.
Domande frequenti
Che cos'è il Traveling Salesman Problem (TSP)?
Il Traveling Salesman Problem (TSP) è un importante rompicapo. Si tratta di trovare il percorso più breve che visita ogni luogo una sola volta e ritorna alla partenza. Questo è fondamentale per le aziende che devono pianificare i percorsi in modo efficiente. La sfida principale è rappresentata dall'enorme numero di percorsi possibili, che cresce con ogni nuova località. Inoltre, problemi reali come il traffico e le scadenze rendono la pianificazione ancora più difficile.
Perché il TSP è considerato un problema NP-hard?
Il TSP è difficile perché il numero di percorsi potenziali aumenta esponenzialmente con ogni città aggiuntiva. Questo rende molto difficile trovare rapidamente il percorso migliore, soprattutto quando si aggiungono più di 20 località.
Quali sono le applicazioni più comuni della FST?
Il TSP viene utilizzato in molti settori, come ad esempio per rendere più efficienti i percorsi di consegna e gestire le catene di approvvigionamento. È utile anche nell'assistenza sanitaria per programmare le visite e per robotica per guidare i movimenti o nell'elettronica di produzione posizionare o testare piccoli componenti e percorsi in rame.
Che rapporto c'è tra la teoria dei grafi e gli algoritmi euristici e il TSP?
La teoria dei grafi è la matematica alla base del TSP. Utilizza i punti (vertici) per rappresentare le città e le linee (bordi) per i percorsi tra di esse. Questo aiuta a sviluppare metodi per risolvere efficacemente i problemi TSP. Gli algoritmi euristici sono scorciatoie intelligenti per risolvere i TSP. Aiutano a trovare rapidamente percorsi sufficientemente buoni, anche se non perfetti. Metodi come gli algoritmi del Vicino più vicino e di Greedy sono esempi comuni. Anche tecniche come l'annealing simulato e gli algoritmi genetici sono particolarmente utili per i problemi di grandi dimensioni.
In che modo il TSP influisce sull'efficienza della catena di fornitura?
Il TSP aumenta l'efficienza della supply chain affinando i percorsi di trasporto. Ciò comporta una riduzione dei costi, un migliore utilizzo delle risorse e un migliore coordinamento tra tutti i soggetti coinvolti. Nel settore sanitario, il TSP ottimizza il modo in cui vengono forniti i servizi di assistenza domiciliare e di emergenza. Assicura che le forniture mediche vengano consegnate tempestivamente, migliorando l'assistenza e la soddisfazione del paziente.
Glossario dei termini utilizzati
Deoxyribonucleic Acid (DNA): Molecola composta da due filamenti che formano una doppia elica, costituita da nucleotidi che codificano l'informazione genetica attraverso sequenze di quattro basi: adenina, timina, citosina e guanina. Costituisce il materiale ereditario nella maggior parte degli organismi viventi.
Printed Circuit Board (PCB): Una piastra piatta realizzata in materiale isolante che supporta e collega i componenti elettronici attraverso percorsi conduttivi, tipicamente ricavati da fogli di rame. Funge da base per l'assemblaggio dei circuiti e facilita i collegamenti elettrici tra i componenti.
Unmanned Aerial Vehicle (UAV): velivolo a pilotaggio remoto o autonomo progettato per varie applicazioni, tra cui sorveglianza, ricognizione e consegna, senza pilota umano a bordo. Opera tramite stazioni di controllo a terra o sistemi di automazione a bordo, spesso dotati di sensori e telecamere per la raccolta dei dati.
Very-large-scale Integration (VLSI): una tecnologia per creare circuiti integrati combinando da migliaia a milioni di transistor su un singolo chip, consentendo la miniaturizzazione di sistemi elettronici complessi e migliorando le prestazioni, l'efficienza energetica e la funzionalità in dispositivi come computer e smartphone.











