A local optimization algorithm based on eliminating the inclusion and intersection relations between sub tours for multi-traveling salesman problem

Zejun Hu; Guohua Yang

doi:10.1117/12.2668134

20 April 2023 A local optimization algorithm based on eliminating the inclusion and intersection relations between sub tours for multi-traveling salesman problem

Zejun Hu, Guohua Yang

Author Affiliations +

Proceedings Volume 12602, International Conference on Electronic Information Engineering and Computer Science (EIECS 2022); 1260210 (2023) https://doi.org/10.1117/12.2668134
Event: International Conference on Electronic Information Engineering and Computer Science (EIECS 2022), 2022, Changchun, China

Abstract

Aiming at the multi traveling salesman problem(MTSP) of balancing workload, this paper proposes two local optimization operators for heuristic planning algorithm. According to the workload constraint, all the cities in the travel path are allocated to k sub tours, and a feasible solution is obtained. Then, the local optimal solution is found through the local optimization operator to optimize a single sub tour and the method of exchanging vertices between multiple sub tours. Genetic is used for global search, and there are two optimization operators in the local optimization process. Among them, eliminating the inclusion relationship operator is used to eliminate the inclusion relationship between sub tours, and the eliminating intersection relationship operator is used to avoid the intersection between different sub tours. These two operators tend to actively shorten the total length of travel, so the convergence performance is good. Data experiments show that the optimization operator in this paper has obvious optimization ability in solving similar problems of MTSP.

Citation Download Citation

Zejun Hu and Guohua Yang "A local optimization algorithm based on eliminating the inclusion and intersection relations between sub tours for multi-traveling salesman problem", Proc. SPIE 12602, International Conference on Electronic Information Engineering and Computer Science (EIECS 2022), 1260210 (20 April 2023); https://doi.org/10.1117/12.2668134

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available