利用配额树改进不可拆分容量约束车辆路径问题的近似比

· · 算法·理论

这篇论文在 UCVRP 上只能做到 (2+\ln 2+\varepsilon) 的近似比？玩得太差了。这个问题存在运行时间为 n^{O(1/\varepsilon)} 的确定性 (5/2+\varepsilon)-近似算法。我们进一步改进路线的选择：

通过为小客户冲突预留部分收益，将“大客户带小客户”的局部搜索与匹配、四集合打包和六集合打包结合，再用配额树构造局部搜索的候选路线，从而得到一般输入下的 (5/2+\varepsilon) 近似。

摘要

在不可拆分容量约束车辆路径问题（UCVRP）中，输入包含客户集合 V（共有 n 名客户）、归一化需求 d_v\in(0,1]、仓库 r、单位车辆容量，以及 V\cup\{r\} 上满足对称度量的旅行费用 c。我们要寻找总费用最小的路线集合，使每条路线从仓库出发并返回仓库，每名客户的全部需求由一条路线服务，且每条路线 R 满足单位容量限制 \sum_{v\in V(R)}d_v\le1，其中 V(R) 表示 R 服务的客户集合。这刻画了从共同仓库配送货物、且每名客户的订单须在一次行程中完成配送的场景。

UCVRP 包含度量旅行商问题（TSP）作为特例，因此是 NP-hard 的。容量限制还带来了装箱方面的困难：当所有客户位于仓库之外的同一位置时，最小化路线费用等价于最小化装箱问题（bin packing）中的箱子数量。因此，除非 P=NP，UCVRP 不存在近似比低于 3/2 的多项式时间算法 [12]。经典的 3.5-近似保证已被近期的若干结果改进；特别地，Zhao 和 Xiao [22] 最近得到了 (2+\ln2+\varepsilon)-近似。

本文对每个有理数 0<\varepsilon\le1/9 给出运行时间为 n^{O(1/\varepsilon)} 的确定性 (5/2+\varepsilon)-近似算法，适用于一般容量和任意正需求。算法使用局部搜索选择服务一名大需求客户和若干小需求客户的路线。通过对需求进行舍入并创建顶点副本，算法利用指定端点的配额树构造候选路线。我们将这些路线与匹配和集合打包得到的路线合并，并保持客户集合互不相交。我们通过划分由带权图拟阵奇偶问题算法构造的巡回来服务剩余客户。

1. 引言

在不可拆分容量约束车辆路径问题（UCVRP）中，输入包含仓库 r、客户集合 V（n=|V|），以及 V\cup\{r\} 上的对称度量 c。每名客户 v\in V 的需求为 d_v\in(0,1]，车辆容量归一化为 1。一个可行解是由若干条从 r 出发并返回 r 的路线组成的集合 \mathcal T。对每条路线 R，记 V(R) 为其服务的客户集合，c(R) 为其费用。集合 V(R)（R\in\mathcal T）必须构成 V 的一个划分，且每条路线 R\in\mathcal T 满足 \sum_{v\in V(R)}d_v\le1。每名客户的全部需求由其所属路线完整服务。目标是最小化 c(\mathcal T):=\sum_{R\in\mathcal T}c(R)，将最优值记为 \mathrm{opt}。这一模型描述从共同仓库出发的配送任务：车辆容量有限，每名客户的订单由一次行程完整配送。

容量约束车辆路径问题（CVRP）的研究可以追溯到 Dantzig 和 Ramser 在 1959 年关于车辆调度的工作 [7]。UCVRP 包含度量旅行商问题（TSP）作为特殊情形：当 \sum_{v\in V}d_v\le1 时，可以选择由一条巡回组成的最优解。因此，UCVRP 是 NP-hard 的，这推动了对其近似算法的研究。

经典方法称为巡回划分（tour partitioning）：先计算一条经过仓库和所有客户的 TSP 巡回 R_{\mathrm{TSP}}，再将客户顺序划分为总需求至多为 1 的连续集合。将每个集合的两端连接到仓库，即得到可行路线。Haimovich 和 Rinnooy Kan [13] 研究了这一方法，Altinkemer 和 Gavish [1] 将其推广到不等需求。令 \alpha 为计算 TSP 巡回所用算法的近似比。最短的此类巡回费用至多为 \mathrm{opt}：在仓库处连接最优解的路线，保留起点和终点处的仓库访问，以及对每名客户的首次访问，再用直接边连接相邻的保留顶点。由三角不等式，费用不会增加。因此，c(R_{\mathrm{TSP}})\le\alpha\mathrm{opt}。经典划分算法得到的路线总费用至多为 c(R_{\mathrm{TSP}})+2\mathrm{opt}\le(\alpha+2)\mathrm{opt}。采用 Christofides 算法 [6]，有 \alpha=3/2，从而得到 3.5-近似。

Blauth、Traub 和 Vygen [3] 利用经典分析接近紧界时实例所具有的结构，改进了这一保证。Friggstad、Mousavi、Rahgoshay 和 Salavatipour [11] 将匹配与改进的巡回划分过程结合，得到了 (\alpha+1.75)-近似。他们还通过舍入一个配置线性规划（configuration LP），先服务大需求客户，再划分经过剩余客户的巡回。这对每个固定的 \varepsilon>0 给出了 (\alpha+1+\ln2+\varepsilon)-近似。取 \alpha=3/2 和充分小的 \varepsilon，即可得到 3.194-近似。将他们的分析与 Blauth 等人的分析结合，还能获得进一步的常数改进。

最近，Ebert 和 Weismantel [9] 提出了 Average Greedy 算法，同时控制所选路线的费用及其对大需求客户的覆盖。将该算法与匹配和巡回划分结合，可得到 (\alpha+1.659)-近似，因此在对称度量下得到 3.159-近似。Zhao 和 Xiao [20] 结合了匹配、LP 舍入和巡回划分。他们修订后的分析基于需求离散化和近似比分析线性规划（factor-revealing LP），对于一般容量，分别给出了约 3.147 的期望近似比和约 3.148 的确定性近似比。

Zhao 和 Xiao [22] 利用带权图拟阵奇偶问题（weighted graphic matroid parity）给出了新的巡回构造。将这一构造与 Friggstad 等人的 LP 舍入 [11] 结合，可以得到 UCVRP 的 (2+\ln2+\varepsilon)-近似。我们使用他们的巡回构造，并给出一个使用配额树的局部搜索算法，再与匹配和集合打包结合，得到 5/2+\varepsilon 的近似保证。

对于若干受限度量，已有更强的保证。Friggstad、Grandoni 和 Mousavi [10] 为欧氏平面上的单位需求 CVRP 给出了近似比低于 2 的多项式时间算法，其中所有客户具有相同需求。对于不可拆分需求，Grandoni、Mathieu 和 Zhou [12] 为欧氏平面给出了 (2+\varepsilon)-近似，Mathieu 和 Zhou [16] 为树度量给出了 (3/2+\varepsilon)-近似。

我们为含 n 名客户的度量 UCVRP 给出一个确定性近似算法。

定理 1.1（主要结果）。 对每个有理数 0<\varepsilon\le1/9，算法 3.1 是度量 UCVRP 的确定性 (5/2+\varepsilon)-近似算法。其运行时间为

n^{O(1/\varepsilon)}. \tag{1.1}

备注 1.2。 补充保证整条边获得服务的论证后，我们的分析可扩展到需求不可拆分的单仓库无向容量约束弧路径问题（CARP），并得到相同的 (5/2+\varepsilon)-近似保证。本文不展开讨论这一扩展。

1.1. 相关工作

在单位需求 CVRP 中，所有客户的归一化需求均为 d_v=1/k，其中 k\ge1 为整数，因此每条路线至多服务 k 名客户。在可拆分 CVRP 中，一名客户的需求可以分配给多条路线。对于这两个变体，经典巡回划分都给出 (\alpha+1)-近似 [13, 3]。当 \alpha=3/2 时，Blauth、Traub 和 Vygen [3] 将这一保证改进为 5/2-1/3000。Zhao 和 Xiao [22] 的巡回构造为两个变体都给出了 2-近似。

对于欧氏距离，Das 和 Mathieu [8] 为任意固定维度下的单位需求 CVRP 给出了准多项式时间近似方案（QPTAS）。对每个固定的 \varepsilon>0，其算法在 n^{\operatorname{poly}(\log n)} 时间内得到 (1+\varepsilon)-近似。在欧氏平面上，Friggstad、Grandoni 和 Mousavi [10] 为单位需求 CVRP 给出了多项式时间的 (2-\tau)-近似，其中 \tau>10^{-5} 是一个绝对常数。对于欧氏平面上的 UCVRP，Grandoni、Mathieu 和 Zhou [12] 对每个固定的 \varepsilon>0 给出了多项式时间的 (2+\varepsilon)-近似。

在树度量中，距离由带权树上的路径长度给出。Mathieu 和 Zhou [15] 为任意容量的树上单位需求 CVRP 给出了多项式时间近似方案（PTAS）：对每个固定的 \varepsilon>0，算法在多项式时间内得到 (1+\varepsilon)-近似。对于不可拆分需求，Mathieu 和 Zhou [16] 得到了 (3/2+\varepsilon)-近似。在树上将 UCVRP 近似到低于 3/2 的因子是 NP-hard 的，因此除非 P=NP，这一保证在忽略 \varepsilon 后是紧的。

对于其他图度量，也已有近似方案。Becker、Klein 和 Schild [2] 在容量 k 固定时，为平面图度量中的单位需求 CVRP 给出了 PTAS。Jayaprakash 和 Salavatipour [14] 为容量不受限制的单位需求 CVRP 给出了 QPTAS，适用于具有有界树宽（treewidth）或公路维数（highway dimension）的图，以及具有有界倍增维数（doubling dimension）的度量。对于由连通无权无向图的最短路距离诱导的图度量（graphic metrics），当除仓库外的每个顶点都是客户时，Mömke 和 Zhou [17] 为单位需求 CVRP 得到了 1.95-近似。

在固定容量情形中，车辆容量 k 是固定的正整数，归一化之前的需求为正整数。对于 UCVRP，这意味着 d_v\in\{1/k,2/k,\ldots,1\}，所以每条可行路线 R 满足 |V(R)|\le k。因此，可以在 n^{O(k)} 时间内枚举所有可行路线。Zhao 和 Xiao [21] 研究了一般度量下的这一情形。使用 \alpha=3/2 时，他们为单位需求和可拆分 CVRP 得到 5/2-\Theta(1/\sqrt{k}) 的近似比，为 UCVRP 得到 5/2+\ln2-\Theta(1/\sqrt{k}) 的近似比。

多仓库 CVRP 允许存在多个仓库，并要求在解中为每条路线选择仓库。在固定目的地变体中，每条路线必须返回其出发仓库。对于一般度量下任意数量的仓库，Zhao 和 Xiao [19] 为单位需求和可拆分变体给出了 4-1/1500 的近似比，为不可拆分需求给出了 4-1/50000 的近似比。Zhao 和 Xiao [22] 将这些保证进一步改进为单位需求和可拆分 CVRP 的 10/3，以及不可拆分需求的 3.792。

1.2. 算法思路

考虑仓库为 r、客户集合为 V、需求为 d_v\in(0,1] 的度量 CVRP 实例。每条路线从 r 出发并返回 r，服务的总需求至多为 1。记 n=|V|，\mathrm{opt} 为最小路线总费用，V(R) 和 c(R) 分别为路线 R 的客户集合与费用。我们使用一个由客户到仓库的距离得到的下界。径向下界为 D:=2\sum_{v\in V}d_vc(r,v)\le\mathrm{opt}。

算法先选择一些客户互不相交的可行路线。对于剩余客户，算法将一条 TSP 巡回上的客户顺序划分成总需求至多为 1 的连续集合，再为每个集合添加从仓库出发和返回仓库的边，得到可行路线。我们使用 Zhao 和 Xiao [22] 的算法为所有客户计算这条巡回。对于最优解 \mathcal T^*，记 \rho(R)=\max_{v\in V(R)}c(r,v)。他们的构造满足

c(R_{\mathrm{TSP}})\le\sum_{R\in\mathcal T^*}\bigl(2c(R)-2\rho(R)\bigr).

对于巡回客户的一个子集 X，限制到 X 的巡回保留起点和终点处的仓库访问，并按原顺序保留 X 中的客户，再用直接边连接相邻的保留顶点。由三角不等式，其费用不会增加。选择路线后，我们将 R_{\mathrm{TSP}} 限制到尚未服务的客户。

Friggstad 等人的 \delta-tank 定理 [11] 在 \delta=3/28 时给出了任意客户集合 X 的费用界。先用 (r,v,r) 服务每名需求满足 d_v>1/2 的客户 v\in X，再将巡回限制到其余客户，并划分得到的客户顺序。这些操作的费用至多为 TSP 费用加上 p(X)，其中 p(X)=\sum_{v\in X}p_v，且

p_v=\min\left\{2c(r,v),\,\frac{56}{25}\left[d_v+(d_v-\tfrac3{28})_+\right]c(r,v)\right\}, \qquad (x)_+=\max\{x,0\}.

我们将 p_v 称为客户 v 的价格：它是在上述剩余客户服务费用界中分配给 v 的费用项。特别地，需求满足 d_v\le3/28 的客户，其价格为 p_v=(56/25)d_vc(r,v)。

