Towards Generalization-Oriented Models for Vehicle Routing Problems with Mixture-of-Experts
For researchers and practitioners using DRL for combinatorial optimization, this work addresses the critical issue of distribution shift, though the gains are incremental over existing methods.
The paper tackles the problem of poor generalization of DRL-based Vehicle Routing Problem solvers under real-world distribution shifts. They propose R2E-IG, a mixture-of-experts model with instance-level gating and dynamic weight adaptation, achieving competitive performance on both in-distribution and out-of-distribution instances across synthetic and benchmark datasets.
In recent years, Deep Reinforcement Learning (DRL) has achieved substantial progress on Vehicle Routing Problems (VRPs). However, existing DRL-based methods are typically trained on instances generated from a uniform distribution, which limits their performance under real-world distribution shifts. In this paper, we aim to develop a generalization-oriented model that partitions the policy network into multiple modules and adaptively recombines modules to form specific policies during inference. Specifically, we propose Residual Refined Experts with Instance-level Gating (R2E-IG) to improve cross-distribution generalization. Our contributions are threefold: (1) We introduce a Residual Refined Expert (R2E) architecture that enhance expert expressiveness via residual refinement; (2) We design an instance-level gating mechanism that learns distribution-aware instance representations and routes inputs to suitable modules; (3) We propose a mixed-distribution training mechanism equipped with Dynamic Weight Adaption (DWA), which dynamically reweights training data from different distributions to emphasize more informative ones. Extensive experiments show that R2E-IG achieves competitive performance against state-of-the-art baselines on both in-distribution and out-of-distribution instances across synthetic and benchmark datasets. Moreover, R2E-IG is generic and can be easily integrated into existing DRL-based methods to further improve performance.