在线请求的动态多车场车辆路径问题：事件驱动的Transformer-深度强化学习与滚动 horizon 基准测试

# 基于事件驱动Transformer–DRL与滚动时域基准测试的动态多车场在线请求车辆路径问题
来源：https://arxiv.org/html/2608.13799
Gerald M\. Knapp致谢：Faezeh Ardali和Gerald M\. Knapp隶属于美国路易斯安那州立大学工业工程系，巴吞鲁日，美国（邮箱：fardal1@lsu\.edu；gknapp@lsu\.edu）。

###### 摘要

本文提出一个事件驱动的学习与基准测试框架，用于解决请求逐步揭示且车辆状态动态变化的动态多车场车辆路径问题。通过行为克隆和近端策略优化训练掩码MLP与Transformer策略。确定性可行性掩码可防止无效的车辆–请求分配，而固定前缀/柔性后缀的路径承诺机制则保护已执行、进行中及近期决策，并分别度量车辆重分配与路径重排序效果。将所学策略与动态插入启发式算法及限时滚动时域优化方法进行对比。在20个场景的策略基准测试中，所有方法均无无效操作地完成了所有请求，但最近可行策略的目标函数均值最低，在路径质量、等待时间、稳定性、总完工时间和运行时间方面均优于学习策略。在五次独立训练运行中，PPO对MLP策略平均影响较小，但对Transformer策略平均有所提升，尽管不同随机种子下的表现差异更大。在统一协议下，最近可行策略实现了最低的综合目标函数值和路径扰动度，而滚动时域策略在计算成本显著更高的情况下实现了最低的等待时间和完工时间。学习策略保持了毫秒级决策速度，并在未重新训练的情况下成功迁移至最多包含80个请求的实例，但未能超越最强启发式算法。在路径效率、服务响应性、稳定性及在线计算方面，没有单一方法在所有维度上均表现最优。

###### 索引术语：

动态多车场车辆路径、动态车辆路径、Transformer强化学习、在线服务请求、滚动时域优化。

## I引言

