Il "Problema del commesso viaggiatore" o "The Traveling Salesman Problem (TSP)" è un problema della Teoria dei Grafi. Nello specifico si riferisce alla necessità di individuare il percorso di minore lunghezza che un ipotetico commesso viaggiatore deve seguire per visitare tutte le città (contenute in un elenco) una e una sola volta (eventualmente tornando alla città di partenza).
PROBLEMA:
E' molto utile saper risolvere questo tipo di problema in quanto esso può far risparmiare chilometri, il che significa anche avere un minore tempo di percorrenza e anche sostenere minori costi di carburante.
Tanto più numerose sono le città o i luoghi da visitare, quanto più complesso da risolvere può diventare il problema!
SOLUZIONI:
La prima soluzione (semiseria) e indicata da uno studente è stata di acquistare una Lamborghini Veneno - Roadster da 355 Km/h (!) per velocizzare gli spostamenti.
E' chiaro che con quest'auto in dotazione non si deve insistere troppo nel riuscire a "risparmiare carburante" 😜
Per gli amanti dei motocicli invece viene suggerita la moto a guida autonoma MOTOROiD di YAMAHA, bellissima e futuristica 😜😜oltre che dotata di Intelligenza Artificiale [Fonte]
La seconda soluzione (seria) è stata di utilizzare appunto la teoria dei grafi, dove per grafo si intende una struttura costituita da:
Un grafo viene raffigurato da punti, che rappresentano i nodi; i collegamenti tra i nodi sono rappresentati da segmenti o curve che collegano due nodi; nel caso di un grafo orientato, il verso degli archi è indicato da una freccia.
E' molto utile saper risolvere questo tipo di problema in quanto esso può far risparmiare chilometri, il che significa anche avere un minore tempo di percorrenza e anche sostenere minori costi di carburante.
Tanto più numerose sono le città o i luoghi da visitare, quanto più complesso da risolvere può diventare il problema!
SOLUZIONI:
La prima soluzione (semiseria) e indicata da uno studente è stata di acquistare una Lamborghini Veneno - Roadster da 355 Km/h (!) per velocizzare gli spostamenti.
E' chiaro che con quest'auto in dotazione non si deve insistere troppo nel riuscire a "risparmiare carburante" 😜
 |
| Lamborghini Veneno Roadster |
 |
| MOTOROiD by YAMAHA |
La seconda soluzione (seria) è stata di utilizzare appunto la teoria dei grafi, dove per grafo si intende una struttura costituita da:
- nodi (ad esempio le città)
- collegamenti orientati cioè dotati di direzione e verso tra i nodi, oppure collegamenti non orientati cioè dotati di una direzione, ma non dotati di un verso (ad esempio le strade)
- pesi per ogni collegamento (ad esempio i KM di distanza tra due città)
Un grafo viene raffigurato da punti, che rappresentano i nodi; i collegamenti tra i nodi sono rappresentati da segmenti o curve che collegano due nodi; nel caso di un grafo orientato, il verso degli archi è indicato da una freccia.
 |
