Towards Efficient Constraint Handling in Neural Solvers for Routing Problems
Authors: Jieyi Bi
Zhiguang Cao
Jianan Zhou
Wen Song
Yaoxin Wu
Jie Zhang
Yining Ma
Cathy Wu
Venue: ICLR 2026 Poster (2026)
Keywords: Routing Problems; Deep Reinforcement Learning; Constraint Handling; Combinatorial Optimization
Primary area: optimization
TL;DR: We advance neural VRP solvers’ constraint handling capability with Construct-and-Refine (CaR), a simple and generic framework featuring shared representation and joint training.

Abstract: Neural solvers have achieved impressive progress in addressing simple routing problems, particularly excelling in computational efficiency. However, their advantages under complex constraints remain nascent, for which current constraint-handling schemes via feasibility masking or implicit feasibility awareness can be inefficient or inapplicable for hard constraints. In this paper, we present Construct-and-Refine (CaR), the first general and efficient constraint-handling framework for neural routing solvers based on explicit learning-based feasibility refinement. Unlike prior construction-search hybrids that target reducing optimality gaps through heavy improvements yet still struggle with hard constraints, CaR achieves efficient constraint handling by designing a joint training framework that guides the construction module to generate diverse and high-quality solutions well-suited for a lightweight improvement process, e.g., 10 steps versus 5k steps in prior work. Moreover, CaR presents the first use of construction-improvement-shared representation, enabling potential knowledge sharing across paradigms by unifying the encoder, especially in more complex constrained scenarios. We evaluate CaR on typical hard routing constraints to showcase its broader applicability. Results demonstrate that CaR achieves superior feasibility, solution quality, and efficiency compared to both classical and neural state-of-the-art solvers. Our code, pre-trained models, and datasets are available at: https://github.com/jieyibi/CaR-constraint.

Published as a conference paper at ICLR 2026
TOWARDS EFFICIENT CONSTRAINT HANDLING IN NEURAL SOLVERS FOR ROUTING PROBLEMS
Jieyi B Zhiguang Cao?, Jianan Zhou', Wen Song', Yaoxin Wu', Jie Zhang', Yining Ma" Cathy Wu
'Nanyang Technological University Siinaapore Management University $Shandong University "Eindhoven University of Technology 'MIT jieyi001@e ntu. eduuu.edd.s. sg, zgcao@smu. edu. sg, jianan004@e ntu. wtw..uu.uuuu...... sg, wensong@email. sdu. edu. en, y wu2@tue nll, zhangj j@ntu.nuuucr edu fyiningma, cathywu\@mit, t.mmit.ee edu
ABSTRACT
Neural solvers have achieved impressive progress in addressing simple routing prob- lems, particularly excelling in computational efficiency. However, their advantages under complex constraints remain nascent, for which current constraint handinngg schemes via feasibility masking or implicit feasibility awareness can be inefficient inapplicable for hard constraints. In this paper, we present Construct-and-Reffn (CaR), the first general and efficient constraint-handling framework for neural routing solvers based on explicit learning- feasibility refinement. Unlike prior construction-seary hybrids that target reducing optimality gaps through heavy improvements yet still struggle with hard constraints. CaR achieves efficient con- straint handling by designing a joint training framework that guides the construction module generate diverse and high-quality solutions well-suited for a lightweight improvement process, e.g., 10 steps versus 5k steps in prior work. Moreover, CaR presents the first use of construction ittpriiiiiimmpormmeetteeeeeeeeee potential knowledge sharing across paradigms by unifying the encoder, especially in more complex constrained scenarios. We evaluate CaR on typical hard routing constraints showcase its broader applicability. Results demonstrate that CaR achieves superior feasibility, solution quality, and efficiency compared to both classical and neural state-of-the-aar solvers. Our code, pre-trained models, and datasets are available at: https::/ //g:://iii thgbtht........ www.tttuu..ooomiiie ctt.cooo//jjj. commjieyibi/Cat constr traint.
representation, enabling
INTRODUCTION
Vehicle Routing Problems (VRPs) often involve complex real-world constraints (Wu al., 2023). Classic VRP solvers, such as LKH-3 (Helsgaun, 2017) and OR-Tools (Furnon & Perron, 2024), have relied on heuristics carefully designed by human experts to handle these constraints and approximate near-optimal solutions. Recently, Neural Combinatorial Optimization (NCO) methods (Bengio et al., 2021) have offered a different path: they automate solver design with deep learning and exploit GPU- batched inference for high efficiency while ensuring solution quality (Kwon et al., 2020). However, recent work has primarily targeted simple variants, leaving their potential on hand-constr VRPs underexplored. In those more complex settings, where hand-crafte heuristics often leave certain research gaps, reinforcement learning (RI))-based methods may offer a promising alternative by learning navigate constraints directly from data. This makes effective constraint handling key challenge in advancing the broader applicability of NCO to real-world VRPs.
Most RL-based NCO solvers handle constraints via two schemes: feasibility masking and implicit feasibility awareness. Feasibility masking enforces constraints by excluding invalid actions in the Markov Decision Process (MDP). While effective for simple MDPs, it becomes intractable in complex cases where computing mask itself is ha-hard, e.g., with complex local search operators in neural improvement solvers (Ma al., 2023), or with interdependent constraints in neural construction
Work done during the author's internship MIT.
Corresponding author.

---

Published as a conference paper at ICLR 2026
solvers (Bi et al., 2024), as in Traveling Salesman Problem with Time Windows (TSPTW). Moreover, even when computable, the impact of strict masking in montticonstraint VRPs is often overlooked. As shown in Section 4.1, enforcing strict masks in Capacitated VRP with backhaul, duration, and time-window constraints (CVRPBLTW) can largely hinder RI convergence to a better policy. A recent line of work instead explores feasibility awareness, implicitly informing MDP decisions via constraint-related features (Chen et al., 2024), reward shaping (Ma et al., 2023), or approximated learnable masks (Bi al., 2024). However, they still remain limited: to our knowledge, no single method is generic to be effective across typical hard VRPs (e.g.. TSPTW and CVRPBLTW), feasibility and optimality gaps persist, and they often incur substantial inference overheads that undermine the efficiency. This motivates practical research question: Can we develop a neural constraint handling frumework that is simple, generul, and crucially, preserves the efficiency of the NCO solvers?
To address this, we emphasize learning- based feasibility refinement that has been overlooked for neural solvers: rather than purely focusing on enforcing feasibility via masking or implicitly learning feasibility signals by features or reward, we ask whether RL can explicitly refine infeasible solutions in very few post-construction steps while preserving optimality. To realize this, one may consider leveraging existing search techniques, such as random reconstruction (RRC) (Luo et al., 2023), efficient active search (EAS) (Hottung et al., 2022), or hybrid frameworks like collaborative policies (L.PP) (Kim et al., 2021), RL4CO (Berto al., 2025), and NCS (Kong et al., 2024). However, these methods are designed and evaluated to reduce optimality gaps on simple VRPs. When applied to hard VRPs, they can yield 100% infeasibility or rely on prolonged improvement process that runs for hours and often fails when search steps are reduced during training or inference (see Table 2).
In this paper, we present Construct-and-KK Refine (CaR), a simple yet effective feasibility refinement framework as a first step toward general neural approach for efficient constraint handling. CaR introduces an end-to-end joint training framework that unifies neural construction module with a neural improvement module. By design, it unites the complementary strengths of both paradigms while targeting efficiency: construction provides diverse and high-quality solutions conducive to fast refinement guided by our tailored loss function. Unlike prior hybrids that rely on heavy improvement to reduce optimality gaps, CaR uses fewer refinement steps, which can reduce runtime from hours to minutes seconds. Moreover, the proposed feasibility refinement scheme inherently motivates novel form of synergized feasibility awareness. CaR thus further considers a construction- construction-ipproeeennn shared encoder for realizing the cross- pross-paradigm representation learning, enabling potential knowledge sharing, thereby improving performance, particularly for more complex constrained scenarios.
We demonstrate the effectiveness of CaR on VRPs with diverse constraints, with particular emphasis on hard-constrained settings. When feasibility masking is NP-hard (e.g.. TSPTW), CaR achieves 6-8x speedups over state-of-the-ar neural baselines while improving feasibility and solution quality, even finding feasible solutions that the strong classic solver LKH-3 fails to produce. When masking is tractable but overly restrictive (e.g., multi-constraint CVRPBLTW), CaR shows dominant superiority over both neural and classic solvers. We also provide detailed analysis and ablation studies.
Our contributions are as follows: 1) We comprehensively analyze the limitations of existing feasibility masking and implicit feasibility awareness schemes, and introduce the learning- based feasibility refinement scheme for efficient constraint handling: 2) We present Sonstruct-and-Refiiee (CaR), a simple, general, efficiency-pressee preserving framework that performs feasibility refinement via end-to-end joint training that constructs diverse and high-quality solutions well-suited for rapid refinement guided by our tailored losses; 3) CaR enables novel synergized feasibility awareness via cross- posss-prraiigm representation learning that further boosts the constraint handling especially in complex cases; 4) Experiments showease that CaR can be potentially applicable to enhance most RL-based construction and improvement solvers in solving various constraend VRPs, delivering superior feasibility, solution quality, and efficiency compared to classical and neural vate-of-the-art solvers
2 LITERATURE REVIEW
We highlight the difference between CaR and existing neural solvers in Table 1: most existing neural solvers emphasize masking- feasibility handling, whereas CaR integrates three complementary schemes for broader and more effective constraint handling.
2

---

Published as a conference paper at ICLR 2026
Table 1:
Comparison between CaR and other existing neural solvers. CaR is the first to cover both simple and complex VRPs by combining flexible* masking, shared-representation to implicitly enhance feasibility awareness, and explicit feasibility refinement.
Methods
VRP applicabllity Simple Complex
Research focus Optimality
Feasibility
Feasbiliit Macking
Penalty
Feasibillity Awareness
Features Shared Rep.
Refinement
Feacibility
Most existing neural solvers
(e.g. PUMO, UIC, LCP RL4C0, NCS)
al., 2023)
Tang et all (2022)
MUSLA (Chen et 2024)
x
(Ri 2024)
CaR (Qurs)
Neural VRP solvers, End-to-end neural VRP solvers mainly fall into two paradigms: 1) Construction solvers learn to construct solutions from scratch in an autoregressive (AR) fashion. Among them, Attention Model (A (AM) (Kool et al., 2018) is milestone for VRPs. POMO (Kwon et al., 2020) further improved AM using diverse rollouts inspired by VRP symmetries. Subsequent studies have advanced AR solvers in inference strategies (Choo et al., 2022), training paradigms (Drakulic et al., 2023; Hottung et al., 2025), scalability (Jin et al., 2023; Hou et al., 2023), robustness (Geisler et al., 2022), and generalization over different distributions (Bi et al., 2022), scales (Zhou et al., 2023; Gao et al., 2024), and constraints (Zhou et al., 2024; Berto et al., 2024); 2) Improvement solvers learn to iteratively improve initial solutions, inspired by classic local search such as k-opt (Costa et al., 2020; Ma et al., 2023). ruin-anddrrepair (Hottung & Tierney, 2022; Ma et al., 2022), and crossover (Kim al., 2023). In general, they achieve near-optimal solutions with prolonged searches. Overall, either construction or improvement solvers mainly focus on simple VRP benchmarks, leaving complex constraint handling underexplored. See Appendix for further discussion.
Constraint handling for VRPs Existing neural solvers handle constraints mainly through two schemes: feasibility masking and implicit feasibility awareness. Most methods enforce constraint satisfaction by excluding invalid actions, such as local search moves in neural improvement solvers or node selection in neural construction solvers, via strict feasibility masking. While effective in simple VRPs, masking becomes intractable or ineffective in complex ones (e.g.. TSPTW, CVRP- BLTW; see Section 4. Recent works have thus explored implicit feasibility awareness, enhancing neural policies via reward/penalty-bast -based guidance or feature augmentation, such as Lagrangian reformulation (Tang et al., 2022), reward shaping for infeasible-region exploration (Ma ct al., 2023), constraint-related features (Chen et al., 2024), approximated learnable masks (Bi et al., 2024). However, they often incur high computational cost and still yield high infeasibility. Overall, even with these two constraint handling schemes, existing solvers is generic enough to be effective across both simple and complex VRPs, motivating a new perspective: explicit feasibility refinement.
Hybrid neural solvers. Recent works have explored hybridizing construction with policy search or heavy improvement. One line extends construction with additional search, e.g., active search (EAS) (Hottung et al., 2022) or beam search (SGBS) (Choo al., 2022), but these remain confined to the underlying construction policy and struggle with complex constraints. Another line employs reconstruction or decomposition, such as random reconstruction (RRC) (Luo et al., 2023) and collaborative policies (LCP) (Kim et al., 2021). While effective on simple VRPs, these methods often break feasibility when reconstructing or decomposing solutions, simlilar as other divide-and- conquer frameworks (Ye et al., 2024; Zheng et al., 2024), leading to high infeasibility even with penalties. Another line combines construction with heavy improvement (e.g., thousands of steps). RL4CO (Berto et al., 2025) couples pretrained POMO (Kwon et al., 2020) and NeuOpt (Ma et al., 2023) only at inference, while NCS (Kong et al., 2024) integrates them via a shared critic. However, both remain limited on hard-constraines VRPs, with NCS yielding 100% infeasibility on TSPTW in our tests. We from them in three key aspects: 1) we jointly targets feasibility and optimality, rather than only focusing on optimality: 2) we tightly couples construction and refinement via joint training and shared representation learning, enabling knowledge transfer, instead of treating both paradigms separately (Berto et al., 2025) or loosely coupled (Kong et al., 2024): 3) we promote efficient and precise refinement rather than lengthy improvement (e.g., from 5k to 10 steps).
3 PRELIMINARIES
VRP definitions. We define VRP on a directed graph 9 = (V.E), where V consists of n customer nodes (Vi,..., vn] and depot vo (except TSP variants). Each edge e(v; - vj) (or eij) & connects
3

---

