Designing Sparse Graphs for Stochastic Matching with an Application to Middle-Mile Transportation Management


Designing Sparse Graphs for Stochastic Matching with an Application to Middle-Mile Transportation Management

  • facebook
  • linkedin
  • twitter
  • whatsapp
Designing Sparse Graphs for Stochastic Matching

This talk is based on a research study partially supported by an Alibaba Cainiao research grant. We consider the problem of designing a sparse subgraph that supports a large matching after some nodes are randomly deleted. It is motivated by how to balance the trade-off between transportation costs and network complexity in the context of middle-mile delivery operations. We study three families of sparse graph designs (namely, Clusters, Rings, and Erdos-Renyi graphs) and show both theoretically and numerically that their performance is close to the optimal one achieved by a complete graph. We test our theoretical results using real data and conclude that adding a little flexibility to the routing network can significantly reduce transportation costs. This is joint work with Yifan Feng (National University of Singapore), René Caldentey (Chicago Booth), Yuan Zhong (Chicago Booth), Bing Wang (Alibaba Cainiao), and Haoyuan Hu (Alibaba Cainiao). 

About the Speaker 
Dr. Linwei Xin is an assistant professor of Operations Management at Booth School of Business, University of Chicago. His primary research is on inventory and supply chain management: designing models and algorithms for organizations to effectively "match supply to demand" in various contexts with uncertainty. His research on stochastic inventory theory by using asymptotic analysis has been recognized with several INFORMS paper competition awards, including the Applied Probability Society Best Publication Award (2019), First Place in the George E. Nicholson Student Paper Competition (2015), Second Place in the Junior Faculty Interest Group Paper Competition (2015), and a finalist in the Manufacturing and Service Operations Management Student Paper Competition (2014). His work with on dispatching algorithms for robots in intelligent warehouses was recognized as a finalist for the INFORMS 2021 Franz Edelman Award, with an estimate of billions of dollars in savings. His other honors include winning a National Science Foundation grant as a principal investigator. His research has been published in journals such as Operations Research, Management Science, Mathematics of Operations Research, and INFORMS Journal on Applied Analytics. He currently teaches MBA and PhD courses at the University of Chicago. 


Watch the webinar recording