Algoritmo de la BÚSQUEDA TABÚ SIMPLE

Objetivos        

Objetivo Fundamental:        

Antecedentes:        

Metodología:        

Definición del problema.        

Búsqueda Tabú        

Características de la búsqueda tabú        

Estructuras de la búsqueda tabú        

Identificación de las variables.        

Limitaciones.        

Restricciones        

Análisis y Discusión de Resultados:        

Algoritmo de la BÚSQUEDA TABÚ SIMPLE        

¿Qué se necesita para su implementación?        

Tabla 3.1        

¿Cuándo se detiene el proceso?        

Aplicación del algoritmo de la búsqueda tabú        

Selección de la solución inicial:        

Conclusiones y Recomendaciones:        

“Heurística del Agente viajero aplicado al reparto de couriers”

Objetivos

Objetivo Fundamental:

1. Repartir todos los couriers en su destino respectivo con la mayor eficiencia posible.

B. Objetivos Específicos:

1. Elaborar el modelo matemático del problema.
2. Encontrar la ruta más corta para repartir todos los couriers mediante la aplicación de un algoritmo de búsqueda tabú.
3. Calcular los costos ahorrados por la empresa al aplicar la nueva ruta.
4. Analizar y discutir los resultados. 

Antecedentes:

Los orígenes de la Búsqueda Tabú (Tabú Search) datan de finales de los 70. Oficialmente el nombre y la metodología fueron introducidos por Fred Glover en dos artículos (1989). En palabras del autor:

“La búsqueda tabú tiene sus orígenes en procedimientos combinatorios aplicados a problemas de cubrimiento no lineales en los finales de los años 70 y aplicada subsecuentemente a una diversa colección de problemas que van desde secuenciación y balance de canales de computación hasta análisis de clusters y planeamiento de espacio”

La primera solución reportada para resolver el problema del Agente Viajero fue en 1954, cuando George Dantzig, Ray Fulkerson, y Selmer Johnson publicaron la descripción de un método de solución del PAV (Problema del Agente Viajero o sus siglas en inglés TSP – Travel Sailsman Problem) 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 donde un agente viajero desea visitar un conjunto de ciudades, asignándoles un costo por visitar ciudades contiguas (distancia de traslado entre dos ciudades). Para esta solución se propusieron 2 condiciones: regresar a la misma ciudad de la cual partió y no repetir ciudades con el objetivo de encontrar una ruta o un camino con el menor costo posible.

1. En 1832 se menciona el problema en un manual del agentes viajeros con ejemplos de tours por Alemania y Suiza, pero sin un tratamiento matemático.
2. En 1932 Karl Menger “Das botenproblem” Ergebnisse eines Mathematischen Kolloquiums 2 pp.11­12 menciona un problema que enfrentan los mensajeros postales y otros viajeros de encontrar para un número finito de puntos el camino más corto que los une.  
3. Martin Groetschel (1977) encuentra el tour óptimo para 120 ciudades de Alemania.

[pic 1] 

Metodología:

Definición del problema.

El problema del agente viajero, consiste en encontrar la secuencia en que un viajero debe visitar n ciudades, de manera que la distancia recorrida sea mínima. Se trata de un problema NP completo, es decir, la única alternativa para su solución consiste en verificar todas las posibles opciones para encontrar cuál es la óptima, hay que tener en cuenta que si el número de ciudades es n, el número de posibles recorridos a ensayar resulta ser n!/(2n). 

Figura 1: Problema del Agente Viajero

[pic 2] 

Principales algoritmos para resolver el problema del agente viajero:

• Algoritmos Genéticos(AGs)
• Recocido Simulado(RS)
• Colonias de Hormigas
• Búsqueda Tabú

Para resolver el problema usaremos el algoritmo de Búsqueda Tabú.

Búsqueda Tabú

S​urge en un intento de dotar de “inteligencia” a los algoritmos de búsqueda local. Según Fred Glover en 1986. La búsqueda tabú es una metaheurística que guía un procedimiento heurístico de búsqueda local en la búsqueda de optimalidad para su resolución de problemas, basadas en procedimientos implícitos y explícitos de aprendizaje.

El marco de memoria adaptativa de la búsqueda tabú no sólo explotaba la historia del proceso de resolución del problema, sino que también exige la creación de estructuras para hacer posible tal explotación. De esta forma, los elementos prohibidos en la búsqueda tabú reciben este estatus por la confianza en una memoria evolutiva, que permite alterar este estado en función de tiempo y las circunstancias. En este sentido es posible asumir que la búsqueda tabú está basada en determinados conceptos que unen los campos de la inteligencia artificial y optimización.

El término tabu(taboo) procede de la polinesia, donde es usado por los aborígenes de la isla Tonga para referirse a cosas que no se pueden ser tocadas porque son sagradas, una acepción más moderna la define como “Una prohibición impuesta por costumbres sociales como que constituye una medida de protección”, también como “marcada como que constituye un riesgo”, esta acepción es la que está más cerca de la esencia del método donde el riesgo a ser evitado es el de seguir un camino no productivo, incluyendo el de ser conducido a una trampa de la que no se puede salir(óptimo local).

...