A Parallel Algorithm for Solving General Colored Traveling Salesman Problems
- Resource Type
- Conference
- Authors
- Ding, Penghui; Xu, Xiangping; Li, Jun
- Source
- 2021 36th Youth Academic Annual Conference of Chinese Association of Automation (YAC) Chinese Association of Automation (YAC), 2021 36th Youth Academic Annual Conference of. :485-490 May, 2021
- Subject
- Aerospace
Communication, Networking and Broadcast Technologies
Components, Circuits, Devices and Systems
Computing and Processing
Power, Energy and Industry Applications
Robotics and Control Systems
Transportation
Instruction sets
Computational modeling
Urban areas
Color
Traveling salesman problems
Search problems
Partitioning algorithms
General colored traveling salesman problem
variable neighborhood search
parallel computing
intelligent optimization
- Language
A colored traveling salesman problem (CTSP) is a generalization of the well-known multiple traveling salesman problem. It utilizes colors to differentiate the accessibility of its cities to ward its salesmen. All the existing algorithms for solving CTSP are serial ones. This paper presents for the first time a parallel algorithm framework for solving general CTSP. Then, an improved variable neighborhood search algorithm is proposed by using this algorithm framework. Finally, extensive simulations are conducted in various test cases. The results show that the algorithm proposed is superior to the compared serial algorithms in terms of convergence and solution quality.