A Hill-Climbing Differential Evolutionary Algorithm for solving Multiple Travelling Salesman Problem

Jinhua Bian; Xiaoxia Zhang

doi:10.54097/fm6hta13

Authors

Jinhua Bian
Xiaoxia Zhang

DOI:

https://doi.org/10.54097/fm6hta13

Keywords:

MTSP Problem, Differential Evolution Algorithm, Hill Climbing Algorithm

Abstract

The Multiple Travelling Salesman Problem (MTSP) is a basic deformation of the Travelling Salesman Problem (TSP), which is a typical NP-Hard problem. For combinatorial optimization problems shaped like MTSP, researchers often use intelligent optimization algorithms such as genetic algorithms, differential evolutionary algorithms, simulated annealing algorithms and other intelligent optimization algorithms to approximate the solution. However, typical intelligent optimization algorithms have the disadvantage of being prone to local convergence and failing to produce theoretically optimal solutions. Based on this, we propose an HCA&DE algorithm that improves the DE algorithm by using the hill-climbing algorithm, and carry out data experiments using the solution set of TSPLIB, which proves the practicality and effectiveness of the algorithm.

Downloads

Download data is not yet available.

References

[1] Zhao Xiaoqiang,Tuo Mingfu. An applied study of task planning problem based on multi-traveler problem model for solving workload equalization[J]. Internet of Things Technology, 2024,14(07): 84-89.DOI:10.16667/j.issn.2095-1302. 2024.07.022.

[2] YANG Hua, CHEN Yanhua, LI Hongyi. Automatic preparation method of contact network maintenance plan based on multi-traveler problem[J]. Electrified Railway,2023,34(01): 81-85.DOI:10.19587/j.cnki.1007-936x.2023.01.016.

[3] Liu Pin. Research based on two-stage heuristic algorithm for multi-traveler problem[D].Northern-Nationalities-University, 2024. DOI:10.27754/d.cnki.gbfmz.2024.000383.

[4] Bao Cong.Research on Evolutionary Algorithms for Access-Constrained Multi-Traveler Problem[D]. Nanjing University of Information Engineering, 2023.DOI: 10.27248/ d.cnki. gnjqc. 2023.001033.

[5] H.R. Zhu. Research on Improving Monophilic Genetic Algorithm to Solve Multi-TravelerProblem[D]. West-China-NormalUniversity,2023.DOI:10.27859/d.cnki.gxhsf.2023.000111.

[6] Dong Yafei. Optimization study of two classes of complex multi-traveler problems based on evolutionary algorithms[D]. Chongqing University, 2022.DOI: 10.27670/ d.cnki. gcqdu. 2022.002674.

[7] SUN Bing, WANG Chuan, YANG Qiang, et al. Evolutionary algorithms for the multiple starting point equilibrium multi-traveler problem[J]. Computer Engineering and Design, 2023, 44(07):2030-2038.DOI:10.16208/j.issn1000-7024. 2023.07.015.