SPACE: Unifying Symmetric and Asymmetric Routing Problems for Generalist Neural Solver
This work addresses the limitation of generalist neural solvers in handling asymmetric VRPs, which is crucial for real-world applications that involve both symmetric and asymmetric routing scenarios.
Existing generalist neural routing solvers struggle with asymmetric vehicle routing problems (VRPs) due to input inconsistencies and structural differences. SPACE introduces a Spatial Pivot-Aligned Coordinate-free Embedding framework that unifies node representation and solution generation across symmetric and asymmetric VRPs, achieving promising zero-shot generalization on 110 VRP variants (55 symmetric and 55 asymmetric).
Generalist neural routing solvers have shown great potential in solving diverse vehicle routing problems (VRPs) with a unified model. However, existing solvers are typically limited to symmetric settings or degrade in performance when switching to asymmetric settings due to input inconsistencies or inherent structural differences, substantially limiting their practicality in real-world scenarios that encompass both scenarios. To address this limitation, we define the spatial position of each node based on the relative distances to a specific set of pivots and further propose a Spatial Pivot-Aligned Coordinate-free Embedding (SPACE) framework that unifies node representation and solution generation across symmetric and asymmetric VRPs. Specifically, we construct a bidirectional Frechet representation using a novel furthest pivot sampling strategy to enable invariant node representations across distinct problem settings. Furthermore, we introduce a weight-decomposed adaptive decoding mechanism that decouples geometric perception from problem representations, mitigating the overfitting of constraint decisions to a specific geometry setting. Extensive experiments on 110 VRP variants, comprising 55 symmetric problems and their asymmetric counterparts, demonstrate that SPACE achieves promising zero-shot generalization in both symmetric and asymmetric VRPs.