scritto da | on , | Nessun commento

Il problema del commesso viaggiatore (TSP) è un classico problema di ricerca operativa cosi posto: Un commesso viaggiatore deve visitare un certo numero di città. Vuole partire da casa e ritornare a casa dopo aver visitato ogni città una sola volta,percorrendo la distanza minima. La risoluzione di questo problema trova vasta applicazione in logistica, come ad esempio individuare il cammino che minimizza il percorso totale di picking nel magazzino, individuare i percorsi che minimizzano la distanza totale per servire i clienti e più in generale come ottimizzare un sistema integrato di produzione e distribuzione. La risoluzione del TSP si è rivelato di grande aiuto per la General Motors che dovendo gestire 13.000 componenti, 20.000 fornitori, 164 impianti e 11.000 rivenditori sparsi nel mondo ha ottenuto un risparmio del costo logistico pari al 26%. La soluzione ottima del TSP è la completa enumerazione ma tale soluzione si rivela impraticabile in quanto i tempi di calcolo aumentano in maniera esponenziale in fatti se per 8 nodi è necessario meno di un secondo già per 16 nodi sono necessari 4 giorni, pertanto considerando che normalmente un TSP viene applicato ad un problema con centinaia o migliaia di nodi tale soluzione non è utilizzabile perciò si ricorre ad algoritmi Branch-&-Bound, Branch-&-Cut oppure euristiche come Nearest Neighbor,  Insertion,  Lin-Kernighan, Tabu search, Algoritmi Genetici, Simulated Annealing. Questi algoritmi sono implementati in diversi software cartografici.

ALLEGATI

tsp03
Titolo: tsp03 (0 click)
Etichetta:
Filename: tsp03.pdf
Dimensione: 218 kB
tsp02
Titolo: tsp02 (0 click)
Etichetta:
Filename: tsp02.pdf
Dimensione: 114 kB
tsp01
Titolo: tsp01 (0 click)
Etichetta:
Filename: tsp01.pdf
Dimensione: 73 kB

Lascia un Commento

News