ETHC-VRC: Explicit Time-State Representation and Hybrid Constraint Handling for Time-Windowed Vehicle Routing Construction

Abstract

Abstract

Learning-based routing for the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) must let a policy visit infeasible states in training, yet deploy routes that provably respect every time window under stated assumptions. In existing deep reinforcement learning (DRL) methods, however, time information serves a single constraint-handling mode, fixed for training and inference. We propose ETHC-VRC, a DRL construction method whose explicit time state is shared by the decoder context and the hard time-window mask, so that a policy trained with soft penalties can be decoded under this mask without retraining; its hybrid constraint strategy decodes each instance in both modes and keeps the lower-cost solution. On 20- to 100-node instances, greedy decoding solves 10,000 instances within seconds on a GPU at a lower hybrid cost than the greedily decoded DRL baselines (not significantly against MVMoE at 100 nodes). Sampling 1280 solutions per mode lowers it by another 3.8–4.9% at 0.07–0.32 s per instance, to within 2.1–4.3% of OR-Tools run for 10–120 s per instance and below OR-Tools at equal time. In zero-shot generalization across five scales, greedy decoding stays ahead of TPA-Reward on all 15 training–test combinations and of MVMoE, which has 5.3 times the parameters, on 8. A single model thus offers an explicit quality–latency trade-off, which we expect to suit both latency-critical and quality-critical logistics applications.