个性化末端物流的新挑战：基于邻域搜索的车辆路径混合启发式求解框架

一、研究背景与问题提出

传统的车辆路径问题（VRP）主要关注利用最少车辆或最短路程完成所有客户配送。然而，随着第三方物流和电子商务的发展，客户可以选择不同的配送方式。例如在中国三方物流公司中，客户可选择送货上门或在便利店（共享提货点）自提，配送成本与服务水平存在明显冲突。因此，学术界提出带配送选项的车辆路径问题（Vehicle Routing Problem with Delivery Options，VRPDO）。

VRPDO的主要特征包括：

• 两类配送地点：

• 共享提货点（SDL）：可同时为多个订单提供服务，容量有限，需要提前停靠。
• 独立提货点（IDL）：对应每个订单的客户地址。

• 多种服务选项：每个请求对应一组可选的SDL或IDL，客户会偏好某一种选项。

• 时间窗和服务水平约束：要求至少β₀比例的订单采用首选选项，β₁比例的订单采用首选或第二顺位选项。

• 目标：在满足车辆容量、时间窗及服务水平约束的同时，最小化总成本（固定车辆成本 + 行驶成本）。

下图展示了一个 VRPDO 场景示意：车辆从配送中心出发，沿途为不同颜色的客户提供不同的配送选项。

二、模型建立与算法概述

2.1 弧流模型

论文构建了一个改进的弧流模型（arc-flow formulation） ，在原有三指标模型的基础上引入了二指标形式，以减少模型对称性。该模型以总成本最小化为目标，兼顾车辆固定成本与行驶成本，与后续集合划分模型保持一致。

决策变量定义：

•  ：若车辆经过弧 ，则取 1，否则为 0；
•  ：若节点  被访问，则取 1，否则为 0；
•  ：车辆在节点  的服务开始时间；
•  ：车辆在节点  服务后的载重。

目标函数：

其中， 为车辆固定成本， 为弧  的行驶成本。前一项代表启用车辆的固定支出，后一项表示总行驶成本。

约束条件包括：

• 流守恒约束：保证每个节点的进入与离开次数相等；
• 车辆启用约束：出发与返回仓库的车辆数量一致；
• 时间窗一致性约束与车辆容量约束；
• 每个请求仅选择一个配送选项；
• 共享提货点容量与服务水平约束 。

该弧流模型主要用于 RFIH（弛松-修复插入启发式） 的初始解构造，为后续的邻域搜索与列生成模块提供高质量起点。

2.2 集合划分模型与列生成

由于直接求解弧流模型规模巨大，作者将问题转换为集合划分模型（set‑partitioning formulation） 。先预生成若干可行路线（列），再选择其中一组组合覆盖所有需求。列生成的子问题采用资源约束最短路（RCSP） 求解，利用动态规划在分层网络中搜索，图中的节点代表不同服务段，弧表示服务决策。下面的分层网络示意图即为动态规划状态网络：

2.3 弛松‑修复插入法 (RFIH)

为快速构造初始解，作者设计了Relax‑and‑Fix Insertion Heuristic (RFIH) 。该方法先忽略部分时间窗与服务水平约束，获得部分可行解，再逐步修复违约的请求，插入到适当路线中。RFIH 能快速得到满足基本约束的高质量初始解，是后续邻域搜索的重要基础。

2.4 邻域搜索与变邻搜索 (VND)

构造初始解后，作者利用可行与不可行邻域搜索结合变邻搜索 (Variable Neighborhood Descent, VND) 改进解：

• 拆分/合并（split/merge）：重新分配请求至不同路线。
• 交换（swap）：交换两条路线中的若干请求段。
• 移位（insert）：将请求插入另一条路线。
• 交叉（cross-exchange）：交换两条路线连续的片段。
• 两点交换（2‑opt）：反转路径中的局部顺序。

为跳出局部最优，VND 允许一定的不可行解探索，并设置惩罚系数逐步调节。此外，作者还提出基于“观察2”的段评估加速剪枝。下图示例说明了某些不必要的路段可被快速排除。

三、算法实现与创新点

作者提出的邻域混合启发式算法（Neighborhood‑based Matheuristic, NMH） 集成了上述模块，整体流程如下：

• 步骤1：使用 RFIH 快速构造一个满足基本约束的初始解。
• 步骤2：在初始解基础上，采用 VND 深入搜索邻域，通过多种局部操作改进路径。
• 步骤3：对产生的可行路线进行列生成，并求解集合划分模型，以进一步优化成本。
• 步骤4：通过动态扰动与重启策略管理路线池（如下图所示），避免陷入局部最优。

创新点主要体现在：

• 双重视角搜索：算法同时从原问题（生成更优路线）和对偶问题（改进下界）两方面优化，综合利用列生成与局部搜索。
• 段‑基评估与主导规则：基于路径片段的支配检查，加快了可行性判断，减少无效搜索。
• 带服务水平约束的插入法：RFIH 在构造初解时融入服务水平权重，对不同选项进行优先排序。

四、实验设计与数值结果

作者将算法与最新文献中的分支‑定价‑剪枝（BPC）及大型邻域搜索（LNS）算法进行对比。实验实例来源于 2021 年 Dumez 等和 Tilk 等的 VRPDO benchmark，包括 25、50、100、200 和 400 个请求的实例。评价指标为最优解 (OPT)、最优已知解 (BKS)、使用车辆数及行驶成本。

4.1 与 BPC 比较（小规模）

在 25 和 50 个请求的实例中，NMH 在短时间内（25 请求时 30s 内）取得了 114 个最佳已知解（BKS）中的 114 个，其中 38 个为新的 BKS。特别是在含更多选项的 U 组中，NMH 降低了平均行驶成本 3.1%，并成功减少使用车辆数。相较于 BPC，NMH 能在很短时间内获得接近最优的可行解，验证了算法的正确性与高效性。

