acceptodds
Under review as a conference paper at ICLR 2027

Alternating Exploration and Repair via Split Search for Hard-Constrained Routing

Abstract

Hard-constrained routing seeks low-cost routes that satisfy operational restrictions, but reducing travel cost can conflict with restoring feasibility. We introduce ALTER, a neural solver that repeatedly alternates cost-oriented exploration and feasibility-oriented repair. Each selected route serves as the reference for the other role's next proposals. Accumulated disagreement carries their interaction across iterations, while a learned state-dependent coupling strength controls how strongly the two searches are coordinated. Our analysis characterizes coupling intervals under which finite-pool selection yields a feasible cost improvement. Experiments cover synthetic single- and multi-vehicle routing. On hard 100-customer draft-limit instances, ALTER produces a feasible output for 99.97% of instances and obtains the lowest gap among tested neural methods. It also obtains the lowest reported costs on the multi-vehicle benchmark.

Primary area:
optimization
Keywords:
Vehicle routing problem, reinforcement learning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_QzwZOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces ALTER, a neural solver for hard-constrained routing that repeatedly alternates cost-oriented exploration and feasibility-oriented repair, coordinated through accumulated disagreement and learned state-dependent coupling. The paper characterizes coupling intervals for feasible cost improvement with finite candidate pools and evaluates ALTER on TSPTW, TSPDL, and CVRPBLTW.

Critical strengths
  1. The split between cost-oriented exploration and feasibility-oriented repair is intuitive.
  2. The coupling-interval analysis is helpful for explaining how the two roles interact.
  3. The results on TSPDL Hard and CVRPBLTW are impressive.
Critical weaknesses
  1. On TSPTW Hard, ALTER has a higher instance infeasibility and longer runtime than LMask [1]. Although the authors acknowledged it, the paper still lacks sufficient analysis of the reasons for this disadvantage.
  2. Native inference configurations and method-specific successful-instance subsets make the reported cost improvements harder to judge.
  3. The ablation study does not isolate the contribution of disagreement memory, leaving its independent benefit unclear.
Questions for authors
  1. Do the reported advantages over LMask [1] and CaR [2] persist under matched time budgets? Please also report gaps in the subset of instances solved successfully by all three methods.
  2. How much does disagreement memory contribute when all other components are kept unchanged?
  3. How does adaptive penalty control compare with a tuned fixed penalty, beyond the reported fixed consensus setting of ρ=1\rho=1?

References:

[1] Li, Tianyou, et al. LMask: Learn to solve constrained routing problems with lazy masking. ICLR 2026.

[2] Bi, Jieyi, et al. Towards efficient constraint handling in neural solvers for routing problems. ICLR 2026.

8 comments
AuthorsOpenReview ↗

Response to QzwZ — W1: Feasibility and runtime on TSPTW Hard

TSPTW Hard has a visit-order structure that LMask can exploit directly during route construction. Its generator first samples a random tour and then constructs each customer's time window around its arrival time on that tour, whereas Medium samples time windows independently [1]. Our TSPTW-50 diagnostic shows that two-step look-ahead leaves an average of 1.14 next-node choices on Hard, compared with 4.51 on Medium, when evaluated along reference-route prefixes. This indicates substantially tighter restrictions on the next visit in Hard.

LMask applies these restrictions before selecting the next customer: if visiting a customer would make another unvisited customer miss its deadline, two-step look-ahead excludes that choice. Backtracking then revises earlier choices when construction reaches a dead end [1]. This allows LMask to use the order information encoded in the time windows explicitly throughout construction.

ALTER's feasibility is handled through learned route generation, candidate scoring and selection, and iterative repair. Recovering the tightly constrained visiting order therefore relies on its learned policies and successive repair steps. This makes LMask particularly well matched to the ordering structure of TSPTW Hard and helps explain its higher feasibility on this distribution.

References

[1] Li, Tianyou, et al. LMask: Learn to solve constrained routing problems with lazy masking. ICLR 2026.

AuthorsOpenReview ↗

Response to QzwZ — W2 & Q1: Matched inference-time budgets and common solved subset

For the comparison under matched inference-time budgets, please see our response to Reviewer 2 (W2 & Q2). ALTER achieves the lowest gap in five of the six TSPTW/TSPDL settings.

Table vii shows the gap over the instances on which all compared methods return a feasible route. ALTER achieves the lowest gap in seven of the eight problems.

Table vii. Average gap (%) on the common instances for which all compared methods return feasible routes.

SettingCommon instancesALTERLMaskCaR
TSPTW-50 Medium9,9991.581.682.61
TSPTW-100 Medium10,0003.043.928.97
TSPTW-50 Hard9,9780.130.100.02
TSPTW-100 Hard7,6860.150.210.76
TSPDL-50 Hard9,9451.322.216.39
TSPDL-100 Hard9,6032.764.1810.31
CVRPBLTW-50974−2.19-2.19–2.12
CVRPBLTW-100969−5.36-5.36–−1.79-1.79
AuthorsOpenReview ↗

Response to QzwZ — W3 & Q2: Independent contribution of disagreement memory

We evaluate the contribution of disagreement memory by disabling it at inference while retaining both search roles and adaptive penalty control. Table viii compares the two configurations on the four TSPTW/TSPDL Hard settings.

Table viii. Memory ablation with adaptive penalty control. Entries are solution infeasibility (%) / instance infeasibility (%) / gap (%).

SettingWithout memoryWith memory
TSPTW-50 Hard2.17 / 0.27 / 0.1321.83 / 0.21 / 0.126
TSPTW-100 Hard27.69 / 8.48 / 0.15619.14 / 5.02 / 0.160
TSPDL-50 Hard0.13 / 0.00 / 1.3960.14 / 0.00 / 1.323
TSPDL-100 Hard0.21 / 0.03 / 2.7790.24 / 0.03 / 2.755

On TSPTW-50 Hard, memory improves all three reported metrics. On TSPTW-100 Hard, it reduces instance infeasibility from 8.48% to 5.02%, yielding 346 more solved instances overall out of 10,000 and a 40.8% reduction in failed instances. On TSPDL-50 Hard, both variants solve all 10,000 instances, and memory reduces the gap from 1.396% to 1.323%. These results demonstrate the contribution of disagreement memory to feasibility recovery and route quality within the full adaptive solver.

Reviewer_AmtwOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes ALTER, which is a neural solver designed for hard constrained routing problems. It alternates cost-oriented exploration and feasibility oriented repair. Numerical experiments shows that ALTER reduced the feasibility rate compared to other neural solver such as POMO.

Critical strengths

Concept of ALTER that combines cost-oriented update and repair-oriented update while adaptive rho produced by neural network, which is clear.

ALTER works better in terms both of speed and quality than state-of-the-art search and repair solver CaR.

Ablation study is efficiently conducted.

Critical weaknesses

ψ is shown in Table 3, but its definition is not found.

Even ALTER works better than CaR, but it needs much more computational time than masking-based feasibility control method.

Proposed method’s scalability is not shown effectively because the number of nodes are at most 100.

Discussion of training cost compared to baselines is not enough.

Questions for authors

What is the definition of ψ in Table3?

Is it possible to compare to masking-based feasibility control methods in terms of the solution quality given same computational time?

Is it possible to extend ALTER that can detect infeasible instance?

While proposed method seems not to be restricted to routing problem, why do authors focus only for routing problem and why not aim to other hard-constrained optimization problem?

8 comments
AuthorsOpenReview ↗

Response to Amtw — W1 & Q1: Definition of ψ (Table 3 in the main text)