| Esempio di un grafo pesato e orientato |
Pensiamo ad esempio al seguente percorso:
- Partenza e Arrivo a: Milano
- Città intermedie da visitare nel percorso: Savona, Torino, Venezia, Parma, Genova
Per ogni coppia di queste città esistono molteplici percorsi di collegamento, ad esempio pensiamo a tutti le strade e autostrade che uniscono Milano e Savona. La teoria de grafi permette di individuare il percorso stradale con la minore distanza fra queste due città. Poi si riapplica la stessa procedura per individuare il percorso minimo fra Savona e Torino, e così via.
In questo caso è bene precisare che il percorso minimo può essere di due tipi:
1) "RELATIVO" quando l'ordine di visita delle città intermedie è vincolato è quindi non può essere variato. Da Milano vado a Savona, come richiesto dal vincolo e poi per lo stesso motivo vado per forza a Torino ecc.
2) "ASSOLUTO" quando l'ordine di visita delle città intermedie NON è vincolato è quindi può essere variato a piacimento per individuare ad esempio il percorso più breve (o più economico, bello, ecc. ). Da Milano vado verso la città che mi permette di fare meno strada (non necessariamente Savona ma piuttosto Torino), e poi proseguo con la stessa procedura di ricerca.
Alcuni siti web gratuiti risolvono egregiamente e velocemente questo tipo di compito!!
Utilizzando questi servizi web è sufficiente inserire i nomi delle città da raggiungere (tappe) e far calcolare online il percorso più corto, il risultato sarà l'elenco ordinato delle città da visitare e una rappresentazione cartografica del percorso trovato.
A) - Percorso Minimo "RELATIVO" con Ordine di Visita VINCOLATO
Ad esempio Google Map e ViaMichelin, tanto per citare due siti che permettono di pianificare i percorsi, attualmente NON possiedono un sistema per calcolare il percorso migliore variando autonomamente l'ordine delle città intermedie da visitare. Infatti, se inseriamo le città nell'ordine indicato nell'esempio precedente, vediamo che su Google Maps ci viene mostrato il tragitto e le tempistiche toccando le città esattamente nello stesso ordine con cui sono state inserite le tappe intermedie e fornendo come risultato (milano-savona-torino-venezia-parma-genova-milano) (1327 km - 14 ore 41 min).
Esso però NON rappresenta il tragitto stradale più corto in assoluto.
Anche ViaMichelin "consiglia" l'tinerario stradale (1369 km 15 ore 15 min) ma non tenta di variare l'ordine con cui visitare le città, e l'opzione "percorso più corto" potrebbe trarre in inganno in quanto cerca sempre il tragitto minore (1268 km 20 ore 53 min) avendo però come sempre vincolo l'ordine con cui si sono inserite le città intermedie.
B) - Percorso Minimo "ASSOLUTO" con Ordine di Visita NON Vincolato
Esistono altri siti web che riescono a calcolare online GRATUITAMENTE il percorso più corto variando appunto l'ordine con cui visitare le tappe intermedie e cercando effettivamente il percorso minimo assoluto.
Eccone alcuni con le relative soluzioni:
findthebestroute.com
- Partenza e Arrivo a: Milano
- Città intermedie da visitare nel percorso: Savona, Torino, Venezia, Parma, Genova
Per ogni coppia di queste città esistono molteplici percorsi di collegamento, ad esempio pensiamo a tutti le strade e autostrade che uniscono Milano e Savona. La teoria de grafi permette di individuare il percorso stradale con la minore distanza fra queste due città. Poi si riapplica la stessa procedura per individuare il percorso minimo fra Savona e Torino, e così via.
In questo caso è bene precisare che il percorso minimo può essere di due tipi:
1) "RELATIVO" quando l'ordine di visita delle città intermedie è vincolato è quindi non può essere variato. Da Milano vado a Savona, come richiesto dal vincolo e poi per lo stesso motivo vado per forza a Torino ecc.
2) "ASSOLUTO" quando l'ordine di visita delle città intermedie NON è vincolato è quindi può essere variato a piacimento per individuare ad esempio il percorso più breve (o più economico, bello, ecc. ). Da Milano vado verso la città che mi permette di fare meno strada (non necessariamente Savona ma piuttosto Torino), e poi proseguo con la stessa procedura di ricerca.
Alcuni siti web gratuiti risolvono egregiamente e velocemente questo tipo di compito!!
Utilizzando questi servizi web è sufficiente inserire i nomi delle città da raggiungere (tappe) e far calcolare online il percorso più corto, il risultato sarà l'elenco ordinato delle città da visitare e una rappresentazione cartografica del percorso trovato.
A) - Percorso Minimo "RELATIVO" con Ordine di Visita VINCOLATO
Ad esempio Google Map e ViaMichelin, tanto per citare due siti che permettono di pianificare i percorsi, attualmente NON possiedono un sistema per calcolare il percorso migliore variando autonomamente l'ordine delle città intermedie da visitare. Infatti, se inseriamo le città nell'ordine indicato nell'esempio precedente, vediamo che su Google Maps ci viene mostrato il tragitto e le tempistiche toccando le città esattamente nello stesso ordine con cui sono state inserite le tappe intermedie e fornendo come risultato (milano-savona-torino-venezia-parma-genova-milano) (1327 km - 14 ore 41 min).
Esso però NON rappresenta il tragitto stradale più corto in assoluto.
Anche ViaMichelin "consiglia" l'tinerario stradale (1369 km 15 ore 15 min) ma non tenta di variare l'ordine con cui visitare le città, e l'opzione "percorso più corto" potrebbe trarre in inganno in quanto cerca sempre il tragitto minore (1268 km 20 ore 53 min) avendo però come sempre vincolo l'ordine con cui si sono inserite le città intermedie.
B) - Percorso Minimo "ASSOLUTO" con Ordine di Visita NON Vincolato
Esistono altri siti web che riescono a calcolare online GRATUITAMENTE il percorso più corto variando appunto l'ordine con cui visitare le tappe intermedie e cercando effettivamente il percorso minimo assoluto.
Eccone alcuni con le relative soluzioni:
findthebestroute.com
(milano-parma-venezia-torino-savona-genova-milano) (1112 km 12 ore 45 min)
www.tulliomarra.it/maps/googlemaps.html
(milano-torino-savona-genova-parma-venezia-milano) (1065 km 12 ore 26 min)
www.gebweb.net/optimap
(milano-parma-venezia-genova-savona-torino-milano) (1111 km 12 ore 16 min)
(milano-torino-savona-genova-parma-venezia-milano) (1065 km 12 ore 26 min)
www.gebweb.net/optimap
(milano-torino-savona-genova-parma-venezia-milano) (1065 km 12 ore 27 min)
route.servicetask.com
(milano-torino-savona-genova-parma-venezia-milano) (1064 km 10 ore 41 min)
A parte qualche piccola differenza in km e minuti, si può osservare come la strategia migliore sia quella di percorrere il tragitto più corto indicato come (milano-torino-savona-genova-parma-venezia-milano) (1065 km 12 ore 26 min)
Quindi il Percorso Minimo ASSOLUTO è inferiore di almeno 200 km rispetto a quello RELATIVO:
a) rispetto ai risultati di Google 1327-1065 = 262 km in meno!!!
b) rispetto ai risultati di ViaMichelin 1268-1065 = 203 km in meno!!!
route.servicetask.com
(milano-torino-savona-genova-parma-venezia-milano) (1064 km 10 ore 41 min)
A parte qualche piccola differenza in km e minuti, si può osservare come la strategia migliore sia quella di percorrere il tragitto più corto indicato come (milano-torino-savona-genova-parma-venezia-milano) (1065 km 12 ore 26 min)
Quindi il Percorso Minimo ASSOLUTO è inferiore di almeno 200 km rispetto a quello RELATIVO:
a) rispetto ai risultati di Google 1327-1065 = 262 km in meno!!!
b) rispetto ai risultati di ViaMichelin 1268-1065 = 203 km in meno!!!
©RIPRODUZIONE RISERVATA
