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 computatio...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on intelligent transportation systems 2022-09, Vol.23 (9), p.16072-16082
Main Authors: Zhou, Yangming, Xu, Wenqiang, Fu, Zhang-Hua, Zhou, MengChu
Format: Article
Language:English
Subjects:
Algorithms
Biological cells
Color
colored traveling salesman problem
Graphs
iterated local search
Multi-neighborhood search
Neighborhoods
Robots
Searching
Simulated annealing
Simulation
Traveling salesman problem
Traveling salesman problems
Upper bound
Upper bounds
Urban areas
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1524-9050
1558-0016
DOI:10.1109/TITS.2022.3147924