pith. sign in

arxiv: 2605.00572 · v1 · submitted 2026-05-01 · 💻 cs.AI · math.OC

Instance-Aware Parameter Configuration in Bilevel Late Acceptance Hill Climbing for the Electric Capacitated Vehicle Routing Problem

Yinghao Qin , Xinwei Wang , Mosab Bazargani , Jun Chen This is my paper

Pith reviewed 2026-05-09 19:37 UTC · model grok-4.3

classification 💻 cs.AI math.OC
keywords electric capacitated vehicle routingparameter configurationmetaheuristicsinstance-aware tuningregression modellate acceptance hill climbingbilevel optimization
0
0 comments X

The pith

A regression model that predicts parameters from instance features improves metaheuristic solutions for the electric capacitated vehicle routing problem over a global setting.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that different instances of the electric vehicle routing problem benefit from different parameter settings in the Bilevel Late Acceptance Hill Climbing algorithm. By training a regression model on features extracted from training instances and their best offline-tuned parameters, it becomes possible to predict suitable parameters for new instances before solving them. This instance-aware method yields an average 0.28 percent better objective value than a single globally tuned configuration across held-out test cases. Such gains matter in practice because routing operations involve high costs where even small improvements add up. The approach keeps the computational overhead low by performing the heavy tuning offline.

Core claim

The paper's core discovery is that instance-specific parameter settings, predicted by a regression model from problem features, lead to an average 0.28% reduction in objective value for the Electric Capacitated Vehicle Routing Problem when using Bilevel Late Acceptance Hill Climbing, outperforming a single global parameter set on held-out instances.

What carries the argument

The regression model that maps instance features to predicted parameter settings for the Bilevel Late Acceptance Hill Climbing algorithm.

Load-bearing premise

The regression model will select parameters that genuinely improve solution quality on new instances instead of just echoing patterns from the training data.

What would settle it

If experiments on additional held-out instances show that the predicted parameters do not produce lower objective values than the global configuration on average, the benefit would be falsified.

Figures

Figures reproduced from arXiv: 2605.00572 by Jun Chen, Mosab Bazargani, Xinwei Wang, Yinghao Qin.

Figure 1
Figure 1. Figure 1: Illustrative solution to the E-CVRP. outperform globally optimised configurations by exploiting instance-level heterogeneity [9]. The effectiveness of IAAC has been demonstrated across several combinatorial optimisation domains. Ansotegui et ´ al. [18] showed that instance-specific configuration can sig￾nificantly improve solvers for the Maximum Satisfiability (MaxSAT) problem across heterogeneous instance… view at source ↗
Figure 2
Figure 2. Figure 2: Overview of the proposed instance-aware parameter prediction framework for b-LAHC. view at source ↗
read the original abstract

Algorithm performance in combinatorial optimization is highly sensitive to parameter settings, while a single globally tuned configuration often fails to exploit the heterogeneity of instances. This limitation is particularly evident in the Electric Capacitated Vehicle Routing Problem, where instances differ in structure, demand patterns, and energy constraints. This paper investigates instance-aware parameter configuration for Bilevel Late Acceptance Hill Climbing, a state-of-the-art metaheuristic for the Electric Capacitated Vehicle Routing Problem. An offline tuning procedure is used to obtain instance-specific parameter labels, which are then mapped from instance features via a regression model to enable parameter prediction for unseen instances prior to execution. Experimental results on the IEEE WCCI 2020 benchmark and its extensions show that the proposed approach achieves an average objective value reduction of $0.28\%$ across eight held-out test instances relative to a globally tuned configuration. This corresponds to a significant cost reduction in multimillion-dollar transportation operations.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper proposes an instance-aware parameter configuration approach for Bilevel Late Acceptance Hill Climbing applied to the Electric Capacitated Vehicle Routing Problem. Offline tuning generates instance-specific parameter labels on a training set of instances; these labels are then used to train a regression model that maps instance features to predicted parameters for unseen instances. Experiments on the IEEE WCCI 2020 benchmark and extensions report that the method yields an average 0.28% reduction in objective value across eight held-out test instances relative to a single globally tuned configuration.

Significance. If the empirical claim is substantiated with proper statistical controls, the work would offer a practical way to exploit instance heterogeneity in metaheuristics for ECVRP, potentially translating small percentage gains into meaningful operational savings. The bilevel formulation and regression-based prediction pipeline are technically coherent, but the modest reported improvement and absence of validation details currently limit the result's demonstrated impact.

major comments (3)
  1. [Abstract / Experimental results] Abstract and experimental results section: the central claim of a 0.28% average objective reduction on eight held-out instances is presented without any report of statistical significance, standard deviation across runs, number of independent trials, or p-values against the global baseline. This information is load-bearing because the small effect size could be explained by noise, run-to-run variance in the metaheuristic, or overfitting in the regression step.
  2. [Methodology / Regression model] Regression model description: no details are given on the size of the training set used to generate offline-tuned labels, the feature selection procedure, the regression algorithm chosen, or any internal validation metric (e.g., cross-validation R² or prediction error on held-out training folds). Without these, it is impossible to assess whether the model learns stable feature-to-parameter mappings or merely fits idiosyncrasies of the training instances.
  3. [Methodology / Offline tuning] Offline tuning procedure: the process that produces the instance-specific parameter labels is not characterized with respect to tuning budget, convergence criteria, or robustness across repeated tunings. If the labels themselves are unstable, the downstream regression cannot be expected to generalize reliably to the test instances.
minor comments (2)
  1. [Abstract] The abstract states that the 0.28% reduction 'corresponds to a significant cost reduction in multimillion-dollar transportation operations' without providing any scaling calculation or reference to typical fleet sizes/costs; this phrasing should be qualified or supported.
  2. [Introduction / Methodology] Notation for the bilevel formulation and the feature vector used by the regression model should be introduced consistently and early; several symbols appear without prior definition in the provided text.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for their thorough review and valuable comments. We believe the suggested additions will strengthen the paper's empirical claims and methodological transparency. We address each major comment below and will incorporate the necessary revisions.

read point-by-point responses

  1. Referee: [Abstract / Experimental results] Abstract and experimental results section: the central claim of a 0.28% average objective reduction on eight held-out instances is presented without any report of statistical significance, standard deviation across runs, number of independent trials, or p-values against the global baseline. This information is load-bearing because the small effect size could be explained by noise, run-to-run variance in the metaheuristic, or overfitting in the regression step.

    Authors: We agree that these statistical details are essential for validating the modest improvement. In the revised manuscript, we will expand the experimental results section to report the number of independent trials conducted for each method, the standard deviations of the objective values, and the outcomes of statistical significance tests (such as paired t-tests or non-parametric alternatives) comparing the instance-aware configuration to the global baseline. This will clarify whether the 0.28% average reduction is robust against run-to-run variance. revision: yes

  2. Referee: [Methodology / Regression model] Regression model description: no details are given on the size of the training set used to generate offline-tuned labels, the feature selection procedure, the regression algorithm chosen, or any internal validation metric (e.g., cross-validation R² or prediction error on held-out training folds). Without these, it is impossible to assess whether the model learns stable feature-to-parameter mappings or merely fits idiosyncrasies of the training instances.

    Authors: We will update the methodology section to include comprehensive details on the regression model. Specifically, we will specify the size of the training set used for generating the offline-tuned parameter labels, the procedure for feature selection, the exact regression algorithm employed, and the internal validation metrics obtained, such as cross-validation R² scores and prediction errors on held-out folds. These additions will enable readers to evaluate the reliability and generalizability of the feature-to-parameter mappings. revision: yes

  3. Referee: [Methodology / Offline tuning] Offline tuning procedure: the process that produces the instance-specific parameter labels is not characterized with respect to tuning budget, convergence criteria, or robustness across repeated tunings. If the labels themselves are unstable, the downstream regression cannot be expected to generalize reliably to the test instances.

    Authors: We acknowledge the need for more information on the offline tuning process. In the revision, we will provide a detailed characterization of the tuning procedure, including the computational budget allocated per instance, the convergence criteria used, and an analysis of robustness by performing multiple independent tunings and reporting the variability in the resulting parameter labels. This will address potential concerns about the stability of the labels used for training the regression model. revision: yes

Circularity Check

0 steps flagged

No circularity: standard train-test split for regression-based parameter prediction

full rationale

The paper's core chain is: (1) offline tuning produces instance-specific parameter labels on a training set of instances, (2) a regression model is fitted to map instance features to those labels, and (3) the model is applied to predict parameters for held-out test instances before running the metaheuristic. This is a conventional supervised-learning workflow with explicit separation between training labels and test evaluation. No equation or procedure reduces a claimed prediction to its own fitted inputs by construction, no self-citation is invoked as a uniqueness theorem, and the reported 0.28% objective reduction is measured on unseen instances rather than on the training data used to build the regressor. The derivation therefore remains self-contained and externally falsifiable.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

Review is based solely on the abstract; therefore the ledger is necessarily incomplete and reflects only the high-level assumptions visible in the summary. The central claim rests on the premise that instance features are predictive of good parameter values and that offline tuning produces reliable labels.

free parameters (1)
  • Regression coefficients
    The mapping from instance features to parameter labels is learned from data, so the regression weights are fitted parameters whose values are not reported.
axioms (1)
  • domain assumption Problem instance features correlate with optimal metaheuristic parameter settings
    The method presupposes that measurable characteristics of an E-CVRP instance (customer count, demand patterns, energy constraints) can be used to predict parameters that improve search performance.

pith-pipeline@v0.9.0 · 5465 in / 1494 out tokens · 49698 ms · 2026-05-09T19:37:33.512137+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [1]

    Parameter adjustment based on performance prediction: Towards an instance-aware problem solver,

    F. Hutter and Y . Hamadi, “Parameter adjustment based on performance prediction: Towards an instance-aware problem solver,”Microsoft Re- search, Tech. Rep. MSR-TR-2005-125, 2005

    work page 2005

  2. [2]

    Birattari and J

    M. Birattari and J. Kacprzyk,Tuning metaheuristics: a machine learning perspective. Springer, 2009, vol. 197

    work page 2009

  3. [3]

    ISAC–instance- specific algorithm configuration,

    S. Kadioglu, Y . Malitsky, M. Sellmann, and K. Tierney, “ISAC–instance- specific algorithm configuration,” inECAI 2010. Ios Press, 2010, pp. 751–756

    work page 2010

  4. [4]

    Automated algorithm configuration and design,

    M. L ´opez-Ib´a˜nez and T. St ¨utzle, “Automated algorithm configuration and design,” inProceedings of the 2020 Genetic and Evolutionary Computation Conference Companion, 2020, pp. 1075–1100

    work page 2020

  5. [5]

    A new hyper-heuristic based on adaptive simulated annealing and reinforcement learning for the capacitated electric vehicle routing problem,

    E. Rodr ´ıguez-Esparza, A. D. Masegosa, D. Oliva, and E. Onieva, “A new hyper-heuristic based on adaptive simulated annealing and reinforcement learning for the capacitated electric vehicle routing problem,”Expert Systems with Applications, vol. 252, p. 124197, 2024

    work page 2024

  6. [6]

    A Q-learning-based hyper-heuristic for capacitated electric vehicle routing problem,

    J. Lin, X. Wang, R. Niu, and Y . He, “A Q-learning-based hyper-heuristic for capacitated electric vehicle routing problem,”IEEE Transactions on Intelligent Transportation Systems, 2025

    work page 2025

  7. [7]

    A deep reinforcement learning-based adaptive large neighborhood search for capacitated electric vehicle routing problems,

    C. Wang, M. Cao, H. Jiang, X. Xiang, and X. Zhang, “A deep reinforcement learning-based adaptive large neighborhood search for capacitated electric vehicle routing problems,”IEEE Transactions on Emerging Topics in Computational Intelligence, 2024

    work page 2024

  8. [8]

    A confidence-based bilevel memetic algorithm with adaptive selection scheme for capacitated electric vehicle routing problem,

    Y . Qin and J. Chen, “A confidence-based bilevel memetic algorithm with adaptive selection scheme for capacitated electric vehicle routing problem,” in2024 IEEE Congress on Evolutionary Computation (CEC). IEEE, 2024, pp. 1–10

    work page 2024

  9. [9]

    Learning instance- specific predictive models

    S. Visweswaran, G. F. Cooper, and M. Chickering, “Learning instance- specific predictive models.”Journal of Machine Learning Research, vol. 11, no. 12, 2010

    work page 2010

  10. [10]

    Benchmark set for the IEEE WCCI- 2020 competition on evolutionary computation for the electric vehicle routing problem,

    M. Mavrovouniotis, C. Menelaou, S. Timotheou, C. Panayiotou, G. Ellinas, and M. Polycarpou, “Benchmark set for the IEEE WCCI- 2020 competition on evolutionary computation for the electric vehicle routing problem,” KIOS CoE, University of Cyprus, Tech. Rep., 2020, technical Report. [Online]. Available: https://mavrovouniotis.github.io/ EVRPcompetition2020/

    work page 2020

  11. [11]

    Machine learning for combinato- rial optimization: A methodological tour d’horizon,

    Y . Bengio, A. Lodi, and A. Prouvost, “Machine learning for combinato- rial optimization: A methodological tour d’horizon,”European Journal of Operational Research, vol. 290, no. 2, pp. 405–421, 2021

    work page 2021

  12. [12]

    A bilevel ant colony optimization algorithm for capacitated electric vehicle routing problem,

    Y .-H. Jia, Y . Mei, and M. Zhang, “A bilevel ant colony optimization algorithm for capacitated electric vehicle routing problem,”IEEE trans- actions on cybernetics, vol. 52, no. 10, pp. 10 855–10 868, 2021

    work page 2021

  13. [13]

    Confidence-based ant colony optimization for capacitated elec- tric vehicle routing problem with comparison of different encoding schemes,

    ——, “Confidence-based ant colony optimization for capacitated elec- tric vehicle routing problem with comparison of different encoding schemes,”IEEE Transactions on Evolutionary Computation, vol. 26, no. 6, pp. 1394–1408, 2022

    work page 2022

  14. [14]

    A dual-population- based co-evolutionary algorithm for capacitated electric vehicle routing problems,

    C. Wang, F. Qin, X. Xiang, H. Jiang, and X. Zhang, “A dual-population- based co-evolutionary algorithm for capacitated electric vehicle routing problems,”IEEE Transactions on Transportation Electrification, vol. 10, no. 2, pp. 2663–2676, 2023

    work page 2023

  15. [15]

    An efficient threshold acceptance- based multi-layer search algorithm for capacitated electric vehicle rout- ing problem,

    Y . Chen, J. Xue, Y . Zhou, and Q. Wu, “An efficient threshold acceptance- based multi-layer search algorithm for capacitated electric vehicle rout- ing problem,”IEEE Transactions on Intelligent Transportation Systems, vol. 25, no. 6, pp. 5867–5879, 2024

    work page 2024

  16. [16]

    Variable neighbor- hood search for the electric vehicle routing problem,

    D. Woller, V . Koz ´ak, M. Kulich, and L. P ˇreuˇcil, “Variable neighbor- hood search for the electric vehicle routing problem,”arXiv preprint arXiv:2511.09570, 2025

    work page arXiv 2025

  17. [17]

    The algorithm selection problem,

    J. R. Rice, “The algorithm selection problem,” inAdvances in computers. Elsevier, 1976, vol. 15, pp. 65–118

    work page 1976

  18. [18]

    Maxsat by im- proved instance-specific algorithm configuration,

    C. Ans ´otegui, J. Gabas, Y . Malitsky, and M. Sellmann, “Maxsat by im- proved instance-specific algorithm configuration,”Artificial Intelligence, vol. 235, pp. 26–39, 2016

    work page 2016

  19. [19]

    Instance-specific algorithm configuration via unsupervised deep graph clustering,

    W. Song, Y . Liu, Z. Cao, Y . Wu, and Q. Li, “Instance-specific algorithm configuration via unsupervised deep graph clustering,”Engineering Applications of Artificial Intelligence, vol. 125, p. 106740, 2023

    work page 2023

  20. [20]

    Evolving instance specific algorithm configuration,

    Y . Malitsky, D. Mehta, and B. O’Sullivan, “Evolving instance specific algorithm configuration,” inProceedings of the International Symposium on Combinatorial Search, vol. 4, no. 1, 2013, pp. 133–140

    work page 2013

  21. [21]

    The late acceptance hill-climbing heuristic,

    E. K. Burke and Y . Bykov, “The late acceptance hill-climbing heuristic,” European Journal of Operational Research, vol. 258, no. 1, pp. 70–78, 2017

    work page 2017

  22. [22]

    Late acceptance hill- climbing for high school timetabling,

    G. H. Fonseca, H. G. Santos, and E. G. Carrano, “Late acceptance hill- climbing for high school timetabling,”Journal of Scheduling, vol. 19, no. 4, pp. 453–465, 2016

    work page 2016

  23. [23]

    Late acceptance hill climbing algorithm for solving patient admission scheduling problem,

    A. L. Bolaji, A. F. Bamigbola, and P. B. Shola, “Late acceptance hill climbing algorithm for solving patient admission scheduling problem,” Knowledge-Based Systems, vol. 145, pp. 197–206, 2018

    work page 2018

  24. [24]

    The irace package: Iterated racing for automatic algorithm configuration,

    M. L ´opez-Ib´a˜nez, J. Dubois-Lacoste, L. P. C ´aceres, M. Birattari, and T. St ¨utzle, “The irace package: Iterated racing for automatic algorithm configuration,”Operations Research Perspectives, vol. 3, pp. 43–58, 2016

    work page 2016

  25. [25]

    An algorithm for the vehicle-dispatching problem,

    N. Christofides and S. Eilon, “An algorithm for the vehicle-dispatching problem,”Journal of the Operational Research Society, vol. 20, no. 3, pp. 309–318, 1969

    work page 1969

  26. [26]

    Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations,

    N. Christofides, A. Mingozzi, and P. Toth, “Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations,”Mathematical programming, vol. 20, no. 1, pp. 255–282, 1981

    work page 1981

  27. [27]

    Optimal solution of vehicle routing problems using minimum k-trees,

    M. L. Fisher, “Optimal solution of vehicle routing problems using minimum k-trees,”Operations research, vol. 42, no. 4, pp. 626–642, 1994

    work page 1994

  28. [28]

    New benchmark instances for the capacitated vehicle routing problem,

    E. Uchoa, D. Pecin, A. Pessoa, M. Poggi, T. Vidal, and A. Subramanian, “New benchmark instances for the capacitated vehicle routing problem,” European Journal of Operational Research, vol. 257, no. 3, pp. 845–858, 2017

    work page 2017

  29. [29]

    A benchmark test suite for the electric capacitated vehicle routing problem,

    M. Mavrovouniotis, C. Menelaou, S. Timotheou, G. Ellinas, C. Panayiotou, and M. Polycarpou, “A benchmark test suite for the electric capacitated vehicle routing problem,” in2020 IEEE Congress on evolutionary computation (CEC). IEEE, 2020, pp. 1–8

    work page 2020