时变路径场景下碳排放优化：基于双向支配算法的时变碳排放最小化模型
一、研究背景与问题提出
1.1 绿色车辆路径问题与时间依赖性
运输业产生的碳排放占全球温室气体排放的重要比例，如何通过优化车辆路径减少碳排放成为运筹学和交通运输领域的重要课题。 传统的车辆路径问题（VRP）假设车辆速度不随时间变化，但在实际城市配送与长途运输中，车辆速度常受道路拥堵或政策限制而呈现时间依赖性。当忽略车辆速度随时间的变化和碳排放的时间依赖性时，可能导致次优方案。
为应对这一挑战，文献提出了时间依赖车辆路径问题（TDVRP）及其绿色扩展，例如考虑不同时间段车辆速度和油耗的时间依赖绿色车辆路径问题（TDGVRP）。 当客户设有服务时间窗且同时优化车辆出发时刻、行驶路径与碳排放时，就得到本文研究的时间依赖绿色车辆路径问题带时间窗（TDGVRPTW）。
1.2 问题定义与挑战
给定一个有向图 ，节点集合 包含出发和返回的仓库（ 与 ）以及客户集合 。弧集 表示各节点间的行驶路线，且每个客户 有需求量和服务时间窗 。 目标是在满足车辆载重与客户时间窗约束的情况下，为所有客户设计若干条路线（每条路线以仓库出发并返回），同时最小化总碳排放。
由于车辆速度在不同时间段具有不同取值（例如速度在 为 ，在 为 等等），因此弧的旅行时间与碳排放均依赖于出发时刻。这要求模型不仅决策访问顺序，还需决策每条路线中各节点的出发时刻，使问题较传统VRPTW更具挑战。
下图展示了车辆速度剖面例子（取自Fig.1），规划地平线 被分为三个时间区间，在不同区间车辆速度不同。
二、模型与方法
2.1 模型与理论创新
论文的核心创新体现在以下三个方面：
提出“后向非支配时间依赖弧（Backward Non-Dominated Time-Dependent, BNTD）”概念对传统的前向非支配弧（FNTD）进行扩展，引入“到达时刻主导性”的判据，构建后向非支配弧，从而在路径生成阶段有效缩减搜索空间。
提出三类最优路径结构
前向最优路径（Forward Optimal Route） 后向最优路径（Backward Optimal Route） 拼接最优路径（Patchwork Optimal Route）前后向路径可通过时间调整（Time Adjustment）过程互相转化，拼接路径则结合两者优点，实现碳排放最小与时间可行的平衡。 提出时间调整（Time Adjustment）与双向标记算法（Bidirectional Labeling）
将时间调整推迟到路径生成的最终阶段，避免在标签扩展时产生组合爆炸； 通过双向标签（Bidirectional Labeling）在中点拼接前后向扩展路径，大幅减少需要扩展的弧数量，提高计算效率。
该设计首次实现了“前向–后向–拼接路径”的统一理论框架，为TDGVRPTW提供了系统化的精确求解思路。
2.2 算法框架：BPC求解流程
BPC算法框架包含以下关键组成部分：
主问题（Master Problem）基于集合分割模型构建，以最小化总碳排放为目标。
定价子问题（Pricing Problem）表述为带资源约束的最短路径问题（ESPPRC），通过生成负Reduced Cost的列变量扩展路径集。
有效不等式（Valid Inequalities）引入 lm-SRCs（有限记忆子集行约束） 以加强线性松弛，提高列生成的收敛速度。
加速策略（Acceleration Strategies）
ng-route 松弛（ng-route relaxation）； bucket graph 桶图结构以优化弧存储与检索； 分支策略基于弧变量以减少节点数量。
该框架通过在列生成基础上融合分支与割平面思想，保证了解的最优性与可扩展性，是TDGVRPTW的核心求解机制。
2.3 时间扩展网络与旅行时间计算
在时间扩展网络中，每个物理节点 在不同出发时间映射为不同的“时点”。对弧，车辆从 在时间 出发，其旅行时间 计算如下：
其中 是满足 的区间索引， 是弧上速度变化的次数， 为第 个区间的速度， 为该区间内行驶的路程，且有 。
同理，以到达时刻 计算时：
其中 满足 ，并有 。
2.4 碳排放函数
根据 Bektaş & Laporte (2011) 及 Franceschetti et al. (2013)，车辆在弧 上的碳排放不仅与行驶距离相关，还与出发时刻（即车辆速度水平） 密切相关。 当出发时刻为 时，碳排放量定义为：
其中： 为燃油转化为碳排放的换算系数，：车辆-路段综合能耗参数， ：车辆自重，：与空气阻力和滚动阻力相关的修正系数。
当以到达时刻 作为自变量时，碳排放函数可等价表示为：
两者满足：
这意味着，无论从出发时刻还是到达时刻进行计算，所得碳排放结果完全一致。 由于速度在规划时域 上呈分段变化（高峰期速度下降、低谷期速度上升），碳排放函数在时间维度上表现出非线性波动特征。
2.5 非支配TD弧与最优时序路径
为减少时间扩展网络规模，论文引入非支配时间依赖弧（TD arc）的概念，仅保留在碳排放与时间上最优的弧。
FNTD弧（前向非支配弧）：
以出发时刻为基准。若存在两条弧 与 ，
且满足 、（至少一个严格不等），
则后者被前者支配。保留下来的弧即为前向非支配弧（FNTD）。BNTD弧（后向非支配弧）：
以到达时刻为基准。若存在两条弧 与 ，
且 、，
则后者被支配。保留下来的即为后向非支配弧（BNTD）。Patchwork路径：
由前向与后向最优部分路径拼接形成整体最优时序路径，保证碳排放最小与时间可行。
最终构造三类路径集合：前向最优 、后向最优 ，拼接形成补丁式最优路径 。
2.6 Set-partitioning模型与分支定价割算法
以最优路径为列变量构建集合分割模型：
其中 为路线 的碳排放成本。
为改进列生成（CG）性能，引入有限记忆子集行列剪枝约束（lm-SRC）：
化减成本：
考虑lm-SRC调整后：
其中 与 为对偶变量。
2.7 时间调整算法与双向标签
为生成最优路径，需在时间扩展网络上求解带资源约束的最短路径（ESPPRC）。论文提出三种标签设定算法：
前向标签算法 (BPC-F) ：使用FNTD弧，适用于碳排放先升后降。 后向标签算法 (BPC-B) ：使用BNTD弧，适用于碳排放先降后升。 双向标签算法 (BPC-BD) ：结合两者，在中间拼接补丁路径。
下图展示了时间调整与双向标签的过程：
图4展示了后向与补丁式路径的时间调整示意，说明如何在保持可行性的前提下，将后向路径调整为前向形式；
图5展示了不同速度曲线下三种标签算法（前向、后向、双向）的扩展差异， 双向标签能在中间拼接时显著减少需扩展的弧数，从而提高计算效率。
三、数值实验与结果分析
3.1 实例设置
以 Solomon 基准实例为基础，构建 25 与 50 客户两类测试集。
规划时域划分为三段速度区间，反映早高峰、平峰与晚高峰的速度变化。
算法运行时间上限设为 30 000 s。
3.2 结果分析
求解效果：在 25 客户实例中，BPC-BD 解得 14 个最优解；在 50 客户实例中解得 2 个，整体性能优于 BPC-F 与 BPC-B。 计算效率：BPC-BD 的运行时间明显低于 BPC-F，且在大规模实例上表现更稳定。 标签算法对比：BPC-F 与 BPC-B 分别对应碳排放随出发时刻先升后降与先降后升的情形；BPC-BD 结合两者，可在时域拼接中获得更低排放。 与启发式对比：BPC-BD 与 ALNS 算法在小规模实例上性能相近，而在部分中大型实例中可进一步降低碳排放。
图6展示了不同算法的最优率与平均碳排放对比，BPC-BD在多数实例中表现最优。
四、结论与管理启示
4.1 研究结论
提出后向非支配弧 (BNTD) 定义与判别定理； 构建补丁最优路径与时间调整算法； 设计双向标签的分支定价割算法框架； 验证算法效率与精度优于单向方法。
4.2 管理启示
出发时刻优化：适当提前或延迟可显著影响碳排放； 时间依赖弧筛选：识别非支配弧以减小规模； 标签策略选择：按碳排放趋势选取前/后/双向算法； 精确与启发式结合：小规模用精确法，大规模用近似法。
文章须知
推文编辑：单子叶
责任编辑：弓仪长
原文链接：https://doi.org/10.1016/j.trb.2025.103155
