Mejora de las soluciones del problema del viajante múltiple mediante técnicas de aprendizaje automático y optimización de Harris Hawks

Ahmed Abdulmunem Hussein; Musa A. Hameed; Saddam Hamdan Ahmed

doi:10.51252/rcsi.v4i2.745

Autores/as

Ahmed Abdulmunem Hussein University of Samarra https://orcid.org/0000-0002-9522-3842
Musa A. Hameed University of Tikrit https://orcid.org/0000-0002-2006-0022
Saddam Hamdan Ahmed Directorate of Education Diyala https://orcid.org/0009-0005-9129-3893

DOI:

https://doi.org/10.51252/rcsi.v4i2.745

Palabras clave:

problemas de optimización combinatoria, inicialización, metaheurísticas, ajuste de parámetros, aprendizaje por refuerzo

Resumen

Este trabajo presenta un enfoque para resolver el Problema del Viajante Múltiple (mTSP) mediante la integración de algoritmos metaheurísticos (MHs) con técnicas de aprendizaje automático (ML). En particular, se desarrolló el algoritmo de Optimización Discreta de Halcones de Harris (DHHO) para manejar la naturaleza discreta del mTSP, ya que el algoritmo original de Optimización de Halcones de Harris (HHO) fue diseñado para problemas continuos. El algoritmo DHHO, mejorado con mecanismos de aprendizaje basados en SARSA para la inicialización de soluciones y ajuste de parámetros, mejora significativamente la eficiencia de las soluciones del mTSP. Al aprovechar la adaptabilidad del ML dentro del robusto marco de MH, este estudio ofrece una nueva perspectiva sobre los problemas de optimización combinatoria, superando las mejores soluciones conocidas (BKS) en varias instancias del mTSP. Los resultados se probaron utilizando instancias de referencia de TSPLIB, incluyendo Att48, Berlin52, Bier127, Pr76 y Rat99, para dos, tres y cuatro vendedores, logrando resultados óptimos en 12 de las 15 instancias. El rendimiento del DHHO se validó por la calidad de las soluciones y la consistencia a lo largo de múltiples ejecuciones, obteniendo resultados óptimos en 5 de 5 instancias para dos vendedores, 3 de 5 para tres vendedores y 4 de 5 para cuatro vendedores. La validación estadística mediante la prueba de rango con signo de Wilcoxon confirmó la significancia de estas mejoras (p < 0.05). Este trabajo destaca el impacto de integrar MHs y ML, contribuyendo de manera sustancial a la literatura actual.

Citas

Belhor, M., El-Amraoui, A., Jemai, A., & Delmotte, F. (2023). Learning-Based Metaheuristic Approach for Home Healthcare Optimization Problem. Comput. Syst. Sci. Eng., 45(1), 1–19. https://doi.org/10.32604/csse.2023.029058 DOI: https://doi.org/10.32604/csse.2023.029058

Cheikhrouhou, O., & Khoufi, I. (2021). A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy. Computer Science Review, 40, 100369. https://doi.org/10.1016/j.cosrev.2021.100369 DOI: https://doi.org/10.1016/j.cosrev.2021.100369

de Castro Pereira, S., Solteiro Pires, E. J., & de Moura Oliveira, P. B. (2023). Ant-Balanced Multiple Traveling Salesmen: ACO-BmTSP. Algorithms, 16(1), 37. https://doi.org/10.3390/a16010037 DOI: https://doi.org/10.3390/a16010037

Ghani, J. A., Choudhury, I. A., & Hassan, H. H. (2004). Application of Taguchi method in the optimization of end milling parameters. Journal of Materials Processing Technology, 145(1), 84–92. https://doi.org/10.1016/S0924-0136(03)00865-3 DOI: https://doi.org/10.1016/S0924-0136(03)00865-3

Gulcu, S. D., & Ornek, H. K. (2019). Solution of multiple travelling salesman problem using particle swarm optimization based algorithms. International Journal of Intelligent Systems and Applications in Engineering, 7(2), 72–82. https://doi.org/10.18201//ijisae.2019252784 DOI: https://doi.org/10.18201/ijisae.2019252784

Guo, Y., Wang, Y., Yang, I.-H., & Sycara, K. (2023). Reinforcement learning methods for network-based transfer parameter selection. Intelligence & Robotics, 3(3), 402–419. https://doi.org/10.20517/ir.2023.23 DOI: https://doi.org/10.20517/ir.2023.23

Hamza, A., Darwish, A. H., & Rihawi, O. (2023). A new local search for the bees algorithm to optimize multiple traveling salesman problem. Intelligent Systems with Applications, 200242. https://doi.org/10.1016/j.iswa.2023.200242 DOI: https://doi.org/10.1016/j.iswa.2023.200242

