Resumen

Este artículo presenta un novedoso método, basado en elementos del pensamiento sistémico, para solucionar instanciasdel problema del vendedor viajero (TSP), el cual es comparado en términos de eficacia y eficiencia con “nearestneighbour”, “cheapest insertion”, “two-way exchange improvement” y “branch and bound”. El primer apartado introducela 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 deDuncan para los factores: método y cantidad de ciudades; este apartado finaliza con el análisis del comportamiento dela proporción de “fracasos” del algoritmo propuesto a medida que aumenta la complejidad del TSP. Como resultado, seobtiene 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 laheurística denominada “sacrificio cortoplacista” es inspirado en el análisis sistémico del “vecino más cercano”, al cualse le identifica el arquetipo de “soluciones rápidas que fallan”, con aplicación a decisiones cotidianas. La tetraheurísticasistémica se destaca, respecto a las demás, en solución arrojada y en tiempo computacional consumido, especialmentecuando incrementa la complejidad del TSP.

INTRODUCCIÓN

La investigación de operaciones conocida como ciencia de la toma de decisiones tiene décadas de existencia y, si bien tiene su origen en aplicaciones militares [1], cobra cada vez mayor rigor en las decisiones empresariales, tanto en el ámbito de producción como en servicios [2-4].

Dentro de las necesidades empresariales a las que puede aportarse con el uso de esta rama se encuentran los problemas de optimización combinatoria, caracterizados porque las variables de decisión son de tipo discreto y sus diferentes soluciones se forman a raíz de la ordenación de números enteros. A pesar de la relevancia de esta disciplina, su aplicación a problemas reales no es tan simple como seguramente se desea, debido a la cantidad de variables y limitantes que rodean una decisión empresarial en términos combinatorios.

Bajo este contexto retador, quizá uno de los problemas más famosos y complejos de la optimización combinatoria es el "agente viajero" o TSP (traveling salesman problem). Este problema es considerado en el ámbito científico y empresarial como una referencia "obligada" para validar cualquier método de resolución de problemas de optimización combinatoria tipo NP-hard [5-6].

• Materias:Modelo de optimización Análisis computacional Algoritmo de programación Técnica heurística
• Subjects:Optimization model Computational analysis Programming algorithm Metaheuristic technique
• Palabras claves:Optimización combinatoria, tetraheurística, pensamiento sistémico, problema del vendedor viajero.
• Keywords:Combinatorial optimization, tetraheuristics, systems thinking, travelling salesman problem.