Delaunay-Triangulation-Based Variable Neighborhood Search to Solve Large-Scale General Colored Traveling Salesman Problems

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 its salesmen. In our prior work, CTSPs are formulated over graphs associated with a city-color matrix. This wo...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on intelligent transportation systems 2021-03, Vol.22 (3), p.1583-1593
Main Authors: Xu, Xiangping, Li, Jun, Zhou, MengChu
Format: Article
Language:English
Subjects:
Color
Colored traveling salesman problem
Delaunay triangulation
genetic algorithm
Genetic algorithms
Graphs
hypergraph
Image color analysis
Insertion
intelligent optimization
Intelligent transportation systems
Search problems
Searching
Traveling salesman problem
Traveling salesman problems
Urban areas
variable neighborhood search
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 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 its salesmen. In our prior work, CTSPs are formulated over graphs associated with a city-color matrix. This work redefines a general colored traveling salesman problem (GCTSP) in the framework of hypergraphs and reveals several important properties of GCTSP. In GCTSP, the setting of city colors is richer than that in CTSPs. As results, it can be used to model and address various complex scheduling problems. Then, a Delaunay-triangulation-based Variable Neighborhood Search (DVNS) algorithm is developed to solve large-scale GCTSPs. At the beginning stage of DVNS, a divide and conquer algorithm is exploited to prepare a Delaunay candidate set for lean insertion. Next, the incumbent solution is perturbed by utilizing greedy multi-insertion and exchange mutation to obtain a variety of neighborhoods. Subsequently, 2-opt and 3-opt are used for local search in turn. Extensive experiments are conducted for many large scale GCTSP cases among which two maximal ones are up to 33000+ cities for 4 salesmen and 240 salesmen given 11000+ cities, respectively. The results show that the proposed method outperforms the existing four genetic algorithms and two VNS methods in terms of search ability and convergence rate.
ISSN:1524-9050
1558-0016
DOI:10.1109/TITS.2020.2972389