PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Faezeh Ardali, Gerald M. Knapp

arXiv:2608.13799v1cs.LG

TL;DR

Dynamic multi-depot vehicle routing must assign newly revealed requests while vehicle locations, capacities, service statuses, and waiting times evolve. This paper develops an event-driven, stability-aware learning and benchmarking framework and finds that the nearest-feasible heuristic outperforms learned policies across most quality and runtime measures, while rolling horizon minimizes waiting and makespan at higher computational cost.

  • Problem

    Dynamic multi-depot routing requires sequentially assigning newly revealed requests while vehicle locations, capacities, service statuses, and customer waiting times change.

  • Method

    The paper combines event-driven modeling, deterministic feasibility masking, route commitments, learned MLP and Transformer policies, and common-protocol comparisons with heuristics and rolling-horizon optimization.

  • Results

    Nearest feasible achieved the lowest mean objective, was best in 18 of 20 scenarios, and outperformed learned policies across distance, waiting, stability, makespan, and runtime.

  • Takeaways & Limitations

    Strong heuristic baselines remain important because no evaluated method dominated routing efficiency, service responsiveness, stability, and online computation simultaneously.

Abstract

from arXiv · show

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.

I. INTRODUCTION … A. Dynamic Multi-Depot Service Network

The paper frames dynamic multi-depot vehicle routing as sequential dispatch under progressively revealed requests and evolving vehicle states. It presents an integrated event-driven framework combining feasibility masking, learned policies, route commitments, and common-protocol benchmarking.

  • I. INTRODUCTION: Dynamic multi-depot routing repeatedly assigns requests to vehicles and depots while vehicle locations, capacities, service statuses, and waiting times change.The resulting D-MDVRP is treated as a sequential decision problem rather than a single static routing task.
  • A. Related Work and Positioning: Dynamic routing commonly uses local insertion, event-driven or periodic replanning, and rolling-horizon reoptimization for newly revealed requests.Learning-based dispatch offers an alternative by training policies offline and evaluating them rapidly during operation.
  • A. Related Work and Positioning: Real-time replanning must balance operational quality against deviations from an existing plan as information evolves.Related work motivates freeze windows and resequencing penalties, while this framework protects completed, active, and near-term decisions.
  • A. Related Work and Positioning: The contribution integrates an event-driven D-MDVRP environment, deterministic feasibility masking, behavior-cloned MLP and Transformer policies with PPO fine-tuning, and fixed-prefix/flexible-suffix commitments.It also reports vehicle reassignment and resequencing separately and compares heuristics, learned policies, and rolling-horizon optimization under a common protocol.
  • II. DYNAMIC ROUTING MODEL AND ASSUMPTIONS: The environment uses capacitated vehicles operating from multiple depots, with an initial request subset known before dispatch and additional requests revealed during route execution.The routing state updates after request arrivals, vehicle arrivals, service starts, and service completions.
  • A. Dynamic Multi-Depot Service Network: Each vehicle has a home depot and capacity, while N_t contains requests revealed by time t.The model denotes the depot, vehicle, and request sets by D, K, and N, respectively.
  • A. Dynamic Multi-Depot Service Network: Requests use 10-dimensional normalized features, and vehicles use nine-dimensional features encoding operational state, route flexibility, depot assignment, and cumulative distance.Request status distinguishes unrevealed, pending, assigned, traveling, serving, and completed states; vehicle status distinguishes idle, traveling, and serving.
  • A. Dynamic Multi-Depot Service Network: Executed, active, and committed route portions remain fixed, whereas flexible suffixes may be revised during replanning.Routes begin and end at each vehicle’s home depot, and unrevealed requests remain represented but are excluded by padding and feasibility masks.

B. Event-Driven Requests and Route Commitments

