.png){kind=icon}
.png){kind=icon}
Return
Population-Based Incremental Learning Algorithm for a Serial Colored Traveling Salesman Problem
.png){kind=icon}
PRE
AI
DOI：10.1109/TSMC.2016.2591267.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Colored traveling salesman problem (CTSP)
combinatorial optimization
computational complexity
genetic algorithm (GA)
modeling
multiple traveling salesman problem (MTSP)
population-based incremental learning (PBIL)
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
10.5
Papers:
1.1W
Citations:
5.0W