Journal
JOURNAL OF SUPERCOMPUTING
Volume 77, Issue 10, Pages 11827-11852Publisher
SPRINGER
DOI: 10.1007/s11227-021-03744-1
Keywords
2opt; Elementary breakpoint operator; Multiple traveling salesmen problem; State transition simulated annealing algorithm
Categories
Funding
- National Natural Science Foundation of China [21606159]
- Key Research and Development Program of Shanxi Province [201803D121039]
Ask authors/readers for more resources
This study introduces an intelligent algorithm for solving the multiple traveling salesman problem using metropolitan criteria and basic matrix operations to generate the solution space, while enhancing the ability to capture the global optimal solution by introducing the 2opt neighborhood search structure. Experimental results demonstrate the superior performance of this method in MTSP.
In this study, we consider the multiple traveling salesman problem (MTSP) with multiple depots, closed paths, and a constraint on the number of cities visited by each traveling salesman. In our previous study, we proposed a state transition simulated annealing algorithm (STASA) that employs the Metropolitan criterion for simulated annealing to solve the traveling salesman problem (TSP). The results obtained were significantly improved according to our previous experiments. In the present study, we propose a new intelligent operator to solve the MTSP called an elementary breakpoint operator, which can generate the solution space for MTSP through elementary matrix operations. A neighborhood search structure called 2opt, which can improve the quality of the solution by connecting two shorter non-adjacent arcs, is then introduced into STASA to enhance the ability to capture the global optimal solution. Finally, comparative experiments were conducted based on a wide range of TSPLIB benchmark instances using our proposed algorithm and other algorithms, and the results demonstrated the superior performance of our proposed approach compared with all other state-of-the-art approaches for MTSP.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available