Learning to Insert for Constructive Neural Vehicle Routing Solver
Authors: Fu Luo
Xi Lin
Mengyuan Zhong
Fei Liu
Zhenkun Wang
Jianyong Sun
Qingfu Zhang
Venue: NeurIPS 2025 poster ()
Keywords: Neural Combinatorial Optimization
Vehicle Routing Problem
Insertion-based Construction
Primary area: optimization

Abstract: Neural Combinatorial Optimisation (NCO) is a promising learning-based approach for solving Vehicle Routing Problems (VRPs) without extensive manual design. While existing constructive NCO methods typically follow an appending-based paradigm that sequentially adds unvisited nodes to partial solutions, this rigid approach often leads to suboptimal results. To overcome this limitation, we explore the idea of the insertion-based paradigm and propose Learning to Construct with Insertion-based Paradigm (L2C-Insert), a novel learning-based method for constructive NCO. Unlike traditional approaches, L2C-Insert builds solutions by strategically inserting unvisited nodes at any valid position in the current partial solution, which can significantly enhance the flexibility and solution quality. The proposed framework introduces three key components: a novel model architecture for precise insertion position prediction, an efficient training scheme for model optimization, and an advanced inference technique that fully exploits the insertion paradigm's flexibility. Extensive experiments on both synthetic and real-world instances of the Travelling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) demonstrate that L2C-Insert consistently achieves superior performance across various problem sizes. The code is available at [https://github.com/CIAM-Group/L2C\_Insert](https://github.com/CIAM-Group/L2C\_Insert).

Learning to Insert for Constructive Neural Vehicle Routing Solver
Fu Luo Xi Lin", Mengyuan Zhong', Fei Liu", Zhenkun Wang Jianyong Sun"*, Qingfu Zhang
School of Automation and Intelligent Manufacturing.
Southern University of Science and Technology, Shenzhen, China
Guangdong Provincial Key Laboratory of Fully Actuated System Control Theory and Technology,
Southern University of Science and Technology, Shenzhen, China
Department of Computer Science, City University of Hong Kong. Hong Kong SAR, China
School of Mathematics and Statistics, Xi' an Jiaotong University, Xi' Xi'an, China
1uof20230mail, sustech. edu. en, xi. cannmm..ittypl edu hk, my zhongostu. canngsttuxjttu. xjt..edu..... edu. cn, fliu36- c0my. cityu. edu. hk, wangzhenkun$0@@maill com, jy sun@xjtu.. edu. cn, qingfu. zhang@ci edu. hk
Abstract
Neural Combinatorial Optimisation (NCO) is promising learning-based approach for solving Vehicle Routing Problems (VRPs) without extensive manual design. While existing constructive NCO methods typically follow an appending- boseed paradigm that sequentially adds unvisited nodes to partial solutions, this rigid approach often leads to suboptimal results. To overcome this limitation, we explore the idea of the insertion- insertion-based paradigm and propose Learning to Construct with Insertion- based Paradigm IIsCC-Inert), novel learning based method for con- structive NCO. Unlike traditional approaches, I.2C-Insert builds solutions by strate- gically inserting unvisited nodes at any valid position in the current partial solution, which can significantly enhance the flexibility and solution quality. The proposed framework introduces three key components: a novel model architecture for precise insertion position prediction, efficient training scheme for model optimization, and an advanced inference technique that fully exploits the insertion paradigm's s flexibility. Extensive experiments on both synthetic and real-world instances of the Travelling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) demonstrate that L2C-Innert consistently achieves superior performance across various problem sizes. The code is available at httpss//gihubb.cm//CCI /CIMM. (Group/I.2C_ Insert]
Introduction
The vehicle routing problem (VRP) [1] is an important combinatorial optimization problem with extensive real-world applications domains such transportation [2], logistics [3], and circuit design 4 Due to its NP-hard nature (5), obtaining exact VRP solutions is computationally diffi- cult [ The existing approaches. therefore. focus on finding approximate solutions within a practical runtime using problem-specifty heuristics. However, designing these heuristics requires substantial domain expertise. Recently, Neural Combinatorial Optimization (NCO) methods have emerged as promising alternative, as they can leverage neural networks to automatically learn effective heuristics from data, thereby significantly reducing the need for extensive manual design 18.
Among NCO methods, constructive approaches attract considerable research interest 6 26 These methods typically employ an appending-baat constructive paradigm that sequentially selects
CCoresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Repeat until All Nodes Visited
Repeat until All Nodes Visited
Intermediaae State
Predict
Intermediate State
Rule based Selection
Prodict
Encoder
Desoder
Encoder
Decodar
Network
Neural Network
Append
Probability
Insert
Probability
Unvisisted
Visisted Node
Unvisisted
Visisted Node
Probubility
Path
Probability
Path
(a) Appending-based Construction for NCO (Conventional)
(b) Insertion-baset Construction for NCO (Unexplored)
Insertion-based construction. Given the same intermediate state the construction process: (a) The appending- based paradigm restricts the addition of selected node exclusively to the end of the current partial solution. This inflexibility leads to path intersections, a common cause of suboptimal solutions.
Figure 1:
Appending- construction
(b) In contrast, the insertion- -hased construction offers greater flexibility by allowing the selected node to be inserted into any feasible position within the partial solution. Such flexibility is crucial for avoiding the intersections and thereby enhancing the potential for generating high-quality solutions.
unvisited nodes and appends them to the end of the current partial solution. This paradigm is inspired by the lequence-to-sequene the model encodes an input sequence into an embedding and then autoregressively generates an output sequence based on this representation. Vinyals al. [6] pioneer this adaptation through their Pointer Networks (Ptr-Nets), which establishes the first sequence-to-sequenee framework specifically for neural combinatorial optimization. Subsequent research has further advanced constructive NCO methods within this appending-based paradigm, with improvements focusing on model training techniques 7 and architectural enhancements [19]. However, appending- baased methods suffer from fundamental limitation due their strict operational constraint that only permits adding new nodes to the end of the current partial solution. This constraint prevents potentially more effective modifications and often leads suboptimal partial solutions caused by early greedy decisions.
framework [27 in natural language processing (NI.P,, where
The insertion-basee -ased paradigm offers more effective alternative for addressing VRPs 28 29). This approach constructs solutions by sequentially inserting unvisited node into any valid position within the current partial solution, which potentially offers greater flexibility and yields higher-quality solutions than the appending-bace based paradigm. For example, shown in Figure given the same intermediate state in the construction process, the rigid sequential nature of the appending paradigm only add the selected node the end of the solution, leading path intersections and suboptimal solution. In contrast, the insertion based construction allows for the flexible placement of the selected node into any feasible position within the partial solution path, thereby avoiding such intersections and holding the potential to generate higher-quality solutions. Despite these clearly demonstrated benefits, the insertion-based constructive approach has remained unexplored in NCO for VRPs in the past decade. A comprehensive review of constructive NCO methods can be found in Appendix [A]
To bridge this research gap, this work proposes Learning Construct with Insertion-based Paradigm (L2C-Insert), a novel insertion-based learning framework for constructive NCO. To the best of our knowledge, L2C-Insert represents the first learning-driven. insertion-based framework specifically designed for solution construction in NCO. Our main contributions can summarized as follows:
We propose a novel model architecture, an effective training scheme, and powerful inference technique for the LnC-Innert framework. Together, these components are crucial for enabling the L2C-Insert framework achieve robust performance.
We develop a supervised learning based training scheme tailored for the efficient learning of the L2C-Insert model. Building on the inherent flexibility of the insertion paradigm,

---

we further propose an insertion- local reconstruction mechanism to enhance model performance during inference.
We conduct comprehensive experiments explore the advantages of the L2C-IInert frame- work on both synthetic and real-world benchmarks. The results demonstrate that our Ins-IInset method achieves outstanding performance on TSP and CVRP instances with sizes ranging from 100 to 100K nodes.
2 Preliminaries
2.1 VRP Formulation
VRP instance can be represented as graph containing n nodes, where each node i E {I.... n3 represented by feature vector 8; E IRd., For example, in the TSP, s; typically corresponds the 2D coordinates of node i. A solution to a VRP instance specifies the sequence, or set of sequences (routes/tours), in which nodes are visited. For example, in the TSP case, a solution a single tour that can be represented as permutation of all nodes: Te (1....,7) , is distinet node. The objective in solving VRPs is generally to minimize the cost of the solution, which often corresponds to the total Euclidean length of the tour(s). A VRP solution is considered feasible if satisfies all
(I.,....p T.:..., Nn), where each element
constraints. For example, in the TSP, a feasible solution must visit each node in the graph exactly once. Constraints in the CVRP additionally include vehicle capacity limits, which are further detailed in Appendix
2.2 Appending-based Construction for Solving VRPs
The appending-basee constructive heuristic is prominent approach that NCO methods frequently leverage for solving VRPs 6 19 21 33 Initializing with empty solution, this heuristic constructs the solution to given instance by sequentially appending unvisited nodes to the end of the current partial solution until all nodes are visited. At each construction step, it selects node from the set of unvisited nodes to append, based on specified strategy. A common selection strategy is choose the unvisited node that has the smallest Euclidean distance the last node in the current partial solution. However, this simple selection strategy typically leads to solutions with relatively low quality. The existing learning- based constructive NCO methods focus on using neural networks to learn more effective selection strategies capable of generating near-optimal solutions.
2.3
sneertio-bbsed Construction for Solving VRPs
The insertion-based constructive heuristic, though well-established in Operations Research for solving VRPs [34 35 29], has not been explored for constructive NCO. Similar to the appending- approach, this heuristic begins with an empty solution and iteratively incorporates unvisited nodes into the partial route until all nodes are included. Unlike simple appending, this method permits insertion of unvisited nodes any valid position within the current partial solution. Each construction step involves two critical decisions: first, selecting an unvisited node for insertion, and second, identifying the proper position within the current partial solution for insertion. Typical node selection strategies include random selection from the unvisited set or choosing the node closest to the previously inserted node. Regarding position selection, common heuristic is to choose the insertion node that minimizes the increase in the total solution cost (e.g., tour length) upon inserting the selected node. Our work mainly focuses on leveraging neural networks learn more effective position selection strategies to generate high-quality solutions.
3 L2C-Insert: Learning to Construct in Insertion Paradigm
This section proposes the I.2C-Insert framework for learning the insertion-based construction heuristic, which integrates three key components: (1) novel model architecture, (2) an effective training scheme, and (3) a powerful inference technique. We demonstrate this framework through solving TSP, and the required adaptations for solving CVRP provided in Appendix B
3

---

Node Embeddings (b. E R+)
Current Node Embedding
Lincar Projection W3 e Raad
X (0)
Attention Layers
X
Unvisited Node Embeddings
Lincur Projection Wi R
Encoder
Linear Projection
Position Embeddings
Linear Projection W2 c Radod
Mask & Softmax
Node Features
Probabilities
Decoder
Select Position and Insert Current Node
Update
Instance Graph
Current Partial Solution
Extended Partial Solution
Unvisisted Node Visisted Node Current Node
Path
Probability
Figure 2: Model Structure I.2C-Insert. (a) Encoding: At the beginning of solution construction, the encoder transforms each node's ' feature vector into d-dimensional node embedding h, E R (b) Decoding: At construction step t. the decoder maintains three embeddings for 1) the current node (the node to be inserted). 2) unvisited nodes, and 3) the positions in the partial solution, where each position embedding is created by horizontally concatenating the embeddings of adjacent visited nodes. Each embedding type undergoes separate linear transformations before being collectively processed through L stacked attention layers. The final insertion probabilities are obtained by applying a linear projection followed by masked softmax operation to the refined embeddings.
3.1 Model Structure
Similar to the appending- based constructive NCO models, our L2C- model utilizes an encoder- decoder framework, with the decoder features with multiple attention layers 36 for the promising as shown in Figure
learning ability 22 23
The encoder contains a linear projection layer followed by an attention layer. For problem instance S with n nodes, each node's feature vector E Rd. (where i = 1,...,n) n) is first transformed into an initial node embedding hς E Rdd where denotes the embedding dimension. These initial embeddings are subsequently updated through the attention layer [21 22 to produce the refined embeddings h, Rd. which the output of the encoder.
Encoder
Decoder At construction step I, the decoder receives the embeddings of all nodes, denoted as and the set of unvisited nodes {uz, My & (m)=-1)) ). To compute the probability of insertion at the current step, embeddings for three distinct inputs are required: 1) the current node (the node to be inserted), 2) unvisited nodes, and 3) the positions in the partial solution.
h TRdd, 1= 1, n. the current partial solution (T ..,..., Tt-1),
First of all, the unvisited node with the minimum Euclidean distance to the previously inserted node is selected as the current node to be inserted, of which the embedding is denoted as h Secondly, the embeddings of the remaining unvisited nodes can be denoted as Ha = (ha,) }, U, $ { U, * Ue- Two learnable linear projections Wo E dddd and W1 E dxd are applied to the current node's 's embedding and each unvisited node's embedding. respectively. Thirdly, to generate the embedding of a potential insertion position within the partial solution, the embeddings of adjacent visited nodes are horizontally concatenated. Given the set of visited node embeddings (h,,) }. the embedding for the insertion position in the solution segment (T,, T++1) is computed as:
[ brail [ [ hn,),
i [1:t: t-:t) 2),
ex;- W2
i=t-1.
where [. represents the horizontal concatenation operator. This operator produces an initial 2d- dimensional initial insertion position embedding, which is subsequently projected to d-dimensional vector via the trainable matrix W₂ E Rddxd to maintain dimensional consistency with node embed- dings. The set of position embeddings is denoted as He (ex;), [1 :t 1).

---

122
P1
55
Encoder
Decdde
P2
Ps
P4
4
62
R6
R5
Model
Pr
( EL
Labeled Solution
Current Partial Solution
Update
Target Position: é' ===6,
Loss: ((0)=
log[pe( é"1 ((.,)t))
O Unvisited Node
Visited Node
Node Selected in Current Step
Path
Insertion Probability
Training Scheme for L2C-Insert Model. The model learns to sequentially insert the current node into the target position in the partial solution. The target position for the current node is determined by its adjacent visited nodes in the original labeled solution. The training objective is to maximize the probability of the model predicting the correct target insertion position, as defined by the provided loss function.
Figure 3:
Then, these embeddings together are refined by L stacked attention layers. The first layer receives input X {he, He. Hu), with each subsequent j-th attention layer processing the output from the (j 1)thth layer, culminating in the final output X x2),, Then, linear projection and softmax function are applied to ( to compute the insertion probabilities of the current node into all valid positions. The masking operation assigns -oe to invalid positions (those corresponding the current node and non-visited nodes) to ensure proper probability normalization over valid insertion locations. The inserting probability ps is calculated as:
24 = xx X + byy,
Vi (maLIT)
(2)
otherwise,
p Softmax(a),
where W Rdx1 and by E RR. are learnable parameters. Each pt p denotes the probability of inserting the current node between consecutive nodes (++)):+) in the partial solution. The decoder executes this sampling-anddinsertion procedure times construct the complete solu- tion {
3.2 Training Scheme
Constructive NCO models typically adopt either reinforcement learning (RL) supervised learning (SL) methods for training. The SL-based method can effectively train the model with a heavy decoder, whereas the RL-based method is not capable, as indicated by Luo et al. (22). Since model utilizes an insertion- based construction process, which differs significantly from the traditional appending- baaed approaches, we redefine the SL-based training scheme follows.
For problem instance with n nodes and its labeled solution π² (e.g., an optimal tour), we first randomly select node as the initial partial solution while designating the remaining nodes as unvisited. Guided by the original labeled solution, the model then learns sequentially re-insert these unvisited nodes into their target positions within the evolving partial solution. The target position for an unvisited node is defined by the two visited nodes adjacent to this unvisited node in the complete labeled solution. For example, consider the partial solution illustrated Figure where T2 represents the current node. After excluding the unvisited nodes क and To, the two visited nodes adjacent to т2 in the labeled solution πı and πz. Therefore, (TT, R3). The loss function is then computed as:
current partial solution that
the target position 2" ē.
[()) log Pe
(E" ['r,,
where (Er..) the set positions the current incomplete solution, E (Er } is the target position, and po (z* Er.., S) is the probability of inserting the current node into target psition predicted by the model parameterized by 0. Subsequently, the model parameters are optimized using gradient-based algorithm (c.g., Adam (37) minimize the loss function. Through this
5

---

training process, the model progressively learns to accurately position previously unvisited nodes into their correct positions within the solution sequence, ultimately acquiring the capability to generate high-quality solutions.
3.3 Insertion-based Local Reconstruction
For NCO, local reconstruction techniques are widely employed during the inference phase to improve solution quality through iterative refinement of local solution segments [38] 39 22 40). While these methods can effectively trade computational time for enhanced solution quality, they face inherent limitations when applied to appending- based constructive models. Specifically. the constraint of using sequence-based based destruction strategies severely limits both the destruction space and the subsequent reconstruction action space, often trapping solutions in local optima. For example, consider a suboptimal solution wherein two nodes are neighbors in terms of the geometric distance but are distant in their relative sequence positions. Under sruuecce-based deconstruction, such nodes have a low probability of being in the same destruction space. Consequently, if an optimal solution requires these two nodes to be adjacent, the subsequent reconstruction step is unlikely to reconnect them, thereby causing the suboptimal solution to stall in a local optimum.
To overcome this limitation, we propose an insertion-bane -based local reconstruction method that exploits the inherent flexibility of the insertion paradigm through a distance- based deconstruction strategy, which can enable more effective reconstruction and consequently enhance the model performance. The iterative local reconstruction process alternates between destruction and reconstruction phases. (1) Destruction Phase: The solution is destroyed based on the distance-based proximity of nodes. The process begins by randomly selecting node from the current solution, followed by the identification and removal of its a-nearest neighbors, which transition to unvisited nodes. The remaining solution segments automatically form a new reduced loop solution. Here, a represents the destruction size. For example, given TSPI0 solution (Ti, ..,.... TIO) where TT is randomly selected with its 3-nearest neighbors { T7, ). the removal of my and { 77, n&} yields the looped solution (T1, T3, TT, T6, Tg. T10). (2) Reconstruction Phase: The model sequentially inserts the unvisited nodes into this partial solution. Once all nodes are re-inserted, the newly generated solution is compared against its predecessor, and the superior solution is retained for subsequent iterations. This iterative process continues until a predefined computational budget (c.g., a maximum number of iterations) is exhausted.
4 Experiments
In this section, we empirically evaluate the L.2C-Insert framework on both synthetic and real-world benchmark TSP and CVRP datasets of various scales. We then contact ablation studies to verify the effect of the proposed framework's 's critical components.
Datasets Following the standard data generation procedure from prior work 19
generate
datasets for both TSP and CVRP problems. (1) Training Datasets: For each problem (TSP and CVRP), create training datasets consisting of one million 100-node instances. We obtain (near- Doptimal solutions for these instances using Concorde [41] for TSP and HGS [42] for CVRP. (2)
Test Datasets: Consistent with established practices [43 22 44 45). we generate five synthetic test datasets with instance sizes ranging from 100 to 100K nodes (100, 1K, 10K, 50K, and 100K). We denote TSP and CVRP instances with N nodes as TSP. and CVRPN (e.g., TSP100, CVRP100).
The dataset composition is as follows: For TSP, the TSP100 and TSPIK datasets contain 10,000
and 128 instances, respectively, while larger-scale datasets (10K, 50K, 100K nodes) each have 16 instances. CVRP datasets follow similar structure, with the exception that CVRPIK IK contains 100 instances, as specified in [4] Following Hou et al. (44) we set vehicle capacities to 50 for CVRP100, 200 for CVRPIK, K, and 300 for larger-scale instances. To evaluate our method on real-world large- scale instances, we also collect 49 symmetric TSP instances and 100 CVRP instances with EUC_2D
features and < IK nodes from TSPLIB 466 and CVRPLIB Set-X 47 respectively.
Model Setting & Training The embedding dimension is set to d = 128, the hidden dimension of the feed-forward layer is set to 512, the query dimension d, is set to 16, and the head number in multi-head attention set to 8. We set the number of attention layers in the decoder to T. following [23). Both the TSP and CVRP models are trained one million instances of size 100. For

---

Table 1: Results on synthetic TSP and CVRP instances. Results marked with an asterisk (*) are from the original paper. The best results are bold. OOM: The method triggered an out-of-memory condition. The reported inference time is the total time required to solve the entire test set.
TSPI00
TSPIK
TSPIOK
Method
Length
Gap
Time
Length
Gap
Time
Length
Gap
Time
LKH3
7.76325
0.000%
56m
23.119
0.000%
8.2h
71.778
0.000%
8.8h
Concorde
7.76324
0.000%
34m
23.118
-0.003%
7.8h
72
0.310%
22.4h
AR-GCN--CTS*
7.764
0.037%
15m
23.863
3.224%
13m
74.93
4.390%
18h
DIFUSCO*
7.78
0.240%
23.56
1.900%
12.1m
73.62
2.580%
47m
T2T
7.76
0.060%
23.3
0.780%
54.7m
NeurOpt
7.765
0.023%
1.8h
307.578
> 100%
3h
SO-mixed*
23.766
2,800%
55.5m
74.299
3.517%
2.034h
H1-TSP
24.718
6,912%
34s
77.75
8.320%
25m
GLOP
7.767
0.048%
1.4h
23.84
3.119%
2.4m
75.04
4.545%
25m
UDC-Xso 50)
7.788
0.319
1.38h
23.53
1.782%
6.21m
OOM
OOM
OOM
POMO a
7.774
0.138%
0.7m
32.5
40.577%
6.
OOM
OOM
OOM
INVIT-3V 16
7.92
2.019%
3.02h
24.343
5.299%
30.43m
76.494
6.570%
1.19h
ELG
7.781
0,229%
2.2m
25.738
11.328%
1.3m
0OM
OOM
OOM
BQ bs16
7.764
0.010%
20m
23.432
1.354%
21m
OOM
OOM
OOM
LEHD RRC1000
7.76337
0.0016%
2.3h
23.288
0.731 %
5.2h
80.9
12.709%
3.6h
L2C- Insert Greedy
7.799
0.459%
0.86mn
24.218
4,754%
0,35m
77.343
7.754%
1.06m
L2C-Insert (/=100)
7.764
0.0038%
47.9m
23.414
1.275%
4.79m
75.603
5,329%
2.58m
I.2C-Insert (/=200)
7.76336
0.0014%
1.62h
23.339
0.952%
9.52m
74.733
4.117%
4.14m
L2C- Insert (f=500)
7.76328
0.0005%
4.0h
23.265
0.633%
22. 22.94m
73.812
2.834%
8.73m
12C-Insert (/=1000)
7.76326
0,0002%
8.0b
23.230
0,481 %
46.4m
73.270
2.079%
16.64m
CVRPI00
CVRPIK
CVRPI0K
Method
Length
Gap
Time
Length
Gap
Time
Length
Gap
Time
HGS
15.56
0.000%
4.5h
41.161
0.000%
5h
226.177
0.000%
8h
LKH3
15.65
0.540%
12h
42.156
2.416%
6.1h
290.575
28.472%
10.3h
NeurOpt
15.66
0.627%
3h
GLOP- (LKH3)
45.753
11.154%
1.93m
276.252 0OM
22.140%
27.98m
UDC-Xs0 50)
16.291
4.699
2.69h
43.583
5.884%
11.96m
OOM
0OM
POMO a
15.75
1.230%
0.86m
100.990
>100%
5.83m
0OM
OOM
OOM
INViT-3V augx 16
16.538
6.282%
3.93h
46.607
13.230%
26.97m
275.691
21.892%
1.28h
ELG
15.84
1.760%
3.4m
66.847
13.812%
3.16m
277.685
22.773%
11.92m
BQ 19
15.81
1.560%
18m
43. 121
4.762%
15m
275.494
21.805%
1.36h
LEHD RRC1000
15.63
0.420%
2.0h
42.408
3.028 %
4.15h
248.604
9.916%
8.1h
Inser Greedy
16. 16.169
3, 3,892%
1 1.4m
44, 454
8. 0,009%
1.17m
255.356
12.901%
2.88m
L2C-Insert (/=100)
15.700
0.877%
1.0h
43 868
6.574%
12.08m
253.462
12.063%
5.75m
L2C-Insert (/=200)
15.667
0.664%
2.0h
43.677
6.113%
24.66m
252.021
11.426%
9.02m
L2C- (/=500)
15.640
0.493%
5.3h
43.416
5.478%
1.05h
248.987
10.085%
19.03m
IIs-et (/=1000)
15.627
0.413%
10.6h
43.152
4.836%
2.05h
245.732
8.646
34.72m
TSP model training, we employ the Adam optimizer [37]. For CVRP model training, we employ the AdamW [48] optimizer, as we find it to be more stable. The initial learning rate is 1 10"4, decaying by a factor of 0.97 after each epoch. The TSP and CVRP models undergo 50 and 15 training epochs, respectively, with a batch size of 1024. All experiments. including training, testing, and evaluation, are conducted on a single NVIDIA GeForce RTX 4090 GPU with 24 GB of memory ensure consistent computational conditions.
Baselines We compare L2C- with a comprehensive set of baseline methods including (1)
Classical Solvers: Concorde 4T). LKH3 44], and HGS 42]: (2) Constructive NCO Methods:
POMO 21: BQ 23 LEHD 22 INVIT 500 and ELG 30 (3) Heatmap-based NCO Methods:
Att- MC-GCNN-MTS SO-mixed [54) GLOP 40) and UDC 40: (5) Improvement-basee NCO Methods: NeurOpt 55
DIFUSCO 55 and T2T 52): (4) Two-stage NCO Methods: H-TSP (33]
In line with the established practice the NCO literature 21), the classical solvers are primarily
included to provide strong, near-optimal baseline for solution quality, rather than to serve as direct competitors in terms runtime. We refer to Appendix C for implementation details of these baselines.
7

