1129. Heuristics for the one-warehouse multi-retailer problem
Invited abstract in session MA-30: Lot-sizing models, stream Advanced Lot Sizing and Inventory Strategies .
Monday, 8:30-10:00Room: Maurice Keyworth 1.05
Authors (first author is the speaker)
| 1. | Matthieu Gruson
|
| Analytique, Opérations et Technologies de l'Information, Université du Québec à Montréal | |
| 2. | Félix Houdouin
|
| Ecole Polytechnique | |
| 3. | Marilène Cherkesly
|
| ESG UQAM |
Abstract
In this work, we address the One Warehouse Multi-Retailer (OWMR) problem. In the OWMR, a central warehouse replenishes multiple retailers that face a dynamic and deterministic demand for a single item over a discrete and finite time horizon. We design several simple yet efficient heuristics to solve the problem. The heuristics we designed are significantly faster than the best-known exact methods, with the most effective among them achieving feasible solutions that typically have costs less than 1% higher than the optimal solution, while being a hundred times faster. Our heuristics leverage the uncapacitated lot sizing and two-level uncapacitated lot sizing algorithms extensively. We introduce heuristics with low polynomial complexity, specifically O(NT^2 log(T)) and O(NT log(T)) where N and T denote the number of retailer and time periods, respectively. Additionally, we newly introduce a powerful process to improve any feasible solution in almost-linear time. While most of our heuristics do not have theoretical guarantees on their approximation ratios, we propose a dynamic method to estimate an approximation guarantee using a heuristic to compute a lower bound. This approach typically yields approximation guarantees around 1.4, which is tighter than the current best-known constant-approximation heuristic that has an approximation guarantee of 1.8.
Keywords
- Logistics
- Production and Inventory Systems
- Combinatorial Optimization
Status: accepted
Back to the list of papers