ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2018, Vol. 55 ›› Issue (11): 2372-2385.doi: 10.7544/issn1000-1239.2018.20180009

Previous Articles     Next Articles

Hybrid Algorithm for Colored Bottleneck Traveling Salesman Problem

Dong Xueshi, Dong Wenyong, Cai Yongle   

  1. (武汉大学计算机学院 武汉 430072) (dxs_cs@163.com)
  • Online:2018-11-01

Abstract: Based on colored traveling salesman problem (CTSP), this paper gives a more widely applicable combination optimization problem (COP) model named colored bottleneck traveling salesman problem (CBTSP), which can be used to model the planning problems with the partially overlapped workspace such as the route planning of persons and vehicles with cooperative and independent tasks. The objective function of these problems is different from the one of traveling salesman problems (TSPs), therefore it can’t be modeled by CTSP. Since CBTSP is NP-hard problem, for this kind of large scale problem, nature-inspired algorithms are good choice for solving it. Based on these, the paper proposes a nature-inspired algorithm to solve CBTSP, and the new algorithm named PSGA is a hybrid algorithm of particle swarm optimization (PSO), simulated annealing (SA) and genetic algorithm (GA) based on IT process. PSGA firstly uses dual-chromosome coding to generate solution of CBTSP, and then updates the solution by using the crossover operator of GA. During this process, the length of crossover is controlled by the activity intensity, which is affected by the particle radius and environment temperature. In order to test the effectiveness of PSGA algorithm, the paper makes experiments by using small scale to large scale CBTSP data, and the extensive experiments show that PSGA can demonstrate better solution quality than the compared algorithms.

Key words: hybrid algorithm, genetic algorithms (GA), colored bottleneck traveling salesman problem (CBTSP), colored traveling salesman problem (CTSP), bottleneck traveling salesman problem

CLC Number: