A novel genetic algorithm for large scale colored balanced traveling salesman problem

摘要

The paper gives an applicable model called colored balanced traveling salesman problem (CBTSP), it is utilized to model optimization problems with partially overlapped workspace such as the scheduling and deploying of the resources and goods. CBTSP is NP-hard problem, the traditional nature-inspired algorithms, such as genetic algorithm (GA), hill-climbing GA and simulated annealing GA, are easy to fall into local optimum. In order to improve it, the paper proposes a novel genetic algorithm (NGA) based on ITO process to solve CBTSP. First of all, NGA utilizes the dual-chromosome coding to represent solution of this problem, and then updates the solution by the crossover and mutation operator. During the process of crossover operator, the length of crossover can be affected by activity intensity, which is directly proportional to environmental temperature and inversely proportional to particle radius. The experiments verify that NGA can demonstrate better solution quality than the compared algorithms for large scale CBTSP. (C) 2019 Elsevier B.V. All rights reserved.