He, P., Hao, J.-K., & Xia, J. (2024). Learning-guided iterated local search for the minmax multiple traveling salesman problem. ArXiv Preprint ArXiv:2403.12389. https://doi.org/10.48550/arXiv.2403.12389

Heidari, A. A., Mirjalili, S., Faris, H., Aljarah, I., Mafarja, M., & Chen, H. (2019). Harris hawks optimization: Algorithm and applications. Future Generation Computer Systems, 97, 849–872. https://doi.org/10.1016/j.future.2019.02.028 DOI: https://doi.org/10.1016/j.future.2019.02.028

Hildebrandt, F. D., Thomas, B. W., & Ulmer, M. W. (2023). Opportunities for reinforcement learning in stochastic dynamic vehicle routing. Computers & Operations Research, 150, 106071. https://doi.org/10.1016/j.cor.2022.106071 DOI: https://doi.org/10.1016/j.cor.2022.106071

Hussein, A. A., Yassen, E. T., & Rashid, A. N. (2023). Grey Wolf Optimizer for Green Vehicle Routing Problem. International Journal of Intelligent Engineering & Systems, 16(5). https://doi.org/10.22266/ijies2023.1031.53 DOI: https://doi.org/10.22266/ijies2023.1031.53

Kusumahardhini, N., Hertono, G. F., & Handari, B. D. (2020). Implementation of K-Means and crossover ant colony optimization algorithm on multiple traveling salesman problem. Journal of Physics: Conference Series, 1442(1), 012035. https://doi.org/10.1088/1742-6596/1442/1/012035 DOI: https://doi.org/10.1088/1742-6596/1442/1/012035

Latah, M. (2016). Solving multiple TSP problem by K-means and crossover based modified ACO algorithm. International Journal of Engineering Research and Technology, 5(02). https://doi.org/10.17577/IJERTV5IS020474

Liu, Y., & Cao, B. (2020). A novel ant colony optimization algorithm with Levy flight. Ieee Access, 8, 67205–67213. https://doi.org/10.1109/ACCESS.2020.2985498 DOI: https://doi.org/10.1109/ACCESS.2020.2985498

Mzili, I., Mzili, T., & Riffi, M. E. (2023). Efficient routing optimization with discrete penguins search algorithm for MTSP. Decision Making: Applications in Management and Engineering, 6(1), 730–743. https://doi.org/10.31181/dmame04092023m DOI: https://doi.org/10.31181/dmame04092023m

Nand, R., Chaudhary, K., & Sharma, B. (2024). Single Depot Multiple Travelling Salesman Problem Solved With Preference-Based Stepping Ahead Firefly Algorithm. IEEE Access, 12, 26655–26666. https://doi.org/10.1109/ACCESS.2024.3366183 DOI: https://doi.org/10.1109/ACCESS.2024.3366183

Pop, P. C., Cosma, O., Sabo, C., & Sitar, C. P. (2023). A Comprehensive Survey on the Generalized Traveling Salesman Problem. European Journal of Operational Research. https://doi.org/10.1016/j.ejor.2023.07.022 DOI: https://doi.org/10.1016/j.ejor.2023.07.022

Ramanathan, T., Suresh, S., & Rao, T. S. (2023). Multiple Depot MTSP using Genetic Algorithm and Reinforcement Learning. 2023 Second International Conference on Augmented Intelligence and Sustainable Systems (ICAISS), 440–446. https://doi.org/10.1109/ICAISS58487.2023.10250669 DOI: https://doi.org/10.1109/ICAISS58487.2023.10250669

Reinelt, G. (1991). TSPLIB—A traveling salesman problem library. ORSA Journal on Computing, 3(4), 376–384. https://doi.org/10.1287/ijoc.3.4.376 DOI: https://doi.org/10.1287/ijoc.3.4.376

Singh, A. (2016). A review on algorithms used to solve multiple travelling salesman problem. International Research Journal of Engineering and Technology (IRJET), 3(4), 598–603. https://www.irjet.net/archives/V3/i4/IRJET-V3I4120.pdf

Sui, J., Ding, S., Liu, R., Xu, L., & Bu, D. (2021). Learning 3-opt heuristics for traveling salesman problem via deep reinforcement learning. Asian Conference on Machine Learning, 1301–1316. https://proceedings.mlr.press/v157/sui21a

Taguchi, G., & Phadke, M. S. (1984). Quality engineering through design optimization. Quality Control, Robust Design, and the Taguchi Method, 77–96. https://doi.org/10.1007/978-1-4684-1472-1_5 DOI: https://doi.org/10.1007/978-1-4684-1472-1_5

Zhang, K., Yang, Z., & Başar, T. (2021). Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, 321–384. https://doi.org/10.1007/978-3-030-60990-0_12 DOI: https://doi.org/10.1007/978-3-030-60990-0_12