Dynamic Multi-Depot Vehicle Routing with Online Requests: Event-Driven Transformer--DRL and Rolling-Horizon Benchmarking

Technical Summary: Dynamic Multi-Depot Vehicle Routing with Online Requests

Problem Definition
This paper addresses the Dynamic Multi-Depot Vehicle Routing Problem (D-MDVRP) characterized by progressively revealed requests and evolving vehicle states. Unlike static VRPs where all requests are known prior to dispatch, the D-MDVRP involves a sequential decision-making environment where new service requests arrive during route execution. The dispatcher must determine which vehicle from which depot serves each request while managing constraints such as vehicle capacity, service demand, route duration, and changing vehicle locations. The problem is framed as a sequential decision process requiring a balance between operational efficiency (minimizing distance and waiting time) and stability (minimizing disruptions to existing plans).

Methodology
The authors propose an integrated, event-driven learning and benchmarking framework that combines deterministic feasibility handling with deep reinforcement learning (DRL) and traditional optimization.

• State and Action Representation: The environment models requests and vehicles using normalized feature vectors. Requests include location, demand, priority, arrival time, and status (unrevealed, pending, assigned, traveling, serving, completed). Vehicles are represented by location, remaining capacity, status, and home depot. The state includes global features such as simulation time and replanning counts.
• Event-Driven Simulation: The system advances through discrete events (request arrivals, vehicle arrivals, service starts/completions). At each replanning event, the route is decomposed into a fixed prefix (completed, active, and near-term committed decisions) and a flexible suffix. Only the flexible suffix is subject to reassignment or reordering.
• Feasibility Masking: A deterministic masking mechanism prevents invalid actions (e.g., assigning a completed request or violating capacity). Invalid vehicle-request pairs are assigned negative infinity logits before softmax or greedy selection, ensuring 100% feasibility during training and testing.
• Policy Architectures:
  • MLP Policy: A Multi-Layer Perceptron scores vehicle-request pairs using request, vehicle, global, and pair-specific features (e.g., incremental distance, predicted waiting time).
  • Transformer Policy: Utilizes attention mechanisms to model dependencies among encoded elements. It employs separate tokens for requests, vehicles, and depots, with learned position embeddings and a global context vector.
• Training Regime: Policies are trained via Behavior Cloning (BC) using expert demonstrations (derived from heuristics like waiting-aware insertion or a hybrid expert) followed by Proximal Policy Optimization (PPO) fine-tuning. The reward function aligns with the evaluation objective, incorporating penalties for distance, waiting time, and route changes.
• Benchmarking: The learned policies are compared against:
  1. Dynamic Insertion Heuristics: Including nearest feasible, cheapest append, and waiting-aware insertion.
  2. Rolling-Horizon Optimization: A time-limited (1-second) reoptimization of flexible requests using OR-Tools/SCIP.

Key Contributions

1. Integrated Framework: The paper presents a unified framework that combines an event-driven D-MDVRP environment, deterministic feasibility masking, and fixed-prefix/flexible-suffix route commitments.
2. Stability-Aware Metrics: It introduces separate measures for vehicle reassignment and predecessor change (resequencing), allowing for a nuanced analysis of route disruption rather than treating all modifications as a single metric.
3. Common-Protocol Benchmarking: The study evaluates learned policies, heuristics, and rolling-horizon optimization under identical feasibility rules, commitment horizons, and scenario seeds, providing a fair comparison of components often studied in isolation.
4. Transferability Analysis: The work investigates the ability of learned policies to scale to larger problem instances (up to 80 requests) without retraining.

Experimental Results
Experiments were conducted on synthetic Euclidean instances with varying numbers of depots, vehicles, and requests (30, 50, and 80 total requests).

• Performance vs. Heuristics: In a 20-scenario benchmark, the "Nearest Feasible" heuristic consistently outperformed all learned policies (MLP and Transformer, with or without PPO) and the rolling-horizon baseline. Nearest Feasible achieved the lowest mean objective (346.1), lowest distance, lowest waiting time, highest stability (fewest route changes), and fastest runtime (0.156 ms/action).
• Impact of PPO: Across five independent training runs, PPO fine-tuning had a negligible average effect on the MLP policy (0.13% improvement) but improved the Transformer policy by approximately 2.5%, albeit with higher variability across seeds.
• Scalability: The learned policies successfully transferred to larger instances (up to 80 requests) without retraining, maintaining millisecond-level decision times. However, their objective values and runtime increased with problem size, and they still did not surpass the performance of the strongest heuristic.
• Rolling-Horizon Trade-off: The rolling-horizon optimization achieved the lowest waiting times and makespan but incurred significantly higher computational costs and greater route disruption compared to heuristics and learned policies.
• Ablation Study: Removing near-term commitments or reassignment penalties increased the overall objective, with the removal of the reassignment penalty showing statistical significance (p = 0.007).

Significance and Claims
The paper modestly claims that its primary contribution is the integration and rigorous comparison of these components rather than the invention of a superior routing algorithm. The results demonstrate that while learned policies offer feasible, millisecond-level decisions and transferability across instance sizes, they did not outperform the strongest heuristic (Nearest Feasible) in terms of routing efficiency, service responsiveness, stability, or online computation time.

The authors emphasize the importance of strong heuristic baselines in evaluating learning-based approaches for dynamic routing. The study highlights that integrating feasibility handling, route commitments, and stability measures is valuable for creating robust dynamic-routing policies, but current learning-based methods in this specific setting have not yet surpassed classical heuristics in overall performance. The work underscores that no single method is optimal across all criteria (efficiency, responsiveness, stability, and speed), suggesting that the choice of method depends on the specific operational priorities of the application.