HUERISTICAS Y EL PROBLEMA DEL AGENTE VIAJERO

HUERISTICA:

Se denomina heurística a la capacidad de un sistema para realizar de forma inmediata innovaciones positivas para sus fines. La capacidad heurística es un rasgo característico de los humanos, desde cuyo punto de vista puede describirse como el arte y la ciencia del descubrimiento y de la invención o de resolver problemas mediante la creatividad y el pensamiento lateral o pensamiento divergente. 

Heurísticas

Las heurísticas son métodos inteligentes que buscan una buena solución en un tiempo de cómputo razonable, pero sin garantizar que ésta sea la óptima (Johnson et al., 2002).

Existen diferentes tipos de heurísticas (Glover, Gutin, Yeo y Zverovich, 2001):

•  Heurísticas constructivas. Procedimientos que se encargan de obtener una solución a partir de un criterio inicial, esto es, construyen una solución factible.

•  Heurísticas de búsqueda local. Procedimientos para mejorar soluciones ya encontradas. Tratan de optimizar localmente alrededor de una solución, ubicando mínimos locales.

• Heurísticas combinadas: Procedimientos que constan de una heurística constructiva y una heurística de búsqueda local.

• Algunas heurísticas para el Problema del Agente Viajero Asimétrico son las siguientes (Cirasella, Lyle, McGeoch y Zhang, 2000):

 PROBLEMA DEL AGENTE VIAJERO

Problema del Agente Viajero (TSP) ¿En qué consiste? Aplicaciones Historia Modelo El Problema del Agente Viajero puede resolverse de diferentes maneras: Ejemplo • Reparto de productos.

• Transporte.

• Robótica.

• Turismo y agencias de viajes.

• Horarios de transportes laborales y/o escolares.

• Inspecciones a sitios remotos.

• Secuencias. Inicia em 1850. William Rowan Hamilton, y Thomas Penyngton Kirkman . Y es justamente a Hamilton a quien se le debe el término de circuitos hamiltonianos. solución del problema del agente viajero desde un punto de vista gráfico,originado en un juego inventado por este matemático en 1859. • Enumeración de todas las soluciones factibles. •Métodos exactos. También llamados algoritmos óptimos, intentan descartar familias enteras de posibles soluciones, tratando así de acelerar la búsqueda y llegar a una óptima.

• Heurísticas. Son métodos obtienen buenas soluciones en tiempos de cómputo muy cortos. las rutas posibles entre 12 ciudades son 479.001.600combinaciones y los caminos individuales entre ciudades son el sumatorio delas 12-1 ciudades es decir 66.

PLANTEAMIENTO DEL PROBLEMA

El problema consiste en determinar la mejor ruta o mínimo recorrido, que serealice entre las 12 ciudades, partiendo desde un punto de partida yregresando a este (ciclo Hamiltoniano), además se tiene que visitar todas lasciudades una sola vez. A continuación se mencionan las ciudades de trabajo:

Bogotá

Cali

Medellín

Pasto

Bucaramanga

Villavicencio

Armenia

Valledupar

Leticia

Yopal

Florencia

Puerto Inírida el PAV iba ganando notoriedad como un problema prototipo de problemas duros en optimización combinatoria

Este problema se abrió camino cuando George Dantzig, Ray Fulkerson, y Selmer Johnson (1954) publicaron una descripción de un método de solución del PAV titulado “Solutions of a large scale traveling salesman problem“, “Soluciones de gran escala para el problema del agente viajero”. para resolver una instancia de 49 ciudades, un agente viajero o bien una persona que desea visitar un conjunto n de ciudades y que se le dan los costos, las distancias o el tiempo de viajar de una ciudad que le podemos llamar i a una ciudad que le podemos llamar j.

Y tiene dos condiciones:regresar a la misma ciudad de la cual partió y no repetir ciudades, es decir, si ya visitó laciudad 3 una vez ya no se puede volver a pasar por esa ciudad. Con el objetivo de encontrar una ruta o un camino que sea el más corto posible. Algunas heurísticas para el Problema del Agente Viajero Asimétrico El vecino más cercano (heurística constructiva).

Moverse de una ciudad a la siguiente, de tal forma que, de todas las opciones, la ciudad elegida sea la más cercana a donde se encuentra ubicado el agente viajero Inserción aleatorizada (heurística constructiva)
consiste en crear una ruta inicial de la forma más económica posible, después elegir una trayectoria de forma aleatoria, y eliminar los vértices que pertenecen a ella Búsqueda local (2-opt).

El movimiento 2-Opt consiste en eliminar dos aristas rompiendo una ruta inicial en dos caminos, y reconectándolos de una manera diferente para obtener un nuevo ciclo Conclusiones
• En general, los dos algoritmos constructivos son capaces
de llegar al óptimo en instancias pequeñas, todos con un
tiempo de cómputo pequeño.
• En instancias grandes, la miopía del vecino más cercano se hace evidente, sin embargo, es el algoritmo con el mejor tiempo de cómputo, esto es, el más rápido.
• La inserción aleatorizada ofrece soluciones de buena calidad aun en instancias grandes, pero es más tardada que el vecino más cercano.
• La búsqueda local unida al vecino más cercano genera una mejora significativa sin comprometer el tiempo. Unida a la inserción aleatorizada, sigue obteniendo muy buenas soluciones, sin embargo, el tiempo aumenta considerablemente.
• Para decidir qué algoritmo utilizar se debe ponderar tanto el tiempo que se tiene para dar una solución, así como qué tan estricta es la exigencia de la calidad de la solución.