DRL Fails to Outperform Heuristics in Dynamic Vehicle Routing

This research investigates solutions for the Dynamic Multi-Depot Vehicle Routing Problem (DM-DVRP), a complex logistics challenge involving online requests and evolving vehicle states. The study introduces an event-driven learning and benchmarking framework to compare various approaches, including Masked MLP and Transformer policies trained with behavior cloning and proximal policy optimization (PPO), against traditional dynamic insertion heuristics and time-limited rolling-horizon optimization. Despite the advanced nature of the deep reinforcement learning (DRL) policies, the findings indicate that they did not surpass the performance of simpler, yet robust, dynamic insertion heuristics. Specifically, the "nearest feasible" heuristic consistently achieved the lowest mean objective across 20 scenarios, demonstrating superior routing quality, reduced waiting times, and greater stability. While DRL policies maintained millisecond-level decision speeds and transferred to larger instances without retraining, they did not achieve better overall performance than the strongest heuristic. The rolling-horizon optimization method achieved the lowest waiting times and makespan but at a significantly higher computational cost. This suggests that for dynamic vehicle routing problems with online requests, well-designed heuristics can still provide more effective and computationally efficient solutions than current DRL approaches.