PROBLEMA DEL AGENTE VIAJERO Y DE LA MOCHILA
Páginas: 12 (2838 palabras)
Publicado: 27 de septiembre de 2013
PROBLEMA DEL AGENTE VIAJERO: SIMPLE Y MULTIPLE
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 cortaposible 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 nodirigido, 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 = Cijpara 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. Ladistancia 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 jal nodo i puede ser diferente.
FORMULACIÓN DEL PROBLEMA DEL AGENTE VIAJERO (PAV) O TRAVELINGSALESMAN 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 nobastan 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 dehacerlo 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 amú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...
PROBLEMA DEL AGENTE VIAJERO: SIMPLE Y MULTIPLE
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 cortaposible 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 nodirigido, 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 = Cijpara 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. Ladistancia 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 jal nodo i puede ser diferente.
FORMULACIÓN DEL PROBLEMA DEL AGENTE VIAJERO (PAV) O TRAVELINGSALESMAN 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 nobastan 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 dehacerlo 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 amú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...
Leer documento completo
Regístrate para leer el documento completo.