Fast Approximation Algorithms for the One-Warehouse Multi-Retailer Problem Under General Cost Structures and Capacity Constraints

作     者：Gayon, Jean-Philippe Massonnet, Guillaume Rapine, Christophe Stauffer, Gautier 

作者机构：Univ Grenoble Alpes CNRS G SCOP F-38000 Grenoble France IMT Atlantique Lab LS2N F-44300 Nantes France Univ Lorraine Lab LGIPM F-57045 Metz 01 France 

出 版 物：《MATHEMATICS OF OPERATIONS RESEARCH》 (运筹学数学)

年 卷 期：2017年第42卷第3期

页      面：854-875页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：approximation algorithms combinatorial algorithm multi-echelon inventory problem lot sizing 

摘      要：We consider a well-studied multi-echelon (deterministic) inventory control problem, known in the literature as the one-warehouse multi-retailer (OWMR) problem. We propose a simple and fast 2-approximation algorithm for this NP-hard problem, by recombining the solutions of single-echelon relaxations at the warehouse and at the retailers. We then show that our approach remains valid under quite general assumptions on the cost structures and under capacity constraints at some retailers. In particular, we present the first approximation algorithms for the OWMR problem with nonlinear holding costs, truckload discount on procurement costs, or with capacity constraints at some retailers. In all cases, the procedure is purely combinatorial and can be implemented to run in low polynomial time.