Estudio comparativo de algoritmos heurísticos para el problema del viajante de comercio

Abstract

Este proyecto consiste en un estudio de diferentes heurísticas para la resolución del Problema del Viajante de Comercio. Dejando de lado la búsqueda de una solución óptima, el proyecto se centra en las implementaciones de diversas heurísticas que obtienen soluciones aproximadas. Dichas heurísticas permiten reducir el tiempo de ejecución desde tiempo exponencial a tiempo polinómico. Las heurísticas implementadas son las siguientes: Inserción, Inserción rápida, Envoltura convexa, Árboles de expansión mínima y Savings. En este trabajo se contrastan las complejidades de las mencionadas heurísticas, y la solución que construyen, con las mejores soluciones conocidas de los problemas reales, accesibles a través de internet1. [ABSTRACT] This research is about studying different heuristics for solving the Travelling Salesman Problem. Leaving an optimal solution search, research focuses in implementation of several heuristics that produce non-optimal solutions. These heuristics let us reduce the execution time from exponential time ‘til polinomic time. The implemented heuristic here are: Nearest neighbor, Insertion, Fast insertion, Convex hull, Spanning Trees and Savings. So research is based on checking complexities of aformentioned heuristics, and solutions which they makes, with best known solutions for the real data problems, open to anybody in internet1.