论文摘要

本文提出周期车辆路径问题的多日行程扩展（PVRPMDT），融合经典周期车辆路径问题与车辆路径–司机排班问题，面向工业气体等区域配送场景。该问题允许客户从多个可行服务日程中选择其一，车辆既需按周期完成配送，又可执行跨越多个工作日的长途行程，并在途中进行夜间休息以满足工时法规。研究目标是在规划期内为异质车队联合规划日内与跨日路径及夜间停留安排，在满足容量、单日与累计行驶时长约束的前提下最小化总成本。

为此，文章构建了基于集合划分的数学模型，并提出适用于多日行程的分支–定价–割（BPC）算法。方法通过引入时间移动函数刻画跨日路径与出发日之间的关系，在定价子问题中增加多日资源以生成合规路线，并配合路径扩展规则、变量固定、路径枚举及针对跨日特性的强化割不等式提升求解效率。同时，通过将客户拆分为多个节点，自然支持服务选择属性。数值实验表明，该方法可在中等规模实例上高效获得最优解，并在工业案例中显著降低配送成本、提升车辆利用率，为长短途融合的周期配送规划提供了一种有效的精确求解框架。

一、研究背景与问题定位

1.1 VRP 与周期配送的研究现状

车辆路径问题（VRP）旨在设计符合容量和业务约束的最低成本路线，是供应链优化的重要模型。经典VRP主要针对单日配送，在食品、报刊和电动车配送等领域已经得到广泛应用。然而在废物收集、医疗和工业气体配送等领域，配送活动跨越多个日子，客户需要按照不同的周期被访问。此类场景催生了周期车辆路径问题（PVRP），既要选择客户的访问日程，又需规划每天的路线。

1.2 长途多日配送与工时法规

在长途运输中，车辆往往无法在单个工作日内完成送达，驾驶员需要在途中休息并遵守严格的工时规定。为此，研究界提出了车辆路径和司机排班问题（VRTDSP），在单一连贯周期内规划多日路线与休息安排，以满足工时法规。

1.3 问题定位与挑战

PVRP强调周期性，VRTDSP强调多日连贯性，二者很少在同一框架下结合。本文提出的PVRPMDT旨在融合两者：为每个客户选择合适的访问日程，并允许部分车辆跨越多个工作日行驶，且在途中夜间休息。这一新问题来源于工业气体配送场景，订单量往往不足一车，需要多点合并，且长途车队与短途配送共用。与经典PVRP相比，PVRPMDT需同时优化日内路线和跨日路线，既要满足周期性拜访，又要满足工时法规，建模和求解难度明显提升。

下面两幅图形直观展示了此问题的时限约束和多日路径特征。图中车辆每天的行驶时间  需不超过日限 ，多日行程的累积时长也必须小于总限 ；同时，跨日配送中驾驶员需要在途中休息，且第二天到达客户现场再开始工作。

二、模型构建与方法框架

2.1 变量定义与假设

• 时间与车队：设规划期离散为  天，车队类别集合为 。函数  表示第  日段所属的日编号， 表示从出发日数前推当前所在的日编号。
• 路径集合：对每个起始日  与车辆类型 ，定义路径集合 ，其中每条路径的长度（跨日天数）为 ，并定义二元参数  指示路径是否延伸至第  日段。参数  表示路径  在弧  上的经过次数。
• 客户与日程：每个客户  提供若干访问日程 ，其中二元参数  表示日程  是否要求在第  日段访问客户。
• 决策变量：二元变量  指示是否选择路径 ，二元变量  指示是否为客户  选择日程 。

2.2 目标函数与约束

模型追求在规划期内最小化总路线费用（包括行驶成本和夜间停车成本）。其核心形式如下：

其中  为路径  的综合成本（行驶费用加夜宿成本）。

约束主要包括：

1. 日程选择约束：每个客户必须选择一个日程，确保客户的访问频率与其给定的备选日程一致。

2. 日程与路径匹配约束：在每一天段，路径访问客户的次数必须与所选日程要求相符，保证每天选定的路线确实覆盖了需要访问的客户。

3. 车队容量约束：任一车辆类型  在某日段  的使用次数不能超过可用数量 ，限制车队同时出车数量。

此外，所有  和  均为二元变量。通过这些约束，模型既能确保客户日程的独立选择，又能在行程设计中反映车辆跨日能力、作业时间和车队规模限制。

