domingo, 31 de marzo de 2013


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