一种用于带时间窗的时变绿色多仓库车辆路径问题的双阶段时空深度强化学习方法

《TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW》：A dual-phase spatio-temporal deep reinforcement learning approach for the time-dependent green multi-depot vehicle routing problem with time windows

　　

•研究时间依赖的绿色多仓库车辆路径问题（考虑时间窗）；•提出基于深度强化学习的两阶段时空策略框架；•数值结果表明所提模型与算法的有效性。

引言

全球贸易与城市化的增长加剧了交通运输领域的能源消耗与温室气体排放，其中公路货运占比显著（美国环境保护署，2024）。绿色车辆路径问题（Green Vehicle Routing Problem, GVRP）通过将能耗或环境相关目标纳入路径优化来应对这一挑战（Moghdani等人，2021）。然而，许多GVRP模型假设旅行速度恒定且车辆立即出发（Garside等人，2024）。在拥堵的城市网络中，路段通行时间与环境成本会随出发时间变化，因此此类假设存在局限性。忽略时间依赖交通状况可能导致路径方案在运营效率或环境效益上存在不足（Donati等人，2008）。时间依赖的绿色车辆路径问题（Time-Dependent Green Vehicle Routing Problem, TDGVRP）通过在路径评估中引入出发时间相关的交通状况，将时间因素纳入绿色路径决策的重要组成（Adamo等人，2024；Franceschetti等人，2013；Liu等人，2023b；Luo等人，2023）。

多仓库情境还需要统筹考虑仓库分配、空间路径构建与时间协调（Kabadurmus & Erdogan，2023；Schmidt等人，2023）。因此，本研究聚焦于时间依赖的绿色多仓库带时间窗车辆路径问题（Time-Dependent Green Multi-Depot Vehicle Routing Problem with Time Windows, TDGMDVRPTW）。这是一个出现在时间变化的城市物流系统中的NP-hard问题（Fan等人，2021；Kabadurmus & Erdogan，2023；Paul & Mahapatra，2026；Wang等人，2025）。该问题整合了多仓库调度、时间依赖交通状况、载荷相关的环境效应以及软时间窗约束，因而超越了传统的静态或单仓库路径模型。在车辆容量同质及客户时间窗为软约束的条件下，TDGMDVRPTW需要在运营效率、环境绩效与服务可靠性之间进行权衡。

现有方法往往将多仓库协调与交通动态和出发时间决策之间的交互加以简化或解耦。具体而言，时间依赖路径研究主要关注将出发时间相关的通行状况纳入路径评估，而多仓库扩展则侧重于仓库分配与车辆协调。将空间路径构建与主动出发时间调整作为耦合的运营决策进行联合优化，在时间依赖绿色物流中仍缺乏充分探索。本研究考虑到的TDGMDVRPTW中，出发时间决策反映了车辆在完成客户点服务后，选择何时进入下一路段的灵活性。这种灵活性体现了城市物流系统中常见的服务后等待操作，特别是在时间依赖的冷链与绿色配送中（Chen等人，2021；Guo等人，2022；Hou等人，2025；Liu等人，2025）。重要的是，所提出的等待机制仅在服务完成后调整出发时间，并不延迟客户服务。解决该问题需要建模这些时空依赖性，同时保证可行路径的构建。

时空耦合带来两大计算挑战。第一，时间变化的通行时间引入了顺序依赖，扩大了精确算法的状态空间（Andelmin & Bartolini，2017；Luo等人，2023）。第二，空间路径与时间调度存在内生的相互依赖。计算通行时长与排放代理成本需要指定出发时间，而评估出发决策的价值则需要定义空间轨迹。因此，路径评估具有非线性特征，迭代方法可能在空间调整后需反复更新时间轮廓，限制了大规模算例的计算效率（Adamo等人，2024；Chen等人，2026）。

深度强化学习（Deep Reinforcement Learning, DRL）通过从状态表征中直接学习路径策略，提供了一种替代人工设计启发式方法的数据驱动方案（Guan等人，2025；Kadyrov等人，2025；Kool等人，2019）。在交通与物流领域的近期研究中，通过引入图注意力机制、能耗感知表征与领域特定的运营特征，进一步增强了神经路径框架捕捉复杂空间结构与环境目标的能力。然而，许多端到端DRL方法或是在统一动作空间中同时表达路径与时间决策，或是完全省略了显式的时间调度决策（Mozhdehi等人，2025；Nazari等人，2018；Peng等人，2020）。尽管近期的绿色路径研究已将车辆能耗状态、排放相关信息及交通依赖特征纳入神经策略，但它们主要聚焦于能耗感知的路径构建，并未显式表达路径选择与出发时间调整之间的条件依赖关系。在TDGMDVRPTW中，等待决策的有效性取决于所选的下游路径。为避免某一路段拥堵而延迟出发，可能会增加后续路段的通行时长、排放代理成本或延迟惩罚。因此，单阶段框架必须隐式地推断这些时空依赖，难以明确区分空间路径决策与时间调整各自的影响。

为此，我们提出了双阶段时空策略框架（Dual-Phase Spatio-Temporal Policy, DPSTP），将空间路径与时间调度显式分解为两个顺序但条件耦合的决策。阶段一利用拥塞感知信息构建可行空间路径；阶段二则在给定所选下游节点与当前交通状况的条件下确定出发时间。不同于传统时间依赖车辆路径问题（TDVRP）方法主要基于预设出发假设评估时间依赖成本，也不同于在统一动作空间内隐式捕捉时空交互的神经路径模型，DPSTP通过路径条件化的时间策略显式建模路径选择与出发时间调整之间的顺序依赖。这种“先路径、后调度”的结构反映了时间决策对所生成空间轨迹的依赖性，并实现了主动规避不利交通时段。主要贡献总结如下：