---

Table 2: Results on synthetic TSP and CVRP instances with 50K/100K nodes. The best results are bold.
TSPS0K
TSP100K
Method
Length
Gap
Time
Length
Gap
Time
LKH3
159.93
0.000%
160h
225.99
0.000%
400h
GLOP
168.09
5.102%
24m
237.61
5.142%
1.04h
INVIT greedy
171.42
7.184%
20.8h
242.26
7.199%
80h
LEHD RRC1000
OOM
0OM
OOM
OOM
OOM
OOM
1.2C-IInert Greedy
171.778
7.408%
5.28m
242.757
7.419%
10.53m
L22C-Inset (7=200)
169.802
6.173%
8.35m
241.194
6.728%
13.60n m0.
L2C-IIneet (7=1000)
166.063
3.835
20.83m
237.109
4.920%
26.07m
CVRP50K
CVRP100K
Method
Length
Gap
Time
Length
Gap
Time
HGS
1081.0
0.000
64h
2087.5
0.000%
100.8h
INVIT-3V greedy
1331.1
23.136%
46.4h
2683.4
28.546%
93h
BQ bs16
OOM
0OM
OOM
OOM
OOM
OOM
LEHD RRC1000
0OM
0OM
OOM
OOM
OOM
OOM
L,CC- Insert Greedy
1188.084
9.906
14.49m
227 1.22
8.804%
29.95m
1.2C- (T=200)
1184.744
9.597%
20.90m
2268. 146
8. 8.654
37.67m
L2C-Insert (7=1000)
1174,208
8.622%
47.63m
2258.005
8,168 %
1.16h
Table 3: Comparison result for appending- and insertion-based constructive heuristics on TSPLIB and CVRPLIB instances.
TSPLIB
CVRPLIB
Method
N<=200
200<N<<1K
Ncc200
200<N<<IK
NeurOpt
9.456%
26.345%
16.350%
24.878%
25.301%
25. 35.190%
UDC-X250 (a = 50)
0.533%
6.578%
3.072%
9.635%
8.864%
9.033%
GLOP
0.561%
2.012%
1.153%
INVIT-3V 16
2.238%
5.654%
3.673%
8.231%
11.504%
10.784%
ELG
1.180%
5.910%
3.111%
4.510%
7.752%
7.039%
POMO augx8
2.022%
21.447%
9.951
6.869%
46.984%
38.159%
BQ hs 16
1.289%
1.946%
1.557%
7.661%
8.1955
8.078%
LEHD RRC1000
0.215%
0.620%
0,380%
2.022%
3.932%
3,512%
L2C-IIsert (7=1000)
0.197%
0,468 %
0.308 %
1.604%
3.651 %
3.201 %
Inference & Metrics For inference, the I.2C-Insert model first generates an initial solution through greedy rollout, then progressively refines solution quality via insertion-based local reconstruction. The number of iterations is denoted as "/=". Following [23], we accelerate inference by processing only the k-nearest unvisited nodes and positions of the current node, with set to 100 for TSP and 200 for CVRP. To further accelerate this process, we limit the local reconstruction destruction size to 300 across all instances. Following [40]. to enhance the consistency of inputs for our model on large-scale instances with more than IK nodes, we employ min-max feature scaling, which adjusts the x-axis and y-axis coordinate values to the interval [0. 1]. A hyperparameter study and discussion on these settings are provided in Appendix D For performance evaluation, we measure: 1) average tour length (Length), 2) performance gap relative to baseline solvers (Gap), and 3) total inference time (Time). Note that reported inference times for classical CPU-based solvers are not directly comparable GPU-executed learning-based methods.
4.1 Comparative Results
Tables [ and present the comparative results on uniformly distributed TSP and CVRP instances scaling from 100 100K nodes. These results show that L2C-Insert consistently achieves outstanding performance across these scales with a reasonable runtime. On TSP100, L2C--Insert (I=200) reduces the gap of the advanced NCO baseline LEHD+RRC1000 by 12.5% with speedup of 1.4x. On T.PIK, L2C-IInset (I=1000) achieves significant reduction of 34.2% while with a speedup of 6.7x compared to LEHD+RRC1000.
TSPI0K. LnCC-Insert (/=1000) outperforms the strong heatmap-based solver DIFUSCO and two-stage solver GLOP with 19. 19.4% and 54.3% gap reduction, while with 2.8x and 1 1.5x speedup, respectively. TSP50K and TSP100K, L22C-Insert (7=200) outperforms the two-stage NCO method GLOP with a gap reduction of 24.8% and 4.3%, respectively.

---

On CVRPI00, L2C- (I=1000) outperforms LEHD RRC1000 by 1.7%, and on CVRPIK it achieves competitive gap while with a speedup of 2x. On CVRPIOK, L2C-IInert (I=1000) outperforms LEHD RRC1000 with speed-up of 14x. On CVRP50K and CVRP100K, 1.2C-Insert using greedy rollout achieves significant gap reductions of 62.7% % and 71 71.4% respectively, compared to INVIT. Overall, our method shows good scalability and can achieve outstanding performance across small-scale to very large-scale problem instances with up to 100K nodes. The experimental results on real-world TSPLIB and CVRPLIB instances are provided in Table 3 These results show that L2C- Insert consistently outperforms representative neural solvers on all instance groups, demonstrating robust generalization ability.
4.2 Ablation Study
Learning to Append vs. Learning to Insert We conduct a comparative evaluation between two constructive NCO approaches: learning to append (L2C-Append) and learning to insert (L2C-Insert). While L2C-Append shares a similar model architecture with InC--Inser, utilizes an appending construction framework akin to LEHD (2). Both models are trained TSP100 under identical budgets and subsequently evaluated on TSP100, TSPIK, and TSPIOK datasets. For inference, we apply local reconstruction with 200 and 1000 iterations using the aforementioned settings. As detailed in Table 4 1.2C-Insert, with only 200 reconstruction iterations, outperforms 1.2C-Append even when the latter uses 1000 iterations of local reconstruction while also consuming less runtime. Remarkably, InsC-Insert (7=1000) outperforms I. 1.2C-Append (7=1000) by achieving substantial gap reductions of least 50.6% on these datasets. These findings highlight that the L2C-IInert framework's s greater flexibility in solution construction directly contributes to its superior performance.
Table 4: Appending- -based Construction vs. Insertion-basee Construction. The best gap is indicated in bold, and the second-best is underlined.
TSP100
TSP1000
TSP10000
Method
Gap
Time
Gap
Time
Gap
Time
L2C-Append
(/=200)
0.00489%
28. 03m
1.159%
3.49m
22.986%
4.11m 16.30m
(d=1000)
0.00144%
2.28h
0.974%
16.88m
12.881%
L2C--Inset
(/=200)
0.00142%
1.62h
0.952%
9.52m
4.117%
4.14m
(/=1000)
0.00017% %
8h
0.481
46.4m
2.079%
16.64m
Effect of Destruction Strategy We ablate the effect of distance-based strategies on local reconstruction. Specif- ically, on TSPIK and TSP10K, we test the L2C-IIsert model using local reconstruction (I=1000) with the distance- based and sequence-based destruction separately. As demonstrated Table the distance-based destruction strategy achieves substantially better performance, indicat- ing its greater effectiveness in helping local reconstruction escape local optima.
Table 5: Effect of deconstruction strat- egy.
TSP1000 Gap
TSP10000
Method
Gap
Sequence-based
1.2% 0.481 %
6.980% 2.079 %
Distance-based
Additional Analysis & Discussion We further investi-
gate the impact of: 1) different distinct distance metrics (Euclidean vs. Polar Angle): 2) the use of different node selection strategies (Random vs. Nearest); 3) the incorporation Positional Encod- ings (36] into embeddings of positions within the partial solution; 4) the exclusion of unvisited nodes as decoder input; and 5) the use of different backbone models for L2C-Insert framework. Detailed results and the corresponding discussion provided in Appendix E
5 Conclusion, Limitation, and Future Work
Conclusion In this work, we have proposed L2C- Insert, a novel learning to insert framework to explore the potential of the insertion paradigm for constructive NCO. By strategically inserting unvisited nodes at any valid position within the partial solution, 1.2C-Insert can flexibly construct high-quality solutions for routing problems. Extensive comparisons with advanced neural solvers demonstrate InC--nsert's 'ss outstanding performance TSP and CVRP.

