acceptodds
Under review as a conference paper at ICLR 2027

PACER: Time Budget-Aware Neural Local Search for Vehicle Routing Problems

Abstract

Within neural combinatorial optimization, learning-augmented local search has emerged as a practical approach to large-scale instances: it iteratively selects a subproblem and re-optimizes it with a repair operator, where either component can be learned or expert-designed. However, existing methods are often budget-agnostic. The learned policy make the same decisions whether the compute budget (e.g., wall-clock time) is tight or generous. This overlooks the budget-dependent opportunity cost of each decision and locks them into a one-size-fits-all way of spending compute, which yields suboptimal performance across the budget. In this study, we introduce PACER, a time-budget-aware neural local search framework that explicitly schedules the pace of the search process conditioned on the given compute budget. At each improvement step, PACER jointly decides which subproblem to re-optimize and how much solver time to allocate to it. We train PACER's subproblem selection and time allocation neural policy through imitation learning. To generate supervision, we roll out beam trees over subproblem selections and probe the solver's objective trajectory over time for each expanded subproblem. We then relabel each search state with downstream action values for any remaining budget through dynamic programming, turning each subproblem's value under different budgets into supervision. Experiments on 500-customer instances of the capacitated vehicle routing problem (CVRP) show that PACER improves the quality–runtime trade-off over budget-agnostic neural local search baselines and strong CVRP solvers under budgets of 1–50 seconds, reducing the optimality gap by up to 1.90%, and remains competitive at longer budgets beyond the training range. Counterfactual analyses that vary only the budget input show that the policy shifts both its solver-time allocation and its subproblem preferences as the remaining budget changes. These results suggest that the compute budget could reshape optimization decisions in the local search. Since real-world combinatorial optimization is a test-time computation that delivers solutions under finite budgets, learning how to spend a budget matters as much as learning where to search.

Primary area:
optimization
Keywords:
neural combinatorial optimization, vehicle routing problems, budget awareness, local search

Reviews

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

The paper presents PACER, a time-budget-aware neural local-search framework for vehicle routing that jointly selects which subproblem to optimize and how much solver time to allocate. By conditioning decisions on the current solution and remaining budget, PACER aims to maximize solution quality before the deadline. Its policy is trained through imitation learning using offline search trees, which dynamic programming relabels under different budgets to capture both immediate and downstream improvements. This allows the same solver-generated data to support training across multiple budgets.

Critical strengths
  1. For me, the point this paper investigates (the time budget) is intersting. Jointly choosing the subproblem and its solver time addresses a practical limitation of local search under deadlines. This matters because a promising repair may be a poor choice when little time remains.
  2. Reusable supervision that accounts for future gains. Dynamic programming relabels the same offline search tree for multiple budgets, considering both immediate and subsequent improvements. This provides richer supervision than greedy selection while avoiding repeated solver calls for each training budget.
Critical weaknesses
  1. The benefit of budget conditioning is not isolated. The introduction claims a comparison with an otherwise identical budget-blind variant, but corresponding results are not reported. Changes in selected actions alone do not establish better solutions, leaving the central explanation for the gains insufficiently supported.
  2. Computational comparisons need stronger controls. The strongest variant runs several solver calls concurrently, but CPU core allocations and comparisons with equally parallel baselines are not reported. This makes it difficult to separate the benefit of learned scheduling from that of additional parallel computation.
Questions for authors
  1. How sensitive is PACER’s performance to the size and quality of the offline search trees, and how expensive are these trees to generate?
  2. Does a policy trained on CVRP-500 retain its advantage on different problem sizes and customer distributions without retraining?
1 comment
AuthorsOpenReview ↗

Response to Reviewer qMiz

We sincerely thank you for your thoughtful comments. We respond to each point below and hope that our responses address your concerns.

Q1. How sensitive is PACER's performance to the size and quality of the offline search trees, and how expensive are these trees to generate?

Thank you for this question. Our collector balances generation cost against tree quality: probing 5% of the candidate subproblems at each expanded state retains 83–97% of the full-probing tree value at about 1/19 of the cost.

