A Self-adaptive Quantum Genetic Algorithm for Vehicle Routing and Scheduling
Yang Shaoliang · 2019
Vehicle Routing and Scheduling Problem (VRP) is an NP-hard problem. In this paper, an adaptive quantum genetic algorithm is proposed to solve the problem of vehicle routing and scheduling. The algorithm uses a binary encoding scheme. In the case of quantum variation using quantum rotation gate, the self-adaptive angular acceleration algorithm (SAAA) is proposed according to the difference of fitness value between the current individual and the optimal individual. On this basis, the strategy of probability-based random reverse rotation is adopted when evolution stagnates, and the evolutionary stagnate escape algorithm (ESEA) is proposed. The experimental results show that the proposed algorithm has some advantages in terms of convergence speed and the ability to find the optimal solution in vehicle routing and scheduling. Finally, according to the pre-set requirements for evolutionary efficiency, the evolutionary efficiency assessment algorithm (EEAA) is proposed, which allows evolution to terminate and output the current optimal solution when the threshold is exceeded.