A Deep Reinforcement Learning Algorithm for the Vehicle Routing Problem with Stochastic Demands and Outsourcing

This paper studies the vehicle routing problem with stochastic demands and outsourcing (VRP-SDO). It partitions customers between a fixed fleet and a common carrier, then estimates the dynamic routing cost of the committed subset with an offline-trained deep Q-network. The policy uses a graph attention network to aggregate customer and vehicle information for each acting vehicle. The authors report a 19.6% routing-cost reduction versus a state-of-the-art method, at least 29.6% versus classical heuristics, and a 13.7% improvement over a non-attention variant. Decisions are generated within minutes, while benchmarks without an offline estimator take over an hour.