Grupo 4: Agente Viajero (TSP)

Problema de Agente Viajero

 ( Traveling Salesman Problem)

El problema del agente viajero o TSP por sus siglas en inglés (Travelling Salesmen Problem) es uno de los problemas más famosos y complejos de las ciencias computacionales y ha sido abordado por varias ramas de la ingeniería y por distintas razones, su principal aplicación es la de ratear desde distintas perspectivas, ya sea un proceso que lleva una secuencia específica o una distribución de carácter logístico en la que intervienen elementos del transporte, buscando la mejor ruta posible con criterios de

Economía en distancia o en costo.

Proveer soluciones contribuye a mejorar tareas y procesos en distintos ámbitos, científicos e industriales, proponiendo alternativas para el mejor uso de los recursos. Disciplinas que abordan este tema son la investigación de operaciones y las ciencias informáticas como algoritmia y teoría de grafos.

 El TSP se describe como: un agente viajero desea programar visitas a sus clientes en diferentes ciudades, por lo que desea viajar lo mínimo posible. Así, se encuentra en el problema de determinar una ruta que minimice la distancia total (o bien tiempo o costo) necesaria para visitar todas las ciudades en su zona.

A las ciudades o a los puntos de partida y llegadas se les llama nodos y los caminos entre ellos se llama arcos. Existen arcos dirigido y no dirigidos los arcos dirigidos  solo pueden ir desde el arco inicial al arco terminal, es como una calle con un solo sentido, si el arco es no dirigido significa que se puede recorrer en doble sentido.

 En estos problemas se construye una ruta de costo mínimo en los cuales cada cliente, ciudades o nodos pasen por lo demás nodos exactamente una vez, es decir;

• Dado n ciudades (o clientes).
• Sea C_{i j}  el costo del viaje desde la ciudad i hasta la ciudad j.
• Construir una ruta de costo mínimo que visite a cada ciudad                       exactamente una vez.
• Si C_{i j =} C_{j i}  para todas la ciudades, entonces el problema es                 simétrico.
• Si C_{i j} ≠ C_{j i}  para algún par de ciudades, entonces el problema es    asimétrico.

Existen numerosos métodos para la resolución de problemas de agente viajero el más exacto es el de la búsqueda exhaustiva o mejor conocido como “Método de fuerza bruta” pero solo es factibles con máximo seis nodos o ciudades debido al tiempo que se debe emplear para su resolución.

Por ejemplo, por exploración exhaustiva del conjunto de soluciones:

•     Cada solución es una permutación del conjunto de vértices

          V= {1, 2, …, n}

• En total se tendrían n! soluciones factibles posibles

•  Con n = 20 ciudades por visitar se requiere evaluar 20! Posibles tours, imposible de realizar en un tiempo razonable.

N	Tiempo
5	1.2 ×10-6 segundos
10	1.2 ×10-6 segundos
15	3.63243 horas
18	741.015 días
20	771.468 años

  

Ejemplo del problema de vendedor viajero por el método de fuerza bruta:

El problema se sitúa dentro de un grafo, en este caso tenemos cinco ciudades y cada nodo es identificado con la primera letra de cada ciudad, además  se muestran los costos asociados para cada arco que representa el costo de traslado entre cada par de ciudades. El problema consiste en que el agente viajero tiene que vender sus productos en las distintas ciudades y debe volver a su lugar de partida u origen; esto debe hacerlo considerando el menor costo posible.

  En este caso se usa la intuición (método de fuerza bruta) para calcular la ruta óptima.

Grafo inicial:( contiene los datos del problema)

                                                                 

• En el primer intento para conseguir la ruta óptima podemos decir, por ejemplo, que la ruta será partiendo de San Felipe  pasando por Los Teques, Zaraza, Caracas, Valencia, y volviendo a San Felipe, es decir, hacer la ruta por afuera  como muestra el siguiente gráfico en la cual  las suma de los costos asociados es 462.

                                                        

