sabato 1 ottobre 2011

Calcola online il problema del commesso viaggiatore!

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

Lamborghini Veneno Roadster
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à da visitare, quanto più complesso da risolvere può diventare il problema! 


SOLUZIONI:
La prima soluzione indicata da uno studente è stata di acquistare una Lamborghini Veneno - Roadster da 355 Km/h (!) 
E' chiaro che con quest'auto in dotazione per gli spostamenti non si deve insistere troppo sul "risparmio carburante" ;-P


Esempio di calcolo percorso minimo su un grafo
La soluzione n.2 è stata invece di utilizzare alcuni siti web gratuiti che 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.

Pensiamo ad esempio al seguente percorso:
- Partenza e Arrivo a: Milano 
- Città intermedie da visitare nel percorso: Savona, Torino, Venezia, Parma, Genova

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

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 Vista 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 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!!!


©RIPRODUZIONE RISERVATA