Desarrollo de un modelo de planificación de rutas basado en el problema del agente viajero

Abstract

Estudios recientes en el campo de la ingeniería de software han promovido el uso de técnicas novedosas para optimizar procesos y resolver problemas en diversas áreas. Uno de los casos comúnmente estudiados para la selección de rutas óptimas es el del Agente Viajero (TSP en inglés); el cual ha sido pilar para aplicaciones en el mundo real. Este trabajo presenta dos métodos rápidos y computacionalmente económicos aplicables a escenarios bidimensionales enfocados en el TSP, para casos de un único agente (TSPVKM_U) y multi-agente (TSPVKM_M) respectivamente. Los métodos son basados en el paradigma de dividir y conquistar, algoritmos voraces, y agrupación por medio de K-Means. A pesar de que existen soluciones sofisticadas, los métodos propuestos calculan soluciones rápidamente, encontrando un balance entre el tiempo de ejecución y la exactitud. Este estudio concluye con la comparación del rendimiento de los métodos en escenarios comúnmente estudiados de TSPLIB.Recent studies in the field of software engineering have led to novel techniques used to optimize processes and solve problems in several areas. One of these commonly studied problemsfocused on optimal routes’ selectionis the Travelling Salesman Problem (TSP); which has been the foundation for real-world applications. This work presents two computationally inexpensive and fast methods applicable to TSP-like bi-dimensional scenarios for single agent(TSPVKM_U)and multi agent cases(TSPVKM_M), respectively. The methods are based on the divide and conquer paradigm, greedy algorithms, and K-Means clustering. Even though there exist elaborated solutions, the proposed methods calculate solutions in short periods of time, balancing the trade-off between execution time and accuracy. This study concludes by comparing the methods’ performance in commonly studied scenarios from TSPLIB.