Order-optimal correlated rounding for fulfilling multi-item e-commerce orders
Will Ma
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.History: This paper was selected for Fast Track in the M&SOM Journal from the 2022 MSOM Supply Chain Management SIG Conference.Funding: This research was partially funded by a grant from Amazon.com Inc., which was awarded through collaboration with the Columbia Center of AI Technology (CAIT).
Year of publication: |
2023
|
---|---|
Authors: | Ma, Will |
Published in: |
Manufacturing & service operations management : M & SOM. - Linthicum, Md. : Informs, ISSN 1526-5498, ZDB-ID 2023273-1. - Vol. 25.2023, 4, p. 1324-1337
|
Subject: | inventory theory and control | math programming | retailing | Electronic Commerce | E-commerce | Einzelhandel | Retail trade | Lagermanagement | Warehouse management | Lagerhaltungsmodell | Inventory model | Online-Handel | Online retailing |
Saved in:
Online Resource
Saved in favorites
Similar items by subject
-
Dynamic assortment customization with limited inventories
Bernstein, Fernando, (2015)
-
M-commerce, sales concentration, and inventory management
Jain, Nitish, (2022)
-
The impact of committing to customer orders in online retail
Figueira, Gonçalo, (2023)
- More ...
Similar items by person