problema del viajante de comercio (TSP)
distancia total mínima
En este apartado se verá una posible aplicación de la teoría de grafos para la resolución y optimización de los problemas de rutas o recorridos: el problema del viajante de comercio (Traveling Salesman Problem - TSP). Se trata de un problema de complejidad NP-completo. Esto es así, porque el número de posibles soluciones crece exponencialmente con el número de nodos del grafo (ciudades), y rápidamente sobrepasa las capacidades de cálculo de los ordenadores más potentes.
Es por ello, por lo que todavía se sigue investigando en nuevas técnicas de resolución que reduzcan el esfuerzo computacional y mejoren la eficiencia de las soluciones y su aproximación a la solución óptima. Actualmente incluso se comienza a investigar la utilización de cubits (bits cuánticos que representan 1 y 0 a la vez), o incluso de ADN para poder evaluar simultáneamente multitud de posibles soluciones en el tiempo actual de proceso de una sola.
Los algoritmos de paralelización de problemas de este tipo y su resolución en GRID (o cálculo distribuido) también están siendo utilizados e investigados actualmente.
Además del reto computacional que representa este tipo de problemas, también es de los más interesantes de la teoría de grafos y de la investigación operativa por su aplicación práctica en la realidad. Su aplicación es visible y de gran importancia para la resolución de problemas reales en la Dirección de Operaciones y Logística. Por ejemplo: problemas de picking, de rutas, sistemas de navegación GPS, planificación de movimientos de robots, vehículos autoguiados (AGV), etc.
Este problema es fácil de enunciar, aunque un poco más complicado de modelar y resolver. Se trata de un vendedor o viajante de comercio que debe visitar $n$ ciudades para vender u ofertar sus productos. Cada par de ciudades puede estar comunicada o no, su distancia se define mediante $c_{ij}$. El problema es por tanto, decidir el recorrido que comenzando por una determinada ciudad pase por todas las demás una sola vez y vuelva finalmente a la primera, de manera que se minimice la distancia total recorrida.
Sea $x_{ij}$ una variable binaria que indica si el viajante utilizará el arco de la ciudad $i$ a la $j$ en su recorrido solución. Para el modelado matemático, la ciudad de comienzo es irrelevante. A continuación se muestra el modelo completo del problema. La función objetivo queda expresada como:
$$ \displaystyle{\min \sum_{i=1}^n\sum_{j=1}^n {c_{ij} x_{ij}}}$$
y está sujeto a las restricciones:
$$ \displaystyle{\sum_{i=1}^n {x_{ij}} =1 \quad \forall {j=1 \ldots n}} $$
$$ \displaystyle{\sum_{j=1}^n {x_{ij}} =1 \quad \forall {i=1 \ldots n}} $$
$$ \displaystyle{x_{ij} \in (0,1)}$$
y con las condiciones de Miller-Tucker adicionales:
$$ \displaystyle{u_i - u_j + n \cdot x_{ij} \leq n-1 \quad 2 \leq i \neq j \leq n}$$
Analizando las restricciones, se puede observar que sólo debe haber un arco de llegada a una ciudad o nodo, y que igualmente tan sólo debe haber un arco de salida. Con esto se garantiza que cada ciudad es visitada sólo una única vez.
Sin embargo, con estas restricciones y la condición binaria de las variables $x_{ij}$, no es suficiente para garantizar que las soluciones factibles son recorridos. Es posible por tanto, que aparezca una solución formada por subrutas (no conectadas entre sí) y que cumplan las restricciones anteriormente comentadas.
Es por ello, por lo que es necesario añadir más restricciones que eviten la formación de subrutas. Una de las posibles formas de hacer esto (ya que existen varias), es la propuesta por Miller-Tucker y que se muestra en el modelo. Las variables de decisión introducidas por las condiciones de Miller-Tucker son reales y no tienen límites ni superior ni inferior. La propuesta de Tucker genera $n^2$ restricciones, mientras que otras en la literatura pueden llegar a generar $2^n$. Sin embargo, desde un punto de vista computacional, este modelo aunque más compacto es menos eficiente.
En el caso de Grafos, este problema se aborda a través del modelo anteriormente expuesto y su resolución mediante Programación Lineal Entera Mixta.
Otra estrategia para solucionar este problema (muy común) es resolverlo sin las condiciones de Tucker. Y si en la solución aparecen subrutas, entonces introducir la restricción oportuna que evite estas subrutas y volver a resolver el problema. Este proceso de relajación-restricción se repetirá hasta obtener la solución óptima.
Además de la PLEM en la literatura existen multitud de estrategias de resolución para este problema: técnicas de aproximación, heurísticas, relajaciones, post-optimizaciones, óptimos locales, enumeración completa, meta-heurísticas y técnicas evolutivas, y otras.
Grafos contiene entre otras una librería bajo licencia LGPL, para solucionar problemas de Programación Lineal Entera Mixta (lpsolve.dll - Copyright © 1991, 2011 Free Software Foundation, Inc.).
Más información en:
- Miller, C. and A. Tucker, R. Zemlin, Integer programming formulations and traveling salesman problems, J. of the ACM, 7 (1960) 326-329.
- N. Christofides (1985). Vehicle Routing, in The Traveling Salesman Problem, Lawler, Lenstra, Rinooy Kan and Shmoys, eds., John Wiley, 431-448.
- J.V. Potvin (1996) Genetic Algorithms for the Traveling Salesman Problem, Annals of Operations Research 63, 339-370.