Hybrid genetic algorithm with variable neighborhood search for multi-scale multiple bottleneck traveling salesmen problem

摘要

The paper gives an optimization model named multiple bottleneck traveling salesmen problem (MBTSP), which can model the optimization problems where there are multiple salesmen and tasks. In intelligent transport systems and multiple tasks cooperation, some real-world problems can be modeled by MBTSP, the scale of constructed model usually tends to multiple scales, therefore it is significant to study multiple scales MBTSP and its solving algorithms. The relevant literatures have proved that genetic algorithm and its versions can show good performance for the variants of TSP, thus this paper proposes a novel hybrid genetic algorithm (VNSGA) with variable neighborhood search (VNS) for multi-scale MBTSP. For VNSGA, the feasible solutions are constructed by dual-chromosome coding, then they are updated by the crossover operator, mutation operator and variable neighborhood search. During this process, the VNS can be carried out by the deleting and reinserting operator of the cities for optimization. The experiments show that VNSGA can demonstrate better solution quality than the state-of-the-art algorithms for MBTSP problem.