Heuristic ( S, T ) Solutions via an FPTAS for a One-Warehouse Multiretailer Problem

Waleed Najy (), Ali Diabat () and Khaled Elbassioni ()
Additional contact information
Waleed Najy: Division of Engineering, New York University Abu Dhabi, Saadiyat Island, Abu Dhabi 129188, United Arab Emirates
Ali Diabat: Department of Civil and Urban Engineering, Tandon School of Engineering, New York University, Brooklyn, New York 11201
Khaled Elbassioni: Computer Science Department, College of Computing and Mathematical Sciences, Abu Dhabi 127788, United Arab Emirates

Operations Research, 2025, vol. 73, issue 3, 1151-1164

Abstract: The difficulty of analyzing and optimizing the stochastic one-warehouse multiretailer problem under the ( S , T ) policy motivates the need to consider approximate but high-fidelity systems that are easier to scrutinize. We consider one such model in the setting in which retailers face independent normally distributed demand with given (nonidentical) means and variances. Safety stock is computed via a type-I service-level formula that ignores allocation issues, and the cost function is computed based on a power-of-two (POT) periodic ordering policy. A critical component of finding good solutions for this problem is solving the continuous relaxation of the optimization model involved. In doing so, the linking square root term introduced by the warehouse safety stock complicates this task as the cost does not decouple by individual retailers for a fixed warehouse replenishment interval. We alleviate this issue by substituting the linking term with an accurate piecewise linear estimator. We show how this helps us design a fully polynomial-time approximation scheme for the problem. From this, we can obtain a POT policy that has a guarantee of 1.061 ( 1 + ϵ ) for small ϵ and for any base planning period and 1.021 ( 1 + ϵ ) when the base planning period is optimally chosen, which is essentially the best possible guarantee up to the deterministic result. We show via an empirical study that the algorithm proposed returns heuristic ( S , T ) solutions that exhibit minimal suboptimality relative to the exact solution. Further, the time needed to compute these solutions is milliseconds for a handful of retailers (in contrast to the multiple hours required by the best existing methods) and just a few minutes for a system of one million retailers.

Keywords: Operations and Supply Chains; multiechelon; stochastic demand; piecewise linearization; approximation algorithms; inventory/production (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2024.1177 (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:oropre:v:73:y:2025:i:3:p:1151-1164

Access Statistics for this article

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