Hybrid Algorithm for Colored Bottleneck Traveling Salesman Problem

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.