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

Xiangping Xu, Jun Li, Meng Chu Zhou

Research output: Contribution to journalArticlepeer-review

37 Scopus citations


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.

Original languageEnglish (US)
Article number9007037
Pages (from-to)1583-1593
Number of pages11
JournalIEEE Transactions on Intelligent Transportation Systems
Issue number3
StatePublished - Mar 2021

All Science Journal Classification (ASJC) codes

  • Automotive Engineering
  • Mechanical Engineering
  • Computer Science Applications


  • Colored traveling salesman problem
  • Delaunay triangulation
  • genetic algorithm
  • hypergraph
  • intelligent optimization
  • variable neighborhood search


Dive into the research topics of 'Delaunay-Triangulation-Based Variable Neighborhood Search to Solve Large-Scale General Colored Traveling Salesman Problems'. Together they form a unique fingerprint.

Cite this