• Segunda ruta, segundo intento.

                                                     

La suma de los costó de esta ruta es mayor que la primera por ello se descarta.

Así después de probar, podemos llegar a preguntarnos, ¿cuántas son las rutas posibles que se podría considerar  el agente viajero?

Después de analizar se puede concluir que si se tiene un conjunto finito de nodos entonces habrá una solución finita, es decir, N nodos = a una cantidad finita de rutas.

En este caso con cinco nodos y haciendo todas las combinaciones posibles podemos identificar que se pueden hacer veinticuatro combinaciones distintas; analizando en  términos matemáticos y pensando en alguna herramienta que permita agrupar de forma distinta una colección de elementos es posible concluir que cuando se tienen N nodos la cantidad de rutas posibles será de “N-1!”(N menos un factorial); es decir, N nodos = (N-1!) rutas posibles.

 En este caso como N vale cinco se determinan las rutas posibles calculando el factorial de 4. La factorial es una herramienta que permite realizar permutaciones; es decir; resolver el problema de cómo se agrupan una cantidad finita de elementos de forma distinta.

• 5 nodos = (5-1!) rutas  (se le resta uno porque en la soluciones no se debe incluir el nodo de partida).
•   = 4!
•   =24

 Al calcular cada una de las rutas nos damos cuenta que cada una de ellas esta duplicadas, es decir, la solución de una también existe como solución en el sentido inverso.

Por ello la cantidad de rutas reales que se van a considerar corresponde a  (5-1!/2) = 12 rutas posibles. Debido a lo anterior se puede concluir que a medida que crece la cantidad de nodos se hará cada vez más complejo determinar el camino óptimo; sin embargo es el método más efectivo, cuando se resuelven problemas igual o menor a 6 nodos porque no da lugar a error.

A través del método de la “Fuerza Bruta” podremos descubrir que la ruta con el costo mínimo en este caso  es (s, z, c, l, v, s) el cual se muestra en el siguiente gráfico:

                                                         

El T.S.P. sería equivalente a encontrar el ciclo Hamiltoniano de

Costo mínimo: Partiendo de un depósito se debe recorrer todos los

Vértices y regresar al depósito con la menor distancia total

Recorrida.

 Un ejemplo del problema de agente viajero con ciclos Hamiltoniano  se puede resolver  de la siguiente manera:

 Un  agente viajero tiene que recorrer un conjunto de”ciudades unidas entre sí por carreteras. Si conoce el costo de transporte entre cada par de ellas se quiere.

•   Recorrer todas las ciudades sin pasar 2 veces por alguna de ellas, volviendo a la ciudad de origen, y que el costo de dicho recorrido sea mínimo. (Circuito hamiltoniano).
• Recorrer todas las ciudades sin pasar 2 veces por alguna de ellas, que el costo del recorrido sea mínimo comenzando por una ciudad dada, sin regresar a ella. (Camino hamiltoniano con origen).
• Recorrer todas las ciudades, que el costo del recorrido sea mínimo y que la elección de la ciudad de origen sea óptima (Camino hamiltoniano).

Consideremos la matriz  {Cij } m x m donde m es el número de ciudades que hay que recorrer  y sea C_{i j} el costo de ir de la ciudad i a la ciudad j, además los C_{i i} son igual a infinito.

El problema del agente viajero equivale a encontrar un circuito hamiltoniano de valor mínimo que una las m ciudades. Es decir equivale a escoger una entrada de cada renglón y de cada columna en la matriz {Cij } tal que la suma de ellas sea mínima.

Se hace muy difícil aplicar técnicas exactas para encontrar la solución óptima, en su lugar se han desarrollado heurísticas para

determinar “buenas soluciones”

HEURÍSTICAS PARA RESOLVER EL TSP

 Las más sencillas están basadas en el sentido común, las

Principales son las heurísticas glotonas:

• Heurística del vecino más cercano.
• Heurística de Inserción más cercana.
• Heurística del Método de ahorros. 

 Heurística del vecino más cercano: Se va construyendo el

