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 fulcro della cosiddetta "storia". problema del commesso viaggiatore (TSP). Non si tratta solo di applicazioni logistiche. Questo pezzo 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.
Perché è un problema NP-Hard?
Il problema del commesso viaggiatore è un rompicapo difficile in informatica. È famoso come problema NP-hard perché è davvero difficile da risolvere, in quanto cresce esponenzialmente più velocemente di quanto qualsiasi computer possa gestire se ci sono molte città.
Che cos'è un problema "NP-hard": In informatica e nella teoria della complessità computazionale, "NP" sta per Tempo Polinomiale Non Deterministico. Un problema NP-hard è almeno altrettanto difficile dei problemi più difficili in NP, il che significa che ogni problema in NP può essere ridotto in tempo polinomiale ad esso. A differenza dei problemi NP-completi che può essere verificato in tempo polinomiale, Tnon esiste un algoritmo noto che risolva problemi NP-hard in tempo polinomiale.
Per questo motivo, gli esperti utilizzano scorciatoie speciali e ipotesi intelligenti. Questi trucchi li aiutano a trovare percorsi abbastanza buoni senza dover ricorrere a quantità impossibili di potenza di calcolo per ottenere una soluzione decente che funzioni abbastanza bene nella vita reale. Nel capitolo seguente sono riportati alcuni di questi approcci che li aiutano a gestire l'enorme numero di percorsi possibili.
Applicazioni industriali
Il problema del commesso viaggiatore aiuta diversi settori industriali migliorare cose come i percorsi e i processi. Molti settori come la logistica, i trasporti e la produzione utilizzano la TSP per semplificare il loro lavoro. Le soluzioni approssimate TSP e le loro varianti sono utilizzate in:
TrasportoGli usi più simili al problema del venditore originale:
| Instradamento
|
You have read 50% of the article. The rest is for our community. Already a member? Accedi
(and also to protect our original content from scraping bots)
Comunità Innovazione.mondo
Accedi o registrati (100% free)
Visualizza il resto di questo articolo e tutti i contenuti e gli strumenti riservati ai soci.
Solo veri ingegneri, produttori, designer, professionisti del marketing.
Nessun bot, nessun hater, nessuno spammer.
FAQ
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?
TSP is used in many areas, like making delivery routes more efficient and managing supply chains. It’s also helpful in healthcare for scheduling visits and in robotica for guiding movements or in manufacturing electronics positioning or testing small components and copper routes.
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.
Post correlati
La metodologia SCAMPI per la valutazione CMMI in dettaglio
Rapporto rischio-beneficio nella valutazione del rischio
Le migliori barzellette sugli ingegneri (e designer, creatori, addetti al marketing...)
I 5 livelli di integrazione del modello di maturità delle capacità (CMMI)
Internet industriale delle cose (IIoT)
Concept Explorer™ di Innovation.world