Colored traveling salesman problem

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

Research output: Contribution to journalArticlepeer-review

126 Scopus citations

Abstract

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
Volume45
Issue number11
DOIs
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

Keywords

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

Fingerprint

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

Cite this