1. 将TDGMDVRPTW形式化为事件驱动的半马尔可夫决策过程（Semi-Markov Decision Process, SMDP）。该形式化整合了多仓库协调、时间依赖通行动态、节点级等待与软时间窗约束。与通常将出发时机视为路径构建隐含结果的传统TDVRP与GVRP形式化方法不同，所提SMDP将出发时间灵活性建模为显式的运营决策。通过在同一时间段（epoch）内处理车辆同时可用性，建立了用于策略学习的事件触发状态表征。

2. 提出DPSTP框架。该框架采用层次化双阶段解码器：阶段一融合局部、全局与仓库中心注意力机制，实现多仓库分配与空间路径构建；阶段二则基于阶段一的路径决策执行出发时间调度。拥塞感知的空间编码器提供交通依赖的弧表示与客户时间窗信息。不同于要求单阶段神经策略隐式推断路径与调度交互的方法，DPSTP显式表达路径条件化的等待机制，并分离空间选择与出发调整各自的影响。该结构使策略能够协调路径构建与出发时机，从而将车辆出发从不利交通时段转移出去。

3. 计算评估。在时间变化的扩展基准算例上开展实验，包括消融分析与敏感性分析，以量化不同框架组件在各种交通与运营设置下的贡献。此外，通过一个大规模Cordeau案例研究，探讨路径条件化的出发调度：固定空间解，评估有界与松弛等待窗口对通行时长、归一化排放代理成本及延迟惩罚相对于立即出发策略的影响。

本文其余部分安排如下：第2节综述相关文献；第3节正式定义问题并构建事件驱动SMDP模型；第4节详细介绍所提DPSTP框架；第5节报告计算实验与性能比较；第6节通过大规模基准算例的案例研究检验路径级出发时间调度的运营影响；最后，第7节总结全文并讨论未来研究方向。

文献综述节选

TDGMDVRPTW处于时间依赖车辆路径问题（TDVRP）与绿色多仓库车辆路径问题（GMDVRP）的交汇地带。其复杂性不仅源于多仓库分配与客户排序的组合爆炸，还在于需要在时间变化的交通条件下联合优化空间路径与出发调度。本节综述两条文献脉络：第2.1节追溯绿色与问题描述节选

时间依赖的绿色多仓库带时间窗车辆路径问题（TDGMDVRPTW）定义在有向图G=(V, A)上。节点集V=C∪D划分为客户集C={1, 2, ..., n}与仓库集D={n+1, n+2, ..., n+m}。弧集A包含所有可行有向弧。每个仓库d∈D管理一支车队Kd，形成全局同质的车队K=?_{d∈D}Kd。每辆车采用统一的载重容量Q。这种同质车队设置代表物流系统

双阶段时空策略框架节选

在第3.2节建立的SMDP环境内，基于引言与第2.2节的动机，TDGMDVRPTW表现出空间路径与时间调度之间的条件依赖：由于通行时间、排放代理成本与延迟惩罚均随路径与时间变化，节点级等待决策的价值无法脱离其下游空间轨迹独立评估。传统单阶段神经组合优化框架将这两个维度纠缠在一起

计算实验节选

本节通过性能对比、组件分析与鲁棒性实验评估DPSTP。第5.1节描述算例、参数、性能指标与评估协议；第5.2节将DPSTP与神经、元启发式及求解器基准进行比较；第5.3节分离拥塞感知空间编码与主动时间调度各自的贡献；第5.4节考察交通状况、时间窗灵活度、排放代理等

案例研究：出发时间调度的运营影响节选

本节采用Cordeau基准中的大规模pr06算例（Cordeau等人，1997），考察特定路径的出发时间调度的运营影响。分析隔离时间灵活性如何改变固定空间解的执行，以补充第5节的总体评估。其底层空间解通过对pr06算例应用DPSTP与拥塞感知构建启发式获得。所得24条路径的结论节选

本研究针对TDGMDVRPTW展开，这是一个涉及空间轨迹、出发调度、排放代理成本与时间窗约束之间复杂时空交互的组合优化问题。为显式表达这些交互，我们提出了DPSTP框架。该框架将决策过程解耦为空间路径构建（阶段一）与时间调度（阶段二）两步。它首先利用

CRediT作者贡献声明

Yang Zou：撰写原稿、软件、方法论、形式化分析、数据整理、概念构思。Xiaokun Huang：撰写原稿、验证、方法论、调查。Yunqiang Yin：审阅与编辑、验证、方法论、经费获取。T.C.E. Cheng：审阅与编辑、验证、方法论。

利益冲突声明

我们声明，本人/本单位与其他个人或组织不存在可能不当影响本工作的财务或个人关系，亦不存在任何性质或种类的职业或其他个人利益可能被视为影响本手稿 entitled “A Dual-Phase Spatio-Temporal Deep Reinforcement Learning Approach for the Time-Dependent Green Multi-Depot Vehicle Routing Problem Yang Zou|Xiaokun Huang|Yunqiang Yin|T.C.E. Cheng