Scalable knowledge-guided framework for large multi-depot vehicle routing

Solving the vehicle routing problem (VRP) in large-scale, multi-depot logistics is complex due to the intricate trade-offs between computational scalability and constraint satisfaction While deep reinforcement learning (DRL)-based approaches seem to be promising, they often struggle with the logical feasibility and interpretability required for real-world operations. We propose the Knowledge-Guided Collaborative Attention Framework (KGCAF), which combines depot-level profile-based decomposition with feasibility-aware graph attention and hybrid heuristic refinement. By employing a depot-level profile decomposition, it enables localized and parallelizable route construction while ensuring logical feasibility through explicit masking. KGCAF unifies learning-based initialization with time-budgeted heuristic optimization. Evaluations on multi-depot VRPTW benchmarks show KGCAF reduces total distance by up to 86%, cuts average time window violations from over 1000 to under 100, and outperforms decomposition-only or graph neural network (GNN)-only baselines in both sequential and parallel executions. These results demonstrate competitive or superior solution quality, strict feasibility adherence, and scalable performance, highlighting the framework's practicality for large-scale, real-world multi-agent routing.