Enhancing the multiple traveling salesman problem solutions through Harris Hawks optimization and machine learning techniques

Authors

DOI:

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

Keywords:

combinatorial optimization problems, initialization, metaheuristic, parameter tuning, reinforcement learning

Abstract

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.

Downloads

Download data is not yet available.

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

RCSI

Downloads

Published

2024-07-10

How to Cite

Hussein, A. A., Hameed, M. A., & Ahmed, S. H. (2024). Enhancing the multiple traveling salesman problem solutions through Harris Hawks optimization and machine learning techniques. Revista Científica De Sistemas E Informática, 4(2), e745. https://doi.org/10.51252/rcsi.v4i2.745