A deep reinforcement learning algorithm for large-scale vehicle routing problems

Deep Reinforcement Learning (DRL) has been successful applied to a number of fields. In recent years, many scholars have used the DRL algorithms to solve a classic combinatorial optimization problem, i.e. Vehicle Routing Problem (VRP). The scale of the problems that are solved in the literatures is small, thus it is difficult to apply the algorithm into practice where there are many large-scale instances. To solve large-scale VRPs by using DRL, this paper proposes a pre-training mechanism for online shared networks. The graph pointer network under the multi-head attention mechanism is trained in the dual-network reinforcement learning mode. The trained model can be applied to large-scale VRP with 100/300/500 customers within a certain time. The experiments reveal that our algorithm can obtain good solutions in terms of solution quality and offline solution efficiency.