Tetraheurística sistémica (THS) para el TSP

RESUMEN: Este artículo presenta un novedoso método, basado en elementos del pensamiento sistémico, para solucionar instancias del problema del vendedor viajero (TSP), el cual es comparado en términos de eficacia y eficiencia con “nearest neighbour”, “cheapest insertion”, “two-way exchange improvement” y “branch and bound”. El primer apartado introduce la optimización combinatoria, el segundo ofrece un marco de referencia, el tercero presenta la metodología empleada, el cuarto apartado presenta el desarrollo de la tetraheurística sistémica, seguido del análisis de varianza y de rangos de Duncan para los factores: método y cantidad de ciudades; este apartado finaliza con el análisis del comportamiento de la proporción de “fracasos” del algoritmo propuesto a medida que aumenta la complejidad del TSP. Como resultado, se obtiene un método para resolver instancias del TSP, conformado por tres heurísticas misionales: 1. “vecino más cercano”, 2. “sacrificio cortoplacista” y 3. “traslado LIFO”, y una de apoyo llamada “búsqueda derecha 4P4”. El diseño de la heurística denominada “sacrificio cortoplacista” es inspirado en el análisis sistémico del “vecino más cercano”, al cual se le identifica el arquetipo de “soluciones rápidas que fallan”, con aplicación a decisiones cotidianas. La tetraheurística sistémica se destaca, respecto a las demás, en solución arrojada y en tiempo computacional consumido, especialmente cuando incrementa la complejidad del TSP

• Autores: Pérez Rave, Jorge Iván; Jaramillo Álvarez, Gloria Patricia; Parra Mesa, Carlos Mario; Moreno Velásquez, Luis Fernando
• Tipo de recurso: Article of investigation
• Fecha de publicación: 2010
• Institución: Universidad de Antioquia
• Repositorio: Repositorio UdeA
• Idioma: spa
• OAI Identifier: oai:bibliotecadigital.udea.edu.co:10495/25732
• Acceso en línea: http://hdl.handle.net/10495/25732
• Palabra clave: Traveling salesman problem (TSP); Análisis de Varianza; Analysis of Variance; Optimización combinatorio; Combinatorial optimization; Pensamiento sistémico; http://id.loc.gov/authorities/subjects/sh85137179
• Rights: openAccess
• License: https://creativecommons.org/licenses/by/4.0/