对已选路线族 \mathcal R，记 V(\mathcal R) 为其服务的客户集合，c(\mathcal R) 为其总费用。对剩余客户应用引理 3.2，可得到总费用至多为 c(R_{\mathrm{TSP}})+c(\mathcal R)+p(V\setminus V(\mathcal R)) 的完整解。固定有理数 0<\varepsilon\le1/9。对每个 k\in\{4,6\}，我们构造路线族 \mathcal R_k，补全剩余客户的服务后，返回费用最小的解。为了得到 (5/2+\varepsilon)-近似，我们对 k=4 和 k=6 分别赋予权重 9/10 和 1/10，将 c(\mathcal R_k)+p(V\setminus V(\mathcal R_k)) 的加权平均界为 \sum_{R\in\mathcal T^*}(2\rho(R)+c(R)/2)+\varepsilon\mathrm{opt}。再加上巡回费用界，即得到所声称的保证。对于路线 R，s(R):=p(V(R))-c(R) 是用路线 R 服务 V(R)、从而不再在费用界中保留这些客户价格所获得的节省。恒等式 c(\mathcal R)+p(V\setminus V(\mathcal R))=p(V)-\sum_{R\in\mathcal R}s(R) 将路线选择转化为获得足够总节省的问题。

先看匹配与集合打包本身能做到什么。将 d_v\le3/28 的客户称为小客户，将 d_v>25/56 的客户称为大客户；记 V_{\mathrm{small}} 为小客户集合。需求满足 d_v>3/28 的客户称为非小客户。在非小客户上，最大权匹配选择总节省最大的可行客户对。对每个 k\in\{4,6\}，我们枚举由二至 k 名非小客户组成的可行集合，并为每个集合选择一条经过仓库和该集合的最便宜路线。每个集合的权重为其路线节省减去所有与它共享客户的匹配边的节省。Thiery 和 Ward 的带权集合打包算法 [18] 返回互不相交的集合：当 k=4 时，其总权重至少为最大可能权重的 10/23；当 k=6 时，至少为最大可能权重的 2/7。再保留与所有所选集合均不共享客户的匹配路线，即得到客户互不相交的路线族。

若最优路线 R 恰好包含一名非小客户 v，且 \Delta(R):=p(V(R))-2\rho(R)-c(R)/2>0，则称其为特殊路线。匹配与集合打包将“所选路线费用加上未服务客户价格”的加权平均界为 \sum_{R\in\mathcal T^*}(2\rho(R)+c(R)/2)，再加上每条特殊路线 R 对应的 \Delta(R)。这样的客户 v 满足 25/56<d_v<31/56 和 c(r,v)>0。我们用局部搜索寻找服务大客户与小客户的路线，以提供这些额外节省。

局部搜索对每名大客户 v 维护一条空路线，或者一条服务 v 和小客户集合 S_v 的路线 R_v。所有非空路线的客户集合互不相交。对每名没有非空存储路线的客户，令 R_v=S_v=\varnothing、c(R_v)=s(R_v)=0。替换 R_v 时，其他路线保持不变，因此新路线可以使用 S_v 中的客户和尚未分配的小客户。位于其他当前路线上的小客户不可用。例如，最优路线可能将小客户 u 和 v 放在一起服务，但当前局部搜索解将 u 分配给了另一名大客户 w。只要保留 R_w，就不能在替换 R_v 时使用 u。

为计入替换路线无法使用的小客户所造成的损失，我们将当前每条路线的节省分成两项。令 \lambda=676/1481。对于非空路线，局部搜索改善评分

\Phi(R_v)=s(R_v)-(1-\lambda)p(S_v)=p_v+\lambda p(S_v)-c(R_v), \qquad s(R_v)=\Phi(R_v)+(1-\lambda)p(S_v),

并令 \Phi(\varnothing)=0。算法终止时，特殊最优路线中大客户的存储评分将足以支付该特殊路线的超额，允许扣除不可用小客户造成的损失和近似误差。小客户价格的剩余比例 1-\lambda 也是实际节省的一部分，在求和后将足以支付不可用客户造成的总损失。

为 R_v 构造替换路线时，我们考虑每个值 \tau\in\{0\}\cup\{c(r,u):u\in V_{\mathrm{small}}\}，并使用满足 c(r,u)\ge\tau 的可用小客户 u。每名这样的客户都满足 p_u\ge(56/25)\tau d_u。为了以较小费用连接这些客户，我们使用 Chaudhuri 等人的指定端点配额树定理 [4]，其形式采用 Chekuri 等人 [5，定理 3.3] 的陈述。对于特殊最优路线上的两条 r–v 路径，分别删除不可用的小客户和满足 c(r,u)<\tau 的小客户，再用直接边连接相邻的剩余顶点。由三角不等式，路径费用不会增加。对于一棵包含 r 和 v 的树 T，将其唯一 r–v 路径之外的边加倍，沿一条欧拉迹从 r 走到 v。随后添加边 (v,r)，保留起点和终点处的仓库访问、对每名所选小客户的首次访问，以及欧拉迹终点处对 v 的访问，再用直接边连接相邻的保留顶点。由于树上的这条路径费用至少为 c(r,v)，所得路线费用至多为 2c(T)。

为了使顶点配额表达需求，我们将客户替换为位于其原位置的带标记副本。在满足 c(r,u)\ge\tau 且 d_u>\varepsilon/4 的可用小客户中，枚举每个与 v 的总需求至多为 1 的子集 B。每个这样的子集都包含少于 4/\varepsilon 名客户。第 4 节给出需求舍入和配额构造，并使用一次贪心扫描选择完整客户，使其总需求满足容量限制。对于一条比较路径 P，令 X 为其上满足 c(r,u)\ge\tau 的可用小客户。引理 4.1 保证，某条被测试的路线费用至多为 2(1+\varepsilon/4)c(P)，且服务的小客户总需求至少为 \sum_{u\in X}d_u-\varepsilon/4。算法测试每个枚举的值、集合和配额，并返回评分最大的路线。

现在令 R_v^* 为唯一非小客户是 v 的特殊最优路线，并定义 U_v=(V(R_v^*)\cap V_{\mathrm{small}})\cap\bigcup_{w\ne v}S_w。它恰好由替换 R_v 时该最优路线上的不可用小客户组成。引理 5.4 将 R_v^* 上小客户的总价格与距离不低于某个被测试阈值的小客户总需求联系起来，由此将需求恢复保证转化为下面使用的价格贡献。从 R_v^* 得到的两条比较路径总费用至多为 c(R_v^*)。令 R' 为替换子程序返回的路线。由于子程序测试了这个阈值，其评分至少为对两条路径所构造路线的平均评分；这些路线的平均费用至多为 (1+\varepsilon/4)c(R_v^*)。引理 5.5 给出