The framework updates revealed-request and vehicle states at operational events while protecting near-term route commitments. Each vehicle route uses a fixed prefix and flexible suffix, with reassignment or reordering restricted to the suffix.

  • Event-Driven Requests: Requests enter the revealed set at arrival events and progress through pending, assigned, active, and completed statuses.Assigned requests are additionally classified as fixed or flexible.
  • Route Commitments: The fixed set protects each vehicle’s next request, requests beginning service within Hcommit, and all active travel or service.These protections define which assignments cannot be altered during online decisions.
  • Route Commitments: Each route consists of a fixed prefix and flexible suffix, and only the suffix can be reassigned or reordered.At every operational event, the environment updates request statuses, vehicle locations, capacities, availability, waiting times, and remaining routes.
  • Event-Driven Requests: Common scenario seeds ensure that all methods operate under identical conditions.This supports direct comparison across the dynamic routing methods.

III. EVENT-DRIVEN LEARNING FRAMEWORK FOR DYNAMIC VEHICLE ROUTING

The framework models D-MDVRP as an event-driven sequential decision problem. It combines deterministic feasibility and route-commitment rules with MLP and Transformer policies trained by behavior cloning and PPO.

  • D-MDVRP is formulated as an event-driven sequential decision problem with common state, action, and reward definitions.
  • Deterministic feasibility and route-commitment rules support MLP and Transformer policies trained by behavior cloning and PPO.

A. Sequential Decision Model … 2) Transformer Actor and Critic:

The framework models dynamic routing as a finite-horizon sequential decision process with event-driven replanning, fixed route prefixes, and feasibility masking. It implements masked MLP and Transformer actor–critic policies that score vehicle–request assignments using state, pair, token, and global features.

  • A. Sequential Decision Model: The routing environment is a finite-horizon Markov decision process whose state combines request, vehicle, depot, and global simulation features.Global features include normalized time, revealed, completed, and pending-request proportions, replanning count, and cumulative route changes.
  • A. Sequential Decision Model: At replanning, fixed prefixes remain unchanged, while requests in the previous flexible suffix return to the pending set for reassignment.Actions assign one pending request and append it to a vehicle’s reconstructed suffix until no revealed pending request remains.
  • A. Sequential Decision Model: Capacity masking updates vehicle load after every assignment, blocks capacity violations, and declares infeasibility when pending requests remain but all actions are masked.Previous assignments and predecessors are stored before replanning; newly revealed requests incur no change penalty, while changes to previously planned requests are finalized after reconstruction.
  • B. Masked MLP and Transformer Policies: At each decision, the policy scores 120 vehicle–request pairs in base instances with four vehicles and 30 requests, assigning zero probability to invalid actions.Valid pairs require revealed, pending or flexibly assigned, eligible requests and a feasible selected vehicle; invalid logits are set to negative infinity.
  • 1) MLP Actor and Critic:: The MLP represents each pair with 10 request, nine vehicle, six global, and five pair-specific features, then applies a shared 30→64→32→1 ReLU scorer.Its critic pools elementwise means and maxima of feasible candidate vectors and uses a 60→64→32→1 Tanh network.
  • 2) Transformer Actor and Critic:: The Transformer uses 30 request, four vehicle, and two depot tokens with feature dimensions 10, nine, and six, respectively.Separate projections map token features to d_model = 32, while learned token-type and position embeddings and a projected six-dimensional global vector are added.
  • 2) Transformer Actor and Critic:: The Transformer encoder has one layer, four attention heads, feedforward dimension 64, ReLU activation, and zero dropout, with unrevealed requests zeroed and masked.For each pair, encoded vehicle, request, and global vectors plus five edge features form a 101-dimensional scorer input processed by a shared 101 →64 →1 ReLU network.
  • 2) Transformer Actor and Critic:: The Transformer critic pools elementwise means and maxima over visible request, vehicle, depot, and feasible-edge features together with six global features.The supplied specification continues with the resulting critic dimension but truncates before stating its complete value.

C. Route Commitment, Stability, Objective, and Reward

The evaluation objective combines executed distance, customer waiting time, and route changes, while additional metrics report service, completion, and runtime outcomes. Commitment-aware analysis separates disruption into vehicle reassignment and predecessor changes, and PPO rewards are aligned with the undiscounted evaluation objective.

  • Objective definition: The objective includes total executed distance, total customer waiting time, and changes to previously planned flexible requests’ vehicle–predecessor pairs.Distance includes depot returns; the associated coefficients use units of distance per customer-minute and distance per route change.
  • Reported metrics: Average and maximum waiting, makespan, completion, and runtime are reported separately from the evaluation objective.
  • PPO reward: PPO uses incremental distance, predicted waiting, and an action-level change indicator to provide dense intermediate feedback.The undiscounted episode reward remains exactly aligned with the evaluation objective.
  • PPO reward: PPO uses γ = 0.99, so the timing of intermediate costs may affect the discounted return.
  • Route stability: Commitment-aware disruption is separated into vehicle reassignment and predecessor change for flexible requests.A request may contribute to both terms.

