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

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.