viernes, 5 de abril de 2013

Agente Viajero: Simple y Múltiple (Grupo 5)


Agente Viajero Simple y Múltiple

El Problema del Agente Viajero (PAV) o Traveling Salesman Problem (TSP) es un problema que se estudia en Investigación de Operaciones como parte de la toma de decisiones en las organizaciones.
Este problema se plantea la siguiente pregunta: Dada una lista de ciudades y las distancias entre cada par de ciudades, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una sola vez y vuelve a la ciudad de origen?
A este tipo de problemas a las ciudades se les define como nodos y a los caminos entre las ciudades se les llama arcos. Los arcos pueden ser dirigidos y no dirigidos. Si el arco es dirigido solo se puede ir desde el nodo inicial hasta el nodo final, es decir, una calle con un solo sentido, y si el arco es no dirigido, significa que los nodos se pueden recorrer en ambos sentidos. A cada arco se le puede asociar una distancia o un costo.



El objetivo principal es ayudar al agente viajero a que dado n ciudades, siendo el Cij el costo o distancia del viaje, desde la ciudad i hasta la ciudad j, encontrar una ruta o un camino que sea el más corto posible y que regrese a su ciudad de partida.
Si Cij = Cij para todos las ciudades, el problema es simétrico y si Cij ≠ Cij para un par de ciudades, entonces el problema es asimétrico.


Problema del Agente Viajero Simétrico
Conocido como el Symmetric Traveling Salesman Problem (TSP o PAV). Dado un conjunto de n nodos y distancias para cada par de nodos, encontrar una longitud total mínima que visite cada uno de los nodos exactamente una vez. La distancia del nodo i al nodo j es la misma que del nodo j al nodo i.
Problema del Agente Viajero Asimétrico
Conocido como Asymmetric Traveling Salesman Problem (ATSP). Dado un conjunto de nodos y distancias para cada par de nodos, encontrar una ruta de longitud total mínima que visite cada uno de los nodos exactamente una vez. En este caso, la distancia del nodo i al nodo j y la distancia del nodo j al nodo i puede ser diferente.

Formulación del El Problema del Agente Viajero (PAV) o Traveling Salesman Problem (TSP)
El TSP presenta una gran facilidad para formularse, pero a medida que crece el número de ciudades, el tiempo para obtener una solución óptima crece más. Para formular el TSP como un problema de programación entera se usa la variable Xij que toma el valor de 1 si el arco (i,j) es usado, y el valor de 0 en cualquier otro caso.

La formulación de este problema es la siguiente: 


Sujeto a las siguientes restricciones,
Para garantizar que se llega a cada ciudad exactamente una vez:

  (j= 1,2,……., n+1)

Para garantizar que se sale de cada ciudad exactamente una vez:

  (i= 0,1,….., n)

Sin embargo, estas restricciones no bastan para garantizar que se está optimizando sobre recorridos, es decir, que las soluciones factibles son sólo recorridos. Esto es, porque permiten la existencia de subrecorridos: Por ejemplo, en el caso de seis ciudades haciendo 1 variables X01,X012,X26,X45,X53, se satisfacen todas estas restricciones. Para restringir sólo a recorridos, hay que añadir restricciones adicionales. Una forma de hacerlo es que en cada recorrido para cada subconjunto de índices de N= 0,1,…..n; debe haber un arco que vaya a su complemento y otro que venga.
En general, para cualquier L  N con 2 ≤ |L| ≤ n−1 (los de tamaño 1 ya están) las restricciones son satisfechas por todo tour pero todo subtour viola al menos una de ellas.


Por su gran facilidad para ser formulado y por su gran adaptabilidad a múltiples situaciones prácticas el TSP ha sido uno de los problemas de optimización que mayor interés ha despertado a los investigadores en las áreas de matemáticas discretas, computación e investigación de operaciones.

El TSP se puede asociar con gran facilidad a múltiples problemas prácticos tales como:

− Programación de tareas en máquinas: Aunque poco parecido a un TSP, esta situación se puede formular de la misma manera. Cada tarea se puede ver como una de las ciudades a visitar y el tiempo necesario para cambiar de tarea será la distancia que hay entre una ciudad y otra. El objetivo en este caso será minimizar el tiempo total de cambio de referencia.

