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 .