Premium
Two‐echelon distribution systems with random demands and storage constraints
Author(s) -
Federgruen Awi,
Guetta C. Daniel,
Iyengar Garud
Publication year - 2018
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.21825
Subject(s) - lagrange multiplier , upper and lower bounds , mathematical optimization , heuristic , computer science , dynamic programming , lagrangian relaxation , stock (firearms) , mathematics , operations research , mechanical engineering , mathematical analysis , engineering
We consider a general two‐echelon distribution system consisting of a depot and multiple sales outlets, henceforth referred to as retailers , which face random demands for a given item. The replenishment process consists of two stages: the depot procures the item from an outside supplier, while the retailers' inventories are replenished by shipments from the depot. Both of the replenishment stages are associated with a given facility‐specific leadtime. The depot as well as the retailers faces a limited inventory capacity. Inventories are reviewed and orders are placed on a periodic basis. When a retailer runs out of stock, unmet demand is backlogged. We propose a new approach to the above class of dynamic programming models based on Lagrangian relaxation. Every choice of the vector of Lagrange multipliers generates a lower bound via the solution of a single dynamic program (DP) with a one‐dimensional state‐space. The best such bound is obtained by maximizing over the vector of multipliers. The strategy that is optimal for this (maximal) lower bound DP employs an ( s , S ) ordering policy (generally, with time‐dependent policy parameters). To arrive at an upper bound and an implementable heuristic, this ( s , S ) policy is paired with one of several possible allocation policies that allocate the system‐wide inventory across the different facilities. We report on an extensive numerical study with close to 14 000 instances which evaluates the accuracy of the lower bound and the optimality gap of the various heuristic policies. The study reveals that the lower bound and the heuristic strategy that is constructed on its basis perform exceedingly well, almost across the entire parameter spectrum, including instances where demands are rather volatile or the average cycle time between consecutive orders is relatively large. The exception arises when storage at the depot is as expensive as at the retailer level and the retailers have large storage capacities.