2026-07-22T03:36:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4698 2024-03-06T10:35:15Z ddc:004 open_access

Deliver or hold: Approximation Algorithms for the Periodic Inventory Routing Problem Fukunaga, Takuro Nikzad, Afshin Ravi, R. Inventry Routing Problem Approximation algorithm Prize-collecting Steiner Tree 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Takuro Fukunaga and Afshin Nikzad and R. Ravi 2014 Is Part Of LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2014.209 urn:nbn:de:0030-drops-46985 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.209 eng https://creativecommons.org/licenses/by/3.0/legalcode