Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention
This addresses complex constraints in vehicle routing for logistics and transportation, representing an incremental improvement over prior machine learning methods.
The paper tackles the challenge of solving vehicle routing problems with time windows by developing a policy model that concurrently extends multiple routes using joint attention, outperforming the existing state-of-the-art constructive model and, for two variants, a comparable meta-heuristic solver.
Many real-world vehicle routing problems involve rich sets of constraints with respect to the capacities of the vehicles, time windows for customers etc. While in recent years first machine learning models have been developed to solve basic vehicle routing problems faster than optimization heuristics, complex constraints rarely are taken into consideration. Due to their general procedure to construct solutions sequentially route by route, these methods generalize unfavorably to such problems. In this paper, we develop a policy model that is able to start and extend multiple routes concurrently by using attention on the joint action space of several tours. In that way the model is able to select routes and customers and thus learns to make difficult trade-offs between routes. In comprehensive experiments on three variants of the vehicle routing problem with time windows we show that our model called JAMPR works well for different problem sizes and outperforms the existing state-of-the-art constructive model. For two of the three variants it also creates significantly better solutions than a comparable meta-heuristic solver.