Traveling Salesman Problem (TSP)

EL PROBLEMA DEL VIAJANTE DE COMERCIO

El problema del viajante de comercio o agente viajero, en inglés Traveling Salesman Problem (TSP), es uno de los problemas de optimización combinatorial NP-duros más ampliamente estudiado. 

Su declaración es engañosamente simple: un viajante busca el camino más corto para pasar por m ciudades. En otras palabras, una persona debe visitar un conjunto de m ciudades, comenzando en una ciudad determinada y finalizando en la misma ciudad; luego de haber visitado todas ellas sólo una vez. Esto significa que nunca regresa a una ciudad ya visitada, excepto la primera.

El objetivo es encontrar la secuencia de visitas óptima; la cual puede ser evaluada según distintos criterios, como por ejemplo: la minimización del costo o del tiempo, la maximización de la velocidad.

Aplicaciones

La mayor parte de las mejoras en TSP durante los primeros años estaban motivadas por aplicaciones directas del mismo. Entre otros, Flood [21] trabajó sobre rutas de autobuses escolares y Morton y Land [43] aplicaron el TSP a la planificación de rutas de una empresa de lavandería. Hasta el día de hoy, el TSP se ha aplicado sobre una gran variedad de problemas que van desde rutas de vendedores hasta la genética. A continuación, se comentan brevemente algunas de las aplicaciones más importantes del problema del viajante: 

Logística.- Las aplicaciones más directas y más abundantes del TSP se centran en el campo de la logística. El flujo de personas, mercancías y vehículos en torno a una serie de ciudades o clientes se adapta perfectamente a la filosofía del TSP, como ya demostraron los primeros estudiosos del problema. Entre las múltiples aplicaciones logísticas del problema del viajante, destacamos:

1. Vendedores y turistas.- Aunque los viajes que se realizan por placer o por negocio rara vez se plantean como un TSP, la mayor parte de los vendedores y turistas utilizan algún planificador de rutas para determinar cuál es el mejor camino para visitar los puntos que desean y volver al punto de origen (nótese que los turistas desean visitar los monumentos o lugares emblemáticos y después regresar al hotel). Estos planificadores generalmente incluyen algún algoritmo de resolución del TSP.

2. Rutas escolares.- Las rutas escolares representan una de las primeras aplicaciones del TSP (Merrill Flood se interesó por el problema del viajante cuando estaba intentando determinar una ruta escolar _optima). Actualmente, muchas empresas dedicadas al transporte de personas adquieren software de resolución de TSP que les permite reducir gastos de una manera significativa.

3. Reparto de correo.- Aunque generalmente el reparto de correo se ajusta mejor a un problema de rutas sobre arcos, como ya se vio anteriormente, en ocasiones el reparto de correo puede modelizarse como un TSP. Se trata de los casos en los que las casas están muy alejadas unas de otras o cuando sólo se debe visitar algunas de ellas (será el caso de las empresas de paquetería). Este esquema es aplicable al reparto de cualquier otro tipo de mercancía.

Industria.- Las aplicaciones en industria no son tan numerosas como en log__stica, pero la aplicaci_on del problema en este _ambito tambi_en ha dado lugar a una signi_cativa reducci_on de los costes. Entre las aplicaciones a la industria encontramos:

1. Secuenciación de tareas.- Supongamos que una máquina debe realizar una serie de tareas en el mínimo tiempo posible y sin importar el orden de las mismas. Supongamos que se tarda un tiempo tij en poner a punto la máquina para realizar la tarea j si la _ultima tarea que realizó fue la i. En ese caso, podemos aplicar un TSP suponiendo que cada tarea es uno de los nodos a visitar, han de realizarse todas las tareas para producir el producto y que la distancia entre ellos es tij. El nodo origen y destino serán el estado de la máquina cuando empieza o termina el producto. Dado que el tiempo que se emplea en realizar cada tarea no depende del orden, no será necesario incluir estos tiempos en el modelo, pues la suma de todos es constante independientemente del orden.