Published as a conference paper at ICLR 2026
node Vi to Vj (i # with weight given by the 2D Euclidean distance. The objective is to minimize the total cost of solution subject to variant-specific constraints. Empirically, we distinguish between simple VRPs (c.g., CVRP), where feasibility masking is tractable and effective. and complex VRPs (e.g., CVRPBLIW with multiple constraints or TSPTW where computing masks is NP-hard since future feasibiiaiy must be evaluated for all possible actions), where masking is ineffective or intractable. See Appendix B for problem definitions and instance generation details.
MDP formulations. We consider neural solvers trained with reinforcement learning (RL), where construction and improvement are formulated as Constrained Markov Decision Process (CMDP), defined by the tuple (S, R. R.C), with S the state space, A as the action space, P SXAXS [0, I] as the state transition probability, R SKA-R as the reward function, and C - as the constraint function penalizing violations m constraints. The goal is to learn a policy ng : S P(A) that maximizes the reward while satisfiying the constraint(s). i.e.,
max (Tg) B, (T(G) s.t. Ja E II. Hyp = {xt II (T(Ta) = 0r),
where I Jnd are the expected returns of the reward and constraint function for constraints, respectively; and Пp represents a feasible space for the policy. Construction solvers construct solutions sequentially from scratch: state s, includes the partial solution, vehicle status (e.g., load, time), and unvisited node representations; action selects the next node; and the reward R is the negative tour cost at completion, R(T()) = -C(r). Improvement solvers learn refine an existing solution. At step the state s, includes the current solution T,, the best-so-fan so-far solution T, and instance features; the action a, applies an operator (e.g., flexible k-opt (Ma et al., 2023), remove- and-reinsert (Ma et al., 2022); see Appendix C). Following the convention (Chen & Tian, 2019), the reward is the cost reduction in the best-so-far solution, i.c., R, = min(C(r)_,) C(t,),
Relaxation of CMDP. Following Bi et al. (2024), apply Lagrangian relaxation to train the construction policy by penalizing constraint violations, adding cost term to the objective in Eq. (1);
C(T) = c.(e.) E E
(2)
R=1
where CL and Cy represent the objective cost (i.e., tour length) and the constraint violations, respec- tively. For example, if the arrival time Ij to node vi exceeds the time window ends új the node-level cost for time window violation is calculated as Cv(ey)= I Kj. The total violation cost Cv also accounts for the number of nodes with constraint violations to enhance constraint awareness.
4 METHODOLOGY
We revisit existing constraint-handling schemes for neural solvers and then introduce our CaR framework, which proposes a new perspective via feasibility refinement and further explores shared representations across construction and refinement enhance feasibility awareness.
4.1 DISCUSSION OF EXISTING CONSTRAINT HANDLING SCHEMES
Feasibility masking excludes invalid actions each node-selection step in construction MDPs and each local-search step in improvement MDPs. is widely used in prevailing neural solvers and works well when VRP constraints are simple. For instance, Table 12 shows that removing masking in CVRP increases POMO's optimality gap from 0.86% to 0.92%, confirming its effectiveness. However, masking faces two fundamental challenges complex VRPs. First, mask computation itself can be intractable. For example, in TSPTW evaluating time- iemeinttrreeendennt feasibility at each construction step requires checking all future actions, which NP-hard (Bi et al., 2024); similarly, computing feasible moves for local search operators such as k-opt is intractable in improvement solvers (Ma et al., 2023). Second, even when tractable, masks can be overly restrictive in multi-constraint VRPs. In CVRPBLTW, for instance, strict masking filters out more than 60% of nodes (Figure 6), severely limiting the search space and hindering RL convergence toward a high-quality policy (more discussion in Appendix E. In these complex VRPs, approximate mask (Bi et al., 2024) relaxed masks (as seen in POMO* vs. POMO in Table 2) provide partial relief but cannot fully resolve these issues: they may still fail to guarantee feasibility, introduce computational inefficiency, or degrade solution
4

---

Published as a conference paper at ICLR 2026
Feasible
Infeasible
Supervised
Diversity
Iteratively Refine for Tg times
Feusibiliit Optimality
Updute
good obj.
Construction
Top p
Refinement (trainable)
P
module
solutions
Oo
(trainuble)
Instances
Updute
pour
Tn
CaR
Shared representation
Overall framework of CaR, where the construction module provides diverse and high- quality solutions for the refinement module generate better solutions.
Figure 1:
quality. Beyond masking, recent works have turned to feasibility awareness, implicitly guiding MDP decisions rewards/penalties or constraint-related features. However, the former has been shown in Bi et al. (2024) to lose effectiveness in complex VRPs, while the latter serves only as an auxiliary signal for policy learning. This motivates the need for alternative schemes that explicitly handle feasibility through refinement.
4.2 JOINT TRAINING FEASIBILITY REFINEMENT WITH A CONSTRUCTION MODULE
To enable efficient feasibility refinement, we leverage the efficiency of construction and propose our CaR framework. CaR jointly trains construction and refinement by guiding construction module to generate diverse, high-quality solutions that are well-suited for rapid refinement with tailored losses. To integrate construction and refinement effectively, design joint training framework that optimizes both processes simultaneously in each gradient step, allowing them to co-evolve. As illustrated in Figure 1, for each batch of training instances G. the construction module first generates a small set of diverse, high-quality initial solutions parallel. These solutions are then refined by a lightweight neural improvement process within TR steps (i.e., TR vs. 5k in classic improvement methods), enabling rapid enhancement of high-potential candidates. The refined outputs then supervise construction, promoting collaborative correction of infeasibility and sub-optimality.
Construction policy loss. The policy
Th is trained by REINFORCE (Williams, 1992) with loss:
1 S E = 5 Σ
1 5 5
Σ R(T,) log x (T.))
R(T))
where the solution probability is factorized as (T) = 17 T ( Ted) with Tu denoting the partial solution prior selecting edge e, at step We employ a group baseline with diverse rollouts to reduce the variance. For simpler variants like CVRP, S solutions are generated via POMO's multi-start strategy (K won et al., 2020), while time-constrained variants (e.g., TSPTW and CVRPBLTW), sample S solutions avoid infeasibility (Hottung et al., 2025; Bi et al., 2024).
Tailored losses in construction module. To compensate for reduced diversity due to the removal of the multi-start mechanism and to enhance the diversity of initial constructed solutions for refinement, we introduce an auxiliary entropy-basee based diversity loss:
LoN Σ
le: Tea) log ( Te)),
which largely encourages policy exploration during RL training. To avoid inefficiency, evaluate candidates using the cost in Eq. (2), and only feed the top p high-quality candidates to subsequent refinement. If the refinement module improves constructed solution (indicated by I 1), the best-refined solution r" is used as a pseudo ground truth to supervise nTC
Ir'l
LsL = -I. Σ log Ty (e; T(y).
(5)
where indicates whether such refinement led to improvement the feasibility and objective. The final construction loss integrates three components, i.e., [(t-) Ls Lorv a2
5

---

Published as a conference paper at ICLR 2026
Instance Generator
Unified Encoder
Last Nade!
Solution Embedding
Construction Decoder
Multi-Head Attention (MHA)
Sulution Features
Sample
MatMul
Node Embeddiing
Select
Instances
K
Mathlul
Softmax
New Embedding
Refinement Decuder
Initiall Solutions
Mathuul
Refinement Features
Repeat
Solutions
Embedding
Copy
(f
Figure 2: Overview of the unified network architecture in CaR. Blue dashed arrows indicate informa- tion flow specific to refinement, while purple dashed arrows indicate flow exclusive to construction.
Relaxation of short-horizon CMDP for efficient refinement. Building the success of relaxed CMDP formulations for construction (Bi et al., 2024), we extend it to the refinement process as well. Unlike prior work (Kong et al., 2024; Ma et al., 2023), which models improvement as infinite-horizon MDP under the assumption that prolonged runtime acceptable (more discussion of short-horizon MDP design in Appendix E.5), adopt short-horizon rollout limit Tg. treating each step equally, consistent with CaR's 's efficient refinement design.
Refinement policy loss. The refinement policy z iteratively improves solutions over T' steps, with
probability of the refined solution step f is factorized as (T,) [ x (aglaxx: T,-1), where K denotes the total number of sequential refinement moves/actions, with further details in Appendix C. The RL loss L (1) for refinement is computed at each step using the REINFORCE algorithm in
Eq. (3), where S is replaced by p. since only p solutions are refined. The final refinement loss is
defined the average across all TR steps: L(OR) Ta Σ/e CR (f), encouraging each refinement step to contribute meaningfully and improving overall refinement efficiency. The joint training loss combines the above two losses, i.e., (()) L((F) + wL()", ), where w balances their scales. Such joint loss promotes information exchange between modules, enhancing synergy in collaboratively handling complex constraints.
4.3 CROSS-PARADIGM REPRESENTATION LEARNING FEASIBILITY
Beyond implicit feasibility awareness via features or rewards/penalties, our feasibility refinement naturally strengthens awareness through cross-paradigm representation learning. To further re- duce overhead and promote synergy, explore shared encoders for knowledge transfer between construction and refinement, especially in hard-constrained VRPs.
Shared representation across paradigms via a unified encoder. Given instance batch ( both paradigms learns to obtain high gigh-dimensional node embeddings h; via encoders. For CVRPBLTW. each node v, is represented by its coordinates, demand (i.e., linehaul backhaul), time window, and duration limit, i.e., ff = (x; Yi. I,, 4; 2). Unlike construction, refinement also incorporates solution features by encoding the sequential structure via positional information. To support both paradigms, we use a shared 6-layer Transformer encoder (Kwon et al., 2020) with multi-head attention. Positional encoding, required only in refinement, is injected using cyclic positional encoding via the synthesis attention mechanism (Ma et al., 2022). As shown in Figure 2, a multi-layer perceptron (MLP) fuses node-level attention scores a" and solution-leve scores a² from positional embedding vectors via element-wise aggregation.
Decoder. The decoder generates action probabilities from node representations, selecting the next node for construction or the modification for refinement. In CaR, we retain the original neural solver designs when applied to one construction and one improvement at a time. To validate generality, experiment with two construction backbones, POMO (Kwon et al., 2020) and PIP (Bi et al., 2024), and two refinement backbones, NeuOpt (Ma et al., 2023) and N2S (Ma et al., 2022). To adapt improvement solvers for variants (e.g.. TSPTW. CVRPBLTW), design and introduce variant-specific features, such as refinement history and node-level feasibility information (see Appendix C for details), to enhance constraint awareness. While also explored
follow their original

---

Published as a conference paper at ICLR 2026
Table 2: Results on complex VRPs: best are bolded; best within min are shaded to show solver efficiency.
n=
n=100
Method
#PParams
Paradigm
Obj. 1
Gap
Infsb
Obj.
Gap
Iufsb%
Time
LKH-3 (max mals 100)
25.590
0.004%
11,88%
7m
46.625
0.103%
31 11.05%
27m
LKH-3 (max trials 100001)
25.611
0.12%
7h.
46.858
0. 0.13%
1.4
OR Tools'
25.763
-0.001%
65.72%
2.4h
46.421
0.026%
97.45%
12m
Greedy-L
100.00%
GroedyyC
26.394
1.534%
72.55%
4.5
$1.945
9.651%
99.85%
11.4s
POMO
1.25M
L2CC-S
100.00%
100.00%
14s
POMO*
1.25M
L2C-S
26.222
1.65%%
37,27%
4s
47.249
1.959%
38.22%
14s
POMO PIP (greddy)
1.25M
122C-8
25.657
0.177%
2.675
7%
47.372
1.223%
6.9655
32s.
TSPRO
POMO* PIP (sampic 10)
1.25M
L2C-S
25.650
0.152%
1.87%
47.291
1.020%
4,47%
4.7m
UDC
250)
L2C-S
100.00%
4.9h
NeaDDg-GIRE +1 (T' 1k)
0.6M
1.21-8
25.627
0.061%
0.19%
2.3m
47.011
0.336%
0.13%
5.9m
NeuOgi-GIRE (7=
0.69M
L21-S
25,621
00448
0.04%
4.
155955
0.215%
0.06%
8m
NCS NeuOpi-GIRE 5kk
0.69M
L2I-S
25.617
0.028%
0.02%
11.6m
46.913
0.123%
0.02%
30m
1.6MM
L2CC+D-
100.00%
11.6m
100.00%
30m
CaR-POMO (Ts. 5) (Ours)
164M
L-
25.619
0.034%
0.02%
15s
47.27%
1.065%
4.20%
366.
CaR-POMO (Ts. 100 (Ours)
164M
LXC++D-S
25.615
00208
0.01%
47.074
0,581
2.77%
1.
CaR-POMO (7s,
(Ours)
12IC+11-8
25.614
0014%
0.01%
47.001
0.4066
3.44%
1m
CaR-PIP (Ta- (Ours)
164M
L-I
25.613
0.10%%
0.02%
47.000
0.315%
58c
CaR-PIP (Ta- 100 (Ours)
164M
L2IC+D-S
25.812
0.006%
0.01%
29s
46.945
0.191
0.004
1.4m
CaR-PIP (7a 201 (Ours)
1.4M
12(C-1-8
25.612
0.005%
0.00%
524
46.923
0. 0.1466
0.02%
2.4m
OR-Tools (short)
14,890
1,402%
0.00%
10:4m
2.518
0.00%
OR-Tools (long)
14.677
0.00%
1.7h
25.342
0.00%
3.5h
POMO
125M
L2C-S
15.999
9.169%
0.00%
2x
27.046
7.004%
0.00%
15
POMO-MTL
125M
L2C-M
15.980
9.055%
0.00%
27.24 244
7.746%
0.00%
76
MVMoE
3.68M
L2C-M
15:945
8.775
0.00%
27.142
7.332%
0.00%
10s
ReLD-MoEL
3.68
L2C-M
27.044
6.915%
0.00%
95
POMO-EAS-SGBS (short)
125
L2C-S
15.386
4.33%%
0.00%
25,
26. 005
2.616%
0.00%
2.3m
CVRPBLTT
POMO-EAS-SGB55 (loog)
125M
L2C-S
15.156
3.263%
0.00%
10.3m
25.558
0.854%
0.00%
1h
NeuOpt- (T Ik)
0.69M
L21-S
14,521
1.329%
33,80%
1.1m
21.597
3.390%
51.20%
2.5m
XenDpt-GIRE 2k)
0.69M
14.352
-0.031%
31.00%
24.366
0.875%
44.50%
5.1m
NeuDDi-GIRF" (T' 5k)
0.60M
121-88
14,201
-1.13%%
27.30%
5.5m
24.038
-1.541%
39 10%
12.7m
POMO* (Ours)
125M
L2C-S
14,873
2.310%
0.00%
2s
24.592
-1.645%
0.00%
4s
CaR (8-opt) (Ours)
161M
L2IC+D-S
14,872
2.271%
0.00%
21.597
-1.674%
0.00%
5s
(1-ap()
(Ours)
164M
L2IC+D-S
2.227%
-1.707%
9%
(6-opt) (T+
L2IC+D-S
2.114%
0.00%
-1.724%
17s
CaR (R&R) (T== 5) (Ours)
1.22M
L2(C+D-S
14.725
1.328%
0.00%
24.552
-1.835%
0.00%
65
CaR (R&R) (Ts 10) (Ours)
1.22M
L2IC+D-S
14.661
0.878%
0.00%
S6
24.174
-2. 14.1
0.00%
10p
CaR (R&R) 1' 20) (Ours)
1.2MM
L2(C+D-S
14,801
0.463%
0.00%
10s
24,400
-2.448%
0.00%
19%
3 abbreviations
Learning to Insprove; S Single-task solver, M Multi-takk Tools presolves before search; if it detects infeusibility, it terminates immodiately, making runtime shorter than preset.
Immroveeent: L2C
Learning Construct; L21
a unified decoder, results in Figure 8 show degraded performance, suggesting that while a shared encoder benefits representation learning, separate decoders remain important for paradigm-specific optimization an insight for future reference.
5 EXPERIMENTS
We now evaluate our proposed Construct-and-Ret -an-Reeine (CaR) framework in handling hard-constrained TSPTW and CVRPBLTW instances. We also provide detailed analysis and ablation studies.
Experimental settings. Training instances are generated on the fly as in (Zhou et al., 2024; Bi et al., 2024) (see Appendix B). For TSPTW, we mainly focus on the hard variants in (Bi et al., 2024). All experiments are conducted on problem sizes n = 50 and 100, following established benchmarks (Kool et al., 2018; Wu et al., 2021). Models are trained with 20,000 instances per epoch for 5,000 epochs with a batch size of 128 (Zhou et al., 2024). We set TR = 5 during training. During inference, 8x augmentation (Kwon al., 2020) is used construct initial solutions, followed by TR-step refinement. paprr-pprrmeters are detailed in Appendix 1. All experiments are conducted on servers equipped with NVIDIA GeForee RTX 4090 GPUs and Intel(R) Core i9- 19-109X0X CPUs at 3.30GHz. Our code, pre-trained models, and datasets will be publicly released upon acceptance.
Baseline. We compare our CaR framework with state-of-the-art (SoTA) classic and neural VRP solvers. Classic solvers include 1) LKH-3 (Helsgaun, 2017); 2) OR-Tools (Furnon & Perron, 2024); 3) Greedy heuristics, minimizing stepwise tour length (L) and constraint violation (C); and 4) HGS (Vidal et al., 2012). Neural solvers include 1) construction solvers such as the single-task solvers AM (Kool et al., 2018), POMO (Kwon et al., 2020) (+EAS (Hottung et al., 2022) + SGBS (Choo et al., 2022)), BQ-NCO (Drakulic et al., 2023), LEHD (+RRC) (Luo al., 2023), UDC (+RRC) (Zheng et al., 2024), VIT (Fang et al., 2024). PIP (Bi et al., 2024) and PolyNet (Hottung et al., 2025), as well the multi-task solvers POMO-MTL. (Liu al., 2024), MVMoE (Zhou et al., 2024)
7

---

Published as a conference paper at ICLR 2026
1.2
PIF
Infoagibiity (%6
Infossiiliity (%)
100
P1P
80
0.8
60
0.4
Nex3pe
Gap
C-0-RAR
40
20
NeDOye
R&R
0.0
200
400
600
200
400
600
200
400
600
200
400
600
Time
Time (8)
Time (5)
Time (6)
Figure 3: Performance over time on TSPTW-100 (left) and CVRPBLTW- (right). For CVRP- BLTW, POMO+EAS+SGBB and CaR always achieve 0% infeasibility due to feasibility guarantee by masking. Dots with black circles represent results reported in Table
and ReLD-MoEL (Huang et al., 2025); 2) the improvement solver NeuOpt-GIRE (Ma et al., 2023); and 3) hybrid solvers, including LCP (Kim et al., 2021). All construction and improvement methods are trained for ~780k (Zhou et al., 2024) (except UDC) and ~600k gradient steps (Ma et al., 2023), respectively, with all methods observed to be converged. For fair comparisons, we use pre-trained models. We note that many baselines were originally designed for simple VRPs (e.g., CVRP) and are not directly applicable to complex variants such as TSPTW and CVRPBLTW. To ensure fair comparison, we upgrade the SoTA neural solvers NeuOpt-GIRE (Ma et al., 2023), UDC (Zheng et al., 2024), and POMO+EAS+SGBS (Choo et al., 2022) using our design enhancements: the relaxed CMDP formulation in Eq. (2) (marked with *) and the proposed solution-level features (marked with $; Appendix C). Baseline selection and implementation details are provided in Appendix D.2.
Evaluation metrics. We evaluate performance using the metrics below: 1) average solution length (Obj.), representing the mean length of the best feasible solutions: 2) average optimality gap (Gap), measuring the difference between the best feasible solutions and (near-)optimal solutions obtained by the pess-perforning classic solvers (LKH-3 for TSPTW, OR-Tools for CVRPBLTW, and HGS for CVRP, marked with o); 3) total inference time (Time) taken solve 10,000 instances for TSPTW or 1,000 instances for CVRPBLTW and CVRP, parallelized on a single GPU; and 4) average infeasible solution ratio (Infsb%) on the best solutions after construction and refinement per instance.
5.1 MODEL PERFORMANCE ON VRPs WITH VARYING CONSTRAINT COMPLEXITIES
TSPTW results. We first test CaR on TSPTW, where most neural solvers fail due to their reliance but lack of feasibility masking. We use two construction backbones: the lightweight POMO* and the heavier but more effective PIP. with at 100 than CaR-PIP As shown in Table 2, CaR-POMO consistently outperforms PIP both solution quality and feasibility. On TSPTW-50, CaR reduces infeasibility to 0.00%, outperforming the best construction baseline PIP (1.87%) and our upgraded So7A improvement solver NeuOpt- GIRE (0.02%). In terms of optimality. CaR nearly matches LKH-3, achieving minimal gap of 0.005%. On TSPTW-100, CaR lowers PIP's 4.67% infeasibility to 0.02% and reduces the gap from 1.030% to 0. 1.66. While NeuOpt* improves with extended search (up to 30 minutes), CaR achieves competitive results with an 8x speedup within a runtime budget of 10 minutes (Figure 3), which aligns with CaR's 's aim of efficiency. Notably, CaR surpasses LKHH- and finds feasible solutions even when it fails, highlighting CaR's 's strength under complex constraints. Moreover, we present the case study of CaR's refinement trajectories Appendix E.6 show how CaR intelligently refines solutions for feasibility and optimality.
training 1.42x faster at n = 50 and 1.65x faster
CVRPBLTW results. On complex CVRPBLTW, feasibility masking filters out over 60% of nodes, severely limiting the search space (Figure 6). Interestingly, removing these masks and applying the relaxed CMDP in POMO significantly improves performance (e.g., CVRPBLTW-108 in Table 2). Unlike TSPTW, NeuOpt* fails in CVRPBLIW with 27-51% infeasibility, while CaR guarantees feasibility as other construction solvers. We compare CaR with the best single- paradigm solvers in Figure 3. CaR achieves best area under the curve, indicating superior efficiency and effeetiveness. We also validate CaR with k-opt and R&R, where R&R performs better (-2.448% vs. -1.724% due to finer-grained search better suited
20
Optimacity Optanniltyygen gon (%6
15
from 7. 7.004% to .645%
10-
POMO
B4-NCO
LBRD
(N177
UDC
ArVM
Cut
Figure 4: CVRPLIB results.
8

---

Published as a conference paper at ICLR 2026
Table 3: Results on T5PDL-50.
Table 5: Effects of joint training on TSPTW-50 under fixed bud- get. Construction cannot be trained with LKH-3 or pretrained improvement without extra design. See Appendix E.5 for more.
Method
Gapl
Infsb% I
Time
PIP (greedy)
3.122%
2.12%
9s
(sample)
2.630%
1.86%
CaR-PIP
2.190%
0.26%
53s
Joint train
Construction
Improvement
Gapl
Infsb%
Table 4: Results on SOP-50.
X
Random
LKH-3
0.011%
60.66%
Random
Pretrained NeuOpt (long)
/
100.00%
Method
Otg. 1
SOP Variant
Gapl
Obj.
SOP Variant
Gap 1
X
X
Pretrained PIP
Random
Trainable NeuOpt (short)
LKH-3
0.003%
7
100.00%
0.20%
Pretrained PIP
Pretrained NeuOpt (long)
0.134%
0.79%
LKH-3
14.732
16.302
Pretrained PIP
Trainable NeuOpe* (short)
0. 0.172%
2.59%
POMO
14,943
0.463%
Cal
14,831
0.676%
16.316
0.084%
/ (CaR)
Trainable PIP
Trainable NeuOpt (short)
0.005%
0.00%
to cuntii-onnstriins variants. Lastly, we observe that the performance of multi-task neural solvers is largely bottlenecked by their backbone (e.g., POMO), suggesting CaR can serve as a stronger backbone for future NCO foundation models.
Results on other VRP variants. We also evaluate CaR on TSP with draft limit (TSPDL), sequential ordering problem (SOP) with discrete precedence constraints and CVRP. Results in Table 3, Table and Appendix E.2 show that CaR consistently delivers competitive results while maintaining efficiency of the neural solvers across different constrained VRPs. To test CaR's generalization across scales, distributions, and simpler VRP variants, we apply it to CVRP and evaluate on CVRPLIB. As shown in Figure 4, CaR achieves strong performance and generalization. Notably, it is the first neural solver to efficiently handle constraints of varying complexity, unlike prior solvers that are either varifit- (e.g., Bi al. (2024)) or inefficient (e.g., Ma et al. (2023)).
5.2 EFFECTS OF THE JOINT TRAINING FRAMEWORK
We assess combinations of different construction (random or pretrained PIP) and improvement methods (LKH-3, pretrained long-horizen NeuOpt, and our short-horizon NeuOpt). Table shows that naive combinations yield only marginal gains over PIP alone 17.% vs. 0.177% gap; 2.59% vs. 2.67% infeasibility). Thus, simply substituting random initialization with a high-quality one is insufficient. However, CaR's joint training unlocks significant performance gains. Despite similar construction quality between pretrained PIP and CaR-PIP (results not shown), the latter exhibits markedly superior refinement. This confirms a non-trivial synergy in CaR, where initialization is specifically tailored for the subsequent refinement.
5.3 EFFECTS or THE DIVERSIFICATION SIGNAL LDIV
We investigate the impact of the diversity loss (Eq. 4) in our joint training framework. Recall that while multi-start mechanisms improve performance on simpler problems like CVRP (as shown in Table 12), they often degrade performance on complex constraints like time windows (Bi et al., 2024). Hence, we sample S start nodes to calculate the group baseline in the construction module rather than enumerating all nodes. To compensate for the resulting loss of diversity, we introduce LONV Results in Table show that adding LDIV improves overall performance, even when multi-start enabled in simple CVRP. To verify the diversity increment, we quantify the solution diversity between the constructed solutions of CaR (trained with LDIV) and PIP (without LDIV). As shown in Appendix E.3, adding LDIV increases the diversity of CaR's 's constructed solutions by 155 over the backbone, confirming that LDIY effectively increases solution diversity and enhances performance.
Table 6: Effects of LDIV.
Problem
Lorv
Gap
Infsb
0.325%
0.00%
CVRP
0.259%
0.00%
TSPTW
x
0.421%
0.58%
0.014%
0.01 %
5.4 EFFECTS OF THE SUPERVISED SIGNAL LSI.
We evaluate the impact of the supervised loss LSL (Eq. 5) in CaR using two construction backbones: POMO and PIP. Results in Table 7 indicate that the efficacy of the supervised loss depends on the strength of the underlying backbone. For the strong backbone (PIP), which is already highly optimized, with the gap of 0. 0.177% and infeasibility rate of 2.67% (as in Table 2), adding Lst.

---

Published as a conference paper at ICLR 2026
Table 7: Effects of LsL.
Table 8: Effects of shared representation on TSPTW.
Backbones
Lst.
Gap 1
Infsb %1
TSPTW-50 Hard
TSPTW-100 Medium
CaR-POMO
0.1366
0.29%.
Shared Rep.
#Params
Gap 1
Infsh %
Gap
Infsb% 1
CaR-POMO
0.014%
0.01%
CaR-PIP CaR-PII
0.006%
0.01% %
2.8M
0.199%
0.68%
7.589%
0.00%
0.005 %
0.00 %
1.6M
0.014%
0.01 %
5.815%
0.00%
Table 9: Generalization results on CVRPBLTW-200, The runtime for OR- is 1.8h.
Method
Train Scale
Test Scale
Gap J
Infsb %
Time
POMO*+EAS+SGBS (Choo et al,, 2022)
100
200
4.51%
0.00%
2.1m
NeuOpt* (Ma et al., 2023)
100
200
6.37%
75. 75.78%
17m
CaR (R&R. 20)
200
2.09%
0.00%
10s
Table 10: Generalization results on TSPTW-100 Hard with different time windows tightness.
Method
Train
Test
Gap
Infsh% %
Time
PIP (sample S) PIP (sample
tight
light
0.26%
4.62%
2.3m
loose
tight
0.03%
31.37%
2.3m
CaR-PIP (Tg 20)
tight
0.02%
3.52%
2.3m
yields only marginal gains; specifically, the gap improves slightly from 0.006% to 0.005%, and the infeasibility rate improves from 0.01% to 0.00%. In contrast, for the weaker backbone (POMO*), where the standalone model performs poorly, with the optimality gap of 1.959% and infeasibility rate of 38.22%, the supervised signal is critical. In this case, joint training with LsL markedly improves performance, reducing the gap from 0. 1.63% to 0.014%, and the infeasibility from 0.29% to 0.01 %.
5.5 EFFECTS OF THE SHARED REPRESENTATION
We study the effect of our shared representation via a unified encoder. As shown in Table 8, CaR with shared representation performs better on both hard-constrained cases (TSPTW-50 Hard and TSPTW- 100 Medium), indicating improved knowledge transfer across paradigms. Compared with using separate encoders and decoders, which share only the constructed solutions, CaR also reduces the number of learnable parameters. See Appendix E,4 for further analysis.
5.6 GENERALIZATION RESULTS
We now evaluate CaR's generalization performance across problem scales and constraint hardness. Regarding cross-scale generalization, where CaR is trained on CVRPBLTW-100 and tested on CVRPBLTW-200, results show that CaR significantly outperforms other SoTA neural baselines, maintaining 0% infeasibility and the lowest optimality gap within 10 seconds. Furthermore, for cross-constraint generalization, Table 10 demonstrates that CaR trained on loose constraints even outperforms PIP trained on tight constraints (see Appendix B. for data generation details).
6
CONCLUSION
This paper proposes Construct-and-Refiie (CaR), the first neural framework to handle constraints through new explicit feasibility refinement scheme, extending beyond feasibility masking and implicit fcasibility awareness. CaR jointly learns to construct diverse, high-quality solutions and refine them with lightweight improvement module, enabling efficient constraint satisfaction. We also explore shared encoders for cross-paradigm representation learning. To best of our knowledge, CaR the first neural solvers applicable and effective on VRPs with varying constraint hardness. Future work includes 1) integrating CaR with diverse backbone solvers, 2) applying more constrained vRPs or even broader COPs, e.g. scheduling (Zhang et al., 2020; 2024; Andelfinger et al., 2025), 3) improving scalability, 4) studying its theoretical properties, e.g. learnability (Yuan al., 2022), convergence (Thoma et al., 2024), or generalization bound (Duan et al., 2021), and 5) developing foundation NCO models based the insights of pross-paradignn representation in this paper.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This research is supported by the National Research Foundation, Singapore under its AI Singapore Al Research Fundamental Research Collaborative (US-NSF Researcher Call) (AISG Award No: AISG3- RP-2025-036-USNSP and its AI Singapore Programme (AISG Award No: LISG3-RP-2022-033 Any opinions, findings and conclusions recommendations expressed in this material are those of the author(s) and do not reflect the views of National Research Foundation, Singapore. We would like thank the anonymous reviewers and (S)ACs of ICLR 2026 for their constructive comments and service to the community.
REPRODUCIBILITY STATEMENT
We have made every effort to ensure the reproducibility of our results. The datasets used in our experiments are publicly available or generated following standard protocols, with all instance generation details provided in Appendix B. The model architecture is described in Appendix C, with hyperparameters and training/inference configurations detailed in Appendix D.1. Implementation details and the selection criteria for baselines are provided in Appendix D.2. Additional ablation studies and robustness checks are reported in Section 5 and Appendix E, Our code, pre-trained models, and datasets are available at: https: / thub. com/ cloo///ieyii//aaae Conssttiiiaaaacccttaattttttt
REFERENCES
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-766 2021.
Philipp Andelfinger, Jicyi Bi, Qiuyu Zhu, Jianan Zhou, Bo Zhang, Fei Fei Zhang, Chew Wye Chan, Boon Ping Gan, Wentong Cai, and Jie Zhang. Learning to Optimize Capacity Planning in Semiconductor Manufacturing. In Asia Simulation Conference (AsiaSim). Springer, 2025.
Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. In International Conference on Learning Representations Workshop Track, 2017.
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 2021.
Federico Berto, Chuanbo Hua, Nayeli Gast Zepeda, André Hottung, Niels Wouda, Leon Lan, Junyoung Park, Kevin Tierney, and Jinkyoo Park. Routefinder: Towards foundation models for vehicle routing problems, arXiv preprint arXiv:2406. 15007, 2024.
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. RI4co: an extensive reinforcement learning for combinatorial optimization benchmark. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining 2, pp. 228899 2025.
Jieyi Bi, Yining Ma, Jiahai Wang, Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng Chee. Learning generalizable models for vehicle routing problems via knowledge distillation. In Advances in Neural Information Processing Systems, 2022.
Jieyi Bi, Yining Ma, Jianan Zhou, Wen Song, Zhiguang Cao, Yaoxin Wu, and Jie Zhang. Learning to handle complex constraints for vehicle routing problems. Advances in Neural Information Processing Systems, 2024.
Felix Chalumeau, Shikha Surana, Clément Bonnet, Nathan Grinsztajn, Amu Pretorius, Alexandre Laterre, and Thomas D Barrett. Combinatorial optimization with policy adaptation using latent space search. In Advances in Neural Information Processing Systems, 2023.

---

Published as a conference paper at ICLR 2026
Jingxiao Chen, Ziqin Gong, Minghuan Liu, Jun Wang, Yong Yu, and Weinan Zhang. Looking ahead to avoid being late: Solving condtroostr traveling salesman problem. arXiv preprint arXiv:2403.05318. 2024.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting combinatorial optimization. In Advances in Neural Information Processing Systems, volume 32, pp. 6281-6299 2019.
Jinho Choo, Yeong-Dae Kwon, Jihoon Kim, Jeongwoo Jae, André Hottung, Kevin Tiemey, and Youngjune Gwon. Simulation- guideed beam search for neural combinatorial optimization. In Advances in Neural Information Processing Systems, volume 35, pp. 8760-8772, 2022.
Paulo da Costa, Jason Rhuggenaath, Yinggian Zhang, and Alp Eren Akçay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Asian Conference on Machine Learning, pp. 465-480, 2020.
Rodrigo Ferreira Da Silva and Sebastián Urrutia. A general vns heuristic for the traveling salesman problem with time windows. Discrete Optimization, 7(4):203 211, 2010.
Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Marc Andreoli. BQ-NCO: Bisimulation quotienting for generalizable neural combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
Yaqi Duan, Chi Jin, and Zhiyuan Li. Risk bounds and rademacher complexity in batch reinforcement learning. In International Conference on Machine Learning, pp. 2892-2902. PMLR, 2021.
Mingfeng Fan, Jianan Zhou, Yifeng Zhang, Yaoxin Wu, Jinbiao Chen, and Guillaume Adrien Sar- toretti. Preference-drie driven multi-objective combinatorial optimization with conditional computation. In Advances Neural Information Processing Systems, 2025.
Han Fang, Zhihao Song, Paul Weng, and Yutong Ban. Invit: A generalizable routing problem solver with invariant nested view transformer. In Forty-first International Conference on Machine Learning, 2024.
James Fitzpatrick, Deepak Ajwani, and Paula Carroll. A scalable learning approach for the capacitated vehicle routing problem. Computers Operations Research, 171:106787, 2024.
Vincent Furnon and Laurent Perron. Or-tools routing library, 2024. URL htt.::::///eeeellprrs... google. hatpll/ccco/ootmmmmtttttt/orrrro
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 on Artificial Intelligence, 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 Learning Representations, 2022.
Nathan Grinsztajn, Daniel Manelos-Blances Shikha Surana, Clément Bonnet, and Thomas 1) Barrett. Winner takes it all: Training performant RL populations for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
Keld Helsgaun. LKH-3 (version 3.0.7), 2017. URL http://wehhorel4..c..dd/
research/LKH-3. 3/.
André Hottung and Kevin Tierney. Neural large neighborhood search for routing problems. Artificial Intelligence, pp. 103786, 2022.
André Hottung, Yeong-Dae Kwon, and Kevin Tierney. Efficient active search for combinatorial optimization problems. problleem In International Conference on Learning Representations, 2022.
André Hottung, Mridul Mahajan, and Kevin Tiemnyy PolyNet: Learning diverse solution strategies for neural combinatorial optimization. In International Conference on Learning Representations, 2025.
12

---

Published as a conference paper at ICLR 2026
Qingchun Hou, Jingwei Yang, Yiqiang Su, Xiaoqing Wang, and Yuming Deng. Generalize learned heuristics to solve large-scale vehicle routing problems in real-time. In International Conference on Learning Representations, 2023.
Ziwei Huang, Jianan Zhou, Zhiguang Cao, and Yixin Xu. Rethinking light bescoder-based solvers for vehicle routing problems. International Conference Learning Representations, 2025.
Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. In International Conference Learning Representations, 2022.
Yuan Jiang, Yaoxin Wu, Zhiguang Cao, and Jie Zhang. Learning solve routing problems via distri- butionally robust optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, 2022.
Yan Jin, Yuandong Ding, Xuanhao Pan, Kun He, Li Zhao, Tao Qin, Lei Song, and Jiang Bian. Pointerformer: Deep reinforced multi-pointer transformer for the traveling salesman problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 8132-8140, 2023.
Chaitanya Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227, 2019.
Daisuke Kikuta, Hiroki Ikeuchi, Kengo Tajiri, and Yuusuke Nakano. Routeexplainer: An explanation framework for vehicle routing problem. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 30-42. Springer, 2024.
Minjun Kim, Junyoung Park, and Jinkyoo Park. Learning to cross exchange to solve min-max vehicle routing problems. In The Eleventh International Conference on Learning Representations, 2023.
Minsu Kim, Jinkyoo Park, and joungho kim. Learning collaborative policies to solve np-hard routing problems. In Advances Neural Information Processing Systems, volume 34, pp. 10418-10430 2021.
Detian Kong, Yining Ma, Zhiguang Cao, Tianshu Yu, and jianhua Xiao. Efficient neural collaborative search for pickup and delivery problems. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2018
Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. POMO: Policy optimization with multiple optima for reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pp. 21188-2111 2111, 2020.
Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. Advances in Neural Information Processing Systems, 02226198-22211 2021.
Zhuoyi Lin, Yaoxin Wu, Bangjian Zhou, Zhiguang Cao, Wen Song, Yingqian Zhang, and Senthilnath Jayavelu. Cross-problem learning for solving vehicle routing problems. arXiv preprint arXiv:2404. 1677, 2024.
Fei Liu, Xi Lin, Zhenkun Wang, Qingfu Zhang, Tong Xialiang, and Mingxuan Yuan. Multi-task learning for routing problem with cross-problem zero-shot generalization. In Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 1898-1908. 2024.
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. In International Conference on Learning Representations, 2023.
Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Advances in Neural Information Processing Systems, 2023.
13

---

Published as a conference paper at ICLR 2026
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 on Learning Representations, 2025. URL https: //openreview. net/ forum?id-TbbJJjjjum
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, pp. 11096-11107, 2021.
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 Thirty-First International Joint Conference on Artificial Intelligence, pp. 4776-47788 2022.
Yining Ma, Zhiguang Cao, and Yeow Meng Chee. Learning to search feasible and infeasible regions of routing problems with flexible neural k-opt. In Thirty-seventh Conference Neural Information Processing Systems, 2023.
Kaustubh Mani, Vincent Mai, Charlie Gauthier, Annie S Chen, Samer B Nashed, and Liam Paull. Safety representations for safer policy learning. The Thirteenth International Conference on Learning Representations, 2025.
Yimeng Min, Yiwei Bai, and Carla P Gomes. Unsupervised learning for solving the travelling salesman problem. Advances in Neural Information Processing Systems, 2023.
Roberto Montemanni, DH Smith, and Luca Maria Gambardella. A heuristic manipulation technique for the sequential ordering problem. Computers Operations Research, 35(12):3931-3944 2008.
Mohammadreza Nazari, Afshin Oroojlooy, Martin Takáč, and Lawrence V Snyder. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, pp. 9861-9871. 2018.
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.
Yiding Shi, Jianan Zhou, Wen Song, Jieyi Bi, Yaoxin Wu, Zhiguang Cao, and Jie Zhang. Generalizable heuristic generation through large language models with meta-optimization. In International Conference on Learning Representations, 2026.
Haoran Sun, Katayoon Goshvadi, Azade Nova, Dale Schuurmans, and Hanjun Dai. Revisiting sampling for combinatorial optimization. In International Conference on Machine Learning, pp. PMLR, 2023.
Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimizztion In Advances in Neural Information Processing Systems, 2023.
Qiaoyue Tang, Yangzhe Kong, Lemeng Pan, and Choonmeng Lee. Learning to solve soft-constrained vehicle routing problems with lagrangian relaxation. arXiv preprint arXiv:2207.
09860, arXiv:2207.098666. 2022.
Vinzenz Thoma, Barna Pásztor, Andreas Krause, Giorgia Ramponi, and Yifan Hu. Contextual bilevel reinforcement learning for incentive alignment. Advances in Neural Information Processing Systems, 37:127369-127435 2024.
Daniela Thyssens, Tim Dernedde, Jonas K Falkner, and Lars Schmidt-Thieme. Routing arena: A benchmark suite for neural routing solvers. arXiv preprint arXiv:2310.04140, 2023.
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-8))) 2017.
Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, Nadia Lahrichi, and Walter Rei. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60 (3):61 1 1-24,, 2012.
14

---

Published as a conference paper at ICLR 2026
Oriol Vinyals. Meire Fortumato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, volume 28, pp. 2692-2700, 2015.
Chenguang Wang and Tianshu Yu. Efficient training of multi-task combinarotial neural solver with multi-armed bandits. arXiv preprint arXiv:2305.06366, 2023.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3):229-23 226, 1992.
Lixia Wu, Haomin Wen, Haoyuan Hu, Xiaowei Mao, Yutong Xia, Ergang Shan, Jianbin Zhen, Junhong Lou, Yuxuan Liang, Liuqing Yang, et al. Lade: The first comprehensive last-mile delivery dataset from industry. arXiv preprint arXiv:2306. 10675, 2023.
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving routing problems. IEEE Transactions on Neural Networks and Learning Systems, 33 (9):5057-5069, 2021.
Pei Xiao, Zizhen Zhang, Jinbiao Chen, Jiahai Wang, and Zhenzhen Zhang. Neural combinatorial optimization for robust routing problem with uncertain travel times. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
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 real-time. In Proceedings of the AAAI Conference on Artificial Intelligence, 2024.
Kexiong Yu, Hang Zhao, Yuhang Huang, Renjiao Yi, Kai Xu, and Chenyang Zhu. Disco: Ef- ficient diffusion solver for large-scale combinatorial optimization problems. arXiv preprint arXiv:2406. /9705, 2024.
Rui Yuan, Robert M Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient. International Conference on Artificial Intelligence and Statisties, pp- 3332-3380. PMLR, 2022.
Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Xu Chi. Learning to dispatch for job shop scheduling via deep reinforcement learning. Advances in neural information processing systems, 33:1621-1634 2020.
Cong Zhang, Zhiguang Cao, Wen Song, Yaoxin Wu, and Jie Zhang. Deep reinforcement learning guided improvement heuristic for job shop scheduling. In International Conference on Learning Representations, 2024.
Xiao Zhang, Hai Zhang, Hongtu Zhou, Chang Huang, Di Zhang, Chen Ye, and Junqiao Zhao. Safe reinforcement learning with dead-ends avoidance and recovery. IEEE Robotics and Automation Letters, 9(1): 498, 2023.
Zeyang Zhang, Ziwei Zhang, Xin Wang, and Wenwu Zhu. Learning to solve travelling salesman problem with hardness-adaptive curriculum. In Proceedings of the AAAI Conference on Artificial Intelligence, 2022.
Zhi Zheng, Changliang Zhou, Tong Xialiang, Mingxuan Yuan, and Zhenkun Wang. Ude: A unified neural dovide-and-conquee framework for large-scale combinatorial optimization problems. Advances in Neural Information Processing Systems, 2024.
Jianan Zhou, Yaoxin Wu, Wen Song. Zhiguang Cao, and Jie Zhang. Towards omni-generalizable neural methods for vehicle routing problems. In International Conference on Machine Learning. pp. 22769-42788 PMLR, 2023.
Jianan Zhou, Zhiguang Cao, Yaoxin Wu, Wen Song, Yining Ma, Jie Zhang, and Xu Chi. MVMoE: Multi-task vehicle routing solver with coatture-of-eppert. In International Conference on Machine Learning, 2024.
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, pp. 4648-4658, 2022.
15

---

Published as a conference paper at ICLR 2026
Appendix
A Detailed literature review: neural VRP solvers
Problem selection and data generation
B.1
Traveling Salesman Problem with Time Window (TSPTW)
B.2
Capacitated VRP with Backhaul, Duration Limit, and Time Window Constraints (CVRPBLTW)
B.3 Capacitated Vehicle Routing Problem (CVRP)
B.4
Traveling Salesman Problem with Draft Limit (TSPDL)
B.5 Sequential Ordering Problem (SOP)
C Network architecture
C.1 Encoder
C.2 Decoder
Experimental settings
D.1 Experimental settings
D.2 Baseline selection and implementation
E Additional experiments and discussion
E.1 Discussion of the existing feasibility masking
E.2 Results on benchmark and synthetic datasets CVRP
E.3 Quantification for the diversity of the constructed initial solutions
E.4 Discussion shared representation
E.5 Discussion of the short-horizon design
E.6 Additional results for the pattern of CaR's refinement
E.7 Effects of different numbers of initial solutions
E.8 Hyperparamter experiments
E.9 Sensitivity to random seeds and statistical significance
E.10 Discussion on theoretical analysis
The Use of Large Language Models (L..Ms)
16

---

Published as a conference paper at ICLR 2026
A DETAILED LITERATURE REVIEW: NEURAL VRP SOLVERS
Generally, neural VRP solvers can be broadly categorized into two paradigms: construction solvers and improvement solvers.
1) Construction--ussel solvers learn to construct solutions from scratch in an end-to-end fashion. Vinyals et al. (2015) introduced the Pointer Network (PuNeet), leveraging Recurrent Neural Networks (RNN) to solve the Traveling Salesman Problem (TSP) in supervised manner. Building this, Bello et al. (2017) explored reinforcement learning (RL) training for PtrNet. Nazari et al. (2018) extended the approach to solve CVRP in autoregressive (AR) way. Among AR solvers, the Attention Model (AM) (Kool et al., 2018) stands out as a milestone to solve multiple VRPs. This was further advanced by the Policy Optimization with Multiple Optima (POMO) (Kwon al., 2020), which leverages diverse rollouts inspired by the symmetry properties of VRP solutions. Subsequently, numerous studies have advanced AR solvers in various perspectives. such as inference strategies (Hottung et al., 2022; Choo et al., 2022; Sun et al., 2023), training paradigms (Drakulic et al., 2023; Chalumeau et al., 2023; Grinsztajn et al., 2023; Luo al., 2023; 2025), interpretability (Kikuta et al., 2024), scalability (Zong et al., 2022; Jin et al., 2023; Hou et al., 2023; Fitzpatrick et al., 2024), robustness (Geisler al., 2022; Xiao al., 2024), benchmarking (Thyssens et al., 2023), and generalization over different distributions (Zhang et al., 2022; Bi et al., 2022; Jiang et al., 2022), scales (Zhou et al., 2023; Gao et al., 2024; Fang et al., 2024), and constraints (Lu et al., 2023; Wang & Yu, 2023; Zhou et al., 2024; Liu et al., 2024; Berto al., 2024; Lin al., 2024). Beyond AR solvers, another line of research predicts heatmaps in a non- con-autoregressve (NAR) manner to represent edge probabilities for optimal solutions (Joshi al., 2019; Hudson et al., 2022; Qiu et al., 2022; Sun & Yang, 2023; Min et al., 2023; Yu et al., 2024). With the learned heatmap, these solvers can greatly reduce the search space. Despite showing better scalability, NAR solvers often depend on post-search procedures, which can be either time-consuming or ineffective in handling VRP constraints, even for the simple cases such as CVRP. Furthermore, recent research has expanded multi-objective optimization (Fan et al., 2025) and
approaches (Shi et al., 2026).
2) Improvement-basee solvers learns to iteratively improve initial solutions, drawing inspiration from classic (meta- >heurissuussss such as k-opt (e.g., 2-opt (Costa et al., 2020: Wu et al., 2021; Ma et al., 2021), extended to flexible k-opt (Ma et al., 2023)), ruin-and-repair (Hottung & Tierney, 2022; Ma et al., 2022), and crossover (Kim et al., 2023). In general, improvement-basee methods can achieve near-optimal solutions given prolonged search time, whereas construction- methods typically offer a more efficient trade-off' between performance and runtime.
B PROBLEM SELECTION AND DAIA GENERATION
As single-task solver focused on constraint handling, our work aligns with prior single-task studies that typically evaluate 2-3 representative VRPs. Specifically, we consider three representative VRPs: complex constrained VRPs where feasibility masking is NP-hard thus intractable (TSPTW) or tractable but ineffective (CVRPBLTW), and simpler constraints (CVRP) where feasibility masking is tractable and effective. Below we introduce the detailed data generation process. Following the convention, all the node coordinates are generated under a uniform distribution, i.e., xi. 2/(0, 1].
B.I TRAVELING SALESMAN PROBLEM WITH TIME WINDOW (TSPTW)
We primarily follow the settings of a recent study (Bi et al., 2024). which introduced TSPTW with three difficulty levels: Easy (Chen al., 2024), Medium, and Hard. Given our focus on complex constrained VRPs, we report results on the Hard variant in the main tables, consistent with the benchmark dataset in (Da Silva & Urrutia, 2010). Except for the experiment in Table 8, where we use the Medium variant to show how CaR's 's unified encoder works constraint hardness changes, all other TSPTW experiments default to the Hard setting.
NP-hardness of computing feasibility masking TSPTW. During solution construction, neural solvers typically apply feasibility masking to exclude actions that violate constraints. In TSPTW, for instance, node v is masked out if its arrival time 1, exceeds its time window end u,. i.e.. fj uj- However, as highlighted in PIP (Bi et al., 2024), feasibility in TSPTW is not purely local: selecting node affects the current time, which in turn influences the feasibility of all future selections due
17

---

Published as a conference paper at ICLR 2026
to interdependent time window constraints. For example, node with a late time window might be locally feasible, but choosing it can delay the tour such that earlier nodes become unreachable, leading to irreversible infeasibility. Ensuring global feasibility thus requires evaluating whether current decision allows for any feasible completions, i.e., a process that involves simulating all future possibilities. This renders feasibility masking itself NP-hard, compounding the inherent difficulty of solving TSPTW.
TSPTW Hard. We first generate a random permutation т of the node set and sequentially as- sign time windows to ensure the existence of feasible solution for each instance. The time windows are drawn from a uniform distribution, where the lower and upper bounds are given by 4 1~ u (C((T) - 17, Cu(t)) " u (C,(r)) Cu(T,) + 77.. where Cz(T,) denotes the cumulative tour length of the partial sequence r' up to step and n7 controls the time window width. To adaptively scale time windows with problem size, we set 17 n, offering greater flexibility than the fixed value of 50 used in (Bi et al., 2024). Concretely, in PIP (Bi et al., 2024), the time window width for TSr decreases as the problem size increases. To scale time windows adaptively with instance size, we set instead of using PIP's fixed value of 50, resulting in a different setting, i.e., a looser time window for TSPTW-100. We note that we evaluate our CaR trained on this new adaptive setting in most of the tables in this work, except Table 10, which uses the original TSPTW-100 dataset from PIP (with significantly tighter time window constraints than our training set). Time windows are then normalized following (Kool et al., 2018) to facilitate neural network training. Since TSP solutions form a Hamiltonian cycle, equivalent to setting any node as the starting point. Thus, we designate a specific starting node for TSPTW by redefining its upper bound No as Uo = max (4, + Cz(e(v, vo))) i [1.
TSPTW Medium. We generate the lower and upper bounds of the time windows following a uniform distribution: 4, ~ '[[0,, Twl. where Nn estimates the expected tour length for the given problem scale (e.g.. T20 x 10.9 (Chen et al., 2024)). The upper bound u; is derived from as u; ~ I,+ Ty++o. 14[0.1 0.2]. While this data generation rule does not guarantee instance feasibility, preliminary results show that the time windows overlap significantly, leading to a high feasibility rate in the generated instances.
For all the TSPTW instances, we normalize all I, and u; by Ug to ensure their values fall within [0, 1J. Training data is generated on the fly, while inference uses the dataset from (Bi et al., 2024) for fair comparison. As noted in (Bi et al., 2024), all test instances are verified to be feasible, either empirically or theoretically.
B.2 CAPACITATED VRP WITH BACKHAUL, DURATION LIMIT, AND TIME WINDOW CONSTRAINTS (CVRPBLTW)
CVRPBLTW follows the setting in (Zhou et al., 2024; Liu et al., 2024: Li et al., 2021) and includes four key constraints: I) Capacity (C). Each node's ' demand q, is sampled from ((I....,,), and the vehicle's capacity Q varies by problem scale, with Q = 40 and Q 50. 2) Backhaul (B). Node demands are sampled from a discrete uniform distribution (1...., 9), with 20% of customers randomly designated as backhauls. Routes include both linehauls and backhauls without strict precedence constraints. 3) Duration Limit (L). The maximum route length is set to l = 3, ensuring feasible solutions in the unit square space '1( 1). 4) Time Window (7W)). The depot time window is defined as (/. uo] = [0. 3). and each customer node has a service time of s; = 0.2. The time window for node vi computed as follows: the center is sampled as y; U(4 Cy(e(vo. v))). ug Cz(e(v, vo)) - s)), where Cz(e(vo. v,)) = Cz(e(v, vo)) represents the travel time between the depot vo and node v,- The half-width drawn from w; u( ))= 10.01, 1). Finally, the time window is set as Ui u,] = [max(/o. Y: - w)), min(Ho. + w;)l Training data is generated on the fly, while inference uses the Ik-instance dataset from (Zhou et al., 2024) for fair comparison.
B.3 CAPACITATED VEHICLE ROUTING PROBLEM (CVRP)
We follow the standard setting (Kool et al., 2018; Ma et al., 2021; Kwon et al., 2020). Each node's demand qi is sampled from U(11 U(I 9), with vehicle capacities set to Ø 40 and 0000 50. Training data is generated on the fly, while inference uses the dataset from (Zhou et al., 2024) for fair comparison.
18

