提出事件驱动框架解决动态多车场路径问题,对比学习与启发式方法表现。
Dynamic Multi-Depot Vehicle Routing with Online Requests: Event-Driven Transformer--DRL and Rolling-Horizon Benchmarking

- 用掩码MLP与Transformer结合行为克隆和强化学习训练策略
- 最近可行法在路径质量、等待时间等指标上全面领先
- 模型可快速决策并迁移至80请求场景,但未超越最优启发式
本文针对请求逐步揭示、车辆状态动态变化的动态多车场车辆路径问题,提出事件驱动的学习与基准测试框架。通过行为克隆与近端策略优化训练掩码MLP和Transformer策略,采用确定性可行性掩码避免无效分配,固定前缀/灵活后缀路由承诺分别保护已完成、进行中及近期决策,并独立评估车辆重分配与重排序。所学策略与动态插入启发式及限时滚动时域优化方法对比。在20个场景的策略基准测试中,所有方法均完成所有请求且无无效动作,但最近可行法在平均目标值、路径质量、等待时间、稳定性、完工时间及运行时间上均最优。五次独立训练中,PPO对MLP影响微弱,对Transformer平均略有提升,但种子间方差较大。在统一协议下,最近可行法在综合目标与路径扰动上最低;滚动时域虽使等待时间和完工时间最低,但计算成本显著更高。所学策略保持毫秒级决策速度,可零样本迁移至最多80请求实例,但未超越最强启发式。任一方法均无法在路径效率、服务响应、稳定性和在线计算中全面占优。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。