%0 Generic
%A Rincón García, Sergio
%A Oller Peña, Alberto
%A Mártinez Maqueda, Daniel
%T Estudio comparativo de algoritmos heurísticos para el problema del viajante de comercio
%J Trabajos de curso (Departamento de Sistemas Informáticos y Programación, FDI)
%D 2003
%U https://hdl.handle.net/20.500.14352/61157
%X Este proyecto consiste en un estudio de diferentes heurísticas para la resolución delProblema 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 queobtienen soluciones aproximadas.Dichas heurísticas permiten reducir el tiempo de ejecución desde tiempo exponencial atiempo 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 lasolució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 SalesmanProblem. Leaving an optimal solution search, research focuses in implementation ofseveral heuristics that produce non-optimal solutions.These heuristics let us reduce the execution time from exponential time ‘til polinomictime. 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, andsolutions which they makes, with best known solutions for the real data problems, opento anybody in internet1.
%~