A deep learning Attention model to solve the Vehicle Routing Problem and the Pick-up and Delivery Problem with Time Windows

SNCF, the French public train company, is experimenting with developing new transportation services by tackling vehicle routing problems. While many deep learning models have been used to tackle vehicle routing problems efficiently, it is challenging to consider time-related constraints. In this paper, we solve the Capacitated Vehicle Routing Problem with Time Windows (C-VRP-TW) and the Capacitated Pick-up and Delivery Problem with Time Windows (C-PDP-TW) with a constructive iterative Deep Learning algorithm. We use an Attention Encoder-Decoder structure and design a novel insertion heuristic for the feasibility check of the C-PDP-TW. Our model yields results that are better than the best-known learning solutions on the C-VRP-TW. We show the feasibility of deep learning techniques for solving the C-PDP-TW but witness the limitations of our iterative approach in terms of computational complexity and efficiency.