---

Limitation and Future Work First, although L2C-IIneer has demonstrated outstanding perfor- mance. its performance could be further boosted through the development of more effective model architectures. These improved architectures would better capture the intricate relationships between current nodes, unvisited nodes, and positions within partial solutions. Second, designing hybrid NCO solver that combines both appending and inserting moves is highly promising research direction. Such a model has the potential to be more flexible and powerful than a model restricted to single type of move. In addition, a limitation may be the greedy, non-learned nearest-neighhor heuristic used for node selection. A promising research direction is to develop a learned policy that works synergistically with the insertion model, potentially through joint two-stage training. Finally, extending the L2C-Insert framework to address a broader range of combinatorial optimization problems is another promising research direction for future work.
Acknowledgments and Disclosure of Funding
This work was supported in part by the National Natural Science Foundation of China (Grant 62476118, 18, Grant 12426305), the Natural Science Foundation of Guangdong Province (Grant 2024A151501 1759), the Guangdong Science and Technology Program (Grant 2024B TABBB122000000 the Center for Computational Science and Engineering at Southern University of Science and Tech- nology, the National Key Research and Development Program of China (Grant 0022YFA1004000 and the Research Grants Council of the Hong Kong Special Administrative Region, China (GRF Project No. CityU 11212524).
References
[1] Bruce I. Golden, S Raghavan, and Edward A Wasil. The Vehicle Routing Problem: Latest Advances and New Challenges, volume 43. Springer Science & Business Media, 2008
[2] Victor Pillac, Michel Gendreau, Christelle Guéret, and Andrés Medaglia, A review dynamic vehicle routing problems. Eurppea Journal of Operational Research, 225 (21(1):1111, 2013.
[3] Grigorios D Konstantakopoulos, Sotiris P Gayialis, and Evripidis P Kechagias. Vehicle routing problem and related algorithms for logistics distribution: litcrature review and classification. Operational research, 22(3):2033-2065 2022.
[4] Jennifer AN Brophy and Christopher A Voigt. Principles of genetic circuit design. Nature methods, 11(5): 508 520, 2014.
[5] Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti- Spachell-Saa and Marco Protasi. Complexity and approximation: Combinatorial optimization problems and their approximability properties. Springer Science & Business Media, 2012.
[6] Oriol Vinyals. Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, volume 28, 2015.
[7] Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv: 1611009900 2016.
[8] Le-yang Gao, Rui Wang, Chuang Liu, and hhao-hong Jia. Multi-objective pointer network combinatorial optimization. arXiv preprint arXiv:2204. 1860, 2022.
[9] Zhi Zheng, Shunyu Yao, Genghui Li. Linxi Han, and Zhenkun Wang. Pareto improver: Learning improvement heuristies for multi-ohjective route planning. IEEE Transactions on Intelligent Transportation Systems, 2531):0033-1043 2024. doi: 10.1109/TTTS.. 201.T...22..333366 3688..
[10] Rui Sun, Zhi Zheng, and Zhenkun Wang. Learning encodings for constructive neural combinatorial optimization needs to regret. Proceedings of the AAAI Conference on Artificial Intelligence, 38(18): 20803 2081 1, Mar. 2024, doi: 10. 10.1669/aaiivv8ii 30009, URL/attps://oos. aaai orr/ worg//nde.....r.oo php/ AAAT AMA//articcle/vee//00065
[1I] Zhi Zheng, Zhuoliang Xie, Zhenkun Wang, and Bryan Hooi. Monte carlo tree search for comprehensive exploration in LLM--ased automatic heuristic design. In International Conference on Machine Learning, 2025. URL /tLtatts:://opereeeee http:p///ppppeeeeeeeee/////////p
10

---

[12] Ni Zhang, Jingfeng Yang. Zhiguang Cao, and Xu Chi. Adversarial generative flow network for solving vehicle routing problems. In International Conference Learning Reprexentations, 2025. URL https //openreview net www.:eorumiddd-tooaaeeeee
[13] Kai Li, Ruihao Zheng, Xinye Hao, and Zhenkun Wang. Multi-objectiive infeasibility diagnosis for routing problems using large language models. arXiv preprini arXiv:2508.03444 2025.
[14] Kai Li, Fei Liu, Zhenkun Wang, Xialiang Tong, Xiongwei Han, Mingxuan Yuan, and Qingfu Zhang. Ars: Automatic routing solver with large language models. arXiv preprint arXiv:2502. /5359, 2025.
[15] Changliang Zhou, Canhong Yu, Shunyu Yao, Xi Lin, Zhenkun Wang, Yu Zhou, and Qingfu Zhang. Urs: A unified neural routing solver for cross cross-problem zero-shot generalization. arXiv preprint 2rXiv2250..34413 2025,
[16] Changliang Zhou, Xi Lin, Zhenkun Wang, and Qingfu Zhang. Learning to reduce search space for generalizable neural routing solver. arXiv preprint 2xXxx:5503001333 2025.
[17] Han Li, Fei I. Liu, Zhi Zheng, Yu Zhang, and Zhenkun Wang. CaDA: Cross-problem routing solver with constraint aware dual-attention. In International Conference on Machine Learning, 2025. URL https://openrevievv
[18] Luo, Yaoxin Wu, Zhi Zheng, and Zhenkun Wang. Rethinking neural combinatorial optimization for vehicle routing problems with different constraint tightness degrees, 2025. [RI.httpss:// //triv/./rr//////////// abs/2506. 24627
[19] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
[20] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d' d'rorizon. European Journal of Operational Research, 290(2):405 421, 2021.
[21] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pages 21 188-21198, 2020.
[22] Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Advances in Neural Information Processing Systems, 2023.
[23] Darko Drakulic, Sofia Michel, Florian Mai, Araad Sors, and Jean-Mare Andreoli. BQ-NCO: Bisimulation quotienting for efficient neural combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
[24] 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 arXiv:2401.06993 2024.
[25] Changliang Zhou, Xi Lin, Zhenkun Wang, Xialiang Tong, Mingxuan Yuan, and Qingfu Zhang. Instance- conditioncd adaptation for large-scale generalization of neural combinatorial optimization. arXiv preprint arXiv:2405.0 007900000............. 2024.
[26] Fu Luo, Xi Lin. Yaoxin Wu, Zhenkun Wang, Tong Xialiang, Mingxuan Yuan, and Qingfu Zhang. Boosting neural combinatorial optimization for large-scale vehiele routing problems. In International Conference on Learning Representations, 2025. lttpp:/:s:///opp
net/ foooooidddduunnnne
[27] Ilya Sutskever, Oriol Vinyals, and Quoe V Le. Sequence sequence learning with neural networks. Advances in neural information processing systems, 27, 2014.
[28] Daniel J Rosenkrantz, Richard E Stearns, and Philip M Lewis, II. An analysis of several heuristics for the traveling salesman problem. SIAM journal computing, 6(3):563-581, 1977.
[29] Fei Liu, Chengyu Lu, Lin Gui, Qingfu Zhang, Xialiang Tong, and Mingxuan Yuan. Hcuristics for vehicle routing problem: A survey and recent advances. arXiv preprint 203.44230 2023.
[30] Chengrui Gao, Haopu Shang. Ke Xue. Dong Li, and Chao Qian. Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy. In International Joint Conference Artificial Intelligence, 2024.
[31] Jonathan Pimay and Dominik G. Grimm. Self improveppoeeennt for neural combinatorial optimization: Sample without replacement. but improvement. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. Featured Certification.
11

---

[32] Zhi Zheng, Changliang Zhou, Tong Xialiang, Mingxuan Yuan, and Zhenkun Wang. UDC: A unified neural divide-and-conquer framework for large-scale combinatorial optimization problems. In Advances in Neural Information Procexsing Systems, 2024.
[33] André Hottung, Mridul Mahajan, and Kevin Tiemey. Polynet:
Learning diverse solution strategies for neural combinatorial optimization. In International Conference on Learning Representations. 2025. URL
https://openrevieeu
[34] Jacques Renaud, Fayez, Boctor, and Jamal Ouenniche. heuristic for the pickup and delivery traveling salesman problem. Computers & Operations Research, 27(9)) 916, 2000.
[35] Refael Hassin and Ariel Keinan. Greedy heuristics with regret. with application to the cheapest insertion algorithm for the isp. Operations Research Letters, 36(2):243-246, 2008.
[36] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, volume 30, 2017.
[37] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Reprexentations, San Diega, CA, USA, 2015.
[38] André Hottung and Kevin Tierney. Neural large neighborhood search for the capacitated vehicle routing problem. In European Conference on Artificial Intelligence, 2020.
[39] Minsu Kim, Jinkyoo Park, et al. Learning collaborative policies to solve np-hard routing problems. In Advances in Neural Information Processing Systems, volume 34, pages 10418-10430 2021.
[40] Haoran Yc, 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, 2024.
[41] David Applegate, Ribert Bixby, Vasek Chvatal, and William Cook. Concorde tsp solver, 2006.
[42] Thibaut Vidal. Hybrid genetic search for the evrp: Open-source implementation and swap" neighborhood. Computers & Operations Research, 140:105643 105643, 2022.
[43] Zhang-Hun 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.
[44] Qingehun Hou, Jingwei Yang, Yiqiang Su, Xiaoqing Wang, and Yuming Deng. Generalize learned heuristies solve large-scale vehicle routing problems real-time. In International Conference on Learning Representations, 2023.
[45] Fu Luo, Xi Lin, Zhenkun Wang, Tong Xialiang, Mingxuan Yuan, and Qingfu Zhang, Self-improved learning for scalable neural combinatorial optimization. arXiv preprint arXiv:2403. 19561, 2024.
[46] Gerhard Reinelt. TSPLIB-a traveling salesman problem library. ORSA Journal on Compuring, 3(4): 376-384, 1991.
[47] Eduardo Uchoa, Diego Pecin, Artur Pessoa, Mareus Poggi. Thibaut Vidal, and Anand Subramanian. New henchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3):845-8588 2017.
[48] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019. URL htLLhttps://ppereviiii
[49] Keld Helsgaun. An extension of the beeemighann-helggau tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12, 2017.
[50] Han Fang, Zhihao Song, Paul Weng, and Yutong Ban. INVit: A generalizable routing problem solver with invariant nested view transformer. In International Conference on Machine Learning, 2024.
[51] Zhiqing Sun and Yiming Yang. DIFUSCO: Graph-based diffusion solvers for combinatorial optimization. In Advances in Newral Information Processing Systems, 2023.
[52] Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. From distribution learning in training to gradient search in testing for combinatorial optimization. In Advances in Neural Information Processing Systems. 2023.
12

---

[53] Xuanhao Pan, Yan Jin. Yuandong Ding, Mingxiao Feng, Li Zhao, Lei Song, and Jiang Bian, H-tsp: Hierarchically solving the large-scale traveling salesman problem. In Proceedings the AAAI Conference on Artificial Intelligence, February 2023.
[54] Hanni Cheng, Haosi Zheng, Ya Cong, Weihao Jiang, and Shiliang Pu. Select and optimize: Learning to aolve large-scale tsp instances. In International Conference on Artificial Intelligence and Statistics, pages 1219 1231. PMLR, 2023.
[55] Yining Ma, Zhiguang Cao, and Yeow Meng Chee. Learning to search feasible and infcasible regions of routing problems with flexible neural k-opt. In Advances in Neural Information Processing Systems, volume 36, 2023.
[56]
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, volume 31, 2018
[57] Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems, volume 30, 2017.
[58] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Step-wise deep learning models for solving routing problems. IEEE Transactions Industrial Informatics, 17(7):4861-487 2020.
[59] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. glimpse for solving vehicle routing problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 12042-12049, 2021.
attention model with embedding
[60] André Hottung, Yeong-Dac Kwon, and Kevin Tiemny. Efficient active search for combinatorial optimization problems. In International Conference on Learning Representations, 2022.
[61] Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-NCO: Leveraging symmetricity for neural combi- natorial optimization. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[62] Jinho Choo, Yeong-Dae Kwon, Jihoon Kim, Jeongwoo Jae, André Hottung, Kevin Tiemny, and Youngjune Gwon. Simulation- guided beam search for neural combinatorial optimization. In Advances in Neural Information Processing Systems, volume 35, pages 8760 07000-7772000 2022.
[63] Jieyi Bi. Yining Ma. Jiahai Wang. Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng Chee. Learning generalizable models for vehicle routing problems via knowledge distillation. In Alice Oh, Alckh A Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[64] Yan Jin, Yuandong Ding, Xuanhao Pan, Kun He, Ziao, Tao Qin, Lei Song, and Jiang Bian. Pointerformer: deep reinforced multi-pointer transformer for the traveling salesman problem. In Proceedings of the AAAI Conference on Artificial Intelligence, 2023.
[65] Yubin Xiao, Di Wang, Boyang Li, Mingzhao Wang. Xuan Wu, Changliang Zhou, and You Zhou. Distilling autoregressive models to obtain high- perforeefor non-auvoregressive solvers for vehicle routing problems with faster inference speed. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pages 20274-20288 2024.
[66] Jicyi Bi, Yining Ma, Jianan Zhou, Wen Song, Zhiguang Cao, Yaoxin Wu, and Jie Zhang. Learning to handle complex constraints for vehicle routing problems. In Advances in Neural Information Processing Systems, 2024. ttttp::
[67] Rui Sun, 7hi 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.
[68] Zhi Zheng, Shunyu Yao. Zhenkun Wang, Tong Xialiang, Mingxuan Yuan, and Ke Tang. DPN: Decou- pling partition and navigation for neural solvers of min-max vehicle routing problems. In International Conference on Machine Learning, 2024. /ttptttpp///perrevvee.. wwwe///orummdaaattteee
[69] Ziwei Huang, Jianan Zhou, Zhiguang Cao, and Yixin XU. Rethinking light bacoder-based solvers for vehicle routing problems. In The Thirteenth International Conference on Learning Representations, 2025. URL htttpss//oppereviieeee
13

---

[70] Darko Drakulic, Sofia Michel, and Jean-Mare Andreoli. GOAL: A generalist combinatorial op-
timization agent learner. In International Conference on Learning Representations, 2025. URL
https://openreviee.. http:://ggeerrrrrreee////eoreeee wtt///ooruurrdddd2222000
[71] Changliang Zhou, Xi Lin, Zhenkun Wang, and Zhang. 1.2r: Learning to reduce search space for generalizable neural routing solver, 2025. https://arxxvvorr//maatt awtgg//aa/2503.... 03137
[72] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint
01227, 2019.
[73] Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. DIMES: A differentiable meta solver for combinatorial optimization problems. In Advances in Neural Information Processing Systems, 2022.
[74] Yifan Xia, Xianliang Yang, Zichuan Liu, Zhihao Liu, Lci Song, and Jiang Bian. Position: Rethinking post- hoc search- based neural approaches for solving large-scale traveling salesman problems. In International Conference on Machine Learning, 2024. URL httpp::://///
[75] Yang Li. Jinpei Guo, Runzhong Wang. Hongyuan Zha, and Junchi Yan. Fast 12t: Optimization consistency speeds up diffusion-based traiiing-to-tsttinn solving for combinatorial optinizzion.. In Advances in Neural Information Processing Systems, 2024. URL httpgg///opperrrrreeeeeeerrrrtts
[76] Xinyun Chen and Yuandong Tian. Learning perform local rewriting for combinatorial optimization. In Advances in Neural Information Processing Systems, volume 32, pages 6281-6292, 2019.
[77] Paulo R O Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akeay, Learning 2-opt heuristies for the traveling salesman problem via deep reinforcement learning. In Asian Conference on Machine Learning, pages 465-480. PMLR, 2020.
[78] Yining Ma, Jingwen Li. Zhiguang Cao, Wen Song. Le Zhang, Zhenghua Chen, and Jing Tang. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. In A. Beygelzimer. Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[79] 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, 2021.
180] Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehiele routing. In Advances in Neural Information Processing Systems, volume 34, pages 26198-2622 2021.
[81] Yining Ma, Zhiguang Cao, and Yeow Meng Chee. Learning to search feasible and infeasible regions of routing problems with flexible neural k-opt. In Advances in Neural Information Processing Systems, volume 36, 2024.
[82] Zefang Zong, Hansen Wang, Jingwei Wang, Meng Zheng, and Yong Li. Rbg: Hicrarchically solving large-scale routing problems in logistic systems via reinforcement learning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4648-4665 2022.
[83] Liang Xin. Wen Song, Zhiguang Cao, and Jie Zhang. Neurolkh: Combining deep learning model with lin nn-kkeiighhn--hhlee helssauu heuristic for solving the traveling salesman problem. In Advances in Neural Information Processing Systems, volume 34, pages 7472-7483, 2021.
[84] Arthur Delarue, Ross Anderson, and Christian Tjandraatmadja. Reinforcement learning with combinatorial actions: An application to vehicle routing. Advances in Neural Information Processing Systems, 33: 609-620, 2020.
[85] André Hottung, Paula Wong-Chung, and Kevin Tiemey. Neural deconstruction search for vehicle routing problems. Transuctions on Machine Learning Research, 2025. ISSN 2835-8856. URL / openreviev. wtt.:e/w.nnt//ooumiidddoooo
[86] Eric Taillard and Keld Helsgaun. Popmusic for the travelling salesman problem. European Journal of Operational Research, 272(2):420 429, 2019.
[87] Zhang- Hua Fu, Sipeng Sun, Jintong Ren, Tianshu Yu, Haoyu Zhang, Yuanyuan Liu, Lingxiao Huang, Xiang Yan, and Pinyan Lu. A hicrarchical destroy and repair approach for solving very large-scale travelling salesman problem. arXiv preprint arXiv:2308.046:: 2023.
[88] Christian Nilsson. Heuristics for the traveling salesman problem. Linkoping University, 38(00085 99:26. 2003.
14

---

[89] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-778, 2016.
[90] Sergey Toffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference Machine Learning, pages 448 448-456. pmir, 2015,
15

---

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: Our abstract clearly reflects the scope (Constructive Neural Combinatorial Optimization), and our introduction clearly summarizes our contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in 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.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The paper discusses the limitations of the work in Section
Guidelines:
The answer NA means that the paper has no 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 a separate "Limitations" section 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 how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low 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 of 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 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.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
16

---

Justification:
The claim of this paper is supported by experimental results.
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 referenced in the statement of any theorems.
The proof' can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch 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 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 of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide the detailed experiment setting in Section 4 hyperparameter settings in Appendix D and implementation Appendix which fully sufficient for
reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all 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 new 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 instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe 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 or verifying the results.
5. Open access to data and code
17

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
See the abstract for the link to the code and trained models.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nnis.cce
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" 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 NeurlPS code and data submission guidelines (https
/tipsscccpubllc/gu..doo
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they 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 provide the detailed experiment setting in Section 4 hyperparameter settings in Appendix D and implementation in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to 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
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: In the field of NCO, the performance of methods is typically not evaluated by error bars or statistical significance. Instead, NCO methods conventionally keep the same seed (seed=123 in work) during training/inference, and use the objective value (Obj.), optimality gap (Gap), and inference time (Time) as metrics to evaluate method performance. A detailed description of these metries provided in Section 4
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
18

---

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 run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to 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 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 error rates).
If error bars 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 to reproduce the experiments?
Question:
Answer: Yes
Justification:
We describe the compute resources in Section 4
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http::://eurrpp..ccppaa///ttttb
Answer: [Yes]
Justification: Ethics.
Our research conducted in the paper conforms with the NeurIPS Code of
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: As learning- cearning-based based method for solving VRPs, the proposed method does not have any specific potential negative societal impact. Detailed discussion can be found in Appendix O discussion.
Guidelines:
19

