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

• 成果类型: Article
• 署名作者: Feng, Yifan; Caldentey, Rene; Xin, Linwei; Zhong, Yuan; Wang, Bing; Hu, Haoyuan
• 署名单位: National University of Singapore; University of Chicago
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2022.01588
• 发表日期: 2025
• 关键词: Transportation; middle-mile; flexibility; stochastic matching; long chain; E-commerce

摘要

Given an input graph G(in) = (V, E-in), we consider the problem of designing a sparse subgraph G =(V, E) with E subset of E-in 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.os-Renyi 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.