2.3 模型的扩展与改进

为处理多日行程，作者引入了时间移动函数 来跟踪车辆跨日状态。相较于经典PVRP，该模型允许路径连续跨越多个日段，且使用  描述路径在各日段的覆盖范围。此外，为支持客户的服务选择，将每个客户拆分为若干复制节点，并在约束 (2) 中对这些节点进行总和约束，使得每个客户只选一条日程。

三、算法设计与实现

3.1 分支–定价–割框架及其改进

为求解上述大规模整数模型，作者采用了分支–定价–割（BPC）算法。其基本流程为：在松弛主问题中采用列生成生成新路线，同时添加强不等式改善松弛界，再通过分支法确保整数性。针对 PVRPMDT，文章作出了五方面重要改进：

• 模型扩展：将原有集合划分模型拓展至可描述多日行程的路径。
• 定价子问题：在动态规划求解过程中加入两类新资源，以同时记录载重和连续行驶时长，生成符合工时规则的多日路线。
• 路径扩展规则：调整前向和后向扩展协议，使得在跨日扩展时合理更新驾驶员日内和累计行驶时间。
• 加速技术适配：改造路径枚举和变量固定策略，使其适用于跨日情形。
• 切割平面：根据多日特性提出改良的容量不等式和有限弧记忆子集割，使松弛解更紧密。

3.2 价格子问题与标签算法

定价子问题通过求解带资源约束的最短路问题（SPPRC）生成新路径。作者采用动态规划标签算法，并针对多日行程作如下改动：

• 标签定义：每个部分路径用标签记录前驱、减成本、终止节点、载重、当前日段、累计行驶时间、当日行驶时间以及禁止访问的顶点集合。
• 兼容日段：根据车辆在前一日段的状态，动态确定可延伸到客户的日段集合，如果集合为空则延伸不可行。
• 资源更新：对于在同一天段内延伸、跨到下一日段且及时到达、跨日且需要等待的三种情况，分别给出更新累计和日内行驶时间的规则。
• 禁忌集合更新：在新一日段开始时清空禁忌集合，使客户可以在不同日段重复访问，从而生成多日路线。
• 双向扩展：在前向标签基础上补充后向标签，便于在变量固定时快速计算可行路径。

下图展示了标签算法中路线元素约束的关键思想：每个日段内禁止重复访问节点，但跨日延伸时可以重新访问，从而兼顾行程连贯性与元素性要求。

下图为部分路径延伸的示意，展示了在扩展到下一节点时如何更新禁忌集合和行驶时间。

3.3 加速策略与切割平面

为提升求解效率，文章引入多种加速策略：

• 变量固定：根据当前松弛解的边成本阈值，对成本过大的弧提前排除，从而缩减搜索空间。
• 路径枚举：当松弛解与最好整数解的差距较小或资源消耗较低时，预先生成所有可能的短路径并加入主问题，以避免反复求解定价子问题。
• 强化不等式：使用圆整容量不等式（RCI）作为鲁棒切割平面，以及有限弧记忆的子集行割（lm‑SRC）作为非鲁棒切割平面，其中前者可以直接通过调整边成本融入定价子问题。
• 分支策略：优先对日程变量  进行分支，其次是车辆使用数量，再是边变量，确保分支过程快速收敛。

作者指出，如果关闭路径枚举或变量固定技术，算法求解到最优解的实例数将显著下降，这些技巧对提高可解规模至关重要。

3.4 服务选择的处理

在具有服务选择属性的实例中，每个客户的访问量取决于选定的访问频率。为处理这一情况，作者将每个客户拆分为多个复制节点，每个节点对应固定的单次配送量。约束 (2) 随之改写为所有复制节点只选择其中一个。这种建模方式既保留了多日行程的路径结构，又能灵活选择服务频率。

四、实验设计与结果分析

4.1 基准实例生成

为评估算法性能，作者在经典PVRP基准实例基础上构造了PVRPMDT实例：设置不同规模的客户数量（12、16、20、24、28、32）以及4天或6天的规划期，并定义每类车辆的数量、容量、日行驶限  和累计限 。此外，将长途车辆的夜宿成本设定为不同倍数以分析其对模型性能的影响。

4.2 求解性能概述

表 4 统计了算法在各基准实例上的表现。主要发现包括：

