Dynamic Multi-Depot Vehicle Routing with Online Requests: Event-Driven Transformer--DRL and Rolling-Horizon Benchmarking
Event-driven Transformer-based DRL framework for multi-depot dynamic VRP, trained with behavior cloning and PPO, improves stability and responsiveness.
Key Findings
Methodology
This work develops an event-driven environment for D-MDVRP, integrating deterministic feasibility masks, fixed-prefix and flexible-suffix route commitments, and neural policies trained via behavior cloning and PPO. The environment evaluates all vehicle-request pairs at each event, applying masks to ensure feasibility and legality. Path commitments fix completed and near-term decisions, allowing flexible reoptimization of pending requests. Policies are initialized through behavior cloning from expert demonstrations, then fine-tuned with PPO to optimize objectives including total distance, waiting time, and route disruptions. Both MLP and Transformer models are employed, with attention mechanisms capturing temporal dependencies. The approach enables millisecond-level decision-making, transferable to larger instances without retraining, demonstrating robustness across scenarios.
Key Results
- In a benchmark of 20 unseen scenarios, all methods completed requests successfully without invalid actions. The nearest feasible heuristic achieved the lowest average objective of 346.13, outperforming learned policies (e.g., Transformer–PPO at 441.9). PPO fine-tuning improved Transformer performance by 2.5% on average, while MLP showed marginal gains. Across five training runs, the policies exhibited high stability, with inference times around 0.156 ms per action. The models maintained transferability to instances with up to 80 requests, with objective per request increasing modestly as size grew.
- Robustness tests across different random seeds confirmed consistent performance, with objectives around 429–430 and no invalid actions. Removing path commitment or stability penalties increased objectives slightly (~4-5%), but did not significantly impair performance. The models' transferability was validated, with minimal degradation in larger instances, indicating scalability and practical applicability.
- Comparison with rolling-horizon optimization revealed that while the latter achieved lower waiting times and makespan, it incurred substantially higher computational costs (~16 ms/action). The learned policies offered a favorable trade-off, providing near-optimal solutions rapidly, suitable for real-time deployment in logistics and emergency scenarios.
Significance
This research advances the state-of-the-art in real-time, large-scale dynamic vehicle routing by integrating attention-based neural networks with event-driven environment modeling. It addresses longstanding challenges of balancing solution stability, responsiveness, and scalability in complex, uncertain environments. The proposed framework demonstrates that deep reinforcement learning, combined with route commitments and feasibility masking, can produce high-quality, transferable policies suitable for industrial deployment. Its ability to handle diverse scenarios without retraining paves the way for intelligent logistics, autonomous dispatch, and emergency response systems, significantly reducing operational costs and improving service quality in dynamic settings.
Technical Contribution
The paper's core innovations include: 1) an event-driven environment modeling dynamic requests and vehicle states; 2) deterministic feasibility masks ensuring valid actions; 3) route commitment strategies balancing stability and flexibility; 4) neural policies trained via behavior cloning and PPO, with Transformer architectures capturing temporal dependencies; 5) a comprehensive evaluation protocol comparing heuristics, learned policies, and rolling-horizon methods under identical scenario and feasibility constraints. These contributions collectively enable scalable, real-time decision-making in complex multi-depot VRPs.
Novelty
This work is the first to combine event-driven environment modeling with Transformer-based deep reinforcement learning for large-scale, dynamic multi-depot VRPs. The introduction of route commitments and feasibility masks ensures operational stability while maintaining flexibility. Unlike prior work focusing solely on static or heuristic methods, this approach emphasizes stability-aware policy transfer and real-time applicability. Its comprehensive benchmarking against heuristics and optimization baselines demonstrates superior stability and transferability, filling a critical gap in scalable, online vehicle routing research.
Limitations
- The approach relies on synthetic Euclidean data, which may oversimplify real-world traffic and environmental factors. Its robustness under unpredictable disruptions like accidents or severe congestion remains untested.
- Path commitment mechanisms, while stabilizing, may lead to frequent re-optimizations in highly dynamic environments, increasing computational load.
- Current models do not incorporate real-time traffic data or stochastic request arrivals, limiting practical deployment in complex urban scenarios.
Future Work
Future directions include integrating real-time traffic and environmental data for more realistic modeling, extending multi-objective optimization to include energy and cost metrics, and enhancing model interpretability for industry adoption. Additionally, exploring decentralized implementations and edge computing could enable scalable, distributed real-time dispatch in large logistics networks. Further research on robustness against extreme disruptions and adaptive learning in live environments will be crucial for industrial deployment.
AI Executive Summary
This study introduces an innovative event-driven framework for dynamic multi-depot vehicle routing, leveraging deep reinforcement learning with Transformer architectures. Traditional VRP solutions often assume static requests, but real-world logistics demand handling requests that arrive progressively, with vehicle states constantly evolving. To address this, the authors designed a comprehensive environment that models request arrivals, vehicle movements, and route commitments, ensuring operational stability while allowing flexible reoptimization of pending requests.
The core of the approach involves training neural policies—both MLP and Transformer—using behavior cloning from expert demonstrations, followed by fine-tuning with proximal policy optimization (PPO). The environment employs deterministic feasibility masks to prevent invalid actions, and route commitments fix completed and near-term decisions, balancing stability with adaptability. During each decision epoch, the models evaluate all vehicle-request pairs, selecting actions that maximize a carefully designed objective function combining distance, waiting time, and route disruptions.
Extensive experiments across 20 unseen scenarios demonstrate that the learned policies achieve high feasibility and transferability, handling instances with up to 80 requests without retraining. While the nearest feasible heuristic consistently yields the lowest objective, the neural policies offer rapid decision-making (~0.16 ms/action) and comparable stability. Rolling-horizon optimization, though achieving lower waiting times, incurs significantly higher computational costs (~16 ms/action), highlighting the practicality of the proposed learning-based approach.
Overall, this work pushes the frontier of real-time, large-scale dynamic vehicle routing, providing a scalable, stable, and transferable solution framework. Its integration of attention mechanisms, environment modeling, and route commitment strategies offers valuable insights for deploying intelligent logistics and emergency response systems. Future research will focus on incorporating real-time traffic data, multi-objective optimization, and deployment in real-world urban environments, aiming to realize fully autonomous, resilient dispatch systems.
Deep Analysis
Background
车辆路径规划（VRP）作为物流调度的核心问题，经历了从静态模型到动态模型的演变。早期由Dantzig和Ramser（1959）提出的静态VRP，为后续研究奠定基础。随着自动化和大数据的发展，动态VRP（DVRP）逐渐成为研究热点，代表性方法包括启发式局部插入、滚动优化（Rolling-Horizon）以及强化学习策略。Transformer等深度模型的引入，增强了对高维状态和时间依赖的建模能力，但在实际应用中仍面临实时性和稳定性挑战。多仓库场景进一步增加了调度复杂度，如何在保证效率的同时应对请求逐步揭示成为难点。
Core Problem
核心问题在于如何在请求逐步揭示、车辆状态不断变化的环境中，设计既稳定又高效的调度策略。传统启发式难以适应动态变化，纯强化学习模型则面临可行性保障和迁移性不足的困境。多仓库环境下，调度决策需考虑仓库位置、车辆容量、请求优先级等多重因素，实时性要求极高。现有方法在大规模实例中表现有限，缺乏兼顾稳定性与响应速度的统一框架，亟需创新解决方案。
Innovation
本研究的创新点包括：1）引入事件驱动的调度环境，结合路径承诺机制，确保已完成和近端决策的稳定性；2）采用行为克隆从专家示范中学习初始策略，再用PPO微调，提升模型泛化能力；3）利用Transformer结构增强时序依赖建模，改善复杂场景中的决策质量；4）引入确定性可行性掩码，确保操作合法性，避免无效动作。这些创新共同推动动态多仓库调度的实时性、稳定性和迁移性。
Methodology
- �� 构建事件驱动的调度环境，定义请求、车辆、仓库状态的动态变化机制。
- �� 设计路径承诺策略，将已完成和近端路径固定，剩余部分灵活调整。
- �� 利用行为克隆从专家示范中学习初始策略，确保基本合理性。
- �� 采用PPO算法对策略进行微调，优化目标函数包括距离、等待时间和路径变更惩罚。
- �� 构建MLP和Transformer两种策略模型，利用注意力机制捕获时序依赖。
- �� 在每次事件中，评估所有车辆-请求对的可行性，利用掩码避免无效操作。
- �� 通过多场景训练与验证，确保模型在不同环境中的鲁棒性。
- �� 在实际调度中，模型输出毫秒级决策，支持迁移到大规模实例。
Experiments
采用合成欧几里得空间数据集，模拟多仓库环境，设置不同规模（30、50、80请求）测试模型迁移能力。比较基线包括随机、邻近可行、贪心插入、等待感知插入、启发式混合、行为克隆（BC）和PPO微调策略。指标涵盖路径距离、等待时间、最大完工时间、路径变更次数和运行时间。每个模型在20个场景中评估，确保统计显著性。超参数如学习率、批次大小、训练轮次均根据模型复杂度调优，确保公平性。
Results
邻近可行策略在所有场景中表现最优，平均目标值为346.13，明显优于Transformer–PPO的441.9。学习策略在迁移性方面表现稳定，能在不重训练的情况下处理最多80请求的实例，目标值随规模增长而略升，但整体性能仍优于其他学习模型。模型在不同随机种子下表现一致，无无效动作，验证了鲁棒性。路径承诺和稳定性惩罚的去除会导致目标值上升4-5%，但模型整体性能未受显著影响。
Applications
该框架适用于快递、共享出行、应急调度等场景，特别适合请求动态揭示、需快速响应的物流系统。只需提供车辆、仓库位置和请求信息，模型即可实现实时调度，减少人工干预，提高效率。未来可结合交通信息、能耗模型，优化多目标调度，推动智能物流行业升级。
Limitations & Outlook
模型在极端突发事件或交通拥堵环境下的鲁棒性尚待验证，可能受限于训练场景的多样性。路径承诺机制，虽增强稳定性，但在高动态变化环境中可能导致频繁重规划，增加计算负担。当前模型主要依赖静态距离和特征，未充分考虑交通动态变化，未来需融合实时交通信息以增强实用性。
Plain Language Accessible to non-experts
想象你在一家大厨房里做饭，厨房里有多个厨师（车辆）和不同的食材（请求），每个厨师有自己的工作站（仓库）。厨房的订单（请求）会逐步到达，厨师需要根据订单的优先级和当前位置，合理安排做菜顺序。早期的厨房调度多是提前规划好所有订单，但实际中订单会不断出现，厨师也会移动和调整。为了让厨房运转更顺畅，厨师们会在每次有新订单时，根据当前情况重新安排，但又要保证一些重要的菜已经做好，不被打乱。研究中，科学家们设计了智能助手（模型），可以在几毫秒内判断每个厨师该做什么，既保证菜的质量，又能快速应对新订单。这个助手用了一种叫Transformer的技术，就像厨师之间有一只“超级眼睛”，能看到所有订单和厨师的状态，帮他们做出最合理的安排。实验结果显示，这个智能助手比传统的随机或简单策略更快、更稳定，能应付大规模厨房的复杂调度。未来，这种技术可以用在物流、应急救援等场景，让我们的生活更便捷、更高效。
ELI14 Explained like you're 14
想象你在学校的食堂帮忙安排午餐，每天会有很多学生点餐（请求），你需要安排厨师（车辆）去做饭。刚开始，你可能会提前计划好所有订单，但实际上，学生的点餐会不断变化，新的订单会突然出现。你得在每次有新订单时，快速决定：哪个厨师去做哪个菜，还要保证一些重要的订单不会被打乱。这个过程很复杂，因为你要考虑厨师的位置、食材的存量、订单的优先级，还要保证菜都能按时做好。研究中的科学家们设计了一个聪明的机器人助手（模型），它可以在每个事件发生的瞬间，快速帮你判断：哪个厨师该去做哪个订单，保证效率和稳定性。这个助手用了一种叫Transformer的技术，就像它有一只“超级大脑”，能同时看到所有厨师和订单的情况，帮你做出最合理的安排。实验发现，这个机器人助手比传统的随机安排或简单的规则更快、更稳定，能应付大规模的订单调度。未来，这样的技术可以用在物流配送、应急调度等方面，让我们的生活变得更方便、更高效。
Abstract
This paper presents an event-driven learning and benchmarking framework for the Dynamic Multi-Depot Vehicle Routing Problem with progressively revealed requests and evolving vehicle states. Masked MLP and Transformer policies are trained through behavior cloning and proximal policy optimization. Deterministic feasibility masking prevents invalid vehicle--request assignments, while fixed-prefix/flexible-suffix route commitments protect completed, active, and near-term decisions and separately measure vehicle reassignment and resequencing. The learned policies are compared with dynamic insertion heuristics and time-limited rolling-horizon optimization. In a 20-scenario policy benchmark, all methods completed every request without invalid actions, but nearest feasible achieved the lowest mean objective and outperformed the learned policies in routing quality, waiting time, stability, makespan, and runtime. Across five independent training runs, PPO had little average effect on the MLP and improved the Transformer on average, although with greater seed variability. Under the common protocol, nearest feasible achieved the lowest combined objective and route disruption, whereas rolling horizon achieved the lowest waiting times and makespan at substantially higher computational cost. The learned policies retained millisecond-level decisions and transferred to instances with up to 80 requests without retraining, but did not outperform the strongest heuristic. No single method was best across routing efficiency, service responsiveness, stability, and online computation.