D. Behavior Cloning and PPO Fine-Tuning · 1) Behavior-Cloning Dataset Construction:

The policies are trained with behavior cloning followed by PPO fine-tuning, using deterministic, scenario-disjoint expert demonstrations for the MLP and Transformer. The Transformer expert selects among heuristic-proposed actions using a deterministic composite score and tie-breaking rule.

  • D. Behavior Cloning and PPO Fine-Tuning: Behavior cloning precedes PPO fine-tuning for both the MLP and Transformer policies.This establishes the two-stage training procedure.
  • 1) Behavior-Cloning Dataset Construction:: Each BC sample contains the complete state, deterministic mask, and expert vehicle–request action, with one sample per expert decision.All data splits are scenario-disjoint.
  • 1) Behavior-Cloning Dataset Construction:: The MLP expert uses waiting-aware insertion and provides 4,525 training and 1,528 validation samples.Training, validation, and held-out seeds are 1000–1011, 2000–2003, and 3000–3005, respectively.
  • 1) Behavior-Cloning Dataset Construction:: The Transformer expert forms Ct from unique actions proposed by nearest feasible, cheapest append, and waiting-aware insertion.At each decision, it considers the candidate vehicle–request actions in this set.
  • 1) Behavior-Cloning Dataset Construction:: Scores are rounded to 12 decimal places, with ties resolved by the smallest flattened vehicle–request action index.This makes expert action selection deterministic.
  • 1) Behavior-Cloning Dataset Construction:: The Transformer dataset contains 4,266 training and 1,372 validation samples.Training, validation, and held-out seeds are 4100–4111, 5100–5103, and 6100–6105, respectively.
  • 1) Behavior-Cloning Dataset Construction:: Actors use masked cross-entropy and retain the checkpoint with minimum validation cross-entropy.The principal behavior-cloning settings are summarized in Table I.

2) PPO Fine-Tuning:

PPO fine-tuning initializes from the selected behavior-cloning actor and uses standard actor–critic optimization with generalized advantage estimation and normalized advantages. Checkpoints are selected by greedy validation, with behavior cloning retained until PPO improves the validation objective.

  • PPO Fine-Tuning: The selected behavior-cloning actor initializes PPO, which separately optimizes actor and critic networks with Adam.PPO uses generalized advantage estimation, normalized advantages, and the standard clipped PPO loss.
  • PPO Fine-Tuning: Greedy validation retains the actor–critic pair with the lowest mean objective after each iteration.Behavior cloning is iteration zero and is replaced only after validation improvement.
  • PPO Fine-Tuning: MLP and Transformer training use distinct seed ranges, while held-out and common-protocol scenarios are excluded from checkpoint selection.MLP training, validation, and held-out seeds are 4000–4023, 5000–5003, and 6000–6005; Transformer seeds are 7200–7211, 8200–8203, and 9200–9205.

E. Event-Driven Operation and Rolling-Horizon Benchmark · IV. NUMERICAL RESULTS · A. Experimental Setup

The framework operates by replanning at discrete operational events while preserving completed, active, and committed route prefixes. Experiments compare heuristics, learned policies, and time-limited rolling-horizon optimization across feasibility, routing, scalability, stability, and online computation.

  • E. Event-Driven Operation and Rolling-Horizon Benchmark: Replanning occurs at request arrivals, vehicle arrivals, service starts, and service completions, retaining active and committed prefixes while rebuilding flexible suffixes.Cumulative loads are initialized from completed, active, and committed demand before feasible actions are selected.
  • E. Event-Driven Operation and Rolling-Horizon Benchmark: Learned policies use offline training and require only the current state, one forward evaluation per decision, and deterministic feasibility checks during testing.New request arrivals do not trigger retraining.
  • E. Event-Driven Operation and Rolling-Horizon Benchmark: Rolling horizon uses the same event states, fixes completed, active, and committed segments, and permits capacity-constrained reassignment and resequencing of flexible requests.Each solve is limited to one second, and the implemented solution is the best feasible incumbent returned within that limit; optimality-gap statistics were unavailable.
  • IV. NUMERICAL RESULTS: The numerical evaluation covers solution feasibility, routing performance, scalability, route stability, and online computation time.Compared methods include dynamic insertion heuristics, behavior-cloned policies, PPO-fine-tuned policies, and time-limited rolling-horizon optimization.
  • A. Experimental Setup: Scaling experiments use 30, 50, and 80 total requests across four dynamic-request waves, averaging three scenarios per size with separate seed ranges.The MLP is applied directly across sizes, while Transformer request, vehicle, and depot position-embedding blocks are interpolated separately.
  • A. Experimental Setup: The unified benchmark evaluates 20 unseen scenarios, while the common-protocol experiment reuses their seeds and request realizations in a commitment-aware environment with a 15-minute commitment horizon.The common protocol compares nearest feasible, waiting-aware, MLP–PPO, Transformer–PPO, and rolling horizon using objective (6).
  • A. Experimental Setup: Experiments run without GPU acceleration, and rolling horizon uses OR-Tools 9.8.3296 with SCIP 8.0.4, one thread, and a one-second limit.End-to-end replanning timing includes state construction, sequential decisions, masking, route updates, and stability accounting; rolling-horizon timing additionally includes model construction, optimization, and route extraction.
  • A. Experimental Setup: Waiting-aware and Hybrid were selected as behavior-cloning teachers to provide multi-criteria demonstrations rather than reproduce the retrospectively strongest test heuristic.Waiting-aware combines incremental distance with predicted waiting and a change indicator, while Hybrid uses the weighted training score.

B. Unified Comparison of Heuristic and Neural Policies · C. Robustness Across Independent Training Seeds

Across 20 common scenarios, nearest feasible was the strongest overall method: all approaches completed requests feasibly, but learned policies did not surpass it in quality or runtime. Across five independent seeds, PPO had little average effect on the MLP and improved the Transformer with greater variability, while nearest feasible remained best.

  • B. Unified Comparison of Heuristic and Neural Policies: 100% request completion was achieved by all methods under the common feasibility rules, with no invalid actions selected.The comparison used 20 common test scenarios.
  • B. Unified Comparison of Heuristic and Neural Policies: 346.13 was nearest feasible’s mean objective; it was best in 18 of 20 scenarios and outperformed learned policies across distance, waiting, makespan, route changes, and runtime.Nearest feasible averaged 0.156 ms/action versus 0.538–0.867 ms/action for learned policies.
  • B. Unified Comparison of Heuristic and Neural Policies: The learned policies provided feasible millisecond inference and limited size transfer, but no quality or runtime advantage over nearest feasible.This conclusion is stated for the unified comparison tests.
  • B. Unified Comparison of Heuristic and Neural Policies: 0.47% was the selected-checkpoint improvement from MLP–PPO over BC, whereas Transformer–PPO worsened the BC objective by 2.50%.These values refer to the selected checkpoints, not the five-run averages.
  • C. Robustness Across Independent Training Seeds: Seeds 2031–2035 repeated the complete BC–PPO pipeline with fixed training, validation, and test scenarios to isolate initialization, minibatch, and action-sampling variability.Each selected policy was evaluated on the same 20 unseen scenarios.
  • C. Robustness Across Independent Training Seeds: 400 evaluations completed every request without invalid actions across the independent-seed experiments.The reported evaluations covered the five training seeds and selected policies.
  • C. Robustness Across Independent Training Seeds: Mean ± SD values were computed over 20 paired scenarios, with adjusted p-values from two-sided exact sign tests against the full framework using Holm correction.This describes the statistical reporting protocol for the seed comparison.
  • C. Robustness Across Independent Training Seeds: 2.50% was the average PPO improvement for the Transformer, while PPO changed the MLP little on average and produced greater Transformer seed variability.Mean ± SD objectives were 429.489±1.689 for MLP–PPO, 426.968±9.358 for Transformer–BC, and 416.308 ± 16.983 for Transformer–PPO; nearest feasible remained best.

