Análisis experimental de heurísticas para el problema del viajante de comercio

Abstract

El Problema del Viajante de Comercio es un problema de optimización de tipo NP-duro cuyo objetivo es, dado un conjunto de puntos y la distancia entre cada par de ellos, encontrar el camino más corto que pase por todos ellos y empiece y acabe en el mismo punto. Este problema aparentemente tan sencillo esconde una gran complejidad a la hora de afrontarlo, pues a medida que va aumentando el número de puntos nos damos cuenta de que resolverlo por fuerza bruta es en vano. Debido a esto y a la importancia de sus aplicaciones se han realizado numerosos estudios acerca del problema, centrados normalmente en el diseño de heurísticas con el n de reducir el tiempo de cálculo de soluciones. En este Trabajo de Fin de Grado se ha llevado a cabo la implementación en el lenguaje de programación Haskell de varias de esas heurísticas y de un algoritmo de fuerza bruta con el objetivo de hacer al nal de la presente memoria un análisis experimental comparativo de la e ciencia de cada uno de estos algoritmos.