Colored traveling salesman problem and solution

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

Abstract

Multiple Traveling Salesman Problem (MTSP) is an important combinatorial optimization problem. However, it is applicable to only the cases in which multiple executing individuals (traveling salesman) share the common workspace (city set). It cannot be used to handle many multi-machine engineering systems where multiple machines' workspaces are not the same and partially overlap with each other This paper proposes and formulates a new MTSP called colored traveling salesman problem (CTSP). Each of its salesmen is assigned a private city set and all salesmen share a public city set. Every set of cities is colored differently. To solve CTSP, we present two improved genetic algorithms (GA) by combining the classic one with a greedy algorithm and hill-climbing one to achieve better performance Finally, the algorithms are applied and compared through a case study. The result shows that the hill-climbing GA enjoys the best performance among the investigated ones.

Original languageEnglish (US)
Title of host publication19th IFAC World Congress IFAC 2014, Proceedings
EditorsEdward Boje, Xiaohua Xia
PublisherIFAC Secretariat
Pages9575-9580
Number of pages6
ISBN (Electronic)9783902823625
DOIs
StatePublished - 2014
Event19th IFAC World Congress on International Federation of Automatic Control, IFAC 2014 - Cape Town, South Africa
Duration: Aug 24 2014Aug 29 2014

Publication series

NameIFAC Proceedings Volumes (IFAC-PapersOnline)
Volume19
ISSN (Print)1474-6670

Other

Other19th IFAC World Congress on International Federation of Automatic Control, IFAC 2014
CountrySouth Africa
CityCape Town
Period8/24/148/29/14

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering

Keywords

  • Genetic algorithm
  • Greedy algorithm
  • Hill-climbing algorithm
  • MTSP
  • Modelling
  • TSP

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

Cite this