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

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, the authors 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.

• Record URL:
  http://dx.doi.org/10.1109/TITS.2022.3147924
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/41297384
• Supplemental Notes:
  • Copyright © 2022, IEEE.
• Authors:
  • Zhou, Yangming
  • Xu, Wenqiang
  • Fu, Zhang-Hua
  • Zhou, MengChu
• Publication Date: 2022-9

Language

• English

Media Info

• Media Type: Web
• Pagination: pp 16072-16082
• Serial:
  • IEEE Transactions on Intelligent Transportation Systems
  • Volume: 23
  • Issue Number: 9
  • Publisher: Institute of Electrical and Electronics Engineers (IEEE)
  • ISSN: 1524-9050
  • Serial URL: http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=6979

Subject/Index Terms

• TRT Terms: Accessibility; Neighborhoods; Transportation planning; Traveling salesman problem
• Subject Areas: Highways; Planning and Forecasting;

Filing Info

• Accession Number: 01871653
• Record Type: Publication
• Files: TRIS
• Created Date: Jan 24 2023 11:15AM