Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention
arXiv:2006.09100
Abstract
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.
References in corpus (6)
- Adam: A Method for Stochastic Optimization
- Learning Combinatorial Optimization Algorithms over Graphs
- Neural Combinatorial Optimization with Reinforcement Learning
- Attention, Learn to Solve Routing Problems!
- Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling Networks
- Learn to Design the Heuristics for Vehicle Routing Problem
Cited by in corpus (5)
- NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem
- Efficient Active Search for Combinatorial Optimization Problems
- Deep Reinforcement Learning for Demand Driven Services in Logistics and Transportation Systems: A Survey
- Joint Attention for Multi-Agent Coordination and Social Learning
- MODRL/D-EL: Multiobjective Deep Reinforcement Learning with Evolutionary Learning for Multiobjective Optimization