Heurística inspirada en el análisis sistémico del “Vecino más cercano”, para solucionar instancias simétricas TSP, empleando una base comparativa multicriterio

Abstract

Esta tesis aporta evidencia que respalda al pensamiento sistémico como un pertinente campo de inspiración para el desarrollo de nuevos métodos de optimización heurística. Se delimita el alcance a la resolución del TSP simétrico como referente internacional de prueba que es. Se desarrollaron dos métodos: Sacrificio Cortoplacista Adaptativo 2-opt (SCA_2opt) y una versión mejorada (SCA_2_opt_r), los cuales son fruto del análisis sistémico de la regla vecino más cercano, encontrándole el arquetipo “Soluciones contraproducentes”. El SCA se basa en que el viajero renuncie en un momento dado a una ciudad inmediatamente cercana y se traslade hacia la segunda más cercana disponible, luego, el viajero continúa con la regla del vecino más cercano; cada que se realiza el SCA (búsqueda global) se efectúa una búsqueda local 2_opt. Las dos heurísticas resultan prometedoras en el balance entre eficacia y eficiencia en comparación con las heurísticas: vecino más cercano, Inserción más barata y 2-opt, y con 19 metaheurísticas en las categorías: Colonia de hormigas, Algoritmos genéticos, Enfriamiento simulado y Otras./Abstract. This thesis provides evidence that supports the relevant systems thinking as a field of inspiration for the development of new heuristic optimization methods. It delineates the scope of the resolution of the symmetric TSP as an international benchmark proves it. Two methods were developed: Adaptive short-term sacrifice 2-opt (SCA_2opt) and an enhanced version (SCA_2_opt_r), which are based on analysis systemic nearest neighbor rule, finding the archetypal "Solutions counterproductive ". The SCA is based on the traveler resign at any time a nearby town immediately and move to the second nearest available Of course, the traveler continues with the nearest neighbor rule, each SCA is performed (global search) is performed a local search 2_opt. The two heuristics are promising in the balance between effectiveness and efficiency compared to the heuristics: nearest neighbor, cheapest insertion and 2-opt, and with 19 metaheuristics in categories: ant colony, genetic algorithms, simulated annealing and Othe.