Problema del viajante (TSP)
El Problema del Viajante (TSP) es muy conocido y tiene aplicaciones en logística. En el TSP, a un viajante se le da una lista de ciudades y la distancia entre cada par. Busca la ruta más corta que parte del origen, pasa por todos los puntos y vuelve de nuevo a la ciudad de origen. Es un problema difícil computacionalmente, pero Miller-Tucker-Zemlin (MTZ) mostraron que puede resolverse usando Programación Lineal Entera. En este ejercicio vas a definir la función objetivo y algunas restricciones del TSP para un conjunto de datos pequeño con 15 ciudades (mira la imagen de abajo). Tu objetivo es practicar el uso de LpVariable.dicts con list comprehension.
Se han creado para ti tres variables de Python: n, cities y dist \(^{1}\). La variable n es el número de ciudades, cities es una lista con las ciudades numeradas y dist es un DataFrame de pandas con las distancias por pares entre cada ciudad. Puedes explorarlas en la consola. Además, el modelo ya está inicializado.
\(^{1}\) Conjunto de datos de Gerhard Reinelt, TSPLIB - A Traveling Salesman Problem Library, ORSA Journal on Computing,
Este ejercicio forma parte del curso
Analítica de la cadena de suministro en Python
Ejercicio interactivo práctico
Prueba este ejercicio y completa el código de muestra.
# 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=____)