A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs
A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs
复制标题
平面有界图上车辆路径的拟多项式时间逼近方案
DOI：
10.4230/lipics.esa.2017.12
复制
发表时间：
2017
影响因子：
3.7
通讯作者：
David Saulpic
中科院分区：
文献类型：
--
作者：
Amariah Becker;P. Klein;David Saulpic
有能力限制的车辆路径问题是旅行商问题的推广，其中一组客户必须由一组有能力限制的图尔斯访问。每次游览最多只能访问Q客户，并且必须在指定的仓库开始和结束。我们提出了非欧度量的能力约束车辆路径的第一近似方案。具体来说，我们给出了一个准多项式时间近似计划的能力限制车辆路径与固定的能力在平面图。我们还展示了如何将这一结果扩展到有界属图和多对数容量，以及包括多个仓库和未访问客户端的收费处罚的问题的变化。1998年ACM主题分类G.2.2图形算法
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. 1998 ACM Subject Classification G.2.2 Graph Algorithms