We clarify that the ψ\psi column in Table 3 in the main text indicates whether the adaptive penalty controller is enabled. The caption of Table 3 in the main text identifies ψ\psi as adaptive penalty control, and, as introduced in the main text, ψ\psi represents the parameters of the penalty controller pψp_\psi. Accordingly, the ψ\psi column indicates whether that controller is enabled.

AuthorsOpenReview ↗

Response to Amtw — W2 & Q2: Solution quality under matched inference-time budgets

Under matched inference-time budgets, ALTER achieves the lowest gap in five of the six TSPTW/TSPDL settings using the native setting from the main paper (Table iv).

For LMask, we vary the backtracking limit R (max_backtrack_steps). When construction reaches a dead end, LazyMask backtracks, updates the mask, and tries another choice; a larger R gives this search more backtracking steps. This directly follows LMask's own inference-budget experiment, which scales R to evaluate the feasibility-runtime trade-off [1].

For CaR, we vary the refinement horizon T (validation_improve_steps), which controls the number of refinement steps after construction. CaR is designed around short-horizon refinement; its own short-horizon study uses a 20-step inference setting [2]. Increasing T gives its refinement policy more opportunities to repair violations and improve route quality. These are the natural budget controls for this comparison because they directly scale the search operations central to each method.

The table uses LMask R=2000 for TSPTW-50 Medium and TSPDL-100 Hard, R=1000 for TSPDL-50 Hard, and R=10000 for the remaining TSPTW settings; CaR uses T=5 in all six settings. The full curves cover backtracking budgets up to R=10000 and refinement horizons up to T=20.

Table iv. Matched inference-time comparison. Entries are instance infeasibility (%) / gap (%) / time (s) for all 10,000 instances. Gaps use each method's solved instances; the lowest gap in each row is bold. * marks LMask at R=10000, where all candidates finish before reaching the backtracking limit.

SettingALTERLMaskCaR
TSPTW-50 Medium0.00 / 1.572 / 18.20.00 / 1.678 / 20.30.00 / 4.465 / 15.9
TSPTW-100 Medium0.00 / 3.049 / 48.90.00 / 3.915 / 29.6*0.00 / 12.862 / 40.8
TSPTW-50 Hard0.23 / 0.125 / 20.70.00 / 0.095 / 5.1*0.01 / 0.033 / 15.5
TSPTW-100 Hard4.84 / 0.158 / 49.20.00 / 0.203 / 19.0*21.62 / 0.777 / 41.2
TSPDL-50 Hard0.00 / 1.324 / 18.20.03 / 2.208 / 21.10.57 / 7.557 / 15.5
TSPDL-100 Hard0.02 / 2.766 / 49.10.12 / 4.160 / 44.33.92 / 10.282 / 40.1

On TSPDL-50 Hard, ALTER achieves a 1.324% gap in 18.2 seconds, compared with LMask's 2.208% in 21.1 seconds. On TSPDL-100 Hard, the comparison is 2.766% in 49.1 seconds versus 4.160% in 44.3 seconds. These correspond to 40.0% and 33.5% lower gaps. ALTER also has lower instance infeasibility than both baselines at both sizes.

We extend LMask's backtracking allowance to R=10000 on TSPTW-100 Medium and both TSPTW Hard settings. All candidates finish before reaching this limit, and the gaps remain 3.915%, 0.095%, and 0.203%, respectively, with zero instance infeasibility. Thus, the extended backtracking budget yields the same solution quality on these settings.

CaR has the lowest gap on TSPTW-50 Hard. On TSPTW-100 Hard, instance infeasibility is 4.84% for ALTER, 0.00% for LMask, and 21.62% for CaR. Figure 14 (bottom) in Appendix I reports both gap and infeasibility for TSPTW-100 Hard. The full time–quality curves are reported in Figure 4 in the main text and Figures 12–14 in Appendix I.

Even with larger baseline budgets on TSPDL-100, LMask reaches 4.159% in 93.8 seconds, and CaR reaches 10.306% in 148.2 seconds. ALTER achieves 2.766% in 49.1 seconds: a lower gap in about half of LMask's runtime and one third of CaR's.

