Solución al problema de generación de planes de trabajo basado en el problema del agente viajero utilizando el algoritmo genético Chu-Beasley

John Fredy Castañeda Londoño; Ramón Alfonso Gallego Rendón; Eliana Mirledy Toro Ocampo

doi:10.24054/rcta.v1i45.3079

Authors

John Fredy Castañeda Londoño Universidad Tecnológica de Pereira https://orcid.org/0000-0002-5957-6966
Ramón Alfonso Gallego Rendón Universidad Tecnológica de Pereira https://orcid.org/0000-0002-0160-8929
Eliana Mirledy Toro Ocampo Universidad Tecnológica de Pereira https://orcid.org/0000-0002-6333-0977

DOI:

https://doi.org/10.24054/rcta.v1i45.3079

Keywords:

traveling salesman problem, genetic algorithm, traffic

Abstract

This article introduces a methodology to address logistics management by generating work plans based on the Multiple Traveling Salesman Problem (MTSP). The primary objective is cost minimization, which can manifest in two forms: distance or the time required for executing work plans. Two methods are used to measure distance: the first calculates spherical distances using the Haversine formula, and the second leverages Google Maps data to obtain traffic-related travel time information. One of the goals of this methodology is to validate the benefits of carrying out optimizations on multiple routes affected by traffic variables, resulting in travel times, within a modern, modular, and rapidly implementable software architecture. To solve the mathematical model, the Chu-Beasley genetic algorithm is used with enhancements through the Or-Opt operator, aiming to obtain high-quality solutions with reasonable times in daily logistics planning. In the results analysis stage, tests were conducted using instances obtained from real company locations whose operations are affected by logistics performance. The study's results were compared to those of an expert in the field using the nearest neighbor algorithm as a reference, focusing on the distance variable, which demonstrated significant improvements and confirmed the benefits of using logistics planning with optimization algorithms considering traffic variables.

Downloads

Download data is not yet available.

References

W. R. Abel and L. M. Blumenthal, “Distance Geometry of Metric Arcs,” Am. Math. Mon., vol. 64, no. 8P2, pp. 1–10, Oct. 1957, doi: 10.1080/00029890.1957.11989113.

K. C. Gilbert and R. B. Hofstra, “A New Multiperiod Multiple Traveling Salesman Problem with Heuristic and Application to a Scheduling Problem,” Decis. Sci., vol. 23, no. 1, pp. 250–259, 1992, doi: 10.1111/J.1540-5915.1992.TB00387.X.

A. Langevin, F. Soumis, and J. Desrosiers, “Classification of travelling salesman problem formulations,” Oper. Res. Lett., vol. 9, no. 2, pp. 127–132, Mar. 1990, doi: 10.1016/0167-6377(90)90052-7.

T. Bektas, “The multiple traveling salesman problem: an overview of formulations and solution procedures,” Omega, vol. 34, no. 3, pp. 209–219, Jun. 2006, doi: 10.1016/J.OMEGA.2004.10.004.

R. I. Bolaños, E. M. Toro O, and M. Granada E, “A population-based algorithm for the multi travelling salesman problem,” Int. J. Ind. Eng. Comput., vol. 7, no. 2, pp. 245–256, Mar. 2016, doi: 10.5267/J.IJIEC.2015.10.005.

O. Cheikhrouhou and I. Khoufi, “A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy,” Computer Science Review, vol. 40. 2021. doi: 10.1016/j.cosrev.2021.100369.

C. Colombaroni, M. Mohammadi, and G. Rahmanifar, “Makespan minimizing on multiple travel salesman problem with a learning effect of visiting time,” WSEAS Trans. Syst. Control, vol. 15, pp. 477–489, 2020, doi: 10.37394/23203.2020.15.50.

R. G. Mbiadou Saleu, L. Deroussi, D. Feillet, N. Grangeon, and A. Quilliot, “The Parallel Drone Scheduling Problem with Multiple Drones and Vehicles,” Eur. J. Oper. Res., vol. 300, no. 2, pp. 571–589, Jul. 2022, doi: 10.1016/j.ejor.2021.08.014.

A. Király and J. Abonyi, “A Google Maps based novel approach to the optimization of multiple Traveling Salesman problem for limited distribution systems,” Acta Agrar. Kaposváriensis, vol. 14, no. 3, pp. 1–14, 2010, [Online]. Available: https://journal.uni-mate.hu/index.php/aak/article/view/1952

R. D. H. Tobing, “A food ordering system with delivery routing optimization using global positioning system (GPS) technology and google maps,” Internetworking Indones. J., vol. 8, no. 1, pp. 17–21, 2016.

I. Ilhan, “An Application on Mobile Devices with Android and IOS Operating Systems Using Google Maps APIs for the Traveling Salesman Problem,” Appl. Artif. Intell., vol. 31, no. 4, pp. 332–345, 2017, doi: 10.1080/08839514.2017.1339983.

L. G. Hernández-Landa and R. E. Mata-Martínez, “Accurate solutions for real instances of the traveling salesman problem using Google Maps APIs,” Proc. Int. Conf. Ind. Eng. Oper. Manag., vol. 2018, no. SEP, pp. 837–843, 2018.

Z. Al-Jabbar, “Using Genetic Algorithm to Solve Travelling Salesman Optimization Problem Based on Google Map Coordinates for Duhok City Areas,” Acad. J. Nawroz Univ., vol. 7, no. 3, pp. 99–114, 2018, doi: 10.25007/ajnu.v7n3a207.

C. Zambrano-Vega, G. Acosta, J. Loor, B. Suárez, C. Jaramillo, and B. Oviedo, “A Sales Route Optimization Mobile Application Applying a Genetic Algorithm and the Google Maps Navigation System,” Adv. Intell. Syst. Comput., vol. 918, pp. 517–527, 2019, doi: 10.1007/978-3-030-11890-7_50.

D. E. Goldberg and R. Lingle, “Alleles, loci, and the traveling salesman problem,” in Proceedings of an International Conference on Genetic Algorithms, 1985, pp. 10–19.

R. A. Gallego Rendón, E. M. Toro Ocampo, and A. H. Escobar Zuluaga, Técnicas Heurísticas y Metaheurísticas. Universidad Tecnológica de Pereira. Vicerrectoría de Investigaciones, Innovación y Extensión. Ingenierías Eléctrica, Electrónica, Física y Ciencias de la Computación, 2015. Accessed: Sep. 03, 2023. [Online]. Available: https://unilibros.co/gpd-tecnicas-heuristicas-y-metaheuristicas.html