Solving Colored Traveling Salesman Problem via Multi-neighborhood Simulated Annealing Search

Yangming Zhou, Wenqiang Xu, Zhang Hua Fu, Mengchu Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A colored traveling salesman problem (CTSP) is an important variant of the well-known multiple traveling salesman problem, which uses colors to differentiate salesmen's accessibility to individual cities to be visited. As a highly useful model for some complex scheduling problems, CTSP is NP-hard. A Multi-neighborhood Simulated Annealing Search (MSAS) approach is proposed to solve it in this paper. Starting from an initial solution, it iterates through two complementary neighborhoods: intra-route and inter-route neighborhoods. Experiments on three groups of 60 widely-used benchmark instances show that it achieves highly competitive performance compared to state-of-the-art algorithms. Moreover, MSAS can be integrated into other search methods to further improve performance, which is demonstrated by using a recently proposed iterated two-phase local search.

Original languageEnglish (US)
Title of host publicationICNSC 2021 - 18th IEEE International Conference on Networking, Sensing and Control
Subtitle of host publicationIndustry 4.0 and AI
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781665440486
DOIs
StatePublished - 2021
Event18th IEEE International Conference on Networking, Sensing and Control, ICNSC 2021 - Xiamen, China
Duration: Dec 3 2021Dec 5 2021

Publication series

NameICNSC 2021 - 18th IEEE International Conference on Networking, Sensing and Control: Industry 4.0 and AI

Conference

Conference18th IEEE International Conference on Networking, Sensing and Control, ICNSC 2021
Country/TerritoryChina
CityXiamen
Period12/3/2112/5/21

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Computer Networks and Communications
  • Statistics, Probability and Uncertainty
  • Control and Optimization
  • Sensory Systems

Keywords

  • Colored traveling salesman problem
  • Heuristic search
  • Intelligent transportation
  • Local search
  • Simulated annealing

Fingerprint

Dive into the research topics of 'Solving Colored Traveling Salesman Problem via Multi-neighborhood Simulated Annealing Search'. Together they form a unique fingerprint.

Cite this