Enhancing the multiple traveling salesman problem solutions through Harris Hawks optimization and machine learning techniques
DOI:
https://doi.org/10.51252/rcsi.v4i2.745Keywords:
combinatorial optimization problems, initialization, metaheuristic, parameter tuning, reinforcement learningAbstract
This work introduces an approach to solving the Multiple Traveling Salesman Problem (mTSP) by integrating metaheuristic algorithms (MHs) with machine learning (ML) techniques. Specifically, the Discrete Harris Hawks Optimization (DHHO) algorithm was developed to handle the discrete nature of the mTSP, as the original Harris Hawks Optimization (HHO) was designed for continuous problems. The DHHO algorithm, enhanced with SARSA-based learning mechanisms for solution initialization and parameter tuning, significantly improves the efficiency of mTSP solutions. By leveraging ML's adaptability within the robust MH framework, this study offers a novel perspective on combinatorial optimization problems, surpassing the best-known solutions (BKS) in various mTSP instances. The results were tested using TSPLIB benchmark instances, including Att48, Berlin52, Bier127, Pr76, and Rat99, for two, three, and four salesmen, achieving optimal results in 12 out of 15 instances. The DHHO's performance was validated by the quality of solutions and consistency across multiple runs, with optimal results in 5 out of 5 instances for two salesmen, 3 out of 5 for three salesmen, and 4 out of 5 for four salesmen. Statistical validation using the Wilcoxon signed-rank test confirmed the significance of these improvements (p < 0.05). This work highlights the impact of integrating MHs and ML, making a substantial contribution to the current literature.
References
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
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Ahmed Abdulmunem Hussein, Musa A. Hameed, Saddam Hamdan Ahmed
This work is licensed under a Creative Commons Attribution 4.0 International License.
The authors retain their rights:
a. The authors retain their trademark and patent rights, as well as any process or procedure described in the article.
b. The authors retain the right to share, copy, distribute, execute and publicly communicate the article published in the Revista Científica de Sistemas e Informática (RCSI) (for example, place it in an institutional repository or publish it in a book), with an acknowledgment of its initial publication in the RCSI.
c. Authors retain the right to make a subsequent publication of their work, to use the article or any part of it (for example: a compilation of their works, notes for conferences, thesis, or for a book), provided that they indicate the source of publication (authors of the work, journal, volume, number and date).
