Una metaheurística co-evolutiva para el problema del viajante de comercio

Abstract

En este Trabajo de Grado se presenta una estrategia general (metaheurística) para la resolución del Problema del Viajante de Comercio. Éste es un problema clásico de optimización combinatoria, cuyo conjunto de soluciones posibles es finito, pero demasiado numeroso para ser manejado en forma directa. Dado un conjunto de ciudades, y una medida de “costo” entre ellas, el problema consiste en hallar un camino cerrado (tour) de costo mínimo, que visite cada ciudad exactamente una vez. El costo puede estar representado por la distancia entre las ciudades, o por cualquier otra medida, tal como el tiempo que las separa o el costo de un pasaje entre ellas. Este problema puede aplicarse en muchas situaciones prácticas, tales como ruteo de vehículos, secuenciamiento de tareas, conexión de módulos electrónicos. Además reviste una importancia teórica para la Teoría de Complejidad, pues pertenece a la clase de los problemas combinatorios NP- Completos, para los cuales se conjetura que el tiempo de cómputo requerido para hallar la solución exacta crece al menos exponencialmente con el tamaño de la instancia considerada. Por esto es necesario buscar heurísticas que encuentren rápidamente tours cercanos al óptimo. En el contexto de los problemas de optimización combinatoria, se pueden definir las heurísticas como técnicas que producen soluciones factibles rápidamente, en cuanto al tiempo de cómputo requerido, pero tales soluciones no son necesariamente óptimas. Estos procedimientos tienen una justificación intuitiva. Las metaheurísticas son estrategias que generalmente guían otras heurísticas, y que no dependen de las características del problema a resolver. El desarrollo de metaheurísticas para resolver este problema, permite que las mismas técnicas puedan aplicarse a una gran variedad de problemas combinatorios. El Problema del Viajante de Comercio se ha utilizado siempre para ensayar diferentes enfoques de optimización combinatoria, incluyendo las técnicas clásicas de optimización local, así como variantes más recientes: Búsqueda Tabú, Redes Neuronales, Algoritmos Genéticos. Es un dominio atípico desde el punto de vista teórico y experimental. Luego de presentar el Problema del Viajante de Comercio, las secciones iniciales de este Trabajo describirán por separado los componentes de la metaheurística a desarrollar: heurísticas de búsqueda local, Búsqueda Local Guiada, Algoritmos Meméticos. En la Sección 6, se integrarán estos conceptos para diseñar una estrategia de resolución del Problema del Viajante de Comercio, que intenta aprovechar las mejores características de cada uno de estos enfoques. Las últimas secciones presentarán los resultados de los experimentos realizados y las conclusiones del trabajo.