Dos modelos de programación lineal entera pura para la resolución del problema del viajante de comercio
1. Introducción
Este artículo trata sobre el famosísimo problema del viajante de comercio (Travelling Salesman Problem en inglés; en adelante, TSP). A lo largo de las siguientes líneas plantearemos dicho problema y formularemos dos modelos de programación lineal entera pura para su resolución (Integer Linear Programming en inglés; en adelante, ILP). Como ejemplo ilustrativo, calcularemos la ruta de mínima distancia que permite recorrer todas las capitales comarcales de la comunidad autónoma de Aragón.
El enfoque que adoptaremos a lo largo de la exposición estará orientado, fundamentalmente, al “saber hacer”; aquellos lectores interesados en una fundamentación teórica rigurosa sobre el problema, sobre su clasificación en términos de complejidad algorítmica, sobre otros posibles algoritmos para su resolución o sobre posibles generalizaciones deberán acudir a la bibliografía especializada sobre la materia. Como único prerrequisito, se asumirá que el lector interesado conoce y domina ya los conceptos más básicos sobre programación lineal.
2. El problema del viajante de comercio (TSP)
El problema del viajante de comercio, o TSP por sus siglas en inglés, se plantea de forma muy sencilla:
Como parte de su trabajo, un vendedor ha de visitar un conjunto de n ciudades o pueblos diferentes. ¿Cuál es la ruta más corta que pasa por todos esos sitios una vez, y solo una vez?
En este punto, y como primera aproximación a la resolución del problema, conjeturamos que lo óptimo podría ser desplazarnos siempre al sitio más cercano a donde nos encontramos en cada momento. Sin embargo, basta con analizar el contraejemplo de la figura 1 para cerciorarnos de que, en general, este algoritmo no siempre conduce a la ruta de mínima distancia total, que es la que buscamos. Todo lo anterior justifica un estudio del problema en profundidad y el diseño de algoritmos específicos para su resolución.
Figura 1. Desplazarse siempre desde cada sito al más cercano (parte superior) no equivale, en general, a la mejor solución (parte inferior). Elaboración propia.
3. Un primer modelo de programación lineal entera pura
El TSP es un problema cuya resolución puede abordarse de múltiples formas. Cabe mencionar algoritmos estocásticos como el simulated annealing, o algoritmos de “fuerza bruta” como la generación y evaluación de todas las posibles permutaciones de los sitios a visitar (si bien este último resulta muy poco eficiente en la práctica real, por ser el número de permutaciones igual al factorial del número de sitios).
En este punto vamos a formular un primer modelo de programación lineal entera pura (ILP) para el TSP. Recordemos que la programación u optimización matemática es la rama de las matemáticas que proporciona técnicas y algoritmos para la maximización o minimización de funciones de una o más variables sometidas a cero, una o varias restricciones. Las variables involucradas se denominan variables de decisión, el conjunto delimitado por todas las restricciones impuestas se conoce como región factible y la función cuyo valor se desea maximizar o minimizar (en general, optimizar) se denomina función objetivo. De entre todos estos problemas son especialmente importantes aquellos en los que tanto la función objetivo como las restricciones son funciones lineales de las variables de decisión; tales problemas se dicen de programación lineal. Si, además, todas las variables de decisión únicamente pueden tomar valores enteros, los problemas se dicen de programación lineal entera pura (ILP).
La formulación del TSP como un modelo ILP resulta conveniente por varios motivos:
- Desde el punto de vista teórico, desde mediados del siglo XX se han venido planteando, investigando, probando y mejorando numerosos algoritmos que permiten resolver este tipo de problemas.
- Desde el punto de vista de la implementación computacional, existen numerosas librerías que permiten trasladar sin grandes dificultades la formulación matemática de este tipo de problemas a un programa de ordenador.
- Desde el punto de vista de la resolución computacional, existen numerosos programas informáticos (conocidos como “optimizadores”, o solvers en inglés) que implementan los algoritmos teóricos previamente mencionados, automatizando así la resolución de este tipo de problemas.
- Desde el punto de vista del problema a resolver, la programación matemática y sus técnicas resultan lo suficientemente flexibles como para permitir modelizar e incorporar todas (o, al menos, gran parte de) las características de los problemas a abordar, que a menudo surgen en la realidad de la industria, de la logística, etc.
Sin más dilación, sea V={s1,s2,…,sn} el conjunto de sitios a visitar, con cardinal n; la ordenación de estos no es relevante, si bien los supondremos todos diferentes y asumiremos también que S1 es el sitio en el que comienza y termina la ruta. Sea A={(si,sj)|i≠j & i,j=1,…,n} el conjunto de todos los pares ordenados de sitios diferentes; asumiremos que es posible llegar a cualquier sitio desde cualquier otro. Para cada arco en A, sea dij la distancia entre los sitios (diferentes) si y sj. Definimos el siguiente conjunto de variables de decisión:
- xij. De tipo binario. Tomará el valor 1 si se decide recorrer el arco (si y sj ) como parte de la ruta y 0 en caso contrario.
La función objetivo a minimizar, que representa la distancia total de la ruta a recorrer, la escribimos en términos de las anteriores variables de decisión de la siguiente manera:
En cuanto a las restricciones, hemos de imponer los dos conjuntos siguientes:
- Conjunto de restricciones 1. A todo sitio se llega una vez, y solo una vez:
- Conjunto de restricciones 2. De todo sitio se sale una vez, y solo una vez:
La gran mayoría de las formulaciones del TSP como modelos ILP se basan en los objetos que acabamos de definir. ¿Y en qué se diferencian? En cómo evitan la generación de subciclos. Entenderemos por subciclo (o subtour en inglés) a toda ruta cerrada que no incluya todos los sitios a visitar. Por ejemplo:
Figura 2. La formulación propuesta hasta ahora no impide la generación de subciclos (parte superior). Hay que evitar su aparición de alguna forma (parte inferior) Elaboración propia.
Este punto, el cómo evitar la aparición de subciclos, es la parte más “artística” de la modelización del TSP como un problema ILP, la que más “ingenio” requiere (sobre todo, conseguirlo utilizando un número polinomial de variables de decisión y de restricciones adicionales) y la que más “personalidad” le confiere a cada formulación. En este punto mostramos la solución debida a Miller, Tucker y Zemlin, que es de las más sencillas de implementar computacionalmente. Definimos un segundo conjunto de variables de decisión así:
- ui. De tipo entero no negativo. Tomará el valor j ∈ {1,…,n} si el sitio si se recorre en el lugar j – éismo. Es decir, estas variables de decisión reflejarán el orden exacto en el que deberán ser recorridos los sitios a lo largo de la ruta.
e imponemos el siguiente conjunto de restricciones:
- A s1 le asignamos el valor u1=1 .
- Para todo arco (si, sj) ∈ A, con j≠1, imponemos que:
Este último conjunto de restricciones sirve para forzar que el movimiento desde cada sitio se haga siempre a otro con un mayor valor de la variable de decisión u (salvo en el último arco, claro está, pues tras recorrerlo regresaremos al sitio de partida y este tiene asignado u1=1).
4. Un modelo alternativo de programación lineal entera pura
En este punto mostramos otra formulación del TSP como modelo ILP, si bien existen muchísimas diferentes. En esta también se hace uso del mismo conjunto de variables de decisión xij, de la misma función objetivo y de los mismos conjuntos de restricciones 1 y 2 que definimos en el punto anterior. La principal diferencia entre ambas la encontramos en cómo se va a evitar la generación de subciclos.
Esta formulación es debida a Finke, Claus y Gunn, recibe el nombre de modelo de flujo de dos mercancías (two commodity flow model en inglés) y consiste en lo siguiente. El viajante parte del sitio s1 con n1 unidades de mercancía tipo I y 0 unidades de mercancía tipo II. Al visitar el siguiente sitio de la ruta, entrega allí una unidad de mercancía tipo I y recoge una unidad de mercancía tipo II. Conforme visita los demás sitios, va repitiendo esta misma operación. De esta forma, regresará al sitio de partida con 0 unidades de mercancía tipo I y n-1 unidades de mercancía tipo II. La formulación matemática de este comportamiento la hacemos definiendo dos nuevos conjuntos de variables de decisión:
- pij. De tipo entero no negativo. Representa el número de unidades de mercancía tipo I que se transporta al recorrer el arco (si,sj) ∈ A.
- qij. De tipo entero no negativo. Representa el número de unidades de mercancía tipo II que se transporta al recorrer el arco (si,sj) ∈ A.
e imponiendo los siguientes conjuntos de restricciones:
- Se sale del sitio s1 con n-1 unidades de mercancía tipo I:
- Se regresa al sitio s1 con n-1 unidades de mercancía tipo II:
- En cualquier sitio que no sea se deposita una unidad de mercancía tipo I:
- En cualquier sitio que no sea se recoge una unidad de mercancía tipo II:
- En cualquier sitio el número total de unidades trasportadas es n-1:
- Por último, tenemos que relacionar entre sí los valores de las variables xij, pij y qij:
Si bien es cierto que esta formulación requiere la incorporación al modelo de un número mayor de componentes (tanto de variables de decisión como de restricciones), esto no implica que utilizarla vaya a conducir necesariamente a peores tiempos de resolución.
5. Ejemplo: de paseo por las comarcas de Aragón
5.1. Objetivo
La comunidad autónoma de Aragón se encuentra organizada en treinta y tres comarcas. Ocurre, además, que en siete de ellas la capitalidad se encuentra compartida entre dos de sus municipios: Sobrarbe (Aínsa y Boltaña), La Ribagorza (Graus y Benabarre), La Litera (Binéfar y Tamarite de Litera), Jiloca (Monreal del Campo y Calamocha), Cuencas Mineras (Montalbán y Utrillas), el Bajo Martín (Albalate del Arzobispo e Híjar) y Matarraña (Calaceite y Valderrobres). Véase la figura 3. Nos preguntamos: ¿cuál es el la ruta de mínima distancia que recorre todas las capitales comarcales (cuarenta en total) una vez, y solo una vez? Antes de seguir leyendo, te animamos a que examines el mapa de la figura 3 y a que intentes encontrar dicha ruta “a ojo”.
5.2 Datos requeridos
Para poder abordar el problema necesitamos los siguientes datos:
Nombres de las capitales comarcales.
Distancia entre cada par de capitales (siendo dAB=dBA).
El dato más importante, y a la vez el más difícil de conseguir, es el de la distancia entre cada par de capitales, pues el número de valores requeridos asciende a (40 2)=780. Extraerlos todos haciendo búsquedas manuales en Google Maps sería una tarea titánica, y requeriría además una gran cantidad de tiempo. De tratarse de un proyecto real, lo más correcto sería utilizar alguna API o servicio de geolocalización para determinar el verdadero valor de todas esas distancias, pero puesto que estamos ante un ejemplo, hemos optado por hacer lo siguiente. Este archivo:
Figura 3. Comarcas de Aragón y sus capitales. Extraída de https://es.m.wikipedia.org/wiki/Archivo:Comarcas_de_Arag%C3%B3n.svg
contiene las coordenadas geográficas (latitud y longitud) de todos los pueblos y ciudades de Aragón, por lo que a partir de esta información podemos aproximar las verdaderas distancias por las distancias geodésicas.
5.3. Stack tecnológico
Hemos resuelto el problema utilizando el lenguaje de programación Python. La ETL de los datos necesarios la hemos hecho con las librerías NumPy y Pandas. Para calcular las distancias geodésicas hemos utilizado la librería GeoPy, mientras que la implementación computacional de los modelos de optimización la hemos hecho con la librería Pyomo. Hemos resuelto los modelos de optimización utilizando el solver CBC.
5.4 Posibles generalizaciones
Anteriormente mencionamos que una de las ventajas de la programación lineal es que permite modelizar las características de los problemas a abordar. Concretamente, permite incorporar a un modelo ya formulado una o más restricciones no contempladas originalmente, sin por ello tener que desechar el trabajo previo realizado. Por ejemplo:
- ¿Cómo formularías un modelo ILP para el paseo de mínima distancia por las comarcas de Aragón de tal forma que solamente se recorrieran cuatro capitales comarcales en cada provincia?
- ¿Cómo formularías un modelo ILP para el paseo de mínima distancia por las comarcas de Aragón de tal forma que algunas parejas de capitales se visitaran consecutivamente? ¿Y para garantizar que otras parejas de capitales nunca se visitaran consecutivamente?
- Supón que las capitales comarcales se encuentran agrupadas en k≤n grupos. ¿Cómo formularías un modelo ILP para el paseo de mínima distancia por las comarcas de Aragón de tal forma que solamente se visitara una capital de cada grupo, y solo una? A modo de ejemplo, en la figura 5 mostramos la solución que resulta de agruparlas según la primera letra de su nombre (nótese que ya no se visitan dos capitales cuyo nombre empiece por la misma letra). De nuevo, antes de ver la solución te animamos a que retomes figura 3 y a que intentes encontrar la nueva ruta “a ojo”.
Figura 4. Ruta de mínima distancia total por las capitales de comarca. Adaptada de https://es.m.wikipedia.org/wiki/Archivo:Comarcas_de_Arag%C3%B3n.svg
Figura 5. Ahora no se pueden visitar dos capitales de comarca que empiecen por la misma letra. Adaptada de https://es.m.wikipedia.org/wiki/Archivo:Comarcas_de_Arag%C3%B3n.svg
6. Conclusiones
El problema del viajante de comercio (TSP) es un problema muy importante desde los puntos de vista matemático y computacional. Puede abordarse de formas diferentes, pero formularlo como un modelo de programación lineal entera pura (ILP) resulta conveniente por su flexibilidad y por permitir potenciales generalizaciones. Al hacerlo hay que garantizar que el planteamiento elegido no permita la generación de subciclos; dos formas de conseguirlo son a través de las formulaciones de Miller – Tucker – Zemlin y de Finke – Claus – Gunn (ambas requieren un número polinomial de variables de decisión y de restricciones). Aunque el ejemplo elegido para mostrar (un paseo por todas las capitales comarcales de Aragón) no tienen un gran interés per se, sí que sirve para mostrar lo potentes que pueden llegar a ser las técnicas de programación matemática cuando estas se aplican con la ayuda de un ordenador.
7. Bibliografía
Finke, G., Claus, A. y Gunn, E. (1984). A two-commodity network flow approach to the traveling salesman problem. Congressus Numerantium, 41, 167-178.
Rardin, R. (2023). Optimization in Operations Research. Pearson.
Artículo desarrollado por Jorge Ara Arteaga, científico de datos en Belerofontech