D. Ablation and Statistical Analysis · E. Scenario-Scaling Performance

Ablation results identify the full framework as the strongest variant, with reassignment penalties providing the only Holm-corrected significant effect. Policies transferred feasibly from 30 to 80 requests without retraining, but nearest feasible remained superior in objective and runtime.

  • D. Ablation and Statistical Analysis: The common reference objective was D + 0.10W + 2.00Nasg + 1.00Nseq across all ablation variants.The decision-rule weights did not change the evaluation objective.
  • D. Ablation and Statistical Analysis: 4.83%, 3.84%, and 3.25% increases followed removal of commitment, reassignment penalty, and resequencing penalty, respectively; only reassignment remained significant after Holm correction (p = 0.007).The full framework achieved the lowest mean objective.
  • D. Ablation and Statistical Analysis: p = 0.875, p = 0.188, and p = 0.188 showed no significant differences for the three five-run comparisons.The comparisons were MLP–BC versus MLP–PPO, Transformer–BC versus Transformer–PPO, and MLP–PPO versus Transformer–PPO; limited power leaves effects seed-dependent.
  • E. Scenario-Scaling Performance: Without retraining, trained policies were evaluated on instances with 30, 50, and 80 requests.All methods completed every request and satisfied the implemented capacity constraints.
  • E. Scenario-Scaling Performance: Nearest feasible retained the lowest objective and runtime at every tested scale.The scaling comparison covered three scenarios per problem size.

F. Common-Protocol Comparison of Principal Methods · V. CONCLUSION

Under a common commitment-aware protocol, all methods remained feasible, while nearest feasible led overall routing quality and rolling horizon led waiting and makespan at much higher computational cost. The framework combines feasibility masking, route commitments, stability metrics, learned policies, and benchmarking, but strong heuristics remained superior overall.

  • F. Common-Protocol Comparison of Principal Methods: All five methods used identical 20-scenario inputs and protected completed, active, and near-term route decisions under the common commitment-aware protocol.The comparison included nearest-feasible assignment, waiting-aware insertion, MLP–PPO, Transformer–PPO, and rolling-horizon optimization.
  • F. Common-Protocol Comparison of Principal Methods: All methods completed every request without invalid actions or commitment violations.Previously selected MLP–PPO and Transformer–PPO checkpoints were evaluated without retraining, while rolling horizon used a one-second solution limit per replanning event.
  • F. Common-Protocol Comparison of Principal Methods: Nearest feasible achieved the lowest objective, distance, disruption, and runtime, whereas rolling horizon achieved the lowest waiting and makespan.Rolling horizon required greater distance, more sequence changes, and substantially higher computation.
  • F. Common-Protocol Comparison of Principal Methods: 35.5 and 29.8 times faster: MLP–PPO and Transformer–PPO, respectively, than rolling horizon, although heuristics remained fastest.No method was best across all performance criteria.
  • V. CONCLUSION: The framework integrates deterministic feasibility masking, fixed-prefix/flexible-suffix commitments, MLP and Transformer policies trained by BC and PPO, and rolling-horizon benchmarking.Reassignment and resequencing are measured separately to capture replanning disruption.
  • V. CONCLUSION: 18 scenarios: nearest feasible was best, achieving the lowest mean objective and outperforming learned policies in distance, waiting, stability, makespan, and runtime.All methods completed every request without invalid assignments across the 20-scenario benchmark.
  • V. CONCLUSION: 2.5%: PPO improved the Transformer across five training runs, while having little average effect on the MLP and greater seed variability.The reported improvement applies to the Transformer across the five independent training runs.
  • V. CONCLUSION: Tens of milliseconds: learned policies produced feasible routes and transferred from 30 to 80 requests without retraining, but did not outperform the strongest heuristic.Nearest feasible again led combined objective and route disruption, while rolling horizon led waiting times and makespan at substantially higher computational cost.
Loading 2608.13799v1…