链上镖师 / Chain Biaoshi
TRB|时间窗与操作同步车辆路径：列生成分解与有效不等式
把跨线路任务同步留在主问题中处理，用冲突路径和SPR割平面压缩精确算法搜索空间
这篇论文面向带时间窗和操作同步的车辆路径问题，提出一种新的Dantzig-Wolfe分解、冲突路径识别和两类SPR有效不等式，目标是在精确求解中降低同步约束带来的定价与搜索压力。
- 01：问题来自集装箱拖运、居家护理、电力维修等场景，多个任务可能分布在不同车辆线路上，开始时间还要满足先后间隔。
- 02：核心算法把路径顺序作为列，把具体服务时间变量留在主问题中，从而避免传统分解在定价子问题中出现线性时间成本。
- 03：实验基于Solomon R1算例扩展生成，最大测试到25个任务和15条时间先后约束，并比较SVF、SPF以及加入SPR割平面的分支定价算法。
研究背景
车辆路径问题通常关注订单访问顺序、车辆数量和总成本。加入时间窗后，车辆还要在每个客户允许的时间段内服务；加入操作同步后，一个任务的可行开始时间会受到另一条线路上任务完成时间的影响，路线之间出现直接联动。
论文给出的典型场景包括集装箱拖运、居家护理和电力线路维修。出口箱运输中，重箱送达托运人之后，空箱回收任务才能启动；护理场景中，给药、进餐或双人协助任务需要满足时间间隔；电力维修中，线路两端变电站操作也需要按安全顺序执行。
这类问题的难点在于，单条线路内部的时间安排已经不足以判断可行性；当相互依赖的任务被分配给不同车辆时，任意一条线路的调整都可能改变其他线路的可行时间窗口。
核心问题
既有精确算法常用分支定价框架处理同步车辆路径问题。传统Dantzig-Wolfe分解会把服务开始时间作为列参数带入主问题，定价子问题随之出现与服务时间线性相关的节点成本，标签算法的资源扩展结构变得更复杂。
另一类做法通过时间窗分支处理同步约束，可以避免定价中的线性时间成本，可是需要时间离散化。时间粒度越细，计算量越大；时间粒度越粗，关键的同步间隔可能被掩盖，应用范围受到限制。
01目标一：构造不含线性时间成本的定价子问题。
02目标二：只用线路访问顺序识别部分同步不可行组合。
03目标三：用有效不等式强化主问题下界，减少分支定价搜索。
Fig. 1 展示两条和三条车辆路径之间的环形同步依赖。图中闭合依赖链如果累积时间为正，就构成冲突环，对应的路径组合不能同时进入可行整数解。来源：Fig. 1
方法框架
论文比较了两种分解思路。SPF把线路顺序和服务开始时间一起放进列，主问题可以直接检查同步约束，定价子问题需要处理服务时间带来的线性节点成本。SVF只让列表示访问顺序，服务开始时间作为主问题变量决定，定价子问题保持标准车辆路径定价结构。
1先用路径列描述车辆访问顺序，每条路径仍从仓库出发并回到仓库。
2再在SVF主问题中引入服务开始时间、完成时间和调整变量，统一处理跨路径同步约束。
3然后用列生成与行生成补充必要路径和约束，避免一次性展开全部主问题行。
4最后加入冲突路径约束和SPR有效不等式，收紧整数解空间和线性松弛。
冲突路径集是论文的关键补强。若若干条路径的先后依赖能构成正长度闭环，那么这些路径在任何可行排程中不能同时被选择。该判断只依赖访问顺序和先后关系，不需要先求出完整服务时间表。
Table 5 对SPR I、SPR II和组合SPR进行拆分比较，用来观察两类subset-precedence-row不等式各自对下界、节点数和求解时间的贡献。来源：Table 5
Table A.1 给出SPR I-DECISION复杂度证明中的矩阵构造示意，支撑论文关于分离问题NP完全性的理论说明。来源：Table A.1
案例或实验设置
实验没有沿用现成同步VRPTW基准集，而是在Solomon VRPTW数据集上生成时间先后约束。作者选择R1类算例，因为初步测试显示C1和RC1等聚类数据在小规模下容易产生单车解，较难体现多车同步带来的跨线路协调压力。
时间先后约束通过随机选择两个节点生成，间隔上限不超过规划期长度的三分之二，并满足早到时间加间隔小于后继节点最晚时间的可行性条件。算例记为R-N-M，分别对应原始Solomon实例、任务数和时间先后约束数量。
Table 1 覆盖从5个任务2条先后约束到12个任务8条先后约束的递增规模测试，比较SVF与SPF分支定价算法的下界、目标值、Gap、节点数和运行时间。来源：Table 1
最大测试规模
25个任务、15条先后约束
单实例时间上限
7200秒
结果分析
在递增规模测试中，SVF的平均运行时间优势从中等规模开始变得明显。以8个任务、4条先后约束的平均结果为例，SVF平均用时13.8秒，SPF平均用时102.3秒；到10个任务、6条先后约束时，SVF平均28.5秒，SPF平均301.2秒。
Table 2 将算例固定在15规模后比较SVF与SPF，展示同步约束变复杂时两种分解方式在Gap、搜索节点和超时控制上的差异。来源：Table 2
在25个任务、15条先后约束的固定规模测试中，SPF列下的结果大量显示7200秒时间上限和100.0 Gap。SVF也会遇到大Gap和超时，可是仍能保留下界和部分可行目标值，说明把服务时间留给主问题处理在大规模同步情境中更稳。
Table 3 展示25规模固定算例的计算表现。多行SPF结果达到7200秒上限并显示100.0 Gap，SVF在若干实例中仍给出可行目标值和下界。来源：Table 3
Table 4 比较加入SPR有效不等式前后的分支定价表现，用于观察割平面对搜索节点、下界质量和求解时间的改进。来源：Table 4
管理启示
对需要同步作业的车队调度场景，建模时只描述订单访问顺序还不够。论文说明，跨车辆任务之间的先后间隔会制造线路组合层面的不可行性，调度系统应当把这些同步关系作为排程约束进入精确求解流程。
算法层面的启示是，服务时间变量放在主问题中统一协调，可以减轻定价子问题压力；同时，冲突路径和SPR割平面能提前排除部分无效组合。对于任务数上升、同步关系增多的算例，这类结构化强化比直接扩展传统分解更有可操作性。
Table 6 在25规模算例上继续比较B&P与B&P&SPR，补充有效不等式在大规模同步车辆路径问题中的上下界和求解时间表现。来源：Table 6
这篇论文的价值在于给同步车辆路径问题提供了一条更适合精确算法的建模路线：路径顺序由列生成处理，跨路径时间同步由主问题协调，冲突结构和有效不等式负责收紧搜索空间。
论文：Dantzig-Wolfe decomposition and valid inequalities for the vehicle routing problem with time windows and operation synchronization
作者：Naiyu Wang，Canrong Zhang
期刊：Transportation Research Part B
链上镖师、先卜交通、先卜运筹通用论文ID
保存此推文 ID，可在粉丝群内获取相关材料，未来更多功能敬请期待
先卜科技团队：常文婕、张巧巧、王一航、夏子帆、张晓乐、祁园园、张仁义
