Towards Zero-Shot Neural Routing via Constraint Consequence Representation

Extending classical solvers for Vehicle Routing Problems (VRPs) to new constraints often requires tailored designs of solver components. While recent neural routing generalists reuse decision rules across variants, their learned representations typically remain tied to predefined constraint types. To enable zero-shot generalization to new constraints, we propose Constraint Consequence REpresentation (CoRE). Motivated by resource extension in classical labeling algorithms, CoRE expresses every constraint through its candidate-level consequences in one shared space, in which a learned heuristic is reused on new constraints without fine-tuning. We integrate this representation into a framework in which one learned scorer guides both construction and refinement. Experiments on 110 VRP variants demonstrate that our model, trained solely on small-scale instances, generalizes effectively to unseen constraint combinations, new constraints, varying constraint hardness, and large-scale instances. CoRE achieves a mean reference gap of 3.68% across 110 routing variants, with a substantial improvement over state-of-the-art neural methods and over prior constraint representations within the same framework. We further show that consequences keep preferred candidates feasible, leading to improved quality, and that our representation serves as a generic module that enhances autoregressive construction and extends to node-oriented problems.