---

Published as a conference paper at ICLR 2026
B.4 TRAVELING SALESMAN PROBLEM WITH DRAFT LIMIT (TSPDL)
TSPDL arises in marine transportation, where vessel capacity constraints must be considered. Each node corresponds port with demand yi and draft limit d;. Instances are generated from TSP by assigning 0%% of nodes draft limits smaller than the total demand, i.e., d; ~ [4/, Σ 9y}, while the remaining nodes are set to d = -0 qJ. Feasible solutions are guaranteed during instance generation. Following Bi et al. (2024), we adopt the Hard setting with o = 90, and during inference we directly the datasets from Bi al. (2024) for fair comparison.
B.5 SEQUENTIAL ORDERING PROBLEM (SOP)
SOP (Montemanni et al., 2008) is routing problem defined by precedence constraints. It can be defined on a graph G (VV E). The objective find a permutation (V), ........ Vi with fixed start and end nodes and V, that minimizes the total travel cost, subject to all precedence constraints Vy) P, i... V; must precede vy. To ensure feasibility, we sample a random valid permutation, identifying all implied precedence pairs. We then randomly sample 4% of these pairs as constraints using a mixture of pairwise Euclidean distance (weight g) and random noise (weight g). We evaluate CaR on two SOP variants: Variant (h 20, g 0.3) and Variant 2 (h = 20, 0.8).
C NETWORK ARCHITECTURE
The network architectures of mainstream neural construction and improvement solvers are typically based Transformer encoder with attention-basee based decoder, enabling unification across both paradigms. In this paper, we adopt a unified encoder shared by the construction and refinement decoders. Specifically, we use 6-layer Transformer encoder, following POMO (Kwon et al., 2020), while retaining the original decoders from NeuOpt (Ma et al., 2023) and N2S (Ma et al., 2022), corresponding two representative local search operators: flexible k-ppt (Ma al., 2023) and remove-and-reinssrtion (R&R) (Ma et al., 2022), respectively. For the unexplored variants TSPTW and CVRPBLTW, we design new constraint-related features analogous the contextual features used in the original decoders. The concrete forward processes are introduced below.
C.1 ENCODER
As shown in Figure 2, the construction module first takes node features f -i-iinccuding coordinates (x,,)) and constraint-related features (c.g., time windows [4, u;] and demand qi) as input. For each node Vi, these features projected into d-dimensional embedding n:Th E Rd (d 128) via linear layer. The initial embedding is then passed through a 6-layer Transformer network (Kwon et al., 2020). At each layer j (j = 6). the embedding A O-11 is projected into query, key, and value vectors:
1 w!
K M
where W w() w e Rdd These are fed into multi-head attention (MHA) layer, whose output is:
(g (g
T
0 Softmax
Vd
The MHA output then linearly transformed:
wLD h MHA
(8)
where W e Rddd This passes through instance normalization with residual connection:
n IN (R.0 -(--1)
Next, a feed-forward (FF) layer refines the output:
" w ReLU x(
(10)
where w()) Ribod, w !dd'dd and d' 512 in (Kwon et al., 2020). The final embedding at layer is:
h IN (k" br)))
(11)
19

---

Published as a conference paper at ICLR 2026
Thereafter, this process is repeated for 6 layers, and the final encoder output is h; n1
When it comes to the refinement module, the input changes from a node feature set to linked list (i.e., the solution), which consists of the original node features plus positional information and pointer to the next node in the solution. Notably, for CVRP variants, the depot node may appear multiple times, with each occurrence treated as a distinct node due to its different position. The refinement module shares the same operations as the construction module, except for Eq. (7). Specifically, we first incorporate the cyclic positional encoding (CPE) from (Ma et al., 2021) to obtain the positional embedding pj E Rd. We then apply a self-attention mechanism:
ij = (i) (W" pi).
(12)
where W W E RRxd, to compute the positional attention matrix a'. We replace Eq. (7) from the construction module with:
11 K MLP ([q) Pil)
(T
h 0
Softmax
(13)
Vd
where the MLP reduces the dimension of the concatenated attention scores, i.e., [a",a"] in Figure 2, from 2 to following the Syn-Att mechanism proposed in (Ma et al., 2022).
C.2 DECODER
The construction decoder primarily employs an MHA layer, where the key and value vectors linearly transformed from the node embedding h, The query vector is computed using contextual information from the construction process, including: I) the embedding of the partial solution h² (i.e., the node embedding of the last node in the partial solution), and 2) the step-wise solution features f², which include the vehicle's 's remaining load, current time, and current sub-tour length. The MHA output is calculated as:
q, ki Vd
Softmax
E
(14)
where & is the feasibility mask for node v,. We mask out visited nodes to ensure solution validity across all variants. For CVRP, discussed in Appendix E. we also mask nodes that violate capacity constraints at each construction step. The output of each head is then passed through a linear layer parameterized by Wo yielding ha Woa. Finally, the decoder computes selection probabilities for all candidate nodes using single-head attention layer:
hT
= Softmax ( tanh
+ E2
(15)
where & scales the logits to encourage exploration (Kwon et al., 2020).
The refinement decoder follows the original design in the NeuOpt (Ma et al., 2023) and N2S (Ma et al., 2022), which performs two representative local search operators: the flexible k-opt' and remove-and- reinsertion (R&R), respectively. Figure illustrates the detailed improvement process in a single time step for different local search operators, where each node selection corresponds to a full computation of the network decoder. Note that although the original NeuOpt and N2S decoders adopt different architectures, their input and output formats are similar. At each refinement step = -,.... TR. the inputs include: (i) the updated node embedding Iy derived from the previous solution T,- (with To as the top-p initial construction solutions); (ii) refinement features encoding feasibility transition history for k-opt or removal action history for R&R; and (iii) refinement embedding of the last action node, analogous to the solution embedding in construction. The output is the selection probability over candidate nodes for the next refinement operation (c.g., k-opt, removal, or insertion).
To adapt improvement solvers to variants (c.g., TSPTW, CVRPBLTW), we follow their original design principles while integrating variant-specific features, such as refinement history and neve-level feasibility information. Specifically, when using the NeuOpt decoder, we encode the feasibility of the most recent three refinement steps as a binary vector to represent refinement history and incorporate node-level feasibility features to enhance constraint awareness. For TSPTW, these features include
Following (Ma al., 2023), we set < 4.
20

---

Published as a conference paper at ICLR 2026
the arrival time at each node, time window violation value, last node arrival time, and indicator of whether the solution becomes infeasible after visiting the current node. For CVRPBLTW, node-level feasibility features include binary indicators for depot and backhaul nodes, violation values for each constraint, constraint-related attributes (e.g., arrival time and cumulative distance/demand), and infeasibility markers indicating whether the solution becomes infeasible before or after visiting the Current selected nodes
current node. Adapted NeuOpt variants are marked with in the main tables.
C End points
+ Added edges
Deleted edges
Direction change
Select
Select @
Select
Remove
Remove +
Remove [null]
-
[null]
$
Select
Select i
Remove
Remove
+
Add
Add
+ 2
Figure 5: Illustration of actions and operations in k-opt (top) and remove-and-reinseriio (bottom).
D IMPLEMENTATION DETAILS
D.I EXPERIMENTAL SETTINGS
We preset refinement steps TR 5 during training. Models trained using Adam with learning rate of x 10-4, weight decay of x 10-6. Follow the setting of (Kwon et al., 2020), we use instance normalization in the MHA and the embedding dimension issues early in training, refinement is activated after a ~ 10-epoch warmup of the construction module. To optimize GPU memory utilization, we adjust the number of refined solutions p separately for each problem size during training. We set = 0.01 and = in the construction loss, and set 100 TSPTW and CVRP, and 10 for CVRPBLTW based on the relative loss scales between modules observed during warm-up epochs. During inference, TSPTW and CVRPBL.TW results are obtained without multi-starting, consistent with the training setup. For each augmented instance, we sample one solution for TSPTW and greedily generate one for CVRPBLTW (p 1), which are then passed to the refinement module. For CVRP, Table 12 shows that multi-starting improves performance, so apply it during construction but refine only the top p solutions for efficiency, setting p 2 for = 50 and = for 100 due to the GPU memory constraint. We use only one GPU for all problem sizes during inference ensure fair comparison across variants.
128. To prevent out-of-memory
D.2 BASELINE
We compare our CaR framework with state-of-the-art classic and neural VRP solvers. Since CaR is positioned as single-task solver, we primarily compare it against the best-performing single- task, single-paradigm methods, namely, construction, improvement, and post-construction search approaches", for the unexplored hard-constrained problems TSPTW and CVRPBLTW. For com-
We do not consider post- construuuttt search methods (e.g., fine-tuning via EAS (Hottung et al., 2022), beam search via SGBS (Choo et al., 2022), and random reconstruction via RRC (Luo et al., 2023)) as cross cross-paradee paradigm like CaR, since they rely the construction policy. These approaches face inherent limitations for constraint handling.
21

---

Published as a conference paper at ICLR 2026
pleteness, we also include comparisons with recent multi-task solvers, particularly benchmark problems like CVRP and CVRPBLTW. Below, we detail the baseline selection for each problem.
1) TSPTW: We primarily compare against PIP, the SoTA construction solver. No improvement or post-search methods have been implemented on TSPTW in prior work, so we adapt the single-task SoTA improvement solver NeuOpt (Ma et al., 2023) (denoted as NeuOpt*#) and the strongest post- search method UDC+RRC (Zheng et al., 2024) by incorporating our Lagrangian-relaxen relaxed reward and constraint-related features. This allows to highlight CaR's cross-paradigm advantage over all types of single-paradign methods. Multi-task solvers are excluded, as they rely on feasibility masking, which is intractable for TSPTW.
2) CVRPBLTW: As this variant has only been addressed by multi-task solvers in prior work, we primarily compare against them. Among single-task methods. POMO (Kwon et al., 2020), as implemented in MVMoE (Zhou et al., 2024), is the best-performing construction solver. No single- task improvement or post-search methods have been applied to CVRPBLTW, so we adapt the SoTA improvement solver NeuOpt (Ma et al., 2023) (denoted as NeuOpt**) and the strongest post- search method UDC+RRC (Zheng et al., 2024) by incorporating our Lagrangian-relaxen reward and constraint-related features. However, UDC cannot handle multiple constraints simultaneously, we instead adapt the relaxed reward to SGBS (Choo et al., 2022) on top of POMO.
3) CVRP: CVRP is well-studied variant that most of the neural VRP solvers have implemented on. For comprehensiveness, we compare with multiple recent baselines listed in Table 11.
Table 11: Neural baselines for CVRP result comparison.
Type
Paradigm
Neural baselines
Single-task
Consiruction
(Kool al., 2018), POMO (Kooon et 2020), BQ-NCO (Draizulic 2023), LEHD
UDC (Zhang et al., 2024), InVI (Pang et al., 2024), PolyNet (Hotting et al., 2025)
2023),
Single task
Construction + Post search
SGi8S (Choo et al., 2022) (on top of POMO EAS (Hotning er al,, 2022). RRC (Lao et al,, 2023) (oe of LEHD and LDC)
Multi-tsk
Construction
POMO-MTI, in al., 2024), MVMofE (Zhon et al., 2024), Rel D-MoL. (Huang al., 2025)
Single-task
Imsrovement
NeuDyc-GiRRF (Ma AM+LCP 202))
2023)
Single-tak
Construction Improvement
We then introduce the implementation details for each baseline.
1) Classic solvers:
LKH-3 (Helsgaun, 2017), a strong solver capable of handling multiple VRP variants, run with maximum of 10,000 trials and I run as in (Kool et al., 2018). We apply LKH-3 to CVRP and TSPTW; however, is not used for CVRPBLTW due to lack of support.
OR-Tools (Furnon & Perron, 2024), an open-source combinatorial optimization suite, where we use cheapest insertion strategies for initialization and guided local search under time limits of 20/40 (short) and 200/400 (long) seconds for =50/100, following (Zhou et al., 2024; Bi et al., 2024). We apply it to TSPTW and CVRPBLTW due to the absence of strong classic solvers for these variants.
Greedy Heuristic, hand-crafted heuristic selecting the nearest node (Greedy-L.) or the node with the soonest time window end (Greedy-C) during construction. We apply it only to TSPTW following (Bi et al., 2024).
HGS (Vidal al., 2012), a state-of-the-eeeeeeeee heuristic solver for CVRP. We directly cite the results of HGS on CVRP and CVRPBLTW from MVMoE (Zhou et al., 2024), as we use the same test dataset.
2) Neural construction solvers:
AM (Kool et al., 2018), a classical neural construction method that first introduced the Transformer architecture for solving various VRP variants via reinforcement learning. We evaluate it only on CVRP (Table 14) due to its inferior performance on constrained VRPs and page limits. Pretrained models are used for evaluation.
POMO (Kwon et al., 2020), an enhanced version of AM, widely adapted for multiple VRPs VRPs-CVRP (Kwon et al., 2020), TSPTW (Bi et al., 2024), and CVRPBLTW (Zhou et al., 2024). We retrain POMO on all variants to match CaR's 's gradient steps for fair comparison.
22

