Learning to Segment for Vehicle Routing Problems
Authors: Wenbin Ouyang
Sirui Li
Yining Ma
Cathy Wu
Venue: ICLR 2026 Oral (2026)
Keywords: Learning-Guided Optimization
Vehicle Routing Problem
Primary area: optimization

Abstract: Iterative heuristics are widely recognized as state-of-the-art for Vehicle Routing Problems (VRPs). In this work, we exploit a critical observation: a large portion of the solution remains stable, i.e., unchanged across search iterations, causing redundant computations, especially for large-scale VRPs with long subtours. To address this, we pioneer the formal study of the First-Segment-Then-Aggregate
(FSTA) decomposition technique to accelerate iterative solvers. FSTA preserves stable solution segments during the search, aggregates nodes within each segment into fixed hypernodes, and focuses the search only on unstable portions. Yet, a key challenge lies in identifying which segments should be aggregated. To this end, we introduce Learning-to-Segment (L2Seg), a novel neural framework to intelligently
differentiate potentially stable and unstable portions for FSTA decomposition. We present three L2Seg variants: non-autoregressive (globally comprehensive but locally indiscriminate), autoregressive (locally refined but globally deficient), and their synergy. Empirical results on CVRP and VRPTW show that L2Seg accelerates state-of-the-art solvers by 2x to 7x. We further provide in-depth analysis showing why synergy achieves the best performance. Notably, L2Seg is compatible with traditional, learning-based, and hybrid solvers, while supporting various VRPs.

Published as a conference paper at ICLR 2026
LEARNING TO SEGMENT FOR VEHICLE ROUTING PROBLEMS
Wenbin Ouyang, Sirui Li, Yining Ma," Cathy Wu MIT (oywenbin, siruil, yiningma, cathywu Jamy @mi @mit. edu
ABSTRACT
Iterative heuristics are widely recognized as state-of-the-arr for Vehicle Routing Problems (VRPs). In this work, we exploit critical observation: large portion of the solution remains stable, i.e., unchanged across search iterations, causing redundant computations, especially for large-scale VRPs with long subtours. To address this, we pioneer the formal study of the (FSTA) decomposition technique to accelerate iterative solvers. FSTA preserves stable solution segments during the search, aggregates nodes within each segment into fixed hypernodes, and focuses the search only on unstable portions. Yet, a key challenge lies in identifying which segments should be aggregated. To this end, we introduce Learning- Learning-to-Segmee to-Segment (L2Seg), novel neural framework to intelligently differentiate potentially stable and unstable portions for FSTA decomposition. We present three L2Seg variants: non- autoregressivve (globally comprehensive but locally indiscriminate), autoregressive (locally refined but globally deficient), and their synergy. Empirical results on CVRP and VRPTW show that 1.2Seg accelerates state-of-the-an solvers by 2x to 7x. We further provide in-depth analysis showing why synergy achieves the best performance. Notably, L2Seg is compatible with traditional, learning-bast based, and hybrid solvers, while supporting various VRPs.
INTRODUCTION
Vehicle Routing Problems (VRPs) have profound applications such as in logistics and ride-hailing, driving advances in combinatorial optimization (Laporte) 2009). As NP-hard problems, they
typically tackled with heuristics approximately. Neural Combinatorial Optimization (NCO) (Kool
al. 2018 Bengio al., 2021 Luo et 2025) Berto al. 2023) has recently introduced machine learning into VRP solving, enabling data-driven decision-maker makinn with minimal domain knowledge while matching and even surpassing the performance of meticulously designed heuristics such as (LKH) (HessaHelggaun) (2117) and Hybrid Genetic Search (HGS) (Vddal 2022).
Lin- Hann-eenighan-Heee
Generally, state-of- thrt- VRP solvers predominantly rely on iterative search to refine solutions through local search (e.g., ruin and repair). However, noted in Section 3 significant portion of edges stabiliza or their presence in the solution stops changing between iterations, as the search progresses, despite repeated local search. For example, inner edges of neighboring subtours may remain fixed while only boundary edges undergo frequent combinatorial changes. Intuitively, such stability be inferred from customer spatial distribution and the solution properties through end-to- end learning. Yet, existing solvers overlook such opportunities, leading to redundant computations that hinder their scalability and efficiency, especially in large-scale vRPs with long subtours.
Motivated by this critical observation, we study how learning to identify such segments can accelerate iterative search solvers, perspective yet to be explored to the best of our knowledge. To this end, formalize a Sewe-Seeeeee--e----gr--eeee stable segments in VRP solution and then aggregates them fixed (one or two) hypernodes with combined attributes (e.g., total demand, min/max time windows). This not only decomposes the
(FSTA) decomposition framework, which identifies
*Corresponding author.
'Specifically, we define stable edges as those that consistently remain in the solution across consecutive solver invocations, where each invocation performs a full optimization round (multiple local search operations) within fixed budget return locally optimal solution (see Appendix A.T for formal definitions).

---

Published as a conference paper at ICLR 2026
original large problem into more tractable subproblems but also significantly accelerates the search by leveraging iterative local search to strategically focus on unstable portions. We further show that FSTA preserves solution equivalence and is broadly applicable to VRPs with diverse constraints.
To identify unstable portions for FSTA dccomposition, we then introduce Learning-to-Segment to-Segment (L.2Seg). novel learning-guide framework that leverages deep models intelligently differentiate potentially stable and unstable portions, allowing dynamic decomposition for accelerated local search. Realizing this, however, is nontrivial: it involves large combinatorial decision space requiring accurate segment grouping, and demands modeling complex interdependencies among predicted edges, constraints, spatial distribution, solution structures, and both node and edge features.
To address these challenges, L2Seg proposes encoder-decoder-stylee neural models. The encoder integrates graph-level and route-level features using attention and graph neural networks, gener- ating node embeddings that guide edge re-optimization predictions. I.2Seg offers three decoders: (1) L2Seg-NAK -ooo-euurrerrsssiee) which features one-shot fast global prediction; (2) L.2Seg-AR -AR (Autoregressive), which enjoys sequential dependency modeling for high-precision local predictions; and (3) L2Seg-SYN (Synergized), which balances the strengths of both NAR and AR. Notably, this represents a pioneering work that explores the joint decision-making between AR and NAR models in neural combinatorial optimization. Our L2Seg models are trained via a weighted cross-entrops loss on datasets labeled using lookahead procedure: edge stability is classified based on whether its presence in the solution was changed during iterative re-optimization.
Extensive experiments on large-scale CVRPs and VRPTW's show that L2Seg accelerates backbone heuristics by 2x to 7x, enabling them to outperform state-of-the-arr classic, neural, and hybrid baselines, while generalizing well across different customer distributions and problem sizes. Notably, L2Seg exhibits strong flexibility in enhancing various solvers, including the classic LKH-3 (Helsgaun 2017) solver, other orthogonal Large Neighborhood Search (LNS) methods (Shaw) 1998), and
Sarning-guided decomposition method Learning-ter to-iieggtt-elegate (L2D) (Li et al. 2021). We further analyze the synergy between AR and NAR models, showing their combination achieves the best performance by integrating NAR's global comprehension with AR's s local precision.
Our contributions are: (1) We make a critical yet underexplored insight that stable segments persist across search iterations in large-scale VRPs, causing redundant computations; (2) We formally study and theoretically prove the properties and applicabilities of Sewe-eeeee--eennngggeeeeeeeeeeee for various VRPs; (3) We develop Learning-to-Seguee bespoke network architecture, training, and inference for segment identification; (4) We propose autoregressive, non autoregressive, and their synergistic deep models, pioneering the first-of-its-king study in NCO; (5) 1.2Seg consistently accelerates state-of-the-ar iterative VRP solvers by 2x to 7x, boosting both classic and carning-based solvers, including other decomposition frameworks.
(FSTA) (L2Seeg), learning-guide framework with
2 RELATED WORKS
VRP Solvers. Classical VRP solvers include exact methods with guarantees (Baldacci et al. 2012)
and practical heuristics (Helsgaun 2017). Recently, machine learning has been applied combi-
natorial optimization, either end-to-end (Kool et al. (0088: Kwon et al.) 20200] Fang et al., 2024
Geisler et al.) 20222 Gao al. [0244] Drakulic et al. 2023 Wang et al. 2024 Min al.) [023 Li
ct al. (202aa) or learning-guide
to unite data-driven insights into human solvers (Li et al. 2021 I
Lu et al.) 2023 Huang et al. 2024 2023 Hottung et al.; 2025). For VRPs, the former could yield
competitive performance to classic methods (Drakulic et al. [003 Luo et al., 2023), while the latter often achieve of-te-of-the-arr performance (Zheng et al. 2024). Among these, most effective VRP solvers rely on iterative search, including classic heuristics such as HGS (Vidal 2022). LNS (Shaw) 1998) and L.K (Helsgaun) (007); neural solvers that learn local search (Ma et al.) 2021 2023 Kim al. 2023 Hottung and Tierney 2022 Ma et al. (2022); neural constructive solvers integrated with search components (Luo et al./ 2023 Hottung et al. 20222 Kim et al. 2021 Sun and Yang 2023
Chalumeau et al. 2023 Kim al.) 2024 Qiu et (002)) y and hybrid sorming-guided methods like
L.D (Li et al.) 2021). However, both handcrafted and neural iterative search solvers overlook the
redundant computations identified in this paper, particularly in aarge-scale VRPs.
Decomposition for Large-scale VRPs. Scalability in VRP solvers often relies on effective de- composition that operates on solutions partially (Santini al. 2023). This includes hand-crafted
2

---

Published as a conference paper at ICLR 2026
heuristics, such LNS (Shaw] 1998) and evolutionary algorithms (Helsgaun 2017). well as learning-based methods such as sub-tour grouping (Zong et al. (022), problem variant reduction (Hou
et al. 2023), action space decomposition (Drakulic al. 2023; Luo et al. 2023 Zhou al. 2025a), spatial-based decomposition (Zheng et al. 2024 //hou et al. 2025b Pan et al.
2025). and hyper- graphs decomposition (Li et al. 2025 Fu et al. 2023). In fact, effective search space reduction is fundamental to modern optimization solvers, including LKH-3 (Helsgaun (017)) (via k-nearest reduc- tion), LNS (Shaw 1998) (via bounded neighborhood reduction), and exact solvers like Gurobi (via branch-and- bound reduction). Different from those hand-crafted ways of reduction, we present FSTA and L2Seg. a learning- based decomposition framework that advances this line by introducing stability estimation to intelligently detect unstable edges and aggregate stable segments in data-driven way. 1.2Seg introduces a fundamentally different decomposition paradigm compared to existing methods. Unlike LNS, which isolates bounded local neighborhood (e.g., 3-5 sub-routes) to destroy and rebuild. L2Seg operates globally across the entire solution, breaking edges and aggregating segments throughout all sub-routes simultancously without predefined neighborhood boundaries. Compared with ML-enhanced LNS methods like L.D eLi al. (022), which operate at the sub-route level (selecting which sub-routes modify), L.Seeg detects unstable edges both within and across sub-routes, enabling finer-grained, edge-level decomposition. Moreover, L2Seg is solver-agnostic and complementary: it can enhance most existing iterative methods such LKH and LNS, e.g., FSTA can be applied on top of LNS to fix stable edges globally within its selected neighborhood (see Appendix for detailed comparisons with representative decomposition methods). While another related work (Morabit et al., (024) explores segment stability for re-optimization in specific dynamic CVRP setting, our work addresses a different problem, i.e., identifying stable segments across search steps to accelerate iterative solvers. And we formally analyze the solution equivalence of FSTA across broader VRP variants. Moreover, L2Seg uniquely designs and integrates three novel deep learning models (AR, NAR, and synergized) to guide FSTA decomposition during search.
AR and NAR Models. In NCO, NAR models make global predictions like edge heatmaps (Sun) and Yang 2023 Li et al., 2023b). However, they struggle model complex interdependencies, particularly VRP constraints. contrast, AR models make sequential predictions, c.g., node by node selection in construction solvers (L. al. (023)). AR offers stronger modeling capacity but might overlook global structure. Recent NCO works combine AR and NAR models in divide-and- conquer frameworks, with NAR for problem splitting and AR for solving (Zheng et al.) 2024 Hou et al. 2023 Ye et al., 2024). We are the first to leverage their complementary strengths for joint decision-making enabling more effective identification of unstable segments in FSTA decomposition.
SRRST--EEMENNT-TENNAAGGGRE
(FSTA)
3.1 VEHICLE ROUTING PROBLEMS (VRPs)
CVRP2K, C=300 CVRP3K, C-300
3.32
VRPs aim to minimize total travel costs (often distance or travel time) while serving a set of customers under constraints. Formally, VRP instance P is defined on a graph G = (V, F), where each node x; E V represents a customer and each edge E4, E represents traveling from I; to xj and is associated with travel cost. For Capacitated VRP (CVRP), vehicles of capacity C' start and end at a depot node zi. The sum of the demands d; on any route must not exceed C, and each customer should be served exactly once. For VRP with Time Windows (VRPTW), each customer is additionally associated with a service time 8; and a time window [t], E within which service must begin. See Appendix [ for the formal definitions of CVRP and VRPTW.
gi24
Re-oo
16
8
11 16 21
# of iterative searches
Figure I: Percentage of re- optimized edges during it- erative search using LKH- 3 on 100 CVRP instances. Most edges remain un- changed, suggesting re- dundant calculations.
3.2 FSTA DECOMPOSITION
Figure I depicts that iterative search solvers perform redundant searches, reoptimizing only a small portion while many edges remain unchanged, especially in large subtours with high capacity C. Inspired by MMoabbi et al. (2024), we formally study the decomposition technique, First-Segment- Tgge-ggge (FSTA), for accelerating iterative search solvers. As shown in the top of Figure 2 FSTA segments the VRP solutions by identifying unstable portions, and then groups the stable
3

---

Published as a conference paper at ICLR 2026
Apgregate Segments Info Hypemodes
Ro opimae the Aggragaied Probiam
&
Unstable Edges
Info Segments
agoregated So utiio
Three Decoding Methods
Merge Unstacda Edges
L25eg-SYN
Netwonk
12Seg-NAR
L2Beg-AR
x
Problem
Non-AR Network
Idendly Inttial Target Nodes (Chaslering Predicted
Network Ied
Identify Intial Target Nodes for (Clustoring Nodes)
Predicted Unstable Nodes
Clastered Subopt. Regions
Intial Target Nodos for AR
"Oracle Nodes %
Predicted
are Bolded
Unstable Edgas
Figure 2: The overview of our FSTA decomposition framework (top) and the three proposed L2Seg models (bottom). L.2eeg-SY, employs a four-step synergized approach: (1) problem decomposition into subproblems, (2) unstable nodes detection globally via NAR decoding, (3) clustering of NAR- predicted nodes to localize unstable regions and select initial target nodes, and (4) refining unstable edge predictions locally via AR decoding starting from these identified initial target nodes.
segments into hypernodes. We thus expect more efficient re-optimization on the reduced problems with smaller size. More visualization of FSTA is provided in Appendix(B..
Segment Definition. Denote the solution (set of routes) of CVRP R R R²2 route as R = (Io + xi + z + + xp) E R. where the first and the last nodes in Ht' are the depot. A segment consists some consecutive nodes within a route. We denote the segment containing the 5th ktth nodes of route as Si k = (z) + + zf.) An aggregated segment S ( H) or two hypermodes ($ (.), a with aggregated attributes (e.g. the demand of " equals to d3 + +... + d()) represent the non- non-aggregae aggregated segment S),,
and each
uses one hypernode (5) j.
FSTA Solution Update. After identifying unstable edges .e),,e/,.....) } in each route (which will be addressed in Section 4). where each ex denotes the edge starting from the jth node in route R', we break these edges and group the remaining stable edges into segments. To preserve valid depot, edges connecting to the depot are included in the unstable edge set. After unstable edges are removed, each route Rt is then decomposed into multiple disjoint segments {2o, Si,,, S2 ...), where zg depot. Each segment S) is then aggregated into one two hypernodes SJ,,, leading to reduced problem P. We then obtain the corresponding solution R. for such reduced problem, where for each R' E R, we have R' = (Io + S + St $1.do - 2o). With fewer nodes than the original problem P, re-optimization with backbone solver becomes more efficient, which is analyzed and confirmed in Appendix B.1 After re-optimization,
obtain
solution R4 for the reduced
problem P. which is then recovered into solution R., for the original problem by expanding each hypernode(s) back into its original segment of nodes. This relies on our monotonicity theorem, which guarantees that an improved solution P maps to an improved solution in P.
Theoretical Analysis. We establish theorem proving FSTA's feasibility and monotonicity across multiple VRP variants (e.g. CVRP, VRPTW, VRPB, and I-VRPPD), with the proof in Appendix B.2
Theorem (Feasibility)) the aggregated solution R. is feasible to the aggregated problem, then R. also feasible the original, non-aggregated problem.
Theorem (Monotonicity). two feasible aggregated solutions R! and R3 satisfy f(R)) f
where f() denotes the objective function (total travel cost), their corresponding original solutions also preserve this order: f(R4) < (RR2).
4

