A decomposition approach to colored traveling salesman problems

Jun Li, Xing Dai, Huaxuan Liu, Mengchu Zhou

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

3 Scopus citations

Abstract

As a well-known combinatorial optimization problem, multiple traveling salesman problem (MTSP) fails to characterize some application problems where cities may have different accessibility for some but not necessarily all salesmen. This work proposes a colored traveling salesman problem (CTSP) in which a city has one to multiple colors allowing any salesman with the same color to visit. It presents a decomposition approach that converts CTSP into a combination of several individual traveling salesman problems (TSPs) and one MTSP for an important class of CTSP. To solve the transformed one, this work proposes a modified greedy algorithm allowing multi-colored city assignment during city search and adopts the formerly presented simulated annealing genetic algorithm. A dual-bridge waterjet cutting example is utilized to compare the presented decomposition approach and direct one. The results show that the former can achieve a better solution than the latter if the cities of same color(s) are clumped.

Original languageEnglish (US)
Title of host publication2015 IEEE Conference on Automation Science and Engineering
Subtitle of host publicationAutomation for a Sustainable Future, CASE 2015
PublisherIEEE Computer Society
Pages51-56
Number of pages6
ISBN (Electronic)9781467381833
DOIs
StatePublished - Oct 7 2015
Event11th IEEE International Conference on Automation Science and Engineering, CASE 2015 - Gothenburg, Sweden
Duration: Aug 24 2015Aug 28 2015

Publication series

NameIEEE International Conference on Automation Science and Engineering
Volume2015-October
ISSN (Print)2161-8070
ISSN (Electronic)2161-8089

Other

Other11th IEEE International Conference on Automation Science and Engineering, CASE 2015
CountrySweden
CityGothenburg
Period8/24/158/28/15

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Keywords

  • Genetic Algorithm
  • Greedy Algorithm
  • Modeling
  • Simulated Annealing Algorithm
  • Traveling Salesman Problem

Fingerprint Dive into the research topics of 'A decomposition approach to colored traveling salesman problems'. Together they form a unique fingerprint.

Cite this