Specifically, at each expanded state, the collector probes a random 5% of the roughly 230 candidate subproblems. For this analysis, we build complete trees at each probing rate from the same initial solutions and with the same random seeds. The table below reports the deadline-DP value under each time budget (higher is better), with the share of the full-probing value in parentheses.

Probing rate per expanded state1 s5 s10 s15 s50 s
100% (full)5.165.435.575.655.82
10%4.58 (89%)5.11 (94%)5.39 (97%)5.53 (98%)5.74 (99%)
5% (used in PACER)4.29 (83%)4.93 (91%)5.25 (94%)5.44 (96%)5.66 (97%)
1%3.55 (69%)4.62 (85%)5.00 (90%)5.22 (92%)5.55 (95%)

As for generation cost, building one oracle tree at the 5% probing rate takes about 9 minutes of wall-clock time on 8 dedicated cores, and collecting 10,000 trees takes about 4 days.

Q2. Does a policy trained on CVRP-500 retain its advantage on different problem sizes and customer distributions without retraining?

Thank you for raising this point. Because PACER relies on a learned neural policy, its performance degrades significantly when the problem size or customer distribution shifts, as is common for neural policies in combinatorial optimization. New data collection and retraining are therefore needed to maintain its performance in a new setting.

Reviewer_sjoROpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

PACER learns a budget-conditioned local-search policy that jointly selects a CVRP subproblem and its PyVRP runtime. It uses offline beam-tree rollouts, dynamic-programming budget relabeling, and imitation learning, and evaluates the resulting policy on synthetic CVRP-500 instances.

Critical strengths
  • Jointly selecting a subproblem and its solver time addresses a relevant quality–runtime trade-off.
  • Offline dynamic-programming relabeling reuses the same solver trajectories across different time budgets.
Critical weaknesses
  • PyVRP overtakes both PACER variants at 60s and 100s. Top5's advantage shrinks from 1.90% at 5s to 0.12% at 50s (Table 1).
  • Top5 solves up to six disjoint subproblems concurrently. A matched-parallelism decomposition baseline is needed.
  • Experiments cover only uniformly generated CVRP-500 instances with capacity 50.
  • Table 2 uses 1/50s and 10/50s comparisons, whereas Appendix C specifies 1/5s, 1/10s, and 5/10s.
  • The beam-tree oracle requires extensive solver probing, but collection cost and tree size are not quantified.
Questions for authors
  • What explains PACER's loss to PyVRP at 60s and 100s? Does subproblem decomposition restrict longer-term improvement?
  • Could the authors report an identical budget-blind policy and fixed-runtime schedules under the same Top-5 setup?
  • How many CPU cores/threads are assigned to each method? Can results be compared with matched parallel resources?
  • Which budget pairs and test instances were used for Table 2, given the discrepancy with Appendix C?
  • What are the total offline oracle-collection time and computational cost?
2 comments
AuthorsOpenReview ↗

Response to Reviewer sjoR

We thank you for your insightful and valuable comments. We respond to each question below and hope that our responses address your concerns.

Q1. What explains PACER's loss to PyVRP at 60s and 100s? Does subproblem decomposition restrict longer-term improvement?

PACER is trained with time budgets of up to 50 s. Because it relies on a learned neural policy, its performance degrades significantly when the budget exceeds this training range, which explains its loss to PyVRP at 60 s and 100 s.

Q2. Could the authors report an identical budget-blind policy and fixed-runtime schedules under the same Top-5 setup?

Yes. Under the same top-5 setup, we compare PACER with (i) a budget-blind policy that uses the same network and training but receives no budget input, and (ii) PACER's subproblem selection with a fixed solver runtime of 1 s or 5 s. We evaluate on 128 test instances, a larger set than the 10 instances used in the paper. The table reports the average objective value (lower is better), with the best result in each column in bold.

Policy (top-5)1 s10 s50 s100 s
PACER (budget-aware, learned runtime)64.09362.93362.75362.686
Budget-blind64.09862.95662.83262.828
PACER selection, fixed 1 s64.17662.91662.76262.729
PACER selection, fixed 5 s64.17563.08862.75962.710

PACER achieves the best result at 1 s, 50 s, and 100 s, and its advantage over the budget-blind policy grows with the budget, from 0.005 at 1 s to 0.142 at 100 s. At 10 s, the fixed 1 s schedule is slightly better (62.916 vs. 62.933).

