Handelsresandeproblemet (TSP)
Handelsresandeproblemet (TSP) är ett välkänt problem med tillämpningar inom logistik. I TSP får en handelsresande en lista med städer och avståndet mellan varje par. Målet är att hitta den kortaste rutten som utgår från ursprungsstaden, passerar alla övriga städer och sedan återvänder till startpunkten. Det här är ett beräkningsmässigt krävande problem, men Miller-Tucker-Zemlin (MTZ) visade att det går att lösa med heltalslinjär programmering. I den här övningen ska du definiera målfunktionen och några bivillkor för TSP med ett litet dataset bestående av 15 städer (se bilden nedan). Målet är att öva på att använda LpVariable.dicts med list comprehension.
Tre Python-variabler – n, cities och dist – har skapats åt dig \(^{1}\). Variabeln n är antalet städer, cities är en lista med numrerade städer och dist är en pandas DataFrame med parvisa avstånd mellan varje stad. Du kan utforska dem i konsolen. Modellen har också redan initierats åt dig.
\(^{1}\) Dataset come from Gerhard Reinelt,TSPLIB - A Traveling Salesman Problem Library, ORSA Journal on Computing,
Den här övningen är en del av kursen
Supply Chain Analytics i Python
Interaktiv övning med praktiskt arbete
Testa den här övningen genom att slutföra den här exempelkoden.
# 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=____)