文章基本信息

标题：Deliver or hold: Approximation Algorithms for the Periodic Inventory Routing Problem
本地全文：下载
作者：Takuro Fukunaga ; Afshin Nikzad ; R. Ravi 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：28
页码：209-225
DOI：10.4230/LIPIcs.APPROX-RANDOM.2014.209
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The inventory routing problem involves trading off inventory holding costs at client locations with vehicle routing costs to deliver frequently from a single central depot to meet deterministic client demands over a finite planing horizon. In this paper, we consider periodic solutions that visit clients in one of several specified frequencies, and focus on the case when the frequencies of visiting nodes are nested. We give the first constant-factor approximation algorithms for designing optimum nested periodic schedules for the problem with no limit on vehicle capacities by simple reductions to prize-collecting network design problems. For instance, we present a 2.55-approximation algorithm for the minimum-cost nested periodic schedule where the vehicle routes are modeled as minimum Steiner trees. We also show a general reduction from the capacitated problem where all vehicles have the same capacity to the uncapacitated version with a slight loss in performance. This reduction gives a 4.55-approximation for the capacitated problem. In addition, we prove several structural results relating the values of optimal policies of various types.
关键词：Inventry Routing Problem; Approximation algorithm; Prize-collecting Steiner Tree