Timezone: »

Learning to delegate for large-scale vehicle routing
Sirui Li · Zhongxia Yan · Cathy Wu

Vehicle routing problems (VRPs) form a class of combinatorial problems with wide practical applications. While previous heuristic or learning-based works achieve decent solutions on small problem instances, their performance deteriorates in large problems. This article presents a novel learning-augmented local search framework to solve large-scale VRP. The method iteratively improves the solution by identifying appropriate subproblems and $delegating$ their improvement to a black box subsolver. At each step, we leverage spatial locality to consider only a linear number of subproblems, rather than exponential. We frame subproblem selection as regression and train a Transformer on a generated training set of problem instances. Our method accelerates state-of-the-art VRP solvers by 10x to 100x while achieving competitive solution qualities for VRPs with sizes ranging from 500 to 3000. Learned subproblem selection offers a 1.5x to 2x speedup over heuristic or random selection. Our results generalize to a variety of VRP distributions, variants, and solvers.

Author Information

Sirui Li (MIT)
Zhongxia Yan (MIT)
Cathy Wu (MIT)

Cathy Wu is an Assistant Professor at MIT in LIDS, CEE, and IDSS. She holds a PhD from UC Berkeley, and B.S. and M.Eng from MIT, all in EECS, and recently completed a Postdoc at Microsoft Research AI. She works at the intersection of machine learning, optimization, autonomy, and urban systems. Her work has been acknowledged by several awards, including the 2019 Microsoft Location Summit Hall of Fame, 2018 Milton Pikarsky Memorial Dissertation Award, the 2016 IEEE ITSC Best Paper Award, and fellowships from NSF, Berkeley Chancellor, NDSEG, and Dwight David Eisenhower.

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors