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

Suyu Liu, Zhiguang Cao, Shanshan Feng, Yew-Soon Ong

Introduction

The Vehicle Routing Problem (VRP) is a notoriously NP-hard logistical challenge. Recently, deep learning models utilizing self-attention and reinforcement learning have emerged as fast, flexible solvers. To handle the messy reality of logistics, researchers are increasingly building "multi-task foundation models" capable of solving various VRP variants—such as routes with time windows, capacity limits, or backhauls—simultaneously.

However, current neural solvers embed all nodes into a standard Euclidean (flat) space. This paper identifies a major flaw in this approach: routing graphs naturally possess curved geometries. For instance, tightly clustered customers resemble spherical (positive curvature) spaces, while diverging delivery routes resemble tree-like, hyperbolic (negative curvature) spaces. Forcing these heterogeneous structures into a flat Euclidean space distorts distance information, leading the model to make suboptimal routing decisions.

To address this, the authors introduce a plug-and-play mixed-curvature pre-training framework that splits feature spaces into multiple non-Euclidean subspaces with learnable curvatures. By integrating this module into existing multi-task VRP solvers, the framework achieves state-of-the-art generalization and solution quality on both synthetic and real-world routing benchmarks.

The Mixed-Curvature Framework

To allow the neural network to natively "understand" geometry, the authors propose a Mixed-Curvature Module designed to be inserted into existing architectures like POMO-MTL, MVMoE, and RouteFinder.

  • Mixed-Curvature Linear Transformation: The standard feature space is partitioned into $C$ smaller subspaces. Each subspace is assigned a learnable curvature parameter $\kappa$. If $\kappa < 0$, the space behaves hyperbolically; if $\kappa > 0$, it behaves spherically; and if $\kappa = 0$, it remains Euclidean.
  • Manifold Mapping: Because standard neural network optimizers (like Adam) expect flat spaces, the model uses mathematical operations called exponential and logarithmic maps. These project features back and forth between the curved manifolds and flat tangent spaces, allowing standard linear transformations to occur without losing geometric integrity.
  • Curvature Mix-up Strategy: The authors identified a "curvature mismatch" across network layers. To prevent performance drops as features move from shallow to deep layers, they introduce a Mix-up technique that interpolates features between consecutive layers, smoothing the flow of geometric information.

Experimental Setup

The framework was evaluated across a robust set of routing scenarios:

  • Synthetic VRP Variants: 24 distinct VRP tasks generated with 50 and 100 nodes, combining constraints like Capacity (C), Open Route (O), Backhauls (B), Duration Limits (L), and Time Windows (TW). Depending on the baseline, 6 or 16 tasks were used for training, with the rest reserved for zero-shot and few-shot evaluation.
  • Real-World Benchmarks: Standard operations research datasets, including CVRPLib (Sets A, B, E, F, M, P, and the large-scale Set-X) for Capacitated VRPs, and Set-Solomon for VRPs with Time Windows.

Key Insights & Discoveries

  • VRPs are inherently non-Euclidean: Using the Ollivier-Ricci curvature metric, the authors prove that almost every node in a VRP instance carries either positive (contractive) or negative (expansive) curvature. Purely Euclidean models are fundamentally mismatched to this data.
Curvature distribution in CVRP instances showing non-Euclidean properties.
  • Network depth dictates geometry: Visualizing the learned curvatures reveals a fascinating pattern. Shallow encoder layers naturally learn negative (hyperbolic) curvatures to capture sparse, local, tree-like connections. As the network gets deeper and aggregates global graph information, the subspaces shift toward positive (spherical) curvatures.
  • Reduced spatial distortion: By calculating the "distortion rate" between the original graph distances and the learned feature distances, the authors show that mixed-curvature spaces preserve the true spatial relationships of the input graph much more faithfully than Euclidean-only models.
  • Geometry over parameter count: In an ablation study, adding the exact same number of parameters to the baseline models using standard Euclidean layers actually dropped performance in most cases. This proves the gains stem specifically from the non-Euclidean geometric design, not just increased model capacity.

Performance & Results

  • In-Distribution & Zero-Shot: The mixed-curvature augmented MVMoE model achieved state-of-the-art performance across 6 seen tasks and 10 unseen tasks (zero-shot), consistently outperforming its Euclidean counterpart.
  • Real-World Gains: On the challenging, large-scale Set-X benchmark, the mixed-curvature POMO-MTL model reduced the optimality gap from 29.65% to 16.61% compared to the baseline POMO model.
  • Few-Shot Learning: When fine-tuned on just 10,000 instances of unseen tasks, the mixed-curvature models adapted faster and achieved lower optimality gaps than standard models.

Limitations and Future Directions

While highly effective, the approach has a few limitations. The frequent use of exponential and logarithmic mapping operations introduces computational overhead, increasing inference time by roughly 7-10%. Additionally, the complex manifold mathematics can occasionally cause numerical instability during training.

Currently, the study focuses on instances up to a few hundred nodes and manually allocates an equal number of dimensions (16) to each curvature subspace. Future work will explore applying this framework to massive-scale VRPs (~10,000 nodes) and using Neural Architecture Search (NAS) to dynamically allocate subspace dimensions based on the specific routing task at hand.

Summary updated

Abstract

Solving various types of vehicle routing problems (VRPs) using a unified neural solver has garnered significant attentions in recent years. Despite their effectiveness, existing neural multi-task solvers often fail to account for the geometric structures inherent in different tasks, which may result in suboptimal performance. To address this limitation, we propose a curvature-aware pre-training framework. Specifically, we leverage mixed-curvature spaces during the feature fusion stage, encouraging the model to capture the underlying geometric properties of each instance. Through extensive experiments, we evaluate the proposed pre-training strategy on existing neural multi-task solvers across a variety of testing scenarios. The results demonstrate that the curvature-aware pre-training approach not only enhances the generalization capabilities of existing neural VRP solvers on synthetic datasets but also improves solution quality on real-world benchmarks.
BibTeX
@inproceedings{liu2025mixed,
  author = {Suyu Liu and Zhiguang Cao and Shanshan Feng and Yew-Soon Ong},
  title = {{A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=JsPyLqCgks},
}
Figure