车辆路径问题是运输、配送和服务运营中的核心决策问题，它决定了车队如何在满足车辆容量、服务需求、路径时长和车场分配等约束条件下，为地理分散的客户提供服务。车辆路径问题（VRPs）的应用场景包括最后一英里配送、现场服务、技术人员调度、移动医疗和应急物流[8 (https://arxiv.org/html/2608.13799#bib.bib4)]。经典VRPs假设所有请求在调度前已知，而实际系统往往在车辆运营开始后接收新请求[16 (https://arxiv.org/html/2608.13799#bib.bib7)]。动态车辆路径问题（DVRP）通过允许请求和运营状态随时间演变来处理这一情况[10 (https://arxiv.org/html/2608.13799#bib.bib9)]。在多车场场景下，调度员必须反复确定哪辆车和哪个车场应服务每个请求，同时考虑车辆位置、容量、服务状态和客户等待时间的不断变化。因此，由此产生的动态多车场车辆路径问题（D-MDVRP）本质上是一个序列决策问题，而非单一的静态路径任务。

### I-A相关研究与定位

动态路径方法通常通过局部插入、事件驱动或周期性重规划、以及时域滚动重优化来响应新揭示的请求[6 (https://arxiv.org/html/2608.13799#bib.bib5), 9 (https://arxiv.org/html/2608.13799#bib.bib8), 16 (https://arxiv.org/html/2608.13799#bib.bib7)]。除经典方法外，新兴的量子优化框架也通过QUBO公式[12 (https://arxiv.org/html/2608.13799#bib.bib15)]瞄准组合工程问题；尽管前景广阔，但其在许多实际工程问题中的实际应用仍受限。快速插入规则对路径进行局部修改，而滚动时域方法在连续的决策点反复对当前可用请求和约束进行重优化，通常在线计算成本更高[16 (https://arxiv.org/html/2608.13799#bib.bib7)]。

基于学习的调度提供了一种替代方案，其中策略离线训练，在运行时快速评估。此类方法已应用于动态和不确定的VRPs、灾后损害评估与维修调度、事件驱动的机组调度以及自主资源分配问题[1 (https://arxiv.org/html/2608.13799#bib.bib2), 14 (https://arxiv.org/html/2608.13799#bib.bib10), 13 (https://arxiv.org/html/2608.13799#bib.bib11)]。相关工作还将基于Transformer的学习应用于组合调度，并评估了在不重新训练的情况下迁移到更大规模问题实例的能力[4 (https://arxiv.org/html/2608.13799#bib.bib3)]。Transformer架构使用注意力机制建模编码元素之间的依赖关系，相关的调度工作利用它来捕捉高维系统状态和时间依赖性[15 (https://arxiv.org/html/2608.13799#bib.bib6), 2 (https://arxiv.org/html/2608.13799#bib.bib1)]。然而，在本文场景下，在线部署还需要在接收到新信息时进行明确的可行性处理和反复的路径重建。

干扰管理研究进一步强调，实时重规划应在运营质量与偏离现有计划之间取得平衡[5 (https://arxiv.org/html/2608.13799#bib.bib12), 7 (https://arxiv.org/html/2608.13799#bib.bib13)]。相关的滚动时域调度工作同样结合了近期冻结窗口与重排序惩罚，以在信息演变下平衡响应性和计划稳定性[11 (https://arxiv.org/html/2608.13799#bib.bib14)]。基于这些考虑，本框架保护已完成、进行中及近期的决策，并分别报告车辆重分配和前驱节点变更，而非将所有路径修改视为无差别变更。

本文的贡献在于一个集成框架，而非新的路径算法、注意力机制或强化学习算法。它结合了事件驱动的D-MDVRP环境、确定性可行性掩码、使用行为克隆和PPO微调的MLP与Transformer策略、固定前缀/柔性后缀承诺机制以及分离的重分配和重排序度量。随后，在相同的可行性、承诺、目标、场景和运行时间协议下，对启发式算法、学习策略和滚动时域优化进行评估。其主要特点是将通常分开研究的组件进行了关注稳定性的统一比较。

本文的主要贡献包括：一个具有确定性可行性掩码的事件驱动D-MDVRP环境、使用行为克隆和PPO训练的MLP与Transformer策略、具有分离重分配和重排序度量的固定前缀/柔性后缀承诺机制，以及与启发式算法和滚动时域优化的统一协议比较。

## II动态路径模型与假设

我们考虑一个动态服务路径环境，其中容量有限的车辆从多个车场运营。初始请求子集在调度前已知，而额外请求在路径执行过程中揭示。路由状态在请求到达、车辆到达、服务开始和服务完成后更新。已完成的服务、进行中的移动以及近期承诺的决策保持不变，而柔性路径部分中的符合条件的请求可以被重分配或重新排序。

### II-A动态多车场服务网络

设D表示车场集，K表示车辆集，N表示请求集。车辆k属于K，其所属车场d(k)属于D，容量为Q_k，而N_t是截至时间t已揭示的请求集。

每个请求i属于N由一个10维的归一化特征向量表示：

ξ_i(t) = [x_i/L, y_i/L, q_i/Q_max, s_i/15, p_i/3, a_i/T_hor, min{max(t-a_i, 0), T_hor}/T_hor, c_i^stat(t)/5, \bar{k}_i(t), δ_i^pen(t)] (1)

其中L、Q_max和T_hor分别是坐标、容量和时间尺度。特征描述了位置、需求、服务时长、优先级、到达时间、等待时间、请求状态、分配的车辆和待处理状态。状态编码c_i^stat(t)属于{0,...,5}，代表未揭示、待处理、已分配、运输中、服务中和已完成的请求。分配的车辆特征在未分配时为零，否则等于(k_i^asg(t)+1)/|K|，而δ_i^pen(t)仅对请求为待处理时等于1。未揭示的请求保留在固定大小的表示中，但被填充和可行性掩码排除在外。

车辆k由一个9维的特征向量表示：

ν_k(t) = [x_k(t)/L, y_k(t)/L, Q_k^rem(t)/Q_k, Q_k^used(t)/Q_k, c_k^stat(t)/2, \bar{r}_k^cur(t), n_k(t)/N, d(k)/max{1, |D|-1}, D_k(t)/(LN)] (2)

特征描述了当前位置、剩余和已用容量、运营状态、当前服务的请求、柔性路径长度、所属车场和累计距离。车辆状态编码c_k^stat(t)属于{0,1,2}，代表空闲、运输中和服务中状态。当前请求特征在没有请求被激活时为零，否则等于(r_k^cur(t)+1)/N。

每条车辆路径从其所属车场开始并结束，包含其有序的已分配请求。已执行、进行中和承诺的部分保持不变，而柔性后缀可以在重规划期间被修改。数值实验中使用欧氏距离和相应的匀速行驶时间。请求属性和到达时间遵循第IV节[https://arxiv.org/html/2608.13799#S4]描述的场景设置。

### II-B事件驱动的请求与路径承诺

新请求在其到达事件时被添加到已揭示集合中。每个已揭示的请求处于待处理、已分配、进行中或已完成状态。已分配的请求进一步分为固定请求和柔性请求。固定集合包含每辆车下一个受保护的请求，以及任何计划在承诺时域H^commit内开始服务的请求；进行中的运输和服务自动受保护。

因此，每条路径由固定前缀和柔性后缀表示：P_k(t) = P_k^fix(t) ⊕ P_k^flex(t)。只有柔性后缀可以被重分配或重新排序。在每个操作事件，环境更新请求状态、车辆位置、容量、可用性、等待时间和剩余路径。共同的场景种子确保不同方法在相同的运行条件下进行。

## III动态车辆路径的事件驱动学习框架

D-MDVRP被表述为一个事件驱动的序列决策问题。在统一的状态、动作和奖励定义下，确定性可行性和路径承诺规则与通过行为克隆和PPO训练的MLP和Transformer策略相结合。

### III-A序列决策模型

路由环境是一个有限时域的马尔可夫决策过程，其状态包含请求、车辆、车场和全局特征。全局特征包括归一化的仿真时间、已揭示、已完成和待处理请求的比例、重规划次数以及累计路径变更次数。

请求经历未揭示、待处理、已分配、运输中、服务中和已完成状态。在重规划时，固定前缀保持不变，先前柔性后缀中的请求返回待处理集合。每个动作分配一个待处理请求并将其附加到车辆的重建后缀中。当没有已揭示的待处理请求时构建结束；未揭示的请求等待到达，并且没有单独的停止或延迟动作。

车辆负载根据已完成、进行中和承诺的需求初始化，并在每次分配后更新。掩码防止容量违规并保留足够的剩余车队容量。如果仍有待处理请求但所有动作都被掩码，则状态被声明为不可行。重规划前存储先前的车辆分配和前驱节点；新揭示的请求不产生变更惩罚，而对先前计划请求的变更在重建后最终确定。

### III-B掩码MLP与Transformer策略

在每个决策点，行动者对每个车辆-请求对进行评分。基础实例包含4辆车和30个请求，产生120个候选动作。在softmax或贪婪选择之前，无效的逻辑值被设置为负无穷大。一对仅在请求已揭示、待处理或柔性分配、未完成、进行中、承诺或在当前重建过程中先前被选中，且对于所选车辆可行时才有效。因此，无效动作在BC、PPO、验证和测试期间接收到零概率。

#### III-B1 MLP行动者与评论家

MLP行动者使用10个请求特征、9个车辆特征、6个全局特征和5个特定于配对的特征来表示每一对。特定于配对的特征包括最近距离、增量距离、预测等待时间、路径变更指示器和路径长度。一个共享的→130→64→32→1 ReLU网络对所有配对进行评分。评论家对可行候选向量的逐元素平均值和最大值进行池化，并应用一个→160→64→32→1 Tanh网络。

#### III-B2 Transformer行动者与评论家

Transformer使用30个请求标记、4个车辆标记和2个车场标记，特征维度分别为10、9和6。车场d表示为：

[x_d/L, y_d/L, d/max{1, |D|-1}, n_d^home/|K|, t/T_hor, 1] (3)

其中n_d^home是驻扎在车场d的车辆数量。独立的线性投影将请求、车辆和车场特征映射到d_model=32。学习的标记类型和位置嵌入以及一个投影的6维全局向量被添加到标记中。编码器有一层。