2. Producción de circuitos electrónicos.- La utilización del TSP para la producción de circuitos electrónicos se centra en dos aspectos: el orden óptimo de taladrar las placas y los caminos óptimos necesarios para conectar los chips entre sí.

a. Problemas de perforado.- Los circuitos integrados se encuentran en muchos dispositivos electrónicos, por lo que la producción de las placas sobre las que se montan dichos circuitos es un problema cotidiano. Dichas placas han de ser perforadas un número relativamente grande de ocasiones. Los orificios resultantes sirven para introducir los chips correspondientes. Generalmente, son taladros automáticos los que realizan, uno tras otro, las perforaciones correspondientes. Si estas máquinas no son programadas correctamente, el tiempo que se tarda en recorrer la placa de un orificio a otro puede aumentar significativamente, dando lugar a pérdidas económicas (si se tarda mucho en producir cada placa, produciremos menos placas en el mismo tiempo). Por tanto, la aplicación del TSP en este campo consiste en, tomando como ciudades cada una de las posiciones donde debe realizarse una perforación y las distancias entre ellas como el tiempo que necesita la máquina en trasladarse de una a otra, minimizar el tiempo que pierde la taladradora en moverse de una posición a otra. La ciudad de origen y destino será un punto adicional que represente el lugar donde permanece la perforadora mientras las placas se cambian. Nótese que si el tiempo que se tarda en perforar es muy superior al tiempo de desplazamiento, no tendrá sentido plantear un TSP, pues la disminución del tiempo será casi imperceptible. Estas aplicaciones llevan años siendo estudiadas (existe un artículo de Lin y Kernighan (1973) [39] donde se trata este tema) y ya han sido utilizadas por grandes empresas, como son Siemens e IBM, dando lugar a mejoras de aproximadamente el 10% del rendimiento total de las líneas de producción. 

b. Conexión de chips.- Este tipo de ejemplos se da frecuentemente en el diseño de ordenadores y de otros dispositivos digitales. Dentro de muchos de estos dispositivos existen placas que cuentan con chips que deben ser conectados entre sí por cables. Para evitar problemas de interferencias y debido al pequeño tamaño de los chips, no se pueden poner más de dos cables en un único pin. La idea es, por tanto, minimizar la cantidad de cable necesaria para unir todos los puntos. Claramente este modelo puede ser modelizado como un TSP tomando los pins como las ciudades y la distancia entre ellas, la cantidad de cable necesario para unirlas. Obsérvese que de no existir la restricción de sólo dos cables por chip, este problema deberá ser modelizado como la búsqueda del árbol de mínima expansión, problema para el cual existen algoritmos eficientes.

Variantes del TSP

Existen multitud de variantes al problema de viajante general, tal cual se ha explicado anteriormente. Seguidamente se enumeran algunas de ellas: 

MAX-TSP.- Consiste en encontrar un circuito hamiltoniano de coste máximo. 

TSP con cuello de botella.- Consiste en encontrar un circuito hamiltoniano tal que minimice el mayor coste de entre todas las aristas del mismo, en vez de minimizar el coste total. 

TSP gráfico.- Consiste en encontrar un circuito de coste mínimo tal que se visiten las ciudades al menos una vez. 

TSP agrupado.- Los nodos o ciudades están divididos en "clusters" o grupos, de manera que lo que se busca es un circuito hamiltoniano de coste mínimo en el que se visiten los nodos de cada grupo de manera consecutiva. 

TSP generalizado.- Los nodos o ciudades también están divididos en grupos, pero lo que se busca es un circuito de coste mínimo que visite exactamente un nodo de cada grupo. 

TSP con múltiples viajantes.- Existen un número m de viajantes, cada uno de los cuales debe visitar algunas de las ciudades. El problema se transforma, por tanto, en la búsqueda de una partición de los nodos a visitar X1 ;:::; Xm y de m ciclos, uno para cada Xi, de manera que la suma de las distancias recorridas por los m viajantes sea mínima. Esta variante del TSP puede ser vista también como una simplificación de los problemas de rutas de vehículos.