Deep Reinforcement Learning for Solving Two-Echelon Capacity Vehicle Routing Problem: An End-to-End Method

Abstract

Two-echelon distribution networks significantly enhance the delivery speed and reduce the distribution cost. Recent years have seen a growing trend in applying the reinforcement learning method to deal with combinatorial optimization problems such as the Vehicle Routing Problem (VRP). The advantage of Deep Reinforcement Learning (DRL) in this context lies in the fast solving of instances under the same distribution via the trained models. To the best of our knowledge, no prior research has applied the DRL to tackle the Two-Echelon Capacitated Vehicle Routing Problem (2E-CVRP). This paper, for the first time, models 2E-CVRP as a Markov Decision Process (MDP) and proposes an end-to-end DRL approach to handle it. Experimental results show that our proposed DRL-2E-CVRP method can rapidly solve unseen instances from the same distribution and improve the solution quality through transfer learning. It is observed that the solution speed surpasses that of commercial solvers, and the solution accuracy matches or even exceeds them within a limited time span. In addition, our method also demonstrates strong performance on benchmarks with unknown distributions.