LPACR: Local Policy with Augmented Contextual Representations for Enhancing OOD Generalization in VRPs

Practical vehicle routing problem (VRP) instances exhibit significant variations in problem scale and intrinsic distribution, posing fundamental challenges to cross-scale and cross-distribution generalization capabilities of neural solvers. Although local policies are effective for cross-scale generalization, their restricted receptive fields lack global awareness. Meanwhile, we reveal that homogeneous training samples fail to cover diverse local topological structures that are crucial for cross-distribution generalization. In terms of learning paradigms, supervised learning (SL) suffers from objective misalignment, whereas reinforcement learning (RL) faces convergence instability. To overcome these limitations, we propose LPACR (Local Policy with Augmented Contextual Representations). We introduce a grid-based distribution compression method that leverages the spatial locality of VRP to encode grid-wise statistical information, thereby augmenting the contextual representation of the local policy. To enhance cross-distribution adaptability, we employ a multi-distribution training strategy that can encompass heterogeneous local topological structures. Furthermore, we train LPACR through a two-stage learning paradigm that synergizes SL and RL. Extensive experimental results on synthetic datasets and real-world benchmarks with diverse scales and distributions demonstrate LPACR's robust generalization capabilities.