4.2 与 LNS 比较（中大规模）

针对 50、100、200、400 个请求的中大规模实例，NMH 使用固定车辆成本 ( f=100{,}000 )（模拟层级目标），运行时间由 30s 到 2000s 不等。实验发现 NMH 在 120 个实例中的 85 个获得了新的 BKS（更新率 53.33%）。在 200 请求组，NMH 平均减少行驶成本 6.35%，部分实例甚至达到 10% 的成本降低。虽然使用车辆数略有增加（最多增加 0.1 辆），但总成本明显下降，证明列生成与变邻搜索的结合能够改进大型问题的解质。

五、案例研究：第三方物流公司应用

5.1 实例描述与数据

作者以中国某三方物流公司一日订单为基础构建真实实例，每个订单有 1–50 件货物并可选择多达 3 个配送选项，要求满足 service level 约束 β₀=80%，β₁=90%。根据区域划分形成四个实例 R1–R4。表1 列出了请求数、地点数、选项数、车辆数及 SDL 数量。R1 的订单最多，车辆12台；R3、R4 则较小

表1 实例的详细信息（取自Table 5）

实例的地理布局如图所示，红色三角表示仓库，黑色点是 SDL，彩色点表示不同区域的 IDL。

运输距离采用实际经纬度计算，公式如下，其中 ϵ 和 ι 分别表示纬度和经度，κ=1.5 为折算系数：

每辆车容量 ，服务时限为 13 小时。SDL 只能服务 5–7 个订单，服务时间 2 分钟，IDL 服务时间 4 分钟。

5.2 优化结果：与人工规划对比

为了验证算法在真实环境中的可行性，作者进一步进行了案例研究。公司当前采用人工经验进行规划（MP）。表2 比较了 MP 与 NMH 的总成本 、行驶成本  及车辆数 ：

• 总成本下降显著： NMH 在平均和最佳情况下比 MP 分别节约 19.65% 和 20.10% 的总成本，R1 实例节约超过 32%。
• 车辆使用减少： 平均车辆数由 8 辆下降到 6.8 辆，行驶成本降低约 22%。
• 服务水平略有下降但可接受： MP 的首选选项占比为 82.89%，NMH 最佳解为 80.29%；然而 SDL 容量利用率由 66.27% 提高至 70.54%，表明 NMH 在成本和服务间实现更优平衡。

进一步观察发现，仓库位于配送区域内的 R1 成本明显低于仓库位于区域外的 R2，说明仓库选址对成本影响极大。地理稀疏的区域（如 R3）倾向使用更多 SDL，以降低长距离行驶成本。

5.3 初始解构造方法对比

表3 比较了三种初解构造方法：RFIH、Greedy（贪婪随机插入）和 Regret（后悔插入）。RFIH 在四个实例中平均总成本最低（2283.13），比 Greedy 和 Regret 分别降低 9.15% 和 6.28%。特别是难度最大的 R1 实例，RFIH 总成本 2365.47，比 Greedy 减少 16.38%，说明合理选择配送选项比复杂插入策略更重要。

5.4 算法组件贡献

为了评估各模块的重要性，作者将 NMH 删减为两种变体：不使用列生成与集合划分 (NMH‑1) 和仅不使用列生成 (NMH‑2)。表4 显示完整的 NMH 在所有实例上表现最佳，而 NMH‑1 的最佳成本平均高出 1.59%。NMH‑2 略好，但仍比完全版高 0.89%。这表明列生成可以丰富路线池，帮助跳出局部最优。

5.5 参数敏感性分析

RFIH 中的随机参数 ρ 决定候选插入数。表5 和图6 显示，当 ρ 从 0.15 减小到 0.05 时，算法运行时间显著增加（平均从 7 s 增加至 21.6 s），而总成本变化不大。因此选择较小的 ρ 并不划算。

表6 探索了服务水平参数 β₀、β₁（60–100%）。结果表明，服务水平要求每提高一个档次，总成本均显著增加。例如，当 β₀=60% 时，R1 的平均总成本为 1761.44；将 β₁ 从 70% 提高到 100% 时成本增至 1828.48，且 SDL 利用率下降。总体而言，车辆数对 β 参数不敏感，但行驶成本和 SDL 利用率显著受到影响。

六、结论与管理启示

本文针对 VRPDO 提出了一种邻域混合启发式算法 (NMH) ，通过弛松‑修复插入法构建高质量初解，再结合多邻域搜索、列生成与集合划分模型，从原问题和对偶问题双视角改进解。算法在基准实例上获得大量新的最优已知解，尤其在含多配送选项的复杂实例中显著降低成本。在实际三方物流案例中，NMH 相比人工规划节省约 20% 总成本，减少车辆使用，同时保持较高服务水平。

对企业实践的启示包括：

• 充分利用共享提货点降低行驶成本。 稀疏区域可适当多用 SDL，提高容量利用率。
• 服务水平与成本存在明显权衡。 提升 β₀、β₁ 会显著增加路线成本，企业需结合客户满意度和成本预算灵活设定。
• 仓库选址影响巨大。 仓库设在配送区域内部可减少空驶距离，从而节省总成本。
• 自动化规划算法的重要性。 RFIH 可在几十秒内构建可行解，应对订单取消等突发情况；列生成和 VND 的结合能有效跳出局部最优，适用于大规模实例。

该算法的框架不仅适用于 VRPDO，还可扩展到废物回收、众包配送和医疗路由等含多选项的车辆路径问题，为复杂末端配送提供科学决策工具。

文章须知 

推文编辑：单子叶 

责任编辑：弓仪长

原文链接：https://doi.org/10.1016/j.tre.2025.104366