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

Yifan Feng (), René Caldentey (), Linwei Xin (), Yuan Zhong (), Bing Wang () and Haoyuan Hu ()
Additional contact information
Yifan Feng: NUS Business School, National University of Singapore, Singapore 119245
René Caldentey: Booth School of Business, University of Chicago, Chicago, Illinois 60637
Linwei Xin: Booth School of Business, University of Chicago, Chicago, Illinois 60637
Yuan Zhong: Booth School of Business, University of Chicago, Chicago, Illinois 60637
Bing Wang: Zhejiang Cainiao Supply Chain Management Co., Ltd, Hangzhou 310000, China
Haoyuan Hu: Zhejiang Cainiao Supply Chain Management Co., Ltd, Hangzhou 310000, China

Management Science, 2024, vol. 70, issue 12, 8988-9013

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

Keywords: transportation; middle-mile; flexibility; stochastic matching; long chain; e-commerce (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.2022.01588 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:70:y:2024:i:12:p:8988-9013

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().