Learning to Delegate for Large-scale Vehicle Routing

Wednesday, December 1, 2021 - 4:00pm to 4:30pm

Event Calendar Category

LIDS & Stats Tea

Speaker Name

Zhongxia (Zee) Yan

Affiliation

LIDS

Building and Room Number

LIDS Lounge

Vehicle routing problems (VRPs) have enjoyed ample applications in logistics and ride-hailing services around the world for decades. While determining the optimal solution to a VRP is NP-hard, powerful heuristic solvers such as LKH-3 and HGS find good solutions in practice for problems of size 1000 or less. Larger problems require decomposition strategies to solve efficiently.

More recently, machine learning methods inspired by the Pointer Network provide alternatives to traditional solvers: the learning-based methods greatly reduce computation time while maintaining decent solution quality on small problem instances (less than 100 cities). However, these methods remain difficult to scale, and few report results on problems of size more than 200.

Our work aims to address scalability by learning to identify smaller subproblems that can be readily solved by existing methods. Our learned subproblem selector guides the problem-solving process to focus local improvement on promising subregions. While there exists a combinatorial number of subproblems that can be selected at each step, we leverage spatial locality commonly found in combinatorial optimization problems to restrict the selection space size to be linear in the problem size. The greatly reduced search space enables us to feasibly train an attention-based subproblem selector.

Our framework combines the advantages of learning and heuristics: our network identifies promising subproblems to improve upon, dramatically speeding up solution times. Using a competitive subsolver on subproblems, we achieve good solution quality without the high computational costs of running the subsolver on large problem instances.

This is joint work with Sirui Li and Cathy Wu. The preprint of our article can be found at https://arxiv.org/pdf/2107.04139.pdf

Zhongxia "Zee" Yan is a fourth-year PhD student in MIT Department of Electrical Engineering and Computer Science (EECS), advised by Prof. Cathy Wu. He obtained his B.S. and M.S. in EECS from UC Berkeley in 2017 and 2018, respectively. Zee's research focuses on the application of machine learning and reinforcement learning approaches to problems involving sequential decision-making in transportation and logistics.