− Recolección de órdenes en bodegas y centros de distribución: Este problema está asociado con la recolección de materiales en las bodegas. Suponiendo que una orden que llega requiere un subconjunto de los artículos almacenados en la bodega. Un vehículo o una persona debe recoger todos los artículos que luego serán enviados al cliente. La relación con el TSP es inmediata. Los lugares de almacenamiento de los artículos corresponden a las ciudades, la distancia entre dos ciudades está dada por el tiempo requerido para desplazarse desde una localización a otra. El problema de encontrar la ruta más corta es decir con el tiempo de recogida más pequeño se puede resolver como un TSP. Algunos casos especiales del problema pueden resolverse fácilmente.

− Optimización de rutas en el Problema de enrutamiento de vehículos: Una de las aplicaciones de mayor importancia que se le ha asociado al TSP es su relación con el Problema de enrutamiento de vehículos (VRP- Vehicle Routing Problem).
Existen también métodos de solución Heurística que buscan explotar la estructura del problema para obtener soluciones en tiempos muy cortos. Entre estos métodos se cuentan el vecino más cercano (Nearest Neighbor.), los métodos de Inserción y de Ahorros.
Se puede ver la resolución de este método a través del siguiente link: http://www.youtube.com/watch?v=xZXm2bM_MdI 

A continuación, se mostrará un ejemplo extraído del libro: Investigaciones de operaciones de Handy Taha.
El programa de producción diaria de Rainbow  Company lotes de pinturas blanca (W), amarilla (Y), roja (R) y negra (B). Como Rainbow usa las mismas instalaciones en las cuatro clases de pintura, es necesario hacer una buena limpieza entre los lotes. La siguiente tabla resume el tiempo de limpieza, en minutos, donde al color del renglón sigue el color de la columna. Por ejemplo, cuando después de la pintura blanca sigue la amarilla, el tiempo de limpieza es de 10 minutos. Como un color no puede seguir así mismo, a los elementos correspondientes se les asigna un tiempo de preparación infinito. Determinar la secuencia óptima para la producción diaria de los cuatro colores, que minimice el tiempo total de limpieza necesario.

Minutos de limpieza si la siguiente pintura es

Pintura actual
Blanca
Amarilla
Negra
Roja
Blanca
10
17
15
Amarilla
20
19
18
Negra
50
44
25
Roja
45
40
20



Se puede concebir que cada pintura es una “ciudad” y que las “distancias” representan el tiempo de limpieza necesario para cambiar de un lote de pintura al siguiente. El caso se reduce  así  a determinar el circuito más corto que se inicie en el lote de pintura y pase exactamente una vez por cada uno de los tres lotes restantes, para regresar al punto de partida. Este problema  se puede resolver enumerando exhaustivamente de los  seis [(4 -1)! =3!=6] bucles posibles de la red. La siguiente tabla indica que   W->->R->B->W es el ciclo óptimo.


Ciclo de producción:

 W -> Y ->B ->R ->W
10+19+25+45=99
 -> Y ->R ->B ->W
10+18+20+50=98
 -> B ->Y ->R ->
17+44+18+45=124
W -> B ->R ->Y ->
17+25+40+20=102
 -> R ->B ->Y ->
15+20+44+20=99
W -> R -> Y ->B ->W
15+40+19+50=124



 Para resolver la formulación del problema de pinturas basadas en asignación se define a:
Xij=  1 si es pintura j sique a las pintura i, y cero en caso contrario.

Sea M con un valor positivo suficientemente grande; se puede formular el problema de Rainbow:

Minimizar Z= MX WW  + 10X WY + 17X WB+ 15X WR+ 20X YW+ MX YY+ 19X YB + 18X YR+ 50X BW+ 44X BY+ MXBB+ 25X BR + 45X RW+ 40X RY+ 20X RB+ MX RR
Sujeto a,


XWW+ XWY+ XWB+ XWR= 1
XYW+ XYY+ XYB+ XYR= 1
XBW+ XBY+ XBB+ XBR= 1
XRW+ XRY+ XRB+ XRR= 1
XWY+ XYY+ XBY+ XRY= 1
XWB+ XYB+ XBB+ XRB= 1
XWY+ XYR+ XBR+ XWR= 1
Xij = (0,1) para toda i y j

