Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning
Authors: Yuanyao Chen
Rongsheng Chen
Fu Luo
Zhenkun Wang
Venue: NeurIPS 2025 poster ()
Keywords: Neural Combinatorial Optimiztion
Large Language Model
Vehicle Routing Problem
Primary area: optimization

Abstract: Neural Combinatorial Optimization (NCO) has emerged as a promising learning-based paradigm for addressing Vehicle Routing Problems (VRPs) by minimizing the need for extensive manual engineering. While existing NCO methods, trained on small-scale instances (e.g., 100 nodes), have demonstrated considerable success on problems of similar scale, their performance significantly degrades when applied to large-scale scenarios. This degradation arises from the distributional shift between training and testing data, rendering policies learned on small instances ineffective for larger problems. To overcome this limitation, we introduce a novel learning framework driven by Large Language Models (LLMs). This framework learns a projection between the training and testing distributions, which is then deployed to enhance the scalability of the NCO model. Notably, unlike prevailing techniques that necessitate joint training with the neural network, our approach operates exclusively during the inference phase, obviating the need for model retraining. Extensive experiments demonstrate that our method enables a backbone model (trained on 100-node instances) to achieve superior performance on large-scale Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) of up to 100K nodes from diverse distributions. The source code can be found in https://github.com/CIAM-Group/TTPL.

Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning
Yuanyao Ch Rongsheng Chen Fu Luo Zhenkun Wangl.2|
1 School of Automation and Intelligent Manufacturing.
Southern University of Science and Technology, Shenzhen, China, 2 Guangdong Provincial Key Laboratory of Fully Actuated System Control Theory and Technology, Southern University of Science and Technology, Shenzhen, China, 3 Peng Cheng Laboratory, Shenzhen, China, sustemtccssssssshseaaamaammm
12433020 sustech, edu. en, chenrs com, 1uof2023@mail. sustech. edu en, wangzhenkknnO@@maii.cc com
Abstract
Neural Combinatorial Optimization (NCO) has emerged as a promising learning- based paradigm for addressing Vehicle Routing Problems (VRPs) by minimizing the need for extensive manual engineering. While existing NCO methods, trained small-scale instances (e.g., 100 nodes), have demonstrated considerable success on problems of similar scale, their performance significantly degrades when ap- plied large-scale scenarios. This degradation arises from the distributional shift between training and testing data, rendering policies Iearned on small instances ineffective for larger problems. To overcome this limitation, we introduce novel learning framework driven by Large Language Models (LLMs). This framework learns projection between the training and testing distributions, which is then deployed to enhance the scalability of the NCO model. Notably, unlike prevailing techniques that necessitate joint training with the neural network, our approach operates exclusively during the inference phase, obviating the need for model retraining. Extensive experiments demonstrate that our method enables back- bone model (trained on 100-node instances) to achieve superior performance on large-scale Traveling Salesman Problems (TSPs) and Capacitated Vehicle Routing Problems (CVRPs) with up 100K nodes from diverse distributions. The source code can found https://gthbbbcom////lMM.Gooo/
Introduction
The vehicle routing problem (VRP) is prevalent in critical domains such as transportation [. logistics (2), and supply chain management 3 However, due to the NP-hard nature, solving VRP can be complex and time-consuming 4 While traditional exact and heuristic methods can yield optimal near-optimal solutions, their high computational cost and dependence domain expertise consequently diminish their feasibility for real-world deployment.
In recent years, neural combinatorial optimization (NCO) has emerged as promising approach for solving VRP (5). It utilizes neural networks learn problem-solvvngg strategies directly from the VRP instances, minimizing the need for algorithms designed by experts. Once trained, these neural networks can efficiently generate solutions for new instances at low computational cost. Therefore.
"Equal contributors
I Corresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

NCO methods demonstrate potential advantages in tackling limitations of traditional methods and exhibit promising performance solving scall-scale VRPs 9
However, due to the different distributions between small and large-scale instances, the effectiveness of existing approaches degrades substantially when it comes to large-scale problems (e-g., problems with more than IK nodes), thereby severely limiting their practical capability. To address the scalability issue, some attempts have been devoted to training NCO models on larger VRP instances (i.e., instances with 500 nodes) [T) M. However, the existing supervised learning (SL) and reinforcement learning (RL) both show their shortcomings when training on large-scale VRP instances. rewards.
SL lacks sufficient labels (e.g., high-quality solutions) while RL suffers from extremely sparse
Consequently, current methods focus on training a model on small-scale instances and generalizing to large-scale scenarios via decomposition or local policy 12] The decomposition-basee method first simplifies large-scale problems to a series of subproblems. Subsequently, a solver trained on the small-scale instances can be utilized construct a partial solution of the subproblems [16 However, the scope of the decomposition often requires manual tuning, and even decomposing the problem could change its property, and thus damage the optimality of the solving algorithm. Another effort is local policy-based methods [5]. It first reduces the search space to a small candidate subgraph at each construction step, typically based on the Euclidean distance the last visited node. The next node is decided by the original policy or a local policy.
However, the distribution of selected subgraphs often differs from training instances, which signifi- cantly impairs the model's scalability. Current methods employ a projection technique to effectively transform these varied input distributions into uniform distribution encountered during training
[15 [9] Nevertheless, existing strategies require integration with the model training to ensure ef- fectiveness during testing. Meanwhile, these manually designed strategies heavily rely on specialized domain expertise, thereby limiting their adaptability.
To address this challenge, propose novel learning framework called Test- Time Projection Learning (TTPL), driven by the Large Language Model (LLM), to design an efficient projection strategy. In particular, and training instances, thereby developing projection strategies that enhance model generalization. Different from existing works, our approach can be directly applied in the inference phase, does not need to train a model from scratch. Moreover, we propose a Multi- View Decision Fusion (MVDF) module to improve model generalization. Specifically, we perform data augmentation on the subgraph to generate multiple views. These views are subsequently processed by the model, with each view yielding a distinct node selection probability. Finally, these probabilities are aggregated, and the node with the highest resulting confidence score is selected.
utilize the LLM to learn the correlation between the input subgraph
Comprehensive experiments are conducted on both synthetic and real-world benchmarks for the TSP and CVRP. The results demonstrate that our proposed distribution adapter enables the base model, pre-trained on small-scale instances (e.g., 100 nodes), to achieve superior performance the majority of large-scale VRP test instances without requiring additional fine-tuning. Our ablation study validates the effectiveness of the designed projection strategy.
2 Related Work
Existing NCO methods can be categorized into constructive 25 and non-constructive 26 29 This paper mainly focuses on the constructive method; a detailed review of the non-constructive method and other LLM-based methods can be found in the Appendix.
2.1 Direct Generalization
This kind of method often trains neural networks on small-scale instances and generalizes them to large-scall instances. It is mostly known as the construction-based methods that predict an approximate solution in an autoregressive manner. Early studies demonstrate that neural models trained with SL or RL can reach promising performance on small-scale instances [2 Moreover, 34 to design powerful attention-based models to
6 33 propose to use the Transformer architecture solve VRPs. Subsequently, various Transformer based approaches have been developed with different strengths [35|4]] Meanwhile, many studies focus on improving model performance on large-scale

---

VRPs 42
In which 42 and [8] train the model with SL on 100-node and exhibit generalization modifies the Markov Decision Process (MDP) to efficiently leverage the symmetries of combinatorial optimization problems (COPs). LEHD [8] develops a light encoder and heavy decoder structure to reach the same result. Nevertheless, the training distribution of 100-node instances drastically differs from the large-scale instances; the trained model usually performs poorly when tested on this large-scale scenario. Consequently, several attempts have trained models on larger-scale instances with up 500 nodes [13 38 [0) or even directly training on the large-scale 44] (up to noOKsn However, these approaches introduce prohibitive computational costs due to the exponentially growing search space.
ability IK nodes. Specifically, BQ 22
2.2 Decompasition Based Generalization
Apart from directly generalizing the model trained on a small-scale dataset the large-scale instances, another line of research focuses on decomposing the large node graph into several small-scale subproblems. This approach involves solving them separately with a particular solver and then combining their solutions to form the solution of the large-scale problem [45] [12 [3] 48). In particular, the problem decomposition and subproblem solving are often involved in different models.
The task of the subproblem solver can be constructing a complete solution of small-scale VRP or partial solutions of large-scale instances [16]18]. However, such decomposition introduces two critical shortcomings. When solving other complicated VRPs (e.g.. CVRP), such decomposition becomes intractable and cannot be achieved by an individual strategy or model. Furthermore, when the decomposed subproblem is not small enough, it may still require other generalization techniques to solve.
2.3 Local Policy-Based Generalization
Another approach to solving large-scale VRPs is to reduce the search space to the K K-Nearest- Neighbors (KNN) from the last visited node. The final decision is guided by either the original neural model with auxiliary distance information [49] or local policy [14]. In addition, [15 50 42
directly select the candidate node from the neighborhood using NCO models. Although local policy can efficiently reduce the search space for constructive NCO, the reduced subgraph often drastically differs from the training instances, especially in large-scale or non-uniform instances. Consequently, the NCO models fail to distinguish the promising node. To this end, 13 [19 propose projection strategy to transform the extracted subgraph to a uniform distribution. While these strategies can enhance generalization, their effectiveness typically requires integration into model training, thereby imposing additional computational overhead and limiting their adaptability.
Preliminaries
VRP Definition The VRP defined on a graph G (V, E). where V (Vo, ui,..., Un) represents nodes (with vo as the depot CVRP) and E denotes edges. Each non-depot node ( has coordinates 8; IR2 and a demand d, while vp has no demand. For the TSP, the objective is to find single tour that explicitly visits all nodes once, minimizing the total Euclidean distance. In CVRP, vehicles with fixed capacity must deliver goods from the depot to customers, forming multiple routes that start and end at Un. Each customer is visited once, and the cumulative demand per route cannot exceed the vehicle capacity. Solutions for both problems aim to minimize the total length of the tour, with feasibility requiring adherence to node visitation and capacity constraints.
Automatic Heuristic Design (AHD) AHD aims to automatically discover high-performing heuris- ties h for a target task T. such as combinatorial optimization. Formally, given a task T with input space Xy, AHD seeks to identify optimal heuristic h" from heuristic space H by maximizing the expected performance over instances I E Xx:
h" arg max Ex-x, (1) bcH
(I)
where fT h) quantifies the effectiveness of heuristic h on instance x. The heuristic space H encompasses all feasible strategies that adhere to the constraints of T. This approach aligns with hyper-heuristic methodologies [5I), which automate heuristic selection or generation without domain- specific bandcrafting.
3

---

LLM-based AHD integrates LLMs into the evolutionary search for a high- performance heuristic [52 This paradigm leverages LLMs to generate and refine heuristics through natural language reasoning and code synthesis. Within an evolutionary computation frame- work, LLMs simulate mutation and crossover operations by modifying or combining existing heuris- tics. For example, given parent heuristic, L.MS can introduce new algorithmic components, adjust parameters, or merge features from multiple candidates, guided by linguistic prompts that encode lask-specific objectives and constraints. This iterative process balances the exploration of high-quality candidates, enabling efficient traversal of the heuristic space H.
LLM-Based AHD
4 Distribution Projection in Large-Scale VRPs
Inforenee
Thining Phase
TSPSE Indence
KNN wwg.ape (RWW 0.124)
Projecte oihyaph (IWWI 01023)
Traininng Incorics
(()
Figure 1: (a) Solution construction process for solving TSP5K instance, gray node, blue node, red node, and grey line denote the unvisited nodes, KNN (k=100) the current node, current node, and constructed partial route, respectively. (b) Extracted KNN graph, RWD [56] indicates the distance between the input graph and a uniformly distributed training instance. (c) Projected KNN graph. (d) Training instance with 100 nodes.
When solving large-scale VRPs, current methods are facing challenges from the exponentially growing search space. As shown in the Figure. (a), existing works reduce the search space to the KNN the last visited node. Despite this reduction providing sufficient improvement, Figure. (b) demonstrates that the selected KNN subgraphs come with various distributions that drastically differ from the training instance. Making it difficult for the model to predict the next promising node. Recent studies provide several projection techniques project the input subgraph to uniform distribution [3 1 19. In this section, we systematically analyze the effectiveness of these projection methods and observe that such technique has great impact the model's final performance.
Table 1: The effect of projection strategy on the gap in the LEHD model
TSPIK Gap
TSPSK Gap
TSPI0K Gap
TSP50K
TSP100K Gap
Method
Gap
LEHD w/o pruj
4.45%
12.80%
17.42% 3.77%
48.00% 3.42%
121 42%%
LEHD w/ proj
2.96%
3.32%
3.24%
To validate the effectiveness of the projection, we employ the LEHD [8] the base model, restricting its search space to the KNN (A= = 100) nodes from the last visited node. Then, we apply the projection method used in INVIT [15] to map the subgraph. Subsequently, the LEHD is adopted to select one promising node within the transformed subgraph. The experimental results are provided Table I The experiment results exhibit that LEHD with the INVIT projection method outperforms LEHD without projection consistently on all scales in TSP.
These findings underscore the criticality of maintaining distribution consistency between the model's training data and its inference inputs for effective large-scale generalization. Projection techniques serve primary mechanism to achieve this alignment by transforming varied input distributions to the training set. Consequently, the development of more sophisticated and robust projections crucial for advancing model generalization capabilities.

---

Prompt Strategles
Olispring
Function Dociption Fince
Exploration
Given seveni functions, generate...
Modification
Given one function, modify... performance.
L.M
Selection prob
Popralation,
Population;
Top-N
Population,
Individual Generation
Evaluate
Fandi
Repest
Fitness
NCO
Value
KNN
Projection
Pane
Unvisited Node
Visited Node
time
Current Node
First Node
The pipeline of the TTPL framework. comprises four components: initialization, fitness evaluation, offspring generation, and population update. (a) Initialization: TTPL establishes the initial population by generating individuals through prompting LLM with a predefined template. Following the initialization, iterative optimization procedure is employed search for the optimal individual. (b) Offspring generation: Offspring individuals are produced using several L.I I.LM-based evolutionary prompt strategies. (c) Fitness evaluation: An NCO model assesses the performance of these newly generated individuals. (d) Population update: The highest-performing individuals then selected to constitute the succeeding generation, and this iterative process repeats until the specified termination criteria are satisfied.
Figure 2:
5 Methodology
5.1 Test-Time Projection Learning
Current methods typically train models on small-scale, uniformly distributed datasets. However, these models often underperform on large-scale or real-world data due to the distributional shift between training and test instances. To address this challenge, we propose Test-Time Projection Learning (TTPL), an I.LM-driven evolutionary framework that leverages LIM to generate optimal projection strategy. Specifically, it comprises two components: 1) NCO-based strategy evaluator designed to measure the strategy generated by LLM; 2) an evolutionary projection strategy generator employs diverse prompt strategies to guide the LLM in developing these strategies.
Method Framework The overall framework of TTPL demonstrated the Algorithm, [ Its inputs consist of the population size N, number of generations N the NCO model fe. the LLM used evolve the strategy, and the evaluation data set D. TTPL follows the general framework of EoH [52]. Therefore, we first generate N individuals using LLM with the prompts from EoH. Here, individuals consist of a description in natural language and code block that implements the projection. These individuals are then evaluated by the NCO model fe to construct the initial population Po. Moreover, we conduct N, iterations obtain an optimal projection strategy. each iteration, we prompt LLMs to design different individuals based on set of selected parents. Once the new population generated, we select the first N best individuals as the next generation. Finally, it outputs the optimal strategy found in previous iterations
5

---

Algorithm 1 a" = TTPL(N, N3 fo, LLM, D)
Input:
2: Population size: N; Number of Generation: Ng; NCO model: fo;
3: given LLM: Evaluation dataset
4: Output:
5: Code for the best found projection strategy:
6: Initialization:
7: for =: do
8: Initialize new individual aj of the target model using LLM
9: Evaluate a, and obtain the fitness value fō(a;) with evaluation dataset D
10: end for
11:
Construct initial population Po = (ai....,aN) aN)
12: for i =: Ng do
13:
for jor: N
14:
Generate new offspring using prompt strategies from 22
15:
Evaluate offspring and obtain their fitness value with evaluation dataset
16:
end for
17:
Construct offspring population O
Sort O in descending order based on their fitness value Update P:-1 with the first N individuals in O
19:
20:
end for
21:
Return: The best found projection strategy: a";
Individual Evaluation To evaluate the LLM-designed strategies, deploy them within the target NCO model and calculate the objective value on the evaluation dataset D. Specifically, given current node Us we first select & nearest neighbors to form the subgraph Gg. Then, the strategy is performed on G2 to obtain the projected graph Gv. Moreover, we input the projected subgraph to the given NCO model So and select a node within GN as the destination of the next step. By repeating the above process, the final solution of a VRP instance is constructed step by step. Finally, the solution length recorded the fitness value of the input strategy.
Individual Generation After initialization, Ng iterations are conducted to evolve the population. In each iteration, we first randomly select set of parent individuals from the current population based on the probability:
1/2":
prob:
Σ 1/2"/
where r; the rank of their fitness. After that, the selected parents are used generate offspring through the four prompt strategies in [52), which consist of two groups, namely, Exploration (E1, E2) and Modification (M1, M2). The exploration prompt focuses on generating new individuals based on several selected parent strategies, while the modification prompt aims to modify the selected strategy for better performance. The details of four prompt strategies can be found the Appendix. B.1
5.2 Multi-Vies Decision Fusion
Projection strategies transform the entire subgraph by a series of operations (e.g., rotation and translation) align complex input distributions with the uniformly distributed training data. However, these graph-wise operations often struggle in normalizing local regions with density variations (i.e., strip-like node clusters TSP), thereby impairing the model to distinguish promising nodes in local regions.
To resolve this limitation, propose Multi- View Decision Fusion (MVDF), applied to the projected subgraphs. MVDF facilitates robust node identifications by generating multiple perspectives (views) of the subgraph. The model evaluates each perspective, and the resulting selection probabilities aggregated. Ultimately, the perspective yielding the highest prediction score primarily guides the final decision.
In particular, given subgraph with coordinates E Rx2 we generate M augmented variants through geometric transformations Tm (X) proposed in (6). Each augmented subgraph X.,. Tm (X)

---

is solved by the NCO model to produce logits aggregating logits across all augmentations:
In E ER.. The final selection probability is derived by
M Σ 17
p p=a
1m
(3)
where a (-) denotes the softmax function. This ensemble strategy forces the model to learn wtn.imatttoooiiiiiannn features, effectively neutralizing local density deviations.
6 Experiment
Table 2: Comparison results on the synthetic TSP and CVRP dataset. *; Results are directly cited from the original publications. N/A: results that exceed the time limitation (seven days). OOM: results that exceed GPU memory limits.
TSPIK
TSPSK
TSP
TSPS0K
TSP LOOK
Method
Obj,/Gap)
Time
Obj//Gup)
Time
Obj/CCp)
Time
ObytCGup)
Time
UbjuGGap)
Time
LKH3
23:12 (OL0HH)
1.7m
50:57 (OLUUSE)
12m
71.78 10.00%)
33m
199.9 (U,009)
10h
225.99 (0 (0.00%)
25g
Conosede
33.12 (0.00%)
Im
50.05 (40.059)
81m
72.00 (0.15%)
1.4h
NIA
N/A
N/A
NIA
Random Inscction
26.11 (12.9%%
<1s
58.06 (9.
<ls
81.82. (13.9%)
<Is
182.65 (14.28)
15.46
(14.28()4288)
1.7m
DIRUSCO*
33.39 (1.175)
11.5%
73.63 (2.58%)
3.0m
TPTSP
24.56 (5.6615)
48s
55.16
(8.21%)
1m
77.75 (8.58%)
2.2m
COM
DOM
GLOPP
23.78 (2.85%)
10.25
53.15 (4.26/9)
1.0
75.04 (4.39%
19th
168.09 (5.10%)
1.5m
237.61 (5 14%)
3.9m
POMO sug 88
32.51 (40.65)
4.14
87.72 (72.1 198)
8.6m
00M
0OM
00M 00M
BLG oug 8
25.758 (11.35%8)
0.8%
66.19 (888))
214
DOM
0OM
LEHD RRCI1000
23.29 (0: (0.725)
3.3m
54.43
16, (6.79%)
6m
80.90 (12.5%)
6m
00M
0OM
BQ hel66
33.43 (1.375)
13c
705) 58.27
24s
0OM
0OM
DOM
SIGD bs16
23.36
17.36
(9.42%)
30.5m
00M
0OM
0OM
INVI 3V greedy
24.56 (6.6618)
9.0s
54,49 (6.905))
1.2m
76.85 (7.0%%)
3.7m
171.42 (7.18%)
1.3h
242.26 (7.201))
5.0h
LEHD gradly
13.84
58 (15.4666)
(445)
00M
00M
BQ greedy
23.65
31%) 57.19
22.5%
25.02%)
00M
00M
SIGD greddy
20.573
(80%)
15.5m
0OM
TTPL
(2.65%)
(3.255)
74.39
(3.22%)
MYDF
23.64 (2.26%)
0.55
52.43 (2.801))
3.24
75.49
(2.39%5
7.24
24 (2.69%)
32.3s
231.78 (615))))
TIPL MVDF RRCIO10
23.19 (0.28%)
3.0m
4.9m
72.59 (1.13%)
5.0m
102.40 (1.55%)
5.4m
229.66 (1.6%%)
5.5m
CVRPIK (hjp(lap))
CVRP5K
CVRPIOK
CVRPSOK
CVRPLOOK
Methed
Time
Ohj/Clap)
Time
Time
Time
(kj.(Giap)
Time
HGS
(0.00)))))
5m
126
(0.0055)
5m
227.3 (0:00)
Sen
1081.0 (0.00%)
4h
2087.5 (0 00%)
6.3h
GLOOP-G (1 KH-3)
(1..41))4%)
1.1%
140
(48)
4.0x
256 (16)
6.24
00M
00M
POMO 88
101 (145, (5%)
4.8
632.9 (401 519)
11m
0OM
00M
0OM
BLG 8
(12.66)))
0OM
0OM
0OM
LEHD RRC11000
(2.412.91%)
3.4m
132.7 (5.15%5
10m
243.8
(7.25%)
51.6m
0OM
0OM
BQ
136.4 4 (896)
00M
0OM
SIGID bc16
(7.54%)
(9.1516)
2.7M
247.2 (9.01%)
60u
1255.5 (16.30%)
0OM
INWIT-WV greedy
(16.99))
(16. 1696)
1.4
(15.318)
4.3m
1331.1 (23.1%)
1.5h
2683.4 (25. 558))
5.8h
LEHD greedy
(9,516)
1.4m
12m
BQ greedy
(7.28%))
139.9 (108895)
18.5%
OOM
SIGD greedy
45,4 (10.39%)
140.2 (11.31%)
9.1s
(11.34%)
48.9%
(18.02))
10.2m
0OM
TIPL MVVDF
(8.60%)
(6.4216)
0.5s
238.9 (5.11%)
1143.2 (5.72%)
2220.4
41.3s
79%))
0.5
132.4 (4 886)
2.5%
253.0 (2.54%)
7.74
1110.9 (2.73%)
40.5%
60%)
TIPL MVDF RRC1000
42.5 (3.281%)
4.1m
129.2 (2.37%)
4.0m
(1.02%)
6.4m
1105.6 (2.25%)
7.0m
(3.32%)
7.7m
Problem Setting We evaluate our method on TSP and CVRP instances. Following established benchmarks 18], the test sets include 128 instances for TSPIK and 16 instances each for TSP5K, 10K, 50K, and 100K. For CVRP, we use 100 instances for CVRP1K and CVRP5K and 16 instances each for CVRP10K, CVRP50K, and CVRP100K CVRP capacities for
200 for CVRPIK and 300
Optimal TSP solutions are calculated using LKH3 57 while CVRP
solutions are derived using HGS (58). To further assess generalization, we follow 4 and evaluate on real-world instances from TSPLIB (59) and CVRPLIB [60]. selecting symmetric EUC_2D instances with over 1K nodes (33 TSP and 14 CVRP instances). This ensures alignment with both synthetic benchmarks and practical scenarios.
Model Setting Our experiments adopt LEHD the base model [8]. aligning with its original architecture and hyperparameters. The embedding dimension is configured to 128, and the decoder comprises 6 attention layers. Each multi-head attention layer uses 8 heads, while the feed-forward layer dimension is set to 512. We configure the KNN to 100. All experiments are performed on a single NVIDIA GeForce RTX 3090 GPU with 24GB of memory.
L.M-AHD Setting The evolutionary framework follows the approach proposed by FoH [52]. The population size is set to 20, and the evolution process is run for 105 generations. The parent heuristic
7

---

is set to 2. The GoT-4o-mini model serves as the LLM backbone. For TSP/CVRP IK, 5K, and 10K. we optimize one projection strategy for each scale, and generalize the strategy optimized on 10K to TSP/CVRP 50K and 100K due to the computational burden. At the beginning of the optimization, we input the projection strategy proposed in as a seed guide the heuristic design.
Baselines We compare TTPL with six categories of methods: Classical Solvers: Concorde [6], LKH3 [57] and HGS [58] Insertion Heuristic: Random Insertion: Construction- NCO
Methods: POMO 77. BQ [42), LEHD [18], INVIT (I5) and SIGD [62]; Heatmap- Methods:
DIFUSCO [8];: Decomposition-basee Method: GLOP 13, H-TSP [2]; Local Construction-
based Method: ELG [4.
Metrics and Inference We evaluate the performance using the optimality gap and inference time. The optimality gap quantifies the percentage difference between solutions generated by our method and the ground truth obtained from LKH3 (TSP) HGS (CVRP). Inference time, reported in seconds (s), minutes (m), and hours (b), captures the computational efficiency of generating solutions across varying problem scales. For TTPL, we report three types of results, those obtained by greedy trajectory with a purely designed projection method, those obtained by greedy trajectory with our designed projection and MVDF, and those obtained with projection, MVDF, and Random Re-Construction (RRC) under 1000 iterations [8]
6.1 Experimental Results
Results on Synthetic Dataset Table presents the comparative results, underscoring our method's superior performance and robust generalization capabilities across various problem scales. For TSP instances, our method, when relying on purely greedy construction, outperforms other greedy constructive methods for 1000 iterations, our approach consistently delivers the best performance across all TSP scales. Specifically, it reduces the optimality gap by 61.11%, 75.59%, 56.2%, 69.6 %, and 68.29% for the TSPIK, 5K, 10K, 50K, and 100K instances, respectively, when compared to the leading alternative method. In the context of CVRP, our method, utilizing purely greedy sampling, secures the best results on all scales, with the exception of CVRPIK. Furthermore, by integrating RRC, our method is able to significantly surpass all other approaches across all evaluated CVRP scales. This translates to optimality gap reductions of 53.98%, 85.99% 86.20% and 88.37% on CVRP5K, 10K, 50K, and 100K instances, respectively, relative to the strongest competing baseline methods.
problem scales, except TSPIK. However, by incorporating RRC
Table 3: Result on TSPLIB and CVRPLIB. OOM: results that exceed GPU memory limits. f: several instances are not solvable due to exceeding GPU memory limits.
TSPLIB
CVRPLIB
Method
IK 5K
5K
All
Solved
IK 7K
7K
All
Solved
GLOP
5.02%
6.87%
5.50%
31/33
15.34%
21.32%
17.90%
14/14
ELG augx8
11.34%
OOM
11.34%
23/33
10.57%
OOM
10.57%
6/14
BQ bs16
10.65%
30.58%
12.95%
26/33
13.92%
OOM
13.92%
8/14
LEHD RRC1,000
4.00%
18.46%
7.37%
30/33
8.42%
21.53%
11.04%
10/14
SIGD greedy
12.37%
152.88%
48.63%
31/33
14.73%
49.49%
29.63%
14/14
BQ greedy
11.64%
162.12%
64.65%
32/33
16.92%
$2.27%
32.07%
14/14
INVIT greedy
11.49%
10.00%
11.04%
33/33
15.87%
26.64%
20.49%
14/14
LEHD greedy
11.14%
39.34%
17.72%
30/33
15.20%
32.80%
18.72%
10/14
TTPL
6.04%
4,57%
5.80%
33/33
11 11.89%
14.93%
13.19%
14/14
TTPL-MVDF
3.81 %
4.05%
3.88%
33/33
10.41%
11.71%
10.97%
14/14
TTPL-MVDF RRC1000
1.04% %
2.12%
1.37%
33/33
5.20%
10.56%
7.50%
14/14
Results Benchmark We further test method on TSPLIB [59] and CVRPLIB (60]. The detailed results are demonstrated in the Table 3 When using greedy construction for inference, LEHD purely with our designed projection can achieve a better result than other construction-base methods on all groups of instances. Using the MVDF and RRC further strengthens our performance, which yields significant gap between the second-bes methods.
6.2 Ablation Study

---

Table 4: Comparison between different projection strategies on the synthetic TSP dataset.
TSPIK
TSP5K
TSP
TSPS0K
TSPI0IK
(hop()
Time
Ohj,(Gap)
Time
Obj:(Giap)
Time
(Cop))
Time
(hjj/Guup)
Time
w/o proj
24.2 (4.49%)
0.1s
57.5 (12.80%)
1.4c
84.3 84.3 (17 42%%)
2.75
236.7 (48 (48.00%)
13.25
(12) (121,4))
27.8s
seed proj
23.8 (2.968)
0.1s
52.7 (3.32%)
1.5s
74.5 (3.77%)
2.9
165.4 (3.42%)
14.4s
233.3 (3.24%)
29.6s
23.73 (2.68%)
0.1s
52.63 (3.25%)
(3.63%)
2.9%
165.19 (3.29%)
233.26 (3.22%)
28.9%
Effects of Designed Projection To validate the effectiveness of the LLM-designed projection strategy, we design two variants of our method: 1) w/o proj: LEHD only uses KNN to reduce the search space during inference. 2) seed proj: The projection strategy is replaced with the input seed strategy in [3]. As exhibited in the Table. 4 the projection strategy designed from the TTPL framework consistently outperforms the two variants on all scales.
Table 5: Comparison between LEHD with MVDF, POMO aug, and without MVDF on synthetic TSP dataset
TSPIK (bjp))ap)
TSPSK
TSP10K
TSPS0K
TSP100K
Time
Obj.(Gap)
Time
(Gap)
Time
ObjaGaa))
Time
(bjp(Gap)
Time
w/o MVDF
23.7 (2.65%)
0.1s
52.6 (3.25%)
1.48
74.4 (3.63%)
2.9s
165.2 (3.29%)
14.3s
233.3 (3.22%)
28.96
POMO aug
23.4 (0.89%)
0.5g
52.1 (2.22%)
3.18
73.6 (2.56%)
6.3s
164.5
86%)
36.6s
232.4 (2.85%)
155m
TTPL-MVDF
23.6 (2.266)
0.5s
52.4 (2.8
3.28
73.5 (2.39%)
7.2s
164.2 (2.
32.1s
231.8 (2.56%)
1.1m
To assess the efficacy of our proposed MVDF, we compare our complete method against two configurations: 1) w/o MVDF: LEHD utilizes the designed projection but without MVDF during inference: 2) POMO aug: test instances are first augmented using the POMO augmentation 77. and then solved with LEHD equipped with the designed projection. The complete results are shown in Table Our MVDF approach outperforms the w/o MVDF variant in out of cases and the POMO aug variant in 3 out of 5 cases. Notably, MVDF demonstrates particular effectiveness when solving large-scale instances.
Effects of MVDF
6.3 Versatility study
Table 6: Results of TTPL-MVDF designed strategy performed on POMO randomly generated test
instances
TSPIK
TSPSK
TSPIOK
TSPS0K
TSP100K
Obj-
Time
Obj.
Time
Obj.
Time
Obj.
Time
Obj.
Time
POMO knn
33.4
0.2s
96.1
3.8s
153.4
7.5s
392.4
38.5s
597.8
1.3m
POMO seed
30.0
0.28
73.8
4.0s
103.0
7.98
235.8
39.9s
331.3
1.3m
POMO Ours
29.8
1.38
67.6
7.8s
94.6
15.5s
212.1
1.3m
296.6
2.6m
Versatility on the Other Model The versatility of our proposed techniques is further investigated by replacing the base model from LEHD with POMO, a well-known model trained by RL. We compare POMO, which is equipped with our proposed projection and MVDF technique, against POMO using KNN and the seed projection method. As shown in the Table our method on POMO surpasses the compared approaches, indicating promising adaptability different base models.
Versatility on Different Distributions The robustness of TTPL-MVDF is evaluated on cross- distribution instances (cluster, explosion, and implosion) from [5] Compared against LEHD without projection and LEHD with seed projection, TTPL-MVDF demonstrates a significant improvement in the base model's 's robustness. These findings (see Appendix D.2 for full results) validate the effectiveness of our proposed method in handling distributional shifts.
7 Conclusion, Limitation, and Future Work
In this work, we have presented an LLM-driven projection learning framework to improve model generalization in large-scale vehicle routing problems (VRPs). The core idea is to utilize an LLM to model the relationship between training and test data distribution, thereby informing the generation of optimized projection strategy. To further boost performance, we have developed Multi-Vin View

---

