Problema de los m-Viajantes de Comercio (m-TSP)

En este apartado se comentará la aplicación de la teoría de grafos para la resolución y optimización de los Problemas de Rutas o Recorridos,  en concreto para la resolución del Problema de los m-Viajantes de Comercio. Siga leyendo para saber más sobre este problema y su resolución.

El Problema de los m-Viajantes de Comercio (m-TSP) es una variante del Problema del Viajante de Comercio (Traveling Salesman Problem - TSP). En este problema, se trata de construir m rutas, una para cada viajante de comercio (o vehículo). Al igual que en el TSP, cada cliente debe ser visitado exactamente una vez. Las rutas de los vehículos deben comenzar y finalizar en un lugar de origen y destino final que llamaremos depósito.

 

Problema de los m-Viajantes de Comercio (mínima distancia recorrida)

Se trata de m vendedores o viajantes de comercio que debe visitar n ciudades para vender u ofertar sus productos. Cada viajante de comercio podrá visitar como máximo a p clientes o ciudades. Cada par de ciudades puede estar comunicada o no, su distancia se define mediante cij. El problema es por tanto, decidir el recorrido que comenzando por una determinada ciudad { 0 } pase por todas las demás una sola vez y vuelva finalmente a la primera, de manera que se minimice la distancia total recorrida de todas las rutas.

Sea xij una variable binaria que indica si el viajante utilizará el arco de la ciudad i a la j en su solución. A continuación se muestra el modelo completo del problema:

El modelo es muy similar al del Problema del Viajante de Comercio. La primera restricción indica que m viajantes saldrán del depósito. Analizando el siguiente par de 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. Por tanto, cada cliente o ciudad es un nodo intermedio de una ruta.

Sin embargo, con estas restricciones y la condición binaria de las variables xij, 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 Tucker y que se muestra en la ilustración superior del modelo. Las variables de decisión introducidas por las condiciones de Tucker son reales y no tienen límites ni superior ni inferior. La propuesta de Tucker genera n² restricciones, mientras que otras en la literatura pueden llegar a generar 2ⁿ. Sin embargo, desde un punto de vista computacional, este modelo aunque más compacto es menos eficiente. En este caso, las restricciones e Tucker imponen además que en cada ruta no haya más de p clientes.

En el caso de que p=n (cuando no hay límite en la visita de los viajantes a los clientes), el m-TSP podría formularse como un TSP con m copias del depósito, con distancia infinita entre ellos. Las soluciones a este TSP no utilizarían arcos que conectara las copias del depósito y podrían ser interpretadas fácilmente como soluciones al Problema de m-Viajantes de Comercio.

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  5.x - Copyright © 1991, 2005 Free Software Foundation, Inc.).

Fuente: A. Rodríguez

más información

- C. Miller, A. Tucker, R. Zemlin: Integer programming formulation of traveling salesman problems. Journal of the ACM 7 (1960) 326-329
- VRP Web
- TSP en GATECH
- Solving Traveling Salesman Problems (Princeton University)
- Traveling Salesman Problem (Kevin Ruland - W. Univ.)