Multi-Neighborhood Simulated Annealing-Based Iterated Local Search for Colored Traveling Salesman Problems

Yangming Zhou, Wenqiang Xu, Zhang Hua Fu, Meng Chu Zhou

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

A coloring traveling salesman problem (CTSP) generalizes the well-known multiple traveling salesman problem, where colors are used to differentiate salesmen's the accessibility to individual cities to be visited. As a useful model for a variety of complex scheduling problems, CTSP is computationally challenging. In this paper, we propose a Multi-neighborhood Simulated Annealing-based Iterated Local Search (MSAILS) to solve it. Starting from an initial solution, it iterates through three sequential search procedures: a multi-neighborhood simulated annealing search to find a local optimum, a local search-enhanced edge assembly crossover to find nearby high-quality solutions around a local optimum, and a solution reconstruction procedure to move away from the current search region. Experimental results on two groups of 45 medium and large benchmark instances show that it significantly outperforms state-of-the-art algorithms. In particular, it is able to discover new upper bounds for 29 instances while matching 8 previous best-known upper bounds. Hence, this work greatly advances the field of CTSP.

Original languageEnglish (US)
Pages (from-to)16072-16082
Number of pages11
JournalIEEE Transactions on Intelligent Transportation Systems
Volume23
Issue number9
DOIs
StatePublished - Sep 1 2022

All Science Journal Classification (ASJC) codes

  • Automotive Engineering
  • Mechanical Engineering
  • Computer Science Applications

Keywords

  • Multi-neighborhood search
  • colored traveling salesman problem
  • iterated local search
  • simulated annealing

Fingerprint

Dive into the research topics of 'Multi-Neighborhood Simulated Annealing-Based Iterated Local Search for Colored Traveling Salesman Problems'. Together they form a unique fingerprint.

Cite this