\Phi(R')\ge2\Delta(R_v^*)-\frac{\lambda}{2}p(U_v)-\frac{\varepsilon}{2}c(R_v^*).

这正是局部搜索所需的比较：扣除所列出的不可用客户损失和近似误差后，候选路线的评分足以支付特殊路线的超额。

局部搜索仅当 \Phi(R')>\Phi(R_v)+\varepsilon D/(4n) 时，才接受对 v 的替换路线 R'。引理 3.1 将被接受的更新次数界为 O(n/\varepsilon)。在一次完整扫描没有产生替换后，对于每条特殊最优路线 R_v^*，当前评分 \Phi(R_v) 满足引理 5.5 的下界，并多出至多 \varepsilon D/(4n) 的误差（引理 3.1）。每名客户至多出现在一个 U_v 中，因此不可用客户造成的总损失至多为 (\lambda/2)\sum_v p(S_v)。

局部搜索结束后，我们在非小客户上使用调整后的价格 p'_v=p_v-s(R_v) 进行匹配和集合打包。若一条新的打包路线使用了大客户 v，则删除其旧路线 R_v，并将 S_v 中的小客户加入最终通过 TSP 巡回划分服务的客户中。对于非空 R_v，恒等式 p'_v=c(R_v)-p(S_v) 解释了这一调整：删除 R_v 节省 c(R_v) 的费用，但会使剩余客户的费用界增加 p(S_v)。对每个 k\in\{4,6\}，令 \mathcal R_{\mathrm{pack},k} 为匹配和集合打包产生的路线。加入所有大客户 v 未被 \mathcal R_{\mathrm{pack},k} 服务的旧路线 R_v，将所得路线族记为 \mathcal R_k。

在加权打包界中，每条特殊最优路线的大客户所对应的价格减少量会被全额扣除，其他客户的价格减少量则至少有 338/805 被扣除（引理 5.3）。代入 p_v-p'_v=s(R_v)=\Phi(R_v)+(1-\lambda)p(S_v)。特殊最优路线上大客户的存储评分，在允许扣除不可用客户损失和近似误差后，足以支付这些路线的超额。所有存储评分均非负，小客户价格的剩余部分贡献至少为 (338/805)(1-\lambda)\sum_v p(S_v)=(\lambda/2)\sum_v p(S_v)，足以支付不可用客户造成的总损失。计入近似误差后，引理 5.7 给出了 \mathcal R_4 和 \mathcal R_6 所需的加权平均界。再加上 TSP 巡回费用，即得到所声称的 (5/2+\varepsilon)-近似。

枚举和配额树调用总共需要 n^{O(1/\varepsilon)} 时间。匹配和集合打包需要多项式时间，每次最终巡回划分由一个 O(n^2) 的动态规划完成。结合多项式时间的巡回构造，算法总运行时间为 n^{O(1/\varepsilon)}。

2. 预备知识

2.1. 问题与记号

定义 2.1（容量约束车辆路径问题）。 一个容量约束车辆路径问题（CVRP）实例 (V,r,c,d) 包含：

一个可行解是满足下列条件的巡回集合 \mathcal T：

路线费用 c(R) 为其边费用之和，重复经过的边按经过次数计入。目标是最小化 c(\mathcal T)=\sum_{R\in\mathcal T}c(R)。固定一个最优解 \mathcal T^*，记 \mathrm{opt}=c(\mathcal T^*)。

我们假设需求和距离都是有理数。用 R 表示路线，P 表示路径，T 表示树；c(P) 和 c(T) 分别表示其边费用之和。对 S\subseteq V，记 d(S)=\sum_{v\in S}d_v。对于非空路线 R，记 \rho(R)=\max_{v\in V(R)}c(r,v)。对于路线族 \mathcal R，记 V(\mathcal R)=\bigcup_{R\in\mathcal R}V(R) 和 c(\mathcal R)=\sum_{R\in\mathcal R}c(R)。如果没有客户同时属于其中的两条路线，就称该路线族互不相交。

在每条路线中途访问仓库的位置将其切开，并在所得全部路线中为每名客户仅保留一次访问。用直接边连接相邻的保留顶点，由三角不等式，这一操作保持可行性且不增加总费用。因此，我们假设每条参考路线恰好访问其每名客户一次，且途中不再访问仓库。

定义 2.2。 将 V_{\mathrm{big}}=\{v\in V:d_v>25/56\} 中的客户称为大客户，将 V_{\mathrm{small}}=\{v\in V:d_v\le3/28\} 中的客户称为小客户。需求满足 d_v>3/28 的客户称为非小客户。

对于可行路线 R 上的每名客户 v，R 中连接 r 和 v 的两个部分的费用均至少为 c(r,v)，因此 2c(r,v)\le c(R)。乘以 d_v，对路线上的客户求和，并利用 d(V(R))\le1，即可得到下面的第一行。再对 \mathcal T^* 求和，便得到径向下界 D：

\begin{aligned} 2\sum_{v\in V(R)}d_vc(r,v)&\le d(V(R))c(R)\le c(R),\\ D:=2\sum_{v\in V}d_vc(r,v)&\le\sum_{R\in\mathcal T^*}c(R)=\mathrm{opt}. \end{aligned} \tag{2.1}

我们使用 Zhao 和 Xiao 的巡回构造。其费用界使用每条参考路线上的最大仓库距离。

定理 2.3（Zhao 和 Xiao [22，引理 4、6、7]）。 存在一个确定性算法，在 O(n^7) 时间内为 V\cup\{r\} 构造 TSP 巡回 R_{\mathrm{TSP}}。对于每个由非空路线组成的可行解 \mathcal T，该巡回都满足

c(R_{\mathrm{TSP}})\le\sum_{R\in\mathcal T}\bigl(2c(R)-2\rho(R)\bigr). \tag{2.2}

在他们的构造中，引理 6 使用划分 \{V(R):R\in\mathcal T\} 构造一个奇偶基（parity basis），其权重至多为 (2.2) 中的和。引理 4 将奇偶基转化为巡回，费用不超过基的权重；引理 7 给出 O(n^7) 的运行时间。算法使用度量费用，参考解用于分析。

2.2. 巡回划分与价格

**定理 2.4（Friggstad 等人 [11]）。** 设 $X\subseteq V$，$R_{\mathrm{TSP}}$ 为 $X\cup\{r\}$ 上的一条 TSP 巡回，且 $0\le\delta\le1/2$。可以将其客户顺序划分为需求至多为 $1$ 的连续段。将每段的两端连接到仓库，得到的路线族 $\mathcal R$ 满足 $$ c(\mathcal R)\le c(R_{\mathrm{TSP}})+\frac{2}{1-\delta}\sum_{v\in X}\bigl[d_v+(d_v-\delta)_+\bigr]c(r,v). \tag{2.3} $$ 对于需求满足 $d_v\le1/2$ 的客户，我们使用定理 2.4 在 $\delta=3/28$ 时的费用项。对于 $d_v>1/2$ 的客户，单客户路线 $(r,v,r)$ 的费用不超过该费用项。因此，我们定义客户价格为 $$ p_v=\begin{cases} \dfrac{56}{25}d_vc(r,v),&d_v\le3/28,\\[2pt] \dfrac{112d_v-6}{25}c(r,v),&3/28<d_v\le1/2,\\[2pt] 2c(r,v),&d_v>1/2. \end{cases} \tag{2.4} $$ 对于任意客户价格向量 $p$，记 $p(S)=\sum_{v\in S}p_v$。(2.4) 中的系数均位于 $[0,2]$，因此 $0\le p_v\le2c(r,v)$。 引理 3.2 将这些价格与巡回划分结合：给定客户集合 $X$ 上的一条 TSP 巡回，它构造费用至多为 $c(R_{\mathrm{TSP}})+p(X)$ 的可行路线。 ### 2.3. 集合打包与配额树 在匹配和集合打包阶段，我们先通过最大权匹配选择非小客户的可行客户对。随后，对 $k\in\{4,6\}$，考虑由二至 $k$ 名非小客户组成的可行集合，并为每个集合选择最便宜的服务路线。选择这样的集合会删除所有与其共享客户的匹配路线。因此，该集合的权重需扣除这些匹配路线的节省；第 3.3 节给出具体公式。对于每个 $k$，我们将推论 2.6 应用于正权重集合。 **定理 2.5（Thiery 和 Ward [18，完整版本中的算法 2.1、定理 4.8 和附录 A.2]）。** 固定整数 $k\ge3$ 和参数 $t\in[0,1/2]$。设 $\mathcal F$ 是显式列出的有限集合族，每个集合的大小至多为 $k$，且具有非负有理权重。存在一个确定性算法，返回两两不交的子族，其总权重至少为 $\mathcal F$ 的所有两两不交子族中最大总权重的 $1/\rho_k(t)$，其中 $$ \rho_k(t)=\frac{k+1}{2}-\frac12\min\left\{\frac{1-t}{2-t},\,\left(k-\frac1{\sqrt{1-t}}\right)\left(1-\sqrt{1-t}\right)\right\}. $$ 对于固定的 $k$ 和 $t$，算法运行时间为 $O((|\mathcal F|+1)^{k^2(k-1)+k+5})$。 对于大小至多为 $4$ 或 $6$ 的集合，这给出了算法所需的保证。 **推论 2.6。** 给定一个显式列出的有限集合族 $\mathcal F$，其中每个集合的大小至多为 $k\in\{4,6\}$，且具有非负有理权重，存在一个确定性算法选择两两不交的子族。当 $k=4$ 时，其总权重至少为最大总权重的 $10/23$；当 $k=6$ 时，至少为最大总权重的 $2/7$。算法在 $k=4$ 时运行时间为 $O((|\mathcal F|+1)^{57})$，在 $k=6$ 时为 $O((|\mathcal F|+1)^{191})$。 证明见附录 A.1。 局部搜索需要经过一名大客户和一个小客户集合的路线。我们构造一棵包含仓库和该大客户的树。为控制树中所表示的需求，我们用带标记的顶点副本编码舍入后的客户需求，并对树的顶点数施加下界。随后，依据原始需求从树中表示的客户中选择满足容量限制的客户，再将树转化为路线。第 4 节给出这一构造。下面的定理用具有相同端点并满足相同顶点配额的路径费用来界定树的费用。 **定理 2.7（Chaudhuri 等人 [4]；Chekuri 等人 [5，定理 3.3]）。** 设 $G=(V,E)$ 为完全无向图，$N=|V|$，边费用非负且满足三角不等式。不同顶点之间的距离可以为零。固定两个不同顶点 $r,v\in V$、整数配额 $2\le k\le N$，以及 $0<\varepsilon\le1$。存在一个运行时间为 $N^{O(1/\varepsilon)}$ 的确定性算法，返回包含 $r$ 和 $v$ 且至少有 $k$ 个顶点的树 $T$。对于每条至少包含 $k$ 个顶点的 $r$–$v$ 路径 $P$，均有 $c(T)\le(1+\varepsilon)c(P)$。 这一陈述也适用于不同顶点之间距离为零的情形。如果与 $r$ 距离为零的顶点包含 $v$，且共有至少 $k$ 个顶点，就在这些顶点上返回一棵费用为零的树。否则，令 $a$ 为最小的正边费用，将不同顶点之间的每条边费用增加 $\varepsilon a/(4N)$；这一操作保持三角不等式。然后以误差参数 $\varepsilon/2$ 应用定理。每条参考路径都访问某个与 $r$ 距离为正的顶点，因此包含一条费用至少为 $a$ 的边。此外，它至多包含 $N-1$ 条边。因此，返回树在原费用下的费用至多为 $(1+\varepsilon/2)(1+\varepsilon/4)c(P)\le(1+\varepsilon)c(P)$。 ## 3. 算法 ### 3.1. 主算法 设 $R_{\mathrm{TSP}}$ 为定理 2.3 返回的 $V\cup\{r\}$ 上的巡回，$\mathcal R$ 为客户集合两两不交的可行部分路线族。将巡回限制在未服务客户上，再应用引理 3.2，所得总费用至多为 $c(R_{\mathrm{TSP}})+c(\mathcal R)+p(V\setminus V(\mathcal R))$。使用式 (2.4) 中的固定价格，将路线的节省定义为 $s(R)=p(V(R))-c(R)$。对每个 $k\in\{4,6\}$，我们构造一个部分路线族 $\mathcal R_k$，并记 $X_k=V\setminus V(\mathcal R_k)$。两个最终解中较小的费用，不超过 $c(R_{\mathrm{TSP}})$ 加上下式左侧的加权和。因此，只需证明 $$ \frac9{10}\bigl[c(\mathcal R_4)+p(X_4)\bigr] +\frac1{10}\bigl[c(\mathcal R_6)+p(X_6)\bigr] \le \sum_{R\in\mathcal T^*}\left[2\rho(R)+\frac12c(R)\right] +\varepsilon\mathrm{opt}. \tag{3.1} $$ 结合定理 2.3，即得总费用至多为 $(5/2+\varepsilon)\mathrm{opt}$。 对每个 $v\in V_{\mathrm{big}}$，局部搜索维护一条经过 $v$、其余客户均为小客户的可行路线 $R_v$，或维护空路线。记其小客户集合为 $S_v=V(R_v)\setminus\{v\}$。约定 $V(\varnothing)=\varnothing$、$c(\varnothing)=s(\varnothing)=0$；对 $v\notin V_{\mathrm{big}}$，令 $R_v=S_v=\varnothing$。局部搜索通过以下评分比较路线： $$ \Phi(R)=s(R)-(1-\lambda)p(V(R)\cap V_{\mathrm{small}}), \qquad \lambda=\frac{676}{1481}, \qquad \Phi(\varnothing)=0. \tag{3.2} $$ 因此，非空存储路线的评分为 $\Phi(R_v)=p_v+\lambda p(S_v)-c(R_v)$。 对于满足 $c(r,v)>0$ 的大客户 $v$，令 $A\subseteq V_{\mathrm{small}}$ 为未被其他当前路线服务的小客户集合。给定输入 $(v,A,\varepsilon)$，算法 4.1 返回一条服务 $v$ 及 $A$ 的某个子集的可行路线。第 4 节给出具体构造，引理 5.5 给出返回路线的评分下界，附录 A.6 分析运行时间。 引理 3.1 保证存储路线的客户集合两两不交、评分非负，且 $0\le s(R_v)\le p_v$。该引理还将接受的更新次数界为 $O(n/\varepsilon)$。局部搜索结束后，$R_v,S_v$ 表示最终存储的路线及客户集合；这些值在合并阶段保持固定，包括最终解中未保留的路线。匹配与集合打包使用调整后的价格 $p'_v=p_v-s(R_v)$，由该引理可得 $0\le p'_v\le p_v$。节省 $s$ 和评分 $\Phi$ 仍使用原始价格 $p$。 算法 3.1 给出全部操作。对于由二至六名非小客户组成的可行集合 $S$，令 $R_S$ 为恰好访问 $S$ 的最便宜路线。这也包括匹配中使用的双客户路线 $R_e$。第 3.3 节定义固定的集合打包权重，第 3.4 节给出最终巡回划分的递推式。 **算法 3.1：不可拆分 CVRP 的 $(5/2+\varepsilon)$-近似算法** **输入：** 实例 $(V,r,c,d)$，以及有理误差参数 $0<\varepsilon\le1/9$。 **输出：** 恰好服务每名客户一次的可行路线族，其总费用至多为 $(5/2+\varepsilon)\mathrm{opt}$。 1. 计算 $D=2\sum_{v\in V}d_vc(r,v)$。 2. 若 $|V|\le1$ 或 $D=0$，则为所有客户返回单客户路线，并终止算法。 3. 应用定理 2.3，得到 $V\cup\{r\}$ 上的巡回 $R_{\mathrm{TSP}}$。 4. 按式 (2.4) 计算固定价格 $p$。 5. 对每个 $v\in V$，若 $d_v>1/2$ 且 $c(r,v)>0$，则令 $R_v\gets(r,v,r)$；否则令 $R_v\gets\varnothing$。 6. 对每个 $v\in V$，令 $S_v\gets\varnothing$。 7. 运行局部搜索，重复以下一轮扫描，直到该轮结束时 $\mathrm{changed}=\mathrm{false}$： 1. 令 $\mathrm{changed}\gets\mathrm{false}$。 2. 按固定顺序，依次考虑满足 $c(r,v)>0$ 的 $v\in V_{\mathrm{big}}$： 1. 令 $A\gets V_{\mathrm{small}}\setminus\bigcup_{u\ne v}S_u$。 2. 对输入 $(v,A,\varepsilon)$ 运行算法 4.1，令 $R'$ 为返回路线。 3. 若 $\Phi(R')>\Phi(R_v)+\varepsilon D/(4n)$，则令 $R_v\gets R'$、$S_v\gets V(R')\setminus\{v\}$、$\mathrm{changed}\gets\mathrm{true}$，并立即退出本轮扫描的整个客户循环。由于本轮接受了更新，随后重新开始一轮扫描。 8. 固定这些存储路线 $R_v$ 及客户集合 $S_v$，并对每个 $v\in V$ 令 $p'_v\gets p_v-s(R_v)$。 9. 在可行的非小客户对 $e$ 上，以正值 $p'(e)-c(R_e)$ 为边权，计算最大权匹配 $M$。 10. 枚举所有满足 $2\le|S|\le6$ 和 $d(S)\le1$ 的集合 $S\subseteq V\setminus V_{\mathrm{small}}$。通过枚举访问顺序计算 $R_S$，并用 $p'$ 按式 (3.3) 计算 $w(S)$。 11. 对每个 $k\in\{4,6\}$，执行以下操作： 1. 对满足 $|S|\le k$ 和 $w(S)>0$ 的集合应用推论 2.6，得到两两不交的集合族 $\mathcal S_k$。 2. 令 $$ \mathcal R_{\mathrm{pack},k}\gets \{R_S:S\in\mathcal S_k\} \cup \left\{R_e:e\in M,\ e\cap\bigcup_{S\in\mathcal S_k}S=\varnothing\right\}. $$ 3. 令 $$ \mathcal R_k\gets\mathcal R_{\mathrm{pack},k} \cup \{R_v:R_v\ne\varnothing,\ v\notin V(\mathcal R_{\mathrm{pack},k})\}. $$ 4. 令 $X_k\gets V\setminus V(\mathcal R_k)$，并令 $\mathcal T_k\gets\mathcal R_k$。 5. 若 $X_k\ne\varnothing$，则在 $R_{\mathrm{TSP}}$ 中保留 $X_k\cup\{r\}$ 的原有访问顺序，并直接连接相邻保留顶点，得到限制巡回。按式 (3.4) 计算费用最小的可行连续划分，回溯得到各条路线，并将它们加入 $\mathcal T_k$。 12. 返回 $\{\mathcal T_4,\mathcal T_6\}$ 中费用最小的路线族。 ### 3.2. 局部搜索 只有在 $n\ge2$ 且 $D>0$ 时，算法才进入这一阶段。测试 $R_v$ 的替换路线时，根据当前局部搜索状态定义可用集合 $A=V_{\mathrm{small}}\setminus\bigcup_{u\in V\setminus\{v\}}S_u$。它包含 $S_v$ 以及所有尚未分配的小客户。阈值 $\varepsilon D/(4n)$ 用于控制更新次数。 ![局部搜索：仅替换当前路线，释放、保留并加入相应小客户。](https://cdn.luogu.com.cn/upload/image_hosting/3978x22j.webp) 下面的引理保证存储路线始终可行、客户集合两两不交，并保证调整后的价格非负。它还给出更新次数上界，以及费用分析中使用的停止条件。 **引理 3.1。** 设 $n\ge2$、$D>0$ 且 $0<\varepsilon\le1/9$。算法 3.1 的局部搜索阶段满足以下性质。 （i）在每个阶段，非空路线 $R_v$ 均可行，且客户集合两两不交。每条路线服务其大客户 $v$ 及一个小客户集合 $S_v$。对每个 $v\in V$，都有 $\Phi(R_v)\ge0$ 和 $0\le s(R_v)\le p_v$。若 $d_v\le25/56$，则 $R_v$ 始终为空；若 $d_v>1/2$ 且 $c(r,v)>0$，则 $R_v$ 始终非空。 （ii）局部搜索在接受少于 $8n/\varepsilon$ 次更新后终止。考虑最后一轮未接受任何更新的完整扫描。对每个满足 $c(r,v)>0$ 的 $v\in V_{\mathrm{big}}$，令 $R'_v$ 为算法 4.1 返回的候选路线。其可用集合为根据最终存储路线计算的 $V_{\mathrm{small}}\setminus\bigcup_{u\ne v}S_u$，且 $$ \Phi(R'_v)\le\Phi(R_v)+\frac{\varepsilon D}{4n}. $$ 证明见附录 A.2。 ### 3.3. 匹配、集合打包与合并 局部搜索结束后，固定存储路线 $R_v$ 及其小客户集合 $S_v$，并对每个 $v\in V$ 令 $p'_v=p_v-s(R_v)$。由引理 3.1 和式 (2.4)，$0\le p'_v\le p_v\le2c(r,v)$。下面的匹配与集合打包使用价格 $p'$。第 5.1 节对任意满足 $0\le p'_v\le2c(r,v)$ 的输入价格分析这两个步骤。 在顶点集 $V\setminus V_{\mathrm{small}}$ 上，若 $e=\{u,v\}$ 满足 $d_u+d_v\le1$ 且 $p'(e)-c(R_e)>0$，则加入边 $e$，赋予它权重 $p'(e)-c(R_e)$，并计算最大权匹配 $M$。 枚举所有满足 $2\le|S|\le6$ 和 $d(S)\le1$ 的集合 $S\subseteq V\setminus V_{\mathrm{small}}$。定义 $w(S)$ 时，扣除所有客户集合与 $S$ 相交的匹配边的节省： $$ w(S)=p'(S)-c(R_S) -\sum_{\substack{e\in M\\e\cap S\ne\varnothing}} \bigl(p'(e)-c(R_e)\bigr). \tag{3.3} $$ 固定 $M$ 和这些权重，对每个 $k\in\{4,6\}$，向满足 $|S|\le k$ 和 $w(S)>0$ 的集合应用推论 2.6，得到两两不交的集合族 $\mathcal S_k$。当 $k=4$ 时，保证因子为 $10/23$；当 $k=6$ 时，保证因子为 $2/7$。令 $\mathcal R_{\mathrm{pack},k}$ 包含所有 $S\in\mathcal S_k$ 对应的路线 $R_S$，以及不与任何选中集合共享客户的匹配路线 $R_e$。 对每个 $k\in\{4,6\}$，从 $\mathcal R_{\mathrm{pack},k}$ 出发，再保留所有非空旧路线 $R_v$，其中大客户 $v$ 尚未被 $\mathcal R_{\mathrm{pack},k}$ 服务，得到合并后的路线族 $\mathcal R_k$。未服务集合 $X_k=V\setminus V(\mathcal R_k)$ 包含每条被删除旧路线上的小客户。第 3.4 节将服务 $X_k$ 中的所有客户。 $\mathcal R_{\mathrm{pack},k}$ 中的路线只包含非小客户，因此它与 $V(R_v)$ 只能在 $v$ 处相交。合并规则会删除每条发生这种相交的旧路线。因此，$\mathcal R_k$ 可行，且客户集合两两不交。 引理 5.6 证明这一合并步骤的费用恒等式，其中通过调整后的价格 $p'$ 计入被删除的旧路线。 ### 3.4. 巡回划分 对每个满足 $X_k\ne\varnothing$ 的 $k\in\{4,6\}$，将 $R_{\mathrm{TSP}}$ 限制在 $X_k\cup\{r\}$ 上，即按原顺序保留这些顶点并直接连接相邻保留顶点。记所得巡回顺序为 $(r,v_1,\ldots,v_\ell,r)$，其中 $\ell=|X_k|$。 令 $q[i]$ 为将 $v_1,\ldots,v_i$ 划分成连续可行路线的最小费用，且 $q[0]=0$。递推式为 $$ q[i]= \min_{\substack{0\le j<i\\\sum_{t=j+1}^{i}d_{v_t}\le1}} \left\{ q[j]+c(r,v_{j+1}) +\sum_{t=j+1}^{i-1}c(v_t,v_{t+1})+c(v_i,r) \right\}. \tag{3.4} $$ 为每个 $i$ 记录一个达到最小值的前驱，即可确定返回的路线。使用需求和边费用的前缀和，运行时间为 $O(\ell^2)$，空间为 $O(\ell)$。 ![巡回划分：删除蓝色虚线边，并添加连接仓库的红色边。](https://cdn.luogu.com.cn/upload/image_hosting/llcfw30a.webp) 下面的引理结合服务 $d_v>1/2$ 客户的单客户路线与巡回划分，得到由客户价格定义的一般费用界。断言 3.3 进一步说明，对算法 3.1 中的未服务集合 $X_k$，动态规划 (3.4) 可以直接达到这一费用界，无需单独构造单客户路线。 **引理 3.2。** 设 $\varnothing\ne X\subseteq V$，并给定 $X\cup\{r\}$ 上的 TSP 巡回 $R_{\mathrm{TSP}}$。可以在 $O(|X|^2)$ 时间和 $O(|X|)$ 额外空间内，计算一个恰好服务 $X$ 中每名客户一次的可行路线族，其总费用至多为 $c(R_{\mathrm{TSP}})+p(X)$。 **证明。** 对每个满足 $d_v>1/2$ 的客户 $v\in X$，用单客户路线 $(r,v,r)$ 服务它，费用为 $p_v$，并将巡回限制在其余客户上。由三角不等式，巡回费用不会增加。对剩余巡回应用定理 2.4，取 $\delta=3/28$。每名剩余客户的费用项为 $\frac{56}{25}[d_v+(d_v-3/28)_+]c(r,v)=p_v$。加上单客户路线的费用，便得到所需费用界。 对剩余客户顺序运行动态规划 (3.4)，得到最小费用的可行连续划分，因此其费用不超过定理所给划分的费用。使用前缀和，该动态规划需要 $O(|X|^2)$ 时间和 $O(|X|)$ 额外空间。证毕。 **断言 3.3。** 对每个 $k\in\{4,6\}$，若算法 3.1 合并后得到的 $X_k\ne\varnothing$，则在 $X_k\cup\{r\}$ 上的限制巡回上运行动态规划 (3.4)，所得可行路线的总费用至多为 $c(R_{\mathrm{TSP}})+p(X_k)$。 **证明。** 由引理 3.1 和合并规则，每个满足 $d_v>1/2$ 的未服务客户都有 $c(r,v)=0$。因此，定理 2.4 在 $\delta=3/28$ 时对每个 $v\in X_k$ 的费用项都等于 $p_v$。限制巡回的费用至多为 $c(R_{\mathrm{TSP}})$，故最小费用可行连续划分也满足所需费用界。证毕。 ## 4. 用配额树构造路线 ### 4.1. 路线构造 固定一名满足 $d_v>25/56$ 和 $c(r,v)>0$ 的客户 $v$、一个可用集合 $A\subseteq V_{\mathrm{small}}$，以及 $0<\varepsilon\le1/9$。枚举每个距离阈值 $\tau\in\{0\}\cup\{c(r,u):u\in V_{\mathrm{small}}\}$。对每个距离阈值，令 $A'=\{u\in A:c(r,u)\ge\tau\}$。对任意 $X\subseteq A'$，将客户价格求和可得 $p(X)\ge(56/25)\tau d(X)$，其中 $d(X)=\sum_{u\in X}d_u$。在引理 5.5 中，我们将这一不等式用于引理 4.1 给出的候选路线上的小客户，以得到候选路线的评分下界。 对每个距离阈值，枚举所有满足 $d_v+d(B)\le1$ 的集合 $B\subseteq\{u\in A':d_u>\varepsilon/4\}$。每个集合都满足 $|B|<4/\varepsilon$。对每个所选集合 $B$，路线必须服务 $B\cup\{v\}$ 中的所有客户。将满足 $d_u\le\varepsilon/4$ 的客户 $u\in A'$ 称为**可选客户**。下面的贪心扫描决定选择其中哪些客户。 对每名可选客户 $u$，令 $m_u=\lfloor4nd_u/\varepsilon\rfloor$，将 $d_u$ 向下舍入为 $\varepsilon m_u/(4n)$，并创建 $u$ 的 $m_u$ 个带标号副本。由于 $0\le d_u-\varepsilon m_u/(4n)<\varepsilon/(4n)$，且可选客户至多有 $n$ 名，总舍入损失至多为 $\varepsilon/4$。令 $m=\sum_{u\in A':\,d_u\le\varepsilon/4}m_u$。每名可选客户至多有 $n$ 个副本，因此 $m\le n^2$。 对 $B\cup\{v\}$ 中的每名客户创建 $m+3$ 个副本，并额外加入独立的端点标号 $r,v$。所有副本和端点标号都是完全图中不同的顶点。边长继承原实例中的距离，同一客户的副本之间距离为零。若树中含有属于某名客户的标号，就称该客户被这棵树表示。 对于每个 $k=0,\ldots,m$，要求树包含至少 $(|B|+1)(m+3)+2+k$ 个顶点，其中包括 $r$ 和 $v$。若树不含 $B\cup\{v\}$ 中某名客户的任何副本，它至多包含 $|B|(m+3)+m+2$ 个顶点，达不到配额。因此，树包含 $B\cup\{v\}$ 中每名客户的至少一个副本。这些客户的副本和两个端点标号至多提供 $(|B|+1)(m+3)+2$ 个顶点，所以树中至少有 $k$ 个顶点是可选客户的副本。 ![配额树构图：复制客户顶点，以顶点配额保证必选客户以及可选客户的副本数量。](https://cdn.luogu.com.cn/upload/image_hosting/bs3p873t.webp) 对每棵返回的树 $T$，按以下贪心规则选择客户。初始化 $S=B\cup\{v\}$。按固定顺序扫描每名至少有一个副本在 $T$ 中的可选客户 $u$，当且仅当 $d(S)+d_u\le1$ 时，将 $u$ 加入 $S$。若拒绝客户 $u$，则 $1-d(S)<d_u\le\varepsilon/4$。将 $T$ 中唯一的 $r$–$v$ 路径以外的每条边加倍，沿所得多重图的一条欧拉迹从 $r$ 走到 $v$，再接上边 $(v,r)$。这条 $r$–$v$ 路径的费用至少为 $c(r,v)$，因此只遍历它一次所节省的费用足以支付返回边。按照欧拉迹中首次访问每名客户的副本的顺序，将 $S\setminus\{v\}$ 中的客户记为 $u_1,\ldots,u_{|S|-1}$，并令 $R'=(r,u_1,\ldots,u_{|S|-1},v,r)$。 **算法 4.1：用配额树选择路线** **输入：** 满足 $d_v>25/56$ 和 $c(r,v)>0$ 的客户 $v$，集合 $A\subseteq V_{\mathrm{small}}$，以及 $0<\varepsilon\le1/9$。 **输出：** 一条服务 $v$ 及 $A$ 的某个子集的可行路线，在下面测试的路线中具有最大的评分 $\Phi$。 1. 令 $R_{\mathrm{best}}\gets(r,v,r)$。 2. 对每个距离阈值 $\tau\in\{0\}\cup\{c(r,u):u\in V_{\mathrm{small}}\}$，执行以下操作： 1. 令 $A'\gets\{u\in A:c(r,u)\ge\tau\}$。 2. 对每个满足 $d_u\le\varepsilon/4$ 的客户 $u\in A'$，令 $m_u\gets\lfloor4nd_u/\varepsilon\rfloor$，并令 $m$ 为这些 $m_u$ 的和。 3. 枚举每个满足 $d_v+d(B)\le1$ 的集合 $B\subseteq\{u\in A':d_u>\varepsilon/4\}$： 1. 使用原实例中的距离，构造完全图。图中包含每名可选客户的 $m_u$ 个副本、每名 $B\cup\{v\}$ 中客户的 $m+3$ 个副本，以及独立端点标号 $r,v$。 2. 对每个 $k=0,\ldots,m$，执行以下操作： 1. 应用定理 2.7，取端点 $r,v$、配额 $(|B|+1)(m+3)+2+k$ 和误差 $\varepsilon/4$，得到树 $T$。 2. 令 $S\gets B\cup\{v\}$。 3. 按固定顺序扫描被 $T$ 表示的每名可选客户 $u$。若 $d(S)+d_u\le1$，则令 $S\gets S\cup\{u\}$。 4. 将 $T$ 中唯一的 $r$–$v$ 路径以外的每条边加倍，沿一条欧拉迹从 $r$ 走到 $v$，再接上边 $(v,r)$。 5. 按照这条欧拉迹中首次访问每名客户的副本的顺序，将 $S\setminus\{v\}$ 中的客户记为 $u_1,\ldots,u_{|S|-1}$。 6. 令 $R'\gets(r,u_1,\ldots,u_{|S|-1},v,r)$。 7. 若 $\Phi(R')>\Phi(R_{\mathrm{best}})$，则令 $R_{\mathrm{best}}\gets R'$。 3. 全部距离阈值、集合和配额枚举结束后，返回 $R_{\mathrm{best}}$。 每个配额都可行：完全图中存在经过全部顶点的 $r$–$v$ 路径。算法 4.1 的一次调用需要 $n^{O(1/\varepsilon)}$ 时间。附录 A.6 估计枚举集合 $B$ 的数量，以及调用配额树算法的次数。 ### 4.2. 需求与费用界 下面的引理将一条测试的候选路线与一条参考 $r$–$v$ 路径比较，给出候选路线的费用上界和其中小客户的总需求下界。引理 5.5 使用这些界，为一条测试的候选路线给出评分保证。算法 4.1 返回的路线评分不低于该值。 **引理 4.1。** 固定算法 4.1 的输入 $(v,A,\varepsilon)$，以及距离阈值 $\tau\in\{0\}\cup\{c(r,u):u\in V_{\mathrm{small}}\}$。令 $A'=\{u\in A:c(r,u)\ge\tau\}$。对于每个满足 $d_v+d(X)\le1$ 的集合 $X\subseteq A'$，以及每条访问 $X$ 中所有客户的 $r$–$v$ 路径 $P$，算法都会测试一条服务 $v$ 及 $A'$ 的某个子集的可行路线 $R'$，满足 $$ c(R')\le2(1+\varepsilon/4)c(P), \qquad d(V(R')\setminus\{v\})\ge d(X)-\varepsilon/4. $$ 算法测试的每条路线都可行，并服务 $v$ 及 $A$ 的某个子集。 **证明。** 我们根据 $X$ 选择枚举集合和配额，使 $P$ 能够用于比较返回树的费用。为控制所选客户的总需求，考虑两种情况：贪心扫描接受树所表示的所有可选客户，或者一次拒绝说明剩余容量已经小于 $\varepsilon/4$。 固定满足引理条件的任意 $\tau,X,P$。对于这个距离阈值，考虑 $B=\{u\in X:d_u>\varepsilon/4\}$、$k=\sum_{u\in X\setminus B}m_u$ 对应的迭代。由于 $d_v+d(B)\le1$ 且 $0\le k\le m$，算法会枚举到这次迭代。 按 $P$ 中的原有顺序保留端点 $r,v$ 和 $X$ 中的客户，并直接连接相邻保留顶点。三角不等式保证费用不会增加。将 $X$ 中的每名客户替换为它的全部副本，略去没有副本的客户，并将 $v$ 的全部副本插入端点标号 $v$ 的紧前方。所得复制图中的路径恰好包含 $(|B|+1)(m+3)+2+k$ 个顶点，费用至多为 $c(P)$。因此，定理 2.7 返回的树 $T$ 满足 $c(T)\le(1+\varepsilon/4)c(P)$。令 $R'$ 为本次迭代中由 $T$ 构造的候选路线。 由第 4.1 节的计数论证，$T$ 包含 $B\cup\{v\}$ 中每名客户的至少一个副本，以及至少 $k$ 个可选客户副本。若可选客户 $u$ 在 $T$ 中有 $t$ 个副本，则 $t\le m_u\le4nd_u/\varepsilon$，所以 $d_u\ge\varepsilon t/(4n)$。对被 $T$ 表示的可选客户求和可知，它们的总需求至少为 $\varepsilon k/(4n)$。 若贪心扫描接受所有这些客户，则 $$ \begin{aligned} d(V(R')\setminus\{v\}) &\ge d(B)+\frac{\varepsilon k}{4n}\\ &=d(B)+\sum_{u\in X\setminus B} \frac{\varepsilon}{4n} \left\lfloor\frac{4nd_u}{\varepsilon}\right\rfloor\\ &\ge d(X)-\frac{\varepsilon|X\setminus B|}{4n} \ge d(X)-\frac{\varepsilon}{4}. \end{aligned} $$ 最后一行使用了 $\lfloor z\rfloor\ge z-1$ 和 $|X\setminus B|\le n$。 若某名可选客户 $u$ 被拒绝，则当时的剩余容量小于 $d_u\le\varepsilon/4$。在后续扫描中，剩余容量只会减少。因此，最终所选小客户的总需求满足 $d(V(R')\setminus\{v\})>1-d_v-\varepsilon/4\ge d(X)-\varepsilon/4$，其中最后一个不等式来自 $d_v+d(X)\le1$。这就证明了需求下界。 为控制路线费用，令 $P_T$ 为 $T$ 中唯一的 $r$–$v$ 路径。将 $P_T$ 以外的所有边加倍后，所得连通多重图只有 $r,v$ 两个奇度顶点，因此存在构造中使用的从 $r$ 到 $v$ 的欧拉迹。在这条欧拉迹后接上边 $(v,r)$，保留仓库的初末访问、沿欧拉迹首次访问 $S\setminus\{v\}$ 中每名客户的副本的位置，以及末端 $v$，再直接连接相邻保留顶点。由三角不等式， $$ c(R')\le2c(T)-c(P_T)+c(r,v) \le2c(T)\le2(1+\varepsilon/4)c(P), $$ 其中使用了 $c(P_T)\ge c(r,v)$。 每次迭代都从可行集合 $B\cup\{v\}$ 开始，且只在 $d(S)+d_u\le1$ 时加入客户 $u$。因此，对于固定的距离阈值，构造出的每条路线都可行，并服务 $v$ 及 $A'$ 的某个子集。由于每个距离阈值下都有 $A'\subseteq A$，所有测试的路线都服务 $v$ 及 $A$ 的某个子集。初始路线 $(r,v,r)$ 也满足这些性质。证毕。 ![从树构造路线：空心圆表示可选客户，贪心扫描选取 p，并因剩余容量不足而拒绝 q。](https://cdn.luogu.com.cn/upload/image_hosting/ijq72uf6.webp) ## 5. 费用分析 本节估计 $k\in\{4,6\}$ 对应的已选部分路线族的费用与未服务客户价格之和的加权平均，以证明式（3.1）。第 5.1 节先将匹配和集合打包得到的节省与一个可行参考解比较，并说明价格降低如何影响所得上界。第 5.2 节将这一比较用于最优路线，找出还需要额外节省的路线。第 5.3 节估计局部搜索中 配额树 候选路线的评分，以取得这些节省。最后，第 5.4 节利用局部搜索的最后一轮扫描估计存储路线的评分，再通过路线替换恒等式合并两部分节省，从而证明式（3.1）。 ### 5.1. 匹配与集合打包 回顾第 3.3 节中以 $p'$ 为输入价格的匹配与集合打包阶段。我们先在可行的 非小客户对上计算最大权匹配 $M$。固定 $M$ 后，为每个由 $2$ 至 $6$ 个 非小客户组成的可行集合 $S$ 赋予权重 $w(S)$：它等于该集合的路线节省减去所有与 $S$ 相交的匹配边的节省。对 $k\in\{4,6\}$，将推论 2.6 用于大小至多为 $k$ 的正权集合，得到互不相交的集合族 $\mathcal S_k$。路线族 $\mathcal R_{\mathrm{pack},k}$ 包含这些选中集合的路线，以及与所有选中集合都不共享客户的匹配路线。 我们使用 $a_4=9/10$ 和 $a_6=1/10$ 比较两个 $k$ 对应的输出。推论 2.6 给出的集合打包保证分别为 $k=4$ 时的 $b_4=10/23$ 和 $k=6$ 时的 $b_6=2/7$。算法对每个 $k$ 构造相应的路线族并服务剩余客户，再返回费用最小的输出。这里的目标是对满足 $0\le p'_v\le2c(r,v)$ 的输入价格，估计 $\sum_{k\in\{4,6\}}a_k[c(\mathcal R_{\mathrm{pack},k})+p'(V\setminus V(\mathcal R_{\mathrm{pack},k}))]$。 为进行比较，固定任意一个客户集合构成 $V$ 的划分的可行路线族 $\mathcal R_0$。匹配阶段使用客户对，因此我们将它与每条参考路线中选出的客户对比较。集合打包阶段使用至多 $4$ 或 $6$ 个客户的集合，因此我们将它与每条参考路线中选出的大小至多为 $k$ 的子集比较。这些子集满足容量约束，来自不同参考路线的子集也互不相交。 对 $R\in\mathcal R_0$ 和 $j\in\{2,4,6\}$，令 $S_j(R)$ 包含 $R$ 上需求最大的 $j$ 个 非小客户；若不足 $j$ 个，则包含全部 非小客户。需求相同时按一个固定顺序选择。对任意非负价格向量 $p'$，定义 $$ \begin{aligned} F(R;p')={}&p'(V(R)) -\frac{129}{805}\bigl(p'(S_2(R))-c(R)\bigr)_+\\ &-\frac9{23}\bigl(p'(S_4(R))-c(R)\bigr)_+ -\frac1{35}\bigl(p'(S_6(R))-c(R)\bigr)_+. \end{aligned} \tag{5.1} $$ $F(R;p')$ 中减去的各项表示对两个 $k$ 的输出进行加权比较时所保证的节省。每条匹配边至多与两个互不相交的参考集合相交，因此，对大小至多为 $k$ 的集合进行比较后，匹配项剩下的系数为 $1-2b_k$。式（5.1）中各项的系数来自 $a_4(1-2b_4)+a_6(1-2b_6)=129/805$、$a_4b_4=9/23$ 和 $a_6b_6=1/35$。 下面引理的（i）将这些节省转化为路线费用与未服务客户价格之和的上界。（ii）说明，在每条参考路线上，$F$ 的下降量至少为总价格下降量的 $338/805$。合并两个阶段时，我们将用它计入局部搜索带来的价格下降。 **引理 5.1。** 设 $\mathcal R_0$ 是一个可行路线族，其客户集合构成 $V$ 的划分，$F$ 由式（5.1）定义。 （i）对于每个 $v\in V$ 都满足 $0\le p'_v\le2c(r,v)$ 的输入价格 $p'$，令 $\mathcal R_{\mathrm{pack},k}$ 表示匹配与集合打包阶段对 $k\in\{4,6\}$ 返回的路线族。则 $$ \sum_{k\in\{4,6\}}a_k \left[c(\mathcal R_{\mathrm{pack},k}) +p'\bigl(V\setminus V(\mathcal R_{\mathrm{pack},k})\bigr)\right] \le \sum_{R\in\mathcal R_0}F(R;p'). $$ （ii）对任意非负价格向量 $p''\le p'$ 以及每条 $R\in\mathcal R_0$，有 $$ F(R;p')-F(R;p'') \ge \frac{338}{805} \bigl(p'(V(R))-p''(V(R))\bigr). $$ **证明。** 对（i），我们将匹配与 $S_2(R)$ 比较，分别将 $k=4,6$ 的集合打包与 $S_4(R)$、$S_6(R)$ 比较。每条匹配边至多与两个参考集合相交，这可以控制从集合权重中扣除的匹配节省。对（ii），我们估计正部项最多抵消多少价格下降量。 固定（i）中的输入价格 $p'$，令 $M$ 和 $\mathcal S_k$ 分别为第 3.3 节中的匹配以及对 $k$ 选出的集合族。先检查比较所用的参考集合。对 $j\in\{2,4,6\}$，每个 $S_j(R)$ 都包含于一条可行路线中，因此满足容量约束。来自不同参考路线的集合互不相交。若 $S_j(R)$ 为空，则对应的正部项为零。若 $S_j(R)=\{v\}$，由价格上界以及 $R$ 中连接 $r$ 与 $v$ 的两部分上的三角不等式，得到 $p'_v\le2c(r,v)\le c(R)$，因此这一项仍为零。当 $|S_j(R)|\ge2$ 时，由三角不等式，将 $R$ 限制在 $S_j(R)$ 上所得路线的费用至多为 $c(R)$。由于 $R_{S_j(R)}$ 是访问 $S_j(R)$ 的最便宜路线，有 $c(R_{S_j(R)})\le c(R)$。 因此，$S_2(R)$ 的每个正贡献都对应一个可行客户对，其边权至少为 $p'(S_2(R))-c(R)>0$。这些客户对属于匹配图，且顶点互不相交，所以构成一个可行匹配。由 $M$ 的最大权性质， $$ \sum_{e\in M}\bigl(p'(e)-c(R_e)\bigr) \ge \sum_{R\in\mathcal R_0} \bigl(p'(S_2(R))-c(R)\bigr)_+. $$ 固定 $k\in\{4,6\}$。对于集合打包，令 $\mathcal R_{+,k}:=\{R\in\mathcal R_0:p'(S_k(R))>c(R)\}$。上述观察说明，对应的 $S_k(R)$ 是大小为 $2$ 至 $k$ 的互不相交可行集合，且都被算法枚举。每条匹配边至多与其中两个集合相交，因为每个端点至多属于一个集合。所有匹配边的权重为正，所以扣除的总量至多为匹配节省的两倍。展开参考集合的权重，并使用 $c(R_{S_k(R)})\le c(R)$，得到 $$ \sum_{R\in\mathcal R_{+,k}}w(S_k(R)) \ge \sum_{R\in\mathcal R_0}\bigl(p'(S_k(R))-c(R)\bigr)_+ -2\sum_{e\in M}\bigl(p'(e)-c(R_e)\bigr). $$ 即使 $p'(S_k(R))>c(R)$，权重 $w(S_k(R))$ 仍可能非正。去掉这些集合保持互不相交性，且不会降低总权重。剩余集合族可能为空，但它是算法所用正权集合打包实例的可行解。因此，推论 2.6 保证 $\sum_{S\in\mathcal S_k}w(S)$ 至少为上述下界的 $b_k$ 倍。 构造 $\mathcal R_{\mathrm{pack},k}$ 时，每条与选中集合相交的匹配边只被删除一次。但在 $\sum_{S\in\mathcal S_k}w(S)$ 中，它的正节省可能被扣除多次：每与一个选中集合相交，就被扣除一次。因此，输出的实际节省至少为匹配节省加上选中集合的总权重。结合这一观察和上述两项比较，并使用 $1-2b_k\ge0$，得到 $$ \begin{aligned} &p'(V(\mathcal R_{\mathrm{pack},k}))-c(\mathcal R_{\mathrm{pack},k})\\ &\quad\ge \sum_{e\in M}\bigl(p'(e)-c(R_e)\bigr) +\sum_{S\in\mathcal S_k}w(S)\\ &\quad\ge (1-2b_k)\sum_{R\in\mathcal R_0} \bigl(p'(S_2(R))-c(R)\bigr)_+ +b_k\sum_{R\in\mathcal R_0} \bigl(p'(S_k(R))-c(R)\bigr)_+. \end{aligned} $$ 乘以 $a_k$ 后对 $k\in\{4,6\}$ 求和，得到加权节省的比较。由于 $a_4+a_6=1$，且参考路线的客户集合构成 $V$ 的划分，从 $p'(V)$ 中减去所得节省即证明（i）。 对（ii），固定 $R\in\mathcal R_0$ 和非负价格向量 $p''\le p'$。比较所用的集合只依赖需求和处理相同需求时使用的固定顺序，因此保持不变。正部函数单调不减且为 $1$-Lipschitz 函数，所以对所有 $z\in\mathbb R$ 和 $t\ge0$，有 $0\le z_+-(z-t)_+\le t$。对每个 $j\in\{2,4,6\}$，取 $z=p'(S_j(R))-c(R)$ 和 $t=p'(S_j(R))-p''(S_j(R))$。由 $p''\le p'$，有 $t\ge0$，且 $z-t=p''(S_j(R))-c(R)$。因此，每个正部项的下降量至多为其参考集合上的价格下降量。 由于 $S_j(R)\subseteq V(R)$，且每个客户的价格下降量非负，每个参考集合上的价格下降量至多为 $p'(V(R))-p''(V(R))$。将这些上界用于 $F$ 中减去的各项，得到 $$ \begin{aligned} F(R;p')-F(R;p'') &\ge\left(1-\frac{129}{805}-\frac9{23}-\frac1{35}\right) \bigl(p'(V(R))-p''(V(R))\bigr)\\ &=\frac{338}{805}\bigl(p'(V(R))-p''(V(R))\bigr). \end{aligned} $$ 这证明了（ii）。证毕。 ### 5.2. 特殊路线 现在将引理 5.1 的比较用于最优路线族 $\mathcal T^*$。引理 5.2 先在原价格 $p$ 下比较 $F(R;p)$ 与 $2\rho(R)+c(R)/2$，并找出可能超过这一上界的路线结构。引理 5.3 再计入局部搜索带来的价格下降。 **引理 5.2。** 设 $p$ 是式（2.4）定义的价格。对每条可行路线 $R$，都有 $F(R;p)\le2\rho(R)+c(R)/2$，除非 $R$ 恰好包含一个 非小客户 $v$，且 $25/56<d_v<31/56$、$c(r,v)>0$。若 $R$ 恰好包含一个 非小客户，则 $F(R;p)=p(V(R))$。 证明见附录 A.3。 在 $\mathcal T^*$ 中，若一条路线恰好包含一个 非小客户，且 $p(V(R))>2\rho(R)+c(R)/2$，则称其为特殊路线。令 $V_{\mathrm{exc}}$ 为这些路线中唯一的 非小客户构成的集合。对每个 $v\in V_{\mathrm{exc}}$，令 $R_v^*\in\mathcal T^*$ 为包含 $v$ 的唯一一条最优路线。由引理 5.2，对 $v\in V_{\mathrm{exc}}$ 有 $25/56<d_v<31/56$ 和 $c(r,v)>0$。 在特殊路线上，价格下降量全部计入费用上界。在其余路线上，至少有 $338/805$ 的比例计入。 **引理 5.3。** 假设对每个 $v\in V$ 都有 $0\le p'_v\le p_v$，且当 $d_v\le25/56$ 时有 $p'_v=p_v$。则匹配与集合打包的输出 $\mathcal R_{\mathrm{pack},4}$ 和 $\mathcal R_{\mathrm{pack},6}$ 满足 $$ \begin{aligned} &\sum_{k\in\{4,6\}}a_k \left[c(\mathcal R_{\mathrm{pack},k}) +p'\bigl(V\setminus V(\mathcal R_{\mathrm{pack},k})\bigr)\right]\\ &\quad\le\sum_{R\in\mathcal T^*}\left[2\rho(R)+\frac12c(R)\right]\\ &\qquad+\sum_{v\in V_{\mathrm{exc}}} \left[p(V(R_v^*))-2\rho(R_v^*)-\frac12c(R_v^*)-(p_v-p'_v)\right]\\ &\qquad-\frac{338}{805}\sum_{v\notin V_{\mathrm{exc}}}(p_v-p'_v). \end{aligned} $$ 证明见附录 A.4。 ### 5.3. 候选评分 引理 5.3 用特殊路线的超额和局部搜索的节省表示费用上界。我们先选择一个距离阈值，将恢复的需求转化为候选评分的下界。再对一条参考路线中从仓库到客户的两条路径应用需求恢复。两条路径的费用之和等于参考路线的费用，因此，对两个候选评分取平均就能得到所需比较。 下面的引理给出这一比较所用的距离阈值。它将 小客户的价格与算法测试的某个距离阈值以上的需求进行比较。 **引理 5.4。** 设 $S\subseteq V_{\mathrm{small}}$ 和 $H\ge0$ 满足对每个 $u\in S$ 都有 $2c(r,u)\le H$。对 $0\le t\le H$，定义 $S(t)=\{u\in S:2c(r,u)\ge t\}$。存在 $t\in\{0\}\cup\{2c(r,u):u\in S\}$，使得 $$ p(S)-\frac{7\lambda}{25}\,t\,d(S(t))\le H d(S). \tag{5.2} $$ 证明见附录 A.5。 下面的引理将候选评分与参考路线超额的两倍比较。比较中扣除不可用 小客户价格的 $\lambda/2$，以及误差 $\varepsilon c(R)/2$。对特殊路线求和，再使用引理 5.3 中的权重后，评分中省去的 小客户价格可以支付不可用客户带来的总损失。近似误差之和至多为 $\varepsilon\mathrm{opt}/2$。 **引理 5.5。** 设 $p$ 为式（2.4）中的价格，$\Phi$ 为式（3.2）中的评分。设 $R$ 是一条恰好包含一个 非小客户 $v$ 的可行路线，且 $d_v>25/56$、$c(r,v)>0$、$p(V(R))>2\rho(R)+c(R)/2$。对可用集合 $A\subseteq V_{\mathrm{small}}$，令 $U=(V(R)\cap V_{\mathrm{small}})\setminus A$。当 $0<\varepsilon\le1/9$ 时，算法 4.1 以 $(v,A,\varepsilon)$ 为输入，返回一条服务 $v$ 以及 $A$ 的某个子集的可行路线 $R'$，且满足 $$ \Phi(R')\ge 2\left[p(V(R))-2\rho(R)-\frac12c(R)\right] -\frac\lambda2p(U)-\frac\varepsilon2c(R). $$ **证明。** 选择引理 5.4 给出的距离阈值，并对 $R$ 的两条 $r$–$v$ 路径应用引理 4.1。两条路径的费用之和为 $c(R)$，因此，对两个评分下界取平均后，费用项为 $-(1+\varepsilon/4)c(R)$。距离阈值给出的界将恢复的需求与参考 小客户的价格比较，同时扣除不可用客户的价格。 令 $L=c(R)$、$H=2\rho(R)$ 和 $S=V(R)\cap V_{\mathrm{small}}$。有 $0<H\le L$。对 $S,H$ 应用引理 5.4，令 $t$ 为其中给出的值，并沿用引理中 $S(t)$ 的定义。算法会测试距离阈值 $t/2$。在这个阈值下，位于阈值以上的可用客户集合为 $A'=\{u\in A:2c(r,u)\ge t\}$。每个 $u\in A'$ 都满足 $p_u\ge(28/25)t d_u$。 将 $R$ 分成两条 $r$–$v$ 路径 $P_1,P_2$，其中第二部分反向。它们的费用之和为 $L$。令 $X_i$ 为 $P_i$ 上属于 $A'$ 的 小客户。这两个集合互不相交，且并集为 $V(R)\cap A'$。对 $i=1,2$，由 $R$ 的可行性，有 $d_v+d(X_i)\le d(V(R))\le1$。引理 4.1 保证存在一条被测试的路线 $R'_i$，满足 $c(R'_i)\le2(1+\varepsilon/4)c(P_i)$，且其 小客户的需求至少为 $d(X_i)-\varepsilon/4$。因此，由 $A'$ 上的价格下界，有 $\Phi(R'_i)\ge p_v+(28\lambda/25)t[d(X_i)-\varepsilon/4]-2(1+\varepsilon/4)c(P_i)$。算法返回所有被测试路线中评分最大的路线。对这两个下界取平均，得到 $$ \Phi(R')\ge p_v-L+\frac{14\lambda}{25}\,t\,d(V(R)\cap A') -\frac\varepsilon4L-\frac{7\lambda\varepsilon}{25}\,t. $$ 由于 $t\le H\le L$ 且 $28\lambda/25<1$，两个误差项之和至多为 $\varepsilon L/2$。 位于距离阈值以上、但不属于 $A'$ 的参考客户都属于 $U$。对其中每个客户，有 $(28/25)t d_u\le p_u$，所以 $(28/25)t[d(S(t))-d(V(R)\cap A')]\le p(U)$。因此， $$ \Phi(R')\ge p_v-L+\frac{14\lambda}{25}\,t\,d(S(t)) -\frac\lambda2p(U)-\frac\varepsilon2L. $$ 为了将这一界与超额比较，使用式（5.2）及可行性，得到 $(14\lambda/25)t d(S(t))\ge2p(S)-2H d(S)$ 和 $d(S)\le1-d_v$。价格公式给出 $p_v\le4d_vc(r,v)\le2H d_v$。因此，$2H d(S)\le2H-p_v$，候选评分至少为 $2[p_v+p(S)-H-L/2]-(\lambda/2)p(U)-\varepsilon L/2$。由 $p_v+p(S)=p(V(R))$ 和 $H=2\rho(R)$，得到所需下界。证毕。 ### 5.4. 合并节省 本节结合候选评分界与打包费用界，控制 $k\in\{4,6\}$ 对应的合并后路线族的费用与未服务客户价格之和的加权平均。我们先用调整后的价格表示这些费用，再对局部搜索最后一轮扫描中的比较求和，利用评分中省去的价格项支付不可用 小客户带来的损失。由此得到的节省将抵消引理 5.3 中特殊路线的超额。 **引理 5.6。** 对 $k\in\{4,6\}$，令 $\mathcal R_k$ 为 $\mathcal R_{\mathrm{pack},k}$ 与保留的局部搜索路线合并后的部分路线族。调整后的价格为 $p'_v=p_v-s(R_v)$，其中 $R_v$ 表示为 $v$ 最终存储的路线。则 $$ c(\mathcal R_k)+p(V\setminus V(\mathcal R_k)) =c(\mathcal R_{\mathrm{pack},k}) +p'(V\setminus V(\mathcal R_{\mathrm{pack},k})). \tag{5.3} $$ **证明。** 固定 $k\in\{4,6\}$，记 $\mathcal R=\mathcal R_k$ 和 $\mathcal R_{\mathrm{pack}}=\mathcal R_{\mathrm{pack},k}$。合并后的路线具有互不相交的客户集合，因此其总节省为保留旧路线的节省与新路线的节省之和。 在新路线上代入 $p_v=p'_v+s(R_v)$，得到 $$ \begin{aligned} &p(V(\mathcal R))-c(\mathcal R)\\ &\qquad={}\sum_{v\notin V(\mathcal R_{\mathrm{pack}})}s(R_v) +p(V(\mathcal R_{\mathrm{pack}}))-c(\mathcal R_{\mathrm{pack}})\\ &\qquad=\sum_{v\in V}s(R_v) +p'(V(\mathcal R_{\mathrm{pack}}))-c(\mathcal R_{\mathrm{pack}}). \end{aligned} $$ 从 $p(V)$ 中减去上述节省，再使用 $p(V)-\sum_v s(R_v)=p'(V)$，即得式（5.3）。证毕。 下面的引理估计 $k\in\{4,6\}$ 对应的 $c(\mathcal R_k)+p(V\setminus V(\mathcal R_k))$ 的加权平均。补全任一部分路线族增加的费用至多为 $c(R_{\mathrm{TSP}})$ 加上未服务客户的价格。因此，将 $c(R_{\mathrm{TSP}})$ 加到引理的上界上，就得到两个补全解中较小费用的上界。 **引理 5.7。** 对 $0<\varepsilon\le1/9$ 和 $k\in\{4,6\}$，令 $\mathcal R_k$ 为算法 3.1 合并步骤后的部分路线族。则 $$ \begin{aligned} &\sum_{k\in\{4,6\}}a_k \left[c(\mathcal R_k)+p(V\setminus V(\mathcal R_k))\right]\\ &\qquad\le\sum_{R\in\mathcal T^*}\left[2\rho(R)+\frac12c(R)\right] +\frac{3\varepsilon}{4}\mathrm{opt}. \end{aligned} $$ **证明。** 最后一轮的候选比较用存储路线的评分、不可用 小客户带来的损失及误差项控制特殊路线的超额。恢复评分中省去的价格项，可以支付这部分损失，并得到打包费用界所需的节省。 最后一轮扫描没有更新，因此所有比较使用同一组路线。每个 $v\in V_{\mathrm{exc}}$ 都会在这一轮中被考察，因为引理 5.2 给出 $d_v>25/56$ 和 $c(r,v)>0$。对 $v\in V_{\mathrm{exc}}$，不可用 小客户恰为 $\bigcup_{u\ne v}S_u$ 中的客户。由引理 3.1（ii），存储路线的评分至少为返回候选路线的评分减去 $\varepsilon D/(4n)$。每条特殊路线的超额都为正，因此可以将引理 5.5 中超额的系数从 $2$ 降为 $1$。对 $R_v^*$ 应用该引理，得到 $$ \begin{aligned} \Phi(R_v)\ge{}&p(V(R_v^*))-2\rho(R_v^*)-\frac12c(R_v^*)\\ &-\frac\lambda2p\left(V(R_v^*)\cap\bigcup_{u\ne v}S_u\right) -\frac\varepsilon2c(R_v^*)-\frac{\varepsilon D}{4n}. \end{aligned} $$ 特殊最优路线 $R_v^*$ 的客户集合互不相交，因此每个不可用客户最多被计入一次，从而 $\sum_{v\in V_{\mathrm{exc}}}p(V(R_v^*)\cap\bigcup_{u\ne v}S_u)\le\sum_{u\in V}p(S_u)$。再使用 $\sum_{v\in V_{\mathrm{exc}}}c(R_v^*)\le\mathrm{opt}$ 和 $|V_{\mathrm{exc}}|\le n$，求和得到 $$ \begin{aligned} \sum_{v\in V_{\mathrm{exc}}}\Phi(R_v) \ge{}&\sum_{v\in V_{\mathrm{exc}}} \left[p(V(R_v^*))-2\rho(R_v^*)-\frac12c(R_v^*)\right]\\ &-\frac\lambda2\sum_{v\in V}p(S_v) -\frac\varepsilon2\mathrm{opt}-\frac{\varepsilon D}{4}. \end{aligned} \tag{5.4} $$ 在引理 5.3 中，$v\in V_{\mathrm{exc}}$ 对应的节省系数为 $1$，其余节省的系数为 $338/805$。为估计这个加权和，使用 $s(R_v)=\Phi(R_v)+(1-\lambda)p(S_v)$ 以及引理 3.1（i）给出的 $\Phi(R_v)\ge0$。这些系数满足 $(338/805)(1-\lambda)=\lambda/2$。因此， $$ \begin{aligned} &\sum_{v\in V_{\mathrm{exc}}}s(R_v) +\frac{338}{805}\sum_{v\notin V_{\mathrm{exc}}}s(R_v)\\ &\quad\ge\sum_{v\in V_{\mathrm{exc}}}\Phi(R_v) +\frac\lambda2\sum_{v\in V}p(S_v)\\ &\quad\ge\sum_{v\in V_{\mathrm{exc}}} \left[p(V(R_v^*))-2\rho(R_v^*)-\frac12c(R_v^*)\right] -\frac\varepsilon2\mathrm{opt}-\frac{\varepsilon D}{4}. \end{aligned} \tag{5.5} $$ 最后一个不等式使用式（5.4）。在引理 5.3 中取 $p'_v=p_v-s(R_v)$ 并代入式（5.5），其中 $p'$ 的条件由引理 3.1（i）保证。特殊路线的超额相消，从而得到打包路线费用与按 $p'$ 计价的未服务客户价格之和的加权上界，误差为 $\varepsilon\mathrm{opt}/2+\varepsilon D/4$。最后，对每个输出应用式（5.3），并使用式（2.1）中的 $D\le\mathrm{opt}$，即得结论。证毕。 ## 6. 运行时间与近似比 第 5 节估计了已选路线的费用与未服务客户价格之和。我们先给出算法的运行时间界，再将上述费用界与 TSP 巡回及补全保证结合，证明定理 1.1。 ### 6.1. 运行时间 式（1.1）中的运行时间界在附录 A.6 中证明。 ### 6.2. 主定理的证明 **定理 1.1 的证明。** 我们先处理提前返回的情形，再检查合并与补全保持可行性。对于费用界，每次 DP 调用都使用同一条巡回 $R_{\mathrm{TSP}}$ 的限制，其费用至多为 $c(R_{\mathrm{TSP}})$。将这条巡回的费用上界加到已选路线和剩余客户价格的加权上界上，每条最优路线对应的 $2\rho(R)$ 项都会相消。 若 $n\le1$，返回的单客户路线最优。若 $D=0$，由需求为正可知每个客户都满足 $c(r,v)=0$，所以返回路线的费用为零，同样最优。下文假设 $n\ge2$ 且 $D>0$。 对每个 $k\in\{4,6\}$，由引理 3.1（i）和第 3.3 节的构造，合并后的路线族 $\mathcal R_k$ 可行，且客户集合互不相交。DP 用可行路线恰好服务 $X_k$ 中的客户。因此，每个最终路线族 $\mathcal T_k$ 都恰好服务每个客户一次，返回的路线族 $\mathcal T$ 也如此。 由断言 3.3，对每个满足 $X_k\ne\varnothing$ 的 $k$，补全增加的费用至多为 $c(R_{\mathrm{TSP}})+p(X_k)$。当 $X_k=\varnothing$ 时，无需添加路线，因此这一上界仍然成立。算法返回 $\{\mathcal T_4,\mathcal T_6\}$ 中费用最小的路线族，所以其费用至多为系数 $9/10$ 和 $1/10$ 对应的加权平均。结合引理 5.7 与定理 2.3，得到 $$ \begin{aligned} c(\mathcal T) &\le c(R_{\mathrm{TSP}}) +\frac9{10}\bigl[c(\mathcal R_4)+p(X_4)\bigr] +\frac1{10}\bigl[c(\mathcal R_6)+p(X_6)\bigr]\\ &\le \sum_{R\in\mathcal T^*} \left[2c(R)-2\rho(R)+2\rho(R)+\frac12c(R)\right] +\frac{3\varepsilon}{4}\mathrm{opt}\\ &=(5/2+3\varepsilon/4)\mathrm{opt} \le(5/2+\varepsilon)\mathrm{opt}. \end{aligned} $$ 其中等式使用 $\sum_{R\in\mathcal T^*}c(R)=\mathrm{opt}$。附录 A.6 证明所述运行时间界。证毕。 ## 致谢 感谢 Zachary Friggstad 对本工作的有益讨论、反馈和建议。 AI 工具用于辅助本文的研究、基于程序的检查和写作。作者负责核实所有数学结论。 ## 参考文献 [1] Kemal Altinkemer and Bezalel Gavish. *Heuristics for Unequal Weight Delivery Problems with a Fixed Error Guarantee*. Operations Research Letters 6(4):149–158, 1987。[DOI](https://doi.org/10.1016/0167-6377(87)90012-5)。 [2] Amariah Becker, Philip N. Klein, and Aaron Schild. *A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs*. WADS 2019, LNCS 11646, pp. 99–111。[DOI](https://doi.org/10.1007/978-3-030-24766-9_8)。 [3] Jannis Blauth, Vera Traub, and Jens Vygen. *Improving the Approximation Ratio for Capacitated Vehicle Routing*. Mathematical Programming 197(2):451–497, 2023。[DOI](https://doi.org/10.1007/s10107-022-01841-4)。 [4] Kamalika Chaudhuri, Brighten Godfrey, Satish Rao, and Kunal Talwar. *Paths, Trees, and Minimum Latency Tours*. FOCS 2003, pp. 36–45。[DOI](https://doi.org/10.1109/SFCS.2003.1238179)；[PDF](https://www.microsoft.com/en-us/research/wp-content/uploads/2003/01/pub08-mlt.pdf)。 [5] Chandra Chekuri, Nitish Korula, and Martin Pál. *Improved Algorithms for Orienteering and Related Problems*. ACM Transactions on Algorithms 8(3):23:1–23:27, 2012。[DOI](https://doi.org/10.1145/2229163.2229167)；[PDF](https://chekuri.cs.illinois.edu/papers/orienteering-journal.pdf)。 [6] Nicos Christofides. *Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem*. Operations Research Forum 3, Article 20, 2022。[DOI](https://doi.org/10.1007/s43069-021-00101-z)。 [7] George B. Dantzig and John H. Ramser. *The Truck Dispatching Problem*. Management Science 6(1):80–91, 1959。[DOI](https://doi.org/10.1287/mnsc.6.1.80)。 [8] Aparna Das and Claire Mathieu. *A Quasipolynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing*. Algorithmica 73(1):115–142, 2015。[DOI](https://doi.org/10.1007/s00453-014-9906-4)。 [9] Daniel Ebert and Leonard Weismantel. *Improved Approximation for Unsplittable CVRP via a Greedy Approach*. arXiv:2609.16910, 2026。[arXiv](https://arxiv.org/abs/2609.16910)。 [10] Zachary Friggstad, Fabrizio Grandoni, and Ramin Mousavi. *Breaching the 2-Approximation Barrier for Euclidean Capacitated Vehicle Routing*. SODA 2026, pp. 2644–2668。[DOI](https://doi.org/10.1137/1.9781611978971.97)。 [11] Zachary Friggstad, Ramin Mousavi, Mirmahdi Rahgoshay, and Mohammad R. Salavatipour. *Improved Approximations for a CVRP with Unsplittable Demands*. Mathematics of Operations Research, Articles in Advance, 2025。[DOI](https://doi.org/10.1287/moor.2022.0097)。 [12] Fabrizio Grandoni, Claire Mathieu, and Hang Zhou. *Unsplittable Euclidean Capacitated Vehicle Routing: A $(2+\varepsilon)$-Approximation Algorithm*. ITCS 2023, LIPIcs 251, 63:1–63:13。[DOI](https://doi.org/10.4230/LIPIcs.ITCS.2023.63)。 [13] M. Haimovich and A. H. G. Rinnooy Kan. *Bounds and Heuristics for Capacitated Routing Problems*. Mathematics of Operations Research 10(4):527–542, 1985。[DOI](https://doi.org/10.1287/moor.10.4.527)。 [14] Aditya Jayaprakash and Mohammad R. Salavatipour. *Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension*. ACM Transactions on Algorithms 19(2):20:1–20:36, 2023。[DOI](https://doi.org/10.1145/3582500)。 [15] Claire Mathieu and Hang Zhou. *A PTAS for Capacitated Vehicle Routing on Trees*. ACM Transactions on Algorithms 19(2):17:1–17:28, 2023。[DOI](https://doi.org/10.1145/3575799)。 [16] Claire Mathieu and Hang Zhou. *A Tight $(1.5+\varepsilon)$-Approximation for Unsplittable Capacitated Vehicle Routing on Trees*. Mathematical Programming 212:115–146, 2025。[DOI](https://doi.org/10.1007/s10107-024-02094-z)。 [17] Tobias Mömke and Hang Zhou. *Capacitated Vehicle Routing in Graphic Metrics*. SOSA 2023, pp. 114–123。[DOI](https://doi.org/10.1137/1.9781611977585.ch11)。 [18] Theophile Thiery and Justin Ward. *An Improved Approximation for Maximum Weighted $k$-Set Packing*. SODA 2023, pp. 1138–1162。[DOI](https://doi.org/10.1137/1.9781611977554.ch42)；[作者完整版](https://arxiv.org/abs/2301.07537)。 [19] Jingyang Zhao and Mingyu Xiao. *Multidepot Capacitated Vehicle Routing with Improved Approximation Guarantees*. Theoretical Computer Science 1043, Article 115265, 2025。[DOI](https://doi.org/10.1016/j.tcs.2025.115265)。 [20] Jingyang Zhao and Mingyu Xiao. *Approximating Unsplittable Capacitated Vehicle Routing: Analysis via Factor-Revealing LPs*. arXiv:2601.21660v2, 2026。[arXiv](https://arxiv.org/abs/2601.21660v2)。 [21] Jingyang Zhao and Mingyu Xiao. *Improved Approximations for the Capacitated Vehicle Routing Problem with Fixed Capacity*. Information and Computation 308, Article 105405, 2026。[DOI](https://doi.org/10.1016/j.ic.2026.105405)。 [22] Jingyang Zhao and Mingyu Xiao. *Tight Approximations for Fixed-Order Vehicle Routing with Stochastic Demands*. arXiv:2610.16802v1, 2026。[arXiv](https://arxiv.org/abs/2610.16802v1)。 ## 附录 A. 省略的证明 ### A.1. 推论 2.6 的证明 **证明。** 在定理 2.5 中取 $k=4$ 和 $t=111/400$。由于 $\sqrt{1-t}=17/20$，近似因子满足 $$ \rho_4(111/400) =\frac52-\frac12\min\left\{\frac{289}{689},\frac{36}{85}\right\} =\frac{1578}{689}<\frac{23}{10}. $$ 因此，返回子族的总权重至少为最优总权重的 $10/23$。对于 $k=6$，取 $t=0$，得到 $\rho_6(0)=7/2$。将 $k=4$ 和 $k=6$ 代入定理 2.5 的运行时间界，分别得到指数 $57$ 和 $191$。证毕。 ### A.2. 引理 3.1 的证明 **证明。** 可用集合保证替换路线不会与其他存储路线共享客户。接着，我们用每条路线所对应的大客户价格界定其节省，从而控制总评分。每次接受的更新都使总评分增加超过接受阈值，因此更新次数有限。 初始时，每条非空路线都是服务需求 $d_v>1/2$ 的客户的单客户路线 $(r,v,r)$。这些路线可行，且客户集合两两不交。由于 $p_v=2c(r,v)$，它们的节省和评分均为零。空路线的节省和评分也为零。 考虑为 $v$ 返回的一条候选路线。由算法 4.1 的保证，它是可行的，且服务 $v$ 和可用集合中的客户。其大客户 $v$ 不同于其他存储路线的大客户，小客户则位于 $\bigcup_{u\ne v}S_u$ 之外。因此，用它替换 $R_v$ 保持了路线结构、可行性和客户集合的不交性。接受替换会严格增加 $\Phi(R_v)$，所以所有评分保持非负。算法只更新由大客户索引的路线，每条替换路线仍服务其对应客户。因此，满足 $d_v\le25/56$ 的客户所索引的路线始终为空，而每条初始非空路线始终非空。 为了证明 $s(R_v)\le p_v$，我们先界定 $R_v$ 上小客户的价格。对于非空路线，由可行性和 $d_v>25/56$，有 $d(S_v)\le1-d_v<31/56$。每个 $u\in S_v$ 都满足 $c(r,u)\le c(R_v)/2$，所以由价格定义，$p(S_v)\le(28/25)d(S_v)c(R_v)\le31c(R_v)/50$。特别地，$p(S_v)\le c(R_v)$，从而 $s(R_v)=p_v+p(S_v)-c(R_v)\le p_v$。下界由 $s(R_v)=\Phi(R_v)+(1-\lambda)p(S_v)\ge0$ 得到。按照约定，空路线也满足这两个界。这就证明了 (i)。 接下来用 $D$ 界定总评分。由价格定义，每名客户都满足 $p_v\le4d_vc(r,v)$。当 $d_v\le3/28$ 时，$d_vc(r,v)$ 的系数为 $56/25<4$；当 $3/28<d_v\le1/2$ 时，该界由 $112d_v-6\le100d_v$ 得到；当 $d_v>1/2$ 时，该界由 $2<4d_v$ 得到。因此， $$ 0\le\sum_{v\in V}\Phi(R_v)\le\sum_{v\in V}s(R_v) \le p(V)\le4\sum_{v\in V}d_vc(r,v)=2D. $$ 价格 $p$ 始终不变，每次接受的更新只修改一条存储路线，因此使总评分增加超过 $\varepsilon D/(4n)$。初始总评分为零，所以接受的更新次数严格少于 $2D/(\varepsilon D/(4n))=8n/\varepsilon$。每轮扫描至多调用 $n$ 次候选路线算法，且要么接受一次更新，要么终止。因此，局部搜索必然终止。 最后一轮扫描没有接受任何更新。因此，所有存储路线在这一轮中保持不变，所有可用集合都由同一个最终状态计算。每条返回的候选路线都未通过严格的接受条件，这就得到 (ii) 中的不等式。证毕。 ### A.3. 引理 5.2 的证明 **证明。** 对于至少包含两名非小客户的路线，我们先将价格提高到与需求有关的上界，再求所得分段线性函数的最大值。对于恰有一名非小客户的路线，我们保留上界 $p_v\le2c(r,v)$，以确定特殊路线对应的需求区间。 若 $c(R)=0$，则 $R$ 上所有客户的价格都为零。否则，令 $L=c(R)>0$，$m=|V(R)\setminus V_{\mathrm{small}}|$。每个 $u\in V(R)$ 都满足 $c(r,u)\le\rho(R)\le L/2$。若 $m=0$，则所有客户都是小客户，因而 $F(R;p)=p(V(R))\le(56/25)\rho(R)$。于是 $F(R;p)-2\rho(R)\le(6/25)\rho(R)\le3L/25$。 现设 $m\ge2$。每名非小客户的需求都大于 $3/28$，所以 $m\le9$。对于每名非小客户 $u\in V(R)$，令 $\tilde d_u=\min\{d_u,1/2\}$，用于下面的上界。由可行性，至多有一名客户的需求大于 $1/2$，且此时其他客户的需求都小于 $1/2$。因此，$\tilde d_u$ 保持了原来的需求顺序，且 $\sum_{u\in V(R)\setminus V_{\mathrm{small}}}\tilde d_u+d(V(R)\cap V_{\mathrm{small}})\le1$。定义价格 $\bar p$：$V(R)$ 外的价格不变；对于 $R$ 上的非小客户，令 $\bar p_u=2\rho(R)(56\tilde d_u-3)/25$；对于 $R$ 上的小客户，令 $\bar p_u=(56/25)\rho(R)d_u$。由式 (2.4) 和 $c(r,u)\le\rho(R)$，这些价格都是 $p_u$ 的上界。按原需求排列非小客户，也就按提高后的价格排列了这些客户。由引理 5.1(ii)，有 $F(R;p)\le F(R;\bar p)$。 记 $A_m=(56-3m)/(25m)$，并令 $z=\bar p(V(R)\setminus V_{\mathrm{small}})/(mL)$。当 $\rho(R)>0$ 时，截断后的非小客户总需求满足 $\sum_{u\in V(R)\setminus V_{\mathrm{small}}}\tilde d_u=(25mLz/(2\rho(R))+3m)/56$。因此，可行性给出 $0\le z\le2\rho(R)A_m/L\le A_m$ 和 $\bar p(V(R))/L\le m\rho(R)A_m/L+mz/2$。若 $\rho(R)=0$，则所有提高后的价格都为零，所需的界成立。 在 $m$ 个非负数中，最大的 $\min\{j,m\}$ 个数之和至少占总和的 $\min\{j,m\}/m$。因此，对于 $j\in\{2,4,6\}$，有 $\bar p(S_j(R))\ge\min\{j,m\}zL$。$F$ 中的所有比较项都带负号。此外，$mA_m/2-1=3(2-m)/50\le0$，且 $2\rho(R)/L\ge z/A_m$。这些界给出 $$ \begin{aligned} \frac{F(R;p)-2\rho(R)}{L} &\le \frac{2\rho(R)}L\left(\frac{mA_m}{2}-1\right) +\frac{mz}{2} -\frac{129}{805}(2z-1)_+\\ &\quad-\frac9{23}(\min\{4,m\}z-1)_+ -\frac1{35}(\min\{6,m\}z-1)_+\\ &\le\left(m-\frac1{A_m}\right)z -\frac{129}{805}(2z-1)_+ -\frac9{23}(\min\{4,m\}z-1)_+\\ &\quad-\frac1{35}(\min\{6,m\}z-1)_+, \qquad 0\le z\le A_m. \end{aligned} \tag{A.1} $$ 最后一个表达式是分段线性的，其最大值在区间端点或某个折点处取得。代入这些点，得到下表中的数值。所有情形的最大值均不超过 $1/2$。 | $m$ | $A_m$ | 内部折点 | 使其最大的 $z$ | 最大值 | | --- | --- | --- | --- | --- | | $2$ | $1$ | $1/2$ | $1/2$ | $1/2$ | | $3$ | $47/75$ | $1/3,\ 1/2$ | $1/2$ | $18622/37835$ | | $4$ | $11/25$ | $1/4$ | $11/25$ | $8873/20125$ | | $5$ | $41/125$ | $1/5,\ 1/4$ | $41/125$ | $2011/4025$ | | $6$ | $19/75$ | $1/6,\ 1/4$ | $19/75$ | $10061/20125$ | | $7$ | $1/5$ | $1/6$ | $1/5$ | $69/175$ | | $8$ | $4/25$ | $\varnothing$ | $4/25$ | $7/25$ | | $9$ | $29/225$ | $\varnothing$ | $29/225$ | $4/25$ | 最后考虑 $m=1$。令 $v$ 为唯一的非小客户。此时所有比较集合都等于 $\{v\}$，且 $p_v\le2c(r,v)\le L$，所以 $F(R;p)=p(V(R))$。其余客户的总需求至多为 $1-d_v$。在 $d_v=1/2$ 两侧分别应用式 (2.4)，得到 $$ \begin{aligned} d_v\le\tfrac12:\qquad p(V(R))-2\rho(R)&\le\frac{56}{25}\rho(R)d_v,\\ d_v\ge\tfrac12:\qquad p(V(R))-2\rho(R)&\le\frac{56}{25}\rho(R)(1-d_v). \end{aligned} $$ 由于 $2\rho(R)\le L$，当 $d_v\le25/56$ 和 $d_v\ge31/56$ 时，上述两个界分别不超过 $L/2$。若 $c(r,v)=0$，则 $p_v=0$，而小客户的价格总和至多为 $(56/25)\rho(R)\le2\rho(R)+3L/25$。因此，只有当 $25/56<d_v<31/56$ 且 $c(r,v)>0$ 时，才可能超出所需的界。证毕。 ### A.4. 引理 5.3 的证明 **证明。** 对 $\mathcal T^*$ 应用引理 5.1(i)，并在价格 $p'$ 下界定每条路线的贡献。输入满足 $0\le p'_v\le p_v\le2c(r,v)$。 对于 $v\in V_{\mathrm{exc}}$，所有比较集合都等于 $\{v\}$。由于 $p'_v\le p_v\le2c(r,v)\le c(R_v^*)$，所有正部项都为零。这条路线上的其他客户 $u$ 均为小客户，所以 $d_u\le3/28<25/56$ 且 $p'_u=p_u$。因此，$F(R_v^*;p')=p(V(R_v^*))-(p_v-p'_v)$。减去再加上 $2\rho(R_v^*)+c(R_v^*)/2$，就得到陈述中该路线的贡献。 对于其他每条 $R\in\mathcal T^*$，都有 $F(R;p)\le2\rho(R)+c(R)/2$。当路线含有零名或至少两名非小客户时，这由引理 5.2 得到；当恰有一名非小客户时，这由同一引理和特殊路线的定义得到。因此，引理 5.1(ii) 给出 $$ F(R;p')\le2\rho(R)+\frac12c(R) -\frac{338}{805}\sum_{u\in V(R)}(p_u-p'_u). $$ 对 $\mathcal T^*$ 中的路线求和，它们的客户集合构成 $V$ 的一个划分。位于特殊路线上的 $V\setminus V_{\mathrm{exc}}$ 中的客户都是小客户，所以其价格减少量为零。因此，其他路线上的价格减少量之和恰好为 $\sum_{v\notin V_{\mathrm{exc}}}(p_v-p'_v)$。代入引理 5.1(i)，即得结论。证毕。 ### A.5. 引理 5.4 的证明 **证明。** 将 $p(S)$ 写成各个距离阈值以上客户需求的积分，就能用 $\max_{0\le t\le H}t\,d(S(t))$ 界定它。在使该量最大的距离阈值 $t$ 处，我们对 $\lambda$ 的选择保证 $p(S)-(7\lambda/25)t\,d(S(t))$ 不超过 $H d(S)$。 若 $S=\varnothing$，或 $S$ 中所有客户到仓库的距离都为零，取 $t=0$。否则，定义 $Z=\max_{0\le t\le H}t\,d(S(t))>0$。在相邻的两个 $2c(r,u)$ 值之间，$d(S(t))$ 保持不变，而 $t\,d(S(t))$ 随 $t$ 增加。因此，某个最大值点等于 $S$ 中一名客户到仓库距离的两倍。此外，$Z\le H d(S)$，且对于 $t>0$，有 $d(S(t))\le\min\{d(S),Z/t\}$。每名客户 $u$ 在整个区间 $[0,2c(r,u)]$ 上贡献其需求，对客户求和得到 $$ \begin{aligned} \frac{25}{28}p(S) &=\int_0^H d(S(t))\,dt\\ &\le\int_0^{Z/d(S)}d(S)\,dt +\int_{Z/d(S)}^H\frac Zt\,dt =Z\left(1+\log\frac{H d(S)}Z\right). \end{aligned} $$ 对 $x=H d(S)e^{-\lambda/4}/Z$ 应用不等式 $\log x\le x-1$（$x>0$）。上述界给出 $p(S)-(7\lambda/25)Z\le(28/25)H d(S)e^{-\lambda/4}$。最后，$\lambda/4=169/1481$，且 $e^{169/1481}>1+169/1481+(169/1481)^2/2>28/25$，所以 $(28/25)e^{-\lambda/4}<1$。取一个使 $t\,d(S(t))$ 最大的 $t$，就得到式 (5.2)。证毕。 ### A.6. 运行时间 所有运行时间界均省略数值输入及精度参数的二进制编码长度中的多项式因子。提前返回的情形 $n\le1$ 和 $D=0$ 需要 $O(n+1)$ 时间。下面假设 $n\ge2$、$D>0$ 且 $0<\varepsilon\le1/9$。 每个被枚举集合 $B$ 中的客户都满足 $d_u>\varepsilon/4$。结合 $d_v+d(B)\le1$，得到 $|B|<4/\varepsilon$。与算法 4.1 中一样，令 $m$ 为可选客户副本的总数，$N$ 为当前集合 $B$ 对应的复制图的顶点数。每名可选客户至多有 $n$ 个副本。因此， $$ \begin{aligned} B\text{ 的枚举数量} &\le\sum_{j=0}^{\min\{n,\lfloor4/\varepsilon\rfloor\}}\binom nj =n^{O(1/\varepsilon)},\\ m&\le n^2,\\ N&:=m+(|B|+1)(m+3)+2\le(n+2)(n^2+3)=O(n^3). \end{aligned} $$ 每次候选路线调用至多测试 $n+1$ 个距离阈值。对于每个距离阈值和枚举集合 $B$，至多测试 $n^2+1$ 个配额值。由引理 3.1(ii)，扫描次数至多为 $1+8n/\varepsilon$，每轮扫描至多调用 $n$ 次候选路线算法。因此，配额树算法的调用总数至多为 $$ n\left(1+\frac{8n}{\varepsilon}\right)(n+1) \left(\sum_{j=0}^{\min\{n,\lfloor4/\varepsilon\rfloor\}}\binom nj\right) (n^2+1). $$ 当精度为 $\varepsilon/4$ 时，定理 2.7 给出的单次调用时间为 $N^{O(1/\varepsilon)}=n^{O(1/\varepsilon)}$。由于 $n\ge2$，上述所有因子都能被 $n^{O(1/\varepsilon)}$ 吸收。构造每个复制图，以及从每棵返回的树中恢复一条路线，都只需关于 $n$ 的多项式时间。因此，整个局部搜索阶段需要 $n^{O(1/\varepsilon)}$ 时间。 对于每个 $k\in\{4,6\}$，令 $\mathcal F_k$ 为大小至多为 $k$ 的正权候选集合族。有 $|\mathcal F_k|=O(n^k)$。计算每条路线的费用至多检查 $6!$ 种访问顺序，每个集合至多与 $6$ 条匹配边冲突。因此，在计算最大权匹配后，存储每名客户的匹配对象，就能在 $O(n^6)$ 时间内完成这些工作。匹配本身需要多项式时间。推论 2.6 对两个集合族分别在多项式时间内给出所需的 $10/23$ 和 $2/7$ 保证。由于 $\varepsilon\le1/9$，这两个运行时间界都被 $n^{O(1/\varepsilon)}$ 吸收。 复制图有 $O(n^3)$ 个顶点，边费用来自输入距离和零费用边。每条存储路线至多访问 $n$ 名原客户。其费用、价格、节省、评分和容量检查只涉及多项式个输入有理数的加法和乘法，因此具有多项式编码长度。改善阈值 $\varepsilon D/(4n)$、调整后的价格 $p'$，以及匹配和集合打包的权重，也都具有多项式编码长度。 算法调用定理 2.3 一次，其多项式运行时间被 $n^{O(1/\varepsilon)}$ 吸收。对于每个非空的 $X_k$，构造该巡回在 $X_k$ 上的限制需要 $O(n)$ 时间。至多两次 DP 调用总共需要 $O(n^2)$ 时间和 $O(n)$ 空间。这证明了式 (1.1)，并且对于每个固定的 $\varepsilon$，数值运算的额外开销也是多项式的。 --- TCS 论文就是简单。