References

[1] Li, Tianyou, et al. LMask: Learn to solve constrained routing problems with lazy masking. ICLR 2026.

[2] Bi, Jieyi, et al. Towards efficient constraint handling in neural solvers for routing problems. ICLR 2026.

AuthorsOpenReview ↗

Response to Amtw — W3: Scalability to larger instances

We respectfully clarify that our evaluation extends beyond 100-node instances. As presented in Table 4 in the main text, we also report results on CVRPBLTW-200 using models trained on 100-node instances, without retraining. ALTER achieves 0.00% instance infeasibility and a −7.86% gap relative to OR-Tools in 5.5 seconds.

Evaluation on 200-node instances after training on smaller instances is an established practice in neural routing, including in the papers introducing our baselines. CaR [2] reports CVRPBLTW-100-to-200 transfer, and ReLD [3] evaluates on CVRP200 after training on 40–100-node instances. DACT [4] and SGBS [5] also evaluate 100-node models on 200-node instances. Our choice of evaluation scale follows these precedents.

References

[2] Bi, Jieyi, et al. Towards efficient constraint handling in neural solvers for routing problems. ICLR 2026.

[3] Huang, Ziwei, et al. Rethinking Light Decoder-based Solvers for Vehicle Routing Problems. ICLR 2025.

[4] Ma, Yining, et al. Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer. NeurIPS 2021.

[5] Choo, Jinho, et al. Simulation-guided Beam Search for Neural Combinatorial Optimization. NeurIPS 2022.

Reviewer_jr5AOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a neural search method for routing problems with hard constraints. Specifically, it alternates between a role that focuses on reducing route cost and a role that focuses on repairing constraint violations. Each selected route becomes the reference for the next role. A memory of past disagreement and a learned, state-dependent coupling strength coordinate the two searches. The paper also gives conditions under which selection from fixed candidate pools yields a better feasible route. Experiments cover synthetic single- and multi-vehicle routing problems with time-window, draft-limit, and other operational constraints, reporting gains in feasibility and solution quality in several settings.

Critical strengths
  1. The proposed method is well-established and theoritical analysis provides conditions for guaranteed improvement.
  2. The empirical gains across the strong baselines CaR and LMask are notable.
  3. The figure 1 is easy-to-understand and clearly presents the methodolofy design.
Critical weaknesses

The idea of alternating descend is interesting. The authors are trying to combine a well-known dual optimization method with neural search paradigm. My main concern is that, under the alternating framework, the neural policy/operation may not be the necessary component for good performance. In other words, replacing neural components with strong heuristic operators (e.g., k-opt) can also yield superior empirical gains. Therefore, I believe the necessity of the ``neual seach" should be justified.

Questions for authors

Is there any real-word benchmark for TSPTW and TSPDL? Why are only synthetic instances included for comparison?

4 comments
AuthorsOpenReview ↗

Response to jr5A — W1: Role of neural policies versus heuristic operators

Our initial experiments explored heuristic proposals within the alternating exploration–repair framework, including k-opt and ruin-and-recreate (R&R). We gave these heuristics substantially larger search budgets than the learning-based configuration (Table i).

k-opt fails to find feasible solutions on 96.33–100% of TSPTW/TSPDL instances. R&R achieves near-complete feasibility on TSPTW Medium and CVRPBLTW, but its gaps remain higher than ALTER's (e.g., −1.697% versus −5.37% on CVRPBLTW-100). Its small TSPTW Hard gaps cover only the few solved instances, with 86.82–98.34% infeasibility. On TSPDL Hard, it still fails on 35.17–36.30% of instances and reports gaps of 7.723–26.992%.

Table i. Comparison of heuristic operators and ALTER. Gap is averaged over each method's solved instances; — indicates no feasible solution. k-opt uses 3-opt for TSPTW/TSPDL and 2-opt* for CVRPBLTW. Entries are infeasibility (%) / gap (%) / time.

