Title: Designing sparse graphs for stochastic matching, with an application to middle-mile transportation management
Abstract: Given an input graph G, we consider the problem of designing a sparse subgraph that supports a large matching after some nodes in G are randomly deleted. We study three families of sparse graph designs (namely, Clusters, Rings, and Erdős-Rényi graphs) and show both theoretically and numerically that their performance is close to the optimal one achieved by a complete graph. Our interest in the stochastic sparse graph design problem is primarily motivated by a collaboration with a leading e-commerce retailer in the context of its middle-mile delivery operations. We test our theoretical results using real data from our industry partner and conclude that adding a little flexibility to the routing network can significantly reduce transportation costs.
This is joint work with Yifan Feng, René Caldentey, Linwei Xin, Bing Wang and Haoyuan Hu.
Bio: Yuan Zhong is an associate professor of operations management at University of Chicago, Booth School of Business. His main research area is applied probability, focusing on the modeling and analysis of large-scale stochastic systems, with applications to cloud computing, manufacturing and e-commerce logistics. Prior to Booth, Yuan was an assistant professor at Columbia University in the Department of Industrial Engineering and Operations Research. Yuan received a PhD in operations research from MIT in 2012. He received the best student paper award at the ACM Sigmetrics conference in 2012.
