Traveling salesman problem (TSP)
Het Traveling Salesman Problem (TSP) is een bekend probleem met toepassingen in de logistiek. In de TSP krijgt een verkoper een lijst met steden en de afstand tussen elk paar. Hij zoekt de kortste route die vertrekt vanuit de oorsprong, langs alle punten gaat en daarna weer terugkeert naar de beginstad. Dit is een rekenkundig lastig probleem, maar Miller-Tucker-Zemlin (MTZ) liet zien dat het oplosbaar is met Integer Linear Programming. In deze oefening ga je de doelfunctie en enkele constraints definiëren voor de TSP voor een kleine gegevensset met 15 steden (zie de afbeelding hieronder). Je doel is om LpVariable.dicts te gebruiken in combinatie met list comprehensions.
Drie Python-variabelen n, cities en dist zijn alvast voor je aangemaakt \(^{1}\). De variabele n is het aantal steden, cities is een genummerde lijst met de steden en dist is een pandas DataFrame met de paargewijze afstand tussen elke stad. Je kunt ze verkennen in de console. Daarnaast is het model al voor je geïnitialiseerd.
\(^{1}\) Gegevensset afkomstig van Gerhard Reinelt, TSPLIB - A Traveling Salesman Problem Library, ORSA Journal on Computing,
Deze oefening maakt deel uit van de cursus
Supply Chain Analytics in Python
Praktische interactieve oefening
Probeer deze oefening eens door deze voorbeeldcode in te vullen.
# 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=____)