IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v70y2024i12p8988-9013.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Yifan Feng & René Caldentey & Linwei Xin & Yuan Zhong & Bing Wang & Haoyuan Hu, 2024. "Designing Sparse Graphs for Stochastic Matching with an Application to Middle-Mile Transportation Management," Management Science, INFORMS, vol. 70(12), pages 8988-9013, December.
    • Handle: RePEc:inm:ormnsc:v:70:y:2024:i:12:p:8988-9013
    DOI: 10.1287/mnsc.2022.01588
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.2022.01588
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.2022.01588?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:70:y:2024:i:12:p:8988-9013. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.