Problema del commesso viaggiatore (TSP)
Il Traveling Salesman Problem (TSP) è un problema molto noto con applicazioni nella logistica. Nel TSP a un commesso viaggiatore viene fornito un elenco di città e la distanza tra ogni coppia. Cerca il percorso più breve che parte dalla città di origine, visita tutte le altre città e ritorna alla città di partenza. È un problema computazionalmente difficile, ma Miller-Tucker-Zemlin (MTZ) hanno mostrato che può essere risolto con la Programmazione Lineare Intera. In questo esercizio definirai l’obiettivo e alcuni vincoli del TSP per un piccolo insieme di dati con 15 città (vedi l’immagine sotto). Il tuo obiettivo è provare a usare LpVariable.dicts insieme alle list comprehension.
Tre variabili Python n, cities e dist sono già state create per te \(^{1}\). La variabile n è il numero di città, cities è un elenco numerato delle città e dist è un DataFrame di pandas con le distanze a coppie tra ogni città. Puoi esplorarle nella console. Inoltre, il modello è già stato inizializzato per te.
\(^{1}\) Dataset tratto da Gerhard Reinelt, TSPLIB - A Traveling Salesman Problem Library, ORSA Journal on Computing,
Questo esercizio fa parte del corso
Analytics per la supply chain con Python
esercizio interattivo pratico
Prova questo esercizio completando questo codice di esempio.
# Define Decision Variables
x = LpVariable.dicts('X', [(____, ____) for c1 in ____ for c2 in ____],
cat='____')
u = LpVariable.dicts('U', [____ for c1 in ____],
lowBound=0, upBound=(n-1), cat=____)