Learn to create neighborhoods in real-world vehicle routing problem

We apply Reinforcement Learning to the destroy routine of a Large Neighborhood Search (LNS) Algorithm for a real-world last mile Pickup and Delivery Problem with Time Windows (PDPTW) with extra compatibility constraints. LNS iteratively improves a solution by destroying and repairing a part of the solution. Since the repair routine of LNS usually is expensive, it is crucial to destroy smartly. Our Reinforcement Learning (RL) model, which is an adaptation of the graph attention encoder-decoder model by Kool et al. [10], aims to create neighborhoods to destroy which yield a high improvement, ultimately speeding up the optimization algorithm. We implement our Smart Neighborhood Creation into two applications: a state-of-the-art application that is used to solve many daily logistic problems and an implementation of LNS for the classical Vehicle Routing Problem with Time Windows (VRPTW). We define three test phases, each with increasing difficulty to learn how to create good neighborhoods. In the first two phases of the first application, our RL model finds higher improvements (3–4 times) and more frequent improvements (8–25% more) than the state-of-the-art optimizer. In the last test phase, which represents the real-world optimization problem, our model needs around 9% fewer iterations to reach the same objective than the algorithm that uses a random neighborhood creation. These results are verified on the VRPTW instances.

• View at Publisher