• 当客户数不超过 20 个时，算法几乎能在几百秒内获得最优解；对于 20 个客户、4 日规划期的 24 个实例，平均求解时间约 353 秒。
• 随着客户数增加到 24 或以上，问题难度急剧上升。20 客户实例中的 22/24 个在六分钟内关闭松弛间隙，但 24 客户仅有 10/24 个实例在 1800 秒内达最优。
• 在解的结构上，日内行程约占 43%，两日行程约 36%，三日行程约 21%，夜宿成本约占总成本的 16–20%。
• 路径枚举与变量固定对效率至关重要，关闭它们会使可解实例数减少一半以上。

4.3 参数敏感性分析

作者进一步分析夜宿成本对求解难度的影响。结果显示，当夜宿成本较低时，多日路线被过度采用，导致模型出现更高的对称性和退化现象，从而难以求解；随着夜宿成本增加，问题可解性显著提升。说明在实际应用中合理设定夜宿费用不仅反映成本，还可提高优化模型的收敛速度。

五、工业案例研究与讨论

5.1 数据概况

作者应用该方法分析了某工业气体企业在欧洲的一个配送中心，该中心需为 12 个客户补货，车队由三辆卡车组成：一辆长途车 A（容量 312 单位，最多 2 日行程），两辆长途车 B1、B2（容量 282 单位，可走 3 日行程）。车辆的日行驶限为 ，累计限为 。规划期设定为 6 天，客户的访问频率可选每天、隔天、三天一次或每周一次，分别对应 1、2、3、6 种不同的日程组合。客户的周需求量分别为 204、72、504、120、234、132、192、6、12、174、396、24 单位，按频率均分到各次访问。夜宿成本设定为每晚 175 单位。

5.2 优化结果与分析

算法在约 116 秒内得到了最优解，目标值为 4 885.9，其中路线成本占 82.1%，夜宿成本占 17.9%，共安排 4 条日内路线、3 条两日路线和 1 条三日路线。表 9 进一步展示各车辆的利用情况：车辆 A 执行 1 日路线 2 次、2 日路线 1 次；B1 执行 1 日、2 日、3 日路线各 1 次；B2 执行 1 日和 2 日路线各 1 次，以及 1 条 3 日路线。

下图展示了该三日路线的具体行程：第一天从仓库出发，经客户 9 送达并休息；第二天经过客户 11 和客户 2；第三天早上再次启程并在当日返回仓库。绿色、橙色和蓝色分别表示行程的三个日段。

案例还显示，大多数客户最终被分配到访问频率最低的日程，这与客户距离仓库较远、夜宿成本较低的特征一致。与实际操作中长途与短途分开规划相比，综合优化能更好地利用长途车辆的闲置时间，减少总行驶成本与夜宿次数。

5.3 启示与讨论

• 混合车队协同：通过统一规划长途和短途车辆，既能充分发挥大车的跨日能力，又能在需求较小的日子让大车承担单日任务，从而整体降低成本。
• 服务选择重要性：在需求随访问频率改变的情况下，允许算法自主选择频率能显著提升效率；案例中大部分客户选择低频访问，说明频率优化对成本有重要影响。
• 夜宿成本的作用：夜宿成本不仅影响成本分布，还影响模型退化程度。适当提高夜宿费用有助于解出更优且更易求解的方案。

六、结论与贡献

本文针对现实长途配送中周期性与跨日性并存的需求，提出了新的周期车辆路径问题多日行程扩展（PVRPMDT）。研究的主要贡献包括：

• 问题正式化与场景分析：首次将 PVRP 与 VRTDSP 两类问题融合，建立多日跨日配送的决策框架，覆盖工业气体等区域配送业务。
• 模型创新：提出带时间移动函数的集合划分模型，引入跨日路径的持续时间和访问模式，支持服务选择等高级需求。
• 算法改进：在经典 BPC 框架上开发出适用于多日行程的定价子问题与标签算法，设计了针对跨日特性的扩展规则、变量固定、路径枚举和强切割不等式。
• 计算验证：通过大量基准实例和一项工业案例，验证了算法的有效性和效率，能够在中等规模实例上快速得到最优解。
• 实践启示：指出夜宿成本、服务频率选择和加速技术对求解质量与效率的深刻影响，为实际物流调度提供了具体建议。

未来的研究可考虑开发近似算法以处理更大规模或实时动态需求，并探索与碳排放约束、混合能源车辆调度等新型因素的结合，为绿色智能物流提供更完善的决策支持。