IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v73y2025i3p1151-1164.html
   My bibliography  Save this article

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

Author

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

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.

Suggested Citation

  • Waleed Najy & Ali Diabat & Khaled Elbassioni, 2025. "Heuristic ( S , T ) Solutions via an FPTAS for a One-Warehouse Multiretailer Problem," Operations Research, INFORMS, vol. 73(3), pages 1151-1164, May.
  • Handle: RePEc:inm:oropre:v:73:y:2025:i:3:p:1151-1164
    DOI: 10.1287/opre.2024.1177
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2024.1177
    Download Restriction: no

    File URL: https://libkey.io/10.1287/opre.2024.1177?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:oropre:v:73:y:2025:i:3:p:1151-1164. 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.