Decision Fusion (MVDF), which presents the model with multiple views of the original problem instance, enabling it to select the most confident one to guide node selection at each construction step. Empirical evaluation on diverse synthetic and real-world TSP and CVRP benchmarks confirms that our approach markedly enhances the zero-shot generalization capability of a hase model (trained solely on 100-node instances) to large-scale instances.
Limitation and Future Work While TTPL-MVDF shows superior performance on large-scale instances, limitation of TTPL-MVDF is the relatively slow convergence to optimal strategies within its LLM optimization phase. In the future, we will investigate more efficient LLM optimization operators for improved evolution speed.
Acknowledgments and Disclosure of Funding
This work was supported in part by the National Natural Science Foundation of China (Grant 62476118) the Natural Science Foundation of Guangdong Province (Grant 2024A1515011755 the Guangdong Science and Technology Program (Grant 2024B12120100 2212000002) and the Center for Computational Science and Engineering at Southern University of Science and Technology.
References
[1] Matthew Veres and Medhat Moussa. Deep learning for intelligent transportation systems: A survey of emerging trends. IEEE Transactions Intelligent Transportation Systems, 21(8):3152-3168, 2019.
Alexandre Laterre, Yunguan Fu, Mohamed Khalil Jabri, Alain-Sam Cohen, David Kas, Karl Hajjar, Torbjorn Dahl, Amine Kerkeni, and Karim Beguir. Ranked reward: Enahling self-play reinforcement learning for combinatorial optimization. arXiv preprint arXiv: 2018.
[3] Antonio Giallanza and Gabriella Li Puma. Fuzzy green vehicle routing problem for designing three echelons supply chain. Journal of Cleaner Production, 259:120774, 2020.
[4] Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Srachetti-Spaccammlla and Marco Protasi. Complexity and upproximation: Combinatorial optimization problems and their approximability properties. Springer Science & Business Media, 2012.
[5] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d' l'horizoo. European Journal of Operational Research, 290(2):405-421, 2021.
[6] Wouter Kool, Herke Van Hoof. and Max Welling, Attention, learn solve routing problems! arXiv preprint arXiv: (atp:1803.0477. 2018.
[7] Ycong-Dac Dac Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Scungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 18:221888-20 21 198. 2020.
[8] André Hottung, Yeong- Boong-Dae Kwon, and Kevin Tierney. Efficient active search for combinatorial optimization problems. arXiv preprint arXiv:2106.051 05126/ 2021.
[9] Changliang Zhou, Canhong Yu, Shunyu Yao, Xi Lin, Zhenkun Wang. Yu Zhou, and Qingfu Zhang. Urs: unified neural routing solver cross-problem zero-shot generalization. arXiv preprint arXiv:2509.23411 234113 2025.
[10] Yan Jin, Yuandong Ding, Xuanhao Pan, Kun He, Li Zhao, Tao Qin, Lei Song, and Jiang Bian. Pointerformer: Deep reinforced Conference on Artificial Intelligence. volume 37, pages 8132-8140. 2023.
transformer for the traveling salesman problem. In Proceedings of the AAAI
[11] Jianan Zhou, Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Towards omni- amni-generalizable neural methods for vehicle routing problems. In International Conference Machine Learning, pages 42769- 42789. PMLR, 2023.
[12] Xuanhao Pan, Yan Jin, Yuandong Ding, Mingxiao Feng. Li Zhao, Lei Song, and Jiang Bian. H-tsp: Hierarchically solving the scale traveling salesman problem. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pages 9345-9355 2023.
10

---

[13] Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao, Yong Li, and Fanzhang Li. Glop: Learning global partition and local construction for solving large-scale routing problems in real-time. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 20284-20292, 2024.
[14] Chengrui Gao. Haopu Shang, Ke Xue, Dong Li, and Chao Qian. Towards generalizable neural solvers for vehiele routing problems via ensemble with transferrable local policy. arXiv preprint arXiv:2308. 14104, 2023.
[15] Han Fang, Zhihao Song, Paul Weng, and Yutong Ban. Invit: A generalizable routing problem solver with invariant nested view transformer. arXiv preprint arXiv:2402.02317, 2024.
[16] Minsu Kim, Jinkyoo Park. et al. Learning collaborative policies to solve np-hard routing problems. Advances in Neural Information Processing Systems, 34: 10411-004440 2021.
[17] Hanni Cheng, Haosi Zheng. Ya Cong, Weihao Jiang, and Shiliang Pu. Select and optimize: Learning to solve large-scale Isp instances. In International Conference Artificial Intelligence and Statistics, pages 1219-1231. PMLR, 2023.
[18] Luo, Xi Lin, Fei Liu. Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. Advances in Neural Information Processing Systems, 06:8845-8864, 2023.
[19] Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha Generalize a small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 7474-7482, 2021.
[20] Ziwei Huang, Jianan Zhou, Zhiguang Cao, and Yixin Xu. Rethinking light decoder-based solvers for vehicle routing problems, arXiv preprint arXiv:2503.00753 2025.
[21] Yeong-Dae Kwon, Jinho Choo, Iijoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. Advances in Neural Information Processing Systems, 14:5138-5149, 2021.
[22] Darko Drakulic, Sofia Michel, and Jean-Mare Andreoli. Goal: A generalist combinatorial optimization agent learner. In The Thirteenth International Conference on Learning Representations, 2024.
[23] Fei Liu, Xi Lin, Zhenkun Wang, Qingfu Zhang, Tong Xialiang, and Mingxuan Yuan. Multi-task learning for routing problem with cross-prohlem zero-shot generalization. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1898-1908, 2024.
[24] Jianan Zhou, Zhiguang Cao, Yaoxin Wu, Wen Song, Yining Ma, Jie Zhang, and Chi Xu. Mymoe: Multi-task vehicle routing solver with mixture-of-expertt arviv preprint arXiv:2405.01029 2024.
[25] Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
[26] Zhang, Jingfeng Yang. Zhiguang Cao, and Xu Chi. Adversarial generative flow network for solving vehicle routing problems. arXiv preprint arXiv:2503.01933 2025.
[27] Yang Li, Jinpei Guo, Runzhong Wang. and Junchi Yan. T2t: From distribution learning in training to gradient search in testing for combinatorial optimization. Advances in Neural Information Processing Systems, 36:50020-5000 50000, 2023.
[28] Zhiqing Sun and Yiming Yang. DIFUSCO: Graph-based diffusion solvers for combinatorial optimization. Advances in neural information processing systems, 36:3706-3731, 2023.
[29] Yang Li. Jinpei Guo, Runzhong Wang. Hongyuan Zha, and Junchi Yan. Fast 12t: Optimization consistency speeds up diffusion- Information Processing Systems, 37:30179-30206, 2024.
solving for combinatorial optmization. Advunces in Neural
[30] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015.
[31] Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv: 1e.1111119999 1,09940, 2016.
[32] Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems, 31, 2018.
11

---

[33] Michel Deudon, Pierre Cournut, Alexandre Lacoste. Yossiri Adulyasak, and Louis-Martin Rousseau. Learning heuristics for the isp by policy gradient. In Integration of Constraint Programming. Artift- cial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26- 29, 2018, Proceedings 15, pages 170-181. Springer, 2018.
[34] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Fukasz Kaiser, and Illia Polosukhin, Attention all you need. Advances neural information processing systems, 30, 2017.
[35] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Step-wise deep learning models for solving routing problems. IEEE Transactions on Industrial Informatics, 17(7):4861 4871, 2020.
[36] Rui Sun, Zhi Zheng, and Zhenkun Wang. Learning encodings for constructive neural combinatorial optimization needs to regret. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 20803-2081 11 2024.
[37] Zhi Zheng. Shunyu Yao, Zhenkun Wang, Tong Xialiang. Mingxuan Yuan, and Ke Tang. DPN: Decoupling partition and navigation for neural solvers of min-max vehicle routing problems. In Forty-firsi International Conference on Machine Learning, 2024. URL http::tttppsesreeeeeeeee
net aet/forumm add-a 14
[38] Changliang Zhou, Xi Lin, Zhenkun Wang, Xialiang Tong. Mingxuan Yuan, and Qingfu Zhang. Instance- conditioned adaptation for large-scale gencralization of neural combinatorial optimization. arXiv preprint arXiv:2405.0199 2024.
[39] Zhi Zheng, Shunyu Yao, Genghui Li, Linxi Han, and Zhenkun Wang. Pareto improver: Learning improvement heuristics for multi-objectinn route planning. IEEE Transactions on Intelligent Transportation Systems, 25(1):1033 1043, 2024. doi:
[40] Han Li, Fei Liu, Zhi Zheng, Yu Zhang, and Zhenkun Wang. CaDA: Cross-problem routing solver with constraint- aware dual-attention. In Intermational Conference on Machine Learning, 2025. URL
httpa://openreviee net/forrmmiddeeeeee .et.//forumrid---5y/hhtut
[41] Fu Luo, Yaoxin Wu, Zhi Zheng. and Zhenkun Wang. Rethinking neural combinatorial optimization for vehicle routing problems with different constraint tightness degrees, 2025. URL lttpps://axxiv........ org/ abs/2505. 24627
[42] Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Mare Andreoli. Bq-nco: Bisimulation quotienting for efficient neural combinatorial optimization. Advances in Neural Information Processing Systems, 36.77416-77429, 2023.
[43] Yuhong Cao, Zhanhong Sun, and Guillaume Sartoretti. Dan: Decentralized attention-based neural network for the minmax multiple traveling salesman problem. In International Symposium on Distributed Autonomous Robotic Systems, pages 202-215. Springer, 2022.
[44] Fu Luo, Xi Lin, Yaoxin Wu, Zhenkun Wang, Tong Xialiang, Mingxuan Yuan, and Qingfu Zhang. Boosting neural combinatorial optimization for large-scale vehicle routing problems. In International Conference on Learning Representations, 2025.
[45] Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate large-scale vehicle routing. Advances in Neural Information Processing Systems, 34:26198-26211 2021.
[46] Zefang Zong. Hansen Wang. Jingwei Wang, Meng Zheng, and Yong Li. Rbg: Hierarchically solving large-scale routing problems logistic systems via reinforcement learning. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4648-4658, 2022.
[47] Qingehun Hou, Jingwei Yang, Yiqiang Su, Xiaoqing Wang. and Yuming Deng. Generalize learned heuristies to solve large-scale vehicle routing problems in real-time. In International Conference on Learning Representations, 2023.
[48] Zhi Zheng, Changliang Zhou, Tong Xialiang, Mingxuan Yuan, and Zhenkun Wang. UDC: A unified neural dividc-and-congeee framework for large-scale combinatorial optimization problems. In Advances in Neural Information Processing Systems, 2024.
[49] Yang Wang, Ya-Hui Jia, Wei-Neng Chen, and Yi Mci. Distance-aware attention reshaping: Enhance generalization of neural solver for large-scale vehicle routing problems. arXiv preprint u6X1::2401.0697, 2024.
[50] Changliang Zhou, Xi Lin, Zhenkun Wang, and Qingfu Zhang. L2r: Learning to reduce search space for generalizable neural routing solver. arXiv preprint arXiv:2503.03137, 2025.
12

---

[51] Edmund K Burke, Michel Gendreau, Matthew Hyde, Graham Kendall, Gabriela Ochoa, Ender Özcan, and Rong Qu. Ilyper-heuristee:: A survey of the state of the art. Journal the Operational Research Society, 64(12):165-1172, 2013.
[52] Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang. Evolution of heuristics: Towards efficient automatic algorithm design using large language m20e.(2024). arXiv preprint WrXiv:2401000055 2024.
[53] Zhi Zheng, Zhuoliang Xie, Zhenkun Wang, and Bryan Hooi. Monte carlo tree search for comprehensive exploration in LLM-based automatic heuristic design. In International Conference on Machine Learning, 2025. URL httthtt htttp::///peereviieee
[54] Kai Li, Fei Liu, Zheakun Wang. Xialiang Tong. Xiongwei Han, Mingxuan Yuan, and Qingfu Zhang. Ars: Automatic routing solver with large language models. arXiv preprini arXiv:2502. 15359, 2025.
[55] Kai Li, Ruihao Zheng. Xinye Hao, and Zhenkun Wang. oulti-objective infeasibility diagnosis for routing problems using large language models. arXiv preprint ar0iv:2508. 03406. 2025.
[56] Xu Wang, Fuyou Miao, Wenjie Liu, and Yan Xiong. Efficient and robust neural combinatorial optimization via wasserstein--aase coresets. In The Thirteenth International Conference on Learning Representations.
[57] Keld Helsgaun. An extension of the Beemiighan-helsgaun tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University. 12:966-980, 2017.
[58] Thibaut Vidal. Hybrid genetic search for the evrp: Open-source implementation and swap* neighborhood. Computers & Operations Research, 140:105643, 2022.
[59] Gerhard Reinelt. Tsplib- traveling salesman problem library. ORSA journal on computing, 3(4):376-384, 1991.
[60] Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, Thibaut Vidal, and Anand Subramanian. New benchmark instances for the capacitated vehiele routing problem. Europeon Journal of Operational Research, 257(3):845-8555 858, 2017.
[61] Robert Bixby Vašek Chvátal David Applegate and William Cook. Concorde tsp solver. Concorde tsp solver. 2006.
[62] Jonathan Pimna and Dominik G Grimm. Self-improvement for neural combinatorial optimization: Sample without replacement, but improvement. arXiv preprint arXiv:2403.15180, 2024.
[63] Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. Advances in neural information processing systems, 32, 2019.
[64] Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. Advances in neural information processing systems, 31, 2018.
[65] André Hottung, Bhanu Bhandari, and Kevin Tiemey. Learning latent search space for routing problems using variational autoencoders. In International Conference Learning Representations, 2021.
[66] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint XxXiv:196.00122: 2019.
[67] Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic programming for vehicle routing problems. In International conference on integration of constraint programmingg artificial intelligence, and operations research, pages 190-213. Springer, 2022.
[68] Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. arXiv preprint arXiv:2110.0529) 2021.
[69] Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. Dimes: A differentiable meta solver for combinatorial optimization problems, Advances in Neural Information Processing Systems, 15:25531-255AM 2022.
[70] Yining Ma, Jingwen Li. Zhiguang Cao. Wen Song. Zhang, Zhenghua Chen, and Jing Tang. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. Advances in Neural Information Processing Systems, 34:1 1096-11107, 2021.
[71] Paulo R O Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Asian conference on machine learning. pages 480.480. PMLR, 2020.
13

---

[72] Quentin Cappart. Thierry Moisan. Louis-Martin Rousseau. Isabeau Trémont-Schwarz, and Andre A Cire. Combining reinforcement learning and constraint programming for combinatorial optimization. In Proceedings of AAAI Conference on Artificial Intelligence, volume 35, pages 3677-3687, 2021.
[73] André Hottung and Kevin Tiemnyy Neural large neighborhood search for the capacitated vehicle routing problem. ECAI 2020, pages 443-450 IOS Press, 2020.
[74] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Neurolkh: Combining deep learning model with lin- kernighan-helsee heuristic solving the traveling salesman problem. Advances Neural Information Processing Systems, 14:7472-7483, 2021.
[75] Jialin Song, Yisong Yue, Bistra Dilkina, A general large neighborhood search framework solving integer linear programs. Advances in Neural Information Processing Systems, 33:20012-20022 2020.
[76] Thomas Barrett, William Clements, Jakob Foerster, and Alex Lvovsky. Exploratory combinatorial opti- mization with reinforcement learning. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages
2020.
[77] Yaoxin Wu, Wen Song. Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving routing problems. IEEE Transactions on Neural Networks and learning systems, 33(9):5057-500 2021.
[78] Gurobi Optimization. Inc.. inuroi optimizer reference manual," 2015. 2014.
[79] Bernardino Comera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M Pawan
Kumar, Emilien Dupont, Francisco JR Ruiz, Jordan S Ellenberg, Pengming Wang, Omar Fawzi, et al. Mathematical discoveries from program search with large language models. Nature, 625(7995):468 475,
2024.
[80] Haoran Ye, Jiarui Wang. Zhiguang Cao, Federico Berto, Chuanbo Hua, Hacyeon Kim, Jinkyoo Park, and Guojie Song. Reevo: Large language models as hyper-heuristic with reflective evolution, Advances neural information processing systems, 37:43571 43608, 2024.
[81] Pham Tuan Dat, Long Doan, Huynh Thi Thanh Binh. Hsevo: Elevating automatic heuristic design with diversity- harmony search and genetic algorithm using llms. Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 26931-26938 2025.
[82] David Applegate, Ribert Bixby, Vasek Chvatal, and William Cook. Concorde tsp solver, 2006.
[83] Fei Liu, Rui Zhang, Zhuoliang Xie, Rui Sun, Kai Li, Lin, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang. LLM4AD: A platform for algorithm design with large language model. arXiv preprint 2rXiv:2412.17288
2024.
14

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, we clearly claim our contribution and scope in the abstract and intro- duction. Our primary contribution is powerful projection technique designed to enhance model generalization for large-scale Vehicle Routing Problems (VRPs). This research is situated within the field of neural combinatorial optimization.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss our limitation in Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
15

---

Answer: [NA]
Justification:
This paper does not incorporate theoretical results; all results presented in this
paper are experimental.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We specify the details reproduce our results in Section. In particular, contains the model architecture, dataset description, parameter settings, and experimental setups. All of them ensure our experiment results can be independently reproduced.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
16

---

reproducible, they 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [No]
Justification:
We will release our code and data once the paper is accepted.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
public/guides
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7/nips cc/ wtc/publicc/ cobollccggiddsss gwt.///ieee//eee// Codeeoomiiieeeee /esocguuuud//eeeuubbiiiiii SanSSuubissss iolbbmisssiooi ssisnnoiccyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We introduce all experimental details in Section. 6
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: In neural combinatorial optimization, we usually adopt the optimality gap and inference time metrics measure performance. Both of them are deterministic.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
17

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have introduced the hardware used to conduct our experiment in Section. 6 Specifically, we ran our experiments on single NVIDIA GeForce RTX 3090 GPU with 24GB of memory.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: ptttps:///eurippt wttpriisspccpppueee ht/ppubbl../tttiiccccceeeeeeeeee
Answer: [Yes]
Justification:
We follow the NeurlPS Code of Ethics in every respect during the research.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: Yes, we claim the details of societal impacts in the Appendix H. We believe the proposed method has no potential risk of leading to negative impacts that we feel must be highlighted.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
18

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper has no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cite the creators in the Reference and provide the license of the code in the Appendix. G
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
19

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not introduce new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing and human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing and human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
20

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [Yes]
Justification: We declare our usage of LLM in Section. projection strategies.
S which involved in designing
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy hatt::///oorrgsscco/oooeeeeeee/e for what should or should not be described.
21

---

A Related work
A.1 Review for Non-Constructive Method
Despite direct learning to construct VRP solution, other methods work closely with search and improvement methods 63 65]. Early studies [66] utilize a graph convolutional network to generate heatmaps indicating the probability of edges belonging
optimal solutions for TSP instances.
Subsequently, an approximate solution can be obtained via beam search [66]. Monte Carlo tree search [9]] dynamic programming [67], and guided local search (68. While initially developed for small-scale problems, recent studies extend heatmap-based methods to larger TSP instances [19] [99.
However, the adaptability of these methods can be limited by their reliance on carefully tuned search strategies, Furthermore, the heatmap representation primarily focuses on edge probabilities, which may restrict applicability problems with complex constraints.
Another research direction involves
algorithmss, where neural networks enhance traditional heuristic solvers. This includes accelerating solvers by learning operation selection
63 70 71 guided improvement (72774), and problem decomposition [45 75 Many improvement-
based methods propose iteratively refine feasible solutions [76 77 70) Nonetheless, these
methods typically depend on well-designed heuristic operators or advanced solvers [78] 57 for
solving different problems.
A.2 Review for LLM-AHD Method
Recent advancements demonstrate the significant potential of Large Language Models (LLMs) in automating the design of high-performing heuristics for complex computational problems. This methodology typically involves maintaining a population of elite heuristic functions, which are evaluated and ranked based their fitness on designated dataset. The LLM is then iteratively prompted with high-performing functions from this population to generate potentially superior heuristic candidates. EoH [52] and Funsearch [79 pioneer the application of LLM to design population- based evolutionary computation procedure. Building on this, ReEvo 80 incorporates reflection mechanism to augment the LLM's reasoning capabilities during heuristic generation. Addressing the challenge of premature convergence, HSEvo [8]] introduces diversity metrics and harmony search algorithm to enhance population diversity without degrading solution quality. In a different approach, MCTS-AHI [33 conceptualizes the task as a search problem, modeling the heuristic design process Monte Carlo tree search to systematically explore the solution space.
B Detailed Methodology
In TSP instances, the input distribution can be interpreted as the coordinate distribution, and transform- ing the coordinate uniform distribution can be seen as normalization. ease the understanding. we replace the projection with normalization when prompting the LLM. While the input of CVRP instances has extra demand and capacity, changing these features can easily lead unfeasible so- lutions. Consequently, we limit the modification to input within custom node coordinates, and the projection can be similarly interpreted as normalization.
B.1 Prompts of TTPL.
Our LLM-driven prompt framework for projection evolution consists of four core strategies (EI, E2, M1, M2) [52], each structured around three components: task description, strategy-specife instructions, parent projection, and template program. In the following, we detail their design principles:
El (Exploratory Generation): This prompt instructs an LLM to generate entirely new projection strategies by contrasting two existing approaches, explicitly avoiding structural similarities. It emphasizes divergence, requiring the LLM to innovate beyond the provided examples.
22

---

Prompt for E1
need help designing an innovative coordinate normalization strategy function im- plemented in PyTorch to normalize a set of nodes' coordinates, aiming to maximize the final negative gap. The input is tensor with shape (batch, num_nodes, and the coors' must be a tensor with the same shape 'coorl'.
have existing algorithms with their codes as follows:
No. algorithm and the corresponding code are:
(projection description) (Code]
No. 2 algorithm and the corresponding code are: [projection description)
[Code]
Please help me create new algorithm that has completely different form from the given ones.
I. First, describe your algorithm and main steps in sentence. The description must be within boxed [).
2. Next, implement the following Python function:
(Template Projection]
E2 (Backbone-Driven Innovation): Focused on identifying common design principles across parent strategies, this prompt guides an LLM to extract shared computational patterns (e.g., scaling mechanisms, coordinate transformations) and generate variants that preserve these core ideas while introducing novel components.
Prompt for E2
need help designing an innovative coordinate normalization strategy function im- plemented in Py'oorch to normalize
nodes' coordinates, aiming to maximize the final negative gap. The input is tensor with shape (batch, num num_nodes, 2) and the "all_coors' must be a tensor with the same shape as 'coorl'.
have existing algorithms with their codes as follows:
No. algorithm and the corresponding code are: (Projection description (Code]
No. algorithm and the corresponding code are: (Projection description) (Code)
Please help me create a new algorithm that has completely different form from the given ones, but be motivated by them.
1. Firstly, identify the common backbone idea in the provided algorithms.
2. Secondly, based on the backbone idea, describe your new algorithm in one sentence. The description must be within boxed [].
3. Thirdly, implement the following Python function:
(Template Projection]
M1 (Structural Mutation): Targets architectural modifications by presenting a single parent strategy and prompting an LLM to redesign its core operations (c.g.. changing anchor point for reference).
23

---

Prompt for M1
need help designing an innovative coordinate normalization strategy function im- plemented in PyTorch to normalize a set of nodes' coordinates, aiming to maximize the final negative gap. The input is tensor with shape (batch, num_nodes, and the "lll coors' must be tensor with the same shape 'coorl'.
have one algorithm with its code as follows. Algorithm description: (Projection description Code: (Code)
Please assist me in creating new algorithm that has a different form but can modified version of the algorithm provided.
1. First, describe your new algorithm and main steps in one sentence. The description must be within boxed {).
2. Next, implement the following Python function: (Template Projection]
M2 (Parametric Optimization): Specializes parameter tuning for critical projection variables (c.g., scaling factors, shift coefficients). directing an LLM to systematically adjust numerical settings.
Prompt for M2
need help designing an innovative coordinate normalization strategy function im- plemented in PyTTrch to normalize the final negative gap. The input is tensor with shape (batch, num_nodes, 2) and the 'oor' must be tensor with the same shape 'coorl'.
of nodes' coordinates, aiming to maximize
have one algorithm with its code as follows. Algorithm description: (Projection description
Code: (Code)
Please identify the main algorithm parameters and assist me in creating new algorithm that has different parameter settings for the score function provided.
1. First, describe your new algorithm and main steps in one sentence. The description must be within boxed [).
2. Next, implement the following Python function: (Template Projection]
The prompt engineering for normalization evolution adopts a standardized template structure across strategies. The template code for TSP and CVRP builds on the INViT framework (15).
Task Description for TSP
I need help designing innovative coordinate projection strategy function implemented in Py Torch to normalize set of nodes' coordinates, aiming to maximize the final negative gap. The input is tensor with shape (batch, num_nodes, and the "all_co coors' must be a tensor with the same shape as 'coorl'.
24

---

Template Program for TSP
def normalize(coorl: torch. Tensor)
torch. Tensor:
Args:
coor1: coordinates of nodes, shape: (batch, 1+k+1, 2)
Return:
all_coors: a tensor containing normal ized coordinates, same shape as coor1
Note:
First_node, coorl[:, : left_node,
last_node:
[: [-1],]]
left_node is the topk close to the last_node **.
batch_size coor1 shape
all_coors coori
graph all_coors[: 1: :]
min_values torch reshapee wwwree.torncneeeee.e (graph, 1) values, (batch_size, 1, 2)
clo_s all_coors min values translate
ratio_x torch. reshape)
torch.max corch.mx(graph(i,, i, 0], 1) values torch.min minamminngggpppa i, 0], 1).
values,
(-1, 1),
ratio_y torch. torch.reshaper reshape(
maxch.max (graphl:, :, 1], values torch 1], 1).
values, (-1, 1),
ratio torch. max (torch. cat ((ratio_x, ratio_y), 1), 1). values praio 0] all_coors all coors (torch. all_coors (ratio 0, :, :] rescchrreehpperraataaa (batch_size, 1, 1)))
all__cors [ratio == 0, :] + min, valuee [ratio == 0, :, :]
all_coors torch. cwwppcallplllcplaaaaaaaa
1)
return all_coors
Task Description for CVRP
I need to develop a coordinate normalization method for CVRP sequences that preserves critical geometric relationships between nodes while enabling effective neural network processing. The function should take depot/vehicle coordinates (coorl), customer node (coor2), and final stop coordinates (coor3) as PyTorch tensors, maintaining their original shapes. Key objectives are: 1) Establish spatial consistency across batches without distorting relative positions, Use the initial node as an anchor point for stable reference, Prevent information loss from hard clipping while controlling magnitude variance, and 4) Ensure scale-invarians features that help the downstream model generalize across problem sizes. The solution should particularly focus on maintaining directional relationships and proportional distances rather than absolute positional constraints.
25