Settingk-optR&RALTER
TSPTW-50 Medium96.33 / 11.328 / 5.5 min0.05 / 4.117 / 9.1 min0.00 / 1.58 / 19.1 s
TSPTW-50 Hard100.00 / — / 5.1 min86.82 / 0.013 / 9.1 min0.21 / 0.13 / 19.1 s
TSPTW-100 Medium99.87 / 25.790 / 7.4 min0.00 / 7.275 / 91.0 min0.00 / 3.04 / 49.6 s
TSPTW-100 Hard100.00 / — / 6.9 min98.34 / 0.006 / 74.5 min5.02 / 0.16 / 49.4 s
TSPDL-50 Hard99.88 / 27.135 / 5.5 min35.17 / 7.723 / 7.9 min0.00 / 1.32 / 19.1 s
TSPDL-100 Hard100.00 / — / 6.6 min36.30 / 26.992 / 63.3 min0.03 / 2.75 / 50.4 s
CVRPBLTW-5018.00 / 21.320 / 1.9 min0.00 / 0.479 / 1.6 min0.40 / -2.15 / 4.9 s
CVRPBLTW-10031.70 / 20.477 / 3.4 min0.00 / -1.697 / 12.2 min0.20 / -5.37 / 14.4 s
AuthorsOpenReview ↗

Response to jr5A — Q1: Benchmark selection and real-world evaluation

Synthetic benchmarks provide controlled comparisons across problem sizes and constraint tightness. We also evaluated ALTER on two established real-world benchmark families: TSPDL instances based on real cities and Dumas-family TSPTW instances [3].

For TSPDL, we use the 120 coordinate-based instances of Rakke et al. [1], which add draft limits to four TSPLIB city instances with 14–29 nodes. Every method uses its TSPDL-50 Hard checkpoint without retraining. Gaps are measured against the optimal values reported by Battarra et al. [2]. All methods solve every instance, and ALTER achieves the lowest gap on all four city bases (Table ii).

Table ii. Public TSPDL results without retraining. Entries are mean gaps to the optimum (%) over 30 instances per city base.

Methodburma14ulysses16ulysses22bayg29CPU time (s)
ALTER, K=51.140.803.033.3952.0
ALTER, K=12.672.234.634.5111.3
LMask13.4910.8612.0014.760.7
PIP15.3111.0512.7516.181.3
PIP-D16.9714.9919.7219.461.3

For TSPTW, we evaluate 100 public Dumas-family instances [3] with 20, 40, 60, and 80 nodes, 25 at each size, using the public instance set evaluated by LMask [4]. Dumas places time windows around arrival times along short tours: the reference-tour travel time is approximately 80% of the time horizon, and mean window widths are approximately 8–15% of it. In the synthetic Medium setting, the corresponding tour-time ratio is only 30–40%; in Hard, windows span just 1–2% of the horizon, strongly restricting the visiting order. Dumas therefore combines a tighter overall time budget than Medium with wider local windows than Hard.

To adapt to this regime, every method is fine-tuned from its TSPTW-50 Medium checkpoint on approximately 1.7 million generated Dumas-style instances. Public benchmark instances are excluded from training, validation, and checkpoint selection.

Table iii. Public TSPTW results after the same 1.7M-instance fine-tuning budget. Entries are mean gaps (%) to the benchmark reference values over each method's solved instances. Solved counts cover all 100 instances.

Method20 nodes40 nodes60 nodes80 nodesSolved
ALTER2.630.871.161.71100/100
LMask4.711.061.232.34100/100
PIP7.231.842.422.9192/100
PIP-D9.112.671.713.7588/100

At this common fine-tuning budget, ALTER solves every public TSPTW instance and achieves the lowest mean gap at every size. Together with the TSPDL results, these evaluations demonstrate strong performance on public benchmarks beyond the synthetic test sets used in the main experiments.

