论文标题
紧密的$（1.5+ε）$ - 在树上无法卸载的电容车辆路线的近似
A Tight $(1.5+ε)$-Approximation for Unsplittable Capacitated Vehicle Routing on Trees
论文作者
论文摘要
在树上无法命中的电容车辆路由问题（UCVRP）中，我们为我们提供了一个带有边缘的树和一个称为终端的树顶点的根树。每个终端都与0到1之间的积极需求相关联。目标是找到最小长度的旅行收集，以从树的根部开始和结束，以使每个终端的需求都被一次游览所覆盖（即无法分配需求），并且每个旅行中终端的总需求不超过1的能力。 对于所有终端都有相等需求的特殊情况，一长串的研究最终以准多项式时间近似方案[Jayaprakash和Salavatipour，Soda 2022]和多项式时间近似方案[Mathieu and Zhou and Zhou，ICALP 2022]。 在这项工作中，我们研究了终端有任意要求的一般情况。我们的主要贡献是树木上UCVRP的多项式时间$（1.5+ε）$ - 近似算法。这是30多年前对2-附属算法的第一个改进[Labbé，Laporte和Mercure，Operations Research，1991年]。我们的近似值本质上是最好的，因为NP近似于树木上的UCVRP比1.5因子更好。
In the unsplittable capacitated vehicle routing problem (UCVRP) on trees, we are given a rooted tree with edge weights and a subset of vertices of the tree 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 root of the tree 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. For the special case when all terminals have equal demands, a long line of research culminated in a quasi-polynomial time approximation scheme [Jayaprakash and Salavatipour, SODA 2022] and a polynomial time approximation scheme [Mathieu and Zhou, ICALP 2022]. In this work, we study the general case when the terminals have arbitrary demands. Our main contribution is a polynomial time $(1.5+ε)$-approximation algorithm for the UCVRP on trees. This is the first improvement upon the 2-approximation algorithm more than 30 years ago [Labbé, Laporte, and Mercure, Operations Research, 1991]. Our approximation ratio is essentially best possible, since it is NP-hard to approximate the UCVRP on trees to better than a 1.5 factor.