La solución es un ciclo.

El uso de M en la Función Objetivo garantiza que un lote de cierta pintura no siga de otro de la misma pintura.

Ejemplo del problema Agente Viajero Simple en Winqsb



Ejemplo del problema Agente Viajero Simple con Sort de EXCEL
En el siguiente link se podrá encontrar un ejemplo de un problema de Agente Viajero Simple resuelto con la herramienta de EXCEL llamada Sort: http://wps.prenhall.com/esm_tannenbaum_excursions_5/14/3688/944318.cw/index.html

El problema de Agente Viajero Múltiple o Multiple traveling salesman problem (m-TSP)
Para clarificar aún más la utilidad que tiene el TSP se explicará una de sus extensiones, el m-TSP (Multiple Traveling Salesman Problem) en el cual hay m agentes viajeros. El m-TSP consiste en determinar un conjunto de rutas para m vendedores quienes parten al mismo tiempo y después de haber realizado su ruta retornan al punto de partida, cada ruta conserva las mismas condiciones de un TSP (Parten desde la ciudad origen recorren un número n de ciudades, cada ciudad es visitada solo una vez y retornan a la ciudad origen). El m-TSP busca minimizar el costo total para visitar todas las ciudades. Su formulación es la siguiente: 

El m-TSP tiene algunas variantes importantes:

− Uno o varios lugares de despacho: En el caso de un solo lugar de despacho los vendedores empiezan y terminan el viaje desde un mismo punto. Mientras que en el otro caso pueden empezar en uno y terminar en otro. Además se debe considerar la asignación de los vendedores a los centros de despacho.

− Número de vendedores: El número de vendedores en el problema es un parámetro establecido a priori o puede tratarse como una variable cuyo valor resulta de la solución del m-TSP.

− Cargos Fijos: Cuando el número de vendedores en el problema no es fijo, a cada vendedor se le asocia un costo en el cual se incurre cuando el vendedor es utilizado en la solución del problema, en este caso la minimización del número de vendedores utilizados puede ser el objetivo.

− Ventanas de tiempo (m-TSPTW): Aquí determinados nodos necesitan ser visitados en periodos específicos de tiempo (conocidos como ventanas de tiempo), teniendo este caso específico utilización en ruteo de buses escolares, horarios de aerolíneas y en navieras.

− Otras variantes especiales: Las cuales tienen restricciones sobre el número de ciudades que pueden visitarse en cada viaje o la distancia máxima o mínima que puede tener un viaje.
Algunas de las aplicaciones para el m-MTSP son:

− Recogida postal: el problema consiste en determinar las distintas rutas para los mensajeros con el mínimo costo posible, en este caso, el volumen pequeño de las cartas hace que no haya restricciones de capacidad de los viajeros y por eso puede modelarse como un m-TSP.

− Enrutamiento de buses escolares: el objetivo es minimizar tanto el número de buses como la distancia total del recorrido de cada uno de estos.

− Robótica: los robots con el tiempo han tenido cada día más utilizaciones tanto en las empresas como en los hogares, ha dichos robots se les asignan un número de tareas especificadas, la relación que tiene con el m-TSP consiste en encontrar la ruta más eficiente para que un conjunto de robot realice sus tareas.

A continuación, se mostrará una forma en que se puede resolver un problema o ejercicio de Agente Viajero Múltiple:  
Hay una "transformación" para resolver el problema de Agente Viajero Múltiple, que es el mismo problema de Ruteo de Vehículos. Siguiéndola, se puede obtener una solución, pero no óptima, para el problema de ruteo de vehículos, usando el mismo método en EXCEL que para el Agente Viajero Simple y que se encuentra en el link anteriormente escrito. Las indicaciones son las siguientes:
a) Si hay "m" viajeros, entonces agregar "m-1" ciudades de "inicio" (normalmente hay sólo una).
b) Las distancias que hay entre las ciudades de inicio y la ciudad de inicio de los viajeros, así como entre ellas, deben ponerse como "infinito".
c) Las distancias entre las ciudades de inicio (las m-1 ficticias y la real) y las ciudades donde se va a "vender" deben definirse como "0" en la matriz de distancias.
d) Aplicar la misma heurística que para el problema de Agente Viajero Simple.
e) Al considerar el resultado, cada "ida" o "venida" a una de las m-1 ciudades origen ficticias, debe redireccionarse a la ciudad origen ficticia 
f)Se finaliza el ejercicio

