论文标题
图形指标中的电容车辆路由
Capacitated Vehicle Routing in Graphic Metrics
论文作者
论文摘要
我们研究图形指标中的电容车辆路由问题（图形CVRP）。我们的主要贡献是最佳解决方案成本的新下限。对于图形指标，该下限紧密且比一般指标众所周知的结合更强大。新的下限的证明是简单而组合的。使用此下限，我们分析了经典迭代游览算法的近似值，并结合了Christofides图形指标的TSP算法[1976]，Mömke-Svensson [Jacm 2016]和Sebinatorica [Combinatorica 2014]。特别是，我们获得了图形CVRP的1.95- approximation。
We study the capacitated vehicle routing problem in graphic metrics (graphic CVRP). Our main contribution is a new lower bound on the cost of an optimal solution. For graphic metrics, this lower bound is tight and significantly stronger than the well-known bound for general metrics. The proof of the new lower bound is simple and combinatorial. Using this lower bound, we analyze the approximation ratio of the classical iterated tour partitioning algorithm combined with the TSP algorithms for graphic metrics of Christofides [1976], of Mömke-Svensson [JACM 2016], and of Sebő-Vygen [Combinatorica 2014]. In particular, we obtain a 1.95-approximation for the graphic CVRP.
