Neural Periodic Reoptimization for Dynamic Vehicle Routing

Dynamic vehicle routing requires repeated route revision as new requests arrive during vehicle execution. Neural construction solvers offer a fast alternative to repeated combinatorial search, but static training does not account for the residual routing states encountered at deployment, which depend jointly on request arrivals, past routing decisions, and irrevocable dispatch commitments. We propose Neural Periodic Reoptimization (NPR), a framework that aligns neural routing solvers with a prescribed periodic execution protocol. NPR represents execution histories as residual routing problems and trains the solver on states encountered during its own protocol-constrained reoptimization rollouts. Its Commitment-Consistent Decoding intersects a commitment mask with the solver's native feasibility mask to preserve committed route prefixes, enabling reoptimization without external search or repair. Experiments with POMO and ReLD on problems with 100-1,000 customers show consistent improvements over static training. For clustered demand with Poisson arrivals at 1,000 customers, NPR reduces ReLD's gap to ALNS from 40.77% to 3.92%. On 122 public DVRP instances, NPR achieves a mean gap of 1.78%. Further experiments demonstrate compatibility with pairwise preference training, transfer across spatial and temporal distributions and degrees of dynamism, and applicability to customer time windows.