文章基本信息

标题：A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs
本地全文：下载
作者：Amariah Becker ; Philip N. Klein ; David Saulpic 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：87
页码：12:1-12:15
DOI：10.4230/LIPIcs.ESA.2017.12
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Capacitated Vehicle Routing; Approximation Algorithms; Planar Graphs