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.ESA.2017.12
URN: urn:nbn:de:0030-drops-78781
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7878/
Go to the corresponding LIPIcs Volume Portal

Becker, Amariah ; Klein, Philip N. ; Saulpic, David

A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs

pdf-format:
LIPIcs-ESA-2017-12.pdf (0.7 MB)

Abstract

The Capacitated Vehicle Routing problem is a generalization of the Traveling Salesman problem in which a set of clients must be visited by a collection of capacitated tours. Each tour can visit at most Q clients and must start and end at a specified depot. We present the first approximation scheme for Capacitated Vehicle Routing for non-Euclidean metrics. Specifically we give a quasi-polynomial-time approximation scheme for Capacitated Vehicle Routing with fixed capacities on planar graphs. We also show how this result can be extended to bounded-genus graphs and polylogarithmic capacities, as well as to variations of the problem that include multiple depots and charging penalties for unvisited clients.

BibTeX - Entry

@InProceedings{becker_et_al:LIPIcs:2017:7878,
  author =	{Amariah Becker and Philip N. Klein and David Saulpic},
  title =	{{A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7878},
  URN =		{urn:nbn:de:0030-drops-78781},
  doi =		{10.4230/LIPIcs.ESA.2017.12},
  annote =	{Keywords: Capacitated Vehicle Routing, Approximation Algorithms, Planar Graphs}
}

Keywords: Capacitated Vehicle Routing, Approximation Algorithms, Planar Graphs
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

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