Population-Based Incremental Learning Algorithm for a Serial Colored Traveling Salesman Problem

Xianghu Meng, Jun Li, Meng Chu Zhou, Xianzhong Dai, Jianping Dou

Research output: Contribution to journalArticlepeer-review

74 Scopus citations

Abstract

A colored traveling salesman problem (CTSP) is a generalization of the well-known multiple traveling salesman problem. This paper investigate a class of CTSP, called serial CTSP (S-CTSP). Each of its salesmen has his exclusive cities and shares some cities with its neighbor(s) in a serial manner. It can be used to model the scheduling problem of multimachine engineering systems with linearly arranged machines. S-CTSP is NP-hard. Developing effective and efficient approaches to S-CTSP is important to enable its industrial applications. This paper presents a population-based incremental learning (PBIL) approach to it. After analyzing its solution space, we set up some probability matrix models to guide the individual search of the algorithm. Then, a distance penalty is introduced into the state transfer function that can select the cities with small penalty values by the Roulette method to form a good route. By adding a powerful local search operation, 2-opt, to the algorithm, we can further enhance its search ability. Extensive simulation is conducted and its results show that the augmented PBIL is effective and well outperforms the genetic algorithms and CPLEX.

Original languageEnglish (US)
Article number7534819
Pages (from-to)277-288
Number of pages12
JournalIEEE Transactions on Systems, Man, and Cybernetics: Systems
Volume48
Issue number2
DOIs
StatePublished - Feb 2018

All Science Journal Classification (ASJC) codes

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

Keywords

  • Colored traveling salesman problem (CTSP)
  • combinatorial optimization
  • computational complexity
  • genetic algorithm (GA)
  • modeling
  • multiple traveling salesman problem (MTSP)
  • population-based incremental learning (PBIL)

Fingerprint

Dive into the research topics of 'Population-Based Incremental Learning Algorithm for a Serial Colored Traveling Salesman Problem'. Together they form a unique fingerprint.

Cite this