CARD: Coupled Asymmetric Role-and-Distance in Real-World Vehicle Routing

Deep reinforcement learning has achieved strong performance in vehicle routing problems (VRPs), yet existing methods mostly ignore both distance and role asymmetries in real-world VRPs, with a few addressing only one. We identify that these two asymmetries are inherently coupled: existing solvers that handle only one degrade more under combined shifts than under each shift separately. We propose CARD, a Coupled Asymmetric Role-and-Distance framework that eliminates this coupling by jointly handling both asymmetries. For asymmetric distance, CARD uses an attention mechanism that explicitly takes both the original and transposed cost matrices as input, while implicitly encoding role distinctions via its MLP scorer. For asymmetric roles, CARD introduces a role-aware training paradigm that operates on the role-reversed view alongside the original view, regularizing the policy through shared gradients. CARD consistently outperforms state-of-the-art neural solver RADAR across four VRP variants, with larger gains under more severe asymmetry, and achieves 5× training speedup to the same performance level. Crucially, CARD remains robust on real-world routing benchmarks across a wide range of distribution shifts without retraining.