HEURISTICAS

              HEURÍSTICAS Y EL PROBLEMA DEL AGENTE VIAJERO

El Problema del Agente Viajero ( TSP, por sus siglas en inglés) es quizá el más estudiado de los problemas de optimización combinatoria (Applegate, Bixby, Chvatal, Cook, 1998; y Lawler, Lenstra, Rinnooy y Shmoys, 1985). Su popularidad se debe a que es fácil de plantear, pero difícil de resolver.

Su planteamiento es: Dadas n ciudades y el costo Cij que se tiene al viajar de una ciudad a otra, se debe encontrar la ruta de costo mínimo para visitarlas todas pasando sólo una vez por cada una de ellas, y regresando a la de partida. A cada ruta se le llama tour o ciclo hamiltoniano.

El problema de agente viajero,
fácil de comprender, pero difícil
de resolver.

En sus aplicaciones encontramos:

Reparto de productos. Donde se puede mejorar una ruta de entrega para seguir la más corta.

a)  Transporte. Mejorando la distribución del camino seguido usando el de menor longitud.

b)  Robótica. Permite resolver problemas de fabricación para minimizar el número de desplazamientos al realizar una serie de perforaciones en una plancha o en un circuito impreso.

c) Turismo y agencias de viajes. Aun cuando los agentes de viajes no tienen un conocimiento explícito del Problema del Agente Viajero, las compañías dedicadas a este giro utilizan un software que hace todo el trabajo. 

d)  Horarios de transportes laborales y/o escolares. Estandarizar los horarios de los transportes es claramente una de sus aplicaciones, tanto que existen empresas que se especializan en ayudar a las escuelas a programarlos para optimizarlos en base a una solución del TSP.

e)  Inspecciones a sitios remotos. Otro ejemplo similar es el caso donde un grupo de la Universidad de Maryland modeló el problema de los horarios de una tripulación barquera para que visitaran aproximadamente 200 estaciones en la bahía de Chesapeake.

f)  Secuencias. Donde se refiere al orden en el cual n trabajos tienen que ser procesados de tal forma que se minimice el costo total de producción.

En el Problema del Agente Viajero, la solución es una permutación de las n ciudades dadas, y se divide en dos tipos:

I) TSP simétrico (STSP): En este caso, la matriz de costos Cij es simétrica, es decir, el costo que genera viajar de la iudad i a la ciudad j es el mismo que el que se tiene al viajar de la ciudad j a la ciudad i.

II) TSP asimétrico (ATSP): En este caso, la matriz de costos Cij no es simétrica, es decir, el costo que se genera de viajar de la ciudad i a la ciudad j, en general, no es el mismo que el que se tiene de viajar de la ciudad j a la ciudad i. 

El Problema del Agente Viajero en su forma asimétrica tiene (n-1)! rutas posibles, esto es, (n-1)! posible soluciones. La forma simétrica tiene tours, porque al cambiar la dirección de la ruta ésta no cambia y sigue siendo la misma.

El Problema del Agente Viajero puede resolverse de diferentes maneras:

I) Enumeración de todas las soluciones factibles. Es decir, enlistar todas las posibles soluciones al problema, calcular sus costos asociados, e identificar, por comparación, cuál es la solución con el costo más conveniente.

II) 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. Los que más se usan para resolver el TSP son Ramificación y Acotamiento, y Ramificación y Corte.

III) Heurísticas. Son métodos obtienen buenas soluciones en tiempos de cómputo muy cortos, aunque sin garantizar la optimalidad de la solución.

El TSP es un problema considerado difícil de resolver. Con el uso de heurísticas se tienen soluciones de muy buena calidad en tiempos de cómputo mucho más pequeños.

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 .

Tipos de heurísticas 

 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.

El problema del agente viajero, es todo lo contrario, a los problemas comunes, que en general son fáciles de resolver, aunque el planteamiento sea difícil de entender. Es decir todo lo contraio al TSP.

Referencias:

http://www.postgradoeinvestigacion.uadec.mx/CienciaCierta/CC30/3.html

                       http://www.slideshare.net/mauro1204/sandoya-fernando-mtodos-exactos-y-heursticos-para-el-vrp-jornadas