LoslegenKostenlos starten

Traveling-Salesman-Problem (TSP)

Das Traveling-Salesman-Problem (TSP) ist ein bekanntes Problem mit Anwendungen in der Logistik. Beim TSP erhält ein Handlungsreisender eine Liste von Städten und die Entfernung zwischen jedem Paar. Gesucht ist die kürzeste Route, die vom Startpunkt aus alle Städte genau einmal besucht und am Ende zum Start zurückkehrt. Das ist rechnerisch schwierig zu lösen, aber Miller–Tucker–Zemlin (MTZ) konnten zeigen, dass es mit Integer Linear Programming lösbar ist. In dieser Übung definierst du die Zielfunktion und einige Nebenbedingungen für ein kleines Datenset mit 15 Städten (siehe Abbildung unten). Ziel ist es, LpVariable.dicts zusammen mit List Comprehensions auszuprobieren.

Photo of Cities

Drei Python-Variablen n, cities und dist wurden für dich erzeugt \(^{1}\). n ist die Anzahl der Städte, cities ist eine Liste der durchnummerierten Städte und dist ist ein pandas-DataFrame mit den paarweisen Entfernungen zwischen den Städten. Du kannst sie in der Konsole erkunden. Außerdem wurde das Modell bereits für dich initialisiert.

\(^{1}\) Datensatz aus: Gerhard Reinelt, TSPLIB - A Traveling Salesman Problem Library, ORSA Journal on Computing,

Diese Übung ist Teil des Kurses

<Kurs>Supply Chain Analytics mit Python</Kurs>
Kurs ansehen

Interaktive praktische Übung

Versuche dich an dieser Übung, indem du diesen Beispielcode vervollständigst.

# 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=____)
Code bearbeiten und ausführen