Product Design, Manufacturing & Innovation Resources
Casa » In primo piano » Il problema del commesso viaggiatore, per l'industria e l'innovazione

Il problema del commesso viaggiatore, per l'industria e l'innovazione

Problema del commesso viaggiatore

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).

  • Per piccoli n (ad esempio n < 20), gli algoritmi esatti (forza bruta, programmazione dinamica) funzionano.
  • Tecniche approssimative/euristiche: nearest neighbor, algoritmo di Christofides, algoritmi genetici sono spesso utilizzati per istanze di grandi dimensioni.
  • Ma, in generale, non esiste un metodo rapido che garantisca la risposta migliore per tutti i casi.

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à visitatePossibili percorsi / combinazioni
36
424
5120
6720
75040
......
206 × 1016 (quasi 2 millenni se il calcolo di ogni percorso richiedesse un microsecondo)
25più dell'età del nostro universo se il calcolo di ogni percorso richiedesse un microsecondo.

Storia del problema del commesso viaggiatore

Una vasta distesa di conoscenze storiche, il viaggio del problema del commesso viaggiatore si dipana davanti a noi. In primo piano, una vasta mappa ornata di linee e percorsi, che traccia l'evoluzione di questa iconica sfida di ottimizzazione. Al centro, una raccolta di diagrammi analitici ed equazioni matematiche, gli strumenti che hanno plasmato la nostra comprensione di questo problema nel tempo. Sullo sfondo, un collage di pietre miliari e figure chiave, ognuna delle quali contribuisce al ricco arazzo della storia del problema del commesso viaggiatore. Illuminata da una calda luce di ispirazione vintage, questa scena cattura la profondità e la complessità di un problema che continua ad affascinare e ispirare ricercatori, logisti e risolutori di problemi.
Una vasta gamma di conoscenze storiche che si snodano lungo il percorso del problema del commesso viaggiatore. Il problema del commesso viaggiatore trova applicazioni reali nell'industria e nella logistica. Pianificazione delle consegne

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.

Log in →  or  Register (100% free) →

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.

Argomenti trattati: Problema del commesso viaggiatore, ottimizzazione, pianificazione dei percorsi, logistica, algoritmo, efficienza, riduzione dei costi, metodi euristici, programmazione dinamica, NP-hard, ottimizzazione combinatoria, algoritmi di approssimazione, ISO 9001, ISO 14001, ISO/IEC 27001, ISO 31000 e ISO 50001.

Contesto storico

1829
1850
1854
1854
1895
1899
1900
1828
1848
1850
1854
1884
1896
1900
1903

(se la data è sconosciuta o non rilevante, ad esempio "meccanica dei fluidi", viene fornita una stima approssimativa della sua notevole comparsa)

Articoli e post più popolari

Strumenti originali di alta qualità

Le immagini a grandezza naturale e i download sono disponibili, 100% gratuitamente, solo per i membri registrati.

> Login <