A Deep Reinforcement Learning Method for Solving the Multi-depot Vehicle Routing Problem

In this paper, a deep reinforcement learning optimization algorithm combined with the clustering decomposition strategy (DRLA_CD) is proposed for solving the multi-depot vehicle routing problem (MDVRP). First, taking into account the NP-hard and strong coupling characteristics of MDVRP, an improved
K-means algorithm (IKA) is designed to decompose MDVRP into several single-depot vehicle routing subproblems, thereby rationally reducing the search space and improving the search efficiency of the algorithm. Second, the deconstructed subproblems are solved using the deep reinforcement learning technique, and then the obtained solutions of subproblems are combined to form the whole solution of MDVRP. Finally, to confirm the efficacy of the proposed DRLA_CD, the comparative and simulation tests are carried out on instances with different scales.