cs.LGNov 9, 2026

MixRoute: Rethinking Single-Distribution Training for Generalizable Neural Routing

Authors: Hang Yi, Ziwei Huang, Yining Ma, Zhiguang Cao

Organizations: Singapore Management University · Massachusetts Institute of Technology

Abstract

Neural Combinatorial Optimization (NCO) is a promising paradigm for solving routing problems, yet its generalization across diverse data distributions remains a critical bottleneck. Existing methods typically tackle cross-distribution generalization through complex multi-distribution training or intricate meta-learning schemes, implicitly presuming that single-distribution training yields a weak zero-shot baseline. In this paper, we demonstrate that the potential of single-distribution training has been substantially underestimated and can be unlocked by a simple architectural inductive bias: Mix Normalization. To approach this, we first construct a comprehensive benchmark spanning three representative routing problems and 179 fine-grained datasets, capturing diverse shifts in node coordinates, customer demands, capacity and time windows. Building on this benchmark, we propose MixRoute, a neural framework that adaptively combines normalization statistics at different granularities to mitigate varying distribution shifts. Trained exclusively on uniform distributions, MixRoute generalizes effectively to a wide range of unseen distributions without any distribution-specific adaptation. Extensive experiments demonstrate that MixRoute consistently achieves state-of-the-art zero-shot generalization. Our work revisits normalization as a parsimonious alternative for zero-shot generalization against complex training-adaptation schemes.

Figures & tables

Appendix figures & tables33 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Instance-Conditioned Adaptation for Large-scale Generalization of Neural Routing Solver

    May 3, 2024Changliang Zhou, Xi Lin, Zhenkun Wang +3Neural Network GeneralizationIntelligent Transportation Systems

  2. Towards Generalization-Oriented Models for Vehicle Routing Problems with Mixture-of-Experts

    May 26, 2026Changhao Miao, Yuntian Zhang, Tongyu Wu +2Reinforcement LearningAdaptive Model Routing

  3. Geometric Self-Supervised Pre-training for Neural Combinatorial Optimization

    Jul 31, 2026David Aguado, Daniel Fuertes, Carlos R. del-Blanco +1Traveling Salesperson ProblemSelf-Supervised Learning