---

Published as a conference paper at ICLR 2026
Deletion
Insertion
HLP+ Big rold
Encottrr
GRU
Roula Engoding
Graph with Input Pestures
Node
Last
Node
MHA
NHA
Encoder
Goagh Freanding
Decoder
NonaR
Availabl
AR Decoder
Figure 3: Architecture of L2Seg: encoder (left), NAR decoder (center), and AR decoder (right). NAR predicts unstable nodes for associated edges. AR uses a two-stage process, where the insertion bridges the deletion stage to accurately detect unstable edges locally, akin to the local search behavior.
LEARNING TO SEGMENT (L2SEG)
We introduce Learning Segment (I.2Seg), neural framework for predicting unstable edges to guide FSTA. We consider two paradigms: 1) ron-autoreeressive (NAR) and 2) Autoregressive (AR) models. NAR models offer global predictions with an efficient single forward pass. However, they lack conditional modeling to accurately capture local dependencies. For example, when one edge is unstable, nearby edges often show instability but not all, but NAR models may fail to distinguish them and mark all neighboring edges as unstable. On the other hand, AR models can more natively capture local dependencies. Yet, they may miss the crucial global structure, For example, when unstable edges are distributed across distant regions, AR models may struggle to recognize and model these broader patterns. Our approach offers three variants as shown in Figure (2] non-autoregressiv (L2Seg-NAR) autoregressive (L2Seg-ARD and synergized combination of both (L2Seg-SYN),
4.1 NEURAL ARCHITECTURE
The autoregressive and non-autoregressive models of L2Seg share the same encoder structure. Next, we first describe the encoder, and then the two decoder architectures.
Input Feature Design. We propose enhanced input features for L2Seg to better distinguish unstable and stable edges (see Appendix [. for intuitions). Key features include node angularity relative to the depot and node internality, where the latter measures the proportion of nearest nodes within the same route. We consider two edge types: edges in the current solution R and edges connecting each node to their k-nearest neighbors. Appendix C.2 provides a detailed feature description.
(Xo, .)) and edge features E = {ea,1, eo. we compute the initial node embedding as hi = Coneat(h,MAA h,o0) E IR,2d,, where MMPP and hypoS are obtained by passing x; through a multilayer perceptron (MLP) and an absolute position encoder (Vaswani] 2017). respectively. Next, we process the embeddings using LIFM Transformer layers (Vaswani] (017) with masks prevent computation between nodes in different routes: h, TFFM-TFM (h E dRd This step encodes local structural information from the current solution.
Encoder. Given node features X
Finally, we compute the node embeddings HGNN = (h,NN Rd | i O..... [V]) leveraging the global graph information by using LGNN layers of Graph Attention Network (GAT) (Veličkovid) al. 2017), where HGNN BGNNNGGNN (HLFM, E).
Auooeeetreeeeesvvee Decoder. It uses an MLP with a sigmoid function to decode the probability NAR of each node being unstable globally in one shot, as identify associated unstable edges:
p NAR - MLP (HNNN)
Autoregressive Decoder. The autoregressive decoder models unstable edge interdependence by generating them sequentially as a {I "xj... J. Following classical local search where removed edges are reconnected via A: new insertions (Funke et al. 2005), the sequence alternates between deletion (identifying unstable edges) and insertion (introducing pseudo-edges that bridge to the next unstable edge), terminating at Zead- Note that the "insertion" stage is designed to model dependencies between consecutive unstable edges rather than actually "insert" edges into the solution. Formally, denote the set of edges within the current solution as FR. The decoding alternates between:
5

---

Published as a conference paper at ICLR 2026
(I) Deletion (t = 2k): Selects unstable edge Fx ER based target node, which is either initialized at the first step (see Section (4.) or the one obtained from the previous insertion step; one of the two edges connected to this node in the current solution is then selected unstable (more than two candidates may exist the node is the depot); importantly, this edge is only marked as unstable, not immediately removed from the solution; and (2) Insertion (t 2k: 1): Selects an new edge E 1, -2x-2 & ER that links to the endpoint of the last unstable edge removed, exploring ([VV) potential candidates serve as bridge the next unstable target node (next unstable region). From a, we then identify the set of removed edges as the unstable edges. i.e., Eunstable = m Cro, Both stages employ two principal modules: Gated Recurrent Units (GRUs) (Chung et al. (2014) to
encode sequence context, and multi-head attention (MHA) (Vaswani, (017) for node selection. The
/ Σ!!! h,NNN At step t, the sequence embedding is updated by h = GRUCh,un (h h ), and the context embedding is formed by concatenating the embeddings of the initial node, the previous node, and the new sequence h,
GRU's initial hidden state the average of all node embeddings: h h
embedding: H. Concat (GGNN h GNN
51 1
distinct MHA modules with L MMA layers, to decode TN2- Specifically, considering the size of the action space (at most 2 for deletion and O((V)) for insertion), we utilize shallow decoder delete 1) during the deletion stage and a deeper decoder (LA 4) during the insertion stage. Let H. C HGNN denote the set of available nodes at step t. During the insertion stage. we also incorporate an additional candidate h cNNNN +(1 a) [ Ei= Eiooh,NN h,NNN where is learnable parameter, to indicate termination of decoding, providing the AR model flexibility determine the number of unstable edges. Formally, the decoding at step given as follows; note that the first dimensions of H (L (LL))AA corresponds to context embeddings H. Hoontex and hence masked from selection:
Inspired by the decoder design in LEHD (Luo et al. 2023
H (0) Concat (H; (Hoontext, H.),
H (1) MHA (H
(W,h")7Wah, (L MHA /d.. if 3,
U1
00,
O.W.,
where 1 1 L MHA W and Wi are learnable matrices, and h ERod concatenates the first three columns of (0) and H MIrA along the last axis. The node Fs, is sampled from AR softmax(u)
4.2 TRAINING
We employ iterative solvers as look-ahead heuristics to detect unstable edges. We utilize imitation learning to train L.2Seg models to replicate the behavior of the look-ahead heuristics.
Dataset Construction. Let the edges in R be ER, and nodes indicated by edge set E be Vg. Given P with cur-
New'
... Didutei
Connected
Exemplary Connected Component
rent solution R, we first employ an iterative solver S to
Deietro: Stage
Donetion Stago
refine R and obtain R_.. We then collect differing edges as R and R., as Edit- (ER \ ER, )U(RR, ER) (in- cluding both the deleted and newly inserted edges). Next, we identify the set of unstable nodes V Vunstable = VEaae i..., the Ean- We empirically observe that solution refinement typically takes place between two adjacent routes. For the NAR model, we construct dataset with binary la- bels. Each problem-label pair consists of a decomposed problem containing two adjacent routes and binary la- bels indicating whether each node is unstable (1) or stable (0), Formally, node is labeled 1 if x Vunstable- For the AR model, we construct labels as node se- quences preserving local dependencies among unstable
Insrrton Stago
Iisefiio Stago
Label (Sequence Nodes) For the Alt Model
nodes that are end points some edge in
Figure 4: Training data construction for the AR model. Re-optimization reveals deleted edges (blue/green dashed) and in- serted edges (red dashed) forming con- nected components (circles). For each component, depth-first search generates node sequences alternating between dele- tion and insertion stages, terminated by an end token as the AR model's training label.

---

Published as a conference paper at ICLR 2026
edges. Nodes without local dependencies naturally excluded through connected component partitioning. We obtain connected components AC induced by Editl and select those spanning at most two routes, denoted KTR. For each K KTR containing nodes from routes R; and R., form subproblem Px with solution Rx = { [, R2). From each component K' (dashed circles in Figure 4. we extract node sequence у/K (T Iny ................................ "...........> Fend by alternating between edge deletion and insertion operations (shown in Figure second row). These problem-labe pairs (PK. WK) constitute the AR model training data.
Loss Function. To balance labels, we use weighted binary cross-entropy for the NAR model (Wpos > 1) and weighted cross- entropy for the AR model to balance the two stages (Winsert > Wdelete).
(P NAR -80)
Σ
ppss Uza, log (pg NAR) + (1 Men) log(1 Pk NAR)
Bag Eye
LA AR .yK
Σ
Winsert log (P
Σ
Wdelect log (p
Zagu EUK
Tanu+1
4.3 INFERENCE
We describe the synergized inference that combines the benefits of global structural awareness from NAR with the local precision from AR, followed by two variants using only NAR or AR.
Synergized Prediction (L22Seg-SYN) L2Segg L.Segg-SSy SYN's inference pipeline for detecting unstable edges consists of four steps: (1) problem decomposition, (2) global unstable node detection via NAR decoding, (3) representative initial node identification for AR decoding based on NAR predictions, and (4) local unstable edge detection using AR decoding.
Given a problem P' with solution R, we partition /' into approximately [R] subproblems, PTR, by grouping nodes from all two adjacent sub-tour pairs. For each subproblem in PTR. the NAR model predicts unstable nodes as ÚNAR = {a, NAR 2 n7,, where is a predefined threshold. We then refine unstable edge detection with the AR model within regions identified by the NAR prediction. To reduce redundant decoding efforts on neighboring unstable nodes, we first group unstable nodes into MEANS clusters using the K-means algorithm, and select the node with the highest y NAR within each cluster as the starting point for AR decoding. The AR model then detects unstable edges based on these initial nodes. Finally, we aggregate unstable edges from all subproblems in PTR as the final unstable edge set for P given the current solution R.
Non-Autoreereesivve Prediction (L.2Seg-NAR, L2Seg-NAK -AR uses only the NAR model for predic- tions. It identifies unstable nodes and marks all connected edges unstable.
Autoregressive Prediction (L2 L2Seg-AR AR exclusively uses the AR model. Instead of using the NAR model, it assumes all nodes may be unstable, applying the K K-means algorithm all nodes. then selects the node closest to each cluster center as the initial node for AR-based decoding.
EXPERIMENT
Our decomposition- FSTA and L2Seg excel on large-scale problems. In this section, we first evaluate how L2Seg-AR, L2Seg-NAR, and L2Seg-SYN accelerate various learning and non-learning iterative solvers on large-capacity CVRPs with long subtours. Next, we compare L2Seg against state-of-the-ar baselines on standard benchmark CVRP and VRPTW instances. Finally, we provide in-depth analyses of our pipeline. Additional results on CVRPLib benchmarks, clustered CVRP, heteroogenoous-demandd CVRP, case study, and further discussions are presented in Appendix
E
Backbone Solvers. We apply 1.2Seg to three representative backbones: LKH-3 (Helsgaun 2017) (classic heuristic), LNS (Shaw 1998) (decomposition framework), and L2D (Li et al. 2021 (learning- guided hybrid solvers, or machine-learning enhanced LNS) to demonstrates the broad applicability. See Appendix D.I for details.
Baselines. We include sfate-of-the-an classic solvers (LKH-3 (Helsgaun, 2017). HGS (Vidal 2022 )
neural solvers (BQ (Drakulic et al.) 2023), LEHD (Luo et al. 2023), ELG (Gao et al. 2024). ICAM
(Zhou et al. 2024), L2R (Zhou et al. 2025a). SIL (Luo et al. 2025 2024)), and learning- based
divide-and-conquer methods (GI.OP Ye al. 2024 TAM (Hou et al. 2023). UDC (Zheng et al.
7

---

Published as a conference paper at ICLR 2026
Table Performance comparisons of our proposed L2Seg- NAR, L2Seg-AR, and L.2Seg-SYN when accelerating three backbone solvers, LKH-3, LNS, and L2D, on the large-capucity CVRP instances. We report the objective value, improvement gain (%), and the time. The gains (the higher the better) are w.r.t. the performance of each back- bone solver. Time limits were set to be 150s for CVRP2k and 240s for CVRP5k, respectively.
45.5
45.0
LXH-3-LL25gg-50
Objeetiun
LNS
LN5-125eg-51N
44.5
120-125eg-SYW
44.0
43.5
20
60
100
140
Time (s)
66.0
LKH-3
Methods
Obj.
CVRPIK Gaint
Timel
Obj.
CVRPSK
Gaint
Time
Objective
65.6
LNS
1XH-3+12Seg-SMM
5.7x
LN5-L25eg-551
LKH-3 (Helsgann 2017
45.24
0.00%
152s
65.34
0.00%
242s
65.0
22Seg-NA--LKR
158s
246x
-125gg SYN
L2Seg-AR-LKH--
44.23
2.23%
151s
64.67
1.03%
2446
64.5
43.92
2.92%
152s
64.12
1.87%
248s
2.0g
LNS [Shaw. 1998
44.92
0.005%
154s
64.69
0.00%
246x
NAR
44.12
1.78%%
154k
64.38
0.48%
244s
L2Seg-AR-LNS
44.02
2.00%
1578
64.24
0.70%
24%
Time
L28eegSYNNL.NS
43.42
3.34%
152g
63.94
1.16%
241s
Figure 5: Search curves for L2Seg on
L2D el.
153s
three backbone solvers on large capacity
LNSGg-NAK-122
43.55
0,32%
152s
64.02
0.30%
2436
L2Scg-AR-L.2D
43.53
0.37%
1568
247s
CVRP2k (upper) and CVRP5k (lower).
L28eg-5YN-1.2D
43.35
0.78%
157%
63.89
0.50%
248s
L2Seg achieves up to 7x speedups.
2024), L.2D (L et al. 2021), NDS (Hottung al.
2025 ). We renun LKH-3, LNS, L.2D, SII and NDS and report results from Zheng et al. (2024): Zhou et al. (2025a): Luo et al. (2024) for other baselines using the same benehmarks. See Appendix D.2 for baseline setup details and Appendix D.3
for L2Seg hyperparameters.
Data Distribution. We generate all training and test instances following prior works Zheng et al. (2024) for CVRP and Solomon (187) for VRPTW. See Appendix D.4 for details. For Section 5. results are averaged over 100 large-scale CVRP test instances at 2k and 5k scales (capacities 500 and 1,000, respectively). For Section 5.22 we follow standard NCO benchmarks, reporting averaged results on 1k, 2k, and 5k test datasets with 1,000 CVRP and 100 VRPTW instances per scale.
Evaluation and Metric. We impose time limits of 150s, 240s, and 300s for CVRP1k, 2k, and 5k, and 120s, 240s, and 600s for VRPTWIK, 2k and 5k, where each solver may finish a few seconds (< 10s) beyond its limit. We set ? = 0.6 and zirmfans
for our L2Seg. We report averaged cost and per-instance solve time for all cases, and report percentage improvements over backbone in Section 5. and gaps to HGS (the best heuristic solvers) for both CVRP and VRPTW Section 5.2
5.1 L2SEG ACCELERATES VARIOUS ITERATIVE BACKBONE SOLVERS
We first verify the effectiveness of the three L2Seg variants to enhance backbone solvers. Table presents results large-capacity, uniformly distributed CVRPs with long subtours. All L2Seg vari- ants consistently improve each backbone across all problem scales. Also, performance gains are larger for weaker backbones. While L2Seg-AA AR and L.Seg-NNA -AR each boost performance, their combination (I (L.2Seg-SYN) delivers the best solutions. 5 average objective curves over time, which re- veal 2x to 7x speedups on the backbone solvers with L.2Seg-SY -YN.. Remarkably, L.2eeg- augeeg-tgmmmntaiionn lets weaker solvers surpass stronger ones (e.g., LKH-3 + L.SeegSY outperforms vanilla LNS).
5.2 L2SEG OUTPERFORMS CLASSIC AND NEURAL BASELINES ON CVRP AND VRPTW
We evaluate the gighest-performing 1.2Seg- -SN implementation with three distinct backbone solvers and compare against kate-of-the-are classical and neural approaches. As demonstrated in Table 2 L2Seg surpasses both classical and neural baselines on CVRP and VRPTW benchmarks. For CVRP,
L2Seg achieves superior performance within comparable computational time relative to competitive classical solvers, including HGS on larger problem instances. It also outperforms the of art learning- beaseng-baseed constructive solver SIL (Luo et al. 2025 2024) and weriid-and-oonueee solver L2D (Li) ctt al. 202I) across all problem seales. For VRPTW, L2Seg exceeds all classical and Baaning-basee solvers across various scales under identical time constraints, with performance advantages increasing
8

---

Published as a conference paper at ICLR 2026
Table 2: Performance comparisons of our L2See-SSYN-LA against baselines on benchmark CVRP and VRPTW instances. The gap % (lower the better) is w.r.t. the performance of HGS.
CVRPIk
CVRP3k
CVRPSk Gopl
Ohjil
Gap)
Time|
Ohj.l
Gapl
Time]
Obj
Time
HGS
Vidal 2022
41,20
0.00%
5m
57.20
0.00%
5m
126.30 20
0.00%
5m
LKH-T TeSESR 2017
42.98
4.32%
6.6m
57.94
1.29%
11.4m
175.70
39.22%
2.5m
LNS
Snaw 1999
42.44
3.01%
2.5m
57.62
0.73%
4.0m
126.58
0.30%
5.0m
Drakulic
55s
62.59
9.42%
139,80
10.78%
45m
LEHD Lai ot 21 Miza
43,96
6.70%
1.3m
61.58
7.66%
9.5m
138.20
9.51%
3h
HLG
43,58
7.78%%
15.6m
ICAN
26a
61.34
7.24%
136.90
L2R
44.20
7.28%
34.2s
131.10
3.88%
1.8m
SIL.
Lio
20244
42,00
1.94%
1.5m
57,10
-0.17%
3.0m
123,25
-2.33%
6.8m
(H-()
(Hogett 2023
46.30
4m
13 29%
9.6m
144.60
14.58%
GLOR-GILKHSS
Te
2024
45,90
11.41%
2m
63.02
10.52%
2.5m
140.40
11 11.25%
8m
UDC Zheng
43,00
4.37%
1.2h
60.01
4.9%
2.15b
136.70
8.32%
16m
2.11%
2.5m
0.42%
4.2m
126.48
NDS
Hotting orain 2025
41.16
-0.01 %
2.5m
56.11
-1.911%
4m
L2Seg-SYN-LKKH
41,42
0.53%
2.5m
56.37
45%
122.34
-3.16%
5.1m
L28cg-SYN-LNS
41.36
0.39%
2.5m
56.08
-1.96%
4.1m
121.96
-3.48%
5.1m
L2Neg-SYN-L.2D
41,23
0.07%
2.5m
$6.05
-2.01% %
4.1m
121.87
.3.55%
5.1m
Methods
VRPTWIK Ik
VRPTW2K
VRPTWSK
Obj.i
Gapl
Timec
Gapl
Timel
Obj.4
Gap
Timel
HGS Vidal 20223
90.35
0.00%
2m
173.46
0.00%
4m
344.2
0.00%
10m
LKH-3 Hesspon 2017
91.32
1.07%
2m
174.25
0.46%
4m
353.2
2.61%
10m
195%
2m
-4. .4.44%
338.5
L2D
Li al 2021
88.01
-2.59%
2m
164.12
-5.38%
Am
335.2
-2.61%
10m
NDS
2025
87.54
-3.11%
2m
167.48
-3.45%
4m
L2Seg-SVV SYN-LKHI-
88.65
-1.88%
2m
169.24
-243%
4m
345.2
0.295
10m
128eg SYN---S
87.31
-3. 36%
2m
163.94
-5. -5.49%
4m
334.1
-2,93%
10m
L2Seg-SYN-L.2D
-5.60%
333.4
Table 3: Performance of L2Seg-SST SYN v.s. Random FSTA to accelerate LNS on CVRP instances.
Methods
LNS (Backbone)
Random PSTA (40%)
Random FSTA (60%)
L2Scg-SYN w/o Enhanced Features L2Seg-SYN
CVRP2
44.92
46.24
46.89
43.65
43.42
CVRP5k 64.69
66.72
65.92
64.22
63.94
as problem size grows. Notably, L.2Seg consistently enhances performance when integrated with any backbone solver, demonstrating its versatility. Additional analyses are provided in Appendix E
5.3 L2SEG PERFORMS AND GENERALIZED WELL ON MORE REALISTIC CVRP
To demonstrate L2Seg's 's robustness beyond uniform distributions, we evaluate both in-distribution and zero-shot generalization on instances with clustered customers and heterogeneous demands-pattenns common in real-world logistics. As shown in Table [2, L2Seg maintains strong performance across all settings: zero-shot transfer achieves 0.82%-3.111 30% improvements over LNS, while in-distribution models reach 1.02%-3.554 33.54% gains. These consistent improvements across diverse distributions validate 1.2Se''s 's practical applicability. See Appendix H.3 for details.
5.4 FURTHER ANALYSIS AND DISCUSSIONS
Ablation Study. Table 3 compares the LNS backbone; random FSTA with 40% and 60% of edges arbitrarily marked as unstable; 1.2Seg- SYN w/o enhanced features; and full I.2Seg-SYN. Results show that Random FSTA worsens performance; and only full L2Seg-SYN with enhanced features achieves top performance. This confirms that L2Seg's 's learnable, Seature-guider segmentation is indispensable for preserving high-quality segments in FSTA for boosting backbone solvers.
High Recall or High TNR? Higher Recall allows more unstable edges to be reoptimized, potentially improving performance, while higher TNR reduces problem size and runtime. However, due to learning imprecision, pursuing high TNRs often reduces Recall, causing premature convergence. Figure shows that for I.2Seg-SYN, fixing too few (left: high Recall, low TNR) or too many (right:

---

Published as a conference paper at ICLR 2026
Table Model prediction analysis of L2Seg-LNS on CVRP2k.
Ground Truth
Predited Unstasle Edges
Methods
Recall"
TNRT
0bj-
aud Die
L2Seg-SYN
89.02%
61.24%
43.42
Ground Truth
L28ag-SYN
128ag-NAR
1.28ag- AR
L2Seg-NAR
91.46%
51.79%
44.02
L2Seg-AR
74.39%
54.07%
44.12
Figure 6: Illustration of L2Seg model behaviors.
high TNR, low Recall) degrades performance. Ours (middle) balances this tradeoff for optimal performance.
Why NAR+AR Is the Best? Figure a conceptual illustration of the model's s behaviour across 1.2Seg variants (See Appendix E.3 for real case-study). L2Seg-NAR identifies unstable regions but over-classifies due to the lack of dependency modeling, while L2Seg-AR models dependencies but struggles with initial detection. L.2Seg- SYN achieves the complementary synergy. Moreover, Table Auble/furthe further shows that L2Seg-SYN achieves the best balanced Recall and TNR for the best performance.
1.00
Metric Values
Size Racall THR
O61
engeeloo
0.00
Oomsrrvetive
Moderste
Aupr madoe Reddutionn
(g.-0.9. PNSCANS
21 - 0.5, norrwss 3360 0.3. (AMEAS
Configuration
Figure 7: Statistic values of Size (re- duced/original ratio), Recall, and TNR across three L.See-SYY configurations.
The Structure of the Stability Labels. We hypothesize that stability labels are composed of two factors: (I) Inher- ent Problem Structure (e.g., edges common to the majority of local optima regardless of the solver), and (2) Solver- Deeleer-eeeenentt Patterns (edges preferred due to specific search biases). We designed an experiment on CVRPIk to compare label similarity across different solvers. We generated labels using HGS (60s time limit) and LKH-3 (1000 local search steps), comparing them against "ground truth" generated by LKH-3 with much longer run (3000 steps). Each solver was run with 10 different seeds remove randomness. Label similarity is defined the percentage of overlapping stable edges. As shown in Table 5] these results reveal two key insights: (1) Even fundamentally different solvers (HGS vs. LKH-3) share 78.3% of stable edges. This indicates that the majority of the stability is contributed by inherent problem structure rather than solver artifacts; (2) More similar solvers produce more similar labels (LKH-3 variants: 85.1% % similarity) compared to fundamentally different solvers (HGS vs LKH-3: 78.3%), suggesting some solver-specific patterns.
Table Label similarity across different solvers
HGS
LKH-3 (1000 Local Search Step)
LKH-3 (3000 Local Search Step)
Label Similarity
78.3%
85.1%
100% (by default)
6 CONCLUSION
This work introduces Learning-to-Segment (L2Seeg), a novel learning-guidee framework that accel- erates state-of-the-art iterative solvers for large-scale VRPs by 2x to 7x. We formalize the FSTA decomposition and employ a specialized encoder-decoder architecture dynamically differentiate potentially unstable and stable segments in FSTA. L2Seg features three variants. L2Seg-NAR, L2Seg- AR, and 1.2Seg-SYN pioneering the synergy of AR and NAR models in NCO. Extensive results demonstrate 1.2Seg's sfate-of-the-art performance on representative CVRP and VRPTW and flexibil- ity in boosting classic and learning-basee solvers, including other decomposition frameworks. One potential limitation is that L2Seg not guaranteed boost all VRP solvers across all VRP variants. Future work includes: (1) extending L2Seg to accelerate additional VRP solvers (e.g.. Vidal (2022) ); (2) applying L2Seg to more VRP variants and other combinatorial optimization problems; and (3) expanding the synergy between AR and NAR models to the broader NCO community. Our code is publicly available at /tthttt:////itt
com mi t wu- lab/ /e ng-
to- segment
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENT
This research was supported by gift from Mathworks, as well partial support from the MIT Amazon Science Hub, the National Science Foundation (NSF) award 2149548 and CAREER award 2239566, and an Amazon Robotics Fellowship. The authors acknowledge the MIT SuperCloud and Lincoln Laboratory Supercomputing Center for providing the high-performance computing resources that contributed to the research results reported in this paper. We particularly thank Andrea Lodi for the insightful discussions throughout this project, especially during its initial stages. We also thank Zhongxia "Zee" Yan, Jianan Zhou, and Samitha Samaranayake for their valuable input.
REPRODUCIBILITY STATEMENT
We provide comprehensive technical details the appendices: architecture and input features (Ap- D.3). data generation (Appendix D.4), training procedures (Appendix (C.4), and experimental setup (Section p.. The complete codebase, including code and pre-trained models, will be released on GutHub under the MIT License upon publication.
REFERENCES
Gilbert Laporte. Fifty years of vehicle routing. Transportation science, 43(4):408-416 2009.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2018.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour d' d'horizon. European Journal of Operational Research, 290(2):405-421, 2021.
Fu Luo, Xi Lin, Yaoxin Wu, Zhenkun Wang, Tong Xialiang, Mingxuan Yuan, and Qingfu Zhang. Boosting neural combinatorial optimization for large-scale vehicle routing problems. In The Thirteenth International Conference Learning Representations, 2025.
Federico Berto, Chuanbo Hua, Junyoung Park, Laurin Luttmann, Yining Ma, Fanchen Bu, Jiarui Wang, Haoran Ye, Minsu Kim, Sanghyeok Choi, Nayeli Gast Zepeda, André Hottung, Jianan Zhou, Jieyi Bi, Yu Hu, Fei Liu, Hyeonah Kim, Jiwoo Son, Haeyeon Kim, Davide Angioni, Wouter Kool, Zhiguang Cao, Jie Zhang, Kijung Shin, Cathy Wu, Sungsoo Ahn, Guojie Song, Changhyun Kwon, Lin Xie, and Jinkyoo Park. RL4CO: extensive reinforcement learning for combinatorial optimization benchmark. arXiv preprint vxXiv:236.117100 2023.
Keld Helsgaun. An extension of the lin-kernighan-hellgaan tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12:966-980, 2017.
Thibaut Vidal. Hybrid genetic search for the evrp: Open-source implementation and swap* neighbor- hood. Computers & Operations Research, 140: 105643, 2022.
Paul Shaw. Using constraint programming and local search methods to solve vehicle routing problems. In International conference principles and practice of constraint programming, pages 417-431. Springer, 1998.
Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. Advances in Neural Information Processing Systems, 34:261 01222619--22111 2021.
Roberto Baldacci, Aristide Mingozzi, and Roberto Roberti. Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. European Journal of Operational Research, 218(1):1-6, 2012.
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 P Processing Systems, volume 33, pages 21 188-21 118-21199 198, 2020.
11

---

Published as a conference paper at ICLR 2026
Han Fang, Zhihao Song, Paul Weng, and Yutong Ban. Invit: A generalizable routing problem solver with invariant nested view transformer. Forty-first Interaational Conference on Machine Learning, 2024.
Simon Geisler, Johanna Sommer, Jan Schuchardt, Aleksandar Bojchevski, and Stephan Günnemann. Generalization of neural combinatorial solvers through the lens of adversarial robustness. In International Conference on Learning Representations, 2022.
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 Proceedings of the Thirty-Firss International Joint Conference Artificial Intelligence, 2024.
Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean- Mare Andreoli. BQ-NCO: Bisimulation quotienting for generalizable neural combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
Chaoyang Wang, Pengzhi Cheng, Jingze Li, and Weiwei Sun. Leader reward for pomo-based neural combinatorial optimization. arXiv preprint arXiv:2405. /3947, 2024.
Yimeng Min, Yiwei Bai, and Carla P Gomes. Unsupervised learning for solving the travelling salesman problem. Advances in Neural Information Processing Systems, 2023.
Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. From distribution learning in training to gradient search in testing for combinatorial optimization. Advances in Neural Information Processing Systems, 2023a.
Han Lu, Zenan Li, Runzhong Wang, Qibing Ren, Xijun Li, Mingxuan Yuan, Jia Zeng, Xiaokang Yang, and Junchi Yan. ROCO: A general framework for evaluating robustness of combinatorial optimization solvers on graphs. International Conference on Learning Representations, 2023.
Taoan Huang, Aaron M Ferber, Arman Zharmagambetov, Yuandong Tian, and Bistra Dilkina. Contrastive sedfiic-and-searde for mixed integer linear programs. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp. editors, Proceedings of the 41 International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 19757-19771. PMLR, 21-27 Jul 2024. URL https::/prrceedding: ml press htw.://insssr..se/////epa.t.t.ee v235 huang html
Taoan Huang, Aaron M Ferber, Yuandong Tian, Bistra Dilkina, and Benoit Steiner. Searching large
neighborhoods for integer linear programs with contrastive learning. In International Conference on Machine Learning, pages 13869-13890. PMLR, 2023.
André Hottung, Paula Wong-Chung and Kevin Tiemney Neural deconstruction search for vehicle routing problems. Transactions on Machine Learning Research, 2025.
Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. Advances in Neural Information Processing Systems, 36:8845-8864, 2023.
Zhi Zheng, Changliang Zhou, Tong Xialiang, Mingxuan Yuan, and Zhenkun Wang. Ude: A unified neural divide-and-conquer framework for large-scale combinatorial optimization problems. In Advances in Neural Information Processing Systems, 2024.
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 Advances in Neural Information Processing Systems, volume 34, pages 11096-11109 107, 2021.
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, 2023.
Minjun Kim, Junyoung Park, and Jinkyoo Park. Learning to cross exchange to solve min-max vehicle routing problems. In The Eleventh International Conference Learning Representations, 2023.
12

---

Published as a conference paper at ICLR 2026
André Hottung and Kevin Tiemey. Neural large neighborhood search for routing problems. Artificial Intelligence, page 103786, 2022.
Yining Ma, Jingwen Li. Zhiguang Cao, Wen Song, Hongliang Guo, Yuejiao Gong, and Yeow Meng Chee. Efficient neural neighborhood search for pickup and delivery problems. In Proceedings of the Fhist International Joint Conference on Artificial Intelligence, IJCAI-22, pages 4776-4784, 7 2022.
André Hottung, Yeong-Dae Kwon, and Kevin Tierney. Efficient active search for combinatorial optimization problems. In International Conference on Learning Representations, 2022.
Minsu Kim, Jinkyoo Park, and joungho kim. Learning collaborative policies to solve np-hard routing problems. In Advances in Neural Information Processing Systems, volume 34, pages 10418-10430, 2021.
Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
Felix Chalumeau, Shikha Surana, Clément Bonnet, Nathan Grinsztajn, Arnu Pretorius, Alexandre Laterre, and Thomas D Barrett. Combinatorial optimization with policy adaptation using latent space search. In Advances in Neural Information Processing Systems, 2023.
Minsu Kim, Sanghyeok Choi, Jiwoo Son, Hyconah Kim, Jinkyoo Park, and Yoshua Bengio. Ant colony sampling with gflownets for combinatorial optimization. arXiv preprint arX1v 2024.
Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. Dimes: A differentiable meta solver for combinatorial optimization problems. Advances in Neural Information Processing Systems, 35:25531-25546, 2022.
Alberto Santini, Michael Schneider, Thibaut Vidal, and Daniele Vigo. Decomposition strategies for vehicle routing heuristics. INFORMS Journal on Computing, 35(3):5433 -5554,555999-1 2023.
Zefang Zong, Hansen Wang, Jingwei Wang, Meng Zheng, and Yong Li. Rbg: Hierarchically 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 4658, 2022.
Qingehun Hou, Jingwei Yang, Yiqiang Su, Xiaoqing Wang, and Yuming Deng. Generalize learned heuristics to solve large-scale vehicle routing problems in real-time. In The Eleventh International Conference on Learning Representations, 2023.
Changliang Zhou, Xi Lin, Zhenkun Wang, and Qingfu Zhang. L2r: Learning to reduce search space for generalizable neural routing solver. arXiv preprint arXiv:2503.03133 2025a.
Shipei Zhou, Yuandong Ding, Chi Zhang, Zhiguang Cao. and Yan Jin. Dualopt: A dual divide-and-optimize algorithm for the large-scale traveling salesman problem. arXiv preprint arXiv:2501.08555. 2025b.
Yuxin Pan, Ruohong Liu, Yize Chen, Zhiguang Cao, and Fangzhen Lin. Hierarchical learning-based graph partition for sarge-scale vehicle routing problems. arXiv preprint arXhv:2502.08344 2025.
Ke Li, Fei Liu, Zhenkun Wang, and Qingfu Zhang. Destroy and repair using hyper-graphs for routing. In Proceedings of the AAAI Conference Artificial Intelligence, volume 39, pages 18341-18349, 2025.
Zhang Hua Fu, Sipeng Sun, Jintong Ren, Tianshu Yu, Haoyu Zhang, Yuanyuan Liu, Lingxiao Huang, Xiang Yan, and Pinyan Lu. A hierarchical destroy and repair approach for solving very large-scale travelling salesman problem. arXiv preprint arXiv:2308.044:
2023.
Mouad Morabit, Guy Desaulniers, and Andrea Lodi. Learning to repeatedly solve routing problems. Networks, 83(3)=503-526, 2024.
13

---

Published as a conference paper at ICLR 2026
Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. T2t: From distribution learning in training to gradient search in testing for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023b.
Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao. Yong Li, and Fanzhang Li. Glop: Learning global partition and local construction for solving large-scale routing problems in real-time. In Proceedings of the AAAI Conference on Artificial Intelligence, 2024.
Vaswani. Attention all you need. Advances Neural Information Processing Systems, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:/710. 101.0/00..000,.. 2017.
Birger Funke, Tore Grünert, and Stefan Imnich. Local search for vehicle routing and scheduling problems: Review and conceptual integration. Journal of heuristics, 11:267-306, 2005.
Junyoung Chung. Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv preprint arXiv: 141.3554 2014.
Changliang Zhou, Xi Lin, Zhenkun Wang, Xialiang Tong, Mingxuan Yuan, and Qingfu Zhang Instance-conditions adaptation for large-scale generalization of neural combinatorial optimization. arXiv preprint 1XXi::4405009900 2024.
Fu Luo, Xi Lin, Zhenkun Wang, Xialiang Tong, Mingxuan Yuan, and Qingfu Zhang. Self-improved learning for scalable neural combinatorial optimization. arXiv preprint arXiv:2403. 19561,, 2024.
Marius M Solomon. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2):254 265, 1987.
Mare Goetschalckx and Charlotte Jacobs-Blecha, The vehicle routing problem with backhauls. European Journal of Operational Research, 32(1))39-51, 1989.
Goran Martinovic, Ivan Aleksi, and Alfonzo Baumgartner. Single-commodity vehicle routing problem with pickup and delivery service. Mathematical Problems in Engineering, 2008(1):697983 2008
Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, Thibaut Vidal, and Anand Subramanian. New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3):845-856 2017.
Florian Amoll, Michel Gendreau, and Kenneth Sörensen. Efficiently solving very large-scale routing problems. Computers & operations research, 107:32 42, 2019.
14

---

Published as a conference paper at ICLR 2026
APPENDICES
CONTENTS
Supplementary Definitions
16
A.1
Unstable Edges and Stable Edges
16
A.2
Capacitated Vehicle Routing Problem
16
A.3 Vehicle Routing Problem with Time Windows
16
Details of First-Segment--hen--ee Then-Aggrenateee (FSTA)
16
More discussions ESTA
16
B.2 Proof of ESTA
21
C
1.2Seg Details
26
C.1
Comparative Analysis of L2Seg Against Existing MethodS
26
Input Feature Design Details
27
Masking Details
27
C.4
Training Data Collection Details
28
Inference Details
28
Experimental and Implementation Details
28
D. Backbone solvers
28
D.2 Baselines
31
D.3 Parameters and Training Hyperparameters
31
D.4
Instance Generation
32
Additional Experiments and Analysis
33
E,1
Hyperparameter Study
33
E.2 Results on Realistic Routing Datasets
34
Results on Clustered CVRP and Heterogcneous--deneee CVRP
................................
Standard Deviation Comparison
35
E.5
Case Study: Comparison of Predictions of Three L2Seg Approaches
35
E.6
Unstable and Stable Edges Convergence
36
The Neural Network Overheads of L2Seg
36
E.8
Time of Training 1.2Seg
36
Broader Impacts
36
Large Language Models Usage
37
15

---

Published as a conference paper at ICLR 2026
A SUPPLEMENTARY DEFINITIONS
A. UNSTABLE EDGES AND STABLE EDGES
We define an iterative step as the t-th invocation of the backbone solver. Within each invocation, the solver performs a full round of optimization (involving multiple local search operations) subject to fixed budget (e.g., time limit or number of steps) to return locally optimal solution. Unstable edges refer to edges that need to be re-optimized during the iterative re-optimization procedure. We supplement the formal definitions as follows: given a solution R, at iterative step t, an edge e E R is unstable if & R2+1- When we generate the labels for training, we use lookahead backbone solver for detecting unstable edges. An edge is stable edge if it's not an unstable edge.
A.2 CAPACITATED VEHICLE ROUTING PROBLEM
Given complete graph G (V, E) where V { {Io, ......, Zn is the set of nodes with node zo representing the depot and nodes æι to Zu representing customers. Each customer has demand d, > 0, and each edge ei,j E E has an associated cost representing the travel distance travel time between nodes and rj. A fleet of homogeneous vehicles, each with capacity C, is available at the depot. The objective is to find set of routes that minimizes the total travel cost, subject to: (i) each route starts and ends at the depot, (ii) each customer is visited exactly once, (iii) the total demand of customers on each route does not exceed vehicle capacity C.
A.3 VEHICLE ROUTING PROBLEM WITH TIME WINDOWS
Given complete graph G (V, E)) where V { T1.... Zn, is the set of nodes with node zo representing the depot and nodes ø1 to on representing customers. Each customer has demand d, > 0, and each edge 6r,j E has associated cost representing the travel distance travel time between nodes z; and zy. Each customer has time window [t tj] where tद is the earliest arrival time and f. is the latest arrival time, and requires a service time s,. fleet of homogeneous vehicles, each with capacity C, is available the depot. The objective is to find set of routes that minimizes the total travel cost, subject to: (i) each route starts and ends at the depot, (ii) each customer is visited exactly once, (iii) the total demand of customers on each route does not exceed vehicle capacity C, (iv) service at each customer begins within their time window [t] f/].
B DETAILS OF FIRST-SEGMENNTTTEENAGGGGE
(FSTA)
B.1 MORE DISCUSSIONS ON ESTA
B. VISUALIZATION OF UNSTABLE EDGE PATTERNS
In this section, we provide visualization and analysis of unstable edge distribution patterns, which serve foundational motivation for our L2Seg approach. We examine unstable edges on three randomly selected CVRPIK instances solved iteratively using LKH-3. In these visualizations, red dashed lines represent unstable edges, and yellow stars indicate depot locations.
Our visualization reveals two key observations: (1) The number of unstable edges generally decreases optimization progresses, with more and more edges remaining unchanged between iterations; (2) Edges at route boundaries exhibit higher stability, while unstable edges predominantly concentrate within route interiors. Despite these discernible spatial patterns, simple heuristic rule appears sufficient to reliably predict unstable edges, as they can be distributed across the start, middle, and end segments of each tour. This complexity motivates our development of L2Seg, learning- bbasd method designed to capture these intricate patterns more effectively.
B.2 VISUALIZATION OF APPLYING FSTA ON ONE CVRP INSTANCE
To provide a concrete illustration of our FSTA methodology, we present an example its application to CVRP in Figure 99. which demonstrates the complete FSTA decomposition pipeline (detailed algorithmic specifications are provided in Appendix B.1.4.. This example utilizes the lookahead oracle model for unstable edge identification (defined in Appendix B.I.T). employs LKH-3 as the
16

---

Published as a conference paper at ICLR 2026
backbone optimization solver, and operates representative small-capacity CVRPIk instance to showcase the framework's 's efficacy. Red dashed lines indicate detected unstable edges, while blue dashed lines represent re-optimized edges. Note that dual hypernode aggregation substantially reduces the problem size compared to the original instance.
B.1.3 ASSUMPTION VERIFICATION
Table 6: Oracle Performance on CVRP2k: Time to Reach L2Seg- Solution Quality
Oracle (LNS) perfect recall & TNR
Oracle (LNS)
Oracle (LNS)
Oracle
Ref (L22Se-SYN-LLNS)
95% recall
90% recall & 90% TNR
70% recall & 70% TNR
& 95% TNR
Obj. Time
56.02
56.01
56.02 119s
56,04
56,08
39s
62s
324s
241s
In Section 3 hypothesized that effective problem reduction substantially accelerate re- optimization. We empirically validate this by implementing a look-ahead oracle for unstable edge detection. The oracle performs 1-step re-optimization using LKH-3 and identifies unstable edges Eunstable as those differing between the original and re-optimized solutions. FSTA then constructs a reduced problem instance based these oracle-identified edges, which is subsequently re-optimized using the LKH-3 backbone solver. As this is an oracle-based evaluation, the time required for look-ahead computation excluded from performance measurements.
reports the time required to achieve performance equivalent to our learned model on small- capacity CVRP2K instances. Beyond the perfect oracle scenario, evaluate imperfect oracle
(a) Random instance 1 step
(b) Random instance 2 at step 1
(c) Random instance 3 step
(d) Random instance step (e) Random instance at step
(I) Random instance step
Figure 8: Spatial distribution of unstable edges (dashed red lines) across optimization iterations using I.KH3 solver. Results are presented for three randomly selected CVRPIk instances at iteatvie search steps and 5. While many edges remain unchanged across iterations, unstable edges predominantly emerge within the interiors of routes. contrast, edges located at route boundaries exhibit higher stability throughout the iterative optimization process.
17

---

Published as a conference paper at ICLR 2026
(a) The original CVRPIK instance
(b) Unstable edges detection
(c) Segment partitioning
(d) Hypernode aggregation
(e) Re-opt. w/ backbone solvers
(l) Solution recovery
Figure 9: Illustration of FSTA applied one CVRP instance. Each FSTA step corresponds the descriptions in Appendix B.1.4] Red dashed lines: unstable edges; blue dashed lines: re-optimized edges. Note that the subproblem (d) contains substantially fewer nodes than the original instance (a).
configurations where recall and true negative rates fall below 100%. The perfect oracle demonstrates substantially superior efficiency. Performance remains competitive under moderate imperfection levels; however, achieving recall and TNR as high as 90% without oracle access highly non- trivial. In more practical scenarios, where recall and TNR drop to 70%, the oracle-based approach is outperformed by our
highlighting the effectiveness our learned model.
These results provide evidence that accurate identification of unstable edges, coupled with appropriate FSTA-based problem reduction, enables significantly more efficient re-optimization.
B.1.4 DETAILS OF FSTA DECOMPOSITION FRAMEWORK
In this section, we present the details of the FSTA decomposition framework. Given routing problem P and an initial solution R, one itcrative step of FSTA yields a potentially improved solution R.. The framework comprises five sequential steps (also illustrated in Algorithm [ and Figure 2
Unstable Edges Detection: We implement effective methods (e.g., our learning- based model L2Seg random heuristics detailed in Section (.4) to identify unstable edges Eunstable and obtain the stable edge set Estable = \ Eunstable- This identification challenge is addressed by L2Seg model, with full details provided in Section 4 and Appendix
2. Segment Partitioning: After removing unstable edges Faustables each route decomposes into multiple disjoint segments consisting of consecutive nodes connected by stable edges. Formally, we segment each route into (Io, Si,j, S 2o) (Io, S/1) ((2) 20)
R', where zo is depot and we simplify the notation by using a single index for segments (note that segment can consist only one single node).
3. Hypernode Aggregation: We aggregate each segment S),,A and represent with either one hypernode (8), ( ) two hypernodes (Š) { .f,)) with aggregated attributes.
18

---

Published as a conference paper at ICLR 2026
This transformation requires that (our feasibility theorem): (a) the reduced problem remains feasible, and (b) a solution in the aggregated problem can be mapped back to feasible solution in the original problem. These transformations produce reduced problem P with corresponding solution R.
4. Re-optimization with Backbone Solvers: We invoke backbone solver to improve solution R. yielding an enhanced solution R.,. While theoretically any solver could serve as the backbone solver, practical acceleration requires solvers capable of effectively leveraging existing solutions (e.g.. LKH-3 (Helsgaun) 2017)).
5. Solution Recovery:
With the improved solution R.+ for the reduced problem P, recover a corresponding solution R.. for the original problem P by expanding each hypernode back into its original segment of nodes. This step relies guarantees that improved solution in P maps to improved solution in P.
monotonicity theorem, which
Selection of Hypernode Aggregation Strategies. We analyze the trade-offs between single and dual hypernode aggregation strategies: (1) Dual hypernode aggregation enables bidirectional segment traversal, potentially improving re-optimization efficiency by expanding the solution search space. However, this approach requires enforcing inclusion of the connecting edge between hypernodes, adding algorithmic complexity. (2) Single hypernode aggregation achieves superior problem size reduction but constrains segment traversal to fixed direction, thereby restricting the re-optimization search space and potentially limiting performance improvements. Additionally, single hypernode aggregation transforms symmetric routing problems into asymmetric variants, which may compromise the efficiency of existing backbone solvers that are typically optimized for symmetric instances.
Selection of Backbone Solvers. Our framework is generic to be applied to most existing VRP heuristics by design. In practice, acceleration within our framework requires solvers that can effectively utilize initial solutions warm starts. Furthermore, if the dual hypernode aggregation used, the backbone solver needs to fix certain edges during local search. Our framework is readily compatible with variety of solvers without modifying their source codes, including LKH-3 solvers like LNS (Shaw) 1998). and learning- methods such 1.2D (Li et al., (02T). Incorporating additional solvers such HGS (Vidal 2022), would involve extending its current code to accept initial solutions as input, which we leave as future work. Notably, demonstrated in Section 5 our L2Seg-augmented approach with relatively weaker backbone solvers outperforms HGS in multplle CVRP and VRPTW benchmark scenarios.
(Helsgaun) 2017). decomposition-
Applicability to Routing Variants. FSTA is broadly applicable to routing problem variants that support feasible hypernode aggregation and solution recovery, as ensured by the feasibility and mono- tonicity conditions established in Section 3 In Appendix B.2] we formally prove that many routing variants meet these conditions, demonstrating the versatility of our I.2Seg framework. Detailed implementation guidelines for applying hypernode aggregation across different routing variants are provided in Appendix B.1.5
Algorithm 1: Iteratively Re-optimize Routing Problems with FSTA
Input: Routing problem P, initial solution R, time limit Trz, backbone solver BS, model M identify unstable edges
Output: Improved solution R
while time limit T is not reached do
Emsstable +- M(P. R):
// Unstable Edges Detection
{ < GetSegments PP R, Eunstable)
// Segment Partitioning
Obtain ( and reduced problem P with solution R: Hypernode Aggregation // Re de-opptimization with Backbone Solver R4 RecoverSolution(? P,
R4 + BS(P,R)
// Solution Recovery // Update current solution
R + R+;
end while
return R
19

---

Published as a conference paper at ICLR 2026
B.1.5 APPLYING ESTA ON VARIOUS VRPs
In this section, we present the implementation details of FSTA across diverse routing variants, including the Capacitated Vehicle Routing Problem (CVRP), Vehicle Routing Problem with Time Windows (VRPTW), Vehicle Routing Problem with Backhauls (VRPB), and Linle-Commmddng Vehicle Routing Problem with Pickup and Delivery (I-VRPPD). Without loss of generality, we denote a segment to be aggregated as Sj.k = (xr + + Tz). and corresponding hypernode representation as either S,,6 = { (single hypernode) or SJ,A = {āz, } (dual hypernodes). The implementation specifications are summarized in Table
CVRP. We provide the formal definition of CVRP in Section 3 Each node in CVRP is characterized by location and demand attributes. For CVRP, we employ dual hypermode aggregation where location attributes are preserved as 3 = T.j and 3% = Tk. while demand is equally distributed between hypernodes dj d2 2 (dj + ... + dx). We force the solver to include the edge connecting ū and Tg in the solution.
VRPTW. We provide the formal definition of VRPTW in Section 3 In addition to location and demand attributes, VRPTW instances are characterized by time windows [t', .t]] and service time for each node. For VRPTW, we employ adaptive strategies for hypernode aggregation based on temporal feasibility. We first compute the aggregated time windows fyy, tj and aggregated service time 83 using the following recursive formulation:
t/2 max t
m = k if S m S k
Et
zl mm+1 (sm + dist(Em Im+1))}
t min (tin: Em+1 - (sm + dist(Em;
if k
(3)
if S m k
8k
if m k j S m S 1,
pm
5m41 + Sm + dist(Im, Fm+1)
where [t'm fml denotes the time window for node Em. 8m represents the service time at node Imm and (is 1) is the travel time from node I' to node Tm+11
If i2 S 12 (feasible time window), we employ single hypernode aggregation with: dist(z;;, = dist(2,,,,), dist(E, x;) = dist(rx. zx), d = dj + + dx. F¹ = Fj, i" = fj, and ă = =
If f > P (temporal infeasible time window), we employ dual hypernode aggregation with: ã, = Tj. it Fg. d, = d. } (d, + ..... + de), time windows 72 0, i3 Fj. i = 2 2 oc, and service times 3, = 0, & = 53. We additionally set dist(E,, 2x) and enforce inclusion of the edge connecting J and Fr in the solution.
VRPB. Compared to the CVRP, the VRPB (Goetschalckx and Racobs-Blechn 1989) involves serving two types of customers: linehaul customers requiring deliveries from the depot and backhaul cus- tomers providing goods to be collected and returned to the depot. The primary constraint is that all linehaul customers must be visited before any backhaul customers on the same route, while ensuring vehicle capacity is never exceeded during either the delivery or pickup phases. We use by E {0, 1 to indicate whether node / is a backhaul customer. For VRPB, we require the edge connecting to linehaul customer and a backhaul customer included in the Eunstable- We employ single hypernode
aggregation that dist(z;; F) = dist (2t, .r dist(E, 2x)) = dist(rx; T.), d d + ..... + dg. and = by (we require customer being the same type within each segment that by ... bb).
1-VRPPD. Compared to the CVRP, the I-VRPPD MMartinovic et al. 2008) deals with customers labeled as either cargo sink (d: < 0) or cargo source (d; > 0), depending on their pickup or delivery demand. Along the route of each vehicle, the vehicle could not load negative cargo or cargo exceeding
the capacity of the vehicle C. For any segment Sy.k, we define D dj. D = d, + dj+1- and D d, + dj+1 + ... dg. We further define mmin min D, D.. and D max (0. Dj. -..). For I-VRPPD, we require three hypernodes म, = I,, &mid. and ã Tk. where the distances from Zamd to ă, or itz are O, and infinity for the other hypernodes. For the aggregated demands, d, = Dmin dmid = max minn and de = D* D - Dmnn Additional constraints are added to ensure the directed edges ū. + Fmiid - Ft are included in the solutions.
20

---

Published as a conference paper at ICLR 2026
Table Implementation specifications FSTA hypernode aggregation for CVRP, VRPTW, VRPB variants. Refer to Equation 3 for the definitions of 8,, it and Pj.
Type
Condition
Attribunte
Aguregation
Additional Constraints Settings
Location/Disaace
2, 2)
Two Hypernodes
Always
2. Zb d = 2(0, + de)
Include edge 2 + 3% in the solution
Demand
VRPTW
Type
Condition
Attribute
Aggregation
Additional Constraints / Settings
Location/Distance
dist(a,, dis)(2;,
dist( n,) dist(
One Hypernode
f 1
Demand
d = dg +...- de
Nome
Service Time
8
Time Windows
7 1y.
=1,
Location/Distance
8, 23.
Two Hypernodes
Demand
{(dy
Include edge 2, - 2x in solu- di.
Service Time
01 82
Time Windows
0,
VRPB
Type
Condition
Attribute
Aggregation
Additional Constraints / Settings
Location/Distance
dist(an; 2) dist(2;; d dist(F, m;) dist(za. d b= by
Require ... by (same customer type) during Unstable Edges Detection Stage
Hypernode
Always
Demand
Is backhaul
1-VRPPD
Type
Condition
Attribute
Aggregation
Additional Constraints / Scttings
Location/Distanee
4, 2y.
dist Fmadl dist( .t.)
Three Hypernodes
Always
aail only connects J. and 5g.
Include edges F; Fnd in the solution
Demand
d, Dain dast Dui Duis
d. D D Dumn
B.2 PROOF OF FSTA
Theorem. (Feasibility) the aggregated solution R4 is a feasible solution to the aggregated problem, then R., a feasible solution to the original, non-aggregated problem. (Monotonicity) Let R. and R2 be two feasible solutions to the aggregated problem, with S(R1) < {(R²), ). where s()) denotes the objective function (total travel cost). Then, for the associated solution in the original space, we also have f(R2) S. f(R3).
Proof Structure and Notation. Without loss of generality, we consider a single-route solution xR) with more than one node, i.e., the solution R contains route = (Zo + I1 7 ... SSN - IK-1 + ... > zn). We define the aggregated problem with node set V = { U (xplo<s 1 where nodes outside the segment retain
containing one segment Sj,x (xj
p>*k
their original representation, ensuring their feasibility by construction. Since we enforce the inclusion of the edge connecting ă and äe in dual hypermode aggregation within solution R4,, the segment SJ.k must be incorporated into some route R E R4 for both hypernode aggregation strategies. We denote the improved route containing this segment after mapping back the original problem R
We present the segment aggregation strategies for different routing variants below, followed by proofs of feasibility and monotonicity for the aggregation scheme. Note that the following analysis naturally extends to multi-route solutions with multiple segments per route.
B.2.1 CVRP
Aggregation Strategy (Two Hypernodes). The detailed implementation of FSTA on CVRP can be found in Appendix BB..5] and Table 7 Notice that one single hypernode aggregation is also applicatable for CVRP, and dg could take other values as long as d; dg dj ... dr.
21

---

Published as a conference paper at ICLR 2026
Feasibility Proof [Capacity Constraint). Notice that since d, + dx d, ... + dg, have:
Σ d
Σ
di +
d, + dr
2, EE
2.ER
(4)
Σ
di + d, +
d₁ Σ d:
2,ER 1Sy.
J,ER
Thus, we have:
Σ dsc= Σ DsC
(5)
FEE
BIER
Then, have feasible R4 feasible R...
Monotonicity Proof. Notice that
f(R+)= = f(R+ (R4)) + f((R)) f(R (14H) f((R7))
- - \ ( (((E)))) E dist(xn, Tq+1) + dist(āz,
(6)
SSack
=f(R+) Const|s
where Const| Sy. is constant once the segment Sn,x is decided. Therefore, we have:
f(R), S f(R²) f(R)) + Const 85,4 f(R²) + Const S, + f(R?)
(7)
We note that the feasibility proof for capacity constraint and the monotonicity proof could easily extended to the single hypernodes aggregation.
B.2.2 VRPTW
Aggregation Strategy (Mixed Strategies). The detailed implementation of FSTA on VRPTW can be found in Appendix 1.5. and Table 7 We denote s 8m + dist(Tm, #m++1 for j S < and &
We further set the service time by 8m Σ sy. and we repeat the temporal time
mS45k
window 17 Fy] (which could be infeasible) defined by the following recursive relationship:
t/e max
k m S (1 1m+1 - 8
(8)
5%
k (min 1m smn j < < k 1,
where [th, (T) is the time window for a node Ims 8m is the service time at node Em and dist(2m, 1m++1 is the time to travel from node E. node rm+1-
Feasibility Proof [Time Window Constraint). We first prove for the condition that the temporal time window E. Ej] is feasible ( +,) and single hypernode aggregation is applied. Then, we extend to the infeasible temporal time window condition where dual hypermode aggregation is applied.
Condition of Feasible Temporal Time Windows (One Hypernode). We present inductive proof based the segment length. Given feasible solution R_, for the aggregated problem, show the following two conditions of the corresponding non-aggregated solution R4 to satisfy the time window constraint:
Condition (1): We visit each node 2m before the end of its time window th.
Condition (2): The total time we spent visiting the entire segment the same in both aggregated and non-aggregated representations.
22

---

Published as a conference paper at ICLR 2026
Total Time Spend on Segment Sm,k
Bm (1)
Case
Case 2
t 2 Gm
8m,
Fm
Sym
km
6m
6m
Arrival Time Node Xm
P
Figure 10: This illustration demonstrates the temporal dynamics of the aggregated segment. The left panel shows the time function characterized by a piecewise linear structure: initially decreasing with slope -1, then transitioning boundary. The right panel presents two distinct scenarios that characterize the relationship between the aggregated left time window (C,) and the individual non-aggregated left time windows (fm)
constant value corresponding the aggregated left time window
Proof of Condition (1):
Base case (segment length = 1). Suppose the segment Sk.k = (æx) contains a single node Ty. Then the aggregated problem is identical the non-aggregated problem by construction, condition (1) is trivially satisfied.
Inductive Step (segment length = (k - m) + +1> 1). textit the aggregation of the segment Sm-1, = (Im+1 - - 2²)) into Sm+1k = {#m+1,) satisfies condition (1). We want to show that the aggregation of the segment S = (Im + + I&) into Sm, = (
also satisfies condition (I).
Since R4 is a feasible solution for the aggregated problem, we will visit the hypernode Tm. before the end of its time window Ir = min [=+1 sm ). Corresponding, in the associated non-aggregated solution, we visit the node Tm before its time limit i hence satisfying condition (I) for the node Im. Furthermore, in the associated non-aggregated solution, we visit the next node Tm+1 before time e,, + S S f Based on the inductive hypothesis, condition (1) holds for the rest of the segment (Em+1 - ... r%k if we arrive at node Tm+1 before its end time. Hence, condition (1) holds for the whole segment xx).
Sm,k- (Im Im+1
Proof of Condition (2): For all m, suppose we arrive at the hypernode Tm, at time < & in the aggregated solution. By definition, the total time spent on the aggregated segment (sum of the waiting time, service time, and the travel time) can be written as the following linear function with -1 slope as shown in the first figure in Figure
pm 2
t t2
Im (t) =
(9)
-
5m
t<
Note: the first condition t Em means do not need to wait at any node in the segment Sm,ks and the second condition means we need wail at some node in the segment Sm,k-
It suffices to show that the total time spent on the non-aggregated segment also follows the same function. Again, we prove this by induction.
Base case (segment length 1). Suppose the segment Sk (æx) contains single node Fy. Then the aggregated problem is identical to the non-aggregated problem by construction, the total time spent the non-agggregated segment is exactly Eq. with = k.
Inductive Step (segment length (I: m) + > 1). Again, suppose the total time spent on the segment Sm+1, = (Im+1 + - xx) into Sm+1, {#m+1, satisfies the function
8m+1
1 7 1
9m+1(t) (m)+
(10)
z Em - 3m+1
t t< F
m+1
23

---

Published as a conference paper at ICLR 2026
We now show the total time function (t) for the segment Sm,k (xm + - Ikk also equals (t).
By definition of the non-aggregated segment, depending on whether we need to wait at the first node Ima, we have:
Im (t) { sm + Im+ill + sm) tym -t sm 9m+1 (t' + stn) t << tm
12 U
(11)
Note: the first condition t 2 i'm means we do not need to wait at the first node Jmm and the second condition < i' means need to wail at the first node Tmm-
We split the discussion into the following two cases, based on whether we need wait at any node along the segment Sm+1,k, if we leave node 2m at t.m
1. t + sm 2 +1 In this case, t 2 P m1 S and hence E. max(ty, (y by m
s }) t'm as shown in case 1 of Figure 10 Hence, we have
Im (t) = { 8m + 9m+1 (1 + stre)
12 7
m
(12)
( + sm + Im+1 (Ihm + smm
< R
By inductive hypothesis, we have
9m+1(t + sm)) = 8mtli
12 t = Zm
in this / + sm 2 1/ + sm 2 T I Hence, we have
bmm + 8m++1
1 12 7
9m (t)
6t + 8m+1
t < 8
(13)
88m
12 7
5m (t).
1 1 + 8m 1 1< Py
where we apply the definition of 8. = sn + 8mt1.
2. t + sm < En+1. In this case, fm+1 St t and hence Hy max(th &
st = f mm st, shown in case 2 of Figure 10
By inductive hypothesis, we have
Jm (t'm + 8tm) = (ntt1 (t'r + sm)) + 3m+1
(14)
R ly 8m41
We also have, for all t 2 e'm
gm+1 (t + ((m)
8mt11
t 8 Z m+1
El Emt1 (t + smm + 3m41,
t sm m+1
(15)
8mt1
12 m
+ 8m+1i
$ t < ft
As result, we have
+ 8m++
1 7 z S F.
9m (t)
5
+ Fm
+ sm+1
"
+ sx + 7 1 + 8m+1
1 < 1/
m
Sm
> 11
(16)
Im
+ 8m
| < < The
z - + 5m
< thm
3m
1> i
(m)(t).
t + 8m
t < fl
m
24

---

Published as a conference paper at ICLR 2026
Condition of Infeasible Temporal Time Windows (Two Hypernodes). In time window aggregation, Fj is responsible for the time expenditure and Fj is responsible for feasibility. In this case, we have f2 > Pj. which indicates that to maintain feasibility along the segment, one must arrive the segment before the aggregated start time 7. and since arrives earlier, one must wait some node within the segment. Since Fj > F is not permitted according to the definition of VRPTW, then utilize additional hypernode to increase the representational capacity such that the first hypernode handles the feasibility component (1j), and the second hypernode handles the travel time
component (t)), Specifically, ? 0, F y. C f). Eh additional constraint that dist(Ty. xx)) 0.
and 3j 0. Sk 8j with the
For time window feasibility (Condition (1)), since f2 = Pj. the vehicle must serve the segment before 17, ensuring the feasibility of serving each customer in the non-aggregated problem. For travel time equivalence (Condition (2)), the time expended before reaching the second node 8y + dist(āz, entirely determined by E E and & 5j. whereby in the feasible temporal time window situation, the travel time equivalence is demonstrated.
O. Namely, after the vehicle arrives at the segment at time the travel time is
We complete the time window constraint feasibility proof for VRPTW for both aggregation strategies across all conditions.
C
Monotonicity Proof. For the dual hypernode aggregation, please refer to the Monotonicity Proof in B.2.1 For the single hypernode aggregation, notice that
f(R+) f(R+ + f(R+ +
-[(R+ (R4)) - Σ dist(rng: Rq+1)
(17)
35ack
f((+) + Const|s,,.
where Const|s,, is constant once the segment Sy,k is decided. Therefore, we have: f(R2) s f(R2,) = f(R)) + Const S f(2,) + Const] = f(R)) S f(R2,
(18)
B.2.3 VRPB
Aggregation Strategy (One Hypernode). The detailed implementation of FSTA on VRPB can be found in Appendix B.1.5 and Table
Feasibility Proof [Backhaul Constraint]. Without loss of generality, assume all nodes within the
segment Sj.k backhaul customers (by by 1). Notice that since d = dy + de, for the backhaul stage, we have:
Σ
de
Σ
di + d
a. R, and b,=1
a fig S8ya and b,=1
(19)
Σ
de +
dg +... +..+oo db
Σ
a R2 (yya and =,=1
z.ER R and 1
For the linchaul stage, we have:
Σ
d,
Σ d
(20)
R and 6==0
m.E and d
Thus, we have:
Σ
CSC
Σ
S
E b,=0
ER and b,=0
(21)
Σ
C
Σ
d
x e and 6==1
E R and b
25

---

Published as a conference paper at ICLR 2026
Then, have feasible R++ feasible R...
Monotonicity Proof. Please refer to the monotonicity proof of VRPTW in Appendix B.2.2
B.2.4 1-VRPPD.
Aggregation Strategy (Three Hypernodes). The detailed implementation of FSTA on 1-VRPPD can be found in Appendix B.1.5 and Table 7
Feasibility Proof [I-Commodity Pickup and Delivery Constraint). A feasible R, indicates that whenever the vehicle is traveling aggregated segment Sj,k. denoted the starting load of the vehicle to be da and ending load the vehicle to be dea, we have:
0 du + Dmin 0
(22)
dst + Dmin D Dmmn C
which requires - Dimin S du SC ma and dea da + D*
On the other hand, a feasible solution R4 indicates that whenever the vehicle traveling a segment Sj.k, denoted the starting load of the vehiele to be du and ending load of the vehicle to be ded, have:
0 S du + D' S C, Vi
(23)
which also requires - -Dmin < da < C - Dmax and ded = da + D* Then, we have a feasible R, + a feasible R+.
C
Monotonicity Proof. As dist(Ej, Fmia) dist(Tmid- Jx) can eliminate the middle hypernode and use two-hypernode representation when calculating the routing objective. Please refer to the monotonicity proof of CVRP Appendix B.2.1 for the monotonicity proof of wwo-hyperoode representation.
C L2SEG DETAILS
C.I COMPARATIVE ANALYSIS OF L2SEG AGAINST EXISTING METHODS
Comparisons with Large Neighborhood Search (LNSS. (1) LNS (Large Neighborhood Search) operates within bounded local neighborhood. The algorithm selects specific region, destroys elements within that boundary, and rebuilds only that portion while keeping the rest of the solution intact. For instance, in Li et al. (2021). LNS selects 3-5 subroutes its neighborhood, modifying only these routes while leaving all others completely unchanged. There is a clear demarcation between the modified neighborhood and the preserved structure. (2) FSTA (our method), in contrast, operates more globally across the entire solution. It can break existing edges and aggregate segments throughout all subroutes simultancously, without any predefined neighborhood boundaries. The modifications are distributed across the entire solution rather than confined to a local region, which represents a fundamental departure from existing LNS more efficiently guide the search. We note that such flexible framework would not be possible without the proposed ML component, which also constitutes the core novelty and contribution of our work the field. (3) Moreover, FSTA and LNS are complementary: FSTA can be applied on top of LNS, where LNS first selects large neighborhood, then FSTA fixes stable edges globally within that selected region.
Comparisons with Evolutionary Algorithms. 1.2Seg framework and evolutionary algorithms (Vidal 2022)) approach the preservation of solution components from different angles and with distinct goals, and are not interchangeable in use. Evolutionary algorithms (Vidal 2022 rely crossover to merge relatively "good" components from different parents, aiming to promote diversity and generate promising offspring, while our L2Seg framework introduces a learning guided mechanism to detect unstable edges and aggregates stable edge sequences into hypernodes, enabling a new form of segment-basee decomposition that improves scalability and efficiency.
saaminggguidedd
26

---

Published as a conference paper at ICLR 2026
Comparisons with Path Decomposition Method. (1) Firstly, path decomposition relies geometric heuristics (e.g., clustering routes by barycenter distances) to identify decomposition boundaries. In contrast, L2Seg employs deep learning models (synergistic NAR-AR architecture) intelligently predict which segments should be aggregated, capturing complex patterns that simple heuristics cannot identify. We also propose novel learning-guided framework with bespoke training and inference processes that are unique to the machine learning method. (2) Secondly, while some prior work explores similar decomposition ideas (c.g.. on CVRP only). we are the first study FSTA decomposition theoretically, providing formal definitions, feasibility theorems, and monotonicity guarantees for various VRPs. (3) Lastly, we empirically demonstrate that by leveraging deep learning in our 1.2Seg framework, our method consistently achieves significant speedups on sate-of-the-ar backbones. This provides new insights for the community, highlighting the power of learning-gund guided optimization in accelerating combinatorial solvers.
Comparisons with Previous Learning-based Framework L.2D (Li et al. 202T). (1) Different from the sub-route level, our method detects unstable edges both within and across sub-routes, enabling more global and flexible decomposition. (2) It optimizes beyond localized neighborhoods by identifying improvements that span multiple distant regions simultaneously. (3) It reduces the size of sub-routes by aggregating stable segments into hypernodes, whereas L2D reduces only the number of sub-routes per iteration. This segment-level aggregation allows more adaptive and coarse-grained reduction, offering higher efficiency and solution quality, while remaining complementary to L.2D.
Comparisons with hypergraph decomposition methods Fu et al. (2023) and Li et al. (2025) Fu
iet al. (2023) introduce HDR, a hierarchical destroy-and-repan algorithm that recursively compresses TSP instances to handle problems with millions of cities. While HDR achieves remarkable scalability on very large TSP instances using non-learning heuristics, our approach differs by employing learned policies to identify unstable edges and extending beyond TSP handle CVRP, VRPTW, and other variants. HDR uses straightforwart destruction patterns from the lookahead heuristics. [i et al. (025) propose DRHG, which uses hyper-graphs to reduce consecutive edges and supervised learning for reconstruction. Their approach applics heuristic clustering for destruction followed by ML-based repair of the destroyed segments. Our method takes the opposite approach: should be destroyed, then employ efficient subsolvers for reconstruction. This reversed strategy allows us leverage learned patterns for the critical decision of what to destroy while using proven optimization techniques for repair. While DRHG demonstrates strong results on TSP and CVRP, our experiments extend more constrained variants like VRPTW.
lige-fixing based on historical local optima, whereas we learn
use machine learning to identify unstable edges that
C.2 INPUT FEATURE DESIGN DETAILS
Previous works Kool et al. (0118) Li et al. (2021); Kwon et al. (2020) typically utilize only basic input features for routing problems (xy-coordinates and normalized demands for node features, and edge cost for edge features). While neural networks potentially learn complex patterns from these basic features, tailored feature engineering may lead to enhanced model performance. As illustrated in Appendix [. we observe that detecting unstable edges may depend on better capturing local dependencies. We therefore design enhanced node and edge features for our learning task, as shown in Table We also include time windows and service time node features for VRPTWs.
C.3 MASKING DETAILS
In general, any set of unstable edges could lead to feasible FSTA problem reduction. However, employing logic- local search algorithms to select unstable edges can produce more reasonable action space reduction and improved performance. Thus, we design the deletion and insertion stages of L2Seg to emulate a general local search operation.
For the deletion stage, given the current node x, mask nodes that are: (1) not connected to x;; or (2) part of an edge that has already been deleted during the current deletion stage. Note that the model may select the special ending node Zend to terminate the decoding sequence.
For the insertion stage, given the current node x, we mask out nodes that are: (1) already connected to x;; (2) endpoints of two newly inserted edges; or (3) the special ending node Fend-
27

---

Published as a conference paper at ICLR 2026
Table 8: Description of enhanced input features for nodes and edges.
Type
Description
Dimension
The xy coordinates
2
The normalized demand
1
The centroid of the subtour for each node The coordinates of the two nodes connecting each node The travel cost of the two edges connecting to each node The relative xy coordinates The angles w.r.t. the depot
2
4
2
Nodes
2
|
The weighted angles w.r.t. the depot by the distances The distances of the closest neighbor for each node The percentage of the K nearest nodes that within the The percentage of the K% nearest nodes that are within the same subtour. K=5, 15, 40
1
3
3
subtour. K=5, 15, 40
3
The travel cost
Edges
Whether each edge is within the current solution
1
The travel cost rank of each edge w.r.t. the corresponding end points
1
C.4 TRAINING DATA COLLECTION DETAILS
In this section, we present pseudocode that demonstrate the process of generating training labels for both NAR and AR models in Algorithm 2 As a complement to the methodology described in Section 4 derive our training data from Np distinct problem instances and extract labels from the first Tis iterative improvement steps. For the AR labels, which emulate feasible local search operations, each label (representing sequence of nodes) is associated with quantifiable improvement solution quality. We retain only those labels that yield improvements exceeding the threshold /improv; and employ stochastic sampling by accepting labels with probability aac- This selective approach ensures both high-quality training signals and sufficient diversity across problem instances and optimization trajectories within the same training budget.
C.5 INFERENCE DETAILS
In this section, we present the pseudocode that delineates the inference processes of L2Seg-SYN (Algorithm 3). L2Seg-NAR (Algorithm -. and L2Seg-AR (Algorithm{3). It is important to note that our implementation leverages batch operations for efficient inference across multiple subproblems simultaneously. The K-means clustering algorithm was strategically selected for initial node identifi- cation due to its parallelization capabilities. By merging graphs from different subproblems into unified structure, we can execute the clustering algorithm once for the entire problem space. This parallel clustering approach through K-means significantly enhances decoding efficiency. Notably, within each iterative step, our design requires only single call of the NAR and AR models, thereby optimizing computational resources.
D EXPERIMENTAL AND IMPLEMENTATION DETAILS
D.1 BACKBONE SOLVERS
LKH-3. The Kan--eenighan--eeeeee algorithm (LKH-33) Helsgaun (017) represents a strong classical heuristic solver for routing problems, which is widely used in NCO for benchmark. It employs sophisticated k-opt moves and effective neighborhood search strategies. For our experiments, we impose time limits rather than local search update limits: 150s and 240s for large-capacity CVRP2k and CVRP5k, respectively, and 2m, 4m, and 10m for VRPTW 1k, VRPTW2k, and VRPTW5K, respectively. For small-capacity CVRPs, adopt the results reported in Zheng et al. 2024
28

---

Published as a conference paper at ICLR 2026
Algorithm 2: Training Data Generation
Input:
Solution distribution P, number of instances Np, backbone solver BS, number of iterative steps Tis, improvement threshold M/ngrov: sample coefficient a,AC
Output: Label sets MARR YAA
NNNA < 0. AARR f- 0 for i <- to Np do
Sample P ~ P and obtain an initial solution R.
for - to Tis do
R+ & ()(,.R)
1/ Apply backbone solver
Fxirr -- (ER \ FR. ).. (ER+ \ ER)
Vunstable VFa
YAR 1sx Vunstable
// NAR model labels
DNNAR - YNAAR U ((P, ((P.YNAR)) NAR)]
ITR < DFS(P, Vunstable; Eas)
// Find sequences
foreach K KTR do Obtain Pk with solution Rg and sequence yx with Improvement Improvemnet 2 Timproy and with probability a then
10
12
VAR VAR U (PR:yK))
// AR model labels
14
end if
// Skip sequences with low improvement by
probability
16
end foreach
R R.
// Update current solution
end for
end for
20 return VAAR VAR
Algorithm 3: 1.2Seg-SYN: Synergized Prediction
Input:
Problem P, current solution R. NAR model, AR model, threshold number of clusters
AKMMAANS
Output: Set of unstable edges Eunstable
PTR <
DecoompoeeinSSSpprobemsssss R)
// Partition into ~ R
subproblems
Eunstable < 9
for each subproblem PIR PIn do
NAR <- NARModel (TR))
11 Get NAR predictions for each node // Identify unstable nodes via threshold
ÚNAR +- {x; NAR > 2n}
Clusters +- KMeans( (KMMEAN)
// Group unstable nodes into
clusters
InitialNodes <- {a | argmar max P NAR , E Clusters)
// Select initial node with highest probability for the AR
model
// Unstable edges for this subproblem for each node Dini E InitialNodes with corresponding PIR do
F.Prx F'ustable +
10
11
EPr
smi ARModel PTR, Pinit)
// Get unstable edges via the
model
PTR E t-
PTR
Pm
12
But
end for 13
14
Emnstable f- Eunstable
sun
// Aggregate unstable edges
15 end for
16 return Eunstable
29

---

Published as a conference paper at ICLR 2026
Algorithm 4: L2Seg-NAN NAR: Not-Autoregressive Prediction
Input: Problem current solution R. NAR model, threshold r
Output: Set of unstable edges Eumstable
PIR Decompoelnouubrroleessss R)
// Partition into ~ R
subproble peprobleme ems
Eunstable <
for each subproblem PIR E PIR do
p pNARR +- NARMMdel(PPrPr
// Get NAR predictions for each node // Identify unstable nodes via threshold Fuustable (1) v2 ÚNAR a E ÚiAR and (z,, Erm) // Mark all edges connected to the unstable nodes as
ÚNAR + { NAR 2n}
unstable
Frunstable &- Fuussable V unstable
PTP
// Aggregate unstable edges
end for
return Exnstable
Algorithm 5: L.2 Autoregressive Prediction
Input: Problem P, current solution R., AR model, number of clusters AKMMEANS
Output: Set of unstable edges Faunstalle
PTR < DecomposeImoSSpproolems//// R)
// Partition into R
subproblems
Eunstable < 9
for each subproblem PIR E PIR do
Clusters KMeans/ AllNodes in PTR. AKMFANS
// Cluster all nodes
Centroids + (t--(Comppnt (ComputeCentroid(c) | c Clusters]
InitialNodes + {a arg minz,ee Distance Distane((x,centroidd,.. E Clusters)
// Select node closest to each cluster centroid for the AR
model
// Unstable edges for this subproblem for each node Vinu E InitialNodes with corresponding PIR do
ExPt
Eusstallc
10
EPTR +- ARModel PIR, Fma)
// Get unstable edges via the
model
11
PIR unstabbl
PIR PtR unstable
U
Pax mank
12
end for
13
Funstable +- Funstable U unstable
// Aggregate unstable edges
14 end for
15 return Exnstable
30

---

Published as a conference paper at ICLR 2026
LNS. Local Neighborhood Search (LNS) Shaw (1998) is powerful decomposition- metaheuris- tic that iteratively improves solutions by destructively and constructively exploring defined search neighborhoods. We implement LNS following the approach in Li et al. (202T). where neighborhoods consisting of three adjacent subrooute are randomly selected for re-optimization. We establish time limits of 150s and 240s for large-capacity CVRP2k and CVRP5K, respectively; 2.5m, 4m, and 5m for small-capacity CVRPIK, CVRP2k, and CVRP5K, respectively; and 2m, 4m, and 10m for VRPTW IK, VRPTW2K, and VRPTW5K, respectively. LKH-3 serves as the backbone solver with a 1,000 per-step local search updates limit.
L2D. Learning to Delegate (L2D) Li al. (2021) is the ofate-oftthe-ar learning- based optimization framework that integrates neural networks with classical optimization solvers to intelligently delegate subproblems to appropriate solvers. The framework employs neural network trained to identify the most promising neighborhoods for improvement. For comparative fairness, we apply identical time limits and backbone solver configurations as used in our LNS implementation. When augmented by L2Seg, training proceeds in two stages: we first train the L2D models following the methodology in Li et al. 202T). then train the L2Seg model using the resulting pre-trained L2D models.
Initial Solution Heuristics. For both training data generation and inference, we employ the initial solution heuristic inspired by (Li et al., 202I). Our method partitions nodes according to their angular coordinates with respect to the depot. We begin by selecting a reference node, marking its angle as 0, and incrementally incorporate additional nodes into the same group until the collective demand approaches the capacity threshold (Ommi Kv Σ d:), where approximately Kveh vehicles would be required to service the group. This process continues sequentially, forming new groups until all customers are assigned. Finally, we apply LKH-3 in parallel to solve each subproblem independently, In our implementation, we set Kee = 6 and Omii 0.95 as the controlling parameters.
D.2 BASELINES
In this section, we provide further clarification regarding the baselines used in our comparative analysis, beyond the backbone solvers. We independently executed LKH-3, LNS, and L.2D using consistent parameters. Results for SIL were sourced from Luo et al. (2024). L2R from Zhou et al. (2025a), and all other baselines from[heng et al.] (2024). When multiple variants of baseline were presented in the original publications, we selected the configuration that achieved the best objective values. Since the original implementations SIL (Luo et al. 2025 (024) and NDS (Hottung et al., 2025) evaluated NVIDIA GeForce RTX 3090 GPU and NVIDIA A.00 GPUs whereas experiments use NVIDIA V100 GPUs, we re-ran them on our hardware for fair comparison. Note that the instance settings used in Table follow Table 2 of SIL in its earlier version (Luo et al., (024). which was removed in the latest version (Luo et al. 2025). We therefore cite both versions when comparing results.
It is important to note that all reported results were evaluated on identical test instances (for CVRPs) or on instances sampled from the same distribution (for VRPTWs), ensuring fair comparison. Moreover, our experiments were conducted on hardware with less powerful GPUs compared to those utilized in Zheng et al. (2024); : Zhou al. (2025a): Luo al. 22224) This hardware discrepancy suggests that the performance advantages demonstrated by our proposed model would likely persist or potentially increase if all methods were evaluated on identical computing infrastructure.
We re- re-implemented the backbone solvers and L2D Li et al. 2021) to ensure a fair and strong comparison. Notably, prior studies (Zheng et al.) 2024; Ye et al. optimized for L.D's full potential. Specifically, they imposed overly conservative limits (e.g., only allowing trail) on LKH-3 local search updates and did not supply current solution information to the LKH-3 solver during the resolution process. This significantly weakened L2D's performance in their benchmarks. In contrast, our comparison reflects L2D's ' best achievable performance.
2024) did not explore configurations
D.3 PARAMETERS AND TRAINING HYPERPARAMETERS
Parameters. Table lists the values of parameters used in training data generation and inference. Training Hyperparameters. For model training, we optimize both NAR and AR architectures using the ADAM optimizer with a consistent batch size of 128 across 200 epochs for all problem variants. The learning rate is calibrated at 10-3 for large-capacity CVRPs and 10-1 for small-capacity CVRPs
31

---

Published as a conference paper at ICLR 2026
Table A list of parameters and their values used in our experiments for training and inference.
Training Data Generation
Parameter
Value
# of instances Np
1000
# of iterative steps Tis Improvement threshold Tinprox
40
Sample coefficient aAAC'
for small capalicy CVRPs and VRPTW'
0.4
for large-capacity CVRPs
Inference
Parameter
Value
Threshold y for NAR model
0.6
# of K-MEANS clusters Timeans
# of LKH-3 local search updates limit
1000
per iterative step
Solve time limits
150s, 240s
for large-capacity CVRP2k, 5k for small-capacity CVRPIK, 2k, 5k for VRPTWIK, 2k, 5k
2.5m, 4m, 5m
2m, 4m, 10m
0.8, and Wdelete = 0.2. All computational experiments are conducted on a single NVIDIA V100 GPU, with training duration ranging from approximately 0.5 to 1.5 days, scaling with problem dimensionality.
and VRPTWs. The loss function employs weighted components with tpos 9, Winsent
Regarding network architecture, our encoder maps node features E TR for standard problems (X E R nx28 for VRPTWs) to node embeddings via himit Concat(h") (MMPP, ..POS) E 2d,, where d, = 128. They then undergo processing through LTFM 2 Transformer layers (Vaswani 2017) with route-specific attention masks, followed by Graph Attention Network to derive the final node embeddings HNN The transformer implementation utilizes 2 attention heads, 0.1 dropout regularization, ReLU activation functions, layer normalization, and feedforward dimensionality of 512. Our GNN employs transformer convolution architecture with 2 layers (LoNN = 2) and single attention head.
Supplementary to the specifications in Section 4 we delineate additional hyperparameters for our decoder modules. The NAR decoder computes p NAR (node instability probabilities) via an MLP with sigmoid activation for final probability distribution. The AR decoder incorporates single-layer Gated Recurrent Units (GRUs), complemented by a hangle--ayrr/sinle-heeaa transformer for the deletion mechanism and four-layer/single-heee transformer for the insertion procedure.
All the training hyperparameters are summarized Table 10
D.4 INSTANCE GENERATION
In general, we generate all training and test instances following established methodologies: Zheng al. (Zheng et al. 2024) for CVRP and Solomon (Solomon 1987) for VRPTW. Specifically, For small-capacity CVRPs, nodes are uniformly distributed within the [0, 1] square, with integer demands ranging from
(inclusive). Vehicle capacities are set C 200, 300, and 300 for problem sizes 1k, 2k, and 5k, respectively. For large-capacity CVRPs, we maintain identical configurations except for increased vehicle capacities of = 500 and 1000 for CVRPIk and CVRP5K, respectively. adopt the same spatial distribution, demand structure, and capacity constraints as
For VRPTWs, the small-capacity CVRPs. Service times are uniformly set to 0.2 time units for each customer and 0 for the depot. Time windows are generated according to the methodology outlined in Solomon (Solomon 1987).
Our experimental framework comprises distinct datasets for training, validation, and testing:
Training: 1,000 instances for each problem type and scale to generate training labels
Validation: 30 instances per problem configuration
32

---

Published as a conference paper at ICLR 2026
Table 10: list of hyperparameters and their values used in our model architecture and training.
Training Configuration
Parameter
Value
Optimizer
ADAM
Batch size
128
# of epochs
200
Learning rates
10 3
large-capacity CVRPs
10
for small-capacity CVRPs and VRPTWs
Weight of unstable nodes Wpos Weight of prediction in insert stage Winser
9
0.8
Weight prediction delete stage Waclets
0.2
Computing Resource
Single NVIDIA V100 GPU
Model Architecture
Parameter
Value
Hidden dimension
Encoder Transformer # layers LTFM # of attention heads
2
Dropout regularization
0.1
Activation function Feedforward dimension Normalization
ReLU
512
Layer normalization
Encoder GNN Architecture # of layers LONN # of attention heads
Transformer Convolution Network
2
1
Decoder Components
NAR decoder activation function
Sigmoid
# of layers in GRUs
R Transformer in Deletion Stage
# of layers I delese
1
# attention heads
AR Transformer in Insertion Stage
layers MHA
# of attention heads
Testing: For smaal-capacity CVRPs, we utilize the 1,000 test instances from Zheng et al. (Zheng et al. (2024); for large-capacity CVRPs and VRPTWs, we evaluate on 100 instances sampled from the same distribution as the training data
E ADDITIONAL EXPERIMENTS AND ANALYSIS
E.1 HYPERPARAMETER STUDY
Figure 11
depicts the effects of rKMmAAS and 77. We
8 46.5
Objective
45.5
45
observe that the best performance when 7KМEANN = and 0.6, suggesting that designating moderate pro- portion edges as unstable represents the most effective strategy.
44.5
84
43.5
43
(a)
(b)
Figure 11: Analysis of key hyperparame- ters: (a) number of clusters rEMAAN, and (b) balancing factor 1).
33

---

Published as a conference paper at ICLR 2026
E.2 RESULTS ON REALISTIC ROUTING DATASETS
We further evaluate 1.2Sgg the CVRPLib realis- tic routing dataset (Uchoa et al., 2017; Arnold et al. 2019). adhering to the settings established in Zheng ct al.) (2024), which incorporates instances from CVRP Set-X [54] and the very large-scale CVRP dataset Set-XXL in the test set. The instances within CVRPLib exhibit more realistic spatial distributions (distinct from simplistic uniform or clustered patterns), greater diversity, and better representation of real-world logistical challenges. For this evaluation, we employ models trained on synthetic small- capacity CVRP2k and CVRP5K datasets and zero-shot transfer them to CVRPLib. Time constraints of 240s and 600s are implemented for L2Seg during testing. Additional methodological details are provided in Appendix D As demonstrated in Table 11 LNS augmented with L2Seg-ST SYN surpasses all other learning--aat based methods in performance. Significantly, the computational time required by (600s) is substantially less than that of the previously best- rest-performing learning- based model, UDC-2250- These results further substantiate 1.2Seg's exceptional generalizability across varied problem distributions.
ANS+I.2Seg-2
Table 11: CVRPL.b results. We present the gap to the best known solutions (%).
Dutaset, N
LEHD
ELG augx8
GLOP-LKH3
TAM(LKH3)
Set-X,(500,1,000
17.4%
7.8%
16.8%
9. 9.9%
Set-XXX,1,,000.100
22.2%
15.2%
19.1%
20.4%
Dataset, N e
UDC-r2
UDC-ar250
LNS+L.2Seg-S (240%)
LNS+L.2Seg-ST SYN (600s)
S5t-X.(500.1.000)
16.5%
7.1%
7.5%
6.9%
Sct.XXL.(1,000111..
31.3%
13.2 %
12.5%
12.0%
E.3
RESULTS ON CLUSTERED CVRP AND HETERROGENEOUS-DEMAADD CVRP
Table 12: Results on clustered CVRP and heterogencous-demand CVRP. We present gains to the backbone solver LNS and the performance of LKH-3 for reference.
Clustered CVRP2k
Clustered CVRP5k
Methods
Obj.4
Gaint
Time
Obj.
Gaint
Timel
LKH-3 (Helsgaun, 2017] (for reference)
42.06
150s
62.33
240s
LNS (Shaw 1998
41.54
0.00%
150s
61.42
0.00%
240s
L.Seg-SSYN-LNG S-N-LNS tzero-sho transfer)
41.03
1.23%
150s
60.87
0.90%
240s
SYN-LLS
40.73
1.95%
150s
60.11
2.13%
240s
Metero-demane CVRP2k
Netero-demant CVRPSK
Methods
Obj-
Gaint
Time!
Obj.l.
Gain
Time.
LKH-3 (Helsgaun, 2017 (for reference)
46.02
150s
65.89
240s
LNS (Shaw 1998
45.77
0.00%
150s
64.81
0.00%
240s
1 12Seg-SYN-LNN (zero-shot transfer)
44.35
3.10%
150s
64.28
0.82%
240s
L2Seg-SYN-LNN
44.15
3.54%
150s
64.15
1.02%
240s
To demonstrate L2Seg's 's robustness across diverse and more realistic scenarios beyond uniform distributions, we provide in-distribution and zero-shot generalization evaluation of our L2Seg on instances with different customer and demand distributions.
Following Li et al. 22021), generate clustered CVRP instances with 7 clusters. For heterogeneous- demand scenarios, we employ a skewed distribution where high and low demands (d E {1, 2, 8, 9}) occur with probability 0.2 each, while others (d (3, 4, 5, 6, 7}) occur with probability 0.04 each. All experiments use LNS as the backbone solver, with LKH-3 included for reference.
Table 12 presents the comprehensive results. L2Seg demonstrates consistent improvements across all settings: zero-shot transfer achieves 1 1.23% to 3. 3.10% gains over LNS, while in-distribution testing reaches 1.02% to 3.54% improvements depending on problem size and variant. These experiments
34

---

Published as a conference paper at ICLR 2026
demonstrate that L2Seg maintains consistent improvements across diverse real-world conditions, from uniform spatial layouts to clustered distributions and heterogeneous demands.
E.4 STANDARD DEVIATION COMPARISON
In this section, we provide standard deviation statistics for L2Seg-SYN across three different backbone solvers on large-capacity CVRPs. We conduct independent trials using different random seeds for each method. All experiments are terminated at the specified time limit, and we report the standard deviations of the objective values for all 6 methods. The results are presented in Table [3] While I.K-3 exhibits the lowest variance among baseline methods, our 1.2Seg approach also demonstrates consistently low variance across different problem types and backhone solvers, confirming both the effectiveness and stability of our method.
Table 13: Performance comparison of backbone solvers with and without L.Seeg-YY SYN on large-scate CVRP instances. Results represent mean objective values + standard deviation across 5 independent trials of testing. L2Seg-SVS SYN demonstrates consistent performance improvements with low variance, indicating both effectiveness and stability of the approach.
CVRP2k
CVRP5k
Methods
Obj-l
Gaint
Time!
Obj-l
Gain
Time!
LKH-3 Helsgaun 2017
45.24 0.17
0.00%
152s
65.34 +: 0.29
0.00%
242s
LKH LZSeg-SYN
43.92 0.20
2.92%
152s
64.12 1 0.34
1.87%
248s
LNS Shaw 19988
44.92
0.00%
154s
64.69 +: 0.37
0.00%
246s
LNS
43.42 0.22
3.34%
152s
63.94 + 0.35
1.16%
241s
L2D Li et al (2221)
43.69 + 0.21
0.00%
153s
64.21 + 0.32
0.00%
243s
L2D+L2Seg-SYL
43.35 0.23
0.78%
157s
63.89 + 0.34
0.50%
248s
E.5
CASE STUDY: COMPARISON OF PREDICTIONS OF THREE L2SEG APPROACHES
42
(a) L2Seg-SSY prediction
(b) LLSeg-NNN NAR prediction
(c) L2Seg-AR prediction
Figure 12: Prediction comparison of L2Seg-SYN, L2Seg-NAR, and L2Seg-AR AR on two adjacent routes from a small-capacity CVRPIk solution. Red dashed lines indicate predicted unstable edges. L2Seg-SYN SYN provides the most reasonable predictions, while L2Seg-NAl -AR over-predicts unstable edges and L2Seg-AR fails to identify unstable regions.
We present a case study on small-capacin CVRPIK instance to analyze model prediction behavior. Since the learned model ultimately predicts on two adjacent routes, we visualize unstable edge predictions (red dashed lines) for two such routes using L.Seg-SYN, L,,ee--Y,,,SSS.NNAA and 1.2eeg-RR in Figure [2] L.2eeg-YY demonstrates selective prediction behavior, avoiding boundary edges while targeting specific unstable edges within route interiors-a a pattern consistent with our observations in Appendix B.I.I L2Seg-NAR successfully identifies unstable regions (route interiors) but lacks discrimination, predicting nearly all edges within these regions unstable without capturing local dependencies. L2Seg-AA AR exhibits selective prediction within regions but fails to properly identify unstable regions, many predictions occur boundaries. These results provide insight into
35

---

Published as a conference paper at ICLR 2026
Table 14: Unstable and stable edges convergence the first 10 iterations
Round #
7
9
Unstable Edge Overlapping Percentage
28.2%
33.5%
41.2%
49.2%
48.8%
54.1%
Stable Edge Overlapping Percentage Avg Segment Length
47.2%
58.2%
60.5%
64.7%
67.3%
69.4%
2.45
2.57
2.44
3.04
2.87
2.73
L.2ee--YYN SYN's s hybrid approach: the NAR component first identifies unstable regions, while the AR component leverages local information to make accurate predictions within each identified region.
E.6 UNSTABLE AND STABLE EDGES CONVERGENCE
We conducted experiments measuring overlapping predicted edges between adjacent iterations the first 10 rounds, revealing interesting dynamics: The overlap of predicted unstable edges increases from 28% 54%, while stable edge overlap increases from 47% to 69% across iterations, shown in the Table [4] This indicates gradual but not rapid convergence, allowing our method to continuously explore regions for re-optimization rather than getting trapped in fixed segments.
E.7 THE NEURAL NETWORK OVERHEADS OF L2SEG
We measured the overhead across CVRP and VRPTW instances ranging from 1k to 5k nodes in the Table [5] Even with our most complex model (L.2Seg-SYe) SYN), the overhead consistently remains below 10% of the total iteration time (ranging from 7.2% to 9.6%). This indicates that the overhead scales efficiently and predictably. Generally speaking, the overhead primarily stems from neural network inference, which is driven by two factors: input data size and network call frequency. Regarding the former, L2Seg employs a Batched Rob-Route Processing design. During embedding, we split problems into adjacent route pairs and use batch processing. This avoids memory bottlenecks and ensures that inference time scales efficiently for large-scale cases. Regarding the latter, the frequency of calling L.2Seg is tunable hyperparameter.
Table 15: Computational overhead analysis of L2Seg variants across problem scales
CVRPIK
CVRP2K
CVRPSK
1.25eg
Avg Total Time/lter
Overhead Rate
Avg 1.2Seg
Avg Total
Overhead Rate
Avg 1.25eg
Avg Total Time/ter
Overhead Rate
Method
Time/ller
Time/lier
Time/ttr
Time/lter
L2Seg NAR-LNS
4.5%
5.4%
12.9
6.2%
L2Seg-AR-LMN
0.63s
9.8s
6.4%
0.90s
10.8s
8.3%
1.24s
13.9s
8.9%
L2Seg-SYN-LL SYN-LNS
7.2%
9.4%
VRPTWIK 1k
VRPTW2k
VRPTW5K
L2Seg-NAR-LNS
0.37s
8.9s
4.2%
0.61s
10.4s
5.9%
0.83s
12.8s
6.5%
L2Seg AR LNS
0.62s
9.1s
6.8%
0.96%
11.9%
8.1%
1.14s
12.4s
9.2%
L2Seg-SYN-LNNS
0.76s
10.1s
7.5%
0.97s
10.8s
9.0%
1.36s
14.2s
9.6%
E.8 TIME OF TRAINING 122SG
We give the time spent on data collection, training the NAR, AR, and total time when training L2Seg. Empirically, our training pipeline scales efficiently, requiring under days for CVRP5k. We project that scaling to 10k instances would take approximately 6 days, which is still feasible.
F BROADER IMPACTS
On hand, the integration of deep learning into discrete optimization offers promising advances for real-world domains such as public logistics and transportation systems, where additional con- siderations for social equity and environmental sustainability can be incorporated. On the other
36

---

Published as a conference paper at ICLR 2026
Table 16: Training time breakdown for L2Seg across problem scales
Data Collection
Training time NAR
Training time AR
Total (parallel)
CVRPIK CVRP2K
6.3h
6.8h
13.7h
20.0h
10.4h
10.4h
22. 4h
32.8h
CVRP5K
19.2h
18. lh
40.7h
59.9h
hand, the application of deep learning methodologies in discrete optimization necessitates substantial computational resources for model training, potentially leading to increased energy consumption and carbon emissions. The quantification and mitigation of these environmental impacts represent critical areas for ongoing research and responsible implementation.
G LARGE LANGUAGE MODELS USAGE
We used LLMs to assist with manuscript revision. After completing the initial draft without LLM assistance, consulted LLMs for suggestions on improving specific text passages. All LLM- generated advice was carefully reviewed to ensure accuracy before incorporation. LLMs were not used for research tasks or any purpose beyond text refinement.
37


Reviews:
[{"review_id": "2uYQSvic6v", "reviewer": "Reviewer_SSqq", "summary": "This paper introduces Learning-to-Segment (L2Seg), a novel learning-guided framework designed to accelerate iterative solvers for large-scale VRPs. It first formalizes a First-Segment-Then-Aggregate (FSTA) decomposition technique, which identifies stable segments in a solution and aggregates them into hypernodes, thereby reducing the problem size for re-optimization. It also employs neural models to predict unstable edges. The paper presents three variants of L2Seg: a non-autoregressive (NAR) model for global prediction, an autoregressive (AR) model for local precision, and a synergized (SYN) model that combines their strengths. Extensive experiments on CVRP and VRPTW show that L2Seg accelerates state-of-the-art solvers by 2x to 7x while maintaining or improving solution quality.", "questions": "1. Can the author explain how to deal with the disconnected node after the insertion (shown as the initial node in the last subfigure in Figure 3)?\n\n2. Can the author explain why not evaluate the proposed L2Segment on another two problems, VRPB and 1-VRPPD, as the FSTA is already theoretically verified on these two problems?\n\n3. Please also see the weaknesses and clarify them.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) The paper is generally well-written and structured.\n\n(2) The novel FSTA framework and the specific problem of learning to segment for decomposition are a fresh perspective.\n\n(3) The FSTA framework is well-motivated, and its theoretical properties (feasibility and monotonicity) are formally proven for multiple VRP variants. \n\n(4) Experiments are comprehensive, testing on large-scale problems, multiple backbone solvers (classic, neural, hybrid), and various VRP types, demonstrating robust performance and generalizability.", "weaknesses": "1. While the paper demonstrates broad applicability, a more explicit discussion of the boundaries of FSTA/L2Seg's effectiveness would be beneficial. For example, under what conditions (e.g., problem size, structure, solver type) might the overhead of segmentation and aggregation outweigh the benefits?\n2. It is unclear that the boundary of the acceleration, as I notice that the HGS and LKH3 only run for a short time (5m and 10m). If the solving time extends, how will the acceleration benefit change in terms of both solution quality and time?\n3. Some works are also based on hypergraphs, but this paper does not discuss [1, 2].\n\n\n[1] A hierarchical destroy and repair approach for solving very large-scale travelling salesman problem. https://arxiv.org/pdf/2308.04639.\n\n[2] Destroy and Repair Using Hyper-Graphs for Routing. https://ojs.aaai.org/index.php/AAAI/article/view/34018", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "y4JjsytCGa", "reviewer": "Reviewer_b73r", "summary": "This paper aims to address the problem of redundant computation in iterative VRP solvers. The authors observe that during the iterative search process, a large portion of the solution stabilizes and no longer changes, yet the solver still consumes computational resources on these stable parts. To address this, the paper proposes FSTA (First-Segment-Then-Aggregate), a formalized decomposition framework with a full theoretical proof, to identify stable segments in the solution, aggregating their nodes into fixed hypernodes and then focusing the search only on the reduced unstable parts. Furthermore, this paper proposes L2Seg (Learning-to-Segment), a novel neural network framework for segmentation identification, including network architecture, training, and inference processes. Empirical results show that L2Seg can achieve speedups of 2 to 7 times for existing classical and learning-based solvers.", "questions": "1. Would better look-ahead heuristics lead to a better L2Seg model and ultimately better solution quality?\n2. How does the time spent on the L2Seg-SYN prediction step compare to the time spent running the backbone solver in a single iteration?\n\nMinor:\n\n3. Some double quotes are different, such as the one in line 252.\n4. Lines 47-48 write: FSTA identifies stable segments and then aggregates them as fixed hypernodes. But lines 146-147 write: FSTA segments the VRP solutions by identifying unstable portions, and then groups them into hypernodes. It seems there is a typo.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper's proposed method of learning to identify and freeze stable segments to accelerate iterative search is intuitive and novel. The proposed method is promising and achieves SOTA performance on most of the testing cases.\n2. The FSTA framework is technically sound and empirically robust. It is formalized, and the authors provide theoretical proofs of its feasibility and monotonicity across various VRP variants (CVRP, VRPTW, VRPB, etc.).\n3. The authors tested L2Seg on three different and representative backbone solvers (LKH-3, LNS, L2D), demonstrating its flexibility and versatility. Ablation experiments strongly support the necessity of the learned component (compared to stochastic FSTA).", "weaknesses": "1. The L2Seg-SYN process seems a bit complicated. It is unclear how much time is consumed by the L2Seg-SYN prediction step. If the L2Seg-SYN prediction step itself is costly, the 2x-7x speedup may only be noticeable over long runs.\n2. While L2Seg has been successfully applied to LKH-3, LNS, and L2D, Appendix B.1.4 mentions that applying it to HGS (another top-level solver) requires modifying the HGS source code, which is left for future work. This is a reasonable limitation, but it means that L2Seg is not \"plug and play\" for all iterative solvers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YSjktJ8JxS", "reviewer": "Reviewer_Kw4B", "summary": "This paper proposes Learning-to-Segment (L2Seg), a learning-based framework that accelerates iterative heuristics for Vehicle Routing Problems (VRPs). The key idea is to detect stable and unstable segments in existing solutions, aggregate stable portions into hypernodes via a First-Segment-Then-Aggregate (FSTA) decomposition, and then re-optimize only the unstable parts.\nThe authors design three neural variants (NAR, AR, and SYN)  and demonstrate empirical speedups over baseline solvers such as LKH-3, LNS, and L2D, on both CVRP and VRPTW benchmarks.", "questions": "- Are there any justifications of the label about stability? It is not entirely clear whether the notion of stability—as defined by differences between consecutive heuristic solutions—is reliable.\n- Are there any baselines using LNS with ML-based neighborhood selection? If such a baseline exists, the efficiency of proposed method can be more convincingly positioned as an improved (or generalized) version of ML-enhanced LNS.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The empirical study is well executed, covering multiple VRP variants, backbone solvers, and problem scales (1k–5k). Ablation studies, oracle comparisons, and visual analyses provide convincing evidence that the proposed framework accelerates iterative search.\n\n- The proposed framework is well documented, including pseudocode and architectural details. The authors have made strong efforts to ensure reproducibility and practical relevance.", "weaknesses": "- Limited conceptual novelty: the proposed framework can be viewed as a natural neural extension of existing decomposition-based heuristics. While the idea of stability is interesting, the framework essentially replaces a search space of LNS.\n- Restricted theoretical contribution: the theoretical analysis is limited to the monotonicity of the FSTA reduction — that improving a reduced problem implies improving the original one. However, the paper lacks theoretical analysis regarding solution quality guarantees or learnability.\n- Dependence on heuristic supervision: the training labels rely on the lookahead procedure with heuristic solvers. This raises concerns about the correctness of the label.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pIlJjtQOYY", "reviewer": "Reviewer_L8xN", "summary": "This paper proposes First-Segment-Then-Aggregate (FSTA), a decomposition framework for large-scale VRPs, motivated by the observation that in iterative optimization methods, a large portion of the intermediate solution structure tends to remain stable across iterations.\nTo effectively identify which parts of the solution should be modified and which should remain fixed, the authors introduce a neural network–based module called Learning-to-Segment (L2Seg), which enables efficient segmentation within FSTA.\nThrough experiments on CVRP and TSPTW, the authors demonstrate that integrating L2Seg can accelerate existing iterative solvers by a factor of approximately 2×–7×, while maintaining or improving solution quality.", "questions": "- How do the authors precisely define “iterative solvers” in the context of this paper?\n\n- The paper states that “a large portion of the solution remains stable.” Does this mean that most parts of the solution are not updated because they do not significantly contribute to objective improvement, or because only a small subset of solution elements is actually targeted for update by the iterative process?\n\n- Does L2Seg generalize to problem sizes that were not seen during training? If not, how feasible is it to train the model for significantly larger problem instances?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The proposed method successfully restricts the search space and achieves higher solution quality within the same computational budget on large-scale CVRP and TSPTW instances.\n\n- The framework is solver-agnostic and can be applied to multiple backbone iterative solvers, demonstrating its flexibility.\n\n- The experimental evaluation is comprehensive, including comparisons against diverse baselines from different methodological categories.", "weaknesses": "- Since L2Seg is trained in a supervised manner, its performance may degrade when the distribution of intermediate solutions during inference differs significantly from that of the training data.\n\n- The behavior of L2Seg appears conceptually closer to search-space restriction rather than genuine problem decomposition. Consequently, there is a risk that the restricted search could lead to premature convergence to local optima, preventing the discovery of globally superior solutions.\n\n- The model is trained and evaluated on problem instances of the same size distribution, leaving it unclear whether L2Seg generalizes to unseen problem scales. If it fails to generalize, collecting sufficient training data for larger instances could become computationally prohibitive, limiting the practical applicability of the approach.\n\n- (Minor) Typo found at line 130.\n\n- (Minor) References in lines 73–75 should be enclosed in parentheses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)