Approximation algorithms for inventory problems with submodular or routing costs

• 成果类型: Article
• 署名作者: Nagarajan, Viswanath; Shi, Cong
• 署名单位: University of Michigan System; University of Michigan
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-0981-y
• 发表日期: 2016
• 页码: 225-244
• 关键词: joint replenishment problem; distribution-systems; allocation

摘要

We consider the following two deterministic inventory optimization problems with non-stationary demands. Submodular joint replenishment problem. This involves multiple item types and a single retailer who faces demands over a finite planning horizon of T periods. In each time period, any subset of item-types can be ordered incurring a joint ordering cost which is submodular. Moreover, items can be held in inventory while incurring a holding cost. The objective is to find a sequence of orders that satisfies all demands and minimizes the total ordering and holding costs. Inventory routing problem. This involves a single depot that stocks items, and multiple retailer locations facing demands over a finite planning horizon of T periods. In each time period, any subset of locations can be visited using a vehicle originating from the depot. There is also cost incurred for holding items at any retailer. The objective here is to satisfy all demands while minimizing the sum of routing and holding costs. We present a unified approach that yields -factor approximation algorithms for both problems when the holding costs are polynomial functions. A special case is the classic linear holding cost model, wherein this is the first sub-logarithmic approximation ratio for either problem.