---

Template Program for CVRP
def normalize(
coor1: Torchr coor2: torch. Tensor, coor3: torch. Tensor
) -> tensor
Args:
coor1: indicate the first node, shape: (batch, 1, 2)
coor2: coordinates of the rest of nodes, shape: (batch, 100, 2)
coor3: coordinate of the last node, shape: (batch, 1, 2)
Return:
coor1: normalized coordinate of the first node, shape: (batch, 1, 2)
coor2: normalized coordinates of the rest of nodes, shape: (batch, left_num, 2)
coor3: normalized coordinate of the last node, shape: (batch, 2)
lengths shape [1], shapee coor3. choe
all_coors torch. cacorr) coor2, coor3), dim-1)
bast_neighbors_x. [ll_coors[; 1:, :]
shape: (batch, 1+neighbor_Et 2)
xy_max torch. march.max((( maaxtlll__eiiii caaatt_neighbora__. dim=1, keepdim=True) values
xy_min = wtt..mmmiatttniigaiaaa
dim=1, keepdim=True) values
shape: (batch, 1, 2)
ratio torch. (xy_max xy_min), dim=-1, keepdim=True) values fratio
shape: (batch, 1, 1)
all_coors torch. cwwp((alllcccollee xy_min) / ratio.expande (xpand 1, 2), 0, 1)
coor1, coor2, coor3 borch.splitall)) lengths, dim=1)
return coorl, coor2, coor3
B.2 EoH Algorithm
The EoH is nopulation-basee framework for LLM-based AHD [52] The algorithm optimizes heuristics by iteratively applying LLM-guided mutation, crossover, and selection operations, enabling the exploration of diverse heuristic designs.
EoH begins by initializing population of N heuristics using LLM, where each heuristic is evaluated on dataset D to compute its fitness value f. In each generation, five evolution strategies (E1, E2, MI, M2, M3) used generate heuristics. For each strategy, N parent heuristies sampled from the current population using rank-based probabilities. LLMs then generate new heuristics by mutating combining features from the parents, guided by the evolution strategy. New candidates evaluated in D, and feasible ones are added to candidate pool after removing duplicates. Finally, the top N heuristics of the expanded pool are selected to form the next generation. This process repeats for N2 generations, eventually returning the heuristic with the highest fitness. The pseudo-code for the EoH is provided in the Algorithm
26

---

Algorithm 2 Evolution of heuristics for automatic heuristic design
1: Input:
2:
Population size Max generations Ng, Evaluation dataset Evaluation function
3: Output:
4: The best found heuristic lt*.
5: Step O: Initialization
6: for j = N do
7: Generate hcuristic h, using initialization prompt.
8: Evaluate hy on to obtain fitness f(D, h2).
9: end for
10: Build initial population Po < (hi. hx].
11: Set O < Po-
12: Step 1: Generation of Heuristics
for 1: Ng do
14: Rank P:-1 by fitness + (fi....,TNI JN
15: for S E (E1, E2, M1, M2, M3) do
16:
for j = 1: N do
Sample parents from P via rank-based sampling.
18:
Generate new heuristic h, based parents using evolution strategies S.
Evaluate h, on the evaluation dataset and obtain the fitness value fo h2).
20:
if h is feasible then
Add hy candidate pool end if
22:
23:
end for
24:
end for
Remove duplicates O.
26: Step 2: Population Management
27: Sort in descending order based on their fitness value.
28: Update P. with the first N heuristics in O.
29:
end for
30: return Heuristic h" with the highest fitness in the final population.
27

---

C TTPL Designed Strategies
C.1
TSP Instances
In this section, we present representative projection strategies optimized by TTPL for TSP and CVRP instances. For TSP, the input is the coordinates of the nodes in the KNN subgraph, and the output is the corresponding transformed coordinates. For CVRP, the inputs consist of the coordinates of the depot, the current node, and the coordinates of the nodes in the KNN subgraph, and the output is the transformed coordinates of these nodes.
For TSPIK instances, TTPL evolves the following projection:
Code 1: Projection designed by TTPL. on TSPIK
def normalize (coor1: torch. >> torch. tensor:
batch_size shore.shapel [o]
alo_s coor1
graph all_coors[:: 1:, :]
Translate to the maximum values max_valuse = torch. resccrrrehpapttorrrd (tarrettaoaggggaaaa.pp.. (graph, dim=1) values, (batch_size, 1, 2)) all_coors max_values all_coors # translate
Calculate ranges ratio_x __x torch, rechapee (torch. max (graph [;, 0], dim=t).values values torch.min graph(:, i, 0], dim=1) values, (-1, 1))
normalization
ratio_y torch reshape (torch. max (graph 11, dim=1) values torch.mint graph[:, :, 1], dim=1) values, (-1, 1))
Find the maximum scale factor ratio torch. max (torch cat ((ratio_x, ratio_y), dim-1), dim-1) values ratio (ratio -- 0]
Avoid division by zero
Normalize ize the coordinates all_ccors_ all_coors / reshape (batch_ size, 1, 1))) all_coors all_coors(ratic [ratio == 0, :] = clors [ratio == 0, i, :] max_ max_valuee vawueallusssse ==
0.
Clip to ensure values are within [0, 1] coors torch.clip(a11) aarc..clipaall_coors. 0, 1)
return all_coors
The corresponding mathematical formulation proceeds as follows. Given input coordinates $ {sp, $1...., .N))....))))...... where 8; E TR2,, with se and sy denoting the component of 8,, the projection process proceeds as follows:
M
max I515N
max & ISIEN
The next step is to establish the maximum coordinate values M (M,r My) as the reference point for transformations, which can be formulated as:
(3,
3 = M S,, Vi (J)...,NN)..
Then, mirrored coordinates are created by reflecting points about the reference point M, ensuring all coordinates lie in the positive quadrant
Tz max 8
1515N N
min 15JSN
f
Fy max ISISN
min
S
ISISN
28

---

Moreover, the coordinate ranges are calculated along both axes to determine the scaling factor
max(r ry) if max(ra, Ty) > 0,
otherwise.
Such that, the maximum range is selected as the normalization factor, with special handling for zero-range edge cases
$
Si + M, vi E to....,,,.. N1}.
8i
81
Finally, coordinates normalized to [0,1] relative the reference point while preserving spatial relationships, and final coordinates are ensured to reside within the unit square through clipping operations, completing the projection
S elipped {(nin(max(57,0) 0), 1), min(max(67, 0).1)) Vi E (o....,N)) N)).
For TSP5K instances, the evolved projection strategy is implemented as:
Code 2: Projection designed by TTPL on TSP5K
def normalize (coor1: torch. tensor) torch. tensor:
batch_size coor1. coori.shape(O))
all_coors coorl graph all_ all_coors[: 1:, :]
Translate by the minimum values in the graph min_values = torch morchapetorcc.milleee all_coors all_coors min values # translate
1) values, (batch_size, 1, 2))
Apply non-linear transformation coors torch, (all(al_oooooo))
Calculate scaling ratios with slight modification ratio_x
www.rc.max (graphh[ 0], 1). values torch mirchmi [:,
i, 0], 1). values, (-1,
ratio_y rorch.reshape
(graphl;; 1), 1). values i, 1], 1) valuue,, (-1, 1))
torch.min min (graph
ratio torch. max (torch. cat cat ((ratio_x, ratio_y), 1), 1) values
Avoid division by zero ratio[ratia == 0] 1 alo_s all_coors / (torch.reshape (ratio, (batch_size, 1, 1)))
coordinates ensure they are clipped within [0, 1] coors torch. torch.clip clip(all_coorss 0, 1)
Post process
return all_coors
The projection process follows these operations:
M min 87. min
15J5N 1515N
S (5r = M, vi (O....,
5 ((ann( Wi (O...., N)}
29

---

The hyperbolic tangent function is employed to compress coordinates into (-1,1) while preserving spatial relationships. The detailed operations are listed follows:
12 = max 5j ISINN
min $ ISISN
Fy max ISISN
8
min 8 ISJSN
max max(T2: ry)
max Ty) > 0,
r
otherwise,
= 8
8;
8;
Vi E (0.
N7
3 (min(maxx( (3) 0), 1), (m, Vi (0.....Ny) N]).
For TSP10K instances, TTPL generates this projection:
Code 3: Projection designed by TTPL on TSP10K
def (cooo
batch_sizz coor1... shape [0] all_coors coor1 clone ()
graph all_ccors 1:, :]
Step Calculate midpoints for translation
midpoints (torch. (torch.max (graph, 1). values + morch.min(graph. 1). values)
midpoints forch.reshape (midpoints, (batch_size, 1, 2)) all_cooms all_coors midpoints translate
Step Calculate the new range after translation
range_* x torch. rewhape (trrharchhhtttrrrcmmmeee mttrrch.mxxgrraphI. :, 0], 1). vavuee torch. minn [:, :, 0], 1) values, (-1, 1))
range_y corch.reshar (torch. (torch.max (graphli, 1], 1) values torch micch.inngggaphllf
:. 1]. 1). values, (-1, 1))
range_val torch max (torch, ((range_x, range_y), 1), 1) values range val [range_val val 0] 1 Prevent division by zero
Step 3: Scale coordinates
all_ coorscors- all_coors (torch.reshape
(range_val, (eaneeaaaaraegge.aaal bbatch_size, ))
Step 4: Shift values to center in [o, 1]
all_coors (all_coors 0.5)
Step Clip the values [0, 1] 0, all_coors torch,
return _cl_s
first calculates the centroid of the input coordinates using the average of extreme values:
max ISiSN
8 +
min
s
Sy
+
min ! ISJEN
ISJEN
IISN
M
2
2
30

---

Then, the projection is mathematically written below:
5 8i 8 8; M, Vi ( N}},
max S - min $j
ISINN
ISIS
max " min *
ISJEN 1SJSN
max Tas Ty) max(r.: ryy > 0,
otherwise,
$ 8
ViE 10, NO.
3 S 0.5),
Satipped (minn(max(3) 0), 1), (), vi NJ).
C.2
CVRP Instances
For CVRP instances, TTPI. develops specialized strategies to handle depot-custommer relationships The CVRPIK projection strategy is implemented via:
Code 4: Projection designed by TTPL on CVRPIK
def normalize (coor1: forch.Tenson coor2: torch. Tensor, coor3: torch. Tensor) ->
torch. Tensor:
lengths [coor1. shape(1) coor2. shape [1], shape [i]] all_coors coors torch. crrcch.ct((ccor,,, coor2, coor3), dim=1)
Calculate the relative vectors relative_vectors all_coors coor1
Compute the magnitudes of the vectors magnitudes porch.norm(relattoo vectors, dim=-1, keepdim-True)
Avoid division by zero magnitudes [magnitudes == 0] =
vectors unit_vecter vectors relative_vectors / magnitudes
Normalize the vectors
Scale unit vectors by the normalized magnitudes normalized_ vectors unit_ miitorsctors (magnitudes magnitudes magnitudes.maxxdmmee max keepdim= True) values)
Combine normalized vectors with the anchor point normalized coors coor1 normaliized_vectore
coor1, coor2, coor3 torch split (nonaaiiitt, lengths, dim=1)
return coor1, coor2, coor3
The projection first integrates all coordinates into unified set with depot so as the reference origin
U; 8; 80,
Vi E (O....,
Secondly, position vectors computed relative to the depot, establishing translation invariant representations
172
of + up² 0, otherwise.
|| =
1
31

---

Thirdly, vector magnitudes are computed with zero-division protection to ensure numerical stability
|
0
max OSISN
poyl
Furthermore, magnitude scaling is performed relative to the maximum vector length
5 S0 Uz.
Then, absolute coordinates are reconstructed while maintaining spatial relationships
3 = (oo). 3 = (81, N1-
S = [8N).
Finally, given coordinate sets Sy {ua} (depot), S₁ (.1...., - }. and S {SN) where 8t E IR? the normalized coordinates Sy, Sk. St are computed through:
= S3 U U.: = {80, ,
For CVRP5K instances, the evolved projection strategy is implemented as:
Code 5: Projection designed by TTPL. on CVRP5K
def normalize (coor1: torch. Tensor, coor2: torch. Tensor, coor3: torch, Tensor) -> torch. Tensor:
lengths @horr.sshape [1], coor2. [1]] coor3. shape [1]] all_coors coors (acorr, coor2, coor3), dim=1)
Get anchor point (coor1) anchor coor1
Translate coordinates based the anchor translated_cooors all_coors anchor
Calculate distances to the anchor point distances torch. norm (tramsttaattee p=2, dim=-1, keepdim=True)
Find the furthest distance for scaling sitthest_distance, distances caaances.mar max (dim=1, keepdin-True) scating_factor torch. sqrt (farthest, (farthest_distance)
scaling_factan lscallllnaaatttooooooooooo
0]
Prevent division by zero
Normalize the coordinates using the scaling factor
normalized_coors translated_coore / scaling factor wwwp:e...ator..aaaaooooaa as (translated_coors)
Combine back with the anchor cormarszed_coors +- anchor
Split back to original coordinates coor1, coor2, coor3 torch (trrhhaeplitnooraaiieeee lengths, dim=1)
return coor1, coor2, coor3
32