---

Published as a conference paper at ICLR 2026
BQ-NCO (Drakulic et al., 2023), a generic framework that reformulates the MDP using bisimulation quotienting to reduce the state space and exploit problem symmetries. We report its greedy decoding results on CVRPLIB for comparison.
LEHD (Luo et al., 2023), a novel framework that rethinks conventional architectures by adopting light encoder and heavy decoder design, trained via supervised learning. We evaluate it only on CVRP, as extending new domains would require extensive label generation.
UDC (Zheng et al., 2024), recent unified divide-and-conquee framework designed for large-scale VRPs. For TSPTW, we retrain UDC with our relaxed objective (Table 2). For CVRPBLIW, applying relaxed CMDP is impractical due to the difficulty in defining consistent objective across sub-tours under multiple constraints, which goes beyond UDC's intended design. For CVRP, use the released pretrained model trained adapting sub-tour lengths to 25 for 50 and 50 for n = 100 (Table 14).
500-1000,
InVIT (Fang et al., 2024), a generalizable solver employing a nested-view Transformer encoder capture multi-scale local structures while enforcing permutation invariance. We compare with its pretrained model on CVRP.
PolyNer (Hottung al., 2025), a fine-tuning method that introduces random vectors into the decoder to enhance solution diversity. Due to the unavailability of source code, we directly cite its performance on CVRP from the original paper for comparison.
EAS (Hottung et al., 2022), a fine-tuning approach that adapts pretrained model parameters per instance. We use the POMO+EAS version as the base model of SGBS for comparison.
SGBS (Choo et al., 2022), or simulation-guided beam search, integrates neural construction with simulation rollouts. For CVRPBLTW, we adapt it with the relaxed reward (*); for CVRP, we use the released pretrained model. As the default 28-iteration setup is time- consuming, we also report a single-iteration version (short) for fair comparison with CaR.
POMO-MTZ. (Liu al., 2024), multi-task solver designed handle multiple VRP variants with single model. We directly cite its results on CVRP and CVRPBLTW from MVMoE (Zhou et al., 2024), as we use the same test dataset.
MVMoE (Zhou et al., 2024), multi-task solver enhanced by a mixture-of-expers mecha- nism and implemented on 16 VRP variants. We evaluate it using the released pretrained models.
ReLD-MoEL (Huann et al., 2025), a multi-task solver that enriches contextual information during auto-regressive solution construction. Due the unavailability of code, we directly cite its reported performance on CVRP and CVRPBLTW from the original paper for comparison.
PIP (Bi al., 2024), novel framework that learns approximate feasibility masking for complex VRPs with interdependent constraints, such as TSPTW. We retrain the model under our settings to ensure fair comparison.
3) Neural improvement solvers:
NenOpt-GIRE (Ma et al., 2023), the SoTA single-task improvement method that uses neural networks to perform flexible k-opt operations. GIRE explores infeasible regions to enhance performance. We follow its default settings for training and testing. For CVRP, directly evaluate using its pretrained model. For TSPTW and CVRPBLTW, which are not implemented in the original paper, adapt the method with the relaxed reward function (*) and our tailored constraint-related features ($), denoted as NeuOpt-GIREet For all variants, we report results with 1k, 2k, and 5k iterations using random initial solutions.
4) Neural hybrid solvers:
LCP (Kim et al., 2021), single-task task cross pooss-pardiigm method where the seeder constructs initial solutions, decomposes them into sub-tours, and the reviser independently refines and merges them into complete solutions. Due to the unavailability of source code, we directly cite reported performance on top of AM for CVRP from the original paper.
NCS (Kong et al., 2024), a single-task cross- passsdia method where the improvement policy is trained with a construction policy via shared critic. It is implemented on the pickup and delivery problems (PDP) and still rely on heavy improvement. To maximize comparison, adapt TSPTW using our constraint-related features and penalty guided.
23

