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

# Dynamic Multi-Depot Vehicle Routing with Online Requests: Event-Driven Transformer–DRL and Rolling-Horizon Benchmarking
Source: [https://arxiv.org/html/2608.13799](https://arxiv.org/html/2608.13799)
Gerald M\. KnappThanks:Faezeh Ardali and Gerald M\. Knapp are with the Department of Industrial Engineering, Louisiana State University, Baton Rouge, LA, USA \(e\-mail: fardal1@lsu\.edu; gknapp@lsu\.edu\)\.

###### 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\.

###### Index Terms:

Dynamic multi\-depot vehicle routing, dynamic vehicle routing, Transformer reinforcement learning, online service requests, rolling\-horizon optimization\.

## IIntroduction

Vehicle routing is a fundamental decision problem in transportation, distribution, and service operations\. It determines how a fleet of vehicles should serve geographically distributed customers while satisfying requirements such as vehicle capacity, service demand, route duration, and depot assignment\. Vehicle Routing Problems \(VRPs\) arise in applications including last\-mile delivery, field service, technician dispatch, mobile healthcare, and emergency logistics\[[8](https://arxiv.org/html/2608.13799#bib.bib4)\]\. Classical VRPs assume that all requests are known before dispatch, whereas practical systems often receive new requests after vehicle operations have begun\[[16](https://arxiv.org/html/2608.13799#bib.bib7)\]\. The Dynamic Vehicle Routing Problem \(DVRP\) addresses this setting by allowing requests and operational states to evolve over time\[[10](https://arxiv.org/html/2608.13799#bib.bib9)\]\. In the multi\-depot case, the dispatcher must repeatedly determine which vehicle and depot should serve each request while accounting for changing vehicle locations, capacities, service statuses, and customer waiting times\. The resulting D\-MDVRP is therefore a sequential decision problem rather than a single static routing task\.

### I\-ARelated Work and Positioning

Dynamic routing methods commonly respond to newly revealed requests through local insertion, event\-driven or periodic replanning, and rolling\-horizon reoptimization\[[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)\]\. Beyond classical approaches, emerging quantum optimization frameworks have also targeted combinatorial engineering problems through QUBO\-based formulations\[[12](https://arxiv.org/html/2608.13799#bib.bib15)\]; while promising, their practical use for many real\-world engineering problems remains constrained\. Fast insertion rules revise routes locally, whereas rolling\-horizon methods repeatedly reoptimize the currently available requests and constraints at successive decision epochs, generally at greater online computational cost\[[16](https://arxiv.org/html/2608.13799#bib.bib7)\]\.

Learning\-based dispatch provides an alternative in which policies are trained offline and evaluated rapidly during operation\. Such approaches have been applied to dynamic and uncertain VRPs, post\-disaster damage assessment and repair scheduling, event\-driven crew dispatch, and autonomous resource\-allocation problems\[[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)\]\. Related work has also applied Transformer\-based learning to combinatorial scheduling and evaluated transfer to larger problem instances without retraining\[[4](https://arxiv.org/html/2608.13799#bib.bib3)\]\. Transformer architectures use attention to model dependencies among encoded elements, and related dispatch work has used them to capture high\-dimensional system states and temporal dependencies\[[15](https://arxiv.org/html/2608.13799#bib.bib6),[2](https://arxiv.org/html/2608.13799#bib.bib1)\]\. In the present setting, however, online deployment also requires explicit feasibility handling and repeated route reconstruction as new information arrives\.

Disruption\-management studies further emphasize that real\-time replanning should balance operational quality against deviations from an existing plan\[[5](https://arxiv.org/html/2608.13799#bib.bib12),[7](https://arxiv.org/html/2608.13799#bib.bib13)\]\. Related rolling\-horizon scheduling work has similarly combined near\-term freeze windows with resequencing penalties to balance responsiveness and schedule stability under evolving information\[[11](https://arxiv.org/html/2608.13799#bib.bib14)\]\. Motivated by these considerations, the present framework protects completed, active, and near\-term decisions and reports vehicle reassignment and predecessor change separately rather than treating every route modification as an undifferentiated change\.

The contribution is an integrated framework rather than a new routing, attention, or reinforcement\-learning algorithm\. It combines an event\-driven D\-MDVRP environment, deterministic feasibility masking, behavior\-cloned MLP and Transformer policies with PPO fine\-tuning, fixed\-prefix and flexible\-suffix route commitments, and separate reassignment and resequencing measures\. Heuristics, learned policies, and rolling\-horizon optimization are then evaluated under the same feasibility, commitment, objective, scenario, and runtime protocol\. Its main distinction is the common stability\-aware comparison of components usually studied separately\.

The main contributions of this paper are an event\-driven D\-MDVRP environment with deterministic feasibility masking, MLP and Transformer policies trained using behavior cloning and PPO, fixed\-prefix/flexible\-suffix commitments with separate reassignment and resequencing measures, and common\-protocol comparisons with heuristics and rolling\-horizon optimization\.

## IIDynamic Routing Model and Assumptions

We consider a dynamic service\-routing environment in which capacitated vehicles operate from multiple depots\. An initial subset of requests is known before dispatch, while additional requests are revealed during route execution\. The routing state is updated after request arrivals, vehicle arrivals, service starts, and service completions\. Completed services, active movements, and near\-term committed decisions remain fixed, while eligible requests in the flexible route portions may be reassigned or reordered\.

### II\-ADynamic Multi\-Depot Service Network

Let𝒟\\mathcal\{D\},𝒦\\mathcal\{K\}, and𝒩\\mathcal\{N\}denote the depot, vehicle, and request sets, respectively\. Vehiclek∈𝒦k\\in\\mathcal\{K\}has home depotd⁡\(k\)∈𝒟d\(k\)\\in\\mathcal\{D\}and capacityQkQ\_\{k\}, while𝒩t⊆𝒩\\mathcal\{N\}\_\{t\}\\subseteq\\mathcal\{N\}contains the requests revealed by timett\.

Each requesti∈𝒩i\\in\\mathcal\{N\}is represented by the 10\-dimensional normalized feature vector

ξ~i\(t\)=\[\\displaystyle\\widetilde\{\\xi\}\_\{i\}\(t\)=\\bigg\[xiL,yiL,qiQmax,si15,pi3,aiThor,\\displaystyle\\frac\{x\_\{i\}\}\{L\},\\,\\frac\{y\_\{i\}\}\{L\},\\,\\frac\{q\_\{i\}\}\{Q\_\{\\max\}\},\\,\\frac\{s\_\{i\}\}\{15\},\\,\\frac\{p\_\{i\}\}\{3\},\\,\\frac\{a\_\{i\}\}\{T\_\{\\mathrm\{hor\}\}\},\(1\)min⁡\{max⁡\(t−ai,0\),Thor\}Thor,cistat​\(t\)5,k¯i\(t\),δipen\(t\)\]\.\\displaystyle\\frac\{\\min\\\{\\max\(t\-a\_\{i\},0\),T\_\{\\mathrm\{hor\}\}\\\}\}\{T\_\{\\mathrm\{hor\}\}\},\\,\\frac\{c\_\{i\}^\{\\mathrm\{stat\}\}\(t\)\}\{5\},\\,\\bar\{k\}\_\{i\}\(t\),\\,\\delta\_\{i\}^\{\\mathrm\{pen\}\}\(t\)\\bigg\]\.Here,LL,QmaxQ\_\{\\max\}, andThorT\_\{\\mathrm\{hor\}\}are the coordinate, capacity, and time scales\. The features describe location, demand, service duration, priority, arrival time, waiting time, request status, assigned vehicle, and pending status\. The status codecistat​\(t\)∈\{0,…,5\}c\_\{i\}^\{\\mathrm\{stat\}\}\(t\)\\in\\\{0,\\ldots,5\\\}represents unrevealed, pending, assigned, traveling, serving, and completed requests\. The assigned\-vehicle feature is zero when unassigned and otherwise equals\(kiasg​\(t\)\+1\)/\|𝒦\|\(k\_\{i\}^\{\\mathrm\{asg\}\}\(t\)\+1\)/\|\\mathcal\{K\}\|, whileδipen​\(t\)\\delta\_\{i\}^\{\\mathrm\{pen\}\}\(t\)equals one only for pending requests\. Unrevealed requests remain in the fixed\-size representation but are excluded by the padding and feasibility masks\.

Vehiclekkis represented by the nine\-dimensional feature vector

ν~k\(t\)=\[\\displaystyle\\widetilde\{\\nu\}\_\{k\}\(t\)=\\bigg\[xk​\(t\)L,yk​\(t\)L,Qkrem​\(t\)Qk,Qkused​\(t\)Qk,ckstat​\(t\)2,\\displaystyle\\frac\{x\_\{k\}\(t\)\}\{L\},\\,\\frac\{y\_\{k\}\(t\)\}\{L\},\\,\\frac\{Q\_\{k\}^\{\\mathrm\{rem\}\}\(t\)\}\{Q\_\{k\}\},\\,\\frac\{Q\_\{k\}^\{\\mathrm\{used\}\}\(t\)\}\{Q\_\{k\}\},\\,\\frac\{c\_\{k\}^\{\\mathrm\{stat\}\}\(t\)\}\{2\},\(2\)r¯kcur\(t\),nk​\(t\)N,d⁡\(k\)max⁡\{1,\|𝒟\|−1\},Dk​\(t\)L​N\]\.\\displaystyle\\bar\{r\}\_\{k\}^\{\\mathrm\{cur\}\}\(t\),\\,\\frac\{n\_\{k\}\(t\)\}\{N\},\\,\\frac\{d\(k\)\}\{\\max\\\{1,\|\\mathcal\{D\}\|\-1\\\}\},\\,\\frac\{D\_\{k\}\(t\)\}\{LN\}\\bigg\]\.The features describe current location, remaining and used capacity, operating status, active request, flexible\-route length, home depot, and cumulative distance\. The vehicle\-status codeckstat​\(t\)∈\{0,1,2\}c\_\{k\}^\{\\mathrm\{stat\}\}\(t\)\\in\\\{0,1,2\\\}represents idle, traveling, and serving states\. The current\-request feature is zero when no request is active and otherwise equals\(rkcur​\(t\)\+1\)/N\(r\_\{k\}^\{\\mathrm\{cur\}\}\(t\)\+1\)/N\.

Each vehicle route begins and ends at its home depot and contains its ordered assigned requests\. Executed, active, and committed portions remain fixed, whereas the flexible suffix may be revised during replanning\. Euclidean distance and the corresponding constant\-speed travel time are used in the numerical experiments\. Request attributes and arrival times follow the scenario settings described in Section[IV](https://arxiv.org/html/2608.13799#S4)\.

### II\-BEvent\-Driven Requests and Route Commitments

New requests are added to the revealed set at their arrival events\. Each revealed request is pending, assigned, active, or completed\. Assigned requests are further classified as fixed or flexible\. The fixed set contains the next protected request of each vehicle and any request scheduled to begin service within the commitment horizonHcommitH^\{\\mathrm\{commit\}\}; active travel and service are protected automatically\.

Each route is therefore represented by a fixed prefix and a flexible suffix,𝒫k​\(t\)=𝒫kfix​\(t\)⊕𝒫kflex​\(t\)\\mathcal\{P\}\_\{k\}\(t\)=\\mathcal\{P\}\_\{k\}^\{\\mathrm\{fix\}\}\(t\)\\oplus\\mathcal\{P\}\_\{k\}^\{\\mathrm\{flex\}\}\(t\)\. Only the flexible suffix may be reassigned or reordered\. At each operational event, the environment updates request statuses, vehicle locations, capacities, availability, waiting times, and remaining routes\. Common scenario seeds ensure identical operating conditions across methods\.

## IIIEvent\-Driven Learning Framework for Dynamic Vehicle Routing

The D\-MDVRP is formulated as an event\-driven sequential decision problem\. Under common state, action, and reward definitions, deterministic feasibility and route\-commitment rules are combined with MLP and Transformer policies trained by behavior cloning and PPO\.

### III\-ASequential Decision Model

The routing environment is a finite\-horizon Markov decision process whose state contains the request, vehicle, depot, and global features\. The global features are normalized simulation time, revealed, completed, and pending\-request proportions, replanning count, and cumulative route changes\.

Requests progress through the unrevealed, pending, assigned, traveling, serving, and completed states\. At a replan, fixed prefixes remain unchanged and requests in the previous flexible suffix return to the pending set\. Each action assigns one pending request and appends it to a vehicle’s reconstructed suffix\. Construction ends when no revealed pending request remains; unrevealed requests wait until arrival, and there is no separate stop or defer action\.

Vehicle load is initialized from completed, active, and committed demand and updated after every assignment\. The mask prevents capacity violations and preserves sufficient residual fleet capacity\. If pending requests remain but all actions are masked, the state is declared infeasible\. Previous vehicle assignments and predecessors are stored before replanning; newly revealed requests incur no change penalty, whereas changes to previously planned requests are finalized after reconstruction\.

### III\-BMasked MLP and Transformer Policies

At each decision, the actor scores every vehicle–request pair\. The base instances contain four vehicles and 30 requests, producing 120 candidate actions\. Invalid logits are set to negative infinity before softmax or greedy selection\. A pair is valid only if the request is revealed, pending or flexibly assigned, not completed, active, committed, or previously selected during the current reconstruction, and feasible for the selected vehicle\. Invalid actions therefore receive zero probability during BC, PPO, validation, and testing\.

#### III\-B1MLP Actor and Critic

The MLP actor represents each pair using 10 request, nine vehicle, six global, and five pair\-specific features\. The pair\-specific features are nearest distance, incremental distance, predicted waiting time, route\-change indicator, and route length\. A shared→→→130\\\!\\rightarrow\\\!64\\\!\\rightarrow\\\!32\\\!\\rightarrow\\\!1ReLU network scores all pairs\. The critic pools the elementwise mean and maximum of feasible candidate vectors and applies a→→→160\\\!\\rightarrow\\\!64\\\!\\rightarrow\\\!32\\\!\\rightarrow\\\!1Tanh network\.

#### III\-B2Transformer Actor and Critic

The Transformer uses 30 request, four vehicle, and two depot tokens with feature dimensions 10, nine, and six, respectively\. Depotddis represented by

\[xdL,ydL,dmax⁡\{1,\|𝒟\|−1\},ndhome\|𝒦\|,tThor,1\],\\small\\left\[\\frac\{x\_\{d\}\}\{L\},\\,\\frac\{y\_\{d\}\}\{L\},\\,\\frac\{d\}\{\\max\\\{1,\|\\mathcal\{D\}\|\-1\\\}\},\\,\\frac\{n\_\{d\}^\{\\mathrm\{home\}\}\}\{\|\\mathcal\{K\}\|\},\\,\\frac\{t\}\{T\_\{\\mathrm\{hor\}\}\},\\,1\\right\],\(3\)wherendhomen\_\{d\}^\{\\mathrm\{home\}\}is the number of vehicles based at depotdd\. Separate linear projections map the request, vehicle, and depot features todmodel=32d\_\{\\mathrm\{model\}\}=32\. Learned token\-type and position embeddings and a projected six\-dimensional global vector are added to the tokens\. The encoder has one layer, four attention heads, feedforward dimension 64, ReLU activation, and zero dropout; unrevealed requests are zeroed and excluded through the padding mask\.

For each vehicle–request pair, the encoded vehicle, request, and global vectors and the five edge features form a 101\-dimensional vector, which is processed by a shared→→1101\\\!\\rightarrow\\\!64\\\!\\rightarrow\\\!1ReLU scorer\. The Transformer critic uses the elementwise mean and maximum of the visible 10\-dimensional request features, all nine\-dimensional vehicle features, all six\-dimensional depot features, and the five\-dimensional features of feasible edges, together with the six global features\. The resulting dimension is2​\(10\+9\+6\+5\)\+6=66,2\(10\+9\+6\+5\)\+6=66,and the critic applies a→→→166\\\!\\rightarrow\\\!64\\\!\\rightarrow\\\!32\\\!\\rightarrow\\\!1Tanh network\.

### III\-CRoute Commitment, Stability, Objective, and Reward

For the principal heuristic and neural\-policy benchmark, the evaluation objective is

Jeval=D\+0\.10​W\+2\.00​Nchg,\\small J\_\{\\mathrm\{eval\}\}=D\+0\.10W\+2\.00N\_\{\\mathrm\{chg\}\},\(4\)whereDDis total executed distance including depot returns,WWis total customer waiting time in customer\-minutes, andNchgN\_\{\\mathrm\{chg\}\}counts previously planned flexible requests whose vehicle–predecessor pair changes at a replanning event\. The coefficients have units of distance per customer\-minute and distance per route change\. Average and maximum waiting, makespan, completion, and runtime are reported separately\.

PPO uses incremental distance, predicted waiting, and the corresponding action\-level change indicator:

rtdense\\displaystyle r\_\{t\}^\{\\mathrm\{dense\}\}=−0\.01​\(Δ​Dt\+0\.10​w^i,t\+2\.00​Itchg\),\\displaystyle=\-0\.01\\left\(\\Delta D\_\{t\}\+0\.10\\widehat\{w\}\_\{i,t\}\+2\.00I\_\{t\}^\{\\mathrm\{chg\}\}\\right\),rTcorr\\displaystyle r\_\{T\}^\{\\mathrm\{corr\}\}=−0\.01​Jeval−∑t=0Trtdense,∑t=0Trt=−0\.01​Jeval\.\\displaystyle=\-0\.01J\_\{\\mathrm\{eval\}\}\-\\sum\_\{t=0\}^\{T\}r\_\{t\}^\{\\mathrm\{dense\}\},\\hskip 18\.49988pt\\sum\_\{t=0\}^\{T\}r\_\{t\}=\-0\.01J\_\{\\mathrm\{eval\}\}\.\(5\)Thus, dense rewards provide intermediate feedback while the undiscounted episode reward remains exactly aligned with the evaluation objective\. PPO usesγ=0\.99\\gamma=0\.99, so the timing of intermediate costs may affect the discounted return\.

For the commitment\-aware comparison, disruption is separated into vehicle reassignment and predecessor change:

Jstab=D\+0\.10​W\+2\.00​Nasg\+1\.00​Nseq,J\_\{\\mathrm\{stab\}\}=D\+0\.10W\+2\.00N\_\{\\mathrm\{asg\}\}\+1\.00N\_\{\\mathrm\{seq\}\},\(6\)whereNasgN\_\{\\mathrm\{asg\}\}andNseqN\_\{\\mathrm\{seq\}\}count flexible requests whose vehicle and predecessor change, respectively\. A request may contribute to both terms\.

### III\-DBehavior Cloning and PPO Fine\-Tuning

The MLP and Transformer policies are trained by behavior cloning \(BC\) followed by PPO fine\-tuning\.

#### III\-D1Behavior\-Cloning Dataset Construction

Each BC sample contains the complete state, deterministic mask, and expert vehicle–request action; one sample is recorded per expert decision, and all data splits are scenario\-disjoint\. The MLP expert is waiting\-aware insertion\. Its training, validation, and held\-out seeds are10001000–10111011,20002000–20032003, and30003000–30053005, yielding 4,525 training and 1,528 validation samples\.

At each decision, the Transformer expert first forms the set𝒞t\\mathcal\{C\}\_\{t\}of unique actions proposed by nearest feasible, cheapest append, and waiting\-aware insertion\. It then selects the candidate\(k,i\)∈𝒞t\(k,i\)\\in\\mathcal\{C\}\_\{t\}minimizing

Sk,ihyb=\\displaystyle S\_\{k,i\}^\{\\mathrm\{hyb\}\}=\{\}0\.55​Δ​dk,iL\+0\.30​\(0\.75\+0\.25​pi\)​w^k,iThor\\displaystyle 0\.55\\frac\{\\Delta d\_\{k,i\}\}\{L\}\+0\.30\(0\.75\+0\.25p\_\{i\}\)\\frac\{\\widehat\{w\}\_\{k,i\}\}\{T\_\{\\mathrm\{hor\}\}\}\+0\.10​Ik,ichg\+0\.04​QkplanQk\+0\.01​nkN,\\displaystyle\+0\.10I\_\{k,i\}^\{\\mathrm\{chg\}\}\+0\.04\\frac\{Q\_\{k\}^\{\\mathrm\{plan\}\}\}\{Q\_\{k\}\}\+0\.01\\frac\{n\_\{k\}\}\{N\},\(7\)whereΔ​dk,i\\Delta d\_\{k,i\}is incremental distance,w^k,i\\widehat\{w\}\_\{k,i\}is predicted waiting time,Ik,ichgI\_\{k,i\}^\{\\mathrm\{chg\}\}is the route\-change indicator,QkplanQ\_\{k\}^\{\\mathrm\{plan\}\}is the current planned cumulative load, andnkn\_\{k\}is the planned route length\. Scores are rounded to 12 decimal places for deterministic comparison, and ties are resolved using the smallest flattened vehicle–request action index\. Transformer training, validation, and held\-out seeds are41004100–41114111,51005100–51035103, and61006100–61056105, yielding 4,266 training and 1,372 validation samples\.

The actors use masked cross\-entropy and retain the checkpoint with minimum validation cross\-entropy\. Table[I](https://arxiv.org/html/2608.13799#S3.T1)summarizes the principal BC settings\.

TABLE I:Behavior\-cloning configurations\.
#### III\-D2PPO Fine\-Tuning

The selected BC actor initializes PPO\. Separate Adam optimizers are used for the actor and critic, with generalized advantage estimation, normalized advantages, and the standard clipped PPO loss\. Table[II](https://arxiv.org/html/2608.13799#S3.T2)reports the complete principal settings\.

TABLE II:PPO training configurations\.MLP training, validation, and held\-out seeds are40004000–40234023,50005000–50035003, and60006000–60056005; the corresponding Transformer seeds are72007200–72117211,82008200–82038203, and92009200–92059205\. After each iteration, greedy validation retains the actor–critic pair with the lowest mean objective\. BC is iteration zero, so PPO replaces it only after validation improvement; held\-out and common\-protocol scenarios are excluded from checkpoint selection\.

### III\-EEvent\-Driven Operation and Rolling\-Horizon Benchmark

The simulator advances directly among request arrivals, vehicle arrivals, service starts, and service completions\. When replanning is required, active and committed prefixes are retained, flexible requests return to the pending set, and cumulative loads are initialized from completed, active, and committed demand\. Feasible actions are then selected until no revealed pending request remains\. The reconstructed suffixes and their assignment and sequence changes are finalized before operations resume\.

Training is offline\. During testing, a learned policy requires only the current state, one forward evaluation per decision, and deterministic feasibility checks; request arrivals do not trigger retraining\.

The rolling\- baseline uses the same event states and fixes completed, active, and committed route segments\. Flexible requests may be reassigned and resequenced subject to capacity constraints\. Each solve is limited to one second, and the best feasible incumbent returned within this limit is implemented\. These incumbents do not necessarily represent proven optimal solutions\. Solver optimality\-gap statistics were not recorded and are therefore unavailable\.

## IVNumerical Results

This section evaluates the event\-driven dynamic routing framework in terms of solution feasibility, routing performance, scalability, route stability, and online computation time\. The experiments compare dynamic insertion heuristics, behavior\-cloned neural policies, PPO\-fine\-tuned policies, and a time\-limited rolling\-horizon optimization baseline\.

### IV\-AExperimental Setup

Synthetic Euclidean instances use vehicle capacity 30 and fixed scenario seeds\. Small, medium, and large cases contain\(2,4,18,12\)\(2,4,18,12\),\(3,6,30,20\)\(3,6,30,20\), and\(4,8,48,32\)\(4,8,48,32\)depots, vehicles, initial requests, and dynamic requests, respectively, giving 30, 50, and 80 total requests\. Dynamic requests arrive in four waves\. Scaling results are averaged over three scenarios per size, using seeds1200012000–1200212002,1300013000–1300213002, and1400014000–1400214002for the small, medium, and large cases, respectively\. The MLP is applied directly across sizes\. For the Transformer, the request, vehicle, and depot blocks of the learned position embeddings are linearly interpolated separately, while all projection, attention, and scoring weights remain unchanged; no scale\-specific retraining is performed\.

The unified heuristic and neural\-policy benchmark uses 20 unseen scenarios with seeds1000010000–1001910019and the objective in \([4](https://arxiv.org/html/2608.13799#S3.E4)\)\. The common\-protocol experiment reuses the same scenario seeds and generated request realizations but evaluates nearest feasible, waiting\-aware, MLP–PPO, Transformer–PPO, and rolling horizon in the commitment\-aware environment with a 15\-minute commitment horizon and the objective in \([6](https://arxiv.org/html/2608.13799#S3.E6)\)\. Consequently, differences between the two result tables arise from the commitment and stability protocol rather than from different scenario samples\. Previously selected neural checkpoints are applied without retraining\.

Experiments use Python 3\.8\.4 and PyTorch 2\.4\.1 on an 11th Gen Intel\(R\) Core\(TM\) i7\-1165G7 CPU at 2\.80 GHz with 32 GB RAM, without GPU acceleration\. Rolling horizon uses OR\-Tools 9\.8\.3296 with SCIP 8\.0\.4, one thread, and a one\-second limit\. End\-to\-end replanning time includes state construction, all sequential decisions, masking, route updates, and stability accounting; rolling\-horizon timing additionally includes model construction, optimization, and route extraction\. Training, model loading, and simulated operations are excluded\. The timing set contains 3,726 replanning events, and every rolling\-horizon call returned a feasible incumbent\. Source code, experiment scripts, and reference outputs used in this study are publicly available in the accompanying GitHub repository\[[3](https://arxiv.org/html/2608.13799#bib.bib16)\]\.

Random selects uniformly from feasible pairs; nearest feasible minimizes endpoint\-to\-request distance; cheapest append minimizes incremental distance; and waiting\-aware minimizes incremental distance plus0\.100\.10times predicted waiting and2\.002\.00times the change indicator\. The Hybrid expert uses the weighted score defined in the training subsection\. Waiting\-aware and Hybrid were selected as BC teachers before final testing to provide multi\-criteria demonstrations rather than to reproduce the retrospectively strongest test heuristic\.

### IV\-BUnified Comparison of Heuristic and Neural Policies

Table[III](https://arxiv.org/html/2608.13799#S4.T3)reports the mean and sample standard deviation over 20 common test scenarios\. All methods achieved 100% request completion under the common feasibility rules, and no invalid actions were selected\.

TABLE III:Unified routing benchmark\.BC denotes behavior cloning; Trans\. denotes Transformer\.

Nearest feasible achieved the lowest objective,346\.13346\.13, was best in 18 of 20 scenarios, and outperformed all learned policies in distance, waiting, makespan, route changes, and runtime\. Its mean runtime was0\.1560\.156ms/action versus0\.5380\.538–0\.8670\.867ms/action for the learned policies\. In these tests, the learned policies offered no quality or runtime advantage over the nearest feasible\.

For the selected checkpoints, MLP–PPO improved the BC objective by0\.47%0\.47\\%, whereas Transformer–PPO worsened it by2\.50%2\.50\\%\. Across the five independent runs discussed next, the corresponding average PPO changes were0\.13%0\.13\\%for the MLP and a2\.50%2\.50\\%improvement for the Transformer, with higher Transformer variability\. The learned policies instead offer feasible millisecond inference and limited size transfer, not better performance than the strongest heuristic\.

### IV\-CRobustness Across Independent Training Seeds

The complete BC–PPO pipeline was repeated for seeds20312031–20352035using fixed training, validation, and test scenarios, thereby isolating initialization, minibatch, and action\-sampling variability\. Each selected policy was evaluated on the same 20 unseen scenarios\.

![Refer to caption](https://arxiv.org/html/2608.13799v1/training_seed_objective_bw.png)Fig\. 1:Combined objective across five independent BC–PPO training runs\.All 400 evaluations completed every request without invalid actions\. Mean objectives were430\.057±2\.513430\.057\\pm 2\.513for MLP–BC,429\.489±1\.689429\.489\\pm 1\.689for MLP–PPO,426\.968±9\.358426\.968\\pm 9\.358for Transformer–BC, and416\.308±16\.983416\.308\\pm 16\.983for Transformer–PPO\. PPO changed the MLP little on average and improved the Transformer by2\.50%2\.50\\%, with greater seed variability\. Nearest feasible remained best\.

### IV\-DAblation and Statistical Analysis

The waiting\-aware policy was evaluated on the same 20 scenarios using the full framework and variants without near\-term commitment, reassignment penalty, or resequencing penalty\. All variants were evaluated using the common reference objectiveD\+0\.10​W\+2\.00​Nasg\+1\.00​NseqD\+0\.10W\+2\.00N\_\{\\mathrm\{asg\}\}\+1\.00N\_\{\\mathrm\{seq\}\}, regardless of the decision\-rule weights\.

TABLE IV:Ablation of route commitment and stability penalties\.Values are mean±\\pmSD over 20 paired scenarios\. Adjustedpp\-values use two\-sided exact sign tests against the full framework with Holm correction\.

The full framework achieved the lowest mean objective\. Removing commitment, reassignment penalty, and resequencing penalty increased it by4\.83%4\.83\\%,3\.84%3\.84\\%, and3\.25%3\.25\\%, respectively; only removal of the reassignment penalty remained significant after Holm correction \(p=0\.007p=0\.007\)\.

Exact Wilcoxon tests across the five training runs found no significant differences for MLP–BC versus MLP–PPO \(p=0\.875p=0\.875\), Transformer–BC versus Transformer–PPO \(p=0\.188p=0\.188\), or MLP–PPO versus Transformer–PPO \(p=0\.188p=0\.188\)\. These five\-pair tests have limited power, so PPO and architecture effects remain seed\-dependent\.

### IV\-EScenario\-Scaling Performance

The trained policies were applied without retraining to instances containing 30, 50, and 80 requests\. All methods completed every request and satisfied the implemented capacity constraints\. Table[V](https://arxiv.org/html/2608.13799#S4.T5)provides the comparison with the strongest heuristic, while Fig\.[2](https://arxiv.org/html/2608.13799#S4.F2)highlights Transformer–PPO size transfer\.

TABLE V:Scaling means over three scenarios per size: objective per request/runtime in ms per action\.![Refer to caption](https://arxiv.org/html/2608.13799v1/transformer_ppo_scaling_bw_clean.png)Fig\. 2:Transformer–PPO objective and decision time across problem sizes\.Nearest feasible retained the lowest objective and runtime at every scale\. Transformer–PPO completed all instances without retraining, but its objective per request increased from14\.2114\.21to17\.7417\.74and its runtime from0\.950\.95to4\.364\.36ms/action as the instance size increased from 30 to 80 requests\. This shows feasible size transfer over the tested range, but no advantage over nearest feasible\.

TABLE VI:Common\-protocol results over 20 paired scenarios \(mean±\\pmsample SD\)\.All methods achieved 100% completion without invalid actions or commitment violations\. Slash\-separated columns report average/maximum waiting and reassignment/sequence changes\.

### IV\-FCommon\-Protocol Comparison of Principal Methods

The five principal methods were evaluated over the same 20 independently generated test scenarios using the common commitment\-aware protocol\. For each scenario, nearest\-feasible assignment, waiting\-aware insertion, MLP–PPO, Transformer–PPO, and rolling\-horizon optimization received identical request arrivals, customer attributes, vehicle states, depot locations, capacities, and operational events\. The same completed, active, and near\-term route decisions were protected for every method, and all results were calculated using the objective in \([6](https://arxiv.org/html/2608.13799#S3.E6)\)\.

The previously selected MLP–PPO and Transformer–PPO checkpoints were applied without retraining\. The rolling\-horizon method optimized the assignment and sequence of the currently flexible requests subject to the same commitment and capacity constraints, with a one\-second solution limit at each replanning event\. Table[VI](https://arxiv.org/html/2608.13799#S4.T6)reports the mean and sample standard deviation over the 20 paired scenarios\.

All methods completed every request without invalid actions or commitment violations\. Nearest feasible achieved the lowest objective, distance, disruption, and runtime\. Rolling horizon achieved the lowest waiting and makespan but required greater distance, more sequence changes, and substantially higher computation\. MLP–PPO and Transformer–PPO were approximately35\.535\.5and29\.829\.8times faster than rolling horizon, respectively, although the heuristics remained fastest\. No method was best across all of these performance criteria\.

## VConclusion

This paper presented a stability\-aware event\-driven framework for dynamic multi\-depot routing that combines 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\.

Across the 20\-scenario benchmark, all methods completed every request without invalid assignments\. Nearest feasible achieved the lowest mean objective, was best in 18 scenarios, and outperformed the learned policies in distance, waiting, stability, makespan, and runtime\. Across five training runs, PPO had little average effect on the MLP and improved the Transformer by approximately2\.5%2\.5\\%, but with greater seed variability\.

Under the common protocol, nearest feasible again 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 produced feasible routes within tens of milliseconds and transferred from 30 to 80 requests without retraining, but did not outperform the strongest heuristic\.

Overall, the results demonstrate the value of integrating feasibility, route commitments, and stability measures into dynamic\-routing policies while emphasizing the importance of strong heuristic baselines\. Future work will consider multi\-size training, improved rewards, time windows, heterogeneous fleets, time\-dependent travel, and real transportation networks\.

## References

- \[1\]F\. Amani, F\. Ardali, and A\. Kargarian\(2026\)Event\-driven deep RL dispatcher for post\-storm distribution system restoration\.In2026 IEEE Texas Power and Energy Conference \(TPEC\),USA\.External Links:[Document](https://dx.doi.org/10.1109/TPEC67884.2026.11513160)Cited by:[§I\-A](https://arxiv.org/html/2608.13799#S1.SS1.p2.1)\.
- \[2\]F\. Amani, F\. Ardali, and A\. Kargarian\(2026\)Learning optimal crew dispatch for grid restoration following an earthquake\.IEEE Transactions on Smart Grid\.External Links:[Document](https://dx.doi.org/10.1109/TSG.2026.3700512)Cited by:[§I\-A](https://arxiv.org/html/2608.13799#S1.SS1.p2.1)\.
- \[3\]F\. Ardali and G\. M\. Knapp\(2026\)Dynamic mdvrp transformer–drl: reproducibility code\.Note:[https://github\.com/Faezeh1994/dynamic\-mdvrp\-transformer\-drl](https://github.com/Faezeh1994/dynamic-mdvrp-transformer-drl)GitHub repositoryCited by:[§IV\-A](https://arxiv.org/html/2608.13799#S4.SS1.p3.1)\.
- \[4\]F\. Ardali, M\. A\. Nyelele, and G\. M\. Knapp\(2026\)A deep reinforcement learning \(drl\)\-based transformer method for solving the open shop scheduling problem\.arXiv preprint arXiv:2606\.13682\.Cited by:[§I\-A](https://arxiv.org/html/2608.13799#S1.SS1.p2.1)\.
- \[5\]R\. Eglese and S\. Zambirinis\(2018\)Disruption management in vehicle routing and scheduling for road freight transport: a review\.TOP26\(1\),pp\. 1–17\.External Links:[Document](https://dx.doi.org/10.1007/s11750-018-0469-4)Cited by:[§I\-A](https://arxiv.org/html/2608.13799#S1.SS1.p3.1)\.
- \[6\]M\. El Jaouhari, G\. Bencheikh, and G\. Bencheikh\(2025\)Metaheuristic and reinforcement learning techniques for solving the vehicle routing problem: a literature review\.Journal of Traffic and Transportation Engineering \(English Edition\)\.Cited by:[§I\-A](https://arxiv.org/html/2608.13799#S1.SS1.p1.1)\.
- \[7\]M\. Gmira, M\. Gendreau, A\. Lodi, and J\. Potvin\(2021\)Managing in real\-time a vehicle routing plan with time\-dependent travel times on a road network\.Transportation Research Part C: Emerging Technologies132,pp\. 103379\.External Links:[Document](https://dx.doi.org/10.1016/j.trc.2021.103379)Cited by:[§I\-A](https://arxiv.org/html/2608.13799#S1.SS1.p3.1)\.
- \[8\]G\. D\. Konstantakopoulos, S\. P\. Gayialis, and E\. P\. Kechagias\(2022\)Vehicle routing problem and related algorithms for logistics distribution: a literature review and classification: gd konstantakopoulos et al\.\.Operational research22\(3\),pp\. 2033–2062\.Cited by:[§I](https://arxiv.org/html/2608.13799#S1.p1.1)\.
- \[9\]M\. Meraliyev, C\. Turan, S\. Kadyrov, and U\. Sadyk\(2025\)A comprehensive survey of methods and challenges of vehicle routing problem with uncertainties\.Mathematics13\(23\),pp\. 3782\.Cited by:[§I\-A](https://arxiv.org/html/2608.13799#S1.SS1.p1.1)\.
- \[10\]W\. Pan and S\. Q\. Liu\(2023\)Deep reinforcement learning for the dynamic and uncertain vehicle routing problem\.Applied Intelligence53\(1\),pp\. 405–422\.Cited by:[§I](https://arxiv.org/html/2608.13799#S1.p1.1)\.
- \[11\]H\. K\. Parmar and S\. Raman\(2026\)Smart manufacturing scheduling under data latency: a rolling\-horizon two\-stage milp framework for oem–tier\-1 coordination\.Journal of Manufacturing and Materials Processing10\(4\),pp\. 142\.Cited by:[§I\-A](https://arxiv.org/html/2608.13799#S1.SS1.p3.1)\.
- \[12\]A\. Rajabi, M\. Hasanzadeh, and A\. Kargarian\(2026\)A distributed quantum approximate optimization algorithm simulator for engineering design optimization\.arXiv preprint arXiv:2606\.26297\.Cited by:[§I\-A](https://arxiv.org/html/2608.13799#S1.SS1.p1.1)\.
- \[13\]M\. Soleymani, M\. Bonyani, and C\. Wang\(2024\)Simulation of autonomous resource allocation through deep reinforcement learning\-based portfolio\-project integration\.Automation in Construction162,pp\. 105381\.Cited by:[§I\-A](https://arxiv.org/html/2608.13799#S1.SS1.p2.1)\.
- \[14\]H\. Torkaman, E\. O\. Boateng, J\. Solanki, and A\. Srivastava\(2026\)An integrated two\-stage deep\-learning tool for rapid post\-hurricane damage identification and repair scheduling\.arXiv preprint arXiv:2606\.29117\.Cited by:[§I\-A](https://arxiv.org/html/2608.13799#S1.SS1.p2.1)\.
- \[15\]A\. Vaswani, N\. Shazeer, N\. Parmar, J\. Uszkoreit, L\. Jones, A\. N\. Gomez, Ł\. Kaiser, and I\. Polosukhin\(2017\)Attention is all you need\.Advances in neural information processing systems30\.Cited by:[§I\-A](https://arxiv.org/html/2608.13799#S1.SS1.p2.1)\.
- \[16\]J\. Zhang\(2025\)Pickup and delivery planning for the crowdsourced freight delivery routing problem\.PloS one20\(2\),pp\. e0318432\.Cited by:[§I\-A](https://arxiv.org/html/2608.13799#S1.SS1.p1.1),[§I](https://arxiv.org/html/2608.13799#S1.p1.1)\.