Colored traveling salesman problem

Jun Li, Meng Chu Zhou, Qirui Sun, Xianzhong Dai, Xiaolong Yu

Research output: Contribution to journalArticlepeer-review

109 Scopus citations


The multiple traveling salesman problem (MTSP) is an important combinatorial optimization problem. It has been widely and successfully applied to the practical cases in which multiple traveling individuals (salesmen) share the common workspace (city set). However, it cannot represent some application problems where multiple traveling individuals not only have their own exclusive tasks but also share a group of tasks with each other. This work proposes a new MTSP called colored traveling salesman problem (CTSP) for handling such cases. Two types of city groups are defined, i.e., each group of exclusive cities of a single color for a salesman to visit and a group of shared cities of multiple colors allowing all salesmen to visit. Evidences show that CTSP is NP-hard and a multidepot MTSP and multiple single traveling salesman problems are its special cases. We present a genetic algorithm (GA) with dual-chromosome coding for CTSP and analyze the corresponding solution space. Then, GA is improved by incorporating greedy, hill-climbing (HC), and simulated annealing (SA) operations to achieve better performance. By experiments, the limitation of the exact solution method is revealed and the performance of the presented GAs is compared. The results suggest that SAGA can achieve the best quality of solutions and HCGA should be the choice making good tradeoff between the solution quality and computing time.

Original languageEnglish (US)
Article number6975134
Pages (from-to)2390-2401
Number of pages12
JournalIEEE Transactions on Cybernetics
Issue number11
StatePublished - Nov 2015

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Human-Computer Interaction
  • Computer Science Applications
  • Electrical and Electronic Engineering


  • Genetic algorithm (GA)
  • greedy algorithm
  • hill-climbing algorithm
  • modeling
  • multiple traveling salesman problem (MTSP)
  • simulated annealing (SA) algorithm


Dive into the research topics of 'Colored traveling salesman problem'. Together they form a unique fingerprint.

Cite this