---

Published as a conference paper at ICLR 2026
E ADDITIONAL EXPERIMENTS AND DISCUSSION
E,1 DISCUSSION OF THE EXISTING FEASIBILITY MASKING
We now present our insights into the limitations of existing feasibility masking mechanisms. As shown in Table 12, removing feasibility masking for CVRP hampers its performance, in contrast to more complex problems like CVRPBLTW, where its removal leads improved results (see results of POMO* vs. POMO in Table 2). To further investigate this, we compare the two model variants with and without masking on CVRPBLTW- 100. Figure 7 shows that the mode with strict feasibility masking (red) converges rapidly in terms of training loss (saturating after 2k epochs) but yields noticeably lower-quality solutions, while the one without masking (blue) converges more gradually but ultimately attains significantly better solution quality. This finding is consistent with prior works (Mani et al., 2025; Zhang et al., 2023), which shows that excessive action-space pruning leads conservative policy behavior and degraded learning performance These results suggest that while existing feasibility masking is sufficient for simple problems, it is far from a silver bullet for handling complex constraints. In fact, for highly constrained problems, feasibility masking is often intractable (e.g., TSPTW) or ineffective (e.g., CVRPBLTW), resulting in infeasibility and sub-optimality.
Table 12: Effects of the multi-starting and feasibility masking during construction on
multi-start w. mask
Obj.l
Gapl
Infsb %c
10,550
2.093%
0.00%
10.520
1.793%
0.00%
10.431
0.921
0.00%
10.424
0.857%
0.00%
Masked modes percuntage
1000
Gap Tools (%)
12
Training loss
10
-1
-2
w. mask
mask wio
w/o mask
60
Construction Step
1000
2000 3000 4000 5000 Epoch
0
1000
2000
3000
4000 5000
Epoch
Figure 6: Masked node count in CVRPBLTW construction.
Figure 7: Curve of training loss (left) and optimality gap (right).
To address these challenges, we propose the CaR framework. For TSPTW, CaR leverages refinement correct infeasibility and improve solution quality. For CVRPBLTW, we found that removing this restrictive mask significantly improves the performance (Gap: 9.17% vs. 2.31 %), but it leads to unexpected infeasibility (2.6%). CaR addresses this by applying refinement, which further reduces infcasibility and improves solution quality. However, small fraction of infeasible solutions can still remain. Since feasibility can ultimately be guarantced through masking, we apply a final reconstruction step with feasibility masking during inference to ensure all reported solutions valid (see Table 13). This strategy allows CaR to relax constraints during construction and refinement to enhance quality while maintaining overall feasibility through targeted post-processing. Note that in this paper, "without masks" does not imply removing all masks. All VRP variants must satisfy the fundamental constraint that each node (except depots) visited exactly once. To ensure the validity of the generated solutions, we retain the masking of visited nodes during the construction process.
E.2 RESULTS ON CVRP
To assess CaR's s extendability, we evaluate on the simple CVRP, where feasibility masking is tractable and effective. In this setting, CaR shifts focus toward optimizing solution quality while still benefiting from limited exploration of infeasible regions. Table 14 compares CaR with classic, single-paradigm, and cross-paradigm methods. CaR delivers strong performance within short
24

