En los últimos tiempos, más de una vez y de dos he tenido que argumentar el enfoque de que la Programación Lineal y Lineal Entera no es la aproximación más adecuada de cara a la resolución de problemas de cálculo de rutas. Esto no es una verdad absoluta, si bien es cierto que, como norma general, tiene bastante sentido.

En este artículo pretendo explicar por qué digo esto, y hacerlo patente con un ejemplo. Vamos a abordar la modelización del Problema del Viajante que, aunque de apariencia simple, pertenece a la categoría de los problemas NP-completos y que, por lo tanto, ha sido objeto de múltiples intentos de resolución. Veremos que, en efecto, hay una manera teórica de resolver mediante una (o varias) formulaciones lineales enteras este problema, aunque también veremos que, en la práctica, en casos donde lo que prima es el rendimiento y no tanto la optimalidad, este método de resolución no es el más adecuado.

Para el que no lo conozca, el Problema del Viajante muy sencillo de definir: Si tenemos N destinos que visitar, el objetivo es el de encontrar la ruta que visite los N destinos recorriendo la mínima distancia global. Normalmente se presupone que se sale y se vuelve al mismo destino, aunque esto no es importante.

Suponiendo que tenemos los siguientes destinos para visitar:

Estaríamos buscando una ruta entre todos los destinos, la cual, probablemente, tendría un aspecto similar al siguiente:

Formulación del Problema

A continuación introduciré la formulación estándar de este problema en una aproximación Lineal-Entera. Supuesto que tenemos:

• D: El conjunto de todos los destinos
• Xij: Variable binaria que indica si recorremos el arco que va del destino i al destino j.
• dij: Constante que indica la distancia entre los destinos i y j.

Es decir:

• Una función objetivo que minimice la distancia recorrida.
• Un conjunto de restricciones (entrada) que garantice que entramos una vez a cada destino.
• Un conjunto de restricciones (salida) que garantice que salimos una vez de cada destino.
• Un conjunto de restricciones (subtour) que garantice que el camino es único.

Creo que merece la pena ahora entender por qué es necesario definir las restricciones del tipo (subtour). Si estas restricciones no estuvieran presentes, obtendríamos una solución parecida a esta:

Como se puede ver a simple vista, esta solución cumple todas las restricciones de la formulación propuesta excepto la (subtour). Es decir, de cada destino salimos y entramos una sola vez, y es bastante mejor con respecto a la función objetivo que la solución anterior (recorremos menos distancia). Las restricciones de tipo (subtour) garantizan precisamente que, para cada subconjunto de destinos S con más de un elemento y distinto del total (D), el número de arcos que salen de este subconjunto es al menos uno, evitando estos sub-caminos que hacen la solución inválida.

El problema aquí es que, si el conjunto de destinos (D) es lo suficientemente grande, el número de posibles subconjuntos (S) del mismo es enorme, por lo que el modelo, que tiene una restricción de tipo (subtour) para cada uno de ellos, crece hasta ser intratable. De hecho, el número de subconjuntos de D es 2^|D|, es decir, crece exponencialmente con la cardinalidad de D.

Una aproximación bastante común para salvar este problema consiste precisamente en resolver una serie de sub-problemas en los que se van introduciendo las restricciones del tipo (subtour) según van siendo necesarias.

De esta manera, en el momento en que el algoritmo acabe, tendremos una solución óptima y sin subcaminos. Tenemos, además, garantías de que el algoritmo acaba, ya que, en el peor de los casos, acabaría añadiendo todas las restricciones de tipo (subtour), que son finitas, por lo que acabar, acaba.

 Conclusiones

A simple vista, este algoritmo podría parecer aceptable y, de hecho, en algunos casos lo es. Pero lo habitual es que, en problemas de tamaño medio, el número de iteraciones del algoritmo hasta encontrar una solución óptima sin subcaminos sea muy elevado, proporcionando tiempos de respuesta que no son aceptables en la industria.

Además, este método tiene un problema adicional a la hora de aplicarlo a problemas reales (es decir, a problemas donde un usuario espera obtener una solución, que necesita para continuar trabajando): el algoritmo no genera ninguna solución válida hasta que acaba. Esto es importante entenderlo. Todas las soluciones que se obtienen después de cada una de las iteraciones (excepto en la última) son de alguna manera óptimas, pero no factibles, ya que contienen subcaminos. Este hecho, que puede no ser un problema en el ámbito académico, donde podemos dejar a un supercomputador procesando durante días para resolver una instancia aún no resuelta del TSPLIB, es inaceptable cuando estamos resolviendo un problema real.

Imaginémonos a un usuario que, después de una hora esperando delante de la pantalla a obtener una solución a su problema, decide parar la ejecución y quedarse con la mejor solución hasta el momento. Al verla, se da cuenta de que la solución es buenísima en lo que respecta a la distancia recorrida, pero no le sirve para nada, ya que no es en realidad una solución a su problema: él buscaba un camino único y se encuentra con una solución compuesta por varios subcaminos.

En el ámbito empresarial, es más importante tener una buena solución en poco tiempo que tener la mejor solución en horas o días. Precisamente por eso, de cara a la resolución de problemas de rutas, es más común utilizar algoritmos Metaheurísticos, que si bien en general no garantizan la optimalidad de las soluciones, sí que aseguran que, en todo momento, hay una solución factible al problema, aunque no sea la mejor.

¿Quieres saber más sobre este tipo de problemas y los algoritmos para resolverlos?

Puedes seguirnos en las redes sociales (Linkedin, Twitter, Youtube) para no perderte nada y mantenerte al tanto de futuros eventos o acciones.