TETRAHEURÍSTICA SISTÉMICA (THS) PARA EL TSP
| Autor: | Carlos Mario Parra Mesa, Luis Fernando Moreno Velásquez, Jorge Iván Pérez Rave, Gloria Patricia Jaramillo Álvarez |
|---|---|
| Rok vydání: | 2010 |
| Předmět: | |
| Zdroj: | Ingeniare. Revista chilena de ingeniería v.18 n.2 2010 SciELO Chile CONICYT Chile instacron:CONICYT |
| ISSN: | 0718-3305 |
| DOI: | 10.4067/s0718-33052010000200006 |
| Popis: | 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-wwy 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|