LIDS & Stats Tea Talk | Zhongxia (Zee) Yan (LIDS)

Wednesday, December 1
4pm

LIDS Lounge

Note: In accordance with MIT’s COVID policies, we are required to collect contact information from those who attend this event. If you are an MIT Covid Pass holder, please bring your smart phone and be prepared to present your MIT ID Barcode, which can be found in the MIT Atlas app.
********************************************
Speaker: Zhongxia (Zee) Yan
MIT Affiliation: LIDS
Talk Title: Learning to Delegate for Large-scale Vehicle Routing
Date: Wednesday, December 1, 2021
Time: 4:00 PM
Location: LIDS Lounge
Host: Yunzong Xu

Abstract: 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

Bio: 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.

********************************************

ABOUT: Tea talks are 20-minute-long informal chalk-talks for the purpose of sharing ideas and making others aware about some of the topics that may be of interest to the LIDS and Statsaudience. If you are interested in presenting in the upcoming tea talks, please email lids_stats_tea@mit.edu.

Information on future talks: https://lids.mit.edu/news-and-events/lids-stats-tea.

Details

  • Date: Wednesday, December 1
  • Time: 4pm
  • Category:
  • Location: LIDS Lounge