MixRoute: Rethinking Single-Distribution Training for Generalizable Neural Routing
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
| Regime | ||||
|---|---|---|---|---|
| Tight | 20 | 0.050 | 0.250 | 0.450 |
| Medium | 50 | 0.020 | 0.100 | 0.180 |
| Loose | 250 | 0.004 | 0.020 | 0.036 |
| Benchmark | # Distributions | Problem Coverage | TSP | CVRP-specific | CVRPTW-specific | Open- | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| # Train | # Test | TSP | CVRP | CVRPTW | Coord. | Demand | Capacity | Width | Timing | Coupling | source | |
| AMDKD [ 4 ] | 3 | 4 | ✓ | ✓ | ✓ | ✓ | ||||||
| INViT [ 9 ] | 1 | 4 | ✓ | ✓ | ✓ | ✓ | ||||||
| Luo et al. [ 27 ] | multiple | 7 | ✓ | ✓ | ✓ | ✓ | ✓ | |||||
| Ours | 1 | 179 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| Node coordinate distributions | Problem-specific shifts | ||||||||||||
| Task | Annulus | Beta | Cluster | Expansion | Explosion | Gaussian | Grid | Implosion | Stripe | Demand | Capacity | TW | Total |
| TSP | 6 | 6 | 6 | 6 | 6 | 4 | 6 | 6 | 8 | — | — | — | 54 |
| CVRP | 6 | 6 | 6 | 6 | 6 | 4 | 6 | 6 | 8 | 5 | 5 | — | 64 |
| CVRPTW | 6 | 6 | 6 | 6 | 6 | 4 | 6 | 6 | 8 | — | — | 7 | 61 |
| In-dist. | Out-of-distribution: Node coordinate shifts | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Method (TSP) | Uniform | Annulus | Beta | Cluster | Expansion | Explosion | Gaussian | Grid | Implosion | Stripe | Avg | Time |
| LKH3 | — | — | — | — | — | — | — | — | — | — | — | 4.31s |
| Single-distribution training | ||||||||||||
| ELG | 0.66% | 0.79% | 1.03% | 2.45% | 0.79% | 0.57% | 1.03% | 1.12% | 0.96% | 1.70% | 1.11% | 3.26s |
| LEHD | 0.57% | 0.62% | 5.71% | 1.62% | 0.64% | 0.50% | 0.73% | 0.94% | 0.69% | 5.03% | 1.71% | 3.82s |
| INViT | 3.80% | 4.30% | 4.15% | 5.90% | 3.88% | 3.85% | 4.13% | 3.51% | 4.37% | 5.36% | 4.33% | 13.99m |
| In-dist. | Out-of-distribution: Demand distribution shifts | |||||||
|---|---|---|---|---|---|---|---|---|
| Method | Uniform | Small-biased | Large-biased | U-shaped | Mid-peak | Bimodal | Average Gap | Time |
| LKH3 | — | — | — | — | — | — | — | 1.63h |
| MatNet | -1.49% | 1.90% | -3.92% | -0.82% | -1.24% | -0.78% | -1.06% | 0.65s |
| MixRoute | -2.02% | 1.06% | -4.58% | -1.12% | -1.74% | -1.35% | -1.63% | 0.69s |
| Node coordinate distributions | CVRP-specific | |||||||||||||
| Method | Norms | Annulus | Beta | Cluster | Expansion | Explosion | Gaussian | Grid | Implosion | Stripe | Demand | Capacity | Avg | Time |
| LKH3 | — | — | — | — | — | — | — | — | — | — | — | — | — | — |
| POMO | IN (original) | 7.11% | 2.95% | 3.25% | 0.65% | -0.19% | 1.72% | 1.38% | -0.15% | 8.30% | 1.49% | 8.34% | 3.17% | 2.03s |
| MixRoute | IN+LN+NoNorm | -0.91% | 1.01% | 1.97% | -0.16% | -0.32% | 1.52% | 1.20% | -0.33% | 1.08% | 1.21% | 4.22% | 0.95% | 2.18s |
| MixRoute | IN+LN+BN | -0.87% | 1.11% | 1.82% | -0.13% | -0.28% | 1.36% | 1.18% | -0.30% | 1.13% | 1.24% | 3.36% | 0.88% | 2.30s |
| MixRoute | IN+LN+RMSNorm | -0.51% | 1.58% | 2.75% | -0.18% | -0.47% | 1.82% | 1.43% | -0.38% | 1.92% | 1.73% | 5.79% | 1.41% | 2.21s |
| Node coordinate distributions | CVRP-specific | ||||||||||||
| Method | Norms | Annulus | Beta | Cluster | Expansion | Explosion | Gaussian | Grid | Implosion | Stripe | Demand | Capacity | Avg |
| LKH3 | — | — | — | — | — | — | — | — | — | — | — | — | — |
| POMO | IN (original) | 7.11% | 2.95% | 3.25% | 0.65% | -0.19% | 1.72% | 1.38% | -0.15% | 8.30% | 1.49% | 8.34% | 3.17% |
| Statistic mixing | |||||||||||||
| Switch Norm | IN+LN | -0.67% | 1.76% | 2.47% | 0.02% | -0.20% | 1.51% | 1.24% | -0.17% | 1.39% | 1.41% | 9.72% | 1.68% |
| Switch Norm | IN+LN+BN | -0.68% | 1.17% | 1.90% | -0.11% | -0.28% | 1.45% | 1.18% | -0.30% | 1.57% | 1.22% | 8.98% | 1.46% |
| Topic | Section | Content |
|---|---|---|
| Multi-seed results | Appendix D | Seed variability of MixRoute. |
| Mechanism of MixNorm | Appendix E | How MixNorm responds to distributional shift. |
| Behavior of the adaptive gate | Appendix F | Gate weights across layers and distributions. |
| Related normalizations | Appendix G | Comparison with existing Mix Norm. |
| Normalizer choice | Appendix H | Effect of pool size and composition. |
Appendix figures & tables33 assets
Supplementary material from the paper’s appendix.
Appendix
| Node coordinate distributions | CVRP-specific | ||||||||||||
| Method | Norms | Annulus | Beta | Cluster | Expansion | Explosion | Gaussian | Grid | Implosion | Stripe | Demand | Capacity | Avg |
| LKH3 | — | — | — | — | — | — | — | — | — | — | — | — | — |
| POMO | IN (original) | 7.11% | 2.95% | 3.25% | 0.65% | -0.19% | 1.72% | 1.38% | -0.15% | 8.30% | 1.49% | 8.34% | 3.17% |
| POMO | LN | -0.38% | 4.09% | 2.85% | 0.03% | -0.20% | 2.14% | 1.43% | -0.28% | 2.25% | 1.59% | 5.79% | 1.76% |
| POMO | NoNorm | -0.61% | 1.68% | 3.24% | -0.11% | -0.27% | 2.73% | 1.34% | -0.30% | 2.01% | 1.47% | 4.35% | 1.41% |
| MixRoute | IN+LN+NoNorm | -0.91% | 1.01% | 1.97% | -0.16% | -0.32% | 1.52% | 1.20% | -0.33% | 1.08% | 1.21% | 4.22% | 0.95% |
| Annulus distribution variants | ||||||||
| Method | Area-uniform | Thin ring | Thick ring | Biased-in | Biased-out | Biased-azimuth | Average Gap | Time |
| LKH3 | — | — | — | — | — | — | — | 7.74s |
| Single-distribution training | ||||||||
| ELG | -0.10% | -2.44% | -0.21% | 0.08% | -0.31% | 6.40% | 0.31% | 4.35s |
| LEHD | 0.51% | -0.90% | 0.20% | 0.07% | 0.16% | 4.71% | 0.61% | 4.27s |
| BQ | 0.92% | -1.27% | 1.69% | 1.37% | 1.33% | 1.94% | 1.00% | 2.30m |
| Beta distribution variants | ||||||||
| Method | Edge | Corner | Center | Strong edge | Strong corner | Strong center | Average Gap | Time |
| LKH3 | — | — | — | — | — | — | — | 10.90s |
| Single-distribution training | ||||||||
| ELG | 1.21% | 2.05% | 1.87% | 1.28% | 5.59% | 2.28% | 2.10% | 4.18s |
| LEHD | 2.85% | 3.17% | 3.06% | 5.94% | 4.52% | 3.45% | 3.92% | 4.20s |
| BQ | 5.04% | 3.25% | 2.38% | 8.87% | 4.09% | 2.33% | 4.83% | 2.30m |
| Cluster distribution variants | ||||||||
| Method | Islands | Mega | Imbalanced | Overlap | Anisotropic | Bridge | Average Gap | Time |
| LKH3 | — | — | — | — | — | — | — | 13.56s |
| Single-distribution training | ||||||||
| ELG | 2.58% | 2.89% | 6.42% | 3.38% | 2.29% | 4.59% | 3.52% | 4.35s |
| LEHD | 3.59% | 3.53% | 4.55% | 3.41% | 3.68% | 5.30% | 3.96% | 4.26s |
| BQ | 3.67% | 2.30% | 3.08% | 2.59% | 3.20% | 2.42% | 2.90% | 2.30m |
| Grid distribution variants | ||||||||
| Method | Regular | Aniso | Rotate | Warp | Gauss | Broken | Average Gap | Time |
| LKH3 | — | — | — | — | — | — | — | 9.64s |
| Single-distribution training | ||||||||
| ELG | 2.01% | 0.89% | 1.74% | 1.70% | 1.77% | 1.72% | 1.65% | 4.12s |
| LEHD | 2.64% | 1.95% | 2.32% | 2.86% | 2.67% | 3.08% | 2.60% | 4.26s |
| BQ | 2.71% | 2.26% | 2.48% | 2.75% | 2.62% | 3.20% | 2.67% | 2.30m |
| Stripe distribution variants | ||||||||||
| Method | Rails | Solo | Comb | Spike | Bands | Mono | Flood | Core | Average Gap | Time |
| LKH3 | — | — | — | — | — | — | — | — | — | 16.39s |
| Single-distribution training | ||||||||||
| ELG | 1.58% | 2.48% | 1.53% | 3.40% | 1.19% | 2.18% | 1.80% | 2.60% | 2.02% | 5.57s |
| LEHD | 1.98% | 3.37% | 2.86% | 4.83% | 1.44% | 3.21% | 2.94% | 3.59% | 2.92% | 5.73 |
| BQ | 3.61% | 4.93% | 2.66% | 2.03% | 1.92% | 3.92% | 3.03% | 1.92% | 3.02% | 3.21m |
| Gaussian distribution variants | ||||||
| Method | Tight ( ) | Compact ( ) | Loose ( ) | Broad ( ) | Average Gap | Time |
| LKH3 | — | — | — | — | — | 7.73s |
| Single-distribution training | ||||||
| ELG | 4.35% | 2.29% | 1.80% | 1.61% | 2.16% | 2.74s |
| LEHD | 4.39% | 3.07% | 3.20% | 2.84% | 3.19% | 2.80s |
| BQ | 3.55% | 2.56% | 2.87% | 2.98% | 2.91% | 1.40m |
| Expansion distribution variants | ||||||||
| Method | Axial | Log | Wedge | Pinch | Shear | Squeeze | Average Gap | Time |
| LKH3 | — | — | — | — | — | — | — | 23.14s |
| Single-distribution training | ||||||||
| ELG | 0.59% | 0.16% | 1.35% | -0.22% | -0.28% | 4.10% | 0.85% | 4.17s |
| LEHD | 0.47% | 0.14% | 0.29% | 0.02% | -0.57% | 2.67% | 0.45% | 4.25s |
| BQ | 2.05% | 1.02% | 0.91% | 0.64% | 0.11% | 3.74% | 1.36% | 2.30m |
| Implosion distribution variants | ||||||||
| Method | Circle | Star | Multi | Line | Ellipse | Gradient | Average Gap | Time |
| LKH3 | — | — | — | — | — | — | — | 22.19s |
| Single-distribution training | ||||||||
| ELG | 0.46% | 0.16% | 0.31% | 0.40% | 0.41% | 0.01% | 0.29% | 4.12s |
| LEHD | 0.25% | -0.12% | 0.20% | 0.38% | 0.24% | -0.03% | 0.15% | 4.25s |
| BQ | 0.85% | 0.40% | 1.11% | 0.84% | 0.74% | 0.63% | 0.76% | 2.30m |
| Explosion distribution variants | ||||||||
| Method | Circle | Star | Multi | Ring | Ellipse | Gradient | Average Gap | Time |
| LKH3 | — | — | — | — | — | — | — | 23.41s |
| Single-distribution training | ||||||||
| ELG | 0.26% | 0.19% | 0.07% | 0.12% | 0.22% | 0.25% | 0.18% | 4.11s |
| LEHD | 0.51% | 0.26% | 0.08% | 0.35% | 0.35% | 0.41% | 0.33% | 4.26s |
| BQ | 0.65% | 0.69% | 0.78% | 1.01% | 0.86% | 0.81% | 0.80% | 2.30m |
| Demand distribution variants | |||||||
| Method | Small-biased | Large-biased | U-shaped | Mid-peak | Bimodal | Average Gap | Time |
| LKH3 | — | — | — | — | — | — | 10.48s |
| Single-distribution training | |||||||
| ELG | 2.21% | 1.82% | 2.23% | 1.60% | 1.89% | 1.94% | 4.48s |
| LEHD | 2.67% | 2.96% | 3.08% | 2.61% | 3.05% | 2.88% | 4.22s |
| BQ | 2.25% | 3.45% | 3.29% | 2.28% | 3.16% | 2.92% | 2.30m |
| Capacity setting | |||||||
| Method | Average Gap | Time | |||||
| LKH3 | — | — | — | — | — | — | 24.30s |
| Single-distribution training | |||||||
| ELG | 2.79% | 2.66% | 5.57% | 8.42% | 11.67% | 4.89% | 3.44s |
| LEHD | 4.37% | 3.23% | 3.25% | 2.80% | 5.60% | 3.97% | 3.55s |
| BQ | 7.66% | 1.61% | 2.57% | 2.97% | 6.24% | 5.18% | 2.51m |
| Method (CVRP) | Annulus | Expansion | Implosion | Explosion | Demand | Capacity |
|---|---|---|---|---|---|---|
| POMO | 7.11% | 0.65% | -0.15% | -0.19% | 1.49% | 8.34% |
| MixRoute (run 1) | -0.87% | -0.13% | -0.30% | -0.28% | 1.24% | 3.36% |
| MixRoute (run 2) | -0.59% | -0.25% | -0.50% | -0.48% | 1.36% | 4.05% |
| MixRoute (run 3) | -0.56% | -0.31% | -0.48% | -0.51% | 1.30% | 3.79% |
| MixRoute (run 4) | -0.57% | -0.30% | -0.51% | -0.55% | 1.33% | 3.40% |
| MixRoute (mean std) | -0.65 0.15% | -0.25 0.08% | -0.45 0.10% | -0.46 0.12% | 1.31 0.05% | 3.65 0.33% |
| Group | Model | L0 | L1 | L2 | L3 | L4 | L5 | Improv. | |
|---|---|---|---|---|---|---|---|---|---|
| 5% | POMO | 0.08 | 0.11 | 0.11 | 0.10 | 0.09 | 0.06 | ||
| MixRoute | 4.72 | 4.94 | 3.48 | 4.57 | 3.44 | 2.31 | 3.82 | +22.6% | |
| 1–5% | POMO | 0.04 | 0.05 | 0.04 | 0.03 | 0.02 | 0.01 | ||
| MixRoute | 1.35 | 1.45 | 1.01 | 1.15 | 0.91 | 0.67 | 1.06 | +3.7% | |
| 1% | POMO | 0.03 | 0.03 | 0.03 | 0.02 | 0.02 | 0.02 | ||
| MixRoute | 0.21 | 0.97 | 0.94 | 0.89 | 0.72 | 0.67 | 0.70 | +0.2% |
| Post-MHA | Post-FFN | |||||
|---|---|---|---|---|---|---|
| Layer | IN | LN | BN | IN | LN | BN |
| L0 | 0.43 | 0.01 | 0.57 | 0.03 | 0.26 | 0.71 |
| L1 | 0.19 | 0.40 | 0.41 | 0.30 | 0.47 | 0.23 |
| L2 | 0.28 | 0.15 | 0.58 | 0.00 | 0.99 | 0.01 |
| L3 | 0.20 | 0.13 | 0.67 | 0.00 | 0.70 | 0.30 |
| L4 | 0.03 | 0.05 | 0.91 | 0.05 | 0.64 | 0.32 |
| Epoch | IN | LN | BN |
|---|---|---|---|
| 500 | 0.21 | 0.23 | 0.56 |
| 2000 | 0.14 | 0.21 | 0.65 |
| 4000 | 0.11 | 0.18 | 0.71 |
| 6500 | 0.05 | 0.19 | 0.77 |
| IN | LN | BN | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Layer | U vs A | U vs S | A vs S | U vs A | U vs S | A vs S | U vs A | U vs S | A vs S |
| L0-attn | (6e-02) | 4e-37 | 4e-70 | 3e-33 | 4e-25 | 2e-89 | (5e-02) | 1e-31 | 3e-44 |
| L0-ffn | 7e-07 | 6e-29 | 1e-39 | 2e-50 | 8e-90 | 5e-195 | 4e-79 | 1e-105 | 2e-181 |
| L1-attn | (7e-02) | 1e-07 | 2e-155 | 5e-19 | 8e-10 | 2e-149 | 3e-06 | 9e-04 | 2e-13 |
| L1-ffn | 2e-55 | 1e-92 | 6e-189 | 3e-05 | 6e-04 | (2e-02) | 4e-61 | 4e-65 | 7e-162 |
| L2-attn | 2e-04 | 4e-58 | 2e-109 | 3e-70 | 3e-58 | 7e-119 | 1e-40 | 3e-13 | 2e-58 |
| Post-MHA | Post-FFN | |||||||
|---|---|---|---|---|---|---|---|---|
| Statistic | Tight | Compact | Loose | Broad | Tight | Compact | Loose | Broad |
| IN mean | 1.11 | 1.10 | 1.08 | 1.04 | 1.10 | 1.09 | 1.06 | 1.03 |
| LN mean | 1.05 | 0.95 | 0.91 | 0.87 | 0.92 | 0.93 | 0.95 | 0.96 |
| BN mean | 0.98 | 1.00 | 1.01 | 1.02 | 0.94 | 0.97 | 1.01 | 1.07 |
| IN std | 0.76 | 0.78 | 0.74 | 0.73 | 0.66 | 0.61 | 0.64 | 0.62 |
| LN std | 0.48 | 0.42 | 0.42 | 0.40 | 0.75 | 0.67 | 0.67 | 0.63 |
| Post-MHA | Post-FFN | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Statistic | 20 | 80 | 120 | 200 | 250 | 20 | 80 | 120 | 200 | 250 |
| IN mean | 0.53 | 1.39 | 1.71 | 1.90 | 1.93 | 0.84 | 0.99 | 0.95 | 0.90 | 0.88 |
| LN mean | 1.17 | 1.01 | 1.03 | 1.04 | 1.05 | 1.13 | 0.99 | 1.01 | 1.02 | 1.03 |
| BN mean | 1.01 | 0.95 | 0.91 | 0.89 | 0.88 | 1.07 | 1.08 | 1.21 | 1.37 | 1.43 |
| IN std | 0.49 | 1.36 | 1.47 | 1.60 | 1.65 | 1.31 | 0.89 | 0.97 | 1.17 | 1.23 |
| LN std | 0.81 | 1.07 | 1.13 | 1.13 | 1.11 | 1.48 | 0.93 | 0.95 | 1.08 | 1.14 |
| Node coordinate distributions | CVRP-specific | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Method | Annulus | Beta | Cluster | Expansion | Explosion | Gaussian | Grid | Implosion | Stripe | Demand | Capacity | Avg |
| LKH3 | — | — | — | — | — | — | — | — | — | — | — | — |
| SN | -0.68% | 1.17% | 1.90% | -0.11% | -0.28% | 1.45% | 1.18% | -0.30% | 1.57% | 1.22% | 8.98% | 1.46% |
| SN-affine | -0.86% | 1.12% | 1.83% | -0.07% | -0.28% | 1.40% | 1.12% | -0.26% | 1.06% | 1.31% | 8.01% | 1.31% |
| MixRoute (ours) | -0.87% | 1.11% | 1.82% | -0.13% | -0.28% | 1.36% | 1.18% | -0.30% | 1.13% | 1.24% | 3.36% | 0.88% |
| Method | Uniform | Annulus | Stripe | Demand | Capacity | Avg |
|---|---|---|---|---|---|---|
| POMO | -0.93% | 7.11% | 8.30% | 1.49% | 8.34% | 4.86% |
| MixRoute-IN+LN | -0.23% | 0.36% | 2.77% | 1.58% | 5.16% | 1.93% |
| MixRoute-IN+LN+BN | -1.03% | -0.87% | 1.13% | 1.24% | 3.36% | 0.77% |
| MixRoute-IN+LN+BN+No Norm | -1.04% | -0.53% | 1.29% | 1.18% | 3.18% | 0.82% |
| Method | Uniform | Annulus | Stripe | Demand | Capacity | Avg |
|---|---|---|---|---|---|---|
| POMO | -0.93% | 7.11% | 8.30% | 1.49% | 8.34% | 4.86% |
| MixRoute-IN+LN+BN | -1.03% | -0.87% | 1.13% | 1.24% | 3.36% | 0.77% |
| MixRoute-IN+BN+No Norm | -0.98% | -0.88% | 1.03% | 1.19% | 5.24% | 1.12% |
| MixRoute-LN+BN+No Norm | -1.01% | -0.68% | 1.81% | 1.52% | 3.71% | 1.07% |
| Type | Asset | License | Usage |
|---|---|---|---|
| Code | LKH3 [ 14 ] | BSD 3-Clause License | Evaluation (reference solver) |
| HGS [ 41 ] | MIT License | Evaluation (reference solver, CVRPTW) | |
| POMO [ 22 ] | MIT License | Backbone & Baseline | |
| MatNet [ 23 ] | MIT License | Backbone (ACVRP) | |
| ELG [ 11 ] | MIT License | Baseline | |
| LEHD [ 26 ] | MIT License | Baseline |
Neural Combinatorial Optimization
Neural combinatorial optimization uses neural networks to find high-quality solutions to discrete problems such as routing, scheduling, and graph partitioning.
See all 146 papers