论文标题
欧几里得电容车辆路由：A $（2+ε）$ - 近似算法
Unsplittable Euclidean Capacitated Vehicle Routing: A $(2+ε)$-Approximation Algorithm
论文作者
论文摘要
在无法实现的电容车辆路由问题中，我们为我们提供了一个称为仓库的顶点和一组称为终端的顶点的度量空间。每个终端都与0到1之间的积极需求相关联。目标是找到最小长度的旅行时间，从仓库开始和结束，以使每个终端的需求都被一次旅行所覆盖（即无法分配需求），并且每个终端在每个旅行中的总需求不超过1。 我们的主要结果是在二维欧几里得平面中为此问题的多项式$（2+ε）$ - 近似算法，即，对于特殊情况，终端和depot与欧几里得平面中的点相关联及其距离及其距离中的点相关。这改善了Blauth，Traub和Vygen [IPCO'21]和Friggstad，Mousavi，Rahgoshay和Salavatipour [IPCO'22]的最新工作。
In the unsplittable capacitated vehicle routing problem, we are given a metric space with a vertex called depot and a set of vertices called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal is to find a minimum length collection of tours starting and ending at the depot such that the demand of each terminal is covered by a single tour (i.e., the demand cannot be split), and the total demand of the terminals in each tour does not exceed the capacity of 1. Our main result is a polynomial-time $(2+ε)$-approximation algorithm for this problem in the two-dimensional Euclidean plane, i.e., for the special case where the terminals and the depot are associated with points in the Euclidean plane and their distances are defined accordingly. This improves on recent work by Blauth, Traub, and Vygen [IPCO'21] and Friggstad, Mousavi, Rahgoshay, and Salavatipour [IPCO'22].
