Research map / Label-efficient and robust learning / Recognition and long-tail

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver

ICML 2025 · Label-efficient and robust learning › Recognition and long-tail · approach: Correspondence and causal representation learning · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a mixed-curvature (hyperbolic/Euclidean/hyperspherical subspace) module with Mix-up layer interpolation that is plugged into existing multi-task VRP neural solvers (POMO-MTL, MVMoE, MVMoE-L, RouteFinder) to improve in-distribution, zero-shot, few-shot and real-world performance.

Problem

Existing neural multi-task VRP solvers use Euclidean embedding and feature spaces, which may not capture the heterogeneous geometric (node-level curvature) structure of VRP instances, limiting performance and generalization across VRP variants.

Approach

Split each feature space into subspaces with learnable curvatures (hyperbolic, Euclidean, hyperspherical) using Exp/Log maps for linear transformations, add a learnable Mix-up interpolation between consecutive encoder layers to handle curvature mismatch, and insert this module into existing neural VRP solvers as a plug-in.

Key results

• On 6 seen VRP tasks (N=100), Mixed-MVMoE-L beats MVMoE-L on all 6 tasks, and Mixed-MVMoE achieves the lowest gaps among baselines in the in-distribution test (e.g., CVRP N=50 gap 0.865% vs MVMoE 0.896%).
• On 10 unseen tasks, Mixed-MVMoE reports state-of-the-art zero-shot gaps on all 10 tasks at both scales (e.g., VRPBL N=100 gap 1.264% vs MVMoE 1.346%).
• With RouteFinder backbone trained on 16 tasks, RF-TE with the mixed-curvature module achieves the lowest gap on all 16 tasks at both node sizes.

Measured effects reported in the paper

Surprising findings

• Naively increasing parameters with Euclidean replacement (Euc-X) often yields worse performance, suggesting gains come from the curvature geometry rather than capacity.
• Naively propagating non-Euclidean features into attention degrades performance, motivating the layer-wise Mix-up interpolation.

Limitations

• Exponential and logarithmic map operations add extra time cost and can cause numerical instability.
• Does not consider large-scale instances (around 10,000 nodes).
• Fixed 16 dimensions per curvature subspace; neural architecture search for subspace allocation not explored.

Experimental setup

Datasets: synthetic VRP instances (6 training variants, 16 variants for RouteFinder setting) CVRPLib set-X Solomon set-VRPTW CVRPLib sets A, B, E, F, M, P, X

Benchmarks: 24 VRP variants (6 seen, 10 unseen) VRPBLTW and OVRPBLTW few-shot CVRPLib set-X Solomon VRPTW CVRPLib sets A, B, E, F, M, P, X

Metrics: optimality gap (%) objective value running time distortion rate

Baselines: HGS LKH3 OR-Tools POMO-MTL MVMoE MVMoE-L RouteFinder (RF-X)

Builds on: POMO POMO-MTL MVMoE RouteFinder Mixed-curvature product manifolds

Closest papers by meaning

• Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDP (NeurIPS 2025 · similarity 0.91)
• MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts (ICML 2024 · similarity 0.90)
• SPACE: Unifying Symmetric and Asymmetric Routing Problems for Generalist Neural Solver (NeurIPS 2026 · similarity 0.89)
• CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention (ICML 2025 · similarity 0.87)
• Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.86)
• SHIELD: Multi-task Multi-distribution Vehicle Routing Solver with Sparsity and Hierarchy (ICML 2025 · similarity 0.86)