---

The projection steps are formalized by:
1//
81 80,
ViE (O....,,)}
|0:
||
of² + og?
max OSISN
if OSISN
118x
|0 > 0,
mmax
otherwise,
Unax
8; 80 + Us.
S (80), S: = (51.... 8N 1)
3:= {8N),
S S Sk US: {so, $1.............. .I....,8N]
For CVRPIOK instances, TTPL generates this projection:
Code 6: Projection designed by TTPL on CVRPIOK
normalize (coor1: Tensor, coor2: Tensor, coor3; torch, Tensor) torch. Tensor: Tensor:
lengths (coori.shapee [1], coor2. shape [1], coor3. shape [1]] coors torch. Carch.cat((coot.) coor2, coor3), dim=1)
Centering the coordinates around the first node center coor1 squeeze coor1. shape: (batch, 2) relative_coors = all_coors center. unsqueeze shape: (batch, 1 k, 2)
Calculate distances from the first node distances torch. norm dim=-1, keepdim=True) k, 1)
shape (batch,
Apply non-linear transformation to the distances (e.g., exponential scaling) diieforreedddsttnceee.ee.
transformed distances torch.exp (diistannee)) - 1 shape: (batch, 1 + k, 1)
Scale transformed distances to [0, 1]
max_ distance forch.max(transforree distancess,, dim=1, keepdim=True) values max_distance tmax_distance 0] 1 Prevent division by zero normalized distances transformed distances max_distance # shape: (batch, 1 k, 1)
Maintain direction by re-constructing relative coordinates
direction relative_coors (distances + 1e-6) # shape: (batch, + k, 2) vormalized_coors normalized distances * direction # shape (batch, 1 + k, 2)
all_ normalized_coorz coora center unsqueeze (1) position
Translate back original
coor1, coor2, coor3 torch sal..ssspl(aalllcooo lengths, dim=1)
return coorl, coor2, coor3
33

---

