Algoritmos heurísticos para el problema del viajante: colonia de hormigas y Christofides

Abstract

Dado un grafo ponderado G=(V,E), el Travelling Salesman Problem (TSP) consiste en encontrar (si existe) el ciclo Hamiltoniano de G que minimiza la suma de los costes de las aristas utilizadas. Como es un problema NP-completo, solo se puede resolver de manera exacta para ejemplos muy pequeños. En este trabajo exploramos dos métodos heurísticos para resolverlo. La parte más importante consistirá en estudiar la optimización por colonia de hormigas (OCH), una técnica probabilística utilizada en problemas computacionales que pueden reducirse a hallar la mejor ruta en un grafo. En concreto se estudiarán dos algoritmos de OCH: Sistema de Hormigas (SH) y Sistema de Hormigas MAX-MIN (SHMM). Por otro lado, describiremos y usaremos también el algoritmo de Christofides, basado en árboles generadores y emparejamientos de peso mínimo, que da una solución aproximada del TSP. Utilizando una implementación propia de los dos algoritmos de OCH en Python y una de libre acceso de Christofides, se aplicarán a varias instancias del TSP con el objetivo de analizar los resultados y sacar conclusiones acerca de su eficacia y rendimiento.

Given a weighted graph G=(V,E), the Travelling Salesman Problem (TSP) consists in finding (if it exists) the Hamiltonian cycle of G that minimizes the sum of the costs of the edges used. Since it is an NP-hard problem, it can only be solved exactly for very small examples. In this paper we explore two heurıstic methods to solve it differently. The most important part will consist of studying ant colony optimization (ACO), a probabilistic technique used in computational problems that can be reduced to finding the best path in a graph. Specifically, two ACO algorithms will be studied: Ant System (AS) and Max-Min Ant System (MMAS). On the other hand, we will also describe and use the Christofides algorithm, based on generating trees and minimum-weight pairings, which gives an approximate solution of the TSP. Using our own implementation of the two ACO variants in python and a freely available implementation of Christofides, we will apply them to several instances of the TSP in order to analyze the results and draw conclusions about their effectiveness and performance.