Agente Viajero
Páginas: 9 (2110 palabras)
Publicado: 13 de febrero de 2013
PRÁCTICA N° 6
TEMA : Problema del agente viajero (Travelling Salesman Problem, TSP)
DURACIÓN : 2 horas
OBJETIVOS
Mostrar los métodos de solución del agente viajero para los problemas de planteamiento de redes.
OBJETIVOS ESPECÍFICOS
Identificar los diferentes métodos de solución del agente viajero.
Utilizar el concepto de la programación heurística sobre algoritmos de solución delagente viajero.
Comprender el concepto de la programación entera para el método de ramificación y acotamiento en la solución del agente viajero.
INTRODUCCIÓN TEÓRICA
El problema del agente viajero consiste en la minimización de una ruta donde se pasen por una serie de lugares diferentes una vez y se vuelva al punto de partida. El criterio de minimización suele tomarse porque su contexto mencionaobservar un mismo para origen y destino final, donde una ruta es evaluada por la distancia recorrida entre todos los nodos.
Inicia en 1850 con William Rowan Hamilton, junto a Thomas Penygton. Hamilton descubre una solución por medio de arcos y circuitos hamiltonianos (a quien debe su nombre) para descubrir una forma de pasar por todas las ciudades una vez y retornar al mismo punto de partida,minimizando la distancia recorrida. El problema fue considerado como un gran reto para resolverlo. Por Malavar (2012), Dantzig, Fulkerson y Johnson publicaron un artículo en 1954 de una forma para resolver problemas de 49 nodos, considerado como un gran problema.
El agente viajero tiene una forma especial en las restricciones de un programa lineal. Se muestra la Figura 1 que contiene todaslas ecuaciones y restricciones pertinentes.
Figura [ 1 ]. Planteamiento general del Agente Viajero.
Su forma de solución, puede ser de varias maneras por la forma que se contienen las restricciones:
a) Enumerando todas las soluciones. Resultaría en un proceso largo para calcular varias ciudades.
b) Métodos determinísticos: Intentan resolver subproblemas en forma entera a modo deencontrar factibilidad.
c) Métodos heurísticos: soluciones muy buenas con un tiempo corto de cálculo.
Según Fischer (2001), el problema del agente viajero (PAV, en inglés, TSP) no considera:
Capacidad de viaje y de las rutas: en caso de repartir productos, no se considera la capacidad de transporte que pueda hacer en un tiempo determinado; así como el ciclo completo de la ruta no tendrá unmínimo a considerar ni un máximo.
Entregas bajo un tiempo determinado: Llegar de un nodo a otro en un tiempo determinado no puede ser considerado. Esto implicaría que no se puede proteger la entrega de un producto a un cliente en un tiempo considerado.
Rutas dinámicas y fluctuantes: en el agente viajero, las distancias sólo consideran un valor conocido del tiempo, pero no pueden predecirsevalores con flujo de tráfico que podría incrementar el hecho de tomar la decisión por una o por otra ruta.
Aleatoriedad: no se reconocen otras decisiones que pueden ser afectadas por el conductor o por el que toma la decisión sobre el problema.
Existen modificaciones al algoritmo como el problema del ruteo de vehículos de carga (Vehicle Routing Problem, VRP) donde se considera una capacidad deltransporte para soportar viajes con carga y capacidades finitas del vehículo.
Métodos de solución
En el programa WinQSB, existen cuatro métodos de solución que se categorizan en dos grandes rubros:
Métodos Constructivos: agregan arcos individuales hasta completar el viaje a todas las ciudades. Entre ellos están: Nearest neighbour heuristic (vecino más cercano) y Cheapest insertion (inserción másbarata).
Métodos Heurísticos: parten de una solución inicial para generar una mejora a partir de un algoritmo que obtiene otra solución y es evaluada para reconocer si ha obtenido mejoras.
Vecino más cercano.
Se basas en armar la red con el arco más cercano al nodo inicial. Luego, evalúa la inserción del arco menor entre las dos ciudades elegidas. El algoritmo termina cuando ya se...
TEMA : Problema del agente viajero (Travelling Salesman Problem, TSP)
DURACIÓN : 2 horas
OBJETIVOS
Mostrar los métodos de solución del agente viajero para los problemas de planteamiento de redes.
OBJETIVOS ESPECÍFICOS
Identificar los diferentes métodos de solución del agente viajero.
Utilizar el concepto de la programación heurística sobre algoritmos de solución delagente viajero.
Comprender el concepto de la programación entera para el método de ramificación y acotamiento en la solución del agente viajero.
INTRODUCCIÓN TEÓRICA
El problema del agente viajero consiste en la minimización de una ruta donde se pasen por una serie de lugares diferentes una vez y se vuelva al punto de partida. El criterio de minimización suele tomarse porque su contexto mencionaobservar un mismo para origen y destino final, donde una ruta es evaluada por la distancia recorrida entre todos los nodos.
Inicia en 1850 con William Rowan Hamilton, junto a Thomas Penygton. Hamilton descubre una solución por medio de arcos y circuitos hamiltonianos (a quien debe su nombre) para descubrir una forma de pasar por todas las ciudades una vez y retornar al mismo punto de partida,minimizando la distancia recorrida. El problema fue considerado como un gran reto para resolverlo. Por Malavar (2012), Dantzig, Fulkerson y Johnson publicaron un artículo en 1954 de una forma para resolver problemas de 49 nodos, considerado como un gran problema.
El agente viajero tiene una forma especial en las restricciones de un programa lineal. Se muestra la Figura 1 que contiene todaslas ecuaciones y restricciones pertinentes.
Figura [ 1 ]. Planteamiento general del Agente Viajero.
Su forma de solución, puede ser de varias maneras por la forma que se contienen las restricciones:
a) Enumerando todas las soluciones. Resultaría en un proceso largo para calcular varias ciudades.
b) Métodos determinísticos: Intentan resolver subproblemas en forma entera a modo deencontrar factibilidad.
c) Métodos heurísticos: soluciones muy buenas con un tiempo corto de cálculo.
Según Fischer (2001), el problema del agente viajero (PAV, en inglés, TSP) no considera:
Capacidad de viaje y de las rutas: en caso de repartir productos, no se considera la capacidad de transporte que pueda hacer en un tiempo determinado; así como el ciclo completo de la ruta no tendrá unmínimo a considerar ni un máximo.
Entregas bajo un tiempo determinado: Llegar de un nodo a otro en un tiempo determinado no puede ser considerado. Esto implicaría que no se puede proteger la entrega de un producto a un cliente en un tiempo considerado.
Rutas dinámicas y fluctuantes: en el agente viajero, las distancias sólo consideran un valor conocido del tiempo, pero no pueden predecirsevalores con flujo de tráfico que podría incrementar el hecho de tomar la decisión por una o por otra ruta.
Aleatoriedad: no se reconocen otras decisiones que pueden ser afectadas por el conductor o por el que toma la decisión sobre el problema.
Existen modificaciones al algoritmo como el problema del ruteo de vehículos de carga (Vehicle Routing Problem, VRP) donde se considera una capacidad deltransporte para soportar viajes con carga y capacidades finitas del vehículo.
Métodos de solución
En el programa WinQSB, existen cuatro métodos de solución que se categorizan en dos grandes rubros:
Métodos Constructivos: agregan arcos individuales hasta completar el viaje a todas las ciudades. Entre ellos están: Nearest neighbour heuristic (vecino más cercano) y Cheapest insertion (inserción másbarata).
Métodos Heurísticos: parten de una solución inicial para generar una mejora a partir de un algoritmo que obtiene otra solución y es evaluada para reconocer si ha obtenido mejoras.
Vecino más cercano.
Se basas en armar la red con el arco más cercano al nodo inicial. Luego, evalúa la inserción del arco menor entre las dos ciudades elegidas. El algoritmo termina cuando ya se...
Leer documento completo
Regístrate para leer el documento completo.