The projection process follows these operations:
U/ = 81 80 Vi N),
|/: ||
vof² + n
elloull 1,
max By USJSN
max Bg > 0, OSJSN
Umax
otherwise,
V/3
1/3
Umax
U/
V
0 Umax
||0:|| 1e6'
8: Sg + 0,
f {5o},
S3. {81
&N 1.
3 [3N),
S Sy U Sp U S = {su, ,
34

---

D Experiment Details
D.1 TSPLIB and CVRPLIB Results
We evaluate the proposed method in four benchmark scenarios: TSPLIB [59] and CVRPLib [60 instances with comparisons both greedy and post-search frameworks. We compare our method against five baselines: INVIT (1S), SIGD [62]. BQ (42, LEHD [18] and GLOP [3]. For TSPLIB, all experiments are conducted on large-scale instances ranging from 1,000 85,900 nodes assess scalability and generalization.
As shown in the Table. 7 our method achieves 3.88% average optimality gap across all 33 instances, significantly reducing the optimality gap by 64.8 44.86% 92.02%, 94.00%, and 78. 10% compared with INVIT, SIGD greedy, BQ greedy, and LEHD greedy.
Table 7: Optimality gaps of greedy-based NCO methods on TSPLib instances. "OOM" signifies out-of-memory failures. Solved# and average gaps are summarized at the bottom.
Instance
Scale
INVIT
SIGD greedy
BQ greedy
LEHD greedy
Ours
dsj1000
1,000
9.20%
7.82%
6.96%
8.3 1%3%%
2.40 %
pr1002
1,002
16.43%
2.95%
3.35%
4.44%
0.90%
u1060
1,060
12.29%
7.60%
10.72%
10.00%
1.22%
vm1084
1,084
10.91%
3.38%
4.41%
5.42%
4.32%
pcbl 173
1,173
8.67%
4.32%
5.61%
8.01% %
2.25 %
d1291
1,291
22.37%
4.50%
10.93%
14.13%
3.59%
rl1304
1,304
8.90%
3.18%
8.48%
8.14%
3.76%
r11323
1,323
17.02%
3.64%
5.44%
9.26%
5.56%
nrw1379
1,379
5.25%
27.91%
18.96%
15.49%
1.00 %
fl1400
1,400
18.30%
24.87%
16.73%
18.80%
7.91 %
ul432
1,432
6.16%
2.79%
4.65%
7.96%
2.81%
fl1577
1,577
12.63%
22.37%
19.95%
14.68%
4.97%
d1655
1,655
12.81%
14.55%
12.53%
13.89%
5.57% %
vm1748
1,748
16.27%
9.95%
7.71%
10.10%
2.37
u1817
1,817
7.31%
7.29%
8.40%
10.32%
4.72%
rl1 11889
1,889
10.44%
7.30%
7.93%
7.49%
5.70%
d2103
2,103
16.79%
10.46%
16.48%
14.57%
5.78% %
u2152
2,152
10.38%
10.22%
11.56%
12.65%
4.01 %
u2319
2,319
0.98%
3.73%
4.33%
4.18%
0.31% %
pr2392
2,392
8.29%
8.88%
13.96%
12.33%
3.53%
pcb3038
3,038
6.85%
11.01%
17.33%
13.44%
3.55%
f13795
3,795
18.75%
57.46%
30.97%
13.55%
9.29%
fnl4461
4,461
7.32%
28.33%
20.35%
19.05% %
2.16%
r15915
5,915
14.02%
44.31%
26.77%
24.17%
4.48%
r15934
5,934
12.91%
53.73%
33.19%
24.11 %
4.26%
pla7397
7.397
9,45%
90.16%
69.34%
40.94%
5.42%
1111849
11,849
12.71%
105.26%
46.65%
38.04%
4.86%
usa13509
13,509
13.44%
525.78%
676.67%
71.10%
4.55%
brd14051
14,051
9.31%
138.65%
145.41 %
41.22%
3.98%
d15112 12
15,112
7.24%
145.56%
172.38%
35.82%
2.09%
d18512
18,512
6.62%
119.58%
126.51%
OOM
1.97%
pla33810
33,810
7.04%
OOM
504.13%
OOM
5.34%
pla85900
85,900
7.21%
OOM
OOM
OOM
3.54%
Sloved#
33/33
31/33
32/33
30/33
33/33
Avg.gap
11.04%
48.63%
64.65%
17.72%
3.88 %
35

---

As shown in the Table 8 our method achieves 1.37% average optimality gap across all 33 TSPLIB instances under the post-seane search framework, reducing the gap by 88.03%, 89.43%, 81.41%, 41,, and 75.09% compared to SIGD bs16, BQ bs16, LEHD RRC1000, and GLOP, respectively.
Table 8: Optimality gaps of post-search-basee NCO methods on TSPLIB instances.
Instance
Scale
SIGD bs16
BQ bs16
LEHD RRC1000
GLOP
Ours RRC1000
dsj1000
1,000
9.27%
4.35%
2.45%
2.45%
0.63 %
pr1002
1,002
2.25%
2.04%
1.08%
3.02%
0.14 %
u1060
1,060
5.45%
5.82%
2.79%
2.40%
0.27 %
vm1084
1,084
6.68%
5.48%
1.47%
3.83%
0.24 %
peb1173
1,173
2.61%
4.45%
2.99%
5.92%
0.63 %
d1291
1,291
6.85%
7.38%
2.88%
5.78%
1.16% %
r11304
1,304
3.64%
6.30%
3.14%
8.02%
0.12% %
rl1323
1,323
2.24%
4.51%
1.16%
6,27%
0.51 %
nrw
1,379
17.82%
13.23%
8.34%
3.34%
0.39 %
fl1400
1,400
33.75%
37.48%
2.96%
2.15%
1.14% %
u1432
1,432
2.10%
4.25%
2.24%
3.40%
0.67 %
111577
1,577
33.27%
18.32%
3.81%
5.85%
1.19%
d1655
1,655
12.98%
10.20%
5,09%
5.33%
2.36% %
vm1748
1,748
4.59%
6.42%
3.36%
3.75%
0.39 %
u1817
1,817
5.91%
6.07%
4.83%
6.26%
2.61 %
rl 11889
1,889
7.39%
7.24%
3.17%
7.06%
1.25% %
d2103
2,103
12.66%
15.46%
2.14%
9.58%
0.13%
u2152
2,152
7.11%
7.69%
6.22%
7.32%
1.77%
u2319
2,319
1.42%
3.17%
1.47%
1.29%
0.19%
pr2392
2,392
5.68%
10.53%
5.63%
5.20%
0.76%
peb3038
3,038
6.56%
11.51%
7.49%
5.28%
1.32%
113795
3,795
53.43%
38.33%
6.85%
7.45%
5.05%
fnl4461
4,461
19.22%
14.68%
10.37%
4.47%
1.10% %
r15915
5,915
OOM
19.58%
12.38%
10.35%
1.76%
r15934
5,934
OOM
24.53%
11.94%
10.28%
1.99 %
pla7397
7,397
OOM
47.63%
15.31%
5,94%
2.68% %
rll 1849
11,849
OOM
OOM
18.19%
8.69%
2.48%
usal 1309
13,509
OOM
OOM
31.37%
5.32%
1.85%
brd 1
14,051
OOM
OOM
21.19%
4.73%
2.47% %
d15112
15,112
OOM
OOM
18.83%
4.67%
1.06 %
d18512
18,512
OOM
OOM
OOM
4.98%
1.15%
p1a33810
33,810
OOM
OOM
OOM
OOM
3.37 %
pla85900
85,900
OOM
OOM
OOM
OOM
2.43%
Sloved#
23/33
26/33
30/33
31/33
33/33
Avg.gap
11.43%
12.95%
7.37%
5.50%
1.37 %
36

---

For CVRPLIB, we evaluate both greedy and post-search frameworks on large-scale instances ranging from 1,000 30,000 nodes. As shown in the Table. a Table. [0 our method achieves 10.97% and 7.34% average optimality gaps in the greedy and post-search frameworks, respectively, outperforming all baselines both settings.
Table 9: Optimality gaps of greedy-based NCO methods CVRPLIB instances.
Instance
Scale
INVIT
SIGD greedy
BQ greedy
LEHD greedy
Ours
X-n1001-k43
1,000
12.60%
8.02%
4.99%
7.57%
4.95%
Li_30
1,040
9.12%
9.81%
10.62%
12.54%
12.84%
Li_31
1,120
12.42%
12.88%
12.93%
4.95% %
16.12%
Li_32
1,200
9.90%
13.61%
13.48%
7.68% %
11.30%
Leuvenl
3,000
13.71%
16.19%
18.53%
16.60%
5.69%
Leuven2
4,000
26.08%
25.64%
30.70%
34.85%
14.99%
Antwerpl
6,000
15.40%
13.98%
16.48%
14.66%
5.76%
Antwerp2
7,000
27.75%
17.72%
27.67%
22.77%
11.66%
Ghentl
10,000
15.87%
24.22%
25.36%
27.23%
5.73%
Ghent2
11,000
30.78%
28.09%
54.04%
38.36%
15.56%
Brussels1
15,000
18.09%
25.48%
35.70%
OOM
6.80%
Brussels2
16,000
32.08%
38.32%
50.90%
OOM
15.38%
Flanders1
20,000
23.41%
43.95%
37.51%
OOM
7.35%
Flanders2
30,000
39.60%
136.89%
110.09%
OOM
19.43%
Sloved#
14/14
14/14
14/14
10/14
14/14
Avg.gap
20.49%
29.63%
32.07%
18.72%
10.97%
Table 10: Optimality gaps of post-search-based NCO methods on CVRPLIB instances.
Instance
Scale
SIGD bsl6
BQ bs16
LEHD RRC1000
GLOP
Ours RRC1000
X-n1001-k43
1,000
5.68%
3.07%
2.92%
16.78%
3.52%
Li_30
1,040
9.04%
11.86%
3.28%
11.10%
4.46%
Li_31
1,120
11.53%
8.18%
3.47%
17.06%
2.73 %
Li
1,200
9.40%
7.43%
1.45%
9.44%
3.41% %
Leuvenl
3,000
14.80%
15.39%
10.71%
14.95%
3.54
Leuven2
4,000
22.82%
25.69%
21.22%
16.54%
10.61 %
Antwerpl
6,000
11.66%
13.64%
8.91%
19.08%
4.44%
Antwerp2
7,000
16.27%
26.09%
15.42%
17.72%
8.91 %
Ghentl
10,000
21.36%
OOM
17.28%
18.28%
4.89 %
Ghent2
11,000
27.71%
OOM
25.77%
16.45%
13.39
Brussels1
15,000
23.12%
OOM
OOM
26.17%
6.26%
Brussels2
16,000
34.87%
OOM
OOM
17.56%
13.71
Flanders1
20,000
40.92%
OOM
OOM
24.02%
6.90%
Flanders2
30,000
129.81%
OOM
OOM
25.42%
18.18%
Sloved#
14/14
8/14
10/14
14/14
14/14
Avg.gap
27.07%
13.92%
11.04%
17.90%
7.50%
37

---

D.2 Result in CrossDistributions
To evaluate robustness against distribution shifts, we tested TTPL on TSP and CVRP instances under three distinct spatial distributions (Clustered, Explosion, and Implosion) [15] on scales from 1,000 to 100,000 nodes.
Table 11: Solution length and runtimes for TSP and CVRP instances under Clustered, Explosion, and Implosion distributions.
Clustered
Method
TSPIK
TSPSK
TSPIOK
TSP50K
TSP100K
w/o prnj
15.3
0.1s
57.1
277.4
27.66x
seed proj
14.5
0.1s
29.8
1.5s
41.4
2.95
91.0
14.66
124.9
29.6s
TTPL
14.4
0.5s
29.6
3.2s
41.3
6.46
90.5
33.9s
123.9
1.1m
Explosion
TSPIK
TSPSK
TSPIOK
TSP50K
TSP100K
wlo proj
17.5
0.1s
39.0
55.6
2.66
13.56
269.5
27.6s
seed proj
16.7
0.1s
34.1
1.5s
43.1
2.95
88.4
14.6s
111.8
29.56
TTPL
16.4
0.5s
33,9
3.2s
42.4
6.6s
87,9
34.1s
110.9
1.1m
Implosion
TSPIK
TSPSK
TSPIOK
TSP50K
TSP100K
wlo proj
21.1
0.1s
75.9
2.66
212.0
13.56
428.
27.5s
seed proj
20.9
0.1%
46.7
1.5s
64.6
2.9%
141.6
14.5%
198.4
29.4s
TTPL
20.7
0.5s
46.7
3.2s
64.2
6.66
140.6
33.8s
196.8
1.1m
Clustered
Method
CVRP-IK
CVRP-5K
CVRP- 10K
CVRP-50K
CVRP-100K
w/o
31.4
0.1s
87.4
1.7s
112.6
3.2s
433.6
16.5s
831.9
36.0s
seed proj
37.4
0.1s
90.3
1.7s
109.1
3.46
217.7
17.2s
373.7
40.7s
TTPL.
384.6
Explosion
CVRP-IK
CVRP-5K
CVRP-10K
CVRP-50K
CVRP-100K
wlo proj
30,0
0.1s
70.2
1.6s
90.3
3.2s
401.3
16.5s
744.9
35.9s
seed proj
39.3
0.1s
78.4
1.7g
94.8
3.38
203.7
17.2s
322.6
41.0s
TTPL
29.6
0.5s
75.5
294.4
1.4m
Implosion
CVRP-IK
CVRP-5K
CVRP- 10K
CVRP-50K
CVRP-100K
wlo proj
39,0
0.1s
102.6
1.68
131.1
3.2s
402.4
16.5s
808.7
35.9
seed proj
51.5
0.1s
124.3
1.78
149.6
3.38
325.2
17.2s
549.7
41.7s
TTPL
38.6
0.5s
98.2
3.8s
120.7
299.0
542.3
1.4m
E Additional Experiment Analysis
E.1
Adaptability of TTPL
To further validate the effecttivneess of TTPL framework, utilize proposed framework different base models. Specifically, we compare POMO (7]. LEHD [8], BQ [42), and SIGD 62). four constructive models, with and without TTPL projection. The test instances set to TSP1K/5K/108 with the same settings as the previous. The results are shown the Table. [2
E.2 TTPL Time Usage
To quantify the extra computational overhead introduced by the TTPL, report the training time used for TTPL to search for a projection strategy in Table I3
E.3 Results from Other LIMMs
To investigate the robustness of TTPL to different LLMs, we test our framework with several state-of- the-art L.LMs, including Claude, Gemini, DeepSeek, and Qwen. The experimental results (Table (4) indicate that the choice of LLM does not significantly influence projection performance
38

---

Table 12: Results of different base models with and w/o TTPL
TSPIK Obj.(Gap)
TSP5K (bj.(Gap)
TSPI0K
Method
(bj.(Gap)
POMO greedy
33.18 (43.51%)
94.04 (84.50%)
150.64 (109.86%
POMO-TTPL
29.68 (28.37% %))
71.76 (40.79%) %)
101.8 (41.82% %
SIGD greedy
23.57(1.96%
57.19 (12.20%)
93.80 (30.68%)
SIGD-TTPL
23.86 (3.20%)
56.05 (9.97 %
80.44 (12.06 %)
BQ greedy
23.65 (2.30%)
58.27 (14.31 %)
89.73 (25.02 (5.0%%)
BQ-TTPL
23.58 (1.99%)
56.47
81.48 (13.51 %)
LEHD greedy
23.84 (3.1 1%)
58.85 (15 (6..
91.33 (27 24%)
LEHD-TTPL
23.73 (2.65 %
52.63 (3.25%) %)
74.39 (3.63%)
Table 13: Time used for TTPL learn projection strategies on different scales
TSPIK time
TSP5K time
TSPI0K time
Mehod
TTPL
5.5h
9.6h
19.9h
Table 14: Result of TTPL using different LLMs
TSPIK Obj.
TSP5K Obj.
TSPIOK
Method
Obj.
TTPL-Claud
23.80
52.79
74.48
TTPL- -eepeeepSeek
23.67
52.39
74.00
TTPL-Gemine
23.76
53.71
76.42
TTPL-Qwen
23.75
52.73
74.25
TIPL-GGPT44-mini
23.73
52.63
74.39
39

---

Solution Visualization
F. Solution Visualizations of Cross-distribution TSP Instances
(a) Optimal solution.
(b) TTPL aug RRC1000 (gap: 1.11%).
Figure 3: The solution visualizations of TSP5K instance with uniform distribution.
(a) Optimal solution.
(b) TTPL aug RRC1000 (gap: 1.10%).
Figure 4: The solution visualizations TSP5K instance with cluster distribution.
40

---

(a) Optimal solution.
(b) TTPL aug RRCI000 (gap: 0.94%).
Figure 5: The solution visualizations of a TSP5K instance with explosion distribution.
(a) Optimal solution.
(b) TTPL aug RRC1000 (gap: 1.56%).
Figure 6: The solution visualizations of a TSP5K instance with implosion distribution.
41

---

F22 Solution Visualizations of Large-scale TSPLIB Instances
(a) Instance r11304 (scale: 1304, gap: 0. 0.12%.)
Instance d2103 (scale: 2103, gap: 0.13%.)
(c) Instance fnl4461 (scale: 4461, gap: 1.10%.) (d) Instance d15112 (scale: 15112, gap: 1.06%..
Figure The solution visualizations of TSPLIB instances with different scales, the solutions are all generated by TTPL aug RRC1000.
42

---

G License
We list the license of the code and the dataset in the Table. 15
Table 15: summary of licenses
Type
LKHB
Code
Available for academic research use
HGS
Code
https://gilllbb
MIT License
Liceuse
POMO 7
Code
http:://itahh..om/y.. www.:/POOOOOO
MIT License
F1D
Code
MIT License
4Q
Code
BY-NC-SA 4.0
GLOM
Code
https://gitlll http://wwwwoomeeeeeeecc......
MIT Liceuse
H-TSP
Code
https///gibbb..com com com//cannngg compLaaningggpppimazaiii Dpttii/aatiin-UUST// HUST/H-TSP
MIT License
DIFUSCO
Code
htips:/gitbbbb.o http:/bbbom//weeeeeeeee wtwm///waaaSSS//D/USSS/S
MIT Liceuse
INViT
Code
htips//giibab.cc Kussmigaok--Utaba/NNN
Available
BLG 14
Code
MIT License
SIGD x
Code
Available for academic research
Code
hrips wttp://hw.ccoooloooooooeeeeeeeee
LLMHAD
Code
htips//gitbbb... Caapaaa.co////iiiiiiieee Opimm-CCiUUULLMAAAA
MIT License
69
Daraset
http://comop ii uni heidelberg deloottsswree//PP1115//
Available for any non-commercial use
CVRPLIN
http///ppp go gos www..ii.....uuubeeeee pue-r
Available for academic
H Broader Impacts
This work advances neural combinatorial optimization through the proposed TTPL framework and MVFD technique, critically enhancing solution efficiency for large-scale Vehicle Routing Problems (VRPs). These developments are expected to inspire further investigations into novel neural methods for complex, lcrge-scale routing tasks. We foresee negative societal impacts from this research.
43


Reviews:
[{"review_id": "rmZZJarfsJ", "reviewer": "Reviewer_gE2W", "summary": "The paper proposes a framework to use LLMs to generate projection  strategies  that enhance model generalization for solving optimization problems.", "questions": "1. What are geometric transformations in Multi-View Decision Fusion?\n2. Is the projection strategy a normalization operation?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\nThe proposed framework is interesting and seems to work well in practice.\n\n**Weaknesses:**\n\n1. The study lacks substantive novelty, with the core value of the methodology appearing to be primarily attributable to EoH [1].\n2. The idea of mimicking evolutionary computation via LLMs is not new. In fact, most (all?) crossover and mutation operators are from EoH.\n3. It remains unclear what specifically constitutes the NCO model in fitness evaluation and whether the selection thereof significantly impacts the results.\n4. The geometric transformations in Multi-View Decision Fusion are not clearly described.\n5. The adoption of LEHD [2] as the base model, while employing POMO and other NCO methods as baselines, appears somewhat inappropriate in the experimental design.\n\n[1] Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model, ICML 2024.\n\n[2] Neural combinatorial optimization with heavy decoder: Toward large scale generalization, NeurIPS 2023.", "was_revised": true, "final_justification": "Although there are still some issues, I am inclined to accept this paper.", "rebuttal": "Dear reviewer gE2W\n\nThank you very much for your time and effort in reviewing our work. We are glad to know you find our proposed framework interesting and work well. We address your concerns as follows.\n\n> **W1. The study lacks substantive novelty, with the core value of the methodology appearing to be primarily attributable to EoH.**\n\n> **W2. The idea of mimicking evolutionary computation via LLMs is not new. In fact, most (all?) crossover and mutation operators are from EoH.**\n\n**A1:** Thanks very much for your comments. We would like to deal with your concerns from the following two aspects.\n\n**1. Novelty**\n\nWe respectfully clarify that this work focuses on enhancing the large-scale generalization ability of NCO methods. Our novelty lies in the introduction of Test-Time Projection Learning (TTPL), a light-weight and universal strategy that can significantly enhance the NCO method's generalization performance. \nUnlike most existing works that focus on modifying model architectures or training paradigms [5-8], our TTPL framework takes a **data-centric** approach. It only operates at the inference stage by aligning the distributions of testing and training data. \n\nTo demonstrate its universality across models, we have integrated TTPL into four different models: POMO [4], SIGD [7], BQ [6], and LEHD [5]. As shown in Table 3 (**A4**), the model equipped with TTPL remarkably outperforms the original version on most test instances. \nIn addition, we would like to emphasize the generalization performance improvements that TTPL brings to NCO methods in large-scale scenarios. As reported in our main experiments (**Table 2, page 7**),  LEHD using the projection learned from TTPL achieves improvements of 14.79\\%, 78.98\\%, and 86.67\\% on TSP instances of sizes 1K, 5K, and 10K, respectively. It is worth noting that it surpasses existing methods and obtains the SOTA results.\n\n**2. Independence on LLM-AHD methods**\n\nIn this work, we do not intend to propose a new LLM-AHD method, but rather aim to employ LLM-AHD for our TTPL implementation. Our proposed TTPL framework is **independent of any specific LLM-AHD methods**. We empirically show that it is a replaceable component within our TTPL framework. To demonstrate it, we replace EoH with two alternative LLM-AHD methods, Funsearch [2] and ReEvo [3], to generate new projection strategies for the LEHD. As presented in Table 1, both resulting projections outperform the original LEHD, confirming the independence of TTPL on the LLM-AHD methods.\n\nTable 1: Results of TTPL using different LLM-AHD methods on TSP1K instances\n|Method|Obj.|\n|-|-|\n|w/o TTPL| 24.16|\n|TTPL-EoH|23.73|\n|TTPL-FunSearch|23.81|\n|TTPL-ReEvo|23.74|\n\n> **W3. It remains unclear what specifically constitutes the NCO model in fitness evaluation and whether the selection thereof significantly impacts the results.**\n\n**A2:** Thank you for your raising this important concern. We would like to answer your comments in two parts.\n\n**Explanation of fitness evaluation**\n\nIn principle, the NCO model within the fitness evaluation phase can be any base model capable of solving the routing problem (e.g., TSP, CVRP). In the specific experiments presented in our study, we employed LEHD as the base model. The evaluation process is described below. First, TTPL proposes a candidate projection strategy. The strategy is applied to a test instance to align its data distribution with the training instances. The aligned test instance is then fed into the chosen base model (e.g., LEHD), which yields a solution. Finally, the quality of this solution is returned to TTPL as the fitness value for the corresponding projection strategy.\n\n**Sensitivity on different base models**\n\nTo verify the impact of the selection of the base model, we adopt TTPL to two additional NCO models, namely POMO and BQ, as base models. The models together with developed TTPL strategies are then tested on the TSP1K instances, and the results are summarized in Table below. It demonstrates that the effectiveness of TTPL consistently exists across different base models\n\nTable 2: Results of TTPL using different base models on TSP1K instances\n||TTPL-LEHD|TTPL-POMO|TTPL-BQ|\n|-|-|-|-|\n|base model w/o proj|24.16|33.18|23.65|\n|base model with proj|**23.73**|**28.75**|**23.57**|\n\n> **W4. The geometric transformations in Multi-View Decision Fusion are not clearly described.**\n> **Q1. What are geometric transformations in Multi-View Decision Fusion?**\n\n**A3:** We sincerely apologize for the lack of clarity in our original description of the geometric transformations and thank you for pointing this out, providing us with the opportunity to elaborate on the key component of our method. We will add a detailed description to our main text in the future.\n\nThe geometric transformations used in our Multi-View Decision Fusion (MVDF) module are specifically a series of **rotational augmentation**, which is inspired by the augmentation mechanism introduced in POMO [4]. In particular, for a given test instance, we generate a projected K-Nearest-Neighbors (KNN) subgraph via the projection obtained in the TTPL. Then, the MVDF rotates the subgraph around its center by angles of $45^{\\circ},90^{\\circ},135^{\\circ},180^{\\circ},225^{\\circ},270^{\\circ},$ and $315^{\\circ}$. Including the original subgraph, this process yields a total of **8 distinct geometric views**. By incorporating these views, MVDF is capable of enhancing the robustness of the final decision.\n\n> **W5. The adoption of LEHD [2] as the base model, while employing POMO and other NCO methods as baselines, appears somewhat inappropriate in the experimental design.**\n\n**A4:**  Thanks for your constructive comments. Following your insightful suggestion, we provide direct comparisons for NCO models, evaluating their performance both with and without the TTPL projection strategy. Specifically, we compare POMO [2], LEHD [5], BQ [6], and SIGD [7], four **constructive** models, with and without TTPL projection. The test instances are set to TSP1K/5K/10K with the same settings as in our original paper. The results are shown in the Table below\n\nTable 3: Results of different base models with and w/o TTPL\n|Method|TSP1K|TSP5K|TSP10K|\n|-|-|-|-|\n|POMO greedy|33.18(30.32\\%)|94.04(45.79\\%)|150.64(52.35\\%)|\n|POMO-TTPL|**29.68(22.1\\%)**|**71.76(28.97\\%)**|**101.8(29.49\\%)**|\n|SIGD greedy|**23.57(1.96\\%)**|57.19(12.20\\%)|93.80(30.68\\%)|\n|SIGD-TTPL|23.86(3.1\\%)|**56.05(9.06\\%)**|**80.44(10.77\\%)**|\n|BQ greedy|23.65(2.30\\%)|58.27(14.31\\%)|89.73(25.02\\%)|\n|BQ-TTPL|**23.58(1.95\\%)**|**56.47(9.74\\%)**|**81.48(11.9\\%)**|\n|LEHD greedy|23.84(3.11\\%)|58.85(15.46\\%)|91.33(27.24\\%)|\n|LEHD-TTPL|**23.73(2.65\\%)**|**52.63(3.25\\%)**|**74.39(3.63\\%)**|\n\nIt clearly indicates that the TTPL consistently improves the performance of all base models. For every model and dataset except SIGD on TSP1K, the TTPL variant achieves a lower optimal gap compared to its original counterpart.\n\n> **Q2. Is the projection strategy a normalization operation?**\n\n**A5:** Thanks very much for your question, which allows us to clarify the relationship between the projection strategy and the normalization operation. **In our study, normalization is a subset of the projection strategy**. To elaborate on the distinction, **projection strategy**: Its goal is to align the distribution of an input instance with a target distribution. This mapping is highly flexible and can encompass a set of transformations, including scaling and rotation. **Normalization operation**: it involves **scaling** an instance's coordinates to fit within a unit interval (e.g., [0, 1]). This is a fixed operation that does not include transformations like rotation or translation. We are more than willing to present further clarification about the difference between the projection strategy and the normalization operation upon any specific remaining questions.\n\nThank you for your time and effort dedicated to reviewing our work. We sincerely hope that our responses have effectively addressed your concerns.\n\n**Reference**\n\n[1] Liu, F., Tong, X., Yuan, M., Lin, X., Luo, F., Wang, Z., ... \\& Zhang, Q. (2024). Evolution of Heuristics: Towards efficient automatic algorithm design using large language model. arXiv preprint arXiv:2401.02051. \n\n[2] Romera-Paredes, B., Barekatain, M., Novikov, A., Balog, M., Kumar, M. P., Dupont, E., ... \\& Fawzi, A. (2024). Mathematical discoveries from program search with large language models. Nature, 625(7995), 468-475. \n\n[3] Ye, H., Wang, J., Cao, Z., Berto, F., Hua, C., Kim, H., ... \\& Song, G. (2024). ReEvo: Large language models as hyper-heuristics with reflective evolution. Advances in neural information processing systems, 37, 43571-43608. \n\n[4] Kwon, Y. D., Choo, J., Kim, B., Yoon, I., Gwon, Y., \\& Min, S. (2020). POMO: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33, 21188-21198. \n\n[5] Luo, F., Lin, X., Liu, F., Zhang, Q., \\& Wang, Z. (2023). Neural combinatorial optimization with heavy decoder: Toward large scale generalization. Advances in Neural Information Processing Systems, 36, 8845-8864. \n\n[6] Drakulic, D., Michel, S., Mai, F., Sors, A., \\& Andreoli, J. M. (2023). BQ-NCO: Bisimulation quotienting for efficient neural combinatorial optimization. Advances in Neural Information Processing Systems, 36, 77416-77429. \n\n[7] Pirnay, J., \\& Grimm, D. G. (2024). Self-improvement for neural combinatorial optimization: Sample without replacement, but improvement. arXiv preprint arXiv:2403.15180. \n\n[8] Fang, H., Song, Z., Weng, P., \\& Ban, Y. (2024). INViT: A generalizable routing problem solver with invariant nested view transformer. arXiv preprint arXiv:2402.02317."}, {"review_id": "Vg0L7DFpWR", "reviewer": "Reviewer_SjSP", "summary": "The paper proposes Test-Time Projection Learning (TTPL), an LLM-driven evolutionary framework that automatically designs geometric projection functions to reconcile the distribution gap between small-scale training instances (≈100 nodes) and large-scale inference instances (up to 100K nodes) in Vehicle Routing Problems (VRPs). A complementary Multi-View Decision Fusion (MVDF) module ensembles multiple transformed views of each K-nearest-neighbour sub-graph to further stabilise node selection. According to the manuscript, the combined TTPL-MVDF system reduces optimality gaps on large-scale Traveling Salesman Problem (TSP) and Capacitated VRP (CVRP) benchmarks by 60~88% relative to the best competing constructive methods.", "questions": "1. It is recommended to provide a more detailed theoretical explanation or interpretability experiment of why the proposed projection strategy improves model generalization in large-scale VRPs.\n2. It is suggested to report mean ±σ over multiple random seeds or instance batches, and add paired-t confidence intervals for key gaps.\n3. The loss functions and the evaluation metrics (e.g., RWD) used in this work needs to be discussed in detail in the main text.\n4. It could be helpful if the author(s) explore ways to speed up the convergence of the LLM optimization phase to improve the practical applicability of TTPL in time-sensitive settings.\n5. Can the authors elaborate on how their LLM-driven method compares to other projection methods (e.g., INViT, LEHD) in terms of computational efficiency, especially for real-time large-scale problems?\n6. Given that TTPL relies on prompt-based LLM outputs, have the authors evaluated the consistency of generated strategies across different LLMs, prompts, or random seeds? Understanding this would help assess the method’s reproducibility and reliability.\n7. Could the authors explain whether the framework could be generalized to other domains beyond VRPs, such as other NP-hard problems?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n1. (Quality) The manuscript includes abundant experimental workloads. It evaluates extensive synthetic and real-world data across five instance sizes per problem. And the ablations isolate the benefit of TTPL and MVDF individually.\n2. (Significance) The introduction of TTPL is a strong advancement in neural combinatorial optimization, improving model generalization on large-scale VRPs without requiring retraining, making it practical for real-world applications.\n3. (Originality) The application of LLMs to design the projection strategies during the inference phase is a novel and promising approach, which is a unique contribution to the field.\n\nWeaknesses:\n1. (Quality) Lack of Theoretical Insights/Interpretability: The paper focuses primarily on experimental results and does not provide any deep theoretical analysis of why the projection strategy works or how it guarantees better performance.\n2. (Quality) Lack of Statistical Significance: The paper does not provide error bars or other statistical measures to indicate the variability or reliability of the results, which would be crucial for validating the robustness of the method.\n3. (Clarity) Some key information is missed: Some critical loss functions and evaluation metrics should be further discussed in the main text. \n4. (Quality) Although results are promising, the paper does not fully address the computational cost, especially in terms of the time required for the LLM optimization process.\n5. (Significance) The paper mentions the slow convergence of the LLM optimization phase, which is a significant practical limitation for deploying this method in real-time applications.\n6. (Clarity) Several typos (e.g., “MVFD” spelled “MVDF”).", "was_revised": true, "final_justification": "The proposed method is empirically effective, but increases computation time. I would keep my original score. I am OK if the paper is accepted.", "rebuttal": "Dear Reviewer SjSP\n\nThank you very much for your time and effort in reviewing our work. We are more than delighted to know you find our method is novel and applicable in real-world scenarios. We address your concerns as follows.\n\n> **W1 & Q1: A deeper theoretical analysis or an interpretability experiment to explain why the proposed projection strategy improves the model's generalization performance.**\n\n**A1**: Thank you very much for raising this concern. We fully agree that providing a deeper analysis of why our projection learning strategy is critical to understanding the significance of this work.\n\nTo theoretically explain the effectiveness of projection, we introduce Rigid Wasserstein Distance (RWD) [1] as a metric to **quantify the similarity between the K-Nearest-Neighbor (KNN) subgraph extracted from the test instance and the target training instance**. Specifically, RWD models CO instances (TSP/CVRP in our study) as probability measures, and the RWD calculates the minimum cost to make them identical under optimal transformations. The formal definition can be written as\n$$\n    V(\\mu, v) := (\\underset{e \\in E(d)}{\\mathrm{min}}\\sum_{i=1}^n \\sum_{j=1}^nC_{ij}||x_i - e(y_j)||^2)^{\\frac{1}{2}},\n$$\nwhere $\\mu$ and $v$ are the probability measures of two different CO instances, $C$ is the cost matrix $C_{ij} = ||x_i - y_i||$ represents distance that transport point $x_i$ to $y_i$, $e \\in E(d)$ indicates rigid transformations, $||x_i - e(y_j)||$ is the distance between a point $x_i$ from the first instance and a transformed point $e(y_i)$ from the second instance.\n\nTo empirically demonstrate how our learned projection strategy improves performance by mitigating the distributional shift between training and test data, we computed the RWD between a given training instance and the KNN subgraphs generated during the search process, both before and after applying our TTPL projection. We then correlated these RWD values with the final solution quality achieved by the LEHD model. The results of this analysis are presented in Table 4.\n\nTable 4: Illustration of distribution difference and performance\n|Method|RWD|Obj.|\n|-|-|-|\n|LEHD|0.121|57.50|\n|LEHD-TTPL|**0.026**|**52.63**|\n\nThe data in Table 4 reveals that a lower RWD in the projected KNN subgraphs corresponds directly to a higher quality solution. This suggests that the model's predictive performance is enhanced when the input graph's distribution is more similar to that of the training instances.\n\n> **W2 & Q2: An inclusion of a statistical significance measure to validate the robustness and reliability of the method**\n\n**A2:** We sincerely appreciate your constructive comments. In response, we have addressed the statistical analysis in two stages of our methodology:\n**TTPL Search Process**\nTo verify the stability of the TTPL search process, we perform 10 independent runs, each initialized with the same base model (LEHD) and settings. We then calculated the mean and standard deviation of the optimal gap of the final strategies obtained on TSP1K/5K/10K. The results are shown in Table 5:\n\nTable 5: Results of TTPL with 10 independent runs\n|Method|TSP1K|TSP5K|TSP10K|\n|-|-|-|-|\n||mean$\\pm$std.|mean$\\pm$std.|mean$\\pm$std.|\n|TTPL|23.77$\\pm$3.22e-03|52.71$\\pm$2.17e-02|74.36$\\pm$2.06e-02|\n\n**Inference stage**\n\nTo assess the performance of the projection found by TTPL, we evaluated it across different batches and calculated the mean and standard deviation as suggested. We have also proceeded with paired t-tests to formally assess the statistical significance of the solution quality between our methods and several strong baselines. The symbols \"+\", \"=\", and \"-\" denote that TTPL performs statistically better than, competitive with, and worse than the compared method, respectively.\n\nTable 6: Statistical results on TSP1K/5K/10K\n|Problem Size|INViT|BQ|LEHD|TTPL|\n|-|-|-|-|-|\n|TSP1K|24.66±0.30+|23.65±0.28=|23.84±0.34+|**23.64±0.36**|\n|TSP5K|54.49±0.14+|58.27±0.97+|58.85±0.38+|**52.43±0.30**|\n|TSP10K|76.85±0.20+|89.73±1.22+|91.33±1.33+|**73.49±0.44**|\n|+/=/-|3/0/0|2/1/0|3/0/0|NA|\n\n> **W3 & Q3: Detailed discussion of the key loss functions and evaluation metrics (e.g., RWD) in the main text**\n\n**A3:** We sincerely thank you for the feedback and apologize for the ambiguity in the description of our methodology. We will add the corresponding explanation to our main text in the revised version. The loss function and the evaluation metrics are described as follows:\n**Loss function**\nThe backbone model used in this paper is LEHD, which is trained with the **Cross-Entropy** loss. It should be noted that the proposed TTPL framework **is strictly inference-only** and the LEHD backbone model is not trained or fine-tuned during the TTPL searching process. \n**Evaluation metrics**\nFitness value: To guide the LLM in designing projection strategies, we use a fitness value defined as the solution length solved by the base model on a set of validation instances. This score measures the quality of a given strategy.\nRigid Wasserstein Distance (RWD): In this paper, we use RWD as the metric to measure the difference between Combinatorial Optimization (CO) instances. The detailed explanation of RWD can be found in the previous answer (**A1**). In general, RWD is used to describe the distance between different CO instances. It first models CO instances as probability measures and then calculates the minimum cost required to transport one measure to the other. \n\n> **W4 & Q5: Detailed analysis of the method's computational cost and efficiency**\n\n**A4:** Thank you for your professional comments. We agree that showing the computational cost introduced by TTPL is important. \nIn our main text, we adopt TTPL to search for the appropriate projection strategy on TSP1K, TSP5K, and TSP10K instances. To exhibit the computational cost, we have recorded the additional time introduced by the TTPL search process in Table 7.\n\nTable 7: Time used for TTPL to learn projection strategies on different scale\n|Method|TSP1K|TSP5K|TSP10K|\n|-|-|-|-|\n|TTPL|5.5h|9.6h|19.9h|\n\nAlthough TTPL introduces additional search costs, its primary contribution is the automated discovery of the best-fitted projection strategy. This automation contributes to TTPL's significant versatility, allowing it to generalize effectively across different base models rather than being confined to a single architecture.\n\n\n> **W5 & Q4: Exploring approaches to accelerate the convergence of the LLM optimization to improve the method's practical applicability**\n\n**A5:** We sincerely thank you for this insightful feedback to explore acceleration techniques. In response, we have implemented a parallel search strategy to enhance the efficiency of the optimization phase.\n\nTo demonstrate the impact of this improvement, we conducted experiments to compare the time consumption of the optimization process with and without the parallel search strategy. The times are summarized in Table 8.\n\nTable 8: Results of TTPL using different search strategies\n|Method|TSP1K|TSP5K|TSP10K|\n|-|-|-|-|\n|TTPL (Sequential)|5.5h|9.6h|19.9h|\n|TTPL (Parallel)|**3.2h**|**5.6h**|**11.6h**|\n\n> **W6. Several typos (e.g., “MVFD” spelled “MVDF”).**\n**A6:** We sincerely apologize for the typo and appreciate you bringing it to our attention. We will correct them.\n\n> **Q6. Consistency and reliability of TTPL's outputs across different LLMs, prompts, or random seeds**\n\n**A7:** We thank you for this constructive question about the sensitivity of TTPL to its hyperparameter. To investigate this, we first tested our TTPL framework with several state-of-the-art LLMs, including Claude, Gemini, DeepSeek, and Qwen. We show the experimental results in Table 9. It is obvious that the choice of LLM has no significant influence on the projection performance.\n\nTable 9: Result of TTPL using different LLMs\n|Method|TSP1K|TSP5K|TSP10K|\n|-|-|-|-|\n|TTPL-Claude|23.80|52.79|74.48|\n|TTPL-DeepSeek|**23.67**|**52.39**|**74.00**|\n|TTPL-Gemini|23.76|53.71|76.42|\n|TTPL-Qwen|23.75|52.73|74.25|\n|TTPL-GPT-4o-mini|23.73|52.63|74.39|\n\nBesides, we examine the influence of different prompt strategies. In this paper, we provide a template program for the LLM to provide guidance in generating a new projection strategy. To examine TTPL's robustness, we remove this template program and let the LLM search on its own capabilities. We equipped LEHD with the obtained projection and tested on TSP1K/5K/10K instances. The results are shown in Table 10.\n\nTable 10: TTPL using different prompts\n|Method|TSP1K|TSP5K|TSP10K|\n|-|-|-|-|\n|LEHD w/o TTPL|24.2|57.5|84.3|\n|TTPL w/o template|24.00|57.13|82.77|\n|TTPL full prompt|**23.73**|**52.63**|**74.39**|\n\n> **Q7. Could the authors explain whether the framework could be generalized to other domains beyond VRPs, such as other NP-hard problems?**\n\n**A8:** Thank you for this insightful question. We sincerely apologize that our current implementation can not be generalized to other domains beyond VRPs. This is because the data formats and problem structures differ significantly across CO domains, and our current strategy is tailored to the coordinate-based routing problem.\n\nHowever, we generalized our method to the Orienteering Problem (OP). Specifically, we employed the TTPL in the Sym-NCO [2] model and tested it on large-scale OP instances. The results are summarized below:\n\nTable 11: Sym-NCO using TTPL on OP instances\n|Method|OP1K|OP5K|OP10K|\n|-|-|-|-|\n|Sym-NCO|89.92|239.40|428.22|\n\nThank you for your time in reviewing our work. We hope that our responses have effectively addressed your concerns.\n\n**Reference**\n\n[1] Wang, X., Miao, F., Liu, W., \\& Xiong, Y. (2025, March). Efficient and robust neural combinatorial optimization via Wasserstein-based coresets. In The Thirteenth International Conference on Learning Representations.\n\n[2] Kim, M., Park, J., \\& Park, J. (2022). Sym-NCO: Leveraging symmetricity for neural combinatorial optimization. Advances in Neural Information Processing Systems, 35, 1936-1949."}, {"review_id": "5IAuxYCtCI", "reviewer": "Reviewer_3Y2f", "summary": "This paper addresses the significant challenge of generalization in Neural Combinatorial Optimization (NCO) for Vehicle Routing Problems (VRPs). While NCO models perform well on problem instances of similar scale to their training data (typically small instances like 100 nodes), their performance degrades significantly when applied to larger-scale problems due to a distributional shift between training and testing data.\n\nTo overcome this limitation, the paper introduces a novel learning framework called Test-Time Projection Learning (TTPL). This framework is designed to learn a projection between the training and testing data distributions, which is then used to enhance the scalability and generalization of existing NCO models.\n\nThe key contributions of this work are:\n\nA novel learning framework driven by Large Language Models (LLMs): This framework learns a projection that bridges the distributional gap between small-scale training data and large-scale test data.\n\nInference-only approach: Unlike many existing techniques that require joint training with the neural network, TTPL operates exclusively during the inference phase. This means it can be applied to pre-trained NCO models without needing to retrain them, making it highly flexible and practical.\n\nEnhanced scalability for NCO models: Extensive experiments demonstrate that TTPL significantly improves the performance of backbone NCO models (trained on 100-node instances) when applied to larger-scale Traveling Salesman Problems (TSP) and Capacitated Vehicle Routing Problems (CVRP) up to 1000 nodes,", "questions": "Question: The paper states that LLMs drive the learning of projection strategies. Could the authors provide a more in-depth explanation of how the LLM specifically learns this projection? What kind of prompts are used? What is the input/output format for the LLM during this process? Is the LLM fine-tuned, or is it used as a zero-shot/few-shot learner? What is the architecture of this \"projection learning\" component?\nA clear and comprehensive explanation of the LLM's internal mechanism for projection learning would significantly improve the Quality and Clarity ratings.\n\nQuestion: While TTPL avoids retraining the NCO backbone, it introduces an additional \"test-time projection learning\" step. Could the authors provide a more detailed breakdown of the computational overhead (inference time and memory) introduced by the TTPL framework itself, distinct from the backbone NCO model's inference? This is particularly relevant for large-scale instances (e.g., N=1000).\nSuggestion: Include a table or graph comparing the inference time of the backbone model alone versus the backbone + TTPL, perhaps also breaking down the TTPL component's time. This would offer a more complete picture of the practical efficiency trade-offs.\n\nQuestion: The method shows strong generalization on TSP and CVRP to larger scales. How do the authors anticipate TTPL performing on other, more complex Combinatorial Optimization Problems (COPs) or more constrained VRP variants (e.g., VRP with time windows, multiple depots, pick-up and delivery, heterogeneous fleets)?\nSuggestion: Discuss the potential applicability and limitations of TTPL for a broader range of COPs. A brief qualitative discussion on how the framework might need to be adapted (e.g., new feature representations, different projection strategies) for problems with more complex constraints would be valuable.\n\nQuestion: Are there specific parameters or hyper-parameters within the projection learning component (e.g., related to the LLM's usage, projection dimension, or learning rate for the projection) that significantly influence TTPL's performance? How robust is TTPL to variations in these parameters?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nQuality: The paper presents a novel and well-motivated approach to address a crucial problem in NCO: generalization to larger problem scales. The proposed Test-Time Projection Learning (TTPL) framework is innovative, particularly its inference-only nature. The experimental evaluation is comprehensive, testing TTPL on both TSP and CVRP benchmarks across various scales (from 100-node training to 1000-node testing). The results clearly demonstrate the effectiveness of TTPL in improving the generalization ability of backbone NCO models, outperforming strong baselines.\n\nClarity: The paper is well-written and easy to understand. The problem of distributional shift and generalization in NCO is clearly articulated. The TTPL framework, including the role of LLMs and the projection learning mechanism, is explained logically. Figures (e.g., Figure 1 illustrating the framework) are helpful in conveying complex ideas. The experimental setup, including baseline models and evaluation metrics, is clearly described.\n\nSignificance: The problem of generalization across different scales is a major hurdle for the practical deployment of NCO models. By proposing an effective inference-only solution, this paper makes a highly significant contribution. TTPL's ability to enhance pre-trained models without retraining is a practical advantage that can save significant computational resources and make NCO more accessible for real-world large-scale problems. The use of LLMs to drive this projection learning is also significant, exploring a novel application area for LLMs in optimization.\n\nOriginality: The core idea of \"test-time projection learning\" to address generalization in NCO is highly original. The framework's unique characteristic of operating solely during inference to bridge the distributional gap, and the novel integration of LLMs to learn this projection, are innovative contributions that distinguish this work from previous efforts in NCO generalization (which often involve data augmentation or architectural changes during training).\n\nWeaknesses:\n\nLLM Role and Transparency: While the paper states LLMs are used to drive the learning of projection strategies, the exact mechanism and specific LLM (or family of LLMs) used for this \"projection learning\" could be more transparently detailed. The justification for LLM usage in the declaration section (\"designing projection strategies\") is somewhat vague. More specifics on the LLM's architecture within the framework, its training (if any specific to TTPL), and how it concretely learns and applies the projection would strengthen this aspect.\n\nTheoretical Guarantees/Insights: The paper primarily focuses on empirical results. While impressive, a deeper theoretical analysis into why TTPL works, or under what conditions the projection learning is guaranteed to succeed, would significantly strengthen the foundational understanding. For instance, what properties of the LLM or the projection mechanism enable it to effectively bridge distributional shifts?\n\nComputational Overhead of LLM/TTPL: While TTPL avoids NCO model retraining, the inference-time projection learning itself might introduce a computational overhead. A more detailed analysis of the time and resource costs associated with the LLM-driven projection learning component during inference, especially for very large instances, would be beneficial for practical considerations.\n\nGeneralization to Other Combinatorial Problems: The method is evaluated on TSP and CVRP. While these are fundamental VRPs, discussing how TTPL might extend to other combinatorial optimization problems (e.g., Orienteering Problem, Prize Collecting TSP, other routing problems with complex constraints) would broaden its perceived applicability.", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 3Y2f\n\nThank you very much for your time and effort in reviewing our work. We are glad to know you find TTPL novel and well-motivated, and recognize its significance for practical NCO deployment. Your concerns are answered as follows.\n\n> **W1 & Q1. LLM Role and Transparency: The paper's explanation of how the Large Language Model (LLM) learns \"projection strategies\" is too vague and lacks transparency. To improve the quality and clarity of the work, please provide a more detailed description of this mechanism, specifying the architecture of the projection learning component, the prompts and input/output formats used, and whether the LLM is fine-tuned or utilized in a zero-shot or few-shot capacity.**\n\n**A1:** Thanks very much for raising concerns about our methodology. The LLM in TTPL framework undergoes **no training or fine-tuning**. During TTPL iteration, LLM generates and refines **executable code** for the projection strategies. \n\nSpecifically, the input is a crafted natural language prompt, which includes the **task description, evolution instructions, and template program**. Task description helps LLM to understand the problem, providing prior information. Evolution instructions indicate the LLM to do reasoning over the in-context information and generate new projection strategies as well as their corresponding code implementations. The template program serves as the seed to guide the optimization direction of LLM. You may kindly refer to **Appendix B.1 (page 14-18)** for more details about prompts.\n\nThe output is an executable source code (e.g., a Python function) that implements a projection strategy. It should be noted that any existing LLMs (e.g., models from the GPT series, Claude, Gemini, etc.) could be integrated into TTPL.\n\n> **W2. Theoretical Guarantees/Insights: The paper primarily focuses on empirical results. While impressive, a deeper theoretical analysis into why TTPL works, or under what conditions the projection learning is guaranteed to succeed, would significantly strengthen the foundational understanding. For instance, what properties of the LLM or the projection mechanism enable it to effectively bridge distributional shifts?**\n\n**A2**: Thank you for your professional comments. We fully agree that providing a deeper analysis of why our projection learning strategy is effective is critical to understanding the significance of this work.\n\nTo provide a theoretical foundation for the effectiveness of our projection strategy, we employ the Rigid Wasserstein Distance (RWD) [1] as a metric. **RWD quantifies the similarity between the K-Nearest-Neighbor (KNN) subgraph extracted from the test instance and the target training instance**. Specifically, RWD models CO instances (TSP/CVRP in our study) as probability measures, and the RWD calculates the minimum cost to make them identical under optimal transformations. The formal definition can be written as\n$$\n    V(\\mu, v) := (\\underset{e \\in E(d)}{\\mathrm{min}}\\sum_{i=1}^n \\sum_{j=1}^nC_{ij}||x_i - e(y_j)||^2)^{\\frac{1}{2}},\n$$\nwhere $\\mu$ and $v$ are the probability measures of two different CO instances, $C$ is the cost matrix $C_{ij} = ||x_i - y_i||$ represents distance that transport point $x_i$ to $y_i$, $e \\in E(d)$ indicates rigid transformations (translation, rotation, reflection, etc.), $||x_i - e(y_j)||$ is the distance between a point $x_i$ from the first instance and a transformed point $e(y_i)$ from the second instance. It is computed after an optimal alignment transformation $e$ has been applied.\n\nTo empirically demonstrate how our learned projection strategy improves performance by mitigating the distributional shift between training and test data, we analyzed the KNN subgraphs generated by the LEHD model on a TSP1K instance. For a given training instance, we computed the RWD between it and the KNN subgraphs, both before and after applying our TTPL projection. We then correlated these RWD values with the final solution quality achieved by the LEHD model. The results of this analysis are presented in Table 12.\n\nTable 12: Illustration of distribution difference and performance\n|Method|RWD|Obj.|\n|-|-|-|\n|LEHD|0.121|57.50|\n|LEHD-TTPL|**0.026**|**52.63**|\n\nThe data in the table reveals a strong correlation: a lower RWD in the projected KNN subgraphs corresponds directly to a higher quality solution. This suggests that the model's predictive performance is enhanced when the input graph's distribution is more similar to that of the training instances.\n\n> **W3. Computational Overhead of LLM/TTPL: While TTPL avoids NCO model retraining, the inference-time projection learning itself might introduce a computational overhead. A more detailed analysis of the time and resource costs associated with the LLM-driven projection learning component during inference, especially for very large instances, would be beneficial for practical considerations.**\n> **Q2. While TTPL avoids retraining the NCO backbone, it introduces an additional \"test-time projection learning\" step. Could the authors provide a more detailed breakdown of the computational overhead (inference time and memory) introduced by the TTPL framework itself, distinct from the backbone NCO model's inference? This is particularly relevant for large-scale instances (e.g., N=1000). Suggestion: Include a table or graph comparing the inference time of the backbone model alone versus the backbone + TTPL, perhaps also breaking down the TTPL component's time. This would offer a more complete picture of the practical efficiency trade-offs.**\n\n**A3:** We sincerely thank you for raising this important point regarding the computational overhead of our TTPL framework. Following your advice, we have performed a detailed breakdown of the computation cost introduced by TTPL on TSP1K/5K/10K. The time is listed in Table 13.\n\nTable 13: Time usage breakdown for TTPL on TSP instances\n|Problem Size|Inference|Inference|Learning|\n|-|-|-|-|\n||Backbone|Backbone+TTPL|TTPL|\n|1000|0.1s|0.1s|5.5h|\n|5000|1.4s|1.4s|9.6h|\n|10000|2.7s|2.9s|19.9h|\n\nThe TTPL learning process, which involves the LLM-driven optimization, is indeed computationally intensive, potentially taking several hours. However, we would like to emphasize that this is **a one-time, offline cost**. In particular, once a projection strategy is discovered, it is highly **generalizable and imposes negligible computational overhead during inference**. Therefore, the initial time investment is worthwhile, as TTPL consistently improves the performance of base models on large-scale instances.\n\n> **W4. Generalization to Other Combinatorial Problems: The method is evaluated on TSP and CVRP. While these are fundamental VRPs, discussing how TTPL might extend to other combinatorial optimization problems (e.g., Orienteering Problem, Prize Collecting TSP, other routing problems with complex constraints) would broaden its perceived applicability.**\n> **Q3. The method shows strong generalization on TSP and CVRP to larger scales. How do the authors anticipate TTPL performing on other, more complex Combinatorial Optimization Problems (COPs) or more constrained VRP variants (e.g., VRP with time windows, multiple depots, pick-up and delivery, heterogeneous fleets)? Suggestion: Discuss the potential applicability and limitations of TTPL for a broader range of COPs. A brief qualitative discussion on how the framework might need to be adapted (e.g., new feature representations, different projection strategies) for problems with more complex constraints would be valuable.**\n\n**A4:** We appreciate your constructive feedback. To demonstrate the generalizability of our method, we have acted on your suggestion and extended our experiments. Specifically, we integrated our TTPL projection with the Sym-NCO [2] model and successfully applied it to the Orienteering Problem (OP). This confirms that the proposed TTPL projection is not confined to a specific problem architecture. Although the present implementation is coordinate-based and potentially limited when coordinate information is not available, we will extend it to a distance-based projection, broaden its applicability to more complex VRPs, such as the Asymmetric TSP.\n\n\nTable 14: TTPL with Sym-NCO on OP instances\n|Method|OP1K|OP5K|OP10K|\n|-|-|-|-|\n|Sym-NCO|89.92|239.40|428.22|\n\n> **Q4. Are there specific parameters or hyper-parameters within the projection learning component (e.g., related to the LLM's usage, projection dimension, or learning rate for the projection) that significantly influence TTPL's performance? How robust is TTPL to variations in these parameters?**\n\n**A5:** We thank you for this insightful question about TTPL's robustness on its hyperparameters. To investigate this, we have conducted a series of ablation studies focusing on the **population size** and the **choice of the LLM**. We report results in Tables 15 and 16, demonstrating that the framework's performance remains stable across these variations. This confirms that TTPL is robust with respect to these \n\nTable 15: Result of TTPL using different population sizes\n|Population size|10|15|20|25|30|\n|-|-|-|-|-|-|\n|TTPL|23.68|23.80|23.73|23.68|23.75|\n\nTable 16: Result of TTPL using different LLMs\n|Method|TSP1K|TSP5K|TSP10K|\n|-|-|-|-|\n|TTPL-Claude|23.80|52.79|74.48|\n|TTPL-DeepSeek|23.67|52.39|74.00|\n|TTPL-Gemini|23.76|53.71|76.42|\n|TTPL-Qwen|23.75|52.73|74.25|\n|TTPL-GPT-4o-mini|23.73|52.63|74.39|\n\nThanks again for your time and effort in reviewing our work. We sincerely hope that our responses have effectively addressed your concerns.\n\n**Reference**\n[1] Wang, X., Miao, F., Liu, W., \\& Xiong, Y. (2025, March). Efficient and robust neural combinatorial optimization via Wasserstein-based coresets. In The Thirteenth International Conference on Learning Representations. \n\n[2] Kim, M., Park, J., \\& Park, J. (2022). Sym-NCO: Leveraging symmetricity for neural combinatorial optimization. Advances in Neural Information Processing Systems, 35, 1936-1949."}, {"review_id": "GrNWZeba5q", "reviewer": "Reviewer_WCWc", "summary": "This paper proposes a projection learning framework TTPL based on Large Language Model (LLM). By optimizing the projection strategy and multi-view decision fusion (MVDF) technology, the generalization ability of the neural combinatorial optimization model in large-scale vehicle routing problems (VRP) is significantly improved.", "questions": "Mainly see weaknesses.\nSmall issues:\n1.What is the full name of AHD? Please give its full name when first appeared in the text.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1.After conducting sufficient ablation experiments and general experiments, I believe the MVDF you proposed has independent significance.\n2.The algorithm in this paper successfully solves the problems of TSP-100K and CVRP-100K in an extremely short time, which shows the potential of LLM.\nWeaknesses:\n1.Although many comparative experiments have been conducted, as far as I know, this is not the first work to apply LLM to the solution of TSP problems. Perhaps, you should compare the results of your model with theirs. For example, the citation [46] in your article. Meanwhile, in the \"Related Work\" section, if possible, some introductions to the LLM-based generalization method should also be added.\n2.You only used GPT-4o-mini and did not use other LLMS. The generalization of the method might be insufficient.\n3.I don't know whether the LLM also uses your training data as the pre-training corpus. This will raise a question: Is the excellent performance of your model due to the good performance of the LLM itself or the effectiveness of the solution you proposed? This will greatly affect the assessment of innovation.", "was_revised": true, "final_justification": "The concerns have been addressed, however, consider the originality of the paper , I will keep my score.", "rebuttal": "Dear Reviewer WCWc\n\nThank you very much for your time and effort in reviewing our work. We are glad to know you recognize the independent significance of MVDF and our method's efficiency in solving TSP/CVRP-100K problems. We address your concerns as follows.\n\n\n> **W1: Although many comparative experiments have been conducted, as far as I know, this is not the first work to apply LLM to the solution of TSP problems. Perhaps, you should compare the results of your model with theirs. For example, the citation [46] in your article. Meanwhile, in the \"Related Work\" section, if possible, some introductions to the LLM-based generalization method should also be added.**\n\n**A1:** We sincerely thank you for this insightful comment and for highlighting the important work in EoH [1]. We agree that a direct comparison and a more comprehensive discussion of related methods are crucial for claiming our contribution.\n**1. Comparison with EoH**\nIn response to your suggestions, we have conducted a comparison experiment between our method and EoH on the TSP task. In particular, we run EoH on TSP1K/5K/10K. We use 128 instances for TSP1K and 16 instances for TSP5K and TSP10K. Moreover, we compare EoH's result with the solution obtained by TTPL using Random Re-Construction (RRC) under the same number of iterations. This is mainly because of the iterative nature of the EoH's implementation when solving TSP, which utilizes a Guided Local Search (GLS) algorithm to iteratively refine solutions. To ensure a fair comparison, we set the iterations of RRC and GLS to the same number. The final average solution length over test instances is reported in Table 17:\n\nTable 17: Comparison results on synthetic TSP dataset\n| Method       | TSP1K | TSP5K | TSP10K |\n|--------------|-------|-------|--------|\n| EoH-GLS1000  | 23.58 | 53.39 | 75.02  |\n| TTPL-RRC1000 | **23.19**  | **51.50** | **72.59**  |\n\nIt is obvious that our proposed method consistently outperforms the EoH over all test scales. Specifically, TTPL reduces the solution length by 1.68\\%, 3.67\\%, and 3.35\\% for the TSP1K, 5K, and 10K instances, respectively. These results indicate the superior performance of TTPL over LLM-based generalization methods.\n\n**2. Additional review for LLM-based generalization methods**\nAs suggested, we will include a discussion of recent LLM-based generalization methods for combinatorial optimization in **Appendix A, page 14**. The details of the introduction to LLM-based generalization methods are as follows:\n\nRecent advancements have demonstrated the significant potential of Large Language Models (LLMs) in automating the design of high-performing heuristics for complex computational problems. This methodology typically involves maintaining a population of elite heuristic functions, which are evaluated and ranked based on their fitness on a designated dataset. The LLM is then iteratively prompted with high-performing functions from this population to generate potentially superior heuristic candidates. EoH [1] and Funsearch [2] pioneered applying LLM to design a population-based evolutionary computation procedure. Building on this, ReEvo [3] incorporated a reflection mechanism to augment the LLM's reasoning capabilities during heuristic generation. Addressing the challenge of premature convergence, HSEvo [4] introduced diversity metrics and a harmony search algorithm to enhance population diversity without degrading solution quality. In a different approach, MCTS-AHD [5] conceptualizes the task as a search problem, modeling the heuristic design process as a Monte Carlo Tree Search (MCTS) to systematically explore the solution space.\n\nWe hope the above response can address your concerns.\n\n> **W2. You only used GPT-4o-mini and did not use other LLMs. The generalization of the method might be insufficient.**\n\n**A2:** We thank the reviewer for raising this important concern about the LLM's generalizability of our method. We agree that testing with a single LLM is a limitation because TTPL highly relies on the LLMs.\n\nTo address this, we have conducted extensive experiments by integrating several state-of-the-art LLMs, including GPT4o-mini, Claude, Gemini, DeepSeek, and Qwen. \nWe have employed all five LLMs to search for projection strategies on TSP1K instances and tested them on TSP1K, 5K, and 10K instances with LEHD as its base model. The results are summarized in Table 18. \n\nLEHD with the TTPL projection achieves better performance compared to its original version across different LLMs. In particular, TTPL helps LEHD reduce the solution length by 0.4, 3.79, and 7.88 of TSP1K, TSP5K, and TSP10K, respectively, with the **worst** projections, while shortening the solution length by 0.53, 5.11, and 10.3 of TSP1K, TSP5K, and TSP10K, respectively, with the **best** projections. It clearly demonstrates the generalization of the method in terms of LLM's usage.\n\nTable 18: Result of TTPL using different LLMs\n| Method           | TSP1K           | TSP5K           | TSP10K          |\n|------------------|-----------------|-----------------|-----------------|\n|                  | Obj. ($\\Delta$) | Obj. ($\\Delta$) | Obj. ($\\Delta$) |\n| LEHD greedy      | 24.2 (0)        | 57.5 (0)        | 84.3 (0)        |\n| TTPL-Claude      | 23.80 (-0.4)    | 52.79 (-4.71)   | 74.48 (-9.82)   |\n| TTPL-DeepSeek    | **23.67 (-0.53)**   | **52.39 (-5.11)**   | **74.00 (-10.3)**  |\n| TTPL-Gemini      | 23.76 (-0.44)   | 53.71 (-3.79)   | 76.42 (-7.88)   |\n| TTPL-Qwen        | 23.75 (-0.45)   | 52.73 (-4.77)   | 74.25 (-10.05)  |\n| TTPL-GPT-4o-mini | 23.73 (-0.47)   | 52.63 (-4.87)   | 74.39 (-9.91)   |\n\n> **W3. I don't know whether the LLM also uses your training data as the pre-training corpus. This will raise a question: Is the excellent performance of your model due to the good performance of the LLM itself or the effectiveness of the solution you proposed? This will greatly affect the assessment of innovation.**\n\n**A3:** We sincerely apologize for the unclear description in our manuscript and thank you for your valuable feedback regarding LLMs' usage. We would like to reassure that the LLM utilized in this paper serves as **a zero-shot learner and was not fine-tuned or trained on any of the training datasets**. Consequently, the LLM had no prior exposure to the specific problem instances used in our experiment evaluation. \n\nOur innovation lies in the introduction of **projection learning** to improve the NCO methods' large-scale generalization capability. Different from the existing generalization methods that focus on model architecture or training paradigm, we propose a data-centric approach. It **only operates at the inference stage** by aligning the distribution of testing and training data. \n\nTo implement the projection learning, heuristic-based methods demand significant domain expertise, while learning-based methods can be hindered by intricate feature engineering and the complex design of loss functions. Recently, LLM-based Automatic Heuristic Design (AHD) has emerged as a promising approach by leveraging the reasoning and code generation capabilities of LLMs to automatically discover and construct effective heuristics. In this paper, we utilize LLM-AHD methods as a design tool to search for a projection strategy.\n\nNonetheless, we wish to clarify that a simple projection still can significantly improve the base model's performance. You may kindly refer to **Table 4 (page 8)**. In this experiment, we replaced our LLM-designed projection with a human-crafted strategy and applied it to the LEHD base model. The results demonstrate that even this basic projection leads to a significant performance improvement over the original LEHD version.\n\nThis confirms that the proposed projection strategy methodology contributes most to the reported performance gains. The LLM functions as an enabling tool that automates the design of this projection, helping us achieve a robust and unified solution across multiple base models. We hope this clarification adequately addresses your concerns.\n\n> **Q1. What is the full name of AHD? Please give its full name when first appeared in the text.**\n\n**A4:** We sincerely thank you for pointing out this oversight. We apologize for failing to define the acronym \"AHD\" at its first mention. The full name for AHD is Automatic Heuristic Design. \n\nThank you for your time and effort dedicated to reviewing our work. We sincerely hope that our responses have effectively addressed your concerns.\n\n**Reference**\n\n[1] Liu, F., Tong, X., Yuan, M., Lin, X., Luo, F., Wang, Z., ... & Zhang, Q. (2024). Evolution of Heuristics: Towards efficient automatic algorithm design using large language model. arXiv preprint arXiv:2401.02051.\n\n[2] Romera-Paredes, B., Barekatain, M., Novikov, A., Balog, M., Kumar, M. P., Dupont, E., ... & Fawzi, A. (2024). Mathematical discoveries from program search with large language models. Nature, 625(7995), 468-475.\n\n[3] Ye, H., Wang, J., Cao, Z., Berto, F., Hua, C., Kim, H., ... & Song, G. (2024). ReEvo: Large language models as hyper-heuristics with reflective evolution. Advances in neural information processing systems, 37, 43571-43608.\n\n[4] Dat, P. V. T., Doan, L., & Binh, H. T. T. (2025, April). HsEvo: Elevating automatic heuristic design with diversity-driven harmony search and genetic algorithm using llms. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 39, No. 25, pp. 26931-26938).\n\n[5] Zheng, Z., Xie, Z., Wang, Z., & Hooi, B. (2025). Monte carlo tree search for comprehensive exploration in llm-based automatic heuristic design. arXiv preprint arXiv:2501.08603."}]

Author rebuttal:

Meta-review: This paper focuses on LLM-based test-time methods for combinatorial optimization. All reviewers unanimously agree that this paper makes significant contributions and recommend acceptance (4,4,4,4). After a careful evaluation, the AC concurs with the reviewers’ assessments and also recommends acceptance.
Decision: Accept (poster)