License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.209
URN: urn:nbn:de:0030-drops-46985
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4698/
Go to the corresponding LIPIcs Volume Portal

Fukunaga, Takuro ; Nikzad, Afshin ; Ravi, R.

Deliver or hold: Approximation Algorithms for the Periodic Inventory Routing Problem

pdf-format:
15.pdf (0.4 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{fukunaga_et_al:LIPIcs:2014:4698,
  author =	{Takuro Fukunaga and Afshin Nikzad and R. Ravi},
  title =	{{Deliver or hold: Approximation Algorithms for the Periodic Inventory Routing Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{209--225},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4698},
  URN =		{urn:nbn:de:0030-drops-46985},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.209},
  annote =	{Keywords: Inventry Routing Problem, Approximation algorithm, Prize-collecting Steiner Tree}
}

Keywords: Inventry Routing Problem, Approximation algorithm, Prize-collecting Steiner Tree
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Issue Date: 2014
Date of publication: 04.09.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI