- 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
- 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.
- 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
- 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.
- 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
- How sensitive is PACER’s performance to the size and quality of the offline search trees, and how expensive are these trees to generate?
- Does a policy trained on CVRP-500 retain its advantage on different problem sizes and customer distributions without retraining?
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.
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.
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.
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.