A Sequential Constructive Reinforcement Learning Approach to Heterogeneous and Dynamic Multi-Vehicle Routing

Abstract

Efficient vehicle routing is a fundamental problem in logistics and automated transportation systems, particularly in real-world settings where heterogeneous vehicle fleets operate under dynamic demand arrivals and stochastic travel conditions. Most existing methods are designed for static or homogeneous scenarios and struggle to scale when vehicle heterogeneity, evolving demands, and travel-time uncertainty must be jointly considered due to combinatorial complexity and inter-vehicle coupling. This paper proposes a lightweight deep reinforcement learning–based routing framework that reformulates multi-vehicle routing as a sequential decision-making process via a Sequential Route Construction strategy, enabling online re-optimization without high-dimensional joint action spaces. The proposed model jointly encodes road-network structure, global fleet-level states, and vehicle-specific attributes of the currently planning vehicle, allowing heterogeneous fleets to be coordinated under dynamic and stochastic environments. To ensure feasibility and training stability, feasibility-aware action masking and a Decision Sequence Equivalence (DSE) scheme are incorporated. Experimental results demonstrate that the proposed framework achieves competitive solution quality and high service fulfillment across heterogeneous and dynamic routing scenarios; compared with the strongest OR-Tools baseline in each setting, its inference-time search reduces objective values by 0.6–2.2% on HVRP and 0.8–1.7% on DSVRP while maintaining 0.991–1.000 fulfillment ratios with 0.495–2.019 s inference time.