---

Published as a conference paper at ICLR 2026
Table 13: CaR module impact on CVRPBLTW feasibility and quality (Bold: reported in Table 2).
n=
n=100
Method
Module
Obj-J
Gapl
Infsb %
Obj-1
Gapl
Infsb %
Construction (w/o mask)
14.798
2.116%
3.50%
24.404
-2.050%
2.80%
CaR
Refinement (k-opt)
14.759
1.682%
2.50%
24.360
-2.285%
2.60%
Re-construction (w. mask)
14.844
2.114%
0.00%
24.585
-1.724%
0.00%
Construction (w/o mask)
14.843
2.235%
2.60%
24.460
-1.715%
3.10%
CaR
Refinement (R&R)
14,567
0.221% 1%
1.10%
24,215
-2.88%%
1.90%
Re-construction (w. mask)
14,601
0.463% %
0.00%
24,400
-2.448% %
0.00%
inference time, for example, achieving 0.889% optimality gap on CVRP-100 in 20s using only 20 refinment steps, whereas NeuOpt-GIRE requires over 5 minutes with 5,000 steps. When combined with EAS, CaR further outperforms all baselines, achieving the SoTA results.
We validate CaR's generalization under distributional shift on the world CVRPLIB dataset (Uchoa et al., 2017), as shown in Figure 4. Since 1) extensive post-search affects the evaluation of gener- alization performance, and 2) prolonged search is impractical for deployment, we test all baselines using a greedy strategy for fair comparison. CaR likewise uses TR = 20 with a greedy strategy, consistent with Table 14. POMO is retrained under the same conditions (epochs and batch size) as CaR. As shown Table 15, CaR achieves a gap of 5.00%, outperforming the best prior neural method MvMoE (Zhou et al., 2024) with the optimality gap: 6.88% showing that CaR's extendability on simple constrained CVRP and good generalization performance.
Table 14: Results on CVRP: best are bolded; best within min / 2min (n 50/100) shaded.
50
100
Method
#Params
Puradigm
Obj.J
Gapl
Time
Obj.J
Gapl
Time
HGS
I
10.334
4.6m
15.504
9.1m
LKH-3
I
10.346
0.115%
9.9m
15,590
0.556%
18.0m
OR-Tools (short)
I
10.540
1.962%
10.4m
16.381
5.652%
20.8m
OR Tools (long)
I
10.418
0.788%
1.7h
15.935
2.751%
3.5h
AM POMO
0,68M
L2C-S
10,590
2.478%
178
16.139
4.098%
1.1m
1.25M
1,20-S
10.424
0.867%
1s
15.741
1.532%
5s
LEHD (groedy)
1.42M
L2C-S
10.861
5.102%
1.2s
16.148
4.154%
InVIT
1.74M
L2C-S
10.827
4.773%
6.3m
16.452
6.117%
9.6m
Poly Net
/
L.C-S
/
/
15.640
0.490%%
5m
POMO-MTL
1.25M
L2C-M
10.437
0.987%
2s
15.790
1.846%
MVMoE
3.68M
L2C-M
10.428
0.896%
3s
15.760
1.653%
10s
ReLD-MoEL
3.68M
L2C-M
10.425
0.866%
3s
15.713
1.354%
9s
POMO-EAS+SGBS (short)
1,25M
L2C-S
10.364
0.293%
15s
15.619
0.744%
1.3m
TOMO+EAS+SGHE (long)
1.25M
L2C-S
10.340
0.056%
6.5m
15.530
0.170%
34m
LEHD (RRC=50)
1.42M
L2C-S
10.419
0.821%
28s
15.674
1.096%
368
LEHD (RRC=500)
1.42M
L2C-S
10.367
0.315%
3.5m
15.581
0.497%
6.5m
UDC (RRC=50)
1,50M
L2C-S
10.722
3.755%
2.8m
16.212
4.567%
9.8m
UDC (RRC=250)
1.50M
L2C-S
10.639
2.953%
12.2m
16.038
3.442%
46m
NeuOpt-GIRE Ik)
0.69M
L21-S
10.411
0.749%
33s
15.809
1.969%
1.4m
NeuOpt-GIRE (T 2k)
0.69M
L21-S
10.377
0.414%
1.1m
15.724
1.417%
2.7m
NeuOpt-GIRE 5k)
0.69M
L21-S
10.355
0.203%
2.8m
15.640
0.878
AM+LCP
L2C-L.21-8
10.520
1.380%
5.2m
2.110%
CaR (Tx
1.64M
L2C-L21-S
10.372
0.360%
4s
15.673
1.085%
CaR (Tx = 10)
1.64M
L2C-12118
10.366
0.305%
7s
15.651
0.943%
14s
CaR (Tw = 20)
1.64M
L2C-L21-S
10.362
0.259%
138
15.642
0.889%
23s
CaR (sumple 4, Tu
1.44M
L2C-L21-S
10.350
0.150%
15.604
0.639%
1.7m
CaR (sample 16, Tg 20)
1.64M
L2C-L21-8
10,344
0.096%
3.6m
15.578
0.476%
6.6m
CaR (Txs 20) + EAS
1.64M
L2C-L21-S
10.341
0.063%
7.8m
15.540
0.230%
25m
CaR (sample Tn 20) EAS
1.64M
L2C-L21-S
10.338
0.034%
31m
15.527
0.148%
1.7h
Due to the unuvailability of the source code, we directly copy their results from original paper for comparison.
E.3 QUANTIFICTTION FOR THE DIVERSITY OF THE CONSTRUCTED INITIAL SOLUTIONS
We now provide a quantitative analysis across a large set of instances. Specifically, we evaluate the average pairwise diversity among the eight constructed solutions for 10,000 instances, comparing
25

---

Published as a conference paper at ICLR 2026
Table 15: Results on CVRPLIB instances. Best results are bolded.
Instance
Opt
POMO
Obi.
(greedy) Gap
RQ-NCO
0bb.
(greedy) Gap
Gap
INVIT (grendy)
Cap
Ob).
LIDC (RRC-2)
Gap
OBl.
MVM (grendy)
Gap
Cal (greedy.
OR1
Gap
Jx=
Xa106-414
26362
49.16%
2522]
7.05%
3.25%
4.75%
25651
3.50%
27278
3,47%
27703
5,09%
X-110kk1
14991
15235
1.68%
15718
4.90%
15252
1358
15720
5.06%
15655
11 1.535
15089
0.79%
15252
1.14%
X 810
12747
16113
26.41%
15265
19.76%
13850
9.48%
13744
7.82%
19056
25.96%
13547
5.638
13997
2.75%
19532
14085
5.65%
15534
16.45%
17831
389%
14363
7.73%
16618
14.57%
14089
5.882
13483
1.15%
X.122 8:3
55539
58313
5.358
62530
13.11%
63475
17.895
50527
7.18%
01745
17.17%
52444
0.138
579577
4.3%%
X-122--188
20346
1.06%
30100
4018
7.25%
32305
20003
Xa11944.00
13950
14035
3.27%
9.22%
14059
12.5%%
13825
X-n14547
15780
16131
2.75%
17605
11.41%
17900
14
12004
K.60%
18755
16
16125
1001
X 246
43448
45328
13.53%
47615
10.05%
60384
35.055 3.05%
45342
4,30%
50157
15.46%
46738
7.625
44643
2.6%
X-1814222
21220
12476
28481
5472%
20559
050 011%
1966
11:505
26671
36.74%
21703
12.115
21250
0.66%
X k13
16876
17650
4.65%
19435
12023
222
17571
5-225
15419
9.145
17650
4,5%%
17720
500%
Xa162-111
14899
5-31/
1102
17581
14654
14580
20557
6.15%
13215
2124
2000
250
21205
Xa173451
40556
40525
55915
18 18.225%
51202
4.77%
X-176--20 k:0
47612
54197
15.39g
57641
30.5%
60711
17035
488%
59171
24. 14.19%
55520
51911
5.70%
X438
25569
37311
45.02%
37002
5.80%
15037
1.44%
17676
8334
28958
13.29%
26256
2.69%
36530
3.766
X
24145
25772
4.46%
25419
0.671
2507
35534
5,545
79953
34 10%
25182
4.29%
34710
2.34%
X ks
16900
18315
7.56%
18629
9.71%
17899
5.46%
1906
5,37%
19756
16.35%
19327
7.93%
18203
7,20%
49158
11
54266
23.75%
51067
0.71%
55152
1471%
49964
13.0%
46K19
591%
X
10.31%
12.13%
64585
61570
5.02%
63398
61530
5.4%
62754
32212
373%
Na219
117595
131545
13.50%
9.10%
135K34
15.5%%
120070
2.36%
128751
9.49%
121046
134143
14.0%%
X-224423
25742
45689
$9.14%
$1668
23.02%
29451
14.41%
27581
K319
31425
22.00%
31054
23,645
27773
7.9%%
41137-214
271MB
75891
10.58%
2797%
3.46%
24140
12.0%%
35192
30.14%
25550
3,58
2892
0.9%
X-227-3.0
37274
56167
30 69.
47644
27.82%
54017
44.926
42545
14.15%
45746
22.75%
43673
17.17%
42408
13.7%%
X-1381423
S1694
4036
4.08%
40648
4.56%
9900
2.37%
41547
7.40%
43777
11 199
41003
0.04%
43406
4.4%%
Arerage
31280
16,63%
13.20%
35M92
12.27%
7,006
36399
33549
33283
5.00%
CaR (trained with diversity loss) and PIP (without diversity loss). For each instance, we calculate the following diversity metries across solution pairs (higher values indicate greater diversity): 1) Hamming Distance (HD), which measures how many positions differ between two solutions, 2) Positional Jaccard Distance (PJD), which measures the proportion of overlapping node positions across all permutations, and 3) Kendall's Tau Distance (KTD), which measures how many node pairs (i.e., edges) have different relative orderings. As shown in Table 16, CaR's s diversity sampling strategy significantly improves the diversity of the constructed solutions compared to the So'AA constructive baseline (PIP), across multiple diversity metrics.
Table 16: Diversity comparison between PIP and CaR constructed solutions.
HD 1
PJD 1
KTD 1
PIP's constructed solutions
0.666 + 0.837
0.013 + 0.017
0.713 # 0.938
CaR's 's constructed solutions
0.770 0.893
0.015 = 0.018
0.821 0.997
CaR's diversity improvement over PIP
+15.6%
+15.6%
+ +15.1%
E.4 DISCUSSION OF SHARED REPRESENTATION
Recall that CaR employs a unified encoder shared across the construction and refinement decoders. As demonstrated in Table 8, this architecture significantly enhances performance. To further assess the impact of the unified encoder under varying constraint complexities, we present comprehensive results in Table 17 for Medium TSPTW-50, Hard TSPTW-50, and Medium 10P.W-100. Results indicate that as problem complexity increases, evidenced by higher infeasibility rates (e.g.. 37.270% in Hard TSPTW-50) and greater optimality gaps (e.g., 10.931% % in TSPTW-100) the performance improvements attributed to the unified encoder become more pronounced. This suggests that shared representations facilitate better generalization and constraint handling in more challenging scenarios.
Table 17: Effects of unified encoder on TSPTW.
TSPTW-50 Medium
TSPTW-50 Hard
TSPTW-100 Medium
Method
Infsb% J
Gap
Infsb %
Gapl
Infsh 1
Gap!
Construction-only
3.77%
5.230%
37.27%
1.635%
0.12%
10.931%
w/o Shared Rep.
0.01%
2.047%
0.68%
0.199%
0.00%
7.589%
Shared Rep.
0.00%
2.173%
0.01% %
0.014%
0.00 %
5.815%
26