References

[1] Rakke, Jørgen Glomvik, et al. The traveling salesman problem with draft limits. Computers & Operations Research, 2012.

[2] Battarra, Maria, et al. Exact algorithms for the traveling salesman problem with draft limits. European Journal of Operational Research, 2014.

[3] Dumas, Yvan, et al. An optimal algorithm for the traveling salesman problem with time windows. Operations Research, 1995.

[4] Li, Tianyou, et al. LMask: Learn to solve constrained routing problems with lazy masking. ICLR 2026.

Thank you for the response. The additional experiments have addressed some of my concerns. However, it remains unclear for me why the heuristic-based variants perform substantially worse than the proposed neural method, while LKH-3, which also relies on k-opt heuristics, achieves the best solution quality in Table 1. Could you provide more detailed analysis to explain this performance gap?

We thank you for highlighting that both our heuristic variant and LKH-3 use k-opt moves. However, they differ in how they select those moves. In our alternating search, the TSPTW variant samples three cuts and a reconnection from the current tour. The exploration step scores the resulting tours primarily by route cost, and the repair step scores them primarily by constraint violation. The tour selected in each step becomes the starting point for the next. LKH-3, by contrast, uses candidate edges to build a sequence of linked exchanges and gives edges shared by its best tours priority in later trials. When comparing tours, LKH-3 first favors the one with the lower constraint-violation penalty; if the penalties are equal, it favors the shorter tour.

In addition, we used LKH-3 as a reference solver for constrained routing [4-6] and deliberately gave it a substantial search budget to obtain high-quality feasible tours. On TSPTW-100 Hard, for example, LKH-3 ran for 26.1 hours across the full test set. The LKH-3 result we report for each instance is the length of the best feasible tour found over that extended search, which serves as the reference for computing the gap.

[5] Bi, Jieyi, et al. Learning to Handle Complex Constraints for Vehicle Routing Problems. NeurIPS 2024.

[6] Bi, Jieyi, et al. Towards Efficient Constraint Handling in Neural Solvers for Routing Problems. ICLR 2026.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Revisions and Key Findings

Thank you for the thoughtful discussion and the opportunity to further strengthen and clarify our work. The principal revisions and findings arising from the discussion are summarized below:

Strong performance under comparable inference-time budgets. The inference-time comparisons conducted during revision reinforce ALTER’s advantage: it continues to achieve lower gaps across the majority of settings when inference budgets are made comparable.

Consistent strengths across diverse evaluation settings. We expanded the evaluation to public TSPDL benchmarks based on four real cities, where ALTER outperforms all tested neural baselines. Together with the lowest gaps in seven of eight routing settings in the manuscript, these results strengthen the case for a framework whose advantages extend across constraint regimes, difficulty levels, and data sources.

Broader applicability of the proposed framework. We further investigated applicability beyond routing through a separately trained extension to 0–1 Knapsack, obtaining near-zero gaps with complete feasibility. Alongside the demonstrated transfer from 100-node training to 200-node CVRPBLTW without retraining, these results provide a stronger empirical foundation for ALTER’s potential as a broadly applicable constrained optimization framework.

Complementary analyses and clarifications. We also examined heuristic alternatives, isolated the contribution of disagreement memory, and compared adaptive control against tuned fixed penalties. Together with fuller reporting of time–quality behavior and training costs, these analyses provide a more complete understanding of ALTER’s design choices, empirical behavior, and computational requirements. We also restored references omitted from the original submission due to the page limit.

While subsequent discussion has increasingly revolved around an isolated comparison with a single baseline under one specific experimental condition, our additional experiments show that ALTER’s performance advantages hold even on those terms. More importantly, a framework validated across diverse constraint regimes, real-world benchmarks, scales, and problem domains should not be evaluated through such an overly constrained lens. We hope these comprehensive results provide a clear basis for evaluating ALTER’s broader contributions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.