---

The answer NA means that there is no societal impact of the work performed.
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), fairness 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 not 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.
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 a 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 poses such risks.
Guidelines:
The answer NA means that the paper poses no 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 we 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 have properly cited the assets (e.g., code, data, models) in section P
Guidelines:
The answer NA means that the paper does not use 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.
20

---

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.papersstt
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if 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]
The datasets utilized in this paper either sourced from prior research or generated using methodologies established in earlier studies. We have appropriately cited them.
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing 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 as details about compensation (if any)?
Answer: [NA]
Justification: This paper studies the neural method for solving TSP and CVRP.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in 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 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 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper studies the neural method for solving TSP and CVRP, which does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
21

---

Depending on 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.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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 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, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy ottp:e///eerrrpo.cccoo/oeeeereee for what should or should not be described.
22

---

A Related Work
A.1 Constructive NCO Methods
Constructive NCO methods typically arrange the input nodes into high-quality solutions autoregres- sively. This paradigm inspired by the sequence-to-sequenee processing (NLP), where a model encodes an input sequence into an embedding and then autore- gressively generates an output sequence based on this representation. Vinyals et al. [ pioneer this adaptation through their Pointer Networks (Ptr-Nets), which establishes the first sequence-to- sequence framework specifically for neural combinatorial optimization. In this paradigm, the neural model learns to predict the probability of appending the unvisited nodes to the partial solution until all nodes are visited. We call this paradigm Learning to Append (L.2C-Append), Subse- quent research has further advanced 1.pn-A NCO methods, with improvements focusing on model training techniques 77. extension to solve other COPs Nazari et al. (56), and architectural enhancements [19]. Among them, the Attention Model [9] introduces the Transformer- bassed model structure [36]. which achieves outstanding performances over various VRPs with up to 100 nodes. Various AM- based improved variants proposed to narrow the performance gap classical heuris- 66
framework (27 in natural language
69 26 70, (1].. For example, PolyNet [33 enhances exploration by learning diverse set of complementary solution strategies in single model. By conditioning the solution generation process on a simple bit vector, PolyNet can generate diverse solutions without relying on handcrafted rules or forced initial moves. Nonetheless, I.2C-Append NCO methods are fundamentally limited by their restriction to appending new nodes, which can lead to suboptimal solutions due to early greedy choices. In contrast, the insertion-based paradigm offers greater flexibility for VRPs by sequentially inserting unvisited nodes into any valid position [28, 29) potentially yielding higher-quality solutions. Despite these benefits, the insertion-based constructive approach has remained unexplored in NCO for VRPs in the last decade. In this work, we introduce InC--nsert, novel learning to insert framework, to investigate the potential of this paradigm for constructive NCO.
tic solvers (37 21 68 22 23
65
39
40
67
A.2
Non-constructive NCO Methods
This series of methods can be broadly categorized into three main groups: (1) Heatmap-based methods: These methods learn graph neural networks to predict a probability distribution, or heatmap, indicating the likelihood of each edge being part of the optimal solution for a given problem instance. Once the heatmap is obtained, it is used to guide subsequent decoding techniques such as greedy search, beam search 72), Monte Carlo Tree Search (MCTS) 43 73 74,, 2-opt [5] (2),
or gradient search 775 to generate the solution. While this approach can successfully solve TSP instances of various sizes, its application other routing problems like CVRP generally more challenging. (2) Improvement-baseee
methods: These approaches iteratively refine solution quality, They employ neural models to predict regions within current solutions where heuristic operators, such as k-opt (55) and swap (76), can be applied to improve the solution quality 877-8] (38 (3) Two-stage
Method: Two-stage methods: These methods address the problem through an iterative divide-and- conquer process. In each iteration, the problem is first decomposed into multiple subproblems using rule-based techniques or neural models. Subsequently, neural solvers (e.g., AM (19) or classical
solvers (e.g.. LKH3 49 or HGS =2]) are used to solve these subproblems. The resulting partial solutions are then merged to form a complete solution 82
32 40). Beyond these primary categories, other constrssteee NCO approaches include learning to augment classical solvers with neural components [83] or solving VRPs at a route level [84). A different approach is Neural Deconstruction Search (NDS) [85]. NDS uses a learned neural policy to iteratively deconstruct solution by selecting customers to remove. These customers are then reinserted one by one using rule-based greedy heuristic algorithm. In this paper, we develop constructive neural model that leamss the insertion-ban based heuristic, building solutions autoregressively.
80
44
23

---

B Implementation Details of L2C-Insert on CVRP
Problem Formulation A CVRP instance can be represented as graph with one depot node and customer nodes, and vehicle with fixed capacity C. Each node i E {0, 1,..., n is associated with feature vector 8; R², representing its two-dimensional coordinates and demand. Node the depot, and its demand is zero.
For any given CVRP instance, the solution set of routes for the vehicle to serve all customers. such that: (1) Each customer is visited exactly once. (2) Each route must start from and end with the depot. (3) The total demand on each route does not exceed the vehicle's 's capacity. The objective of solving CVRP is to determine the optimal solution such that the total cost of the routes, typically the total distance traveled, is minimized.
Solution Construction Process Initially, all customer nodes unvisited. In the first step, the depot node and its nearest unvisited node initialize the incomplete solution. We call the node selected in the last step last node and the node selected in the current step current node. In each step except the first step, only the unvisited customer nodes can be selected as the current node. In each following step, the model predicts both the probability of 1) inserting the current node for each available position in the incomplete solution and 2) inserting it into the middle of the two copies of the depot nodes initiate new route.
Remaining Capacity During solution construction, the remaining capacity associated with each route is calculated by using the vehicle's capacity minus the total demand of this route so far.
B.1 Encoder
The encoder transforms each node feature 8; E projection:
R to node embeddings h, E Id by a linear
h = s, (o) + b
Vi = -01.....,
(4)
where W7()) E Rxdd ((0) E Rd are learnable parameters. These initial embeddings are subsequently updated through the attention layer (2 22 to produce the refined embeddings h; E IRd, which is the output of the encoder.
B.2 Decoder
At construction step the decoder receives the embeddings of all nodes, denoted h, RR
1 1...., ni the current partial solution (0, T1, T2, O,.... ,, 0) (Node O denotes the depot), and the set of unvisited nodes (u,, Mj {= J. To compute the probability of insertion at the current step, embeddings for three distinct inputs are required: 1) the current node (the node to be inserted),
2) unvisited nodes, and 3) the positions in the partial solution.
Embeddings of Positions in the Current Partial Solution The unvisited node with the minimum Fuclidean distance to the last node is selected as the current node to be inserted, of which the embedding is denoted as hy Secondly, the embeddings of the remaining unvisited nodes can be denoted as H₁ {bu,, J uj & { u * uc. Two learnable linear projections Wo E Rdxd and W1 Rdddd are applied to the current node's embedding and each unvisited node's embedding, respectively
Embeddings of the Current Node and Unvisited Nodes insertion position within the partial solution, the embeddings of adjacent visited nodes are horizontally concatenated. For example, for a partial solution:
To generate the embedding of a potential
+ -
+
where the positions are indicated by these arrows. The arrow from the tail to the head (0 <- 0) indicates the position that allows the current node to inserted to start a new route. To simplify the notation, assume the current incomplete solution is of length I, and the embeddings of the nodes
24

---

it are ( {1: :1). Then the set of embeddings of the positions in the partial solution can be denoted as {er). {1: : [], where
h,, h,41l e; [,, hi].
iE f1:11-11 i=4,
(5)
where [::]] is the horizontal concatenation operator. We note that both h1 and h, are the depot embeddings. To incorporate the remaining capacity information, position embedding by horizontally concatenating it with the remaining capacity of the route where the position located, increasing the embedding dimension by I. Subsequently, linear projection W2 E (24++))x applied to the updated position embedding to project to the embedding with the same dimension as the node embedding. The set of output position embeddings is denoted as He = [er: J E {1 1-1
decoder updates each
Then, these embeddings together are refined by L stacked attention layers. The first layer receives input X (hc. He. H.). with each subsequent j-th attention layer processing the output from the 1) layer, culminating in the final output X (4), This process can be denoted as:
H = (ttnLayer(H
H(2 AttnLayer(H
(6)
H(4) (ianLayer(HH(L-)))
Where the formulation of "AttnLayer" is detailed in Appendix N Then, a linear projection and softmax function are applied to X(L) to compute the insertion probabilities of the current node into all valid positions. The masking operation assigns -oo to invalid positions (those corresponding to the current node and non-visited nodes) to ensure proper probability normalization over valid insertion locations. The inserting probability p; is calculated as:
2;
X
W + by. Vi (1:1) 1) and the remaining capacity of the route where the position is located not less than the current node's demand,
0;
otherwise,
= Sof,max(a),
where W, E Rdx1 and by E R² are learnable parameters. where Wy E gdx1 and by E R are learnable parameters. Each p; p denotes the probability of inserting the current node between consecutive nodes (T;, 7s+1) in the partial solution. The decoder executes this sampling-and-insertion procedure n times to construct the complete solution {0, TT.....,..
.0.... .0.............................. }
B.3 Implementation of Insertion-based Local Reconstruction CVRP
In the main paper, we introduce the process of insertion- based local reconstruction on TSP. This process remains nearly the same in CVRP, which is described follows:
Solution Initialization The initial solution also generated by the model through a simple greedy rollout.
Distance-based Destruction In the CVRP case, also destroy the solution by the node's neighbor relationship in terms distances. Specifically, we first randomly sample a customer node. Then, select its c-nearest neighbor customer nodes and remove them unvisited nodes, the left solution automatically creates an incomplete solution with multiple looped routes. Here, we refer to the destruction size. For example, if CVRP10 solution is (0, mi T2, O, T3. T4, R5, 0, No: T7, 0, 7g, .g. Tin, 0), the node गड is randomly sampled, and its 3-nearest neighbors are {Ti, T3, me). then they are removed from the solution to unvisited nodes. The left incomplete solution is (0, π2, 0, n4, O, n7, O, ns, Tg, Ti0, 0).
Insertion- Reconstruction The model inserts the unvisited nodes to the incomplete solution node by node. Initially, the last node is randomly selected from the incomplete
25

---

solution. The subsequent procedures are the same those for greedy rollout. When all nodes are visited, a new complete solution is generated. We compare the previous solution with the new one, accepting the higher-quality solution for the next destruction- reconstruction cycle. This iterative process continues until the computational budget (e.g.. maximum iterations or time) is reached.
Padding for Solution Misalignment Since the solution to each CVRP instance may involve a different number of depot visits, the resulting solution lengths can vary when solving multiple CVRP instances batches. address this issue, we apply simple padding technique by adding extra zeros at the end of solutions with fewer depot visits. These extra zero pairs are then masked in the model.
C Implementation Details of Baselines
We compare 1.2CCInsert with comprehensive
of baseline methods including (1) Classical
Solvers: Concorde [41]
LKH3
[4)] and HGS 42]; (2) Constructive NCO Methods: POMO [1]]
BQ [23] LEHD 22 INVIT 500, and ELG (30 (3) Heatmap-based NCO Methods: Att-
GCN+MCTS |43, DIFUSCO [51] and T2T 522: (4) Two-stage NCO Methods: H-TSP (33
SO-mixed (54), GLOP 40), and UDC 40: (5) Improvement-basee NCO Methods: NeurOpt (55
For the heatmap-based based methods, we directly use their reported results. For SO-mixed, as their source codes not released available, choose to directly report their original results. However, the same test datasets for fair comparison (all these methods used the same TSPIK and TSP10K test datasets from Fu et al. [3)). For other methods, if not otherwise stated, we directly their source codes with the default settings.
Conconde 41] We run the Python wrapper for the concoder, namely PyConcorde. We use the default settings across TSP instances of various sizes.
LKH3 49
We run the code provided by AM 199. For TSP100K, we use POPMUSIC 86 to reduce the complexity for pre-procsssing (by setting CANDIDATE SET TYPE= POP-
MUSIC and INITIAL PERIOD=1000), following the suggestion from Fu et al. 87 Other settings are default.
HGG 22
We run the Python wrapper for the HGS-CVRP solver, namely PyHygese.
LEHD
We limited the maximum destruction size of RRC to 1000 after observing that performance remained nearly unchanged when compared to cases without this restriction, while inference time increased significantly.
22
26

---

D Hyperparameter Studies
We conduct hyperparameter studies for the values of neighborhood size is and destruction size by running L2C-IInert using local reconstruction with 7=50 iterations.
D.1 Defining the Neighbor Unvisited Nodes and Positions
Neighbor Unvisited Node Given current node and unvisited node-set B, categorize the unvisited nodes B that are closer to the current node as neighbor nodes based on the distance.
Neighbor Position The position-node distance between the position and current node is measured by the smallest distance between the current node and the adjacent visited nodes of this position. Given a current node and position E, categorize the positions in E that are closer to the current node as neighbor positions based on the position-noo node distance.
D.2 On TSP
As detailed in 6 model performance initially improves with increase in destruction size from 100 to 300, beyond which it declines as the destruction size extends to 500. Consequently, we select an intermediate destruction size of 300 to achieve optimal performance. Furthermore, our analysis reveals that increasing the neighborhood size from 100 to 500 leads to progressively longer solution lengths. We hypothesize that the intricate interplay of numerous positions and nodes complicates the processing, thereby diminishing the model's effectiveness. Therefore, we set the neighborhood size 100 enable robust problem-solving while maintaining low runtime.
Table 6: Effect of the setting of neighborhood k and destruction size in inference stage on TSP10K.
Destruction Size
100
300
500
Length (Time)
Length (Time)
Length (Time)
100
76. 66.669 (1.32m)
76.573 (2.04m)
77.078 (3.94m)
Neighborhood Size k
200
78.407 (1.68m)
76.610 (3. mm)
78.320 (5.77m)
300
80.349 (2.26m)
78 78.983 (4.17m)
79.042 (7.29m)
500
81.448 (4.36m)
80.451 (7.48m)
79.150 (12.18m)
D.3 On CVRP
As indicated in Table model performance generally improves with increasing destruction size from 100 300, but declines when the destruction size further extends from 300 500. Consequently, we select an intermediate destruction size of 300 to achieve favorable results. Furthermore, with the destruction size at 300, the model exhibits significantly better performance when the neighborhood size is 200, leading us to choose this value for our experiments.
Table 7: Effect of the setting of neighborhood and destruction size a in inference stage on CVRPIK.
Destruction Size
100
300
500
Length (Time)
Length (Time)
Length (Time)
100
43.011 I (0.51m)
43.196 (0.71m)
43.530 (1.31m)
Neighhorhnod Size &
200
43.127 (0.95m)
42,783 (1.53m)
43.069 (2.78m)
300
43.030 (1.29m)
42.989 (2. (2m)
43.166 (3.81m)
500
43.178 (2.53m)
42.887 (4.37m)
43.204 (7.47m)
27

---

E
Additional Ablation Studies and Analysis
Each step in the insertion-basedd construction process is divided into two substeps: (1) selecting node from the unvisited nodes and (2) selecting an edge in the incomplete solution for insertion. In this paper, the second substep is conducted by the model, and the first substep is operated through predetermined rules. Specifically, for the first substep, we define the insertion node selected in the previous step as the last node, and the insertion node selected in the current step as the current node. The current node is the unvisited node closest to the last node. In this section, we study the impact of the distance criterion and the current node selection strategy on model performance. Beyond those, we also study the impact of adding the Positional Encoding [36] to the embeddings of the positions in the partial solution, the effect of unvisited nodes as decoder input, and the performance of LL2-IIneri using different backbone models.
E. Effect of Distance Criterion for CVRP
We test two classic distance criteria, Euclidean Distance and Polar Angle. For two customer nodes p (p1, P2) and q = (41, 92). Euclidean Distance defined as:d (p. q) v(pi q1)² + (p2 92)².
For Polar Angle, we must introduce the depot node d. (d,, d2) to serve as the Polar center. Then
it is defined as: (p q) = 10p- lal. where Op = arctan
2 22- and 0g arctan T2 (2-d2
-di are
pr
the angles formed by the lines connecting the depot de to the customer nodes p and q with respect to the horizontal axis.
We train and test the same model with these two distance criteria, maintaining the node selection strategy that the current node is the closest unvisited node to the last one. Both models are trained with the same budget mentioned in the main paper. We then test these models on CVRPI00 and EVRP10000 using greedy rollout. The results, as shown in Table 8 indicate that the model trained and tested with Polar Angle performs much better. This improvement can be attributed the nature of CVRP, where multiple routes are usually ordered around a central depot. Using polar angles tightly coupled to the solution structure of CVRP. a result, the model is easier to learn and ultimately achieves better performance. Therefore, we use the Polar Angle to measure the neighbor relationship on CVRP.
Table 8: Effect of distance criterion for CVRP.
CVRPI00 CVRP1000 Gap
Gap
Euclidean Distance
5.151% 3.892%
10.155% 8.009
Polar Angle
E.2
Effect of Node Select Strategy
We use two different current node selection strategies described in Nilsson 88 for comparison:
Random: select an unvisited node randomly.
Nearest Neighbor: select the unvisited node that is nearest to the last node.
Specifically, we train the same models with two different current node selection strategies. The CVRP models use the same training budget mentioned the main paper, while TSP models are trained with budget of 10 epochs due to the runtime. We test these models on TSP100 and CVRP100 using greedy rollout. The results in Table 9 show that the nearest neighbor node selection strategy has the best overall result. Therefore, in this paper, choose to use it for the selection of the current node.
Table 9: Effect of selection strategy.
TSP100 Gap
CVRP100 Gap
Random
1.1557% 0.9535
11.370% 3.892%
Nearest Neighbor
28

---

E.3 Effect of Positional Encoding
We compare the performance of models with and without incorporating the Positional Encoding (PE) from [36] to the embeddings of positions in the partial solution. The models are trained on TSP100
with budget of epochs, and tested on TSP100 using greedy rollout. The results in Table T0 show that incorporating PE will damage both in-domain and out-of-domain performance. Therefore, this paper does not include the positional encoding our model.
Table 10: Effect of selection strategy.
TSP100 Gap
CVRP100 Gap
W/ PE 1.0475% 0.9535% %
5.802% 3.892%
W/o
E,4 Effect of Decoder Input of Unvisited Nodes
We compare the performance of models trained on TSP100 with and without inputting unvisited nodes to the decoder. The results in table shoooow that while inputting unvisited nodes the model results in additional computational cost, the performance improvement is significant, proving its indispensability.
Table 11: Training with unvisited node vs. without.
TSP10D
TSPIK
Method
Gap
Time
Gap
Time
W/o
5.161%
0.44m 0.86m
23.9799. 4.757% %
0.15m 0.36m
W/
0.460 %
Why the L2C-IInert Model Necessitates the Unvisited Nodes the Decoder Input To illustrate why this input is crucial, consider the example depicted in Figure Figure displays the optimal solution for TSP instance, while Figure 4 (b) shows intermediate state during the solution construction process. Without considering unvisited nodes, the insertion action shown in Figure (c). despite yielding better partial solution, constitutes a suboptimal choice when evaluated against the global optimum considering all nodes. In contrast, when unvisited nodes are factored in, the insertion action in Figure 4 (d), even though results in a partial solution with path intersections, identifiable as more globally optimal insertion by referencing the overall optimal solution. Therefore, insertions made without information about unvisited nodes tend be shortsighted. Incorporating unvisited nodes, however, provides the model with broader context, enabling more informed decisions for selecting insertion positions. Consequently, the InsC-Insert model needs to leverage information from unvisited nodes to mitigate such shortsightedness, thereby guiding the construction process towards higher-quality solutions.
E.5 Performance of I.2C-Insert using Different Backbone Models
We conduct experiments to investigate the performance of the proposed L2C-IInert framework under different backbone NCO models. Specifically, three recently proposed models are employed: POMO (21). LEHD [22), and INVIT [50). which feature 1, 3, and 6 decoder layers, respectively, each within a 7-layer overall model architecture. These models represent light, balanced, and heavy decoder architectures, respectively. Building upon these models, L2C-IIsert variants developed using the proposed L2C-Insert framework. These models are evaluated using the TSPLIB and CVRPLIB instances detailed in Section 4 Both the L2C-Append and L2C-Insert methods utilize one-shot greedy search for inference.
The experimental results are presented in Table 12 These results indicate that for the LEHD model, the In2C-Insert method outperforms the L2C-Append method on out 6 instance groups. Conversely, the I.2C-Insert method, when based the POMO model, generally underperforms the Appe-A method, proving inferior in 3 out instance groups, respectively. Similarly, the InC-rInert method, built upon the INVIT model, also generally underperforms L2C-Append,
29

---

Opeinal Training
Subaptinal
(di Optimal Insertion
Figure 4: figure
Example of a suboptimal insertion (not considering unvisited nodes) versus an optimal insertion (considering unvisited nodes). The red node is the current node insert.
showing inferiority in 6 of instance groups. These findings suggest that the L2C-Insert method may be more effective when utilized with a heavy decoder model. This advantage could stem from the complex position relationships within an incomplete solution and the current node being inserted during solution construction. Capturing these intricate relationships effectively necessitates, heavy decoder with sufficient model capacity to inform appropriate decisions regarding the correct insertion position.
Table 12: Performance of L2C-Insert and L2C-Append using different backbone models. These methods use the greedy rollout (Greedy) for inference.
Method
TSPLIB
CVRPLIB
(Using Greedy)
Nc=200
200<Nc=IK
All
Nc=200
200<N<<IIK
All
Perform Better #
POMO Insert
Append
5.325
35.337% 38.344%
17.575%
15.596%
41.759%
36.003%
3/6
19.111%
26.961%
14.650%
19.305%
18.281%
3/6
INVIT Append
2.788 3.961 %
6.315%
4.228
8.046
11.313%
10.594%
6/6
Insert
8.70%
5.653%
14.927%
22.55 1%
20.874%
0/6
LEHD
Append
1.922% 1.526%
3.646 % 4.382%
2.626%
11.346%
12.851%
12.520%
1/6
Insert
2.691% 1691%
10.903% %
9.548 %
9.846 %
4/6
F Discussion on the Advantage of the Insertion-based Construction Paradigm in Search
The iterative local reconstruction is significant factor in achieving the final reported performance. We believe the key innovation our work, the inertion-baseed policy, is what unlocks the true potential of this search procedure. The policy's inherent flexibility is key enabler for the search's effectiveness.
1. The advantage of insertion-based search
As discuss in Section 3.3 conventional appending- -opeed models face fundamental limitation when used with local search. When nodes are removed during the destruction phase, they can only be re-appended to the end of the sequence during reconstruction. This rigidity makes it difficult for the model to escape local optima. For instance, reconnecting two nodes that are geometrically close but far apart in the sequence common requirement for improving tour-is highly improbable.
Our L2C-IIneet framework directly overcomes this bottleneck. By allowing a node to be re-inserted at any valid position, our model facilitates a much more powerful and effective exploration of the solution space during the reconstruction phase. This flexibility the core reason why the wnwtroo--nddreeoosstee loop is effective in our framework.
30

---

2. Direct Ablation Study: Isolating the Policy's Contribution
To provide direct and fair comparison that disentangles the policy's contribution, conduct the ablation study presented in in the main paper. In this experiment, we compared our I.2C-Insert model against an I.2C-Append model (which uses similar architecture but appending policy) within the exact same local reconstruction framework.
The results show that our L2C-Insert with only 200 iterations significantly outperforms the L2C- Append model that uses 1000 iterations. This finding directly demonstrates that the superior perfor- mance stems from the intrinsic quality and flexibility of the insertion policy itself, and not just from the application of search method.
G Clarification on Fair Comparison and Calculating Costs
Clarifying Iteration Settings of Baselines
To clarify, we summarize the iteration settings of iterative methods in the table below. From this table, we can observe that he number of iterations varies significantly. For instance, NeurOpt utilizes 10,000 lightweight k-opt iterations, while two-stage methods like UDC and SO-mixed perform 50-100 concqqu iterations.
Table 13:
Iteration settings for baselilne methods. "Reviser-n" refers a solver designed repair local solution of length n.
Method
Probiem
Number iteration
NourOpt
TSP & CVRP
10000 (k:opt)
80-mixed
TSPIK
(Reviserr1O0V55) (Reviser- 10055)))1)000)
UDC
TSP & CVRP
for Reviser- 100 (with 50 initial solutions)
Gl KP
TSP
100/5010 for Reviser- 100V5022
CVRP
for LKH Reviser-20
2. A Note on Comparing Computational Budgets
We would like to respectfully clarify that directly comparing 'iteration counts' may be challenging, as the definition and computational cost of an "iteration" differ substantially across methods:
Improvement-i based methods like NeurOpt perform very fast, local search operations (e.g.. k-opt) in each iteration.
Two-stage methods like GLOP and UDC involve multiple sub- bebb-problm solvers per iteration or perform destroy-and-repaa on multiple initial solutions, and also may call powerful heuristic solver like LKH3 internally.
Our L2C- Insert performs local reconstruction only on single solution using one neural model.
For this reason, the total inference time may offer more holistic and equitable basis for comparing the computational budget. Our analysis therefore centered on the solution quality (optimality gap) achieved within given runtime. Our experimental results, when viewed in terms of total runtime, seem to support this perspective. For example, in Table (TSP1K), our In2C-Insert (I=1000) achieves 0.481 % gap in 46.4 minutes. In contrast, strong baseline like LEHD+RRCIONS requires 5.2 hours to achieve a 0.731 gap. This suggests that our method appears to offer a favorable trade-off between time and solution quality.
H Total Inference Time and Average Inference Time Per Instance
The apparent decrease in total inference time for larger instances is due to the different number of instances in the test datasets for each problem size.
Following the standard evaluation protocols established in prior NCO research 22 43
the test sets
for larger problems contain significantly fewer instances. For example, our TSP100 test set contains 10,000 instances, while the TSPI0K and TSP100K sets contain only 16 instances each. The total
31

---

inference times reported in Tables and 2 of our main paper reflect the time required to solve the entire dataset.
To provide a clearer picture, the table below breaks down the total inference time into the average time per instance.
Table 14: Add caption
TSP100 10000 instances
TSPIK
TSPIOK
TSPI0OK 16 instances
Dataset Size
128 instances
16 instances
L2C-Insert Total Inference Time
8.0h
46.4m
16.64m
26.07m
Insert Inference Time / instance
2.9s
21.8s
62.4s
97.8s
As the table clearly shows, the average inference time per instance for L2C-Insert scales with the problem size as expected, increasing from 2.9 seconds for TSPI00 to 97.8 seconds for TSP100K.
32

---

I Clarification on Method Positioning and Technical Contribution
Regarding the positioning of our method (construction heuristic vs. improvement heuristic) and its technical contributions, we make the following discussion to clarify and strengthen the core value of our paper.
The iinsertion-based construction" is a well-established concept in the traditional field of Operations Research. The core contribution of our work is not the invention of the 'insertion' operation itself, but rather being the first learning-driven, insertion- based framework specifically designed for solution construction in the field of NCO for solving the vehicle routing problem, which is currently dominated by the 'appending-basee basedd' paradigm.
The make the technical contribution of this paper clear, we elaborate from the following three perspectives:
1. The Essence of Our Core Method: A Pure Insertion-basee based Construction Method
Our core model, L22--Inert, is fundamentally construction-basee model in its design. Its task is to learn a policy pxpositionnode, partial tour) to predict the best insertion position, given an incomplete solution (partial solution) and a node to be inserted. This process starts from an initial solution (e.g.. one node) and builds complete solution by sequentially adding unvisited nodes, which fully aligns with the definition of a construction- based neural model.
Model Architecture and Training:
As described in Sections 3.1 and 3.2 of the paper, our model architecture (especially the decoder) and the supervised learning scheme are designed to learn this single-step constructive action. The model learns to master the optimal "insertion" decision at each step by reconstructing a given optimal solution. This is fundamentally different from improvement heuristic (like 2-opt), which requires complete solution as input for iterative refinement.
Comparison with the Appending-based Paradigm: The starting point our work is precisely to overcome the limitations of the popular "appending-based paradigm" in existing NCO methods (as mentioned in the Introduction and Figure 1). "Appending" is a construction method, and so is "insertion." However, the latter offers greater flexibility and larger solution space, which is the core of our exploration.
2. The Application of the Method: Distinguishing the Core Construction Model from the Inference Improvement Strategy
We would like clarify that our adoption of the insertion-based Local Reconstruction strategy during the inference stage (Section 3.3) is an advanced search strategy that uses our learned "construction model" as core operator, rather than being the model itself.
This can be understood as two-tiered structure:
Lower Level (Core Contribution): A learned, efficient construction heuristic model (L2C-Insert) that knows how to intelligently "insert" nodes.
Upper Level (Application Strategy): An improvement framework (akin to Large Neigh- borhood Search, LNS) that utilizes the lower-level construction model iteratively "destroy and repair" a solution during inference to enhance its quality.
This practice of "embedding a learned construction model into an improvement framework" is one of the most recognized, sfate-of-the-art and effective practices in the current NCO field (as referenced in the paper, e.g., LEHD 22 GLOP 40). Our storyline does not confuse the two. Instead, it is:
We propose new, more flexible construction model (L2C-Insert).
To validate its powerful performance, we follow the best practices in the field and use it as a potent "local reconstruction" tool during the inference stage.
3. Clear Technical Contributions
Based on the two points above, our technical contributions can be summarized more clearly as follows:
33

---

Paradigm Innovation: In the NCO field, we are the first to explore and successfully implement learning-driven cnssetiionbbsste construction framework, breaking the reliance of previous research on "appending- construction. This is an important supplement and rethinking of the existing NCO construction methodology.
We designed specific decoder structure (Section 3.1) to handle the complex "insertion" decision. It needs to simultaneously understand the intricate relationships between the node be inserted, all unvisited nodes, and all possible insertion positions in the current partial solution. This is much more complex than an "appending" model, which only needs focus on the last node. The corresponding supervised learning training scheme (Section 3.2) is also newly designed to fit the "insertion"
Novel Model Architecture and Training Mechanism:
task.
Synergistic Inference Strategy: We propose distance-based destruction strategy (Section 3.3) that is highly synergistic with the "insertion" paradigm. As described in the paper, this strategy can more effectively identify and break "bad edges" that are spatially close but sequentially distant, a flexibility that traditional "sqquence-base destruction strategies" lack. The experiment (Table 5) also proves its effectiveness. This demonstrates the powerful synergy between our proposed construction paradigm and inference strategy.
In summary, our work is not simple application of a known "insertion heuristic" to NCO. Our core is novel construction model, and its application during the inference stage is an advanced and reasonable improvement strategy. We believe that this clear hierarchical division and the technical innovations each level together constitute the solid technical contribution of this paper.
34

---

J Analysis of Computational Complexity for Insertion-based and Appending-basee heavy decoder-based NCO model
A formal analysis of computational complexity is essential for thorough comparison. Here is detailed comparison:
Computational Complexity of Appending-based NCO (L.2CAApeedd)
The primary source of computational complexity of the Transformer-basee model comes from the attention mechanism employed.
In a heavy decoder-based appending-based NCO model (e.g., LEHD, where heavy decoder means the decoder has six attention layers), the task at each construction step t select one node from the t unvisited nodes. The decoder computes a context query and attends to the embeddings of all n initial nodes determine the next node append. This attention mechanism has complexity of t22 where is the total number of nodes and d is the embedding dimension. This process repeated for steps. Thus, the total complexity for constructing a single solution is O dd. In Big O notation, this simplified (n)d).
Computational Complexity of insertion-based NCO (L2CCIInser)
Our proposed L2C-IIneer framework also adopts heavy decoder-based model. The task at each step is more complex. To make an informed decision, our decoder processes a much richer set of inputs simultaneously: the embedding of the current node to be inserted, the embeddings of all remaining unvisited nodes, and the embeddings total number of input embeddings processed by the self-attention layers at every step is therefore (1) + (n - t) + (t 1) = n. The complexity of a single construction step O(n2d). This step is repeated n times to build the full solution. Consequently, the total theoretical complexity is O(n d).
('1 possible insertion positions. The
Discussion and Practical Implications
Theoretically, both heavy-decoder paradigms exhibit a cubic complexity of O(nad). However, the insertion- -ased paradigm is computationally more intensive it consistently processes nodes per step, whereas the appending-basee approach processes a decreasing number of nodes (n t). This higher computational cost is direct trade-off for the enhanced flexibility and expressive power of the insertion mechanism.
To ensure practical applicability to large-scale problems, strategy during inference. Instead processing all n contextual nodes, the decoder's attention mechanism is constrained to only the k-nearest unvisited nodes and positions. This reduces the effective sequence length from n to a much smaller, constant & (e.g., k = 100 in our paper), making the per-step complexity approximately O(k2d).
employ k-nearest neighbor (k-NN)
35

---

K Clarification on the Definition of Target Position
We provide the following clarification clarify the definition of the target position.
Why two visited nodes the current partial solution determine the target position
During the process of the insertion construction, at each step, an unvisited node is inserted into position of the partial solution constructed in the current step. Since 1) the nodes connected in the current partial solution are all visited nodes; 2) an insertion position is essentially an edge and is uniquely determined by the two nodes connects, therefore, the only insertion position determined by two visited points.
How the target position is determined
To make the process of identifying the target position clearer, we break it down into two steps. Given labeled solution, current partial solution, and selected unvisited node insert:
Step Identify the circular sequence in the labeled solution
We first consider the complete labeled solution ग and remove all unvisited nodes except for the currently selected one. This leaves with a circular sequence containing only the selected unvisited node and the nodes already in the partial solution, preserving their original ordering from n².
For example, suppose the labeled solution is π (TT1 722 T3, TA, Ts, T6, T7), the partial solution is (TT, T3, T6. 77), and the selected unvisited node is T2. Then the other unvisited nodes are {T } After removing {Ta, ) from n², the resulting circular sequence is 1T1, T2, T3, N6: T7).
Step Identify the target position in the current partial solution
Within this newly formed circular sequence, we can find the two nodes that are now adjacent to the selected unvisited node. These two nodes, which are part of the partial solution, define the target position for the insertion.
Continue the above example. In the circular sequence (TT1, 72, T3, T6, T7). the nodes adjacent to I22 are { J. Since и and T3 are connected in the current partial solution, these two visited nodes determine the target position.
36

---

L Rationale and Principles of the Logarithmic Loss Function in Equation 3
The use the negative log-likelihood loss function Equation 3 a standard and principled choice for our supervised learning framework, primarily because it is highly effective for gradient-ban baaeett--aadd optimization.
Our model treats the selection of an insertion position at each construction step as a classification problem. The model's decoder, via softmax function, outputs probability distribution pe all valid insertion positions. Our objective to train the model to assign the highest possible probability the correct target position E
The logarithmic nature of this loss function [()) = - log pe (e" E T²) provides two key advantages for training:
Strong Error Correction: When the model assigns very low probability the correct target position (i.e., Po(ē*) ) -
), the loss -log pa (e") approaches infinity. This results in very large gradient, providing strong signal the optimizer to correct the model's parameters significantly.
Conversely, as the model's prediction for the correct class approaches 1, the loss approaches 0. This leads smaller gradients, promoting stable convergence the model learns to make correct predictions. This behavior effectively focuses the training effort on the most difficult examples.
Stable Convergence:
37

---

M Visualization
In this section, we provide graphical examples from both TSPLIB and CVRPLIB illustrate the insertion-based construction process clearly. As shown in Figure [S] the process begins by randomly selecting an unvisited node as the starting node for the incomplete solution. The model then continuously selects unvisited points to insert into the incomplete solution. Notably, in step 47, there are no unvisited nodes near the current node that can be connected without crossing the existing the next step will involve directly connecting
path. If the construction process is appending-basee the node to distant unvisited node, resulting in a very long edge. However, the insertion- based construction allows for the direct insertion of the distant unvisited node into the incomplete solution (as seen step 48), thereby avoiding the generation of the long edge mentioned above. Similarly, in Figure 6 steps 42 to 43 demonstrate similar behavior of error correction in previous steps. This highlights the flexibility the insertion-bace construction.
Step
Step
Step 3
Step
Step 47
Step 48
Step 50
Step 50
Step 51
Figure 5: Insertion based construction process the TSPLIB instance "eil51". The green dot is the node selected in the current step for insertion. The hollow dots are the unvisited nodes. The black dots visited nodes.
Step
Step
Step
Step
Step 40
Step 41
Step 42
Step 43
Step 44
Figure 6: insertion-based construction process the CVRPLIB instance "A-n45-k7". The red triangle is the depot node, the green dot is the unvisited customer node selected the current step for insertion. The hollow dots are the unvisited nodes. The black dots are visited nodes.
38

---

Detailed Formulation of Attention Layer
N.1
Attention Layer
The attention layer in the transformer model [36] is widely adopted in NCO for solving VRPs, mainly including multi-head attention (MHA) sublayer and node-wise feed-forward (FF) sublayer. Each sublayer is followed by a skip-connection [89] and normalization (Norm) [90]. We denote ((e-1) E Roxd as the inputs of the ε-th attention layer, the output of the attention layer is calculated
as:
X Norm(MHA(XX(-1)) + x(()1)),
X Norm(FF(XX) XX).
We denote this calculation process as follows:
X (anLayer(X((f-))
(9)
In this paper, the normalization is removed from the attention layer for enhancing generalization performance following Luo et al. [22]. For readability, omit the (E) and (e 1) in the following context.
N.2 Multi-head Attention
We first describe the single-head self-attention function as follows:
Attn(X) = softmax (XWo(XWx) XWv,
(10)
Vd
where X Rexdd is the input matrice, and We Rdxds parameters.
WK Raxde Wy E Raxd, are learnable
The multi-head attention sublayer applies the single-head attention function in Equation 10 for times in parallel with independent parameters:
MHA(X) Concat(head),.. head,) W
(11)
head, AXtn;(X),
where for each of (X), d2 = d, d/h. W e gaxd is a learnable matrix.
N.3 Feed Forward Layer
FF(X) = max (0, XW + 12
(12)
where Wn1 E Rddxdji, by Rdd and Wa Rdyxxd by2 Rdd are learnable parameters.
39

---

Broader Impacts
This research advances the field neural combinatorial optimization by introducing the L2C-IInert framework, which employs advanced machine learning techniques to solve Vehicle Routing Problems (VRPs). We believe this framework will provide valuable insights and inspire subsequent research focused on developing more efficient and effective neural methods for VRPs. Moreover, general learning- approach for solving VRPs, the proposed InC--Insert framework not anticipated to have specific negative societal impacts.
P Licenses
The licenses for the codes and the datasets used in this work are listed Table [5
Table 15: List of licenses for the codes and datasets we used in this work
Resource
Type
Link
License
LKH3
49
Code
bttp://webhotcll..uoo ruc.el//rruc...c ruc.dk/ keld/research/
Available for academic research use
hupp::/sithuh..o///kwwww Pyyggee
License
Concorde 41
Code
BSD 3- C-Cluuse License
hatps://gituh..com/yd kwon/POMO
Att MCCTS
+
Code
A1--CRN-MCCT
MIT License
hatps:/githuh..om/CTAA.
Grup/NCOO Catmup/ACO_coeeerr///miii code//ree/miin/
single_objectivee objectivv/IEEHD
BQ
Code https://githbb..c
BY-NC-SA
GLOP 40
Code
MIT License
HTSP
Code
MIT License
DIMES 73
Code
MFT License
DIFUSCO
Code
License
UDC 32
Code
/ /oode/ree/mmii/
MIT License
single
objective/UUDCC Large scale CO master
ELG 30
Code
MIT License
INVI 50
Code
https://githhhh.ooo wwtttauuhhoom/aaaaaa com/Kasumigaoka Ulaha/NNVT
Available for acalemic research use
NeurOpt [5
Code
MIT License
TSPI ih
46
Dataset
http///comopt. ifi uni heidelherg wwwp://awae/TS..........
Available for any non-commercial use
CVRPLib
http://ep. weterrppgggggg galgus inc. www.br/idex..pppeee phpp/en
Available for academic research
40


Reviews:
[{"review_id": "LnJf2jWE6K", "reviewer": "Reviewer_s3Av", "summary": "The paper introduces an insertion heuristic based on attention neural networks for solving large vehicle routing problems. It evaluates it on large problem instances and compares it to existing heuristics.", "questions": "- Why does L2C-Insert gets faster as the instance size increase?", "limitations": "See weaknesses.", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 1, "originality": 2, "strengths_and_weaknesses": "The paper is well-written and the approach is interesting. Extending NCOs with insertion capabilities is a valuable contribution. However, I find that the proposed experimental results do not allow for a fair assessment of the value of the proposed method. This is for a few reasons:\n- the methods have a different computational budget, which vary with the instance size. However, only a single point in time is shown. The authors claims that L2C-Insert can reach speed-up of up to 8x compared to the oracle heuristic benchmarks. However, the value achieved by these heuristics with the same time budget as L2C insert is never shown.\n- it is stated that L2C uses an \"accelerate[d] inference by processing only the k-nearest unvisited nodes and positions of the current node\". This is a valuable strategy. However, it is unclear why it can be applied only to L2C and not to all other benchmarks. This will lead to significant speed-ups on large instances and avoid OOM.\nThe paper is essentially an experimental one. Yet, the current experiments do not allow to fairly assess the value of the new method compared neither to existing NCOs nor HGS.\n\nHGS is the state-of-the art heuristic. It uses a variety of moves for constructing its solutions. As shown by the authors, most NCOs focus on appending nodes to partial solutions. L2C-Insert focuses on inserting nodes. Since solvers are modular, it would be very interesting to design a NCO that combines existing appending moves with L2C-Insert.", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviwer s3Av,\n\nThank you very much for your time and effort in reviewing our work. We are glad to know you find our paper well-written and the approach interesting, and that extending NCOs with insertion capabilities is a valuable contribution.\n\nWe address your concerns as follows.\n\n> **C1. the methods have a different computational budget, which vary with the instance size. However, only a single point in time is shown. The authors claims that L2C-Insert can reach speed-up of up to 8x compared to the oracle heuristic benchmarks. However, the value achieved by these heuristics with the same time budget as L2C insert is never shown.**\n\nThank you very much for raising this concern. We agree that a direct, time-normalized comparison against all baselines is important for a comprehensive evaluation. We would like to make the following clarifications to address your concern. \n\n**1. On the Evaluation Protocol and Role of Heuristic Solvers**\n\nWe would like to clarify the role of classical heuristic solvers (e.g., LKH3, HGS) in our experimental setup. In line with the established practice in the NCO literature, these solvers are primarily included to provide a strong, near-optimal baseline for solution quality, rather than to serve as direct competitors in terms of runtime. This evaluation protocol follows the precedent set by numerous recent publications in top-tier conferences. For example, prominent works such as POMO [1] and BQ-NCO [2] adopt a similar evaluation strategy.\n\n**2. On the Speed-up Claim**\n\nAdditionally, we would like to clarify that all speed-up claims in our paper are made in comparison to other state-of-the-art Neural Combinatorial Optimization (NCO) methods, not classical heuristic solvers like LKH3 or HGS.\n\nWe recognize the potential for confusion. In the revised version of our paper, we will explicitly clarify the distinct evaluation roles of classical solvers versus NCO methods in our experimental setup section.\n\n[1] POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. NeurIPS, 2020.\n\n[2] BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization. NeurIPS, 2023.\n\n\n> **C2. it is stated that L2C uses an \"accelerate[d] inference by processing only the k-nearest unvisited nodes and positions of the current node\". This is a valuable strategy. However, it is unclear why it can be applied only to L2C and not to all other benchmarks. This will lead to significant speed-ups on large instances and avoid OOM.**\n\nThank you very much for raising this concern. We agree that the acceleration techniques like k-nearest neighbors (k-NN) strategy are powerful to be applied to other constructive NCO methods. We would like to make the following clarifications to address your concern. \n\n**1. Impact of the acceleration techniques**\n\nIt is challenging to uniformly apply a specific set of acceleration techniques across all baseline methods and expect consistent improvements. To provide a concrete example, we applied our acceleration settings (specifically, using k=100 nearest neighbors and limiting the destruction size to 300 for local reconstruction) to a strong baseline, LEHD RRC1000. The results are presented in Table 1 below.\n\nTable 1: Performance of LEHD RRC1000 with and without the acceleration techniques.\n||TSP1K|||TSP10K|||TSP100K|||\n|-|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n||Length|Gap|Time|Length|Gap|Time|Length|Gap|Time|\n|LEHD RRC1000|23.288|0.731\\%|5.2h|80.900|12.709\\%|3.6h|OOM|||\n|LEHD RRC1000 with acceleration techniques|23.389|1.168\\%|17.62m|79.734|11.084\\%|9.49m|368.023|62.849\\%|15.47m|\n\nThese results lead to several key observations:\n\n + **The strategy is not a universal enhancement:** On TSP1K, applying acceleration techniques drastically reduces inference time but leads to a noticeable degradation in solution quality (Gap increases from 0.731\\% to 1.168\\%). This demonstrates a non-trivial trade-off between speed and performance.\n+ **They enable large-scale inference but with limitations:** On TSP100K, the acceleration techniques successfully avoid the OOM error, allowing LEHD to produce a solution. However, the resulting quality (62.8\\% gap) is not competitive, suggesting that simply restricting the search space is insufficient for achieving good performance on very large instances with this model.\n\nThese results show that while acceleration techniques can be integrated into other methods, they are not a \"free lunch\". Their impact on performance is unpredictable and can even be detrimental, indicating that such strategies need to be co-designed with the model architecture.\n\n\n**2. Fair Comparison and Our Experimental Choices**\n\nGiven the above, we chose to run baselines using their original, published configurations for two main reasons:\n\n+ **To ensure a transparent and faithful comparison:** Modifying baselines with a strategy that has complex trade-offs could be seen as unfairly altering their intended design.\n+ **Some baselines already incorporate similar acceleration techniques:** For instance, INViT-3V already incorporates a  k-NN neighborhood-based attention mechanism.\n\nIn short, while we acknowledge the general applicability of acceleration techniques like k-NN, our analysis shows they are not a simple, plug-and-play solution that guarantees benefits for all models. Therefore, to maintain a fair comparison, we benchmark against the original design of the baseline methods.\n\n> **Suggestion. It would be very interesting to design a NCO that combines existing appending moves with L2C-Insert.**\n\nThank you very much for this insightful and forward-looking suggestion. We completely agree that designing a hybrid NCO solver that combines both appending and inserting moves is a highly promising research direction. A modular framework that can dynamically learn to select the most effective operator—be it appending to the end of a tour or inserting into an optimal position—could leverage the strengths of both paradigms. Such a model has the potential to be more flexible and powerful than a model restricted to a single type of move.\n\nNonetheless, the primary objective of this paper is to serve as an in-depth investigation into the insertion-based paradigm within the constructive NCO framework. To rigorously and clearly establish its standalone value, we intentionally isolated it and benchmarked it against the traditional, purely appending-based paradigm (as shown in our ablation study in Table 4 in the main paper, L2C-Append vs. L2C-Insert). Introducing a hybrid model from the outset would have made it difficult to disentangle the benefits and attribute performance gains directly to the insertion capability itself versus other potential synergistic effects. By focusing on a pure insertion model, we aim to provide a clean and interpretable analysis of its unique contributions.\n\nWe believe your suggestion represents a natural and exciting next step for this line of research. We will explicitly add this idea to our \"Limitation and Future Work\" section in the revised manuscript to highlight its potential and inspire future work in this area.\n\n\n> **Q1. Why does L2C-Insert gets faster as the instance size increase?**\n\nThank you very much for raising this important question. The apparent decrease in total inference time for larger instances is due to the different number of instances in the test datasets for each problem size.\n\nFollowing the standard evaluation protocols established in prior NCO research [1,2], the test sets for larger problems contain significantly fewer instances. For example, our TSP100 test set contains 10,000 instances, while the TSP10K and TSP100K sets contain only 16 instances each. The total inference times reported in Tables 1 and 2 of our main paper reflect the time required to solve the entire dataset.\n\nTo provide a clearer picture, Table 2 breaks down the total inference time into the average time per instance.\n\nTable 2: Total and Average Inference Time of L2C-Insert on TSP Datasets of Varying Scales\n||TSP100|TSP1K|TSP10K|TSP100K|\n|-|-|-|-|-|\n|Dataset Size|10,000 instances|128 instances|16 instances|16 instances|\n|Total Inference Time|8.0h|46.4m|16.64m|26.07m|\n|Inference Time/instance|2.9s|21.8s|62.4s|97.8s|\n\nAs the table clearly shows, the average inference time per instance for L2C-Insert scales with the problem size as expected, increasing from 2.9 seconds for TSP100 to 97.8 seconds for TSP100K. We apologize for the lack of clarity in our initial presentation. In the revised manuscript, we will add a note to the results table to explicitly state that the reported times are for the entire test set and will consider adding the per-instance average time to avoid any future confusion.\n\n\n[1] Neural combinatorial optimization with heavy decoder: Toward large scale generalization. NeurIPS, 2023.\n\n[2] Generalize a small pre-trained model to arbitrarily large tsp instances. AAAI, 2021.\n\nOnce again, we would like to express our heartfelt gratitude for the time and effort you've dedicated to reviewing our work. We will carefully incorporate the above discussions into our revised paper. We sincerely hope that our response can address your concerns."}, {"review_id": "W7fs6WtYzs", "reviewer": "Reviewer_hZDB", "summary": "The paper explores an insertion-based variant of Neural Combinatorial Optimization (NCO) for vehicle routing problems, proposing a method called L2C-Insert. In contrast to standard appending-based approaches that build solutions by adding nodes sequentially, the proposed method allows for inserting nodes at arbitrary feasible positions within partial solutions. The approach involves a custom model architecture for predicting insertion positions, a training procedure tailored to this setting, and an inference strategy that leverages the increased flexibility of the insertion paradigm. The authors evaluate their method on Travelling Salesman and Capacitated Vehicle Routing Problem instances, reporting improved results over existing NCO baselines. However, the extent and generality of the claimed improvements may warrant further scrutiny.", "questions": "Q1 Can you specify the technical contribution? Insertion-based construction is not a new concept and the way it is applied it resembles more an improvement instead of a construction method.\n\nQ2 Can you clarify the doubts and questions listed under weaknesses with respect to the numerical experiments?", "limitations": "The paper contains a short discussion on limitations.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 1, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n\nS1 The topic studied is timely and general of interest\n\n\nWeaknesses\n\nW1 There are many vague and partially wrong statements in the paper. E.g., HGS is a heuristic algorithm but is claimed to provide optimal solutions.\n\nW2 The method proposed is pitched as a construction heuristic, but is essentially used in an improvement heuristic, which misaligns the storyline with the content\n\nW3 The results are counterintuitive and need further investigation, e.g., running an HGS on a 100 customer instance should not take 4.5 hours - with the right implementation that can be downloaded from the respective git repository, it should be possible in the order of seconds. Such kind of question marks put the overall experiments in question.\n\nW4 Some benchmarks, e.g., the recent works of Tierney and coauthors are not considered in the numerical study although these outperform the used benchmarks.", "was_revised": true, "final_justification": "the authors clarified my concerns and promsied to improve the ambiguous statements. moreover they justified why they could not do further comparisons.", "rebuttal": "Dear Reviewer hZDB,\n\nThank you very much for your time and effort in reviewing our work. We are glad to know you find the topic studied in our paper timely and generally of interest.\n\nWe address your concerns as follows.\n\n\n> **C1. There are many vague and partially wrong statements in the paper. E.g., HGS is a heuristic algorithm but is claimed to provide optimal solutions.**\n\nThank you very much for pointing this out. We agree with you that HGS is a state-of-the-art heuristic solver for CVRP, not an exact one. We apologize for the incorrect statement. In the revised manuscript, we will correct this statement. Furthermore, we will conduct a thorough review of the entire manuscript to identify and rectify any other vague or imprecise statements.\n\n\n> **C2. The method proposed is pitched as a construction heuristic, but is essentially used in an improvement heuristic, which misaligns the storyline with the content.**\n\n> **Q1. Can you specify the technical contribution? Insertion-based construction is not a new concept and the way it is applied it resembles more an improvement instead of a construction method.**\n\nThank you very much for raising this important concern. Your questions regarding the positioning of our method (construction heuristic vs. improvement heuristic) and its technical contributions have been instrumental in helping us further clarify and strengthen the core value of our paper. We hope the following clarification will articulate our work more clearly and address your concerns.\n\nWe fully agree that \"insertion-based construction\" is a well-established concept in the traditional field of Operations Research. The core contribution of our work is not the invention of the 'insertion' operation itself, but rather being the first learning-driven, insertion-based framework specifically designed for autoregressive solution construction in the field of NCO for solving the vehicle routing problem, which is currently dominated by the 'appending-based' paradigm.\n\nTo address your concerns more clearly, we will elaborate from the following three perspectives:\n\n**1. The Essence of Our Core Method: A Pure Insertion-based Autoregressive Construction Method**\n\nOur core model, L2C-Insert, is fundamentally an autoregressive construction-based model in its design. Its task is to learn a policy $p$(position∣node, partial tour) to predict the best insertion position, given an incomplete solution (partial solution) and a node to be inserted. This process starts from an initial solution (e.g., one node) and builds a complete solution by sequentially adding unvisited nodes, which fully aligns with the definition of a construction-based neural model.\n+ **Model Architecture and Training:** As described in Sections 3.1 and 3.2 of the paper, our model architecture (especially the decoder) and the supervised learning scheme are designed to learn this single-step constructive action. The model learns to master the optimal \"insertion\" decision at each step by reconstructing a given optimal solution. This is fundamentally different from an improvement heuristic (like 2-opt), which requires a complete solution as input for iterative refinement.\n+ **Comparison with the Appending-based Paradigm:** The starting point of our work is precisely to overcome the limitations of the popular \"appending-based paradigm\" in existing NCO methods (as mentioned in the Introduction and Figure 1). \"Appending\" is a construction method, and so is \"insertion.\" However, the latter offers greater flexibility and a larger solution space, which is the core of our exploration.\n\n**2. The Application of the Method: Distinguishing the Core Construction Model from the Inference Improvement Strategy**\n\nWe would like to clarify that our adoption of the Insertion-based Local Reconstruction strategy during the inference stage (Section 3.3) is an advanced search strategy that uses our learned \"construction model\" as a core operator, rather than being the model itself.\n\nThis can be understood as a two-tiered structure:\n\n+ **Lower Level (Core Contribution):** A learned, efficient construction heuristic model (L2C-Insert) that knows how to intelligently \"insert\" nodes.\n+ **Upper Level (Application Strategy):** An improvement framework (akin to Large Neighborhood Search, LNS) that utilizes the lower-level construction model to iteratively \"destroy and repair\" a solution during inference to enhance its quality.\n\nThis practice of \"embedding a learned construction model into an improvement framework\" is one of the most recognized, state-of-the-art, and effective practices in the current NCO field (as referenced in the paper, e.g., LEHD [1], GLOP [2]). Our storyline does not confuse the two. Instead, it is:\n\n+ We propose a new, more flexible construction model (L2C-Insert).\n+ To validate its powerful performance, we follow the best practices in the field and use it as a potent \"local reconstruction\" tool during the inference stage.\n\n**3. Clear Technical Contributions**\n\nBased on the two points above, our technical contributions can be summarized more clearly as follows:\n\n+ **Paradigm Innovation:** In the NCO field, we are the first to explore and successfully implement a learning-driven \"insertion-based\" construction framework, breaking the reliance of previous research on \"appending-based\" construction. This is an important supplement and a rethinking of the existing NCO construction methodology.\n+ **Novel Model Architecture and Training Mechanism:** We designed a specific decoder structure (Section 3.1) to handle the complex \"insertion\" decision. It needs to simultaneously understand the intricate relationships between the node to be inserted, all unvisited nodes, and all possible insertion positions in the current partial solution. This is much more complex than an \"appending\" model, which only needs to focus on the last node. The corresponding supervised learning training scheme (Section 3.2) is also newly designed to fit the \"insertion\" task.\n+ **Synergistic Inference Strategy:** We propose a distance-based destruction strategy (Section 3.3) that is highly synergistic with the \"insertion\" paradigm. As described in the paper, this strategy can more effectively identify and break \"bad edges\" that are spatially close but sequentially distant, a flexibility that traditional \"sequence-based destruction strategies\" lack. The experiment (Table 5 in the main paper) also proves its effectiveness. This demonstrates the powerful synergy between our proposed construction paradigm and inference strategy.\n\n\nIn summary, our work is not a simple application of a known \"insertion heuristic\" to NCO. Our core is a novel construction model, and its application during the inference stage is an advanced and reasonable improvement strategy. We believe that this clear hierarchical division and the technical innovations at each level together constitute the solid technical contribution of this paper.\n\nThank you again for your valuable comment. We hope the above explanation can address your concerns.\n\n> **C3. The results are counterintuitive and need further investigation, e.g., running an HGS on a 100 customer instance should not take 4.5 hours - with the right implementation that can be downloaded from the respective git repository, it should be possible in the order of seconds.**\n\n\nThank you very much for raising this concern. We would like to clarify that the 4.5 hours reported in Table 1 in the main paper is the total time required for HGS to solve the entire CVRP100 test set, which consists of 10,000 instances, not the runtime for a single instance. We follow the practice of some representative literature by reporting the cumulative time over the entire test set [1, 2].\n\nIf we calculate the average time, the time to solve a single CVRP100 instance is approximately 2s/instance. This average runtime is consistent with the \"order of seconds\" expectation mentioned by you. We sincerely apologize for this confusion. To present the results more clearly, we will explicitly state in the table captions or footnotes that the reported times for classical solvers (like HGS and LKH3) are the total times for solving the entire test set.\n\n[1] Attention, Learn to Solve Routing Problems! ICLR, 2019.\n\n[2] POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. NeurIPS, 2020.\n\n> **C4. Some benchmarks, e.g., the recent works of Tierney and coauthors are not considered in the numerical study although these outperform the used benchmarks.**\n\nThank you very much for raising this concern. We fully agree that including the important works of Tierney and coauthors [1, 2] in the numerical study is crucial for a comprehensive evaluation of our work's contributions.\n\nHowever, we are unable to find publicly available source code for these two papers [1, 2]. Consequently, we could not perform a fair reproduction and direct numerical comparison, which is why they are not included as baselines in our experiments. To address this and ensure our paper reflects the latest progress in the field, we commit to including a detailed introduction and discussion of these two papers in the Related Work section of our final manuscript.\n\n\n[1] PolyNet: Learning diverse solution strategies for neural combinatorial optimization. ICLR, 2025.\n\n[2] Neural Deconstruction Search for Vehicle Routing Problems. Arxiv, 2025.\n\n\nOnce again, we would like to express our heartfelt gratitude for the time and effort you've dedicated to reviewing our work. We will carefully incorporate the above discussions into our revised paper. We sincerely hope that our response can address your concerns."}, {"review_id": "DwSfe4EYnx", "reviewer": "Reviewer_havL", "summary": "The paper proposed an insertion-based approach to Neural Combinatorial Optimisation for solving VRP (including TSP) problems. This idea is interesting as it replaced the existing appending-based approaches, and it is a natural extension of the later considering there are existing interstation-based approaches for solving VRP problems. The model used encoder-decoder architecture, and learnt three embeddings: current node, unvisited node, and position embeddings.", "questions": "Why was the logarithm loss function used in Equation 3? \n\nTarget positions: it is said: “The target position for an unvisited node is defined by the two visited nodes in the current partial solution that are adjacent to this unvisited node in the complete labelled solution”   I wonder why “two visited nodes”. \n\nTable 1:  I wonder why L2C-Insert methods took longer time on TSP100 compared to TSP1K and TSP10K?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strength: \nThe idea is novel and sensible, and the experimental results show the proposed model has promising potential. \nThe presentation for the design of the model and experiments are done in a systematic and comprehensive way.  \nExamples were given to better understand how insertion-based approaches work. \n\nWeakness:  \nComputational complexity analysis on insertion-based against appending-based are not presented. \nMore detailed justification on the definition of target positions in Section 3.2. \nThe loss function: more details could be given.", "was_revised": true, "final_justification": "This is an interesting piece of work and the idea is novel. The experimental results were solid.  This paper can be accepted by the conference.", "rebuttal": "Dear Reviewer havL,\n\nThank you very much for your time and effort in reviewing our work. We are glad you find that our idea of learning to insert is novel and sensible, that the proposed model has promising potential, and that the presentation of the model design and experiments is systematic and comprehensive.\n\nWe address your concerns as follows.\n\n> **C1. Computational complexity analysis on insertion-based against appending-based are not presented.**\n\nThank you for raising this crucial point. For a thorough comparison, we provide the following computational complexity analysis of insertion-based versus appending-based models:\n\n**1. Computational Complexity of Appending-based NCO (L2C-Append)**\n\nWhile both appending-based and insertion-based models can have the same theoretical complexity, how they arrive at it differs based on the nature of their constructive step.\n\nIn a heavy decoder-based appending-based NCO model (e.g., LEHD, where heavy decoder means the decoder has six attention layers), the task at each construction step $t$ is to select one node from the $n - t$ unvisited nodes. The decoder computes a context query and attends to the embeddings of all $n$ initial nodes to determine the next node to append. This attention mechanism has a complexity of $O((n-t)^2 \\cdot d)$, where $n$ is the total number of nodes and $d$ is the embedding dimension. This process is repeated for $n$ steps. Summing this over all $n$ construction steps results in a theoretical total complexity of $O(n^3⋅d)$.\n\n**2. Computational Complexity of Insertion-based NCO (L2C-Insert)**\n\nOur proposed L2C-Insert framework also adopts a heavy decoder-based model. The task at each step $t$ is more complex. To make an informed decision, our decoder processes a much richer set of inputs simultaneously: the embedding of the current node to be inserted, the embeddings of all $n − t$ remaining unvisited nodes, and the embeddings of all $t − 1$ possible insertion positions. The total number of input embeddings processed by the self-attention layers at every step is therefore $(1)+(n - t)+(t - 1)=n$. The complexity of a single construction step is $O(n^2⋅d)$. This step is repeated $n$ times to build the full solution. Consequently, the total theoretical complexity is $O(n^3⋅d)$.\n\n**3. Discussion and Practical Implications**\n\nTheoretically, both heavy-decoder paradigms exhibit a cubic complexity of $O(n^3⋅d)$. To ensure practical applicability to large-scale problems, we can employ a k-nearest neighbor (k-NN) strategy during inference, as detailed in Section 4 in the main paper. Instead of processing all $n$ contextual nodes, the decoder's attention mechanism is constrained to only the k-nearest unvisited nodes and positions. This reduces the effective sequence length from $n$ to a much smaller, constant $k$ (e.g., $k=100$ in our paper), making the per-step complexity approximately $O(k^2⋅d)$. This practical optimization makes our approach's runtime competitive with other state-of-the-art methods on larger-scale instances such as TSP10K instances, as shown in Tables 1 and 2 in the main paper.\n\n> **C2. More detailed justification on the definition of target positions in Section 3.2.**\n\n> **Q2. Target positions: it is said: “The target position for an unvisited node is defined by the two visited nodes in the current partial solution that are adjacent to this unvisited node in the complete labelled solution” I wonder why “two visited nodes”.**\n\nThank you very much for your insightful comment. We apologize for the unclear definition of the target position. We make the following clarification to address your question.\n\n**1. Why two visited nodes in the current partial solution determine the target position**\n\nDuring the process of the insertion construction, at each step, an unvisited node is inserted into a position of the partial solution constructed in the current step. Since 1) the nodes connected in the current partial solution are all visited nodes; 2) an insertion position is essentially an edge and is uniquely determined by the two nodes it connects, therefore, the only insertion position is determined by two visited points.\n\n**2. How the target position is determined**\n\nTo make the process of identifying the target position clearer, we break it down into two steps. Given a labeled solution, a current partial solution, and a selected unvisited node to insert:\n\n+ **Step 1: Identify the circular sequence in the labeled solution**\n\n We first consider the complete labeled solution $\\boldsymbol{\\pi}^\\star$ and remove all unvisited nodes except for the currently selected one. This leaves us with a circular sequence containing only the selected unvisited node and the nodes already in the partial solution, preserving their original ordering from $\\boldsymbol{\\pi}^\\star$.\n\nFor example, suppose the labeled solution is $\\boldsymbol{\\pi}^\\star=(\\pi_1, \\pi_2, \\pi_3, \\pi_4, \\pi_5, \\pi_6, \\pi_7)$, the partial solution is $(\\pi_1, \\pi_3, \\pi_6, \\pi_7)$, and the selected unvisited node is $\\pi_2$. Then the other unvisited nodes are $\\{ \\pi_4, \\pi_5\\}$. After removing $\\{ \\pi_4, \\pi_5\\}$ from $\\boldsymbol{\\pi}^\\star$, the resulting circular sequence is $(\\pi_1, \\pi_2, \\pi_3, \\pi_6, \\pi_7)$.\n\n+ **Step 2: Identify the target position in the current partial solution**\n\nWithin this newly formed circular sequence, we can find the two nodes that are now adjacent to the selected unvisited node. These two nodes, which are part of the partial solution, define the target position for the insertion.\n\nContinue the above example. In the circular sequence $(\\pi_1, \\pi_2, \\pi_3, \\pi_6, \\pi_7)$, the nodes adjacent to $\\pi_2$ are $\\{\\pi_1,\\pi_3\\}$. Since $\\pi_1$ and $\\pi_3$ are connected in the current partial solution, these two visited nodes determine the target position.\n\nWe sincerely hope that our clarification can address this concern. We will carefully incorporate the above discussion into the revised paper to enhance the clarification.\n\n> **C3. The loss function: more details could be given.**\n\n> **Q1. Why was the logarithm loss function used in Equation 3?**\n\nThank you very much for the valuable comment. The use of the negative log-likelihood loss function in Equation (3) is a standard and principled choice for our supervised learning framework, primarily because it is highly effective for gradient-based optimization.\n\nOur model treats the selection of an insertion position at each construction step as a classification problem. The model's decoder, via a softmax function, outputs a probability distribution $p_{\\theta}$ over all valid insertion positions. Our objective is to train the model to assign the highest possible probability to the correct target position $\\vec{e}^{\\star}$.\n\nThe logarithmic nature of the loss function provides two key advantages for training:\n\n+ **Strong Error Correction:** When the model assigns a very low probability to the correct target position (i.e., $p_{\\theta}(\\vec{e}^{\\star})\\rightarrow$0 ), the loss $-log \\ p_{\\theta}(\\vec{e}^{\\star})$ approaches infinity. This results in a very large gradient, providing a strong signal to the optimizer to correct the model's parameters significantly.\n\n+ **Stable Convergence:** Conversely, as the model's prediction for the correct class approaches 1, the loss approaches 0. This leads to smaller gradients, promoting stable convergence once the model learns to make correct predictions. This behavior effectively focuses the training effort on the most difficult examples.\n\n> **Q3. Table 1: I wonder why L2C-Insert methods took longer time on TSP100 compared to TSP1K and TSP10K?**\n\nThank you very much for raising this important question.\nThe apparent decrease in total inference time for larger instances is due to the different number of instances in the test datasets for each problem size.\n\nFollowing the standard evaluation protocols established in prior NCO research [1,2], the test sets for larger problems contain significantly fewer instances. For example, our TSP100 test set contains 10,000 instances, while the TSP1K and TSP10K sets contain only 128 and 16 instances each, respectively. The total inference times reported in Table 1 of our main paper reflect the time required to solve the entire dataset.\n\nTo provide a clearer picture, table 3 breaks down the total inference time into the average time per instance.\n\nTable 3: Toal and Average Inference Time of L2C-Insert on TSP Datasets of Varying Scales\n||TSP100|TSP1K|TSP10K|\n|-|-|-|-|\n|Dataset Size|10,000 instances|128 instances|16 instances|\n|Total Inference Time|8.0h|46.4m|16.64m|\n|Inference Time/instance|2.9s|21.8s|62.4s|\n\nAs the table clearly shows, the average inference time per instance for L2C-Insert scales with the problem size as expected, increasing from 2.9 seconds for TSP100 to 62.4 seconds for TSP10K. We apologize for the lack of clarity in our initial presentation. In the revised manuscript, we will add a note to the results table to explicitly state that the reported times are for the entire test set and will consider adding the per-instance average time to avoid any future confusion. Thank you for helping us improve our paper.\n\n[1] Neural combinatorial optimization with heavy decoder: Toward large scale generalization. NeurIPS, 2023.\n\n[2] Generalize a small pre-trained model to arbitrarily large tsp instances. AAAI, 2021.\n\n\nOnce again, we would like to express our heartfelt gratitude for the time and effort you've dedicated to reviewing our work. We will carefully incorporate the above discussions into our revised paper. We sincerely hope that our response can address your concerns."}, {"review_id": "mUyhuu0JHU", "reviewer": "Reviewer_fNy1", "summary": "This paper proposes L2C-Insert, the first constructive Neural Combinatorial Optimisation (NCO) framework that learns insertion to address the inherent rigidity of the prevailing append operation. Its Transformer encoder-decoder jointly embeds the current node, all candidate positions, and the remaining unvisited nodes to output a masked softmax over valid insertion positions. Supervised learning is used to train the model to learn to re-insert nodes into their ground-truth positions as defined by an optimal solution , while a distance-based destroy-reconstruct loop iteratively refines solutions at inference time. Notably, a single model trained solely on 100-node synthetic data generalizes to Travelling Salesman and Capacitated VRP instances of up to 100K nodes , achieving consistently superior performance and lower optimality gaps than recent neural and hybrid baselines", "questions": "Please see the above sections.", "limitations": "Well described in the paper", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "# Strengths\n\nS1. The paper introduces *insertion* as the learning target, replacing the usual tail-appending step; this is a new idea for neural combinatorial optimisation and it is good to see it explored in the field.\n\nS2. The paper's insertion-based local reconstruction is a powerful method that is proven to improve the final solution.\n\nS3. The paper is well organised the method is explained clearly, and the results are backed by solid evidence.\n\n# Weaknesses\nW1 . The node to be inserted is selected using a simple nearest-neighbor heuristic, not learned by the model. This greedy choice could be a limitation, and it would be interesting to know if learning this selection was explored.\n\nW2. The paper's quality gains seem heavily dependent on the iterative destroy-reconstruct loop. On TSP100 instances, the one-shot Greedy version is notably outperformed by several NCO baselines, which makes it important to distinguish the search contribution from the policy's contribution.\n\nW3. The runtime comparisons are difficult to fairly assess, as the search iteration budget for competing iterative methods (like NeurOpt ) is not reported. Clarifying these settings is crucial for comparing against the L2C-Insert's 1000 reconstruction steps.", "was_revised": true, "final_justification": "The authors' rebuttal successfully resolved all primary concerns, and I recommend acceptance.", "rebuttal": "Dear Reviewer fNy1,\n\nThank you very much for your time and effort in reviewing our work. We are glad that you consider the introduction of insertion as a learning target for NCO a novel idea worth exploring, and also find the paper to be well-organized with a clearly explained method.\n\nWe address your concerns as follows.\n\n> **C1. The node to be inserted is selected using a simple nearest-neighbor heuristic, not learned by the model. This greedy choice could be a limitation, and it would be interesting to know if learning this selection was explored.**\n\n\nThank you very much for this insightful comment. We agree that the choice of which node to insert is a critical component of the overall construction process. Our decision to use a nearest-neighbor heuristic aims to first establish the core value of the insertion paradigm itself.\n\n**1. Effectiveness of the current heuristic strategy**\n\nOur ablation study in Appendix E.2 (Table 9) provides empirical support for this choice. We compare the \"Nearest Neighbor\" strategy with a \"Random\" selection strategy and found that the nearest-neighbor approach yields substantially better performance. This indicates that this simple, efficient heuristic already provides a strong guiding signal for the construction process, making it an effective baseline.\n\n**2. Considerations for not yet adopting a learning strategy**\n\nWhile a learned selection policy could potentially unlock further performance gains, we consciously deferred its exploration in this foundational work for two main reasons:\n\n+ **Managing Complexity:** Introducing a learned selection mechanism, whether through a separate model or by extending the current one, would significantly increase the model's complexity and computational overhead. A separate model would pose co-training challenges, while a single model performing both the selection and insertion would face a much harder learning challenge, which could degrade performance.\n\n+ **Isolating the Core Contribution:** Our primary goal was to clearly isolate and demonstrate the effectiveness of the insertion paradigm as a superior alternative to the conventional appending paradigm. By using a fixed, simple heuristic for node selection, we can more confidently attribute the performance improvements to the flexibility of the insertion mechanism itself.\n\n\nWe fully agree with the reviewer that learning the node selection policy is a valuable and logical next step. Developing a policy that works in synergy with the insertion model—perhaps through joint or two-stage training—is a highly promising research direction. We will add this point to the \"Limitation and Future Work\" section to explicitly highlight this opportunity and hope our work will inspire the NCO community to further investigate all facets of the powerful insertion-based construction paradigm.\n\n\n\n> **C2. The paper's quality gains seem heavily dependent on the iterative destroy-reconstruct loop. On TSP100 instances, the one-shot Greedy version is notably outperformed by several NCO baselines, which makes it important to distinguish the search contribution from the policy's contribution.**\n\nThank you very much for raising this important concern. We agree that the iterative local reconstruction is a significant factor in achieving the final reported performance. We also appreciate the opportunity to clarify our perspective: we believe the key innovation of our work, the insertion-based policy, is what unlocks the true potential of this search procedure. The policy's inherent flexibility is a key enabler for the search's effectiveness.\n\n**1. The advantage of insertion-based search**\n\nAs we discuss in Section 3.3, conventional appending-based models face a fundamental limitation when used with local search. When nodes are removed during the destruction phase, they can only be re-appended to the end of the sequence during reconstruction. This rigidity makes it difficult for the model to escape local optima. For instance, reconnecting two nodes that are geometrically close but far apart in the sequence—a common requirement for improving a tour—is highly improbable.\n\nOur L2C-Insert framework directly overcomes this bottleneck. By allowing a node to be re-inserted at any valid position, our model facilitates a much more powerful and effective exploration of the solution space during the reconstruction phase. This flexibility is the core reason why the destroy-and-reconstruct loop is effective in our framework.\n\n**2. Direct Ablation Study: Isolating the Policy's Contribution**\n\nTo provide a direct and fair comparison that disentangles the policy's contribution, we conducted the ablation study presented in Table 4 in the main paper. In this experiment, we compared our L2C-Insert model against an L2C-Append model (which uses a similar architecture but an appending policy) within the exact same local reconstruction framework.\n\nThe results show that our L2C-Insert with only 200 iterations significantly outperforms the L2C-Append model that uses 1000 iterations. This finding directly demonstrates that the superior performance stems from the intrinsic quality and flexibility of the insertion policy itself, and not just from the application of a search method.\n\n\n> **C3. The runtime comparisons are difficult to fairly assess, as the search iteration budget for competing iterative methods (like NeurOpt ) is not reported. Clarifying these settings is crucial for comparing against the L2C-Insert's 1000 reconstruction steps.**\n\nThank you very much for your constructive suggestions. We agree that clarifying the iteration budget details of baseline methods would help to fairly evaluate the runtimes.\n\n**1. Clarifying Iteration Settings of Baselines**\n\nTo clarify, we summarize the iteration settings of iterative methods in Table 4 below. From this table, we can observe that he number of iterations varies significantly. For instance, NeurOpt utilizes 10,000 lightweight k-opt iterations, while two-stage methods like UDC and SO-mixed perform 50-100 divide-and-conquer iterations.\n\n\nTable 4: Iteration settings for baselilne methods. \"Reviser-$n$\" refers to a solver designed to repair a local solution of length $n$.\n|Method|Problem|Number of iteration|\n|:---:|:---:|:---:|\n|NeurOpt|TSP \\& CVRP|10000 (k-opt)|\n|SO-mixed|TSP1K|50 (Reviser-100/50)|\n| |TSP10K|100 (Reviser-100/50)|\n|UDC|TSP \\& CVRP|50 for Reviser-100 (with 50 initial solutions)|\n|GLOP|TSP|100/50/10 for Reviser-100/50/20|\n| |CVRP|5 for LKH3 as Reviser-20|\n\n\n**2. A Note on Comparing Computational Budgets**\n\nWe agree that a fair comparison is essential. In this context, we would like to respectfully clarify that directly comparing 'iteration counts' may be challenging, as the definition and computational cost of an \"iteration\" differ substantially across methods:\n\n+ Improvement-based methods like NeurOpt perform very fast, local search operations (e.g., k-opt) in each iteration.\n+ Two-stage methods like GLOP and UDC involve multiple sub-problem solvers per iteration or perform the destroy-and-repair on multiple initial solutions, and also may call a powerful heuristic solver like LKH3 internally.\n+ Our L2C-Insert performs local reconstruction only on a single solution using one neural model.\n\nFor this reason, the total inference time may offer a more holistic and equitable basis for comparing the computational budget. Our analysis is therefore centered on the solution quality (optimality gap) achieved within a given runtime. Our experimental results, when viewed through the lens of total runtime, seem to support this perspective. For example, from the results in Table 1 in the main paper, we can observe that on TSP1K, our L2C-Insert (I=1000) achieves a 0.481\\% gap in 46.4 minutes. In contrast, a strong baseline like LEHD+RRC1000 requires 5.2 hours to achieve a 0.731\\% gap. This suggests that our method appears to offer a favorable time-quality trade-off.\n\nWe will carefully incorporate the above discussion into our revised paper for better clarification.\n\n\nOnce again, we would like to express our heartfelt gratitude for the time and effort you've dedicated to reviewing our work. We will carefully incorporate the above discussions into our revised paper. We sincerely hope that our response can address your concerns."}]

Author rebuttal:

Meta-review: This paper proposes a novel insertion-based paradigm for Neural Combinatorial Optimization (NCO), as an alternative to the conventional appending-based approaches, and demonstrates promising results on the Vehicle Routing Problem. By integrating model design, training strategy, and inference algorithms, the paper consistently outperforms existing baselines, and its novelty and usefulness are evident.

The review situation is as follows:

Reviewer havL and Reviewer fNy1 praised the novelty of the idea and the persuasiveness of the experiments, ultimately recommending Accept (5).

Reviewer hZDB initially raised concerns but found them sufficiently addressed through the rebuttal, raising the score to 4 (Borderline Accept).

In contrast, Reviewer s3Av provided some technical comments but did not engage at all with the authors’ detailed rebuttal. This lack of dialogue was flagged by the Area Chair as an insufficient review. Therefore, the reliability of this review is low and should not weigh heavily in the final decision.

Overall, the paper establishes a novel paradigm with clear originality and demonstrates promising results through solid experiments. The concerns raised have been adequately addressed by the authors, and remaining weaknesses are minor and can be improved in future work.

In conclusion, I recommend this paper for acceptance at NeurIPS.
Decision: Accept (poster)