---

Published as a conference paper at ICLR 2026
Table 18: Model parameters and performance of different unifications on TSPTW-50 Hard. / indi- cates shared representation.
Unified Separic Drcada (Cune)
0. Lo!
Encoder
Decoder
#Params
Infsh %+
Gapl
2.8M
0.68%
0.199%
V
1.4M
0.01 %
0.041%
1.6
0.01 %
0.014%
Figure 8: Effects of separate decoder.
We further evaluate this design on CVRPBLTW-100, where using separate encoders reduces the optimality gap slightly but increases model parameters by 1.7x compared to the unified encoder version of CaR (2.9M vs. 1.7M). To balance performance and computational efficiency, we advocate for the unified encoder design.
Moreover, we explore the unification of the encoder and decoder components. As shown in Table 18 and Figure 8, results TSPTW-50 indicate that employing a separate decoder increases the number of model parameters by 1.1x, yet it further reduces the optimality gap. Therefore, this paper adopts an architecture with unified encoder and separate decoders for each module.
We also examine the effect significance of shared representation compared to another learning component, i.e., the supervised loss. Results show that shared representation is mostly critical. Across all settings (regardless of the construction used, which is different from what we observe in the impact of the supervised loss), the shared representation plays the dominant role. It enables the necessary information synergy. allowing the refinement module to leverage structural context from the construction phase repair constraints effectively.
Table 19: Comparison of different backbones with shared encoder and supervised loss.
Backbones
Shared Rep.
Ls.
Gap J
Infsb
POMO (Construction-only)
1.959%
CaR. *OMO
0.136%
0.29%
CaR-POMO*
0.199
0.68%
CaR POMO* (Ours)
PIP (Construction-only
0.177%
2.67%
CaR-PIP
x
x
0.156%
1,85%
0.175%
CaR-PIP
0.006%
0.01%
CaR PIP (Ours)
0.005 %
0.00 %
E.5 DISCUSSION OF THE SHORT-HORIZON DESIGN
To further validate CaR's ss short-horizon design, we further retrain NeuOpt* by gradually decreasing the training horizon of NeuOpt and evaluate performance under inference budgets: (1) T,est 20 (same as CaR), and (2) T,est = 1,000, which reflects the refinement length typically required by neural improvement solvers. Results in Table 20 show that NeuOpt* cannot produce any feasible solutions under limited T,est, regardless of whether its training horizon is short or long, while CaR achieves strong performance, with an optimality gap of 0.005% and 0% infeasibility within just 20 steps of refinement. This discrepancy arises because NeuOpt is inherently unsuitable for short-horizon refinement. Even when retrained with our designed constraint-related features and constraint-aware penalty function in the MDP formulation, NeuOpt relies on long rollouts to gradually correct constraint violations and improve performance. In contrast, CaR specifically designed to enable rapid feasibility refinement and solution improvement within tight step budgets. is nontrivial and architecturally distinct from
This highlights that short-houe horizon standard improvement-only methods.
27

---

Published as a conference paper at ICLR 2026
Table 20: Performance of NeuOpt* with different short-horizon settings during training.
Method
Tinin
Tisst
Gap
Infsb
5 as CaR)
20
100%
10
20
100%
NeuOpt*
20
20
100%
100
20
100%
200 (original NeuOpt)
20
100%
5 (same as CaR)
100
100%
10
100
1.314%
99. 79%
NeuOpt*
20
100
0.397%
7.36%
100
100
145%
0.22%
200 (original NeuOpt)
100
0.061 %
0.19%
CaR
5
20
0.005%
0.00%
E.6 ADDITIONAL RESULTS PATTERN OF CAR's REFINEMENT
During inference, we follow (Kwon et al., 2020) to augment each instance 8x, generating eight initial solutions for refinement. All eight trajectories on TSPTW instance are presented Figure 9to illustrate the diversity in initial solutions and their subsequent refinement. Moreover, to better understand how CaR refines solutions for feasibility and optimality, we also visualize the objective trajectories on other randomly generated TSPTW-50 instances in Figure 10. CaR dynamically navigates both feasible and infeasible regions, adjusting its focus based on the current solution state. For example, in the instance of Figure 10 (d), CaR begins with a near-leasible solution (1 0), achieves feasibility in one step (r = 1), explores infeasible regions (r 2 12), and ultimately improves optimality (r 13). In contrast, in the instance of Figure 10 (c). the construction already yields a feasible, high-quality solution, and refinement continues to enhance optimality efficiently. These patterns illustrate CaR's ability to balance feasibility and optimality by exploring both feasible and infeasible spaces. By comparison, NeuOpt fails to escape infeasible regions within limited steps, highlighting CaR's advantage constraint-awarg refinement.
27.5
27.0
27.0
27.0
27.0
26.5
26.5
26.5
26.5
15
20
10
20
10
20
10
15
20
(a)
(b)
(c)
(d)
27.3
27.0
27.0
27.0
27.0
26.5
26.0
26.0
26.0
26.0
15
Itaration
Itaration
Iteratioo
Iteration
(c)
(f)
(h)
Figure 9: CaR's refinement and infeasible solutions, respectively. Green dashed lines mark the best-so-fal feasible objective; the red line indicates the best objective with data augmentation. CaR's refinement process is shown over time, with = 0 representing the initially constructed solution.
TSPTW instance. Green dots and red crosses denote the feasible
E.7 EFFECTS OF DIFFERENT NUMBERS OF INTTIAL SOLUTIONS
Our CaR framework first samples S solutions per instance during construction, then selects solutions for refinement over TR steps. As shown in Figure 11, reducing p from 10 to 5 TSPTW-50 increases both infeasibility and optimality gap. In contrast, further increasing it from 10 to 20 slightly enhance the performance (the optimality gap reducing from 0.014% to 0.007%, and the infeasibilityy reducing from 0.01% % to 0.00%). This finding indicates that larger p yields better final performance, but the gains become increasingly marginal p grows. Since p is constrained only by GPU memory (we
28

---

Published as a conference paper at ICLR 2026
Call
22,00
27.00
Bad-sooffr (CaR)
26.00
25.50
25.75
26.00
28.68
20.00
25.25
10
10
15
10
15
20
10
15
26
(a)
(b)
(c)
(d)
30.00
27.80
Bast-eo-far (NeuOpt)
POWO-
223.00
25.00
23.00
28.00
24.00
22.00
24.00
Iteration
Ieertton
Iteratioo
Iteration
(e)
(h)
Figure 10: Refinement efficiency of CaR (top) and NeuOpt (bottom) typical TSPTW-50 instances.
single Nvidia RTX 4090), select the largest feasible p in practice (i.e., p=10). Nonetheless, even with smaller p. CaR consistently outperforms the state-of-thearrt neural solver PIP (Bi et al., 2024), as well classic heuristics, including LKH-3 with limited trials (100), ORTools, and greedy heuristics.
E.8 HYPERPARAMTER EXPERIMENTS
We initially set hyperparameters without extensive tuning, focusing on validating the framework design. To assess their effects,
Table 21: Hyperparameter sensitivity.
CaR-POMO* on TSPTW-50. (1) For diversity loss (, set at 0.01 to avoid dominating gradients, removing degrades performance while larger values (e.g.. 0.1) also harm learning. (2) For supervised loss (a22), set at larger weights (c.g.. 2) reduce performance by overem- phasizing supervision. Overall, results show that CaR is robust to hyperparameters, and improvements reflect the framework's inherent strength rather than aggressive tuning.
Hyperparameters
Gap
Infsb %
an
0.421%
di 0.01 (Ours)
0.014%
0.01%
0.1
1.483%
32.68%
0.136%
0.29%
I (Ours)
0.014%
0.01 %
1.63%
32.12%
E.9 SENSITVVITY
STATISTICAL SIGNIFICANCE
Sensitivity to random seeds. To assess the robustness of CaR, evaluate its performance under five different random seeds, i.c., 2023, 2024, 2025, 2026 and 2027, during inference. As shown in Table 22, the standard deviations are small, indicating that CaR's ss performance stable with respect to random initialization. Note that we use 2023 as the default random seed for inference across all baselines to ensure consistency performance comparison, following (Zhou al., 2024).
0.4
lc-5
p p= 5
Percentage (%)
0.3
p 10 (ours)
0.2
0.1
-1
0.0
Gap
Infsb%
NeuOpt
CaR-POMO
CaR-PIP
Figure 11: Effects p.
Figure 12: Boxplot of diverse methods on TSPTW-50.
29

---

Published as a conference paper at ICLR 2026
Table 22: Standard deviation of the results in Table under five different random seeds.
n=
n= 100
Problem
Method
Gap 1
Infsb 1
Gap
Infsh %
TSPTW
CaR-POMO (7x = 20)
0.016%
0.000%
0.01% a 0.00%
0.401
0.002%
2.33%
0.02%
CaR-PIP 20)
0.005%
0.000%
0.00%
0.01%
0.158%
0.001%
0.64%
0.06%
CaR (p: (7x 20)
2.166%
0.025%
0.00%
0.00%
-1.997 + 0.00668
0.00/ 0.00%
CVRPBLTW
CaR (R&R) (7A. 20)
0..54% 0.012%
0.00% a: 0.00%
-2.473% = 0.015%
0.00% 0.00%
Statistical significance. Figure 12 illustrates the distribution of optimality gaps for NeuOpt, CaR- POMO, and CaR-PIP, corresponding to the results on TSPTW550 in Table 2. We additionally conduct significance tests, revealing that all pairwise differences are statistically significant (p < 0.001). This suggest that CaR delivers significant performance improvement over the representative baselines.
E.10 DISCUSSION ON THEORETICAL ANALYSIS
While our primary contribution empirical, we acknowledge the importance of establishing strong theoretical foundations for NCO. In this section, we outline promising directions for analyzing the learnability, convergence, and generalization bounds of the proposed CaR framework. 1) Learn- ability: Since CaR jointly trains construction module (policy xe) and a refinement module (policy T&) with a shared encoder, a key theoretical question concerns the sample complexity or PAC-style learnability of this joint policy class. Specifically, future work could investigate how many training instances are required for the learned xe and to yield solutions within of the optimal cost with constraint-violation probability I (with high probability). Such analyses could leverage established results policy gradient sample complexity Yuan al. (2022). 2) Convergence: CaR employs entropy-regularized policy gradients (to encourage diversity) within a short-horizon refinement pro- cess. Consequently, convergence analysis could draw upon existing literature regarding smooth policy gradient methods Agarwal et al. (2021) and two-stage or bilevel RL optimization Thoma et al. (2024). These frameworks may help characterize the conditions under which joint updates the shared encoder converge to a stationary point. 3) Generalization Bounds: The generalization behavior of CaR can be examined from multiple perspectives. One direction follows recent NCO generalization analyses, studying how learned policy transfers across diverse settings (c.g.. varying instance sizes, distributions, or constraint patterns). Alternatively, from the perspective of RL generalization theory, one could derive the gap between empirical and expected performance.
bounds Duan et al. (2021) to formally characterize
THE USE OF LARGE LANGUAGE MODELS (LLMs)
In accordance with ICLR policy, we disclose that LLMs were used solely to polish the writing and improve readability. LLMs were not involved in research ideation, experimental design, or any part of the scientific contributions of this work.
30


