Traveling salesman problem (TSP)
The Traveling Salesman Problem (TSP) is a popular problem and has applications is logistics. In the TSP a salesman is given a list of cities, and the distance between each pair. He is looking for the shortest route going from the origin through all points before going back to the origin city again. This is a computationally difficult problem to solve but Miller-Tucker-Zemlin (MTZ) showed it can be completed using Integer Linear Programing. In this exercise you are going to define the objective and some constraints for of the TSP for a small dataset with 15 cities (see the image below). Your goal is to try out using LpVariable.dicts with list comprehension.
Three Python variables n, cities, and dist have been created for you \(^{1}\). The n variable is the number of cities, cities is a list of the cities numbered and dist is a pandas DataFrame with the pairwise distance between each city. You can explore them in the console. Additionally, the model has been initialized for you.
\(^{1}\) Dataset come from Gerhard Reinelt,TSPLIB - A Traveling Salesman Problem Library, ORSA Journal on Computing,
This exercise is part of the course
Supply Chain Analytics in Python
Hands-on interactive exercise
Have a go at this exercise by completing this sample code.
# 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=____)