Referencia: Prof. Orestes Manzanilla.


11 comentarios:

  1. Otra tecnica que puede ayudar en la resolucion de problemas de TSP, es el uso del algoritmo de Christofides.
    Segun wikipedia :" El algoritmo de Christofides es un algoritmo aproximado que permite resolver instancias del problema del viajante de comercio (designado convencionalmente por su acrónimo en inglés, TSP) en donde los pesos de las aristas del grafo satisfacen la desigualdad triangular. Fue desarrollado en 1976 por Nicos Christofides, profesor del Imperial College London.1

    Supongamos que G=(V,w) representa una instancia del TSP, en donde G es un grafo completo definido por: un conjunto V de vértices o nodos y una función w que asocia un peso o valor real positivo a cada arista del grafo G."

    ResponderEliminar
  2. Se puede entender, e intentar resolver, el problema del vendedor viajero como si fuera un 'juego'. Se crea un tablero con clavos, a distancias apropiadas, que marcan los 'sitios' que debe visitar el vendedor. Cada jugador escoge un recorrido uniendo todos los 'sitios'(clavos) con una cuerda y, al retirarla del tablero, se mide la longitud del recorrido. Habiendo realizado sus recorridos todos los participantes, gana el que tuvo la cuerda mas corta.

    ResponderEliminar
  3. El tema de Agente Viajero es muy interesante y me pareció que fue explicado de forma completa, solo quiero aportar que las heurísticas de el vecino más cercano (heurística constructiva) y el de Inserción aleatorizada, son métodos aplicados para la solución de problemas de Agente viajero Asimétrico.

    El vecino más cercano: esta heurística se encuentra basada en la idea de moverse de una ciudad a la siguiente, de forma que, de todas las opciones la ciudad que se elija sea la más cercana a aquella en donde se encuentra ubicado el agente viajero. Tiene su desventaja ya que se toma como la mejor opción disponible en ese momento, pero más adelante esto puede obligarle a tomar decisiones incorrectas o malas.

    Inserción aleatorizada: esta heurística consiste en crear una ruta inicial de la forma más económica posible, luego se procede a elegir una trayectoria de forma aleatoria y se eliminan los vértices que pertenecen a ella, los vértices eliminados se reinsertan a la ruta resultante de la forma más barata, creando de este modo una ruta mejor a la inicial.

    ResponderEliminar
  4. Este comentario ha sido eliminado por el autor.

    ResponderEliminar
  5. Un ejemplo que pudiese complementar éste articulo, mostrarnos algo mas "gráfico" del tema y salirnos un poco del aspecto matemático puede ser el caso de las hormigas. De acuerdo a un articulo publicado en http://www.ddsmedia.net, establece que desde varios años se ha estudiando el comportamiento de estos insectos y han descubierto que ellas por donde pasan secretan moléculas de feromonas. A la larga, esto representa para las hormigas, que los caminos con mayor cantidad de feromonas es la ruta mas corta para regresar a su origen; por lo que se considera que éste es un excelente método aplicado por ellas para optimizar su recorrido.

    ResponderEliminar
  6. El tema del agente viajero es uno de los más famosos pero a la vez menos inexactos a la hora de conocer cual seria la ruta más corta para recorrer todas las ciudades sin repetir visitas, para la resolución de este problema se recorre a heuristicas porque a pesar de que es fácil formularlo NO se puede resolver de forma óptima como un modelo de programación lineal, este articulo http://alt1040.com/2010/10/las-abejas-resuelven-problemas-que-los-ordenadores-no-tan-facil, me parece interesante porque explica como se aplica agente viajero en la naturaleza, en este caso las abejas que de acuerdo al articulo deben hacer un recorrido en diversas ubicaciones en búsqueda de flores,y encuentran una ruta que les mantiene volando el menor tiempo posible para no gastar tanta energías.

    ResponderEliminar
  7. El problema del agente viajero o TSP como se le conoce en la literatura, consiste en un agente de ventas que tienes que visitar N ciudades, comenzando y terminado en una misma ciudad, visitando solamente una vez cada ciudad, y haciendo un recorrido de costo mínimo, este costo de recorrido puede estar expresado en términos de tiempo y distancia, es decir, recorrer el mínimo de Kilómetros o llevar acabo un tour en el menor tiempo posible.

    El Problema de Agente viajero se puede modelar fácilmente mediante un grafo dirigido en donde los vértices del grafo son las ciudades y los arcos son los caminos, dichos arcos deben de tener un peso, y este peso representa la distancia que hay entre dos vértices que están conectados por medio de dicho arco.

    Una solución al problema del agente viajero se puede representar como una secuencia de n+1, en donde el tour comienza y termina en la misma ciudad.

    Navegando en la red encontré que existen varios técnicas para resolver este tipo de problemas e incluso se les puede combinar para encontrar una mejor solución. Me pareció muy interesante la información esta colgada en el siguiente link http://www.researchgate.net/publication/40739299_Estudio_comparativo_de_diversos_mtodos_de_solucin_del_problema_del_agente_viajero_(PAV)

    Nos habla de que hay tres métodos exactos los cuales son: Búsqueda Exhaustiva Ingenua(Naive Search Exhaustive),"Ramificación y Acotamiento Ingenuo (Naive Branch and Bound) y el de Una Mejor Ramificación y Acotamiento (A Better Branch and Bound). Nos habla que también existen métodos que no te dan una solución bastante aproximada los cuales son: "Dos Optimal", "Adaptación Prim", "Híbrido Dos Optimal-Prim" y el de "Red Neuronal de Hopfield". Estos métodos lo trataron de funcionar y obtuvieron buenos resultados lo que significa que vale la pena híbridar métodos para poder obtener métodos que proporcionen mejores resultados en exactitud. Si quiere mas información del comentario accedan al lick anteriormente dejado.

    ResponderEliminar
  8. El problema de agente viajero es sencillo de entender y fue bien explicado, al igual que en flujo máximo dejo un vídeo de youtube donde se explica nuevamente la resolución del problema de forma teorica manual: http://www.youtube.com/watch?v=Jb9ZERkyV1s
    :)


    ResponderEliminar
  9. Como ya se ha comentado, existen métodos de mejoramiento para resolver problemas de Agente viajero, entre las que esta el vecino más cercano (heurística constructiva) y el de Inserción aleatorizada.

    Adicional a estas, existen otro métodos más llamados: Two-way exchange improvement heuristi, el cual consiste en iniciar con un tour, en el que se buscan diferentes interaciones para alcanzar la mejora de la solución inicial.

    Se basa en la hipótesis de que si dos rutas se encuentran en un tour, se puede reconectar las mismas mendiante la unión de las ciudades participes y así evitar el cruce entre ellas. Por lo que al ejecutar este método, se produce un nuevo tour el cual tendrá una distancia mucho menor con respecto al anterior.

    ResponderEliminar
  10. Una manera de resolver el problema del Agente viajero es atacarlo con fuerza bruta, es decir, nos ponemos a analizar todas las rutas posibles y luego tomamos la más barata. Por ejemplo, si tenemos que visitar tres ciudades A, B, y C, tendríamos que analizar 6 rutas:

    A->B->C
    A->C->B
    B->A->C
    B->C->A
    C->A->B
    C->B->A

    Pero en el caso que tengamos que analizar 300 ciudades y 300 diferentes costos, ya seria sumamnete complejo, es por ello que mediante al aplicacion llamada " CONCORDE TPS" , en la cual se introduciran los datos de las cuiudades, origenes y costos, y el mostrara mapas especificando distancias, coordenadas y costos , para obtener una solucion optima.

    Dicha herramienta puede descargarse desd el siguente link: http://www.tsp.gatech.edu/concorde.html




    ResponderEliminar
  11. El link del archivo en excel no redirecciona, valor hacermelo llegar o corregir el url a andree_912@hotmail.com

    ResponderEliminar