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

Given an input graph [Formula: see text], we consider the problem of designing a sparse subgraph [Formula: see text] with [Formula: see text] that supports a large matching after some nodes in V are randomly deleted. We study four families of sparse graph designs (namely, clusters, rings, chains, 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 paper was accepted by David Simchi-Levi, optimization. Funding: This work was supported by the University of Chicago Booth School of Business, an Alibaba Cainiao Research Grant, and the Singapore Ministry of Education [NUS Startup Grant WBS A-0003856-00-00]. Supplemental Material: Data and the online appendix are available at https://doi.org/10.1287/mnsc.2022.01588 .