Reviews:
[{"review_id": "KmFk9TnXjn", "reviewer": "Reviewer_wzGX", "summary": "This paper presents Construct-and-Refine (CaR), a neural framework for efficiently handling hard constraints in vehicle routing problems (VRPs). By integrating construction and refinement paradigms via joint training and shared representations, CaR achieves significant improvements in feasibility, solution quality, and computational efficiency. The method demonstrates strong performance across diverse constrained VRP variants, outperforming both classical and neural baselines while maintaining minimal inference overhead.", "questions": "1.\tHow does CaR achieve effective refinement in just 10 steps, while prior learn-to-improve methods require thousands? Is this solely due to the short-horizon design, or does the joint training framework play a critical role?\n\n2.\tWhy are TSPDL results omitted from the main experiments? Additionally, Appendix results for TSPDL100 are missing. Could the authors clarify this gap?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tThe paper is highly mature, with extensive experiments covering multiple VRP variants (TSPTW, CVRPBLTW, CVRP, TSPDL), scales, and constraint settings. The implementation details are thorough, including hyperparameters, baseline adaptations, and reproducibility measures.\n\n2.\tThe paper provides detailed ablations validating key components, e.g., joint training, diversity loss, shared representations, and their individual impacts on performance. These analyses offer valuable insights into understanding the framework.", "weaknesses": "The technical contribution of this paper is limited. Although it addresses important constrained problems, CaR primarily adapts the existing construct-and-refine framework (e.g., NCS) to constrained domains. The shared representation and lightweight refinement design are incremental and do not introduce fundamentally novel ideas.", "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": "EVlSeJ2mwD", "reviewer": "Reviewer_iA9w", "summary": "This paper addresses the challenge of applying neural combinatorial optimization (NCO) solvers to VRPs with complex constraints. The authors introduce \"Construct-and-Refine\" (CaR), a hybrid framework that jointly trains a construction and refinement module. The construction module is trained to produce diverse and high-quality solutions. These are then fed to a refinement module that operates for a short horizon to rapidly find feasible, high-quality solutions. Experiments on hard-constrained VRPs (TSPTW, CVRPBLTW) and others (CVRP, TSPDL) show that CaR can achieve state-of-the-art feasibility and solution quality.", "questions": "(1) Can the authors more clearly distinguish the conceptual difference between CaR's joint training and that of NCS? Both seem to jointly train a constructor and improver with a shared component.\n\n(2) Could the authors provide results for CaR compared against NeuOpt-GIRE (or another SOTA improvement solver)  that is re-trained to optimize its performance for a short rollout?\n\n(3) Why was the ablation in Table 5 compared against a \"Random\" constructor? Could the authors provide results for CaR compared with a jointly trained constructor and improver with a separate encoder and the same model, but not use the $L_{SL}$ loss during training?\n\n(4) How sensitive is the framework to the choice of p (top-p solutions)?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "(1) The paper is well-written and clearly structured. \n\n(2) The paper tackles a critical problem. The failure of NCO solvers to handle complex constraints is arguably the barrier to their practical adoption. \n\n(3) The experimental evaluation is comprehensive, demonstrating strong results on different VRPs with hard constraints.", "weaknesses": "(1) This paper proposes CaR to efficiently handle complex constraints in VRPs and subsequently produce high-quality solutions. However, the core contribution appears to combine PIP and existing hybrid methods (LCP and NCS) for solving hard-constrained VRPs.\n\n(2) The idea of combining construction and improvement is not new. NCS also employs a joint training paradigm with a shared component. The distinction of the joint training paradigm is not strong. \n\n(3) What is the fundamental difference between the approach used in this paper for handling constraints and the essence of PIP?\n\n(4) The ablation study of the effectiveness of the joint training is unconvincing. A much stronger ablation would be jointly training PIP + NeuOpt, but with separate encoders and without the $L_{SL}$ feedback loss, and compare with (1) add the $L_{SL}$ loss, (2) add the  shared encoder\n\n(5) The arguments in this paper \"In CVRPBLTW, for instance, strict masking filters out more than 60% of nodes, severely limiting the search space (Figure 6) and hindering RL convergence.\" Why does limiting the model search space hinder RL convergence?", "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": "NlsbAQlMf5", "reviewer": "Reviewer_8D1i", "summary": "This paper proposes a neural combinatorial optimization (NCO) solver for vehicle routing problems (VRPs) with hard constraints.\nExisting NCO approaches can be categorized into (1) construction solvers that sequentially build solutions, (2) improvement solvers that iteratively refine them, and (3) hybrid methods that combine both.\nHowever, these approaches struggle to effectively handle hard constraints such as time windows or multiple interdependent resource limits.\nTo address this issue, the authors introduce a new framework called Construct-and-Refine (CaR), which explicitly refine a constructed solution to recover feasibility.\nCaR jointly trains construction and refinement modules with a shared encoder, enabling fast and effective recovery of feasibility while maintaining solution quality.\nExperiments on several constrained VRP variants (TSPTW, CVRPBLTW) demonstrate that CaR achieves superior feasibility, optimality, and computational efficiency compared to both classical heuristics and recent neural baselines.", "questions": "- The first question is how CaR could be analyzed from a theoretical standpoint (possibly as a future work). Possible directions include learnability, convergence, or generalization bound.\n- The second question is about applicability of the proposed method. It appears general and could be extended to other structured optimization domains where constraint handling is non-trivial, such as scheduling problems or SAT.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- This paper is well-motivated. It addresses a fundamental challenge in neural combinatorial optimization (NCO) — effectively satisfying hard constraints such as time windows constraints. This limitation has been a core weakness of existing NCO solvers, and this paper clearly explains the importance of effectively handling such constraints.\n- The proposed approach is conceptually sound. Introducing an explicit feasibility refinement module to recover infeasible solutions is a natural and intuitive. \n- Though the proposed approach is simple, it works well in practice. Experiments demonstrate that it consistently finds feasible solutions more reliably than other NCO solvers and classical heuristics on hard-constrained routing problems such as TSPTW and CVRPBLTW, while also achieving higher solution quality. The experimental evaluation is comprehensive, covering multiple benchmarks, ablation studies, and generalization tests that convincingly support the method’s effectiveness.", "weaknesses": "While the paper’s empirical contributions are strong, there is no theoretical discussion of why the joint learning of construction and refinement works well. In particular, questions regarding learnability, convergence, or generalization bound of the proposed method remain open. Formal analysis would strengthen the work’s long-term impact.", "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": "VRfH2h4rjo", "reviewer": "Reviewer_FEWD", "summary": "This paper proposes Construct-and-Refine (CaR), a framework designed to improve constraint satisfaction in neural combinatorial optimization solvers. Existing constraint-handling approaches can be broadly categorized into feasibility masking and feasibility awareness, but both tend to struggle with hard-to-satisfy constraints.\nThe proposed framework introduces two decoders: one for constructing an initial feasible solution and another for refining it iteratively. The authors evaluate CaR on TSPTW and CVRPLTW, demonstrating that it achieves higher constraint satisfaction rates for difficult instances and better objective values for larger-scale problems compared to existing methods.", "questions": "- What types of constraints are better handled by existing constraint-handling methods, and which types particularly benefit from the proposed CaR framework?\n\n- What characteristics must existing methods, such as POMO, have in order to integrate with CaR?\n\n- In what situations does the proposed method fail to find a constraint-satisfying solution? Are there any common patterns or characteristics in such cases?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The proposed framework achieves superior constraint satisfaction and objective performance across multiple constraint types, demonstrating that the construct-and-refine approach can lead to more effective constraint handling.\n\n- The paper includes a well-designed ablation study that helps clarify which components of the framework contribute most to performance improvements.", "weaknesses": "- The range of constraints for which the proposed framework is effective remains unclear. For example, constraints such as time-window or route-length can often be relaxed smoothly, but it is not evident whether CaR is equally effective for non-continuous or discrete constraints, such as precedence or ordering constraints.", "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 (Poster)