Order-Optimal Correlated Rounding for Fulfilling Multi-Item E-Commerce Orders

Will Ma ()
Additional contact information
Will Ma: Graduate School of Business, Columbia University, New York, New York 10027

Manufacturing & Service Operations Management, 2023, vol. 25, issue 4, 1324-1337

Abstract: Problem definition: We study the dynamic fulfillment problem in e-commerce, in which incoming (multi-item) customer orders must be immediately dispatched to (a combination of) fulfillment centers that have the required inventory. Methodology/results: A prevailing approach to this problem, pioneered by Jasin and Sinha in 2015 , has been to write a “deterministic” linear program that dictates, for each item in an incoming multi-item order from a particular region, how frequently it should be dispatched to each fulfillment center (FC). However, dispatching items in a way that satisfies these frequency constraints, without splitting the order across too many FCs, is challenging. Jasin and Sinha in 2015 identified this as a correlated rounding problem and proposed an intricate rounding scheme that they proved was suboptimal by a factor of at most ≈ q / 4 on a q -item order. This paper provides, to our knowledge, the first substantially improved scheme for this correlated rounding problem, which is suboptimal by a factor of at most 1 + ln ( q ) . We provide another scheme for sparse networks, which is suboptimal by a factor of at most d if each item is stored in at most d FCs. We show both of these guarantees to be tight in terms of the dependence on q or d . Our schemes are simple and fast, based on an intuitive idea; items wait for FCs to “open” at random times but observe them on “dilated” time scales. This also implies a new randomized rounding method for the classical Set Cover problem, which could be of general interest. Managerial implications: We numerically test our new rounding schemes under the same realistic setups as Jasin and Sinha and find that they improve runtimes, shorten code, and robustly improve performance. Our code is made publicly available online.

Keywords: inventory theory and control; math programming; retailing (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/msom.2023.1219 (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:ormsom:v:25:y:2023:i:4:p:1324-1337

Access Statistics for this article

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