Tour secuencialmente, a partir del depósito, eligiendo en

Cada paso como el nodo siguiente al nodo más cercano al

Nodo actual.

• Paso 1. Seleccionar un nodo inicial

• Paso 2. Identificar al nodo más cercano al último agregado,

        siempre que no haya sido agregado.

•  Paso 3. Repetir el paso 2 hasta incluir todos los nodos.

La cota superior garantiza que la solución del TSP aplicando

este algoritmo es a lo más {½(log2 n) }+1/2.

El siguiente ejemplo muestra la resolución de un problema de agente viajero  utilizando el método de “el vecino más cercano”con el software “WinQSB”.

Alberto está  a punto de cumplir 10 años, por lo que su mamá le está organizando una fiesta a la cual podrá invitar a sus 4 amigos más cercanos, Beto, Carlos, Daniel y Ernesto.

Problema:

¿En qué orden debe repartir Alberto las tarjetas de cumpleaños para demorarse lo menos posible a fin de ir a escoger su regalo con su mamá?

 Datos:

                                                        

1 Paso: Cargamos en WinQSB  los datos presentados en el grafo, asumiremos que es distancia por el contexto del problema, por lo que la unidad será en (Km).

                                                  

2 Paso: Una vez cargados los datos del problema, procederemos a dar clic en (Solve and Analyze) señalado con la flecha roja.

                                                      

                                                        

3 Paso: Abrirá la ventana de color naranja y daremos clic nuevamente en «Nearest Neighbor Heuristic» que significa (Heurística del Vecino más cercano). Señalado con la flecha negra. Y luego en SOLVE.

 4 Paso: Se mostrará la solución final encontrada.

                                                               

Heurística de inserción más cercana:

•             Ir a la ciudad más cercana y retornar.
•           Insertar la ciudad más cercana a la ruta en la mejor secuencia.

Heurística  de método de ahorros:

•            Adicionar a la ruta la ciudad o nodo que permite mayor ahorro, una y otra vez hasta volver al nodo de partida.

Algoritmo determinístico

La técnica búsqueda tabú:

La Búsqueda Tabú (BT) es un método metaheurístico que puede utilizarse para resolver problemas de optimización combinatoria, tales como el problema del agente viajero (TSP). La búsqueda tabú utiliza un procedimiento de búsqueda local o por vecindades para moverse iterativamente desde una solución x hacia una solución x* en la vecindad de x, hasta satisfacer algún criterio de parada. Para poder explorar regiones del espacio de búsqueda que serían dejadas de lado por el procedimiento de búsqueda local, la búsqueda tabú modifica la estructura de vecinos para cada solución a medida que la búsqueda progresa. Las soluciones admitidas para N*(x), el nuevo vecindario, son determinadas mediante el uso de estructuras de memoria. La búsqueda entonces progresa moviéndose iterativamente de una solución x hacia una solución x* en N*(x).

Quizás la estructura de memoria más importante usada para determinar las soluciones permitidas a un N*(x), sea la lista tabú. En su forma más simple, una lista tabú es una memoria de corto plazo que contiene las soluciones que fueron visitadas en el pasado reciente (menos de n iteraciones atrás, donde n es el número de soluciones previas que van a ser almacenadas). La búsqueda tabú

Excluye las soluciones en la lista tabú de N*(x). Una variación de la lista tabú prohibe soluciones que tienen ciertos atributos.

Esta  técnica de búsqueda tabú para la resolución de problemas de agente viajero es utilizado en su mayoría  cuando el número de nodos o ciudades a visitar es mayor a 15 o 20 debido a su complejidad, y se utilidad software de programación como el conocido “Matlab” usualmente por expertos en programación computacional.

Por último se puede agregar, que existen otros programas computacionales que se pueden utilizar para  la resolución de problemas complejos del agente viajero, como el programa estadístico Excel con su aplicación solver, WinQSB, java tabú; entre los mas usados.