Q3. How many CPU cores/threads are assigned to each method? Can results be compared with matched parallel resources?

Each baseline run is pinned to a single physical CPU core. Top-5 PACER uses five cores to solve the top-5 subproblems in parallel. We also run LKH and PyVRP with five cores each; since both solvers are single-threaded, the additional cores do not improve their performance.

Q4. Which budget pairs and test instances were used for Table 2, given the discrepancy with Appendix C?

Thank you for pointing out this discrepancy, and we apologize for the confusion. Table 2 uses the budget pairs (1 s, 50 s) and (10 s, 50 s), as stated in the table. We will correct Appendix C in the revision.

Q5. What are the total offline oracle-collection time and computational cost?

Building one oracle tree takes about 9 minutes of wall-clock time on 8 dedicated cores. Collecting all 10,000 trees takes about 4 days of wall-clock time, for a total of about 12,000 core-hours.

Thank you for the clarification. I will maintain my score because my main concern is how well a policy trained for a one-time budget performs at another. Could you train four separate PACER policies, one for each search budget of 1, 10, 60, and 100 seconds, and report each policy’s gap to PyVRP at all four test budgets on the same CVRP instances?

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

This paper proposes PACER, a time budget-aware neural local search solver for vehicle routing problems. At each step, the solver jointly selects a subproblem and its time allocation, conditioned on the current solution and remaining budget. Training supervision is generated through offline beam-tree exploration and dynamic programming. Experiments on synthetic CVRP-500 instances demonstrate the superiority of PACER over traditional solvers and learning-based decomposition methods across multiple time budgets.

Critical strengths
  1. The motivation is clear. Explicitly considering the remaining budget when selecting subproblems and allocating solver time is a reasonable direction for improving neural local search. Meanwhile, reusing collected search trees to generate supervision under multiple budgets is a good design, which separates expensive solver-based data collection from training.

  2. The experimental results over traditional solvers and learning-based decomposition methods are generally encouraging, especially on small-budget cases.

Critical weaknesses
  1. The experiments do not isolate the contribution of budget awareness. The introduction states that PACER outperforms an otherwise identical budget-blind variant, but I do not find the corresponding results in the main paper or appendices. Comparisons with L2D and UDC do not substitute for this control, since these methods may differ in other components. An otherwise identical budget-blind solver, together with fixed-time allocation baselines, is necessary to establish whether the improvements come from conditioning on the remaining budget.

  2. The experimental coverage is very limited. All results are obtained on 100 synthetic CVRP-500 instances from a single distribution. Generalization to other instance sizes, customer distributions, and standard benchmarks such as CVRPLIB is not evaluated. The advantage also decreases with the budget: PACER-top1 no longer outperforms PyVRP from 30 seconds onward, and both variants are worse at 60 and 100 seconds. Meanwhile, state-of-the-art auto-regressive NCO methods are not included in the comparison.

Questions for authors
  1. Could the authors clarify the computational fairness of the comparisons, including CPU parallelism, subsolver choice, and the offline costs of data collection and training?
1 comment
AuthorsOpenReview ↗

Response to Reviewer qtUX

We thank the reviewer for the insightful and valuable comments. We respond to each comment below and hope that our responses address your concerns.


Q1. Could the authors clarify the computational fairness of the comparisons, including CPU parallelism, subsolver choice, and the offline costs of data collection and training?

CPU parallelism. Each baseline run is pinned to a single physical CPU core. Top-5 PACER uses five cores to solve the top-5 subproblems in parallel. We also run LKH and PyVRP with five cores each; since both solvers are single-threaded, the additional cores do not improve their performance.

Subsolver choice. For a fair comparison, PACER and all baselines start from the same initial solution generated by LKH. PACER uses PyVRP as its subsolver in all runs.

Offline costs of data collection and training. Data collection runs entirely on CPUs: building one oracle tree takes about 9 minutes of wall-clock time on 8 dedicated cores. Collecting 10,000 trees takes 4 days. Training then converges in about 4 hours on a single NVIDIA A100 GPU.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.