An iterative deep reinforcement learning approach to solve vehicle routing problems

Abstract

Vehicle routing problems have been studied for more than 50 years, and their in- terest has never been higher. It is partly due to their significant economic impact. Decreasing the traveling time, certainly for big organizations, can save costs in the range of millions of dollars and increase their service quality. Moreover, the wide variety of real-world applications comes with very different objective functions and constraints that must be considered. Also, finding optimal or approximate so- lutions in a reasonable time is a challenge for this NP-hard problem. This paper proposes a framework using deep reinforcement learning that can ameliorate VRP instances based on already-found solutions. Most of the research in the literature that uses deep learning to solve VRPs, describes construction algorithms. We, on the other hand, propose an improvement algorithm. We propose a method that takes as input an already found solution of the VRP, then computes the state of each node and vehicle using attention layers. Afterward, a problem-type specific algorithm computes a newly found solution based upon those embeddings. The effectiveness of our framework is then proven with two VRPs, namely the CVRP and the CVRP with strict time windows. They are chosen because of their differ- ence. Because when assigning a node to a vehicle, the order of passage needs to be considered for the CVRP-TW while for the CVRP it doesn’t. They prove the ability of our framework to be applied on very different VRPs-types. Computational experiments show the effectiveness and efficiency of our framework compared to the other works that use deep learning to solve CVRPs. It also proves: the broad applicability of our framework, the ability to use deep learning to improve a so- lution based upon an already found solution, and the advantages of using deep reinforcement Learning to solve combinatorial problems.