链上镖师 / Chain Biaoshi
EJOR|带同时取送与时间窗的车辆路径：载荷相关成本下的精确路线优化
Branch-price-and-cut算法如何处理燃油、收费与车重共同影响的运输成本
论文将车辆载荷对燃油、轮胎磨损和按重量收费的影响纳入同时取送与时间窗车辆路径问题，并用定制化分支定价切割算法求解。
- 01：研究对象同时包含配送、取货、时间窗和载荷相关弧成本。
- 02：成本函数可采用连续或不连续的单调非递减形式。
- 03：算法通过资源扩展函数处理部分路径中尚未确定的载荷。
- 04：载荷影响因子升高会改变车辆数量、容量利用率、总距离和总成本。
- 05：异质车队与可升降轴车队的优劣取决于需求结构和低载荷行驶比例。
研究问题与文献定位：车辆路径成本随载荷变化
经典车辆路径模型通常把弧成本视为固定值。论文研究的VRPSDPTW-LDC同时考虑配送、取货、时间窗和载荷相关成本，使车辆经过同一条道路时的费用随车上载荷变化。该设定对应燃油消耗、轮胎磨损、按重量收费和限重通行等运营情境。
表1 载荷相关成本车辆路径问题变体与既有方法（来源：Table 1）。
论文的主要贡献是建立适用于多类载荷相关成本函数的统一描述，并将其嵌入完整的精确分支定价切割算法。
问题建模：把车上载荷转化为逐弧运输成本
车辆在弧(i,j)上的载荷由此前已取货的数量与后续仍需配送的数量共同决定。论文以车辆自重、载荷和最大总重定义运营重量，并要求成本函数对载荷严格为正且单调非递减。车辆容量、客户服务一次性约束和车队数量限制共同决定可行路线集合。
在线性连续成本情形下，弧成本按基础成本乘以载荷影响项计算，参数ρ表示满载相对于空载的成本增幅。模型也允许在收费阈值、限重通行或可升降轴动作处出现不连续点，从而表达现实运输规则中的跳跃成本。
图1 载荷相关成本函数示例（来源：Fig. 1）。
1路线状态：客户访问顺序、时间窗、配送量与取货量
2载荷传播：根据当前服务点更新弧上的实际载荷
3成本计算：将载荷代入对应弧的连续或不连续成本函数
4路线选择：在覆盖客户、容量和车队限制下最小化总成本
算法机制：分支定价切割与双向标签传播
算法以路线集合划分模型作为主问题，每个二进制变量表示是否选择一条可行路线。列生成定价子问题被转化为带资源约束的最短路问题，动态规划标签记录时间、访问次数、已取货量、最大载荷和依赖未知后续需求的约化成本函数。
阶段 1 前向标签：从起始仓库扩展，保留未知后续配送量对应的成本函数
阶段 2 后向标签：从终止仓库反向扩展，保留未知后续取货量对应的成本函数
阶段 3 双向合并：在中点合并前后标签并检查时间窗、容量与访问约束
阶段 4 加速求解：使用ng路径松弛、时间资源分桶和部分定价
阶段 5 整数化：加入有效不等式并采用分支规则获得整数路线方案
图2 RCDP203实例中标签成本函数片段数量分布（来源：Fig. 2）。
算法有效性与规模扩展：精确性保持下的计算代价
在56个基准实例上，基础BPC实现于1小时内证明最优的实例数为35个，载荷相关成本扩展后的LD实现为30个。平均计算时间由1724.5秒增至1866.0秒，整体增幅为8.2%，扩展后的通用算法仍保持可接受的性能。
表2 载荷相关BPC扩展对计算性能的影响（来源：Table 2）。
规模实验覆盖20、40、60、80和100个客户。20客户实例的平均求解时间约为0.1秒，100客户实例的总平均时间达到1582.5秒；R2与RC2等类别在规模扩大后出现更明显的计算压力，说明客户数量和实例结构共同影响精确求解难度。
表3 实例规模对BPC算法性能的影响（来源：Table 3）。
敏感性分析：载荷强度与成本不连续性如何改变求解
当载荷影响因子ρ从0%提高到120%时，56个实例中在时限内证明最优的实例数由30个增至47个，平均计算时间由1866.0秒降至972.6秒。结果显示，成本结构会影响路线排序、下界质量和搜索过程，求解难度不随参数单调增加。
表4 线性载荷相关成本函数中载荷影响因子ρ的作用（来源：Table 4）。
表5 成本函数不连续点位置对计算表现的影响（来源：Table 5）。
不连续点越多，标签约化成本函数的片段数通常越高。CFmulti在56个实例中平均产生14.9个标签函数片段，完整BPC平均时间为3009.4秒，仅有12个实例求得最优解；单一断点位于容量中部或高位时，计算表现相对稳定。
路线结构与车队配置：载荷成本进入运营决策
在RDP101的示例中，ρ升高会推动路线结构发生变化。论文用车辆数量、平均容量利用率、总距离和总成本四项指标观察这种变化，结果说明高载荷弧段的成本权重会影响车辆使用和客户组合安排。
图4 增加载荷影响因子ρ对四项解指标的影响（来源：Fig. 4）。
图3 RDP101实例在无约束与受限条件下的最优解（来源：Fig. 3）。
在37个完成比较的实例中，异质车队平均使用29.8辆车，可升降轴车队平均使用29.4辆车。可升降轴车队的总成本平均低0.3%，总距离平均低1.3%，优势集中于低载荷路段较多且车辆峰值容量需求可以分离的实例类别。
表6 异质车队与可升降轴车队的比较（来源：Table 6）。
适用范围与研究边界
该模型适用于同时取送、时间窗、容量约束和弧成本随载荷变化的车辆路径场景，也适合表达按重量收费、限重通行、燃油消耗和可升降轴等成本机制。算法要求成本函数保持正值与单调非递减，并依赖路线集合和资源扩展规则的可计算表示。
✓适用条件：载荷能够沿路线传播，并可映射到弧级成本函数。
✓参数条件：成本函数可为连续或不连续形式，车队可设置为同质或异质。
✓数据边界：实验基于Solomon系基准实例及论文设定的成本函数。
✓外推限制：论文明确提醒，真实成本结构和客户需求结构可能与实验设定存在差异。
✓验证范围：输入页面文本未报告真实运营数据上的部署验证。
车队配置需要结合载荷分布、峰值容量、低载荷行驶比例和重量收费规则评估，单一车队形式无法覆盖所有需求结构。
论文：Branch-price-and-cut for the vehicle routing problem with simultaneous delivery and pickup, time windows, and load-dependent cost
作者：Carolin Hasse，Stefan Irnich
期刊：European Journal of Operational Research
链上镖师、先卜交通、先卜运筹通用论文ID
保存此推文 ID，可在粉丝群内获取相关材料，未来更多功能敬请期待
先卜科技团队：常文婕、张巧巧、王一航、夏子帆、张晓乐、祁园园、张仁义
