A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
Authors: Suyu Liu
Zhiguang Cao
Shanshan Feng
Yew-Soon Ong
Venue: ICML 2025 poster (2025)
Keywords: Combinatorial Optimization
Constrained Optimization
Vehicle Routing Problems
Deep Reinforcement Learning
Primary area: optimization->discrete_and_combinatorial_optimization
TL;DR: We propose a geometric pre-training method to get a more powerful foundation model for various kinds of VRPs.

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.

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
Suyu Liu' Zhiguang Cao?
Shanshan Feng? Yew-Soon Ong' 14
Abstract
Sermighan-Helsgaue (LKH) (Lin & Kernighan, 1973; Hels- gaun, 2017), Hybrid Genetic Search (HGS) (Vidal, 2022) and OR-Tools (Perron & Didier, 2024). Despite the fact that these solvers have achieved remarkable performances, their reliance on hand-crafted rules and specialized domain knowledge may severely limit their abilities to generalize to more general problem types, especially the emerging VRP variants. Additionally, these solvers may become computa- tionally prohibitive when applied on large-scale instances.
Solving various types of vehicle routing prob- lems (VRPs) using unified neural solver has garnered significant attentions in recent years. De- spite their effecctivnness, 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 spaces during the feature fusion stage, encouraging the model to capture the un- derlying 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 sce- narios. The results demonstrate that the curvature- aware pre-training approach not only enhances the generalization capabilities of existing neural VRP solvers synthetic datasets but also improves solution quality on real-world benchmarks.
On the other hand, deep learning based neural solvers such as (Kool et al., 2019; Kwon et al., 2020; Zhou et al., 2023b;a; Goh et al., 2024; Zhang et al., 2025) require minimal hand- crafted rules and offer significantly much faster inference speeds. Typically, following the architecture of POMO (Kwon et al., 2020), these neural solvers often contain self- attention modules and utilize reinforcement learning as their optimization algorithms. Besides, hard masks are integrated into the attention mechanism to eliminate infeasible actions. Despite their efficiency and flexibility, these solvers primar- ily address relatively simple VRPs, and extending current frameworks to handle more complex problem types remains an under-explored area.
Recently, there has been a growing trend towards build- ing multi-task foundation models for solving various types of VRPs (Liu et al., 2024; Zhou et al., 2024; Berto et al., 2024; Huang et al., 2025). Although these models have demonstrated promising results, they largely overlook the geometric structures that widely exist in different tasks. As shown in Figure 1, VRP instances, despite being defined in Euclidean coordinates, exhibit node-level curvature distri- butions that cannot be faithfully captured in flat spaces: the Ollivier-Ricci curvature (defined in Eq. (15), Appendix. 1) which effectively quantifies geometric structures on dis- crete spaces like graphs or networks, reveals that almost every node carries either negative positive curvature, in- dicating that the underlying data contains structures in mixed-curvature space rather than a purely Euclidean one. Specifically, we observe that nodes are frequently situated in regions of either positive (contractive) or negative (ex- pansive) curvature spaces, which correlate with delivery patterns such as customer clustering or route divergence in the delivery map (Figure Appendix. 1). All of these factors
1. Introduction
Vehicle routing problems (VRPs) owing to its broad ap- plicability among various domains such as transportation service (Ge et al., 2019; Zhou et al., 2023a) and trajectory planning (Dantzig & Ramser, 1959; Min, 1989), have gar- nered great attentions in recent years. However, because of its NP-Hard complexity, obtaining optimal solutions within reasonable time is almost infeasible. Regarding to this, several heuristic solvers have been proposed, such as Lin-
'College of Computing and Data Science, Nanyang Technolog- ical University, Singapore "Scooo of Computing and Information Systems, Singapore Management University, Singapore 'Centre for Frontier Al Research, The Agency for Science, Technology and Research, Singapore "Centre for Frontier AI Research, Institute of High Performance Computing, Agency for Science, Technol- ogy and Research, Singapore. Correspondence to: Zhiguang Cao <zgcao sasoo@smuucciee edu.s"".
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
critical decision makings in solving vehicle routing problems. However, the embedding and feature transfor- mation spaces in current neural solvers are still confined to Euclidean geometric spaces where each point (or node) is treated uniformly, severely limiting their abilities to adapt to such heterogeneous geometries (Nickel & Kiela, 2017:
Count
Ganea et al., 2018; Liu et al., 2019; Chami et al., 2019; Desai et al., 2023). Indeed. prior work (Sala al., 2018) has shown that Euclidean spaces, regardless of dimension- ality, struggle to represent complex structures such as trees without incurring significant distortions. Fortunately, some deep learning methods on Riemannian manifolds (Nickel & Kiela, 2017; Ganea et al., 2018; Gu et al., 2018) have provided an alternative way to avoid these potential pitfalls.
Curvature
Curvature
(a) CVRP
(b) OVRP
Count 40
Count
19
In this work, we propose the first pre-training strategy that trains multi-task foundation models within mixed- curvature geometric space to solve various types of VRPs, which empowers the neural solvers with the ability to capture nuanced geometric information from inputs in a curvature- sensstive manner. Specifically, we partition the feature space of each encoder layer into multiple subspaces, each mapped to a geometric space of a specific curvature. Features from the previous layer are projected into these distinet curvature spaces and subsequently merged in the output stage. By leveraging the unique properties of non- Euclidean spaces such as hyperbolic (negative curvature) and hyperspherical (positive curvature) geometries, our ap- proach allows the model to effectively capture complex geometric patterns from problem instances, offering a novel way to enhance performance across wide range of VRPs. Accordingly, our contributions are summarized as follows:
.23 0.6 6.5
15 19
-500
-235 0.50 6.5
975
Curvature
Curvature
VRPB
(d) VRPL
Count
Count
-11 OR Co OS 1h Curvature
MAS 600 G2 15 335 Curvature
(e) VRPTW
(1) OVRPTW
Figure I. Histograms of curvatures for cach node across 6 VRP tasks. We utilize 1,000 instances for every task, cach containing 50 nodes, to visualize curvature distributions. The x-axis represents curvature values, while the y-axis denotes count of each value. The avg line indicates the average curvature across all nodes. We employ Ollivier-Ricci curvature (Ollivier, 2009) which is well- suited for measuring curvatures in discrete structures like graphs. For further details on this curvature, please refer to Appendix. It is demonstrated that almost every node in the dataset has either negative or positive curvature and the average curvature suggests that each task in the Euclidean space contains non- non-Euclidean ge- ometry information, motivating the use of mixed-curvature space. Visualizations of curvatures for other VRP tasks provided in Figure 4, Appendix. 1. Better viewed in color.
We investigate the multi-task VRP problem from a novel perspective by introducing mixed-curvature ge- ometric spaces, motivated by the diverse curvatures of nodes. To our knowledge, this is the first work to explore a curvature-awand neural solver for VRPs.
We propose a novel and practical pre-training paradigm that integrates spaces of varying curvatures, enabling the model to explore inherent geometric structures from the inputs for solving VRPs.
2. Related Work
VRP Solvers
Existing solvers for VRPs can be broadly classified into three categories: 1) Traditional Solvers: This cate- gory includes established methods such Lin-Kernighan- Helsgaun (LKH) algorithm (Lin & Kernighan, 1973), Hy- brid Genetic Search (HGS) (Vidal, 2022), and OR-Tools (Perron & Didier, 2024). These solvers leverage heuristic search algorithms and rely heavily on expert knowledge, which may limit their adaptabilities to new problem settings. 2) Neural Solvers: Building on early works like (Vinyals
Through extensive experiments, demonstrate that our proposed approach not only achieves remarkable improvements across various types of VRPs but also shows its strong adaptability to different architectures of multi-task solvers. In addition, results on real-world benchmarks further validate its effectiveness.
2

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
al., 2015), these methods employ deep learning itera- tively construct solutions. The introduction of self-attention (Vaswani et al., 2017) to VRPs (Kool et al., 2019; Kwon et al., 2020) has significantly improved solution quality. Subsequent progress, such as (Kim et al., 2022; Zhou et al., 2023b), focuses on training with varied data to enhance generalization to unseen scenarios. Recent developments include scaling to larger problem instances (Luo et al., 2023; Pan al., 2023; Ye et al., 2024; Cheng al., 2023) and exploring non-autoregressive decoding (Sun & Yang, 2023). However, these methods often rely on additional heuristic searches for particularly challenging or large-scale instances, which may limit the efficiency. 3) Hybrid Solvers: These ap- proaches combine the strength of neural approaches with tra- ditional heuristics to overcome their own limitations. Exam- ples include the adaptation of neural methods for candidate set generation (Xin et al., 2021), enhancing the flexibility and efficiency of classic architectures. Hybrid solvers like (Hottung& & Tierney, 2020; Hottung et al., 2021; Xin et al., 2021; Chalumeau et al., 2023; Ma et al., 2024; Chen et al., 2024) have demonstrated considerable success. However, these methods often require task-specific training, which hinders their ability to generalize across different VRPs.
2022; Moreira et al., 2024), language (Dai et al., 2021; Fan et al., 2024; Qu et al., 2024), audio (Hong et al., 2023) and data mining (Chami et al., 2019; Liu et al., 2019; Sun et al., 2021; Choudhary et al., 2024). On the other hand, hyper- spherical surfaces constrain data representations within a unit hypersphere. This property helps model achieve lower variances and better generalization abilities across a wide range of applications, including image classification (Liu et al., 201 7b;)), adversarial attack (Pang et al., 2020) and generative modeling (Qiu et al., 2023). Other works like (Gu et al., 2018; Wang et al., 2021; Sun et al., 2022; Cho et al., 2023; Wang et al., 2024; Fu et al., 2025) have explored a mixed-curvature environment where models process fea- tures across spaces with varying curvatures, which leverages the strengths of both hyperbolic and hyperspherical geome- tries into learning process. In contrast to all these works, ours focuses on learning diverse data representations for variants of VRPs, aiming to enhance the cross-task general- ization ability.
3. Preliminaries
We introduce essential definitions related to mixed-curvature spaces and key concepts in VRPs. For broader overview of geometric deep learning, we refer interested readers to the surveys (Peng et al., 2021; Mettes et al., 2024).
Recent efforts (Liu et al., 2024; Zhou et al., 2024; Berto et al., 2024) have begun focusing on cross-task learning to address the generalization gaps observed in earlier ap- proaches. For instance, (Liu et al., 2024) introduces attribute composition to handle a wide range of VRP variants, while (Zhou et al., 2024) employs a mixture-of ef-eertss (MoE) framework to balance performance and computational ef- ficiency. Our method diverges from these by leveraging mixed-curvature spaces to process input features, enabling more effective capture of intricate geometric structures and providing a generalizable solution across diverse VRP tasks.
3.1. Basics of Riemannian Manifolds
A Riemannian manifold M is a smooth structure equipped with a metric Jx- This metric is a smoothly varying positive- definite inner product defined on the tangent space T of point x E M. Such kind of structures generalizes the con- cepts like distance and angle from Euclidean space to more complex geometric spaces. To navigate between the mani- fold and its tangent space more conveniently, the following two important mappings are often used:
Deep Learning in Non-Euclidean Space
Unlike the Euclidean setting, which assumes data points lie in flat and homogeneous spaces, non-Fuclidean geometry models the underlying space by curved Riemannian mani- folds. The family of curved Riemannian manifolds can be broadly categorized into two types: hyperbolic surface (char- acterized by negative curvature) and hyperspherical surface (characterized by positive curvature). In details, hyperbolic geometry can be expressed through five isometric models, including Poincaré ball model (Nickel & Kiela, 2017: Ganea et al., 2018) 8), Lorentz model(typerboloid) (Chen et al., 2021; Bdeir et al., 2024; Nickel & Kiela, 2018), Poincaré half space model (Stahl, 1993), Klein model (Bi al., 2015) and hemisphere model (Cannon et al., 1997). Thanks to their non-uniform distance metric, hyperbolic surfaces are particularly well-suited for extracting hierarchical and re- lational structures from data and this has led to their wide applications in vision (Khrulkov et al., 2020; Atigh et al.,
Expa T&M + M, Loge M T.M. (I)
The exponential map, denoted by Expa. transfers vectors from tangent space TxM back to manifold M of curvature K. The logarithumic map, denoted by Log transfers vectors from manifold M of curvatre k to tangent space T.M. Due to page limit, we put their mathematical expressions under hyperbolic and hyperspherical settings in Eqs. (17), (18), (19), (20), Appendix.1.
3.2. Hyperbolic and Hyperspherical Spaces
Our framework is built upon mixed-curvature space that integrates properties of multiple geometric spaces. Below, we provide a brief overview of the two geometric spaces that are employed in this work: the hyperbolic spaces and hyperspherical spaces.
3

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
Input Instance
Subspace
Lo
Subssacce C" Subspace
LopO
Curvature Space
Subspaco Subsgace Subspuce
Subspace 2
LogO)
LogO
Subspace
Self-
Expú
LogO
Exp(
LogU
Attention
Ag
LogO)
Decoder
K1
Customen
Depot
Embedding Layer
Encoder Layer
Figure The framework the proposed module, We consider three geometrie spaces with negative (hyperbolic), zero (Fuclidean) and positive (hyperspherical) curvatures, respectively. For each feature transformation operation, we split original feature space into C' smaller subspaces, each with their own learnable curvatures (K1, RC). Operations like Exp and Log are frequently used to navigate vectors between manifold and tangent space. In the encoder layer, an extra Mix-up method is utilized to make information transmission smoother from shallow layer to deeper ones.
Hyperbolic Spaces. In our work, we adopt the Poincaré ball for modeling hyperbolic geometric information as proposed in (Ganea et al., 2018). Hyperbolic space characterized by a negative curvature x < 0 and its domain defined as:
3.3. Product Manifold Spaces
Product manifold space consists of multiple manifolds with different curvatures. It is defined by Cartesian product:
((x)= {x Rd
||x1 1},
(2)
M = M1 M2 x ... x xMc.
where ||x||2 l is the regular Le distance. The associated conformal factor is given by >x(:,-) 1+*||>113 Distance
which is equipped with curvature = (M1, Kc). Each point in M has the form X = (x1, ... xc). In this case, exponential map and logarithmic map take following forms:
and arithmetic operations are derived in (Ganea et al., 2018). For instance, the addition operation, denoted by @x takes the following form:
(00()))(E(((gpppp()) Exp(() = (Exp%) (),, ... EEpptC (-)),
(1 - 2- y) - 16 Iy
(1 + R x 12xx
(8)
G y
Logg() (.) = (Log (),,... Logge (.))-
2x
2
(3)
Building on this, the distance between two points x and y in hyperbolic space can be calculated in the following format:
3.4. Basics of VRPs
The input of VRP instance (e.g. CVRP) is a fully connected, undirected graph = (V, E), where V = -o...... v, denots the set of n + nodes including the depot uy and n customer nodes. The set denotes the set of edges and each edge has cost c.j. Other inputs like capacity and tine-window are concatenated with coordinates to formalize features of each node. Then, model starts to decode feasible solutions auto-regressively:
2 ta (V-xi Ox y112). (4)
yx =
{esj- i,j 0,...,, m}
Hyperspherical Spaces. The hypersphere, also referred to as a spherical space, is characterized by a positive curvature K 0:
S(n) (x e |R ||x||2 = 1},
(5)
and the distance between two points x and y on the sphere given as:
po (o = II po polaylar-,,G)
(9)
1 cos- (N (z, v)),
(x.
(6)
where a,, T and @ represent next step's action, generated tra- jectory and model parameters, respectively. During decod- ing, remaining capacity, elapsed time and traveled distance are recorded and treated as dynamical features.
where ( the regular vector inner product.
Remarks. In hyperbolic spaces, as |k] increases, the con- formal factor Xx decreases, leading to greater distances be- tween points. This causes points on the manifold to spread out in a more noticeable way. Conversely, in hyperspherical spaces, increasing |r|] results in shorter distances, drawing points closer together. As [K| approaches zero, both geome- tries degenerate into the standard Fuclidean space.
Remarks. Note that although some intermediate represen- tations of our proposed module locate in non-Euclidean spaces, all of the problem instances from each considered task are grounded in Euclidean space, following the data generation process in (Zhou al., 2024; Berto et al., 2024).

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
4. Methodology
dress this issue, we first project the depot and customer node embeddings from Euclidean space into mixed-curvature space (i.e., the embedding layer in Figure 2), and then apply two independent mixed-curvaiee curvature layers following Eq. (10), This process yields two feature representations, Xdep and X We then concatenate them to form the final embed- ding:
In this section, we illustrate the mixed-curvature module using the architecture proposed in (Kwon al., 2020; Liu al., 2024) as an example. However, this module can be seamlessly integrated into other neural architectures, such as MVMoE(-L) (Zhou et al., 2024) and RouteFinder (Berto et al., 2024). As shown in Figure 2, our framework firstly embeds concatenated features of graphs by Euclidean em- bedders and then projects these features from flat space into a mixed-curvature space by partitioning the original fea- ture space into multiple geometric subspaces, each with a learnable curvature parameter. Furthermore, to mitigate the geometry mismatch phenomena at each encoder layer, we in- terpolate representations between current layer and previous layer. By doing this, we can enable model to acquire a soft and learnable alignment process among incompatible geo- metric spaces, facilitating a smoother information flow and ultimately enhancing the quality of learned representations.
Xemb = [Log (Xdep); Logö (Xeus)
(1I)
where [:] denotes the concatenation operation.
4.3. Mixed-Curvature Augmented Encoder Layer
In the prior experiments for our proposed architecture, we observe that naively propagating features from non- Euclidean subspaces (e.g.. hyperbolic or hyperspherical) into attention blocks often leads to performance degradation. We suspect this phenomenon is attributed to the shift of the receptive field with respect to the network depth: In shal- low layers, the model primarily captures localized structural information (so the connectivity resembles sparse graph which is a tree-like structure), where curvature tends to be negative (Nickel & Kiela, 2017: 2018). However, as the depth increases, the receptive field expands and the model begins to aggregate global information thus entangling the features of all nodes. This leads the model into hyperspher- ical spaces where points in feature space become substan- tially interconnected. Such properties of neural networks introduce a form of curvature mismatch between consec- utive layers, leading into inferior performances. Drawing inspiration from the Mix-up technique (Zhang et al., 2018), which stabilizes training by interpolating representations of different samples, we design a similar mixing strategy that interpolates features across layers before sending them into current layer's attention block. Specifically, we formal- ize the input to each attention block as a weighted sum of the original Fuclidean representation and the logarithmic- mapped mixed-cume curvatuurvtture features from the previous layer:
4.1. Mixed-Curvatuur Linear Transformation
In the first stage, we split original feature space with dimen- sion D into C' subspaces so that each subspace is equipped with a learnable curvature parameter i and smaller di- mension L. After conducting transformations in geometric spaces, these scattered features will be merged together to formalize a complete vector with original dimension D. Similar to (Ganea et al., 2018; Gu et al., 2018; Cho et al., 2023), we rely on exponential map and logarithmic map defined in Eq. (8) to perform feature transformation opera- tions. To be specifie, suppose that our intermediate feature representations X now reside in mixed-curvatue space and we aim to perform operations such as feature transformation f = XW, then we have:
X ExPo (Logō' (X)
(10)
where we choose the original point 0 to define the tangent space. Note that the tangent space is flat, so W actually re- sides in the Euclidean space, allowing us to train it with the standard optimizer like Adam. Also note that K₁ may not always equal to Rg. By applying these different curvatures, our proposed module can capture diverse geometric struc- tures in a layer-by-lage subspaces with limited semantics. Activation functions and normalization modules can be similarly adapted, following the form of Eq. (10).
X k
X k-1 + 3 * Logö (X* (x==)),
(12)
where a, 3 are learnable parameters. In this way, model itself can gradually adjust to the evolving curvatures across layers. Unlike previous rigid transitions, this module en- courages the model to retrieve previous layer's 's information in dynamical manner, thereby improving the quality of representations.
manner instead of being confined to
4.2. Mixed-Curvature Augmented Embedding Layer
4.4. Loss
In the original POMO-MTL architecture (Liu et al., 2024), the embedding layer consists of two parts: one for the depot node and the other for the customer nodes. However, this setup can lead suboptimal embeddings that fail to capture the full range of geometric information in the inputs. To ad-
Once decoder receives embeddings from previous estab- lished mixed-curvature encoder layers, the model starts to generate logits for each trajectory in the way of Eq. (9). Following (Kwon et al., 2020), we adopt the reinforce algo- rithm proposed in (Williams, 1992) for training. Specifically,
5

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
I1:50
I==100
I==50
u=100
Type Model
Obj
Gap
Time
Ohj
Gap
Time
Type Model
Obj
Gap
Time
Obj
Gap
HGS
10.334
0.00015
4.6m
15,504
01.00%%
9.1m
HGS
14,500
0.000%
8.4m
24.139
0.00015
19.6m
0.115%
9.9m
15,590
0.556%
18.0m
LKHE
14,607
0.664%
5.5m
24.721
1.584%
OR-Tools
10.540
1.9022
10.4m
16.381
5.6525%
20.8m
OR-Tools
14,915
2.694%
10.4m
25.890
6. 6.297%
21.8m
OR-Taols(x 10)
10418
0.788%
1.7h
15.935
2.751%
OR-Tool(x10)
14.665
1.011%
1.7h
25.212
3.482%
CVRP
POMO-MTI.
10443
0.987%
36
15,790
1.846%
9s
POMO-MIL
15.032
3.6.75%
3s
25.610
5.313%
124
Mixed-POMO-MTT
10436
0.950%
15.271
1.311%
Mixed POXOO--PMM-NTTL
15.021
3.5864
25.556 4s
5.090%
MVM
10444
0.955%
46
15.771
1.728%%
11s
MVMoF-1.
15.013
3.500%
46
25.519
4.927%
14A
Minel-MVMoE-L
10431
0.933%
66
15.758
1.645%
146
MisLd-MVMoELL
15,002
3,421%
25.
4.872%
15%
MVMoF
10.428
0.896%
46
15,760
1.6535%
12s
MVMoR
14,999
3,410%
46
25.512
4,9013%
15%
Minod-MVMOE
10.424
0.865%
76
15.751
1.599%
166
Mixcd-MVMoE
14.995
3.373%
4s
25,473
4.732%
16s
LKH3
6.511
0.198%
4.5m
9.878
0.000%
5.3m
LKH3
10.571
0.790%
7.8m
15:771
0.000F6
16.0m
OR-Tools
6.531
0.195%
10.4m
10.010
1.806%
20. 8m
OR-Tools
10.677
1.746%
10.4m
16.496
1.587%
20.8m
OR-Toels(x 10)
6.498
0.000%
1.7h
9.842
0.122%
3.5h
Toolsxx 10)
10.495
0,000%
1.5h
16.004
1.444%
3.5h
POMO-MTL
6.671
2.6334%
28
10.169
3/158%
9:
POMO-MIL
10.513
0.201
2s
15.8/6
0.179%
10s
OVRP
Mixed POMO-MTL
6.670
2.637%
36
10.154
3.312%
10s
VRPL
Slised-POMO-MTE
10.511
0.185%
3s
15.827
0.362%
11s
MVMeE-L
6.665
2.518%%
36
10.145
3.21
11s
MVMoE-L
10.506
0.131%
3s
15.821
0.323%
12s
Mixed-MVMoE.J
6.658
2.448%
46
10.136
3.133%
12s
LVMoELL
10.502
0.098%
38
15.813
0.270%
13s
MVMoE
6.655
2.4022%
36
10.138
3.1336%
12s
MVMaE
10.501
0.0925%
3s
15.812
0.2611%
14s
Mixed-MVMo MVMoE
6.681
2.336%
46
10.119
2.946%
12s
MVMoE
10.497
0.052%
4s
15,806
0.227 %
14s
OR-Tools
8.127
0.9899%
10.4m
12.185
2,594%
20 8m
OR-Tools
8,737
0.5925
10:4m
14:635
1.756%
20 8m
OR-Toels(x
8.046
0.0009%
1.7h
11,878
0.000%
3.5h
ToRlsxo 10)
8.638
0.000%
1.7h
14.380
0.000%
3.5h
POMO-MIL
8.182
1.684%%
28
12,072
1.674%
86
POMO-MIIL
8,987
3.470%%
36
15:00K
4,411%
125
VRPH
Mixal-POMO-MITL
1665%
12,013
142278
OVRPTW
MOMOM--OMO-MITL
8,982
3.420Y3
36
14,9-18
3.996%
MVMoE-L
8.176
1.6055%
36
12,036
1. 1.368%
10s
MVMoE-L
8,974
5.322%
46
14,940
3.941%
146
Mina--MMMoE-L
1.531%
36
12,025
1.265%
Missd-MMMoE-L
8.961
3.219%
46
14,911
3.749%
MVMoE
8:170
1.540%
36
12.027
1.2855%
10s
MVMoE
8,964
3.210%%
46
14.927
3.852%
1.58
Mixa--MVMOE
36
1.153%
Miscd-MVMoE
3.060%
45
14,898
3,579 %
Table 1. Performances on 6 seen tasks by following the setting of (Zhou et al., 2024). Each task is assigned with 1,000 unseen instances for testing. The best performances are annotated with bold and domains improved by our module are highlighted with underlines.
based on Eq. (9), our objective function is defined as:
are conducted on a machine equipped with four NVIDIA RTX A6000 GPUs, each with 48 GB of memory. In the following, we first introduce the baselines used in our exper- iments, then describe the training and testing configurations. Finally, we report the experimental results along with de- tailed result analysis'.
L Er=po(+(c)((((])) [R()]]
(13)
and during the optimization stage, the gradient of the objec- tive function takes the following form:
1 N
VoL
(R(7)) - b(G)) V (o (14)
Baselines
where R(T') denotes the reward (in our case, it is defined as the negative length) obtained from the i-th generated tra- jectory r', and b% bC) is the shared baseline introduced to reduce the variance in optimization stage. For other models such as MVMoE(-L) (Zhou al., 2024), an additional ob- jective may be added to balance the load among different expert modules.
The baselines used in our study fall into two categories: traditional heuristic solvers and neural solvers. Below, we provide specific details for each baseline:
HGS (Vidal, 2022): A traditional solver based on genetic algorithm, designed to tackle different VRP variants.
LKH3 (Helsgaun, 2017): A widely used heuristic algo- rithm for solving VRP variants. It employs k-opt mecha- nism where, during the search stage, k edges are removed and reconnected to discover potentially better solutions.
Remarks, As noted in (Cho et al., 2023), the linear transfor- mation defined in Eq. (10) is differentiable with respect to curvature k. Hence, we can treat x as learnable parameter and optimize it during training.
comprehensive comprehensive solver developed by Google that supports various combina- torial optimization tasks, including VRPs.
OR-Tools (Perron & Didier, 2024): A
5. Experiments
POMO-MTL (Liu et al., 2024): A multi-task extension of POMO (Kwon et al., 2020), which enables the model to address multiple VRPs simultaneously.
In this section, we present our experimental findings to demonstrate the effectiveness of the proposed mixed- curvature pre-training paradigm in enabling a multi-task solver for vehiele routing problems (VRPs). Specifically, we evaluate our approach on 24 distinct VRP variants (or tasks) spanning 6 different constraint types. All experiments
MVMoE(-I.) (Zhou et al., 2024): MVMoR incorporates
Our code is available at: https: / / htt///tttbb.ooo com/
6

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
B=50
m=100
n=:50
B=100
Type Model
Ohj
Gap
Time
Obj
Gap
Time
Type Model
Ohj
Gap
Obj
Gap
Time
OR-Tools
5,764
0.352%
10.4m
8.522
1.852%
20.8m
OR-Tools
6.522
0,481%%
10.4m
9.966
1.783%
2m
OR-Toolsix 10)
5.745
0.000%
1.7h
8.365
0.000%
3.5h
TRolsx 10)
6.490
0.000%
1.7h
9,790
0.000%
POMO-MTI.
6.116
6.430%
24
8.979
7.335%
86.
POMO
6.668
2.734%
26
10.126
3.441%
10s
VRPBL OVRP3
Mixed-POOMO-MTT.
6.112
6.348%
9.021
7,831%
Mixed. POMO-MTI
6.667
2.708%
10.116
3.350%
MVMoE&1
6.122
6.522%
36
8.972
7.243%
10s
MVMoF-1.
6.659
2.597%
36
10.106
3 3.244%
12%
MVxed--MMMoELL.
6.102
6.175%
8,951
6.997%
1ls
MVMeELL
6.653
2.497%
10.098
3.159%
MVMoR
6.092
5.999%
36
8,959
7.888%
11s
MVMoF
6.650
2,454%
36
10,097
3.148%
13s
Mixol-MVMoE
6,084
5.871%
8.934
6.800%
12s
Mixed-MVMoB
6.648
2.419%
10.079
2.971 %
14s
OR-Tools
8,131
1.254%
10,4m
12,905
2.586%
20.8m
OR-Tools
15.053
1.857%
10.4m
26.217
2 2.8588%
20.8mL
OR-Toob(X10)
8.029
0.000%
1.7h
11.790
0.000%
3.5h
OR- OR-Toolsix10
14,771
0.000%
1.7h
25.496
0.0010%
3.5h
POMO-MTL
8,188
1.971%
24
11.998
1.793%
9s
POMO-MILL
16.055
8.841%
3s
27.519
7,413%%
11s
Mixel-POMO-MTTL
8.182
L905%
36
11.964
1.514%
10s
VRPBTV
POMO--PO
16.071
8.913%
35
27.327
7.457%
12s
MVMoE-L
8,180
1.872%
3s
11,960
1.473%
10s
MVMcE-L
16.04]
8.745%
27.265
7.190%
135
Mixel-MVMoE-L
8.172
L.781%
36
11.949
L.378%
12s
Mised-MVMoB-LL
16.039
8.715
27.223
7.018%
11s
MVMoE
8.172
L.776%
3s
11.945
1.346%
11s
MVMoE
16.022
8.600%
27.236
7.078%
14s
Mixod-MVMoE
8,168
1.729%
4s
11.936
1.264%
12s
MiMe
16,014
8.545%
27.208
6.967%
1.s
OR-Tools
14.815
1.432%
10:4m
25.823
2.534%
20.8m
OR-Tools
5.731
0.549%
10.4m
8.555
2.459
20.8m
OR-TnOk(xxO)
14,59%
0.0KMMS
1,7h
25. 195
0.001%
3.5h
ORR-Tools(x 10)
5,739
0.000K5
1.7h
8. 348
0.0000%
3 5.5h
POMO-MTL
14.961
2.586%
34
25.619
1.920%
13s
POMO-MIL
6.104
6.306%
8.961
7.343%
VRPLTW
Misat-POMO--MIL
14,966
2.6211%
34
25.561
1.673%
14s
OVREDD
Mixet--OMMU-MIII
6,102
6.282%
36
9:009
7.919%
10%
MVMoE-L
14.953
2.535%
25.529
1.545%
16s
MVMoF-I.
6.104
6.310%
8.957
7.300%
11s
MixoI-MVMMtt-L
14,941
2.448%
46
25,521
1.515%
176
Mixed-MV Mob-L
6,090
6.077%
36
8.9.5
7.0275%
11%
MVMeE
14:937
2.4211%
25.514
1.471%
17s
MVMoE
6.076
5.813%
1,9442
7.115%
Mixol-MVMMH
14.931
2.387
46
25.486
1.365 %
186
Mixed-MVMobt
6.068
5.705%
4s
8,920
6.857%
12%
OR-Tools
8.758
0.927%
10.4m
14.713
2.268%
20.5m
OR-Tools
8.728
0.656%
1.779%
20
OR-ToobaX10)
8.675
0.001/%
1.7h
14.38-
0. 0.0001
3.5h
OR-Tools(x10
8,669
0.00009
1.7h
14.279
0.000/%
3,5h
OVRPBTW
Mixol-POMO-MITL
POMO-MTL
9.523
9.514
9.734%
9.628%
36
15.844
15.879
10.453%
19.%%
10s
11s
ONRELLN
Misod-POMO-MITL
POMO-MTL
8.987
8,984
3.633%
3.6009%
36
14.845
14.896
4.3749
4.020S
128
12s
MVMeE-L
9.515
9.630%
10.188%
12s
MVMcE-L
8.974
3.488
3.971%
MVMed--MMMo-LL
9.506
9.530%
46
15,502
9,899%
13s
Mixed MVM
8.961
3.335%
4s
14.816
3.816%
1.5
MVMcE
9,486
9.308%
15.506
9.948%
13s
MVMoE
8.966
3.396%
14.828
3.903%
MiMod-MMMME
9,483
9.283%
4s
15.779
9.749
14s
Mixed MVMoE
8,951
3.225%
4s
14.779
3.560%
16s
OR-Tools
14,890
L.02%
10.4m
25.979
2.518%
OR-Tools
8.729
0.624%
14.496
1.724%
20.8m
OR-Tool(x11) 10)
14,667
0.0000%
1.7h
25.342
0.000%%
3.5h
DR-TToos(x10)
8.623
0.000%
1,7h
14.250
0.000%
3.5h
VRPBLTW
Mixet-POMOO-TIL
POMO-MTL
15.980
15.998
9.139%
9.035%
34
34
27.247
27.219
7.658%
7.746%
12s
13s
OVRPBLTW
POMO-MIL
POMO-MTTM
9.541
9.532
9.851%
9.946%
36
15.738
15:720
10.498%
10.358%
11s
136
MVMoE-L
15.963
8.915%
27.177
7.473%
14s
MVMoE-L
9.518
9.682%
15:706
10.26345
13s
Mixed-MWMoFF-I
15.961
8.871%
44
22.129
7,278%
15s
Mixed-MVMoFFLL
9.509
9.582%
4x
15.673
10.027%
14s
MVMoE
15:945
8.775
27.142
7.332%
15s
MVMoE
9,503
9.516%
15.671
10 10.009%
14s
MixoI-MVMoE
15,932
8.690%
27,136
7,304
16s
Mixed-MVMMB
9.495
9.462%
15.636
9,772
16s
Table 2. Performances on 10 unseen tasks following the setting of (Zhou et al., 2024). Each task is assigned with 1,000 instances for testing. The best performances are annotated with bold and domains improved by our module are highlighted with underlines.
mixture-of-ene expert (MoE) modules into both encoder and decoder layers, differing from the original POMO-MTL architecture. In the meanwhile, MVMoE-L is a lightweight variant of MVMoE that accelerates the routing mechanism while maintaining computational efficiency.
lem scales: 50 and 100 nodes in each instance. As men- tioned earlier, our pre-training paradigm can be seamlessly integrated into any existing architectures,
take POMO- MTL (Liu et al., 2024), and MVMoB(-L) (Zhou et al., 2024) as our backbones. We adopt Adam as our optimizer. The learning rate, weight decay and batch size are set to le-4 and le-6 and 128, respectively. We train each model with 5, 5,000 epochs and for each epoch there are 20,000 instances. During the last 500 epochs, we decay the learning rate by 10. At the very beginning, we initialize all of the curvatures as 0 and jointly optimize them with other parameters. Note that only 6 VRP variants are used for training. Further details about hyper-parameters are listed in Table 12, Appendix.2. 2.
RF-X (Berto et al., 2024): RouteFinder (or its variant) of- fers a more fine- grained feature fusion approach that further enhances performances of POMO-MTL. and MVMoEE-L).
Training Configurations
Due to the significant differences in experimental settings between (Zhou et al., 2024) and (Berto et al., 2024), we divide our experiments into two parts. The first part strictly follows the training configurations outlined in (Zhou al., 2024), and the analysis of these results is presented in Sec- tion 5.1. The second part follows the experimental setup from (Berto et al., 2024), with the corresponding analysis provided in Section 5.2.
Configurations with (Berto et al., 2024). The problem scales consist of 50 and 100 as well. We take RF-X (Berto et al., 2024) as the backbone, and follow the settings in its original paper, where each model is only trained with 300 epochs and each epoch is assigned with 100,000 training instances. Note that different from (Zhou et al., 2024), in this case, 16 VRP tasks are all used for training RF-X Besides, the
Configurations with (Zhou et al., 2024). We have two prob-
7

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
learning rate, weight decay and batch size are set 3e-4, le-6 and 256, respectively. In epoch 270 and 295, we decay the learning rate by 10. The detailed experimental configu- rations of RF-X can be found in Table 17, Appendix.4.
stage. Notably, in the more challenging scenario where N 100, MVMoE-L. with the mixed-curvature module outperforms the original MVMoE across all 6 tasks, demon- strating strong versatility across different problem sizes.
Zero-shot Test on Unseen Tasks. To further assess the
Validation Configurations
zero-shot predictive capabilities of our approach, we evalu- ate each model on 10 tasks that were not included in training, The results, shown in Table 2, reveal that MVMoE with the module achieves state-of-the hhrt perfor- mance on all 10 tasks at both node number scales. This outcome underscores the effectiveness of our module in en- abling solvers to generalize to previously unseen scenarios.
We conduct four types of validation experiments: the in- distribution testing, zero-shot testing, few-shot testing, and real-world testing. We divide these evaluations into two sets of configurations corresponding to (Zhou et al., 2024) and (Berto et al., 2024).
Configurations with (Zhou el al., 2024). For each VRP task, we pre-collect 1,000 unseen instances and report gaps rel- ative to the optimal (or best) known solutions. Following (K (wwon& et al., 2020; Zhou et al., 2024), we apply greedy rollout with 8x instance augmentation for fair comparisons, where best solutions for each instance are obtained by solv- ing multiple (8x) equivalent instances. Those equivalent instances are acquired by rotating or clipping the original instances (Kwon et al., 2020). The in-distribution test com- prises 6 VRP tasks included during training, while the zero- shot test includes 10 tasks not seen during training. For few-shot testing, we choose VRPBLTW and OVRPBLTW to assess model performance in low-data scenarios. Lastly, we follow (Zhou et al., 2024) for real-world evaluations on set-X (Uchoa et al., 2017) for CVRP and set-Solomon (Solomon, 1987) for VRPTW.
Few-Shot Test. Following the experimental setup of (Zhou et al., 2024), we examine two previously unseen tasks, OVRPBLTW and VRPBLIW, to gauge each model's perfor- mance in few-shot context. Specifically, we fine-tune each model for 10 epochs, with each epoch drawing on 10,000 randomly sampled training instances. As illustrated in Fig- outperform
ure 3, Mixed-MVMoL and the baseline models, demonstrating that the incorporation of mixed-curvature spaces can enhance performance in low- resource settings well.
VRPBLTW
OVRPBLTW
POND MiLL
POMO-NTL
Hore Wiltee
Mace WWite
Configurations with (Berio et al., 2024). In this setting, each task is again assigned 1,000 unseen instances, with the gaps to the optimal (or best) solutions reported. 16 VRP tasks are designated as the seen ones in the in-distribution test, while 8 tasks are the unseen ones in few-shot evaluations. For real-world testing, we follow (Berto et al., 2024) and use sets A, B, E, F, M, P. and X from CVRPLib (Uchoa et al., 2017) to assess the model performance under more practical conditions.
Epoch
Epech
Figure 3. The shot performance on two unseen tasks following settings of (Zhou et al., 2024). The x and y axis represent epochs and gaps, respectively. Here each problem instance has 50 nodes.
Real-World Instances Test. We also evaluate the mod- els on real-world testing instances sourced from CVRPLib, categorized broadly into moderate-scale and large-scale set- tings. Table 13, Table 14 and Table 15, Appendix.3 show that models incorporating our mixed-cuuvatun module out- perform both the single-task model (POMO) and multi-task models (POMO-MTL and MVMoE). The results indicate not only a reduction in the performance gap on moderate- scale problems but also consistent narrowing of the gap on large-scale instances, showing our mixed-curvature module enables the original model to adapt effectively to real-world scenarios.
Distortion Rate and Curvature Analysis. Apart from the above validations, we also analyze the distortion rates and visualize the learned curvatures. Due to space limits, we move them to Appendíx.1.
5.1. Results Compared with (Zhou et al., 2024)
In-distribution Test on Seen Tasks. To evaluate perfor- mance on tasks seen during training, we begin by testing the models 6 such tasks. The results, presented in Ta- ble 1, indicate that the original MVMoE augmented with the mixed-curvature module outperforms all prior baselines. Furthermore, the mixed-curvature module improves POMO- MTL and MVM performance on 5 out of tasks and 6 out of 6 tasks, respectively, emphasizing the general bene- fits of incorporating geometric subspaces the pre-training
5.2. Results Compared with (Berto et al., 2024)
In RouteFinder (Berto et al., 2024), all of the 16 tasks from (Zhou et al., 2024) are used for training, and the results are shown in Table 18. From these presented outcomes, it is evident that RF-TE combined with the mixed-curvature
8

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
module achieves the lowest performance gaps on 16 of the 16 tasks both node sizes. Besides, augmented with mixed-curvature modules, backbones like MTPOMO, MV- MoE and RF-MVMoE get consistent improvements on their performances. We also evaluate its performance on 7 real- world benchmarks from CVRPLib, where RF-TE equipped with the mixed-curvature module further reduces the aver- age gaps (as shown in Table 19). Moreover, we assess its capabilities on 8 few-shot tasks. As illustrated in Table 20, the mixed-curvature-aa
ule's utility and necessity in smoothing transitions between different curvature spaces.
Effects of the Number of Subspaces. In our experiment, we set the number of subspaces in mixed-curvature space as 8 and each subspace is assigned with 16 feature dimen- sions. To further investigate the effects of the number of subspaces on model's performances, we also try 4 and 16 in to illustrate the difference. We show results both node scales in Table 10. From the presented results for N = 50, we can find that the Mixed-POMO- MTL-8 can achieve the best averaged performances on 16 tasks, while the Mixed-POMO-MTTL-4 and MiXed-POMO- M1L-16 achieve relatively inferior performances. We guess the reason is that although POMO-MTL--Mieed- acquires larger subspaces, its diversity is severely limited by the number of subspaces compared to the other two. In the meanwhile, Mixed-POMO--TTL. but the feature dimension maybe too small to capture impor- tant geometric information from the inputs. However, when problem size becomes larger, Mixed-POMO- surpass Poredd-OMO-MTL.... by a large margin and greatly shorten the gap with respect to Mixed-POMO-MTT-44
model trained with EAL (shorted for Efficient Adapter Layer in (Berto et al., 2024)) signif- icantly surpasses the performance of the original model tuned with EAL. Furthermore, when trained from scratch, the niixedcurrvauurebaan based model outperforms the original model with EAL on 6 of the tasks, demonstrating the effectiveness of the mixed-curvature module in enhancing existing multi-task VRP solvers.
enhances its diversity
5.3. More Ablation Studies and Discussions
Effects of Increased Parameters. Since we insert several mixed-curvature modules into the embedder and encoder layer, the total number of parameters is increased and we list the number of parameters of each model in Table 9. Com- pared to previous baselines, the increased ratio is between 3.57% and 10.56%. Moreover, from results presented in Table 7, we can observe that only increasing the number of parameters will downgrade performances in most cases. In specifies, we replace the mixed-curvatuu space modules in encoder with their Euclidean counterparts so that the num- ber of parameters is still in the same level as before (we name these models as SLe-POMO-MTL, Euc-MVMoE-L and MVo)M. For the LLu--OOM-MML, it achieves the worst performances on 13 out of 16 and 11 out of 16 tasks with node size of 50 and 100, respectively. For the Buc- MVMoF, it achieves worst performances on 12 out of 16 tasks under both of the node size settings. These evidences demonstrate that naively increasing the number of parame- ters will often lead into inferior results in most cases, which indicates that the improvements on performances largely benefit from the introduction of mixed-curvature spaces.
can
Discussions of Running Time. Since several mixed- curvature modules are inserted into the embedder and en- coder, the running time will be increased. As reflected in Table I and Table 2, the model requires more time to process instances on almost every VRPs task. Taking N = 100 as POMO-MTL, Mixed-MVMoE. and an example, introduce 10.72%, 7.68%. 7.56% extra time costs their own backbones, respectively. These show that although mixed-curvature modules bring extra compu- tational burdens. the added costs are moderate.
Conclusions
In this work, we present novel pre-training paradigm that processes features in curved geometric spaces for solving multi-task VRPs. By splitting the original feature space into multiple subspaces, each with its own learnable curvature, we enable the model to capture diverse geometric structures from inputs. Extensive experiments show that our mixed- curvature modules consistently enhance various backbonn architectures, highlighting the promise of mixed-curvature spaces in improving multi-task VRP solvers. However, our approach has limitations. First, the frequent use of exponen- tial and logarithmic map operations introduces extra time costs and may cause some unstable numerical phenomena. Second, our study does not consider large-scale instances with around 10,000 nodes which has achieved great atten- tions recently. Thirdly, we allocate 16 dimensions for each curvature subspace but other adaptive methods like neural- architecture-search (Elsken et al., 2019) may also be feasible. We plan to explore and address them in future works.
Effects of Mix-up Modules. In this part, we discuss the effectiveness of Mix-up modules and how will it affect the performances of model. We utilize Mixed- POXMd--O Mixed-MVMoECC to conduct ablation experiments. From results presented in Table 8, we can observe that after re- moving the Mix-up modules from the encoder, the perfor- mances for Mixed-POMO-MTTL will become worse on 12 out of 16 tasks with node size N- = 50 and 11 out of 16 tasks with node size N = 100, respectively. Similarly, the MiXed-MVMoE without Mix-Up modules will lose their SOTA performances on 1 11-12 tasks across problem types and node sizes. These demonstrate that the Mix-up modules can further enhance performances, which validates this mod-

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
Impact Statement
Chalumeau, F., Surana, S., Bonnet, C., Grinsztajn, N., Pre- torius, A., Laterre, A., and Barrett, 'T. Combinatorial optimization with policy adaptation using latent space search. Proceedings of the 37th Advances in Neural In- formation Processing Systems (NeurIPS), 2023.
This paper presents work whose goal to advance the field of deep learning for vehicle routing problems. To our best knowledge, there is no potential socictal consequence of our work since the module developed in our work focuses facilitating the constrained optimizations.
Chami, I,, Ying, Z., Ré, C., and Leskovec, J. Hyperbolic graph convolutional neural networks. Proceedings of the 34th Advances Neural Information Processing Systems (NeurIPS), 2019.
Acknowledgment
This research/project is supported by the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No: AISG3-RP-202-031] the MTI under its AI Centre of Excellence for Manufacturing (AIMfg) (Award W25MCMF014), and the College of Computing and Data Science, Nanyang Technological University. We also want to express our sincere thanks to all reviewers and area chair for their constructive engagement and valuable suggestions during the rebuttal stage.
Chen, J., Wang. J., Zhang, Z., Cao, Z., Ye, T., and Chen, Efficient meta neural heuristic for multi-objectto natorial optimization. Proceedings of the 38th Advances in Neural Information Processing Systems (NeurIPS), 2024.
combi-
Chen, W. Han, X.,, Lin, Y., Zhao, H., Liu, Z., Li, P., Sun, M., and Zhou, J. Fully hyperbolic neural networks. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL), pp. 5672-5686, 2021.
References
Atigh, M. G., Schoep. J., Acar, E., Van Noord, N., and Mettes, P. Hyperbolic image segmentation. In Proceed- ings of the 35th IEEE/CVE conference Computer Vi- sion and Pattern Recognition (CVPR), pp. 4453-4462, 2022.
Cheng, H., Zheng, H., Cong. Y., Jiang, W., and Pu, S. Select and optimize: Learning to solve large-scale tsp instances. Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1219- 1231, 2023.
Cho, S., Cho. S., Park, S., Lee, H., Lee, H., and Lee, M. Curve your attention: Mixed-curvature transform- ers for graph representation learning. arXiv preprint arXiv:2309.04003 04082, 2023.
Bachmann, G., Bécigneul, G., and Ganea, O. Constant cur- vature graph convolutional networks. In Proceedings of the 37th International Conference on Machine Learning (ICML), pp. 486-496, 2020.
Choudhary, N., Rao, N., and Reddy, C. Hyperbolic graph neural networks at scale: meta learning approach. Pro- ceedings of the 38th Advances in Neural Information Prucessing Systems (NeurIPS), 2024.
Bdeir, A., Schwethelm, K., and Landwehr, N. Fully hyper- bolic convolutional neural networks for computer vision. In Proceedings of the 12th International Conference on Learning Representations (ICLR), 2024.
Chow, B. and Knopf, D. The Ricci Flow: An Introduction: An Introduction, volume 1. American Mathematical Soc., 2004.
Berto, F., Hua, C., Zepeda, N. G., Hottung, A., Wouda, N., Lan, L., Tierney, K., and Park, J. Routefinder: Towards foundation models for vehicle routing problems. ICML 2024 Workshop on Foundation Models in the Wild, 2024.
Dai, S., Gan, Z., Cheng, Y., Tao, C., Carin, L.,, and Liu, J. Apo-vae: Text generation hyperbolic space. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HI.T), pp. 416- 431, 2021.
Bi, Y., Fan, B., and Wu, F. Beyond mahalanobis metric: cayley-klein metric learning. In Proceedings of the 28th IEEE conference Computer Vision and Pattern Recog- nition (CVPR), pp. 2339-2347, 2015.
Cannon, J. W., Floyd, W. J., Kenyon, R., Parry, W. R.R al. Hyperbolic geometry. Flavors of geometry, 31(59-115): 2, 1997.
Dantzig, G. B. and Ramser, J. H. The truck dispatching problem. Management science, 6(1):80-91, 1959.
Desai, K., Nickel, M., Rajpurohit, T., Johnson, J., and Vedantam, S. R. Hyperbolic image-text representations. Proceedings of the 40th International Conference on Machine Learning (ICML), pp. 7694-7731, 2023.
Cao, Y., Li, D., Sun, H., Assadi, A. H., and Zhang, S.
Efficient weingarten map and curvature estimation on manifolds. Machine Learning, 11066)1119-1344,, 2021.
10

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
Elsken, T., Metzen, J. H., and Hutter, F. Neural architecture search: A survey. Journal of Machine Learning Research, 20(55): 1-21, 2019.
Huang. Z.., Zhou, J., Cao, Z., and Xu, Y. Rethinking light decoder-based solvers for vehicle routing problems. In International Conference Learning Representations, 2025.
Fan, X., Xu, M., Chen, H., Chen, Y., Das, M., and Yang, H. Enhancing hyperbolic knowledge graph embeddings via lorentz transformations. In Findings of the Association for Computational Linguistics ACL (ACL), pp. 4575-4589, 2024.
Joshi, C. K., Laurent, T., and Bresson, X. graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227, 2019.
An efficient
Fu, X., Wang, J., Gao, Y., Sun, Q. Yuan, H., Li, and Li,
Khrulkov, V., Mirvakhabova, L., Ustinova, E.,, Oseledets, I., and Lempitsky, V. Hyperbolic image embeddings. In Pro- ceedings of the 33th IEEE/CVF conference Computer Vision and Pattern Recognition (CVPR), pp. 6418-6428, 2020.
X. Discrete curvature graph information bottleneck. In Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), volume 39, pp. 16666-16673, 2025.
Ganea, O., Bécigneul, G., and Hofmann, T. Hyperbolic neural networks. Proceedings of the 32th Advances in Neural Information Processing Systems (NeurIPS), 2018.
Kim, M., Park, J., and Park, J. Sym-nco: Leveraging sym- metricity for neural combinatorial optimization. Pro- ceedings of the 36th Advances in Neural Information Processing Systems (NeurIPS), 2022.
Ge, Y., Li, H., and Tuzhilin, A. Route recommendations for intelligent transportation services. IEEE Transactions on Knowledge and Data Engineering, 33(3):1169-1182, 2019.
Kool, W., van Hoof, H., and Welling, M. Attention, learn solve routing problems! In Proceedings of the 7th International Conference on Learning Representations (ICLR), 2019.
Goh, Y. L., Cao, Z., Ma, Y., Dong, Y., Dupty, M. H., and Lee, W. S. Hierarchical neural constructive solver for real-world tsp scenarios. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 884-895, 2024.
Kwon, Y.-D., Choo, J., Kim, B., Yoon, I,, Gwon, Y., and Min, S. Pomo: Policy optimization with multiple op- tima for reinforcement learning. Proceedings of the 34th Advances in Neural Information Processing Systems (NeurIPS), 2020.
Gu, A., Sala, F., Gunel, B., and Ré, C. Learning mixed- curvature representations in product spaces. In Proceed- ings of the 6th International Conference Learning Representations (ICLR), 2018.
Langley, Crafting papers on machine learning. In Langley, P. (ed.), Proceedings of the 17th International Conference Machine Learning (ICML 2000), pp. 1207-1216, Stan- ford, CA, 2000. Morgan Kaufmann.
Helsgaun, K. An extension of the lin weekk-eannnnelaaeeeeeee tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12: 966-980, 2017.
Lee, J. M. Riemannian manifolds: an introduction to curva- ture, volume 176. Springer Science & Business Media, 2006.
Hong, J., Hayder, Z., Han, J., Fang, P., Harandi, M., and Petersson, L. Hyperbolic audio-visual zero-shot learn- ing. In Proceedings of the 19th IEEE/CVF International Conference on Computer Vision (ICCV), pp. 7873-7883, 2023.
Lin, S. and Kernighan, B. W. An effective heuristic algo- rithm for the traveling-salesmm problem. Operations research, 21(2):49-511 1973.
Hottung, A. and Tierney, K. Neural large neighborhood search for the capacitated vehicle routing problem. In Proceedings of the 25th European Conference Artifi- cial Intelligence, volume 313, pp. 453-450. IOS Press, 2020.
Liu, F, Lin, X., Wang, Z., Zhang, Q., Xialiang, T., and Yuan, M. Multi-task learning for routing problem with cross-problem zero-shot generalization. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (SIGKDD), pp. 1898 1908-1908, 2024.
Hottung, A., Kwon, Y.-D., and Tierney, K. Efficient active search for combinatorial optimization problems. In Pro- ceedings of the 9th International Conference on Learning Representations (ICLR), 2021.
Liu, Q., Nickel, M., and Kiela, D. Hyperbolic graph neural networks. Proceedings of the 34th Advances in Neural Information Processing Systems (NeurIPS). 2019.

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
Liu, W. Wen, Y., Yu, Z.,, Li, M., Raj. B., and Song, L. Sphereface: Deep hypersphere embedding for face recog- nition. In Proceedings of the 30th IEEE conference Computer Vision and Pattern Recognition (CVPR), Pp. 212-220, 2017a.
Pang, T., Yang, X., Dong, Y., Xu, K., Zhu, J., and Su, H. Boosting adversarial training with hypersphere bedding. Proceedings of the 34th Advances in Neural Information Processing Systems (NeurIPS), 2020.
Peng, W. Varanka, T., Mostafa, A., Shi, H., and Zhao, G. Hyperbolic deep neural networks: A survey. IEEE Trans- actions on Pattern Analysis and Machine Intelligence, 44 (12):10023-10044, 2021.
Liu, W., Zhang, Y.-M.. Li, X.. Yu, Z., Dai, B.. Zhao, T., and Song, I.. Deep hyperspherical learning. Proceedings of the 31th Advances in Neural Information Processing Systems (NeurIPS), 2017b.
Perron, L. and Didier, F. Cp-sat, 2024. https://developeee google.com/ ppriimiiaat.iooocc/ccc...o
URL
Luo, F. Lin, X., Liu, F., Zhang, Q.. and Wang. Z. Neu- ral combinatorial optimization with heavy decoder: To- ward large scale generalization. Proceedings of the 37th Advances in Neural Information Processing Systems (NeurIPS), 2023.
Postnikov, M. M. Geometry VI: Riemannian Geometry, volume 91. Springer Science & Business Media, 2013.
Ma. Y., Cao, Z., and Chee, Y. M. Learning search feasible and infeasible regions of routing problems with flexible neural k-opt. Pruceedings of the 38th Advances in Neural Information Processing Systems (NeurIPS), 2024.
Qiu, Z., Liu, W., Feng, H., Xue, Y., Feng, Y., Liu, Z., Zhang, D., Weller, A., and Schölkopf, B. Controlling text-to- image diffusion by orthogonal finetuning. Proceedings of the 37th Advances in Neural Information Processing Systems (NeurIPS), 2023.
Mettes, P., Ghadimi Atigh, M., Keller-Ressel, M., Gu, J., and Yeung, S. Hyperbolic deep learning in computer vision: survey, International Journal of Computer Vision, pp. 1-25, 2024.
Qu, H., Cai, Y., and Liu, J. Lims are good action recognizers. In Proceedings of the 37th IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), pp. 18395-18406, 2024.
Min, H. The multiple vehicle routing problem with si- multaneous delivery and pick-up points. Transportation Research Part A: General, 23(5)3377-386, 1989.
Sala, F. De Sa, C.,, Gu, A., and Ré, C. Representation tradeoffs for hyperbolic embeddings. In Proceedings of the 35th International Conference on Machine Learning (ICML), pp. 4460-4469, 2018
Moreira, G., Marques, M., Costeira, J. P., and Hauptmann, A. Hyperbolie vs euclidean embeddings in few-shot learn- ing: Two sides of the same coin. In Proceedings of the IEEE/CVF Winter Conference on Applications of Com- puler Vision (WACV), pp. 2082-2090, 2024.
Solomon, M. M. Algorithms for the vehicle routing and scheduling problems with time window constraints. Op- erations research, (5(2):254-266) 1987.
Najman, L. and Romon, P. Modern approaches to discrete curvature, volume 2184. Springer, 2017.
Stahl, S. The Poincaré half-plane: A gateway to modern ge- ometry. Jones and Bartlett, 1993. ISBN 9780763753818.
Nickel, M. and Kiela, D. Poincaré embeddings for learn- ing hierarchical representations. Proceedings of the 31th Advances in Neural Information Processing Systems (NeurIPS), 2017.
Sun, L., Zhang, Z., Zhang, J., Wang. F., Peng, H., Su, S., and Philip, S. Y. Hyperbolic variational graph neural network for modeling dynamic graphs. In Proceedings of the 35th AAAI Conference Artificial Intelligence (AAAI), volume 35, pp. 4375-4383, 2021.
Nickel, M. and Kiela, D. Learning continuous hierarchies in the lorentz model of hyperbolic geometry. In Proceedings of the 35th International conference machine learning (ICML), pp. 3779-3788, 2018
Sun, L., Zhang, Z., Ye, J., Peng, H., Zhang, J., Su, S.,, and Philip. S. Y. A self-supervised mixed-curvatur graph neural network. In Proceedings of the 36th AAAI Con- ference on Artificial Intelligence (AAAI), volume 36, pp. 4146-4155, 2022.
Ollivier, Y. Ricci curvature of markov chains metric spaces. Journal of Functional Analysis, 256(3):810 10008880-644 2009.
Pan, X., Jin, Y., Ding, Y., Feng, M., Zhao, I.., Song, I.., and Bian, J. H-tsp: Hierarchically solving the large- scale traveling salesman problem. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), volume 37, pp. 9345-99333, 2023.
Sun, Z. and Yang, Y. Difusco: Graph-based diffusion solvers for combinatorial optimization. Proceedings of the 37th Advances in Neural Information Processing Sys- tems (NeurIPS), 2023.
12

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Vidal, T., and Subramanian, A. New benchmark instances for the ca- pacitated vehicle routing problem. European Journal of Operational Research, 257(3):845-88)) 858, 2017.
In International Conference on Learning Representations, 2025.
Zhou, J., Wu, Y., Cao, Z., Song, W., Zhang, J., and Chen, Z. Learning large neighborhood search for vehicle routing in airport ground handling. IEEE Transactions on Knowl- edge and Data Engineering, 35(9):779-99785 2023a.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L.,, Gomez, A. N., Kaiser, t.., and Polosukhin, I. Attention is all you need. Proceedings of the 31th Advances in Neural Information Processing Systems (NeurIPS), 2017.
Zhou, J., Wu, Y., Song, W., Cao. Z., and Zhang, J. Towards omni- omni-generalizable neural methods for vehicle routing problems. In Proceedings of the 40th International Con- ference on Machine Learning (ICML), pp. 42769-42789, 2023b.
Vidal, Hybrid genetic search for the evr:: Open-source implementation and swap* neighborhood. Computers & Operations Research, 140:105643, 2022.
Vinyals, O., Fortunato, M., and Jaitly, N. Pointer networks. Proceedings of the 29th Advances in Neural Information Processing Systems (NeurIPS), 2015.
Zhou, J., Cao, Z., Wu, Y., Song, W., Ma, Y., Zhang, J., and Xu, C. Mvmoe: Multi-task vehicle routing solver In Proceedings of the 41th Inter-
with mixture-of-expers national Conference Machine Learning (ICML), pp. 61 884-611822 6244 2024.
Wang, S., Wei, X., Nogueira dos Santos, C. N., Wang, Z., Nallapati, R., Arnold, A., Xiang, B., Yu, P. S., and Cruz, F. Mixed-curvature multi-relational graph neural network for knowledge graph completion. In Proceedings of the Web Conference (WWW), pp. 1761-1771, 2021.
Wang, Y., Zhang, S., Ye, J., Peng. H., and Sun, L. A mixed- curvature graph diffusion model. In Proceedings of the 33th ACM International Conference on Information and Knowledge Management (CIKM), pp. 2482 2492, 2024.
Williams, R. J. Simple statistical
algo- rithms for connectionist reinforcement learning. Machine learning, 8:229-255 256, 1992.
Wouda, N. A., Lan, L., and Kool, W. PyVRP: high- performance VRP solver package. INFORMS Journal on Computing, 36(4):943-955, 2024. doi: 10. 10.12887/joc.2223. 0055. URL htttps://doi.ore 10. 1ww.:12171111111 2023. 0055.
Xin, L., Song, W., Cao, Z., and Zhang, J. Neurolkh: Com- bining deep learning model with fn-kkernghaanhhelseee heuristic for solving the traveling salesman problem. Pro- ceedings of the 35th Advances in Neural Information Processing Systems (NeurIPS), 2021.
Ye. H., Wang, J., Liang, H., Cao. Z. Li, Y., and Li, F. Glop: Learning global partition and local construction for solving large-scale routing problems in real-time In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), volume 38, pp. 20284-20292, 2024.
Zhang, H., Cisse, M., Dauphin, Y. N., and Lopez-Paz, D. mixup: Beyond empirical risk minimization. In Proceed- ings of the 6th International Conference on Learning Representations (ICLR), 2018
Zhang, N., Yang, J., Cao, Z., and Chi, X. Adversarial gener- ative flow network for solving vehicle routing problems.
13

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
A. Appendix
Appendix.1. Definitions, Formulas and Visualizations
Definition of Ollivier-Rieci Curvatures
Curvature describes how much a curve deviates from being a straight line or how much a surface bends the space. The Ollivier-Ricci curvature (Ollivier, 2009) is discrete notion of curvature that extends Ricci curvature from smooth (thus continuous) Riemannian manifolds structures like graphs and networks (Fu et al., 2025). To be specific, suppose that are given a metric space denoted by (X, d) where d represents metric distance (in our case X consists of two dimensions (coordinates) and d is the L2 distance between two points), then the Ollivier-Ricci curvature has the following form:
<(2, y) = W( My) d(z, y)
2, E
(15)
where (t,-) denotes Wasserstein distance between two probability measures:
Cpz
(2(2) = Cyz
(x(2)
(16)
Ei= Ozi
E/ Cyf
where Crz, Cyz are edge weights on edges x2, yz and Na. Ny are numbers of adjacent neighbors of æt y, respectively. Based on these quantities, Pzz and My actually measure the transition probability of the random walk starts from æ, y and ends at some point z. In other words, the smaller (bigger) the W(zz: My), the higher (lower) the chances that æ and y will encounter each other within a few steps. which shares great similarity with the contraction (divergence) behaviors in spherical (hyperbolic) spaces. In our implementation, for each node X, we use K-Nearest Neighbors algorithm to sample 5 nodes from each node's 's neighbour set and calculate the node curvature by averaging Ollivier-Ricci curvatures on the selected 5 edges. Finally, we can get the graph curvature by averaging all of these nodes' curvatures.
Remarks. Note that although we only take 5 edges for each node in the stage of curvature calculations, the embedder takes the complete graph as the input. The reason for us to choose KNN graphs to analyze curvatures is that during the delivery, not all of the edges are worth of being considered: some maybe less important and some maybe blocked due to hard constraints (e.g., the same edge can't 't be visited twice during the delivery). As result of this, applying KNN graphs here is more faithful to actual scenarios. Similar operations also appear in some prior works for solving traveling salesman problem (Joshi et al., 2019).
In previous works such as (Gu et al., 2018; Bachmann et al., 2020), the Parallelogram Law has been utilized to analyze the deviations of datasets from Euclidean geometry. This classical geometry identity checks whether quadruple of points behaves flat in the normal Euclidean sense: If the sum of the squares of the diagonals is greater (less) than the sum of the squares of the sides in a parallelogram then it indicates that data points are located in negative (positive) curvature spaces. The reasons for us choose Ollivier-Rice curvature mainly lie in two sides: 1) Enumerating all of the four point configurations from graph with N 50 nodes is computationally expensive while Ollivier-Ricct curvature offers more light-weight method. 2) Allivier-Ricci curvature enables more nuanced understanding of geometric structures in datasets under optimal transport: it captures the degree to which local neighborhoods contract or diverge and this makes it especially well-suited for datasets represented as graphs or networks. For a more comprehensive comparison between these different curvature concepts, please refer to Table 4.
Hyperbolic Model (is 0)
Let x. be point the manifold [H))),, TK) tangent space vector and Xx |+<||x|] @n is defined in Eq. (3).
Exponential Map
Evpg(v) = x @n. (tant) (v-x>>)) Ax|vv v
(17)
Logarithmic Map:
2 tanh-1 (V-xlx Bx (-x)))
x @ (-y) θx (-y)
LogE(y)
(18)
Xx
14

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
Hyperspherical Model (x
Let y be point the manifold S(k),, and (x)( tangent space vector. (x, is defined in Eq. (6).
Exponential Map:
(v) = vos((vklvl) x sin(Vrevl) |vl
(19)
Logarithmic Map:
y cos(d,, (x. (og)(y) = (x,
(20)
y cos((1 (d (x.
Curvature Visualizations for another 10 VRPs Tasks
The visualizations of curvatures for remaining datasets are included in Figure 4. Note that these 10 tasks are unseen during training stage, following the settings of (Zhou et al., 2024) while in (Berto et al., 2024), all of the previously mentioned 16 VRP variants are used for training the neural solvers. From Figure 4, we can observe that non-Euclidean information exists widely across these tasks, which further validates the necessity of introducing mixed-curvature space into neural solvers.
Definition of Distortion Rate and Average Distortion Rate
We adopt the notations from (Gu et al., 2018) where U1 and U2 denote two metric spaces (possibly with different dimensions)
and they are equipped with distances dz, (+--) and dy. (-.-,, respectively. A mapping denoted by f : U, - U2 typically exists between these two spaces, such as deep neural networks. For any pair of points and b, the distortion rate induced from mapping f is defined as:
du, (f(a).
(21)
(a,(a,b)
To evaluate the distortion rate globally, we consider all pairs of points and compute the average distortion as:
Davg N Σ
du, (f(a,,
(22)
du,(a.b)
where N denotes the number of node pairs such that + b without repetitions. By using Eq. (21) and (22), we can know how far away distances in the feature space learned by neural solvers deviates from those distances in the original input graphs. The lower the average distortion rate, the better the quality of representations we get from those models.
Distortion Rate Analysis for Features of Encoder Module
As previously mentioned, learning solely in Euclidean space significantly distort distance information, adversely affecting the model's decision-makinn process and the final performances. In Table compare the distortion rates (defined in Eq. (22)) across various models. From the presented results, our approach achieves considerably lower distortion rates than the baselines, indicating that mixed-curvature space preserves original distances more faithfully. This allows the model to retain more accurate distance-related information, thus enhancing its decision-making capability.
Model
Distortion
POMO-MTL
2477.725
POMO-MTL
1678.605
MVMoE-L
2923.151
Mixed-MVMoF-L
1981.076
MVMoE
2083.015
Mixed-MVMoE
1274.142
Table Distortion rates of different models. We extract intermediate representations the final layer encoder module and we use 1,000 CVRP instances with size N 50 from testing datasets to calculate the distortion rate (defined in Eq. (22)).
15

---

Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
Curvature Analysis for Subspaces of Each Layer in Encoder module
For the model familys in (Zhou al., 2024), visualize the curvature of each subspace in every encoder layer of Mixed-POMO-MTL (Figure 6, Appendix.3), MVMoE-L (Figures 7, Appendix.3), and MVMoE (Figures 8.Appendix.3), The distinct color gradients reveal that subspaces in shallower layers tend to lie in hyperbolic geometry. This observation aligns with the intuition that shallow layers primarily capture local structures, which often resemble trees or sparse graphs structures that naturally associated with negative curvatures. In contrast, as we move to deeper layers, the subspaces gradually transition towards the spherical geometry, reflecting the tendency of deeper layers to encode global information, where node features become increasingly aggregated or even collapsed with each other. For RF-X (Berto al., 2024), also visualize the curvature of subspaces in the model RF-MVMoE (Figure Appendix.4) and RF-TE (Figure 10, Appendix.4 4), where we can observe similar curvature evolving patterns across layers.
Curvature Type
Definition
Formula
Measures the failure of second covariant deriva- tives commute with each other, encoding the intrinsic curvature of Riemannian manifold.
Riemann Curvature Tensor (Lee, 2006)
R(u, v)w - V.W.
V. R
[u,a] W
Trace of the Riemann curvature tensor, demot- ing the average sectional curvature along differ- ent directions.
Ricci Curvature (Chow & Knopf, 2004)
Ric(u) E. R(u,
Product of the principal curvatures at point on surface, encoding the intrinsic measure of curvature.
Gaussian Curvature (Postnikov, 2013)
K = kn k2
Mean Curvature (Postnikov, 2013)
Average of the principal curvatures.
H = [kh + K2)
Principal Curvatures (Postnikov, 2013)
Maximum and minimum normal curvatures
Eigenvalues ki, ka of Weingarten map (Cao et al., 2021)
point on surface.
It measures how the manifold curves in the di- rection of a tangent space. It generalizes Gaus- sian curvature into higher dimensions.
Sectional Curvature (Lee, 2006)
K(u, v) (R(u,))o.))
Measures the difference between two metric measure spaces based on optimal transport, especially suitable for discrete structures like graphs and networks.
Ollivier-Rice Curvature (Ollivier, 2009)
<<xx v) = W(
d(x.9)
Whether sum of the squares the diagonals equals the sum of the squares of the sides in parallelogram.
Parallelogram Law (Gu et al., 2018)
|| + v/12 || w112 21| + 2/
Table 4. Different types of curvatures and their expressions in Lifferential/Riemannn geometry. One major difference between Ollivier- Ricci curvature and Ricci/Gaussian/ MeaM/MMaaaa/Ppaaee curvatures Ollivier-Rice curvature can handle discrete structures like graphs and networks while the others require the underlining manifold is continuous and smooth. Apart from Ollivier-Rice curvature, there have been some other recent efforts that adapt curvatures on continuous spaces into discrete structures. For more information about this, we refer interested readers to (Najman & Romon, 2017).
16

---

Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
Acronym
Meaning
POMO
Policy Optimization with Multiple Optima for Reinforcement Learning (Kwon et al., 2020)
POMO-MTL
Policy Optimization with Multiple Optima for Reinforcement Learning with Multi-Task- Task--eamnng (Liu et al., 2024)
MVMoE-L
Multi-Task Vehicle Routing Solver with Mixture-of Mixture-of-EEpeets--nee (Zhou al., 2024)
MVMoE
Multi-Task Vehicle Routing Solver with Mixture-of-Expee -firrets (Zhou et al., 2024)
RF
RouteFinder (Berto et al., 2024)
LKH
Hant-eemighan--ellggee (Lin Kernighan, 1973; Helsgaun, 2017)
HGS
Hybrid Genetic Search (Vidal, 2022)
HGS-PyVRP
A Python implementation of HGS for VRPs (Wouda al., 2024)
VRP(s)
Vehicle Routing Problem(s)
C
Capacity
O
Open Route
I.
Duration Limits
B
Backhauls
TW
Time Window
Mixed-X
The model named X augmented with Mixed-Curvature space modules
Euc-X
The model named X augmented with Euclidean space modules
Table 5. List acronyms appear in paper.
Notations
Mcaning
x,y,
Finite dimensional vectors
M
Riemannian manifold
Ox
Riemannian metric
dx
Conformal factor hyperbolic space
Curvature
Consists (K1, N2..,....., each entry corresponds the curvature geometric space
x
Consists of (x1, x2.... x.) each entry corresponds to chunk of feature located in geometric space Hyperbolic space with curvature
H((x)
8(K)
Hyperspherical space with curvature Tangent space attached with x on Riemannian manifold, Hyperbolic space, Hyperspherical space Addition operation of hyperbolic space Geodesic distance on byperbolicchhpperpheericcl space Inner product in vector space Generative model with parameter 0 Graph with vertex set and edge set Action taken in time step f Trajectory taken by the model Number of time steps
M,M. Tx)( (x)(
@x
d.(s))
(
po(.)
G= (V.
T
D
The dimension of original feature space
The number of mixed-curvature subspaces
U2
Metric spaces
(xpp(-)
Exponential map attached with point the Riemannian manifold with curvature Logarithmic map attached with point x on the Riemannian manifold with curvature k Learnable factors for balancing geometric information between layers
(.ga()
0,
Table List of notations that appear the paper.
17

---

Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
n=50
n=100
n=50
n=100
Type
Model
Gap
Gap
Type
Model
Gap
Gap
POMO-MTL
0.987%
1.846%
POMO-MTL
3.637%
5.313%
Mixed-POMO-MTTL
0.980%
1.731 %
Mixed-POMO-ME
3.556%
5,090 %
Euc-POMO-MTL
1.033%
1.815%
Bue-POMO-MTL
3.719%
5.305%
CVRP
MVMoE-L
0.955%
1.728%
VRPTW
MVMoB-L
3.500%
4.927%
Mixed-MVMoF-L
0.933%
1.645 %
Mixed-MVMoE-L
%
4.872%
Euc-MVMoF-LL
0.965%
1.743%
Euc-MVMoB-L
3.508%
4.995%
MVMoB
0.896%
1.653%
MVMоB
3.410%
4.903%
Mixed-MVMoF
0.865
1.599 %
Mixed-MVMoF
3.373%
4.732%
Euc-MVMoE
0.900%
1.672%
Euc-MVMoE
3.414%
4.892%
POMO-MTL
1.684%
1.674%
POMO-MTL
3.470%
4.411
Mixed-POMO-MITL
1.645
1.427 %
Mixed-POMO-MTTL
3.420%
3.996%
Euc-POMO-MTL
1.713%
1.569%
Euc-POMO-MTL
3.577%
4,401 %
OVRP
MVMoE-L
1.605%
1.368%
MVMoE-L
3.322%
3.941% %
Mixed-MVMoE-L
1.531 %
1.265 % 1.427%
VRU
Mixed-MVMoE-L
3.219%
3.749 %
Euc-MVMoE-L
1.602%
Euc-MVMoE-L
3.366%
3.992%
MVMoE
1.540%
1.285%
MVMoE
3.210%
3.852%
MVMoE
1.456%
1.153 %
3.060%
3.579 %
Euc- MVMoE
1.535%
1.304%
Euc-MV Moe-MVMoE
3.202%
3.708%
POMO-MTL
2.634%
3.458%
POMO-MTL
0.201
0.479%
Mixed-POMO-MME
2.637%
3.312%
Hixed-POMO-MII
0.185
0.362 %
Euc-POMO-MTL
2.656%
3.479%
Euc-POMO-MTL
0.242%
0.472%
VRPB
MVMoE-L
2.548%
3.214%
OVRPTN
MVMoB-L
0.131%
0.323%
Mixed-MVMoE-L
2.448%
3.133%
Mixed-MMMMEEL
0.098%
0.270%
Euc-MVMoE-L
2.532%
3,410%
Euc-MVMoE-L
0,365%
0.096 %
MVMоE
2.402%
3.136%
MVMoE
0.092%
0.261% %
Mixed-MV MVMoE
2.336%
2.946 %
Mixed-MV MVMoE
0.052%
0,227 %
Euc Euc-MVMoO MVMME
2.410%
3.157%
Euc-MVMoE
0.096%
0.277%
POMO-ME -OMO-MTL
6.430%
7.335 %
РOMO-MTH
2.734%
3,441 %
Mixed-POMO POMO-MTL
6.348%
7.831 %
Mixed- PooeddPPOO-MMOA -TL
2.708%
3.350 %
Buc-POMO-MTL
6.378%
7.971
Euc-POMO-MTL
2.762%
3,453%
OVRPB
MVMoE-L
7.243%
7.243%
OVRPL
MVMoE-L
2.597%
3.244%
Mixed-MVMoB-L
6.175%
6.997 %
Mixed-MVMoB-LL
2.497%
3.159%
Euc-MVMoE-L
6.525%
7.580%
Euc-MVMoE-L
2.606%
3.120% %
MVMoE
5,999%
7.088%
MVMoE
2.454%
3.148%
Mixed-MVMoE
5,871%
6.800 %
Mixed-MVMoE
2.419%
2.971 %
Euc-MVMoE
5.994%
6.909%
Euc-MVMoE
2.459%
3.141%
POMO-MTL
1.971%
1.793%
POMO-MTL
8.841
7.413%
Soxed-POMO-MII
1.905%
1.514 %
Soted-POOO-MMR
8.934%
7.457%
Euc-POMO-MTL.
1.969%
1.693%
Euc-POMO-MTL
9.188%
7.414%
VRPBL
MVMoF-L
1.872%
1.473%
MVMoF-L
8.745%
7.190%
Mixed-MVMoF-L.
1.781 %
1.378 %
Mixed-MVMoEA.
8.715%
7.018 %
Fuc-MVMoF-L.
1.886%
1.516%
Fuc-MVMoF-L.
8.803%
7.183%
MVMoB
1.776%
1.346%
MVMoB
8.600%
4.903%
Mixed-MVMoE
1.729%
1.264 %
Mixed-MVMoE
8.545%
4.732%
Euc-MVMoE
1.779%
1.405%
Euc-MVMoE
8.665%
7.113%
POMO-MTL
2.586
1.920%
POMO-MTH
6.306%
7.343 %
Mixed-POMO-MTLL
2.621%
1.673% %
Mixed-POMO-MITL
6.282%
7.919%
Euc-POMO-MTL.
2.720%
1.926%
Euc-POMO-MTL
6.305%
8.015%
VRPLIW
MVMoE-L
2.535%
1.545%
OVRPBL
MVMoE-L
6.310%
7.300%
Mixed-MVVMo-LL
2.448%
1.515%
Mixed-MVMoFLA
6.077
7.027 %
Euc-MVMoE-L
2.530%
1.618%
Euc-MVMoEE
6.311%
7.560%
MVMoE
2,421%
1.471%
MVMoE
5.843%
7.115%
MiXed-MVMoE
2.387 %
1.365 %
Mixed-MVMoE
5.705%
6.857 %
Continued on the next page
18

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
n=50
n=100
n=50
n=100
Type
Model
Gap
Gap
Type
Model
Gap
Gap
Euc-MVMoE
2.418%
1.492%
Euc-MVMoE
5.831%
7.047%
POMO-MTL
9.628%
10.453%
POMO-MTL
3.633%
4.374%
Mixed-POMO-MITL
9.734%
10.192%
Mixed-POMO-MITL
3.600%
4.020 %
Euc-POMO-MTL
9.785%
10.666%
MMc-POMO-MTL
3.710%
4.375%
OVRPBTW
OVRPLTW
MVMoE-L L
9.630%
10.188%
MVMoB-L
3.488%
3.396%
M
9.530%
9,899 %
Moo--
3,335%
3,816 %
Euc- MV-MVVEE--LL
9.592%
10.163%
Euc- M
3.529%
4.063%
MVMоE
9.308%
9.948%
MVMoE
3.396%
3.903%
Mixed-MVMoF
9.2833
9.749 %
Mixed-MVMoF
3.225%
3.560 %
Fuc-MVMoE
9.443%
9.968%
Fuc-MVMoE
3.386%
3.915%
POMO-MTL
9.035%
7.746%
POMO-MTL
9.851
10.498%
Mixed-POMO-MTLL
9.139%
7.658 %
Mixed-POMO-MTTL
9.946%
10.358 %
Euc-POMO-MTL
9.286%
7.761 %
Euc-POMO-MTL
9.967%
10.670%
OVRPBLIW
VRPBLIW
MVMoE-L
8.915%
7.473%
MVMoE-L
9.682%
10.263%
Mixed-MVMoELA
8.871 %
7.278
Mixed-MVMoBE
9.582%
10.027 %
Euc-MVMoE-L
8.996%
7.537%
Euc-MVMoE-L
9.754%
10.247%
MVMoE
8.775%
7.332%
MVMoE
9.516%
10.009%
Mixed-MVMoE
8.690 %
7.304% %
MiXed-MVMoE
9.462%
9.772%
Fuc-MVMoF
8.875%
7.422%
Fuc-MVMoF
9.636%
10.045%
Table 7: Ablation studies whether the improvements performances stem from the increased number of parameters or the design of mixed-curvature geometric spaces. The training configurations are consistent with (Zhou et al., 2024), Comparisons are conducted on MVMoE with 16 VRP variants (6 in-distribution and 10 out-of-diitributiin tasks) in which case each task contains 1,000 instances. Bold indicates best and underline indicates the second-best result. Euc-X represents the model that replaces the mixed-curvature modules with their Euclidean counterparts so that numbers of total parameters for these models are in the same level.
19

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
n=50 Gap
n=100
n=50
n=100
Type Model
Gap
Type Model
Gap
Gap
POMO-MTL
0,987%
1.846%
POMO-MTL
3.637%
5.313%
Mixed-POMO-MTT
0.980 %
1.731 %
Mixed-POMOP POMO-MTL
3,556 %
5.090 %
Mixed-POMO-MTTL (w.o. Mix-up)
1.057%
1.807%
Mixed- PE----PPOOM-TTT (w.o. Mix-up)
3.647%
5.156%
VRPTW MRPTWW
CVRP
MVMoE-L
0.955%
1.728%
MVMoE-L
3.500%
4.927%
Mixed-MVMoE-L.
0,933 %
1.645 %
Mixed-MVMoEEL
3,421 %
4.872 %
Mixed-MVMoE-L (w.o. Mix-up)
0.984%
1.731%
Mixed-MVMoE--L (w.o. Mix-up)
3.516%
5.018%
MVMoF
0.896%
1.653%
MVMoF
3.410%
4.903%
Mixed-MVMoF
0.865 %
1.599 %
Mixed-MVMoE
3.373%
4.732%
Mixed-MVMoE (w.o. Mix-up)
0.890%
1.674%
Mixed-MVV MMoed (w.o. Mix-up)
3,256%
4. 4.897%
POMO-MTI
2.634%
3.458%
POMO-MTL
0,201 %
0.479%
Mixed-POMO-MIII
2.637%
3.312%
Mixed-POMM POMO-MTL
0.185%
0.362
Mixed-POMO-MIII (w.o. Mix-up)
2.607 %
3.373%
Mixed-POMO-MMTL (w.o. Mix-up)
0.205%
0,420%
OVRP
MVMoE-L
2.548%
3.214%
VRPL
MVMoE-L
0.131%
0.323%
Mixed-MVMoE-L
2.448 %
3.133%
Mixed-MMMooE-L
0.098% %
0.270 %
Mixed-MVMoB-L. (w.o. Mix-up)
2.608% %
3.197%
Mixed-MVMoE-LL (w.o. Mix-up)
0.150%
0.350%
MVMoE
2.402%
3.136%
MVMoE
0.092%
0.261 %
Mixed-MVMM (w.o. Mix-up)
2.336 %
2.946 %
MMxed-MVMMEE
0.052 %
0.227 %
2.421%
3.129%
(w.o. Mix-up)
0.086%
0.294%
POMO-MTI
1.684%
1.674%
POMO-MTI.
3.470%
4,41 1%
Mixed-POMO-MTL
1.645 %
1.427 %
Mixed-POMe YOMO-MTL
3,420%
3.996 %
Mixed-POMO-MMTH (w.o. Mix-up)
1.682%
1.517%
O WRRPTW -
Mixed-POMe POMO-MTL (w.o. Mix-up)
3.599%
4.136%
VRPB
MVMoE-L
1.605%
1.368%
MVMoE-L
3.322%
3.941
Mixed-MVMoE-L
1.531
1.265
Mixee--VMoE--L
3.219%
3.749
MiXed-MVMoE-L (w.o. Mix-up)
1.591% %%
1.418%
Mixed-MVMod MVMoE-L (w.o. Mix-up)
3.431%
4.001%
MVMoE
1.540%
1.285%
MVMoE
3,210%
3.852%
1.456 %
1.153%
Mixed- MVMoE
3.060
3,579 %
Mixed-MVMoE (w.o. Mix-up)
1.540%
1.307%
Mixed Mixed-MVMoo MVMoE (w.o. Mix-up)
3.256%
3.939%
POMO-MTL
6.430%
7.335 %
РOМО-MP -TL
2.734%
3,441
Mixed-POMO-P
6.348 %
7.831%
Mixed-POMO POMO-MTI
2.708 %
3.350%
Mixxe-POMO-MMTI (w.o. Mix-up)
6.298%
7.414%
Mixed-POMO-Aae (w.o. Mix-up)
2.830%
3,332 %
OVRPB
OVRPL
MVMoE-L
%
7.243%
MVMoE-L
2.597%
3.244%
Mixed-MVMole
6.175 %
6.997 %
Mixed-MV
2.497%
3.159 %
Mixed-MVMoE-L (w.o. Mix-up)
6.241 %
7.094%
(w.o. Mix-up)
2.668%
3.173%
MVMoE
5 5,999%
7.088%
MVMoE
2.454%
3.148%
Mixed-MVMoE
5.871 %
6.800 %
2.419
2.971 1
Mixed-MVMoE (w.o. Mix-up)
5.760%
6.782%
Mixed-MVMoE (w.o. Mix-up)
2.505%
3.152%
POMO-MTL
1.971%
1.793%
POMO-MTL
8.841
7.413%
1.905 %
1.514%
Mixed-POMO POMO-MTL
8.934%
7 7.457%
Mixed-POMOO-MTL. (w.o. Mix-up)
1.987%
1.639%
Sieed-POMO-MTL.C (w.o. Mix-up)
8.900%
7.383 %
VRPBL
MVMoF.-L
1.872%
1.473%
MVMoF-I.
8.745%
7.190%
Mixed-MVMoF-L
1.781 %
1.378 %
Mixed-MVMoRE
8.715 %
7.018 %
Mixed-MVMoB.L. (w.o. Mix-up)
1.860%
1.531
Mixed-MVMoF.I. (w.o. Mix-up)
8.790%
7.169%
MVMoE
1.776%
1.346%
MVMoE
8.600%
4.903%
Mixed-MVMoE
1.729 %
1.264%
Mixed-MVM
8.545 %
4.732
Mixed-MVMoE (w.o. Mix-up)
1.773%
1.430%
Mixed-MVMoE (w.o. Mix-up)
8.649%
7.041
POMO-MTL
2.586 %
1.920%
POMO-MTL
6.306%
7.343%
Mixed-POMO-MITL
2.621 %
1.673% %
MixeedPOMO-MTL
6.282%
7.919%
Mixed-POMO-MTL. (w:o. Mix-up)
2.670%
1.805%
Mixed-PO POMO--OO (w.o. Mix-up)
6.111
7.460%
VRPLTW
OVRPBL
MVMoEE-
2.535%
1.545%
MVMoE-L.
6.310%
7.300%
Mixed-MVMoB-L
2,448
1.515
Rixed-MVMoF-L
6.077%
7.027
Mixed-MVMoE-L (w.o. Mix-up)
2.533%
1.601%
MVMoE-LL (w.o. Mix-up)
6.198%
7.109%
M
2,421%
1.471%
MVMoE
5.843%
7.115%
MiXed-MVMoE
2.387 %
1.365
5.705
6.857
Continued on the next page
20

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
n=50
n=100
n=50
n=100
Type Model
Gap
Gap
Type Model
Gap
Gap
Mixed-MVMoE (w.o. Mix-up)
2.478%
1.523%
Mixed-MVMoo (w.o. Mix-up)
5.705%
6.809%
POMO-MTL
9.628% %
10.453%
POMO-MTL
3.633%
4.374%
Mixed-POMO-MTTL
9.734%
10.192 %
Mixed-POMO--TTI
3,600 %
4,020 %
OVRPBTW
Mixed-POMO-MTII (w.o. Mix-up)
9.818%
10.251 %
OVRPLIW
Mixed-POMO POMO-MTL (w.o. Mix-up)
3.765%
4.124%
MVMoE-L
9,630%
10.188%
MVMoE-L
3,488%
3.396%
9.530 %
9.899 %
Mixed- MVMoE-L
3,335 %
3,816 %
Mixed-MVMon MVMoE-L (w.o. Mix-up)
10.032% 9.639%
Mixed-MVMoEEI (w.o. Mix-up)
3.546%
4.037%
MVMoE
9.308%
9.948%
MVMoE
3.396%
3.903%
9,283 %
9.749 %
Mixed-MV
3,225% %
3,560 %
Mixed-MVMoF (w.o. Mix-up)
9 9.441 %
10.096%
Mixcd-MVMoE (w.o. Mix-up)
3.434%
3.932%
POMO-MTL
9.035 %
7.746%
POMO-MTL
9.851 %
10.498%
Mixed-POMO-MTT.
9.139%
7.658 %
Mixed- POMO-MTL
9.946%
10.358
VRPBLTW
Mixed-POMO MOMMLTLLLLL (w.o. Mix-up)
9.102%
7.699%
Mixed-POMO- POMO-MTL (w.o. Mix-up)
9.940%
10.323%
MVMoE-L
8.915%
7.473%
MVMoE-L
9,682%
10.263%
Mixed-MVMEEL
8,871 %
7.278% %
Mixed- MVMoE-L
9.582 %
10.027
Mixed-MVMoE-LL (w.o. Mix-up)
9.013%
7.410%
Mixed-MVMoE-A (w.o. Mix-up)
9.764%
10. 135%
MVMoE
8.775%
7.332%
MVMoE
9.516%
10.009%
Mixed-MVMoE
8.690 %
7.304%
Mixed-MVMoE
9.462
9.772%
Mixed-MVMoF (w.o. Mix-up)
8.881 %
7.351%
Mixed-MVMoF (w.o. Mix-up)
9.579%
10.201 %
Table 8: Ablation studies whether the Mix-up module brings improvements on performances. The training configurations are consistent with (Zhou et al., 2024). Comparisons are conducted on MVMoE with 16 VRP variants (6 in-distribution and 10 out-of-distribution tasks) in which case each task contains 1,000 instances. Bold indicates best and underline indicates the second-best result.
Model
Parameters
POMO-MTL
1,254,656
Hixed-POMO-MMT
1,386,810
MVMoF-Light
3,698,944
Mixed-MVMoOE-Lgee
3,831,116
MVMoE
3,682,176
Mixed-MVMoE
3,814,348
Table Comparisons for the number of parameters in each baseline model and their mixed curvature space counterparts. Our comparisons based on the models mentioned in (Zhou al., 2024). For the embedder, insert mixed-curvattee modules for processing features from depot and customer nodes, respectively. For each layer of encoder, we insert one mixed-curvature module for processing features from the previous layer. In specifics, the ratio of increased parameters is between 3.57% and 10.56% compared to baselines.
21

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
n=50
n=100
n=50
n=100
Type
Model
Gap
Gap
Type
Model
Gap
Gap
Mixed-POMO POMO-MTL-44
1.011%
1.840%
Sixed-POMO-MTL-4
3.583%
5.205%
CVRP
Mixed-POME POMO-MTL-8
0.980%
1.731 %
VRPTW
Mixed-POMO-MTL-S
3,556 %
5.090 %
POMO-MPOMO-
1.009%
1.80%
Mixcl-POMOO-MTT-16
3.570%
5.250%
Mixed-POMOO POMO-MTL-4
2.645%
3.465%
PIxee-PPMMO-TT--4
0.193%
0.450%
OVRP
Mixed- POMO-MTL-8
2.637%
3.312 %
VRPL
0.185 %
0.362
Mixed-POne 10MO-MTL-16
2.592%
3.367%
Hixed-POMO-MTLL-.
0.187%
0.456%
Mixed-POMOO POMO-MTL-4
1.678%
1.585%
Mixed-POMO-MTL-4
3.423%
4.361%
VRPB
Sixed-POMO-MTL-S
1.645%
1.427% %
OVRPTW
3.420%
3.996 %
Ponecl-OMO-MTII-116
1.65%%
1.564%
Mixcx-POMMO-MTI--I
3.475%
4.234%
Mixed-POMO-NO POMO-MTL-4
6.279%
7.470%
Mixed-PPMMO-TT-4
2.737%
2.692 %
OVRPB
Mixed-POMOAAD POMO-MTI--8
6.348%
7.831 %
OVRPI.
Hixed-POMO--TI--S
2.708%
3.350%
Mixed- 10M0-MTL-0-
6.290%
7.328 %
Mixed-POMOO-MTL-16
3.356%
3.349%
Mixed-POMO-MIII POMO-MTL-4 1.947%
1.729%
Sixcl-POMO-MTT-4
8.820%
7.548%
VRPBL
Sixed-POMO-MTL-S
1.905%
1.514%
VRPBTW
Mixed-
Ponccl-OO-MMT--SS
8.934%
7.457%
Mixed-POME POMO-MTL-16
1.956%
1.696%
1oxed-POMO-MTL-16
8.847%
7.402%
Mixed-PORE POMO-MTL-4
2.520%
1.830%
POMO-MTL-4
6,151 %
7.444%
VRPLTW
Mixed- POMO-MTI.-S
2.621%
1.673%
OVRPBI.
Mixed-POMI POMO-MTI--8
6.282%
7.919%
Mixed SroeedPOOO-AAA POMO-MTL-16
2.585%
1.891 %
Mixed-POMO-NE POMO-MTL-16
6.160%
7.376%
Mixed-POMO-MIE POMO-MTL-4
9.788%
10.470%
Sixcd-POMO-MTL-
3.630%
4.382%
OVRPBTW Mixed-POMO-MTI POMO-MTL-8
9.734%
10.192 %
OVRPLTW Hixed-POMO-MTTI
3.600%
4.020% %
Mixed-POMOAA POMO-MTL-16
9.698%
10.415%
1ixed-POMO-MTL-16
3.573%
4.270%
Pinel--OMOMTTL-4
9.022%
7.731 %
Mixxl-POMO-MTL-4
9.836 %
10.583%
VRPBLTW Mixed-POMEE POMO-MTI--
9.139%
7.658%
OVRPBLTWW Mixel-POMO-MTTI-8
9.946%
10.358%
Hixed-POMO-MTEE 9.112%
7.733%
Mixed-POMO-MILLI6
9.868%
10.488%
Table Ablation studies on number subspaces mixed-curvature modules. The training configurations are consistent with (Zhou al., 2024). Comparisons conducted on POMO-MTL with 16 VRP variants in which cases each task contains 1,000 instances. Bold indicates best value and underline indicates second best result.
22

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
100
avg
190
avg
35
avg
Count
Count
Count
60
20
40
15
20
-S.c0 5..0--075--00
1.70--0.75
-..00
Curvature
Curvature
Curvature
(a) OVRPB
(b) OVRPL
(c) VRPBL
avg
avg
avg
40
50
40
Count
30-
Count
Count
30-
30
20.
20-
20
10
10
10-
-1.00
2.75 75-5--5-8880
0.50
-.25
0.00
025
050
0.75
1.00
-
-0.75 -2 50 0225 não
n25
0.50
6.75
1.00
$ 0.00
-0.75
-0.0
0.00
0.25
0.50
0.75
1.0
Curvature
Curvature
Curvature
(d) VRPBTW
(e) VRPLTW
OVRPBI.
70
60.
25
50
Count
Count
Count
40-
18
30
20
20
10
10
-1.00 0.000.75
-1.00
-.50-00000-0 0.25
0.75 1.00
-..00
3..00-0755
0.25
0.50 0.55 1000
Curvature
Curvature
Curvature
(g) OVRPBTW
(h) OVRPLTW
ii VRPBLTW
avg
Count
20.
20.
10
00 -0.5
-550-000
0.00 0.25 0.50 0.75 1.00
Curvature
(i) OVRPBLTW
Figure 4. The histogram of curvatures each node from the remaining 10 VRP tasks. We utilize 1,000 instances with size 50 for each task to visualize curvature information. The x-axis represents curvature values, while the y-axis denotes the count of cach value. The all nodes. We adopt Ollivier-Ricel curvature (Ollivier, 2009) which especially suitable
avg line indicates the average for measuring curvatures on discrete structures like graphs. From the information in the figure, shows that almost every node in cach task dataset either negative or positive curvature and the average curvature suggests that each task contains non- Euclidean geometry patterns. Better viewed in color.
23

---

Mixed-Curvature based Pre-training Paradigm for Mulk Vehicle Routing Solver
OllivierRicii Curvature
d OllivierRicci Curvature
1 Rilivie-Ricci Curvature
1
(a) N=50
(b) N=100
(c) N=1.5
i Ollivier-Rice Curvature
S Ricci Curvature
Ollivier-Rici Curvature
2 5
(d) N=200
(e) N=250
(f) N=300
Ollivier-Ricii Curvature
OllivierRicei Curvature
Ollivier-Rlcei Curvature
o
(g) N=350
(h) N=400
(i) N=450
Ollivier-Ricel Curvature
Ollivier-RRici Curvature
Ollivier-Rici Curvature
N=500
(k) N=600
(1) N=800
Figure 5. Visualization of Ollivier-Rice curvatures random generated complete graphs with different sizes. Each node's coordinate restricted in the 2D region [-1, 1] x [-1, For each complete graph, we use KNN to select 5 nearest neighbors of each node. Warm (cold) colors represent positive (negative) curvatures. From these presented results, often link distant nodes while edges with positive curvatures often exist in highly clustered regions. This property is shared among all of the node sizes. Better viewed color.
observe that edges with negative
24

---

Mixed-Curatture based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
Appendix.2. Detailed Experimental Configurations with (Zhou et al., 2024)
Definitions of Constraints in Utillzed Tasks
We follow the settings of (Kool et al., 2019; Kwon et al., 2020; Zhou et al., 2024) and details listed follows:
Coordinates: We focus on uniform distribution setting which case each node's 's locations are sampled from ((0, 1) in a unit square.
Capacity:
We set capacity to 40 and 50 for N = 50 and N = 100, respectively. Note that one of the hard constraints involved in each task is that nodes with demands greater than delivery vehicle's ' current demand are masked.
Demand: We sample the demand of each node from the list ... 9}. Note that before sending into model, the node demand is normalized by the demand of delivery vehicle.
Open Route: We it as an indicator vector with all ones. During decoding stage, we need to manually set mask to prevent delivery vehicle from going back to the depot node.
Backhauls: Similar to demand setting, we sample from {1, 2, ,.. 9) as our initial demands. Then, in the same way as that of (Liu al., 2024), we sample 20% of nodes be the backhauls nodes.
Duration Limit: We set it to 3, which represents the maximum length of delivery vehicle's route.
Time Window: For the depot node, we assign its time window as [0, and service time for depot by default.
However, service time for customer nodes is set 0.2 and time window for customer nodes sampled from uniform distribution.
By combining constraints in different ways, we can obtain various kinds of tasks as listed in Table 11. Since some nodes don't 't have features like time-windowe or backhauls, these features will separately appear in the encoder module.
Capacity (C) Open Route (O) Backhauls (B)
Duration Limit (L) Time Window (TW)
CVRP
VRPTW
AANTAA KAKY
X
AXX
OVRP
X
VRPL
VRPB
OVRPTW
OVRPB
OVRPL
VRPBL
VRPBTW
VRPLTW
OVRPBL
OVRPBTW
OVRPLTW
VRPBLTW
OVRPBLTW
Table Detailed descriptions of constraints contained in each problem type. We have 16 VRP tasks in total. The first VRP tasks get involved in training stage and the last 10 tasks are used for saro-sho//few-sht testings.
25

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
Hyper-Parameters
Value
Training Epochs
5,000
Fine-tuning Epochs
10
Instances in each Training Epoch
20,000
Instances in each Fine-tuning Epoch
10,000
Optimizer
Adam
LR Scheduler LR Milestones
MultiStepLR
[4,501]
LR Gamma
0.1
Training Learning Rate
le-4
Fine-tuning Learning Rate
lc-4
Weight Decay
le-6
Training Batch Size
128
Fine-tuning Batch Szie
128
Evaluation Batch Size
64
Problem Scales
{50, 100}
Node Distribution
UO0,1)
Number of Experts in MoE
Auxiliary Loss Weight in MoE
0.001
Gating Mechanism in MoE Embedding Size
node-level, input-choice gating
128
Hidden Feature Size
512
Number of Encoder Layers
6
QKV Dimension
16
Attention Head Number
Logit Clipping
10
Evaluation Type
argmax
Number of Experts in MoE for Routing
2
Number of Subspaces (C)
Initialization value of Curvature (k)
Initialization value of a, 3
{1,1}
This configuration is consistent with (Zhou et al., 2024). However, other choices number subspaces are also valid as long as the sum of subspaces' dimensions equals 128. Even if 128 not divisible by number of subspaces, can still determine dimensions manually automatically (e.g., neural architecture search (Elsken et al., 2019)).
Table 12. Detailed experiment settings of
26

---

Mixed-Curvtture based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
Appendix.3. Real-World Experimental Results with (Zhou al., 2024) and Subspace Visualizations
Set-Solomon
POMO
POMO-MTL
MVMoE
Mixed-POMO-MITI
Instance
Opt
Obj
Gap
Obj
Gap
Obj
Gap
Obj
Gap
R101
1637.7
1805.6
10.252%
1821.2
11.205%
1798.1
9.794%
1862.3
13.714%
R102
1466.6
1556.7
6.143%
1596.0
8.823%
1572.0
7.187%
1634.1
11.422%
R103
1208.7
1341.4
10.979%
1327.3
9.812%
1328.2
9.887%
1374.1
13.687%
R104
971.5
1118.6
15.142% %
1120.7
15.358%
1124.8
13.780%
1134.4
16.767%
R105
1355.3
1506.4
11.149%
1514.6
11.754%
1479.4
9.157%
1569.7
15.818%
R106
1234.6
1365.2
10.578%
1380.5
11.818%
1362.4
10.352%
1413.4
14.480%
R107
1064.6
1214.2
14.052%
1209.3
13.592%
1182.1
11.037%
1230.2
15.556%
R108
932.1
1058.9
13.604%
1061.8
13.915%
1023.2
9.774%
1063.0
14.046%
R109
1146.9
1249.0
8.902%
1265.7
10.358%
1255.6
9.478%
1258.2
9.704%
R110
1068.0
1180.4
10.524%
1171.4
9.682%
1185.7
11.021%
1213.2
13.593%
RI11
1048.7
1177.2
12.253%
1211.5
15.524%
1176.1
12.148%
1189.8
13.453%
R112
948.6
1063.1
12.070%
1057.0
11.427%
1045.2
10.183%
1097.3
15.676%
RC101
1619.8
2643.0
63.168%
1833.3
13.181% %
1774.4
9.544%
1882.7
16.231%
RC102
1457.4
1534.8
5.311 %
1546.1
6.086%
1544.5
5.976%
1616.4
10.907%
RC103
1258.0
1407.5
11.884%
1396.2
10.986 %
1402.5
11.486%
1403.0
11.526%
RC104
1132.3
1261.8
11.477%
1271.7
12.311%
1265.4
11.755%
1252.6
10.628%
RC105
1513.7
1612,9
6.553%
1644.9
8.668%
1635.5
8.047%
1660.1
8.382%
RC106
1372.7
1539.3
12.137%
1552.8
13.120%
1505.0
9.638%
1497.2
9.072
RC107
1207.8
1347.7
11.583%
1384.8
14.655%
1351.6
11.906%
1330.8
10.180% %
RC108
1114.2
1305.5
17.169%
1274.4
14.378%
1254.2
12.565%
1273.9
14.332%
RC201
1261.8
2045.6
62.118%
1761.1
39.570%
1577.3
25.004%
1595.3
26.428%
RC202
1092.3
1805.1
65.257%
1486.2
36.062%
1616.5
47.990%
1416.4
29.672%
RC203
923.7
1470.4
59.186%
1360.4
47.277%
1473.5
59.521%
1223.3
32.433 %
RC204
783.5
1323.9
68.973%
1331.7
69.968%
1286.6
64.212%
1103.8
40.887 %
RC205
1154.0
1568.4
35.910%
1539.2
33.380%
1537.7
33.250%
1365.2
18.301 %
RC206
1051.1
1707.5
62.449%
1472.6
40.101%
1468.9
39.749%
1239.7
17.939%
RC207
962.9
1567.2
62.758%
1375.7
42.870%
1442.0
49.756%
1264.7
31.345% %
RC208
776.1
1505.4
93.970%
1185.6
52.764%
1107.4
42.688%
1113.0
43.407 %
Average Gap
29.658%
21.380%
20.317%
17.84 %
Table Zero-Shot Inference on VRPTW benchmark instances from Set-Solomon. Each model trained on n=100, following the settings in (Zhou et al., 2024).
27

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
Sct-X
POMO
POMO-MTL
MVMoE
Mixed-POMO-MII
Instance
Opt
Obj
Gap
Obj
Gap
Obj
Gap
Obj
Gap
X-n101-k25
27591
30138
9.231
32482
17.727%
29361
6.415
29676
7.557%
X-n106-k14
26362
39322
49.162%
27369
3.820%
27278
3.475%
27821
5.936%
X-n110-k13
14971
15223
1.683%
15151
1.202%
15089
0.788%
15226
1.703%
X-n115-k10
12747
16113
26.406%
14785
15.988%
13847
8.629%
13328
4.558%
X-n120-k6
13332
14085
5.648%
13931
4.493%
14089
5.678%
14039
5.303%
X-n125-k30
55539
58513
5.355%
60687
9.269%
58944
6.131%
59642
7.388%
X-n129-k18
28940
29246
1.057%
30332
4.810%
29802
2.979%
29476
1.852%
X-n134-k13
10916
11302
3.536%
11581
6.092%
11353
4.003%
11298
3.499%
X-n139-k10
13590
14035
3.274%
13911
2.362%
13825
1.729%
13760
1.251
X-n143-k7
15700
16131
2.745%
16660
6.115%
16125
2.707 %
16070
2.357%
X-n148-k46
43448
49328
13.533%
50782
16.880%
46758
7.618%
47157
8.537%
X-n153-k22
21220
32476
53.040%
26237
23.643%
23793
12.125%
23392
10.236%
X-1157-k13
16876
17660
4.646%
17510
3.757
17650
4.586%
18444
9.291%
X-n162-k11
14138
14889
5.312%
14720
4.117%
14654
3.650%
14588
3.183%
X-n167-k10
20557
21822
6.154%
21399
4.096%
21340
3.809%
21141
2.841 %
X-n172-k51
45607
49556
8.659%
56385
23.632%
51292
12.465%
48815
7.034%
X-n176-k26
47812
54197
13.354%
57637
20.549%
55520
16.121%
52593
10.000%
X-n181-k23
25569
37311
45.923%
26219
2.542%
26258
2.695%
27552
7.755%
X-n186-k15
24145
25222
4.461%
25000
3.541%
25182
4.295%
24900
3.127%
X-n190-k8
16980
18315
7.862%
18113
6.673%
18327
7.933%
18593
9.499%
X-n195-k51
44225
49158
11.154%
54090
22.306%
49984
13.022%
48689
10.094%
X-n200-k36
58578
64618
10.311%
61654
5.251
61530
5.039
61844
5.575%
X-n209-k16
30656
32212
5.076%
32011
4.420%
32033
4.492%
31828
3.823%
X-n219-K73
117595
133545
13.564%
119887
1.949
121046
2.935%
125002
6.299%
X-n228-k23
25742
48689
89.142%
33091
28.549%
31054
20.636%
29244
13.604%
X-n237-k14
27042
29893
10.543%
28472
5.288%
28550
5.577%
28850
6.686%
X-n247-k50
37274
56167
50.687%
45065
20.902%
43673
17.167%
41142
10.377 %
X-n251-k28
38684
40263
4.082%
40614
4.989%
41022
6.044%
40792
5,449%
Average Gap
16.629%
9.820%
6.884%
6.243 %
Table Zero-Shot Inference on CVRP benchmark instances from Set-X. Each model is trained on n=100, following settings in (Zhou et al., 2024).
28

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
Set-X
POMO
POMO-MTI.
MVMoE
Mixed-POMO--MTL.
Instance
Opt
Obj
Gap
Obj
Gap
Obj
Gap
Obj
Gap
X-n502-k39
69226
75617
9.232%
77284
11.640%
73533
6.222%
81423
17.619%
X-n513-k21
24201
30518
26.102%
28510
17.805%
32102
32.647%
29529
22.016%
X-n524-k153
154593
201877
30.586%
192249
24.358%
186540
20.665%
173928
12.507 %
X-n536-k96
94846
106073
11.837%
106514
12.302%
109581
15.536%
105632
11.372%
X-n548-k50
86700
103093
18.908%
94562
9.068%
95894
10.604%
95680
10.358%
X-n561-k42
42717
49370
15.575%
47846
12.007%
56008
31.114%
49619
16.158%
X-n573-k30
50673
83545
64.871%
60913
20.208%
59473
17.366%
57588
13.646%
X-n586-k159
190316
229887
20.792%
208893
9.761 %
215668
13.321% %
212404
11.606%
X-n599-k92
108451
150572
38.839%
120333
10.956 %
128949
18.901 %
120722
11.315%
X-n613-k62
59535
68451
14.976%
67984
14.192%
82586
38.718%
71275
19.719%
X-n627-k43
62164
84434
35.825%
73060
17.528%
70987
14.193%
69334
11.534%
X-n641-k35
63682
75573
18.672%
72643
14.071%
75329
18.289%
71750
12.669 %
X-n655-k131
106780
127211
19.134%
116988
9.560 %
117678
10.206%
120227
12.593%
X-n670-k130
146332
208079
42.197%
190118
29.922%
197695
35.100%
170403
16.450%
X-n685-k75
68205
79482
16.534%
80892
18.601%
97388
42.787%
80512
18.044%
X-n701-k44
81923
97843
19.433%
92075
12.392%
98469
20.197%
90724
10.734%
X-n716-k35
43373
51381
18.463%
52709
21.525%
56773
30.895%
50798
17.119%
X-n733-k159
136187
159098
16.823%
161961
18.925%
178322
30.939%
161089
18.285%
X-n749-k98
77269
87786
13.611%
90582
17.229%
100438
29.985%
87907
13.767%
X-n766-k71
114417
135464
18.395%
144041
25.891%
152352
33.155%
128375
12.199
X-n783-k48
72386
90289
24.733%
83169
14.897%
100383
38.677%
84181
16.295%
X-n801-k40
73305
124278
69.536%
85077
16.059%
91560
24.903%
86152
17.525%
X-n819-k171
158121
193451
22.344%
177157
12.039%
183599
16.113%
183792
16.235%
X-n837-k142
193737
237884
22.787%
214207
10.566%
229526
18.473%
213651
10.279
X-n856-k95
88965
152528
71.447%
101774
14.398%
99129
11.425 %
115359
29.668%
X-n876-k59
99299
119764
20.609%
116617
17.440%
119619
20.463%
112067
12.858 %
X-n895-k37
53860
70245
30.421%
65587
21.773%
79018
46.710%
69614
29.250%
X-n916-k207
329179
399372
21.324%
361719
9.885% %
383681
16.557%
365822
11.132%
X-n936-k151
132715
237625
79.049%
186262
40.347%
220926
66.466%
167584
26.274%
X-n957-k87
85465
130850
53.104%
98198
14.898%
113882
33.250%
117787
37.819%
X-n979-k58
118976
147687
24.132%
138092
16.067%
146347
23.005%
132921
11.721 %
X-n1001-k43
72355
100399
38.759%
87660
21.153%
114448
58. 18.176%
88897
22.862%
Average Gap
29.658%
16.769%
26.048%
16.614%
Table 15. Zero-Shot Inference on large-scale CVRP instances from Set-X. Each model trained on the size n=100, following the setting in (Zhou et al., 2024).
29

---

A Mixed-Curaature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
Curvature(N=50)
Curvature(N=100)
0.8
Embedder -4009
Embedder
-0.19
0.8
Layer 2 0.03
.0.10
0.04
0.02
-006
-0.15
.0.10
0.33
Layer 2
0.35
0.08
-0.16
-0.31
0.04
-0.31
0.62
-0.01
Layer
0.03
0.03
-0.00
0.04
0.04
0.04
0.05
-0.02
Layer
0.05
-0.02
0.04
0.04
0.08
0.05
-0.00
0.03
0.4
0.4
0.2
0.2
0.04
0.01
0.43
0.03
0.06
0.35
0.19
-0.03
0.52
0.40
0.78
0.58
0.60
0.65
0.47
-0.0
-..0
Layer 0.15
0.46
0.48
0.45
0.34
0.47
0.49
0.48
Layer
0.76
0.68
0.69
0.68
0.76
0.72
0.87
0.75
-00
Layer
Layer
-0.35
Subspace Index
Subspace Index
Figure Visualization of curvature for each subspace each layer in the encoder module. Shown model Hixed-POMO-MTI The shown colors indicate that subspaces in shallower layers tend to reside in hyperbolic space. As the layer index increases, more subspaces shift closer spherical geometry. The tendency towards spherical geometry even more serious
N 100. However, we also observe unexpected change in last layer where curvatures cluster around zero. Such kind of inconsistency may explain the inferior performances of Mixed-POMO POMO-MTL on some unseen tasks like VRPBIW. Better viewed color.
30

---

Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
Curvature(N=100)
Embedder - -0.09 -0.07 -0.23 -0.15
-0.10
-0.10
-0.24
40.9
1.75
Embedder
-0,02
-0.14
-0.30
-0.01
-0.07
-0.08
-0.01
-0.20
0.8
Layer 2 -0.05 0.10
-0.19
0.06
-0.06
-0.18
0.04
00008
1.50
Layer 2 -00.08
0.04
0.05
0.07
0.05
-0.13
0.08
-0.08
0.6
1.25
Layer
Layer
0.49
00.4
1.00
0.51
0.58
0.44
0.44
0.74
0.57
0.14
0.38
4
0.44
0.46
0.65
0.49
0.52
0.53
0.35
0.13
-0.2
Layer 5 0.36
0.53
0.18
0.30
0.57
1.05
0.42
0.46
Layer
0.64
0.49
0.57
0.90
0.79
0.60
0.42
0.18
0.0
Layer
0.36
0.56
0.48
1.20
0.47
1.99
0.41
0.01
Layer 6
0.05
0.81
0.51
0.84
0.43
0.01
0.36
0.31
Layer
Layer 0.60
0.46
-0,2
3
Subspace Index
Subspace Index
Figure 7. Visualization of curvature for each subspace of each layer in the encoder module. Shown model is Mixed-MVMoEL The shown colors indicate that subspaces shallower layers tend to reside in hyperbolic space. As the layer index increases, more subspaces shift closer to spherical geometry. Compared with Mixed-POMO POMO-MTL is consistent the layer deepens. Better viewed in color.
(urvature(N=SO)
Curvature(N=100)
1.0
-0.17
-0.15
1.0
-0.11
-0.08
0.07
0..9
-0.05
-0.10
0.04
-0.07
0.8
0.07
-0.01
-0.09
0.07
1.17
-0.11
-0.10
-0.15
0.8
Layer 3
0.02
0.15
.0.02
0.28
0.49
-0.05
-0.03
.0.03
0.6
Layer 3
..008
-0.02
-0.02
-0.03
-0.03
0.28
0.46
0.37
0.6
Layer
Layer
0.53
0.42
0.70
0.52
0.58
0.54
0.04
0.37
Layer
Layer
-0.04
-0.02
0.36
0.37
0.38
0.05
0.04
-0.03
0.4
Layer
0.2
0.2
Layer
0.82
0.44
0.59
0.71
0.77
0.61
0.55
0.44
0.0
Layer
0.21
0.40
1.11
0.44
0.87
1.19
0.58
0.50
Layer
0.52
0.50
0.42
0.52
-0.12
0.62
0.50
0.44
-00
Layer -0.05
-0.22
-0.03
-0.02
-0.08
0.23
-0.02
0.30
-0.2
Subspace Index
Subspacn Index
Figure Visualization of curvature each subspace each layer the encoder module. Shown model is Mixed-MVMoE (n=100). The shown colors indicate that subspaces in shallower layers tend to reside in hyperbolic space. As the layer index increases, more subspaces shift closer to spherical geometry. As we can observe from the presented color gradients, MVMoE sometimes can learn very positive curvatures in the shallow layer. We hypothesize this maybe due the fact that MVMoE doesn't apply approximate routing mechanism so that model itself acquires much stronger abilities to capture high-level information. Better viewed in color.
31

---

Mixed-Curvtture based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
Appendix.4. Detailed Experimental Configurations, Results and Visualizations with RouteFinder (Berto et al., 2024)
Definitions of Constraints in Utillied Tasks
In this case, follow the settings of (Berto et al., 2024) and details are listed as follows:
Coordinates: We focus on uniform distribution setting which case each node's locations are sampled from U(0, 1) in a unit square.
Capacity:
We set capacity to 40 and 50 for n = 50 and n = 100, respectively. Note that one of the hard constraints involved in each task is that nodes with demands greater than dilvery vehicle's current demand are masked.
Demand: We sample the demand of each node from the list ... .). Note that before sending into model, the node demand is normalized by the demand of delivery vehicle.
Open Route: We it as an indicator vector with all ones. During decoding stage, we need to manually set mask to prevent vehicle from going back the depot node.
Backhauls: Similar to demand setting, we sample from f1,2...., 9 as our initial demands. Then, the same as in (Liu et al., 2024), we sample 20% nodes to be the backhauls nodes.
Duration Limit: We set it to 3, which represents the maximum length of delivery vehicle's route.
Time Window: For the depot, we assign its time window as [0, 3] and service time for depot is by default. However, service time for customer nodes set to 0.2 and time window for customer nodes sampled from uniform distribution.
Mixed: In the regular setting, there is a strict preceeding ordering between linehaul and backhaul customers. However, the mixed scenario allows linchaul and backhaul customers to happen an interleaved manner.
By combining constraints in different ways, we can obtain various kinds of tasks in Table 16. Since some nodes don't have features like time-windows and backhauls, these features will separately appear in the encoder module.
Capucity (C) Open Route (O)
Backhauls (B)
Duration Limit
Time Window
Mixed
VRPTW
OVRP
VRPL
VRPB
OVRPTW
OVRPB
OVRPL
VRPBL
VRPBTW
VRPLTW
OVRPBTW
OVRPLTW
VRPBLTW
OVRPBLTW
VRPMB
OVRPMB
VRPMBL
VRPMBTW
OVRPMBL
OVRPMBTW
VRPMBLTW
OVRPMBLTW
Table Detailed descriptions of constraints coutained in each problem type. We have 24 VRP tasks in total. Note that first 16 VRP tasks get involved in training stage and the last 8 tasks are used for few-shot testings.
32

---

A Mixed-Curvature based Pre-training Paradigm for Mulki-Task Vehicle Routing Solver
Hyper-Parameters
Value
Training Epochs
300
Fine-tuning Epochs
10
Instances in each Training Epoch
100,000
Instances each Fine-tuning Epoch
10,000
Optimizer
Adam
LR Scheduler
MultiStepLR
LR Milestones
[270,295]
LR Gamma
0.1
Gradient Clips
1.0
Training Learning Rate
3e-4
Fine-tuning Learning Rate
3e-4
Weight Decay
1e-6
Training Batch Size
256
Fine-tuning Batch Szie
256
Evaluation Batch Size
128
Problem Scales
{50, 100} (0,1)
Node Distribution
Number of Experts in MoE
4
Auxiliary Loss Weight in MoE
0.001
Gating Mechanism in MoE Embedding Size Hidden Feature Size
node-level, input-choice gating
128
512
Number of Encoder Layers
6
QKV Dimension
16
Attention Head Number
8
Logit Clipping
10
Evaluation Type
argmax
Number of Experts in MoE for Routing
2
Number of Subspaces (C)
8
Initialization value of Curvature (R)
0
Initialization value of a, B
{ {1.1}
Table 17. Detailed experiment settings of hypee--arameters for RouteFinder (Berto et al., 2024) based model. However, other choices for the number of subspaces also valid long the sum of subspaces' dimensions equals 128. Even if 128 not divisible number of subspaces, we can still determine dimensions manually or automatically (e.g., neural architecture search (Elsken et al., 2019)).
33

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
n=50
I= 100
n=50
100
Type
Model
Obj
Gap
Time
Obj
Gap
Time
Type
Model
Obj
Gap
Time
Obj
Gap
Time
HGS-PyVRP
10,372
0,000%
10,4m
15.628
0.000%
80.8m
HGS-PyVRP
16.03]
0.000%
10,4m
25.423
0.000%
20,8m
OR-Taols
10.572
1.907%
10.4m
16,280
4.178%
20
OR-Tools
16.089
0.347%
10.4m
25.814
1.506%
20.8m
MTPOМO
10.518
1.111%
1s
15.934
1.988%
7s
MTPOMO
16.410
2.364%
Is
26.412
3.873%
7s
Mixcd-MTPOMO
10,518
1.413%
2s
15.951
2,095%
8s
Mixod-MTPOMO
16,414
2.391
2s
26. 26.388
3. 3.78%%
8s
MVMoE
10,501
1.242%
2s
15,888
1.694%
9%
MVMoE
16.404
2.329%
2s
26.389
3.788%
9s
Mixed MVMoE
10,503
1 1.265%
36
15.887
1.890%
10s
Mixed Mixed-MVMof MVM
16.396
2.272%
3s
26.387
3.775%
10s
RF-MoR
10,499
1.2266%
2s
15,876
1.6225%
9%
RF
16.389
2.234%
2s
26.322
3.519%
9s
Mixed-RF-MVMA
10,500
1.230%
38
15,866
1.559%
10s
MiXod-RF-MMMME
16.371
2.118%
36
26.307
3,457%
10s
RE-TE
10.504
1.2744%
2x
15,857
1.505%
7s
RE-TE
16.364
2.077%
Is
26.235
3.178%
74
Mixed-RF-TE
10.493
1.166
38
15.846
1.440%
98
MiXod-RF-TE
16.320
1.798 %
26.167 3s
2.914%
9s
HGS-PyVRP
6.507
0.000%
10
9.725
0.000%
20.8m
HGP
10.587
0.000%
10.4m
15.766
0.000%
20.8m
OR-Tools
6.553
0,686%
10.4m
9.995
2.732%
20 8m
OR-Tools
10.570
2.343%
10,4m
16.466
5,3024
20,8m
MTPOМO
6.718
3,209%
Is
10.210
4,965%
66
MIPOMO
10.775
1.734%
1s
16.149
2.434%
7s
MTFOM
6.714
3.150%
28
10.230
5.166%
8s
Mixed-MIPOMO
10.771
1.698%
2s
16.161
2.5133%
8s
OVRP
MVMoE
6.702
2.965%
2%
10.177
4.6211%
9%
VRR
MVMoE
10.751
1.505%
2s
16.099
2.1155
96
Mixed-MVMoE
6.699
2.929%
36
10.181
4.658%
9%
MiXcd-MVMoE
10.752
1.523%
36
16.099
2.118%
9s
RF MoE
6.697
2.886%
2%
10.139
4.229%
9%
MoE
10.737
1.388%
2s
16.070
1.941%
9%
MVMMME
6.689
2.764%
36
10.137
4.2116%
10s
MixMd-RF-MVMoE
10.736
1.381%
36
16.062
1.888%
9s
RF-TE
6.684
2,687%
18
10.121
4.055%
66
RF-TE
10.749
1.5022%
16
16.051
1.827%
Gs
Mixed-RI-TE
6.675
2.551%
10.111 28
3.946%
7s
Mixod-RE-TE
10.731
1.339
16.040 2s
1.751 %
7s
HGS-PyVRP
9.687
0.000%
10:4m
14,377
0.000%
20.8m
HGS-PyVRP
10,510
0.000%
10.4m
16.926
0.000%
20.8m
OR-Tools
9.802
1.159%
10.4m
14,933
3.853%
8m
OR-Tools
10.519
0,078%
10.4m
17.027
0.583%
20.8m
МTРOМO
10.033
3.564%
1s
15.082
4.922%
66
MIPOMO
10.668
1.479%
1s
17.420
2.8922%
7s
Mixeed-MPPMMO
10.035
3.5835%
2%
15,
5.045%
76
MTPOOO
10.676
1.555%
2s
17.419
2.889%
74
MVMeE
10.005
3.270%
28
15.023
4.508%
9%
MVMoE
10.669
1.492%
17.416 2x
2.872%
10s
VRPB
Mixed MVMoF
10,002
3.242%
2%
15.027
4.537%
10s
Mixed Mixed MVMoB
10.665
1.49%
17.393
2.738%
10s
RF-MoE
9.980
3.015%
28
14,973
4,16%%
8s
RF-MoE
10,674
1.539%
26
17.387
2.697%
10s
RR-MMR
9,980
3.012%
28
14.962
4.085%
98
Mixod-RF-MVMoE
10.660
1.403%
2s
17.369
2.592%
11s
RE-TE
9.977
2.989%
18
14,942
3.952%
68
RE-E
10.652
1.3261%
1s
17.327
2.346%
7s
Mixed RE
9.963
2.832%
25
14.929
3.863%
7%
Mixed-RF-TI RE
10.635
1.166 %
17.285 2s
2.100 %
76
HGP-PyVRP
10,186
0.000%
10.4m
14.779
0.000%
20 8m
HGS--yVRP
15,510
0.000S
10.4m
16.926
0.0000
20,8m
Tools
10.331
1.390%
10.4m
15.426
4.338%
20.8m
OR Tools
18.422
0.332
10.4m
29.830
2.770%
20.8m
MIPOMO
10.672
4.697%
1s
15.712
6.251
7s
MITOMO
18.990
2.128%
1s
30.898
3.624%
76
Mixed MTPOMO
10.666
4.644%%
2%
15.728
6.359%
8is
Mixed MTPOMO
19.015
2.258%
2s
30.897
3.616%
8s
VRPBL
MVMoR
10.637
4.354%
28
15.640
5.758%
9%
MVMoF
18.985
2.10
2s
30.892
3,608%
10s
Mixcd-MVMoE
10.640
4.394
28
15.647
5.816%
10s
Mixed-MVMoE
18.977
2,060%
2s
30.883
3,569%
1ls
RF-MoB
10.575
3.765%
2s
15,541
5.121
9%
RF-MoE
18.957
1.960'
2s
30.808
3.323%
10s
Mixed MVMME
10,568
3.702%
28
15.537
5,089%
10s
Mixed-RF MVM
18.939
1.873%
2s
30.773
3.202
11s
RE-TE
10.578
3,803%
Is
15.528
5.039%
6is
RE-TE
18.941
1.87%%
Is
30.688
2,923%
7s
Mixed-RF- RF-TE
10,553
3.555%
15.499 28
4.843%
7s
Mixed-RE-TE
18.89
1621%
2s
30.642
2.768% %
HGS-PyVRP VRP
18.292
0.000%
10.4m
29.467
0.000%
20.8m
HGS-PyVRP
16.356
0.000%
10.4m
25.757
0.000%
20 80.8m
OR-Tools
18.366
0.383%
10.4m
29.945
1.597%
20 8m
TR-Tssls
16.441
0.499%
10.4m
26.259
1.899%
20.8m
MTPOМO
18.639
1.878%
Is
30.437
3.285%
7s
MTPOMO
16.824
2.823%
Is
26.891
4.368%
7s
Mixed-MTPOMO
18.659
1.985%
2s
30.428
3.253%%
8s
Mixed-MTPOMO
16.816
2.779%
2s
26.882
4.330%
8s
VRPSTW
MVMeE
18.640
1.883%
28
30.436
3,28 5%
98
MVMoE
16,811
2.750%
2s
26.868
4,277%
9s
Mixed-MMMMlE
18.630
1.830%
28
30.422
3.232%
10s
Mixed-MVMol
16,804
2.703%
26.851
4.211%
10s
RF MoE
18.616
1.757%
24
30.341
2.954%
9%
MoE
16.777
2.550%
2s
76.
3.912%
9s
Mixed-RI-Me MV-MME
18.607
L.706%
28
30.306
2.839%
10s
16.762
2.453%
2s
26.746
3.802%
10s
RE-TE
18.600
1.676%
30,241
2.619%
7s
RE-TE
16.762
2.454%
Is
26.689
3.579%
7s
Mixed-RF-TE
18,555
1.417%
30.172 2s
2.385%
8s
Mixed-RF-TT
16.706
2.121
2s
26.633
3.377 %
8s
HGGS PYP
6,898
0.000%
10.4m
10.335
0.000%
20.8m
IIGS IIGS-Py VYP
6.899
0.000%
10.4m
10.335
01.000%
20.8m
OR-Tools
6.928
0.4125
10.4m
10.577
2.3155%
20.8m
OR-
6.927
0.386%
10.4m
10.582
2.3633%
20.8m
MTPOМM
7,108
3.005%
Is
10,878
5,224%
7s
MTPOMO
7.112
3.055%
Is
10.884
5.276%
6s
Mixed-MTPOMO
7.099
2,889%
2s
10.892
5.354%
8s
MiKod-MIPOMO
7,108
3.002%
28
10.899
5.419%
8s
OVRPP
MVMoE
7,089
2.741%
28
10.840
4.861%
9%
MVMoE
7,098
2.846%
2s
10.847
4,928%
9s
Mixcd-MVMoE
7,088
2.729%
28
10.835
4.809%
10s
Mixod-MVMoE
7,090
2.739%
2s
10.842
4.878%
10s
RI-Moli
7,080
2.513%
28
10.805
4.522%
9%
RE-MoE
7,083
2.635IE
28
10.805
4.534%
9s
Mixed RFRRRVMVV MVMoB
7.075
2.509%
26
10,791
4.188%
10s
Mixed RF MVMoE
7.076
2.539%
2s
10.796
4.428%
10s
RF-TE
7.071
2.479%
10.772
4.208
7s
RF-TE
7.074
2.508
1s
10.778
4.262%
74
Mixcd-RF-TE
7.053
2.216%
2s
10.745
3,939%
8s
MiXod-RF-TE
7.054
2.215%
10.749 25
3.979 %
8s
HRR
11,668
0.000%
10.4m
19.156
0.000%
20.8m
HGS-PyVRP
11.669
0.000%
10.4m
19.15
0.000%
20.8m
OR-Tools
11.681
0.1066
10.4m
19,305
0.767%
20.8m
OR-Tools
11.682
0.109%
10.4m
19.303
0.757%
20.8m
MIPOMO
11.817
1.260%
1s
19.637
2.496%
7s
MITOMO
11.814
1.229%
1s
19.635
2.485%
78
OVRPSLTW
11,823
1.312%
2s
19.634
2,476%
86
OVRPRTN W ONRRI MiX-d-RF-MVVME
Mixed-MTROMO
11.824
1.315%
2s
19.631
2.465%
8s
MVMoE
11.822
1.301
2s
19.641
2.518%
10s
MYMoE
11.819
1.271
2s
19.638
2.503%
10s
Mixed MVMOE
11.814
1.228%
28
19.621
2.412%
10s
Mixed-MV MYMEE
11.813
12166%
2s
19.624
2.424%
11s
M..
11,824
1.312%
24
19.607
2.334%
10s
RF
11.825
T.304
2s
19.606
2.328
10s
MFMM-E
11.813
1.225%
2s
19,584
2.2112%
11s
11.813
1.218%%
2s
19.583
2.209%
1ls
RF-TE
11,805
1.150%
1s
19.551
2.048%
7s
RE-TE
11.805
1.151%
1s
19.550
2.042%
7s
Bixed-RF-TE
11.780
0.949%
2%
19.503
1.793%
8s
Mixed-RE-TE
11.780
0.946 %
2s
19.501
1.73%%
Continued on the next page
34

---

A Mixed-Curvtture based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
n=50
I= 100
n=50
Type Model
Obj
Gap
Time
Obj
Gap
Time
Type
Model
Obj
Gap
Time
Obj
Gap
Time
HGS-PyVRP
6.507
0.000%
10.4m
9.724
0.000%
20.88 80.8
HGS-PyVRP
10.510
0.000%
10,4m
16.926
0.000%
20.8m
OR-Taols
6.552
0.668%
10.4m
10.001
2.791%%
20.8m 8m
OR Tools
10.497
0.114%
10.4m
17.023
0.728
20.8m
MTPOMO
6.719
3.227%
10.214
5.002%
66
МTРОМO
10.670
1.500%
Is
17.420
2.889%
76
Mixcd-MTPOMO
6.715
3,159%
28
10.234
5.214%
7s
Mixod-MTPOMO
10.678
1.571%
2s
17.418
2,882%
8s
OVRPL
28
OVRPLA
Mixed MVMoE
6.700
2.949%
2%
10.183
4.683%
10s
Mixed MVMoE
10.662
1.429%
2s
17.397
2.759%
11s
6.696
9%
17.386
Mixed-RF-Mi
MF-Moo
6,689
2.762%
28
10,136
4,202%
10s
Mixod-RF-MVMoE
10.661
1.419%
26
17.369
2.591%
1Is
RE-TE Mixed-RF-TE
6,686
2.721
1s
10.120
4.052%%
66
RE
10.653
1.341%
Is
17.327
2.347%
74
6.675
2.545%
2s
10.110
3.937%
7s
MiXed-RF-TE
10.636
1.176%
2s
17.287
2.108 %
8s
Table 18: Each model's performances 16 seen tasks following the setting of (Berto al., 2024). Each task is assigned with 1,000 instances for testing. The best performances are annotated with bold and domains improved by module are highlighted with underlines.
VRPLib
RF-POMO-MTL
RF-MVMoE
RF-TE
Mixed-RF-TE
Gap
Gap
Gap
Gap
A
2.529%
2.833%
2.825%
2.454%
B
2.752%
3.171%
2.583%
2.665%
E
5.069%
2.348%
2.929%
3.369%
12.772%
14.858%
12.951%
11.479%
M 5.907%
7.010%
5.078%
5.102%
P 4.678%
3.389%
4.573%
4.254%
X
9.143%
10.259%
8.435%
9,458%
Average Gap
6.121%
6.267%
5.627%
5,579%
Table 19. Zero-Shot Inference on CVRP benchmark instances from Set-X (Uchoa et al., 2017).
Method
VRPMB
OVRPMR
VRPMRI
VRPMRTW
OVRPMBI
OVRРMЕТW
VRPMBLTW
OVRPMBLTW
Cost
Gap
Cost
Gap
Cost
Gap
Cast
Gap
Cost
Gap
Cost
Cap
HGS-PPVRR
13.54
0.00%
9.01
0.00%
13.78
0.00%
25.51
0.00%
9.01
0.90%
16.97
0.00%
25.85
0.00%
16.97
0.00%
OR-Tools
14,93
10.27%
10.59
17.54%
13.78%
17.76%
19.31
Zero-shot
14.88
10.13%
10.72
19.02%
15.18
10.32%
28.29
10.89%
10.72
19.01%
18.45
8.68%
28. 65
10.82%
18:45
8.69%
Mixed-ZZeo-Sloot
16.04
16.61
Train (scratch)
15.12
12.13%
10.40
15.35%
16.32
18.27%
28.15
10.71%
10.18
16.08%
18.36
11.19%
28. 69
10.95%
18.86
11.19%
(scratch)
7.96%
9.61
3.39%
EAL (step D)
14.88
10.13%
10.72
19.02%
15.
10.32%
28.29
10.89%
10.72
19.01'%
18.45
8.68%
28.65
10.82%
18:45
8.69%
Mixed- EAL (step 0)
31.20%
EAL
14.59
7.89%
9.66
7.19%
14.78
7.39%
26.69
4.61%
9.65
7.13%
17.59
3.65%
27.13
4.90%
17.59
3.65%
Mixed-EAL
9.37
17.46
3.99%
Table 20. Performance comparisons under few-shot scenario on 8 unseen tasks. EAL here denotes the Efficient Adapter Layer proposed (Berto et al., 2024). pads zeros on original weight matrix, which can infuse unseen features into model. Following (Berto al., 2024), each model is trained on the size N 100 and each task is assigned with 1,000 test instances for validations. During few-shot learning, model is trained with 10 epochs and each epoch contains 10,000 instances. The best performances are annotated with bold and domains improved by module are highlighted with underlines.
35

---

A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver
(N-Vature(N=50)
Curvature(N=100)
0.8
Embedder
-0.03
-0.14
-0.29
.0.16
-0.33
-0.21
-0.23
-0.24
Embedder
-0.16
-0.15
-0.25
-0.06
-0.12
-0.07
-0.15
-0.29
0.6
Layer 2 2-0006
-0.05
-0.03
-0.09
-0.11
-0.03
-0.05
-0.03
Layer 2 2-00.7
-0.01
-0.04
0.03
-0.08
-0.00
-0.00
-0.10
0.6
Layer
Layer
-0.00
Layer
0.05
0.39
0.06
-0.04
-0.12
0.54
-0.05
0.06
0.21
-0.00
0.22
0.22
0.23
0.00
0.19
0.13
0.2
Layer 5
0.48
0.42
0.55
0.58
-0.01
0.68
0.46
0.51
Layer 5
0.43
0.49
0.63
0.67
0.34
0.07
0.42
0.36
0.0
Layer
-0.23
-0.09
Layer
0.40
.0.16
-0.2
Layer
Layer
0.68
-0.2
Subspace Index
Subspace Index
Figure 9. Visualization of curvature for each subspace of each layer in the encoder module. Shown model is Mixed-RF-MVMM The shown colors indicate that subspaces shallower layers tend to reside in hyperbolic space. As the layer index increases, more subspaces shift closer spherical geometry. Similar to the results presented in Figure 8, the MVMoE based model keeps the consistency in the evolution of curvatures across layers. Better viewed in color.
Curvature(N=50)
(N=100)
Embedder - .0.02
0.06 -0.09 0.03
.0.05
.0.04
-0.02
0.04
0.5
Embetider- -0.01
0.05
.0.07
.0.09
-0.10
-0.03
-0.03
0.03
Layer 2 .0000
0.01
00.11
0.01
-0.00
4.00
-0.01
0.00
0.4
Layer 2
-0.01
0.01
.0.01
.0.01
-0.01
.0.01
.0.01
0.01
-..
Layer
0.3
Layer
Layer Layer Index
0.2
-0.02
-0.02
0.35
-0.01
-0.00
-0.00
0.10
00.01
Layer
-0.00
-0.01
-0.00
-0.01
-0.01
-0.00
-0.00
40.00
Layer 5
0.53
00.02
-0.03
-0.01
-0.02
0.39
0.13
-0.02
Layer 5
0.04
-0.02
0.24
.0.02
-0.02
-0.04
-0.01
0.02
0.1
0.11
Layer
0.29
-0.00
0.27
0.35
0.31
0.29
0.32
0.43
Layer
0.40
0.07
-0.02
0.30
0.30
0.47
0.03
0.35
0.0
0.0
0.35
0.42
Layer
0.24
-0.07
0.33
0.21
0.34
-00.1
Subspace Index
Subspace Index
Figure 10. Visualization of curvature for each subspace of each layer the encoder module. Shown model is Mixed-RF-TE The shown colors indicate that subspaces in shallower layers tend to reside in hyperbolic space. As the layer index increases, more subspaces shift closer to spherical geometry. Compared to the MVMoE based models in Figure 8, -ixxed-RF-TE docsn't acquire very positive negative curvatures, they mostly cluster around the zero point. Better viewed in color.
36


Reviews:
[{"review_id": "psaRgQKGmN", "reviewer": "Reviewer_dd5d", "summary": "This paper presents a pre-training framework for multi-task vehicle routing solver. The main difference between this framework with existing literatures is the integration of the geometric structures. Specifically, this framework utilizes the curvature of the routes and encodes the geometric features in mixed-curvature spaces to thoroughly learn and leverage the data representations of the problem.  Experiments are conducted by comparing with previous works which didn't account for the geometric information of the input. Results demonstrate the effectiveness of the proposed paradigm.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer dd5d for the valuable comments and suggestions. We provide the point-to-point responses below to address the concerns.\n#### **[Figures to show curvatures of inputs]** Figure 1 visualizes the curvature information on 6 training tasks. We use 1,000 VRP instances (size 50) to record the frequency of node curvatures via Ollivier-Ricci curvature[1] (briefly introduced in Appendix.1). Histograms in Figure 1 show that each task consists of nodes with either positive or negative curvatures with a tendancy towards negative curvature. Similar conclusions also hold for another 10 OOD tasks and we report their histograms in Figure 4 (Appendix.1). These all validate our motivation in introducing mixed-curvature space into pre-training stage.\n#### **[Clarification for operations in Figure 2]** Each curvature subspace needs exponential mapping $Exp(\\cdot)$ and logarithmic mapping $Log(\\cdot)$ for feature transformation. The subspace $C$ also needs $Log(\\cdot)$ but it was omitted for brevity. We have created a complete one **[here](https://anonymous.4open.science/r/VD-5D0E/README.md)** and will update it in final version.\n#### **[Mixed-curvature VS non-Euclidean space]** The Euclidean space is flat and has zero curvature. Conversely, non-Euclidean space acquires non-zero valued curvature. The mixed-curvature space consists of multiple subspaces with possible different curvatures. In our case, the original 128-dimension feature space is split into 8 subspaces (16 dimensions) and each is assigned with a learnable curvature.\n#### **[How do subspaces look like]** In Appendix.3, we visualize curvature information of subspaces in embedder and encoder layer under different settings. For POMO-MTL based architectures, we visualize both scales (n=50, 100) in Figure 5 and Figure 6 (Appendix.3), respectively. Similarly, we show results for MVMOE-Light and MVMOE in Figure 7,8 (Appendix.3) and Figure 9,10 (Appendix.3), respectively. From the results, one can observe a common phenomena: the shallow layers favor low-curvature/hyperbolic space while deeper layers favor high-curvature/spherical space, illustrating how features evolve through layers.\n#### **[Computation efficiency]**  We provide running time of baselines and models with mixed-curvature modules **[here](https://anonymous.4open.science/r/15699-8B57/README.md)**. As we can see, time increase is moderate and it doesn't cause significant burdens. Moreover, the recent work[2] can avoid mapping operations by fully exploitting geometric properties of certain manifolds, and we can explore it to further reduce the computation in future.\n#### **[More details for methodology]** We acknowledge the concern regarding the imbalance between the Preliminary and Methodology section. We agree that the methodology section requires greater detail and clarity. In the final version, we will add following details and make it more informative:\n#### **1.How to process inputs** \nFollowing the prior works[3], we first project raw inputs into high-dimensional Euclidean space and then transform them into mixed-curvature space via $Exp^{\\kappa}(\\cdot)$.\n#### **2.How curvatures affect Exp($\\cdot$) and Log($\\cdot$)**\nThe curvature is vital for $Exp(\\cdot)$ and $Log(\\cdot)$. Given a curvature $\\kappa$:\n#### **2.1 Hyperbolic Model ($\\kappa < 0$)**\n- ##### **Exponential Map**:\n  $\\exp_p(v) = p \\oplus_{\\kappa} \\left(\\tanh\\left(\\sqrt{-\\kappa} \\frac{\\lambda_p \\|v\\|}{2} \\right) \\frac{v}{\\|v\\|} \\right),\\quad p\\in \\mathcal{M}, v \\in T_{v}\\mathcal{M}$\n- ##### **Logarithmic Map**:\n  $\\log_p(q) = \\frac{2}{\\lambda_p \\sqrt{-\\kappa}} \\tanh^{-1}(\\sqrt{-\\kappa} \\|p \\oplus_{\\kappa} (-q)\\|) \\frac{p \\oplus_{\\kappa} (-q)}{\\|p \\oplus_{\\kappa} (-q)\\|},\\quad p,q \\in \\mathcal{M}$\n\nwhere $p$ is point on manifold $\\mathcal{M}$, $v$ denotes point on tangent space $T_{v}\\mathcal{M}$ and $q$ denotes a point on $\\mathcal{M}$. $\\lambda_p$ here is the hyperbolic metric: $\\frac{2}{1 - \\kappa \\|p\\|^2}$.\n#### **2.2 Spherical Model ($\\kappa > 0$)**\n- ##### **Exponential Map**:\n  $\\exp_p(v) = \\cos(\\sqrt{\\kappa} \\|v\\|) p + \\sin(\\sqrt{\\kappa} \\|v\\|) \\frac{v}{\\|v\\|}$\n- ##### **Logarithmic Map**:\n  $\\log_p(q) = d_{\\mathbb{\\kappa}}(p, q) \\frac{q - \\cos(d_{\\mathbb{\\kappa}}(p, q)) p}{\\|q - \\cos(d_{\\mathbb{\\kappa}}(p, q)) p\\|},\\quad d_{\\mathbb{\\kappa}}(p,q)=\\frac{1}{\\sqrt{\\kappa}} \\cos^{-1}(\\kappa \\cdot \\langle p, q \\rangle)$\n#### **2.3 Effects of $\\kappa$** \nFor hyperbolics, if $|\\kappa|$ increases, the metric $\\lambda_p$ will decrease thus distance between two points will become larger and points on the manifold acquire stronger tendancy to spread out. For sphericals, enlarging $|\\kappa|$ will lead to shrinkage on the distance, which means points on sphere become closer together.\n\n[1]Ricci curvature of markov chains on metric spaces. JFA, 2009.\n\n[2]Hypformer: Exploring efficient transformer fully in hyperbolic space. KDD, 2024.\n\n[3]Hyperbolic vision transformers: Combining improvements in metric learning. CVPR, 2022.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "For the effectiveness, it's okay. However, the authors skip the computation efficiency, which is also an important evaluation criteria to mention.", "theoretical_claims": "yes", "experimental_designs_or_analyses": "Yes. Massive experiments and benchmark comparisons are conducted to validate the effectiveness of the proposed framework.", "relation_to_broader_scientific_literature": "The key contributions lie in the introduction of the curvature analysis from differential geometry and so on. The curvature analysis accurately capture the geometrical features of the problem input.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths: This paper is clearly written, and the introduction of the curvature analysis is significant since it captures the geometrical features overlooked by previous works. The features in this paper are more reasonable both intuitively and theoretically, reflecting that the authors are skillful in geometry analysis. Besides, the linear transformation of the mixed-space transformation, which perfectly suits the structure of the neural network. The experiment results demonstrate the effectiveness of the proposed framework.\n\nWeakness: As the authors mentioned, the proposed framework struggles in computation efficiency. Besides, the authors spend too much attention on the Preliminaries but section Methodology lacks more details, making this part a little confusing.", "other_comments_or_suggestions": "The geometrical analysis is an important part and foundation of this paper. It analyses the curvature of the input information. It would be better if there are figures to illustrate the original input and corresponding curvature, as well as the linear transformation process.", "questions_for_authors": "The first question, at Figure 2, the features of subspace 1,2,3 will pass through a Log() transformation, but it seems that subspace C don't, why?\nThe second question, two key statements are frequently mentioned all across the paper: mixed-curvature space and (non-)Euclidean space. Can I understand like this: mixed-curvature space is the concatenation of Subspace C; non-Euclidean space is when curvature \\kappa is not equal to zero? What's the relationship between curvature calculation and space transformation Exp() and Log()? Should Input Instance pass through an Exp() first to become Subspace C? Given Input Instance, what does Subspace 1,2,3 look like?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ag8qbRY4ep", "reviewer": "Reviewer_qtXz", "summary": "This article considers modeling the VRP tasks in multi-task NCO in Riemannian space instead of the original Euclidean one. This article modifies the embedding layer based on this idea, and the experiment demonstrated the effectiveness of the proposed method.\n\n## update after rebuttal\n\nI think the topic of this article is interesting and super novel, and I have no problem with the possible admission decision. However, since the experiment added by the author does not fully demonstrate the significant effect of non-Euclidean transformation, I am not motivated enough to improve my score.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincere gratitude to the reviewer qtXz for detailed and valuable suggestions and comments.\n#### **[Dimension of $X$]** Since graph is discrete, Ollivier-Ricci metric is used for measuring curvature based on edges weights, which doesn't require dimensions of inputs. This is different from curvature on 3-dimension smooth manifolds. Our $X$ only consists of two dimensions (coordinates) for calculating curvatures. Since some nodes don't have features like time-windows and backhauls, these features will separately appear in encoder.  We will make this clear in the final version.\n#### **[Instance augmentation method]** We follow POMO-MTL[1] and MVMOE[2], applying greedy rollout with 8× instance augmentation for fair comparisons, where best solutions for each instance are obtained by solving multiple (8×) equivalent instances. Those equivalent instances are acquired by rotating or clipping the original instances[7]. We will clarify this in the final version.\n#### **[Vector diagram]** We have created a new vector diagram (**[here](https://anonymous.4open.science/r/VD-5D0E/README.md)**) that will replace the original Figure 2 in the final version.\n#### **[Clarification for motivations]** Following [1,2], settings of VRPs are based on Euclidean space. However, the underlining data structures are graphs and they produce certain kinds of complex structures (e.g., node clustering, scattering) which can be approximated by tree-like or cycle-like patterns[4,5,6]. As pointed out in[4,6], to capture these nuances and variations from datas, Riemannian manifolds provide us with a more flexible and effective framework. Though graph is discrete, which is usually different from Riemannian manifolds that are smooth and continuous, we can use some discrete analogs (e.g., the Ollivier-Ricci curvature used for visualizations in Figure 1) to get some senses.\n#### Recall definitions in Equation 15,16 (Appendix.1), the node curvature is calculated based on edge weights of neighbour nodes. So, given a graph $G$ and two nodes $u$ and $v$, the positive Ollivier-Ricci curvature $\\kappa(u,v)$ indicates that $u$ and $v$ share many common points in their neighbours. In other words, if random walks $A$ and $B$ start from $u$ and $v$ respectively, then $A$ and $B$ are more likely to meet with each other in a few steps.  In this case, paths on $G$ tend to collapse together. Similarly, the negative curvature indicates that paths on $G$ tend to diverge and spread out. Such kinds of behaviours are quite similar to those of geodesics on Riemannian manifolds where initially parallel geodesics will converge and diverge on Spherical and Hyperbolic Spaces, respectively. From these, Ollivier-Ricci curvature can be treated as a discrete analogy of curvature on continuous domain and its outputs strongly reflect the existence of non-uniform structures in datas, which motivates us to leverage Riemannian manifold spaces for creating a feature space that preserves the underlying node distances and relative positions more faithfully.\n#### From Table 3 (Appendix.3), the calculated distortion rates (defined in Equation 9) of different models show that Riemannian manifolds have done a better job of preserving original distances among nodes in feature space compared with other baselines, which is more desirable since neural solvers for VRPs heavily rely on the quality of produced hidden features to select next node. \n#### To summarize, graphs used in VRPs often contain intricate relations that can't directly be viewed as flat structures. Though graph is discrete, we can utilize neural networks to firstly embed graph into continuous embeddings and apply curved manifolds to fit the underlining geometric structures, which can let model enjoy much stronger abilities to detect and capture fine-grained information from the inputs.\n#### **[How to set $D$ and $C$ in indivisible case]** In our case, $D=128$ and $C=8$ so each subspace has 16 dimensions. When $D$ is not divisible by $C$, we need to manually design the dimension of each subspace. For instance, when $D=127$ and $C=8$, the first 7 subspaces can have 16 dimensions and last one has 15 dimensions (other choices are also allowed as long as the summation of subspaces' dimensions is equal to $D$). We follow POMO-MTL[1] and MVMOE[2] where $D$ is always divisible by $C$. But this can be explored in future (e.g., using neural architecture search[3] to decide dimensions of subspaces).\n\n[1]Multi-task learning for routing problem with cross-problem zero-shot generalization. KDD, 2024.\n\n[2]Mvmoe: Multi-task vehicle routing solver with mixture-of-experts. ICML, 2024.\n\n[3]Neural architecture search: A survey. JMLR, 2019.\n\n[4]Learning mixed-curvature representations in product spaces. ICLR, 2018.\n\n[5]Hyperbolic graph neural networks. NIPS, 2019.\n\n[6]Constant curvature graph convolutional networks. ICML, 2020.\n\n[7]Pomo: Policy optimization with multiple optima for reinforcement learning. NIPS, 2020.", "claims_and_evidence": "To my understanding, discussing the relation curvature shown in Figure 1 with the Euclidean space should have at least three dimensions of $ xin X$. Unfortunately, based on the current version of this article, I am not sure whether the $X$ space represents coordinates (2-dimensional) or coordinates with node features (such as time window or capacity). I suspect your intention should be the latter. I suggest you pay attention to this point and add clear illustrations and definitions.", "methods_and_evaluation_criteria": "I am not familiar with the basic definitions of Riemann manifold and tank space, and I am curious about the specific formulas for the $Exp$ operator and the $Log$ operator in this work.", "theoretical_claims": "This paper does not contain theoretical claims.", "experimental_designs_or_analyses": "What do you mean about ``we use an instance augmentation method for solution decoding.`` 8-augmentation or something else. Please state clearly.", "relation_to_broader_scientific_literature": "I think it is valuable to discuss the distribution of the entire node feature (including constraints and coordinates) for multi-task NCO, and this article first discusses this part.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "**Strength:**\n1. The general representation of multi-task NCO features can be improved, and this paper notices such drawback.\n\n\n**Weakness:**\n\n1. Based on my background, I have limited knowledge of Riemannian space so I am confused about the analysis presented in this article. Based on the current version, I cannot intuitively understand the necessity of mapping features to Riemannian space. Figure 1 attempts to demonstrate the necessity, but this is only a statistical value. In my opinion, it can only indicate that these points are relatively clustered or scattered, and have no strong relationship with whether they belong to the Riemann space or not. Furthermore, the author did not provide any intuitive explanation. After using the method proposed in this article, why does the embedding method proposed in this article achieve better results?\n\nI am looking forward to the author's complete explanation of these motivational doubts.", "other_comments_or_suggestions": "Figure 2 is not a vector diagram, please replace it with a vector diagram.", "questions_for_authors": "1. Can you please provide me with an intuitive reason why the embedding method proposed in this article can achieve better results?\n\n2. What is the detailed rule for subspace partition when D cannot be divided by C?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kcPgGuEK0M", "reviewer": "Reviewer_gmJz", "summary": "In the context of neural solvers for vehicle routing problems (VRP), the paper introduces a methodology to learn embeddings in non-Euclidean space, where the embedding space is divided into several subspaces with adaptively learned curvatures.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer gmJz's insightful questions and constructive feedbacks.\n#### **[Acronyms]** Thank you for the suggestion. We will ensure all acronyms are properly defined upon first use and provide a reference table in the final version. For example, \"VRPs\" stands for Vehicle Routing Problems, \"LKH\" for Lin-Kernighan-Helsgaun and \"HGS\" for Hybrid Genetic Search, etc.\n#### **[Typos]** We appreciate the attention to typos. We identified and will correct errors such as \"manioflds\" (line 123), \"hypersphereical\" (line 124), \"$n$ nodes\" (line 185). The cardinal of $V$ on page 4 is indeed $n+1$ and we will correct it. Besides, in Table 6 (Appendix.3), we notice that for the row indexed by \"R102\", two columns are mis-highlighted at same time. We have checked all tables and will make sure all bold values are correctly used. \n#### **[Comments on curvature figure]** In Figure 4 (Appendix.1), we show node curvatures on 10 OOD tasks. It shows that almost every node in the dataset has either negative or positive curvature and the average curvature suggests that each task  contains geometry patterns. For Figure 5-10 (Appendix.3), we provided corresponding comments in \"curvature analysis\" part (Appendix.1), where shallow layers and deeper layers present different curvatures. We will move this analysis directly into these figure captions in the final version.\n#### **[Why is transition non-smooth]** The transition between different curvature spaces is non-smooth primarily due to the incompatibility of geometric structures among different subspaces. In specifics, hyperbolic and spherical spaces have fundamentally different distance metrics. In details, the geodesic distance in hyperbolic space grows exponentially when $|\\kappa|$ ($\\kappa$ here denotes negative curvature of hyperbolic space) increases. While on the other hand, the distance in spherical space is bounded. This discrepancy may introduce unexpected disturbance in feature transformation. In Figure 5-10 (Appendix.3), we visualize the curvature information of different subspaces layer by layer. From the results in these figures, the shallow layers tend to process features in hyperbolic spaces while deeper layers choose to process features via spherical spaces. The transitions between hyperbolic space and spherical space usualy happen around layer 2 and layer 3. The inferior features caused by non-smooth transition will severly affect deeper layers' learning ability. To mitigate this, we apply techniques similar to Mix-Up[1] where previous layer's features was infused into deeper layers. This can guide deeper layers gradually move into new curvature spaces.\n\n#### **[Settings of hyperparameters]** Table 5 (Appendix.2) lists our detailed settings of hyperparameters and we strictly follow prior works[2,3]: 5,000 training epochs, batch size of 128, and 20,000 instances per epoch from 6 VRPs. Fine-tuning uses 10,000 instances per epoch for 10 epochs with the same batch size. We employ Adam optimizer with learning rate 1e-4, decayed by 10 after 4,500 epochs. Feature space (128 dimensions) is split into 8 subspaces of 16 dimensions, initialized at 0. Number of attention heads and encoder layers are 8 and 6, respectively.\n\n#### **[Number of parameters in our method]** For embedder, we insert two mixed-curvature  modules for depot and customer node, respectively. For each layer of encoder, we insert one mixed-curvature module for processing feautres from previous layer. The comparisons between baselines and mixed-curvature versions are listed as follows:\n| **Models** | **Number of parameters** |\n|---------------------------------------------|-------------------------------------|\n| POMO-MTL | 1,254,656 |\n| Mixed-POMO-MTL | 1,386,810 |\n| MVMOE-Light | 3,698,944  |\n| Mixed-MVMOE-Light | 3,831,116 |\n| MVMOE | 3,682,176 |\n| Mixed-MVMOE | 3,814,348|\n#### From table, compared with original backbones, the number of parameters is inreased by 3.57\\%~10.56\\%. We will emphasize these changes in the final version.\n\n#### **[Computational cost]** To compare the computational cost with baseline models like POMO-MTL and MVMOE, we list the running time **[here](https://anonymous.4open.science/r/15699-8B57/README.md)**. From results in the table, running time of our model increases a little bit compared to backbones. Taking (n=100) as example, Mixed-POMO-MTL, Mixed-MVMOE-L and Mixed-MVMOE introduce 10.72\\%, 7.68\\%, 7.56\\% costs to backbones, respectively. These show that mixed-curvature modules bring moderate costs, which would not cause serious inference burden.\n#### **[Ablation]** We conduct ablation studies on MVMOE and results are shown **[here](https://anonymous.4open.science/r/15699-8B57/README.md)**. We can see that Mix-Up can improve performances.\n\n[1]Pomo: Policy optimization with multiple optima for reinforcement learning. NIPS, 2020.\n\n[2]Mvmoe: Multi-task vehicle routing solver with mixture-of-experts. ICML, 2024.\n\n[3]mixup: Beyond empirical risk minimization. ICLR, 2018.", "claims_and_evidence": "The authors claim that their proposition can be integrated in various existing solvers and improve their performance. This claim is empirically demonstrated with three backbone methods (i.e., POMO-MTL, MVMoE, RouteFinder) on various problems (e.g., random and real instances) in different settings (e.g., in-distribution, zero-shot, few-shot test). \n\nI would have appreciated an ablation study (e.g., for mix-up technique) and/or sensitivity analysis (e.g., number of subspaces) for the proposed method to have a stronger confidence in the results.", "methods_and_evaluation_criteria": "The proposed method defines a more expressive neural architecture where embeddings are divided in several subspaces with different curvatures. The architecture seems natural, although the need of the mix-up technique (equation 13) seems a bit strange to me, since it amounts to do a linear combination of two embeddings in two different spaces. The use of this technique is only justified empirically (i.e., it leads to better performance). The explanation in the first sentence of page 5, col. 2 is not very convincing to me. Why is the transition non-smooth?", "theoretical_claims": "There is no theoretical claim in this paper.", "experimental_designs_or_analyses": "The empirical validation uses standard evaluation criteria (e.g., gap) and is conducted according to different previously-proposed protocols. The analysis followed by the authors is standard when evaluating neural solvers. It would have been nice to report computational times and the sizes of the models.", "relation_to_broader_scientific_literature": "The paper summarizes recent research in solving VRP and in deep learning in non-Euclidean space. The work in this paper is at the intersection of those areas. As far as I know, the relevant work seems to be discussed.", "essential_references_not_discussed": "I'm not aware of a missing reference.", "other_strengths_and_weaknesses": "The idea of learning embeddings in non-Euclidean spaces with different curvatures for solving VRP is novel. It seems that it may introduce more parameters and the computation time increases. This discussion is missing in the current paper.", "other_comments_or_suggestions": "The paper should be proofread, e.g., \n- the meaning of acronyms should ideally be recalled.\n- there are many typos in page 3.\n- in page 4, the cardinal of V is actually n+1.\n- the bold values seem to be off in Table 6 in the appendix.\n- It would be nice if there were some comments on the figures showing the curvatures in the appendix.", "questions_for_authors": "1. Why is the transition between different curvature spaces non-smooth?\n2. How did you choose the hyperparameters specific to your proposed method?\n3. How does the number of parameters changes when using your proposed architecture compared to a backbone architecture?\n4. What is the additional computational cost required by your proposed method?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes a mixed-curvature based pre-training paradigm for multi-task vehicle routing solver. The pretraining framework is able to fully leverage the rich gemmetric information embedded within the tasks. Overall the paper is well motivated, written well and the experiments are sufficient to claim the contribution.

The major concerns raised by reviewers are:

- Computational efficiency
- Technical details / implementation details.
- How to verify the significance of the non-Euclidean transformation.
- Clarification of the motivation on the pipeline. Why tranform to Riemannian space.

During rebuttal, authors did a fair good job to address most of the concerns. The final rating is 2x weak accept and 1x weak reject. The negative reviewer admits the technical contribution of the paper while still has concerns on technical design. Authors provide more results and explanation. Overall the paper has good merits and could potentially draw interest from the community. Please revise accordingly and incorporate all results in the revised version.
Decision: Accept (poster)