pith. sign in

arxiv: 2604.13013 · v1 · submitted 2026-04-14 · 💻 cs.AI · math.OC

Bilevel Late Acceptance Hill Climbing for the Electric Capacitated Vehicle Routing Problem

Yinghao Qin , Mosab Bazargani , Edmund K. Burke , Carlos A. Coello Coello , Zhongmin Song , Jun Chen This is my paper

Pith reviewed 2026-05-10 14:40 UTC · model grok-4.3

classification 💻 cs.AI math.OC
keywords electric capacitated vehicle routingbilevel optimizationlate acceptance hill climbingsurrogate objectivemetaheuristic searchrouting and charging decisionsbenchmark performance
0
0 comments X

The pith

Bilevel Late Acceptance Hill Climbing improves electric vehicle routing solutions by guiding search with a surrogate objective for routing and charging.

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

The paper presents a bilevel optimization method for the Electric Capacitated Vehicle Routing Problem that separates routing and charging decisions at different stages of the search while still combining them for final evaluation. A surrogate objective approximates the full cost at the upper level to speed convergence without losing the need for joint lower-level solutions. The resulting b-LAHC algorithm uses three fixed phases and no parameter tuning, delivering competitive or better results than eight existing algorithms on standard test sets and establishing new best-known solutions on nine of ten large instances with an average improvement of 1.07 percent. This approach matters for problems where energy constraints and charging choices interact with route planning at scale.

Core claim

By analyzing the interaction between routing and charging, the bilevel Late Acceptance Hill Climbing algorithm employs a surrogate objective at the upper level to guide search through greedy descent, neighborhood exploration, and final refinement phases, achieving superior or competitive performance against eight state-of-the-art methods while setting nine new best-known results on large-scale IEEE WCCI-2020 benchmarks under a fixed evaluation budget and improving records by an average of 1.07 percent.

What carries the argument

The bilevel Late Acceptance Hill Climbing (b-LAHC) framework that uses a surrogate objective based on routing-charging interaction to direct upper-level decisions while deferring full joint evaluation to the end.

If this is right

  • Large-scale E-CVRP instances can be solved to higher quality within the same computational budget.
  • The algorithm requires no parameter adaptation, allowing direct application without extensive tuning.
  • The bilevel separation remains necessary for final solution quality even when the surrogate accelerates the process.
  • Problems with clear hierarchical structure in routing and resource decisions become more tractable.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same surrogate-plus-bilevel pattern could be tested on other energy-constrained routing variants such as those with time windows or multiple depots.
  • Replacing the hill-climbing core with another metaheuristic while keeping the bilevel surrogate might yield further gains on very large networks.
  • Application to real fleet data would show whether the benchmark improvements reduce actual operational costs in charging and travel time.

Load-bearing premise

The surrogate objective at the upper level tracks the true complete cost of routing plus charging closely enough to steer the search productively.

What would settle it

A new collection of large E-CVRP instances where the surrogate objective values show little or no positive correlation with actual total costs would demonstrate that the guidance mechanism fails to produce the reported gains.

read the original abstract

This paper tackles the Electric Capacitated Vehicle Routing Problem (E-CVRP) through a bilevel optimization framework that handles routing and charging decisions separately or jointly depending on the search stage. By analyzing their interaction, we introduce a surrogate objective at the upper level to guide the search and accelerate convergence. A bilevel Late Acceptance Hill Climbing algorithm (b-LAHC) is introduced that operates through three phases: greedy descent, neighborhood exploration, and final solution refinement. b-LAHC operates with fixed parameters, eliminating the need for complex adaptation while remaining lightweight and effective. Extensive experiments on the IEEE WCCI-2020 benchmark show that b-LAHC achieves superior or competitive performance against eight state-of-the-art algorithms. Under a fixed evaluation budget, it attains near-optimal solutions on small-scale instances and sets 9/10 new best-known results on large-scale benchmarks, improving existing records by an average of 1.07%. Moreover, the strong correlation (though not universal) observed between the surrogate objective and the complete cost justifies the use of the surrogate objective while still necessitating a joint solution of both levels, thereby validating the effectiveness of the proposed bilevel framework and highlighting its potential for efficiently solving large-scale routing problems with a hierarchical structure.

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

2 major / 2 minor

Summary. The paper introduces a bilevel Late Acceptance Hill Climbing (b-LAHC) algorithm for the Electric Capacitated Vehicle Routing Problem (E-CVRP). It uses a hierarchical framework with a surrogate objective at the upper level to separate routing and charging decisions during search phases (greedy descent, neighborhood exploration, final refinement), while solving both levels jointly at the end. With fixed parameters and no complex adaptation, b-LAHC is tested on IEEE WCCI-2020 benchmarks, claiming competitive or superior results against eight state-of-the-art algorithms, including 9/10 new best-known solutions on large instances with 1.07% average improvement under fixed evaluation budget. The surrogate's strong (though not universal) correlation with complete cost is cited to justify the bilevel approach.

Significance. If the empirical claims hold under rigorous validation, this work offers a lightweight, fixed-parameter hierarchical method for E-CVRP that accelerates search via surrogates while preserving quality through joint refinement. The approach could generalize to other bilevel routing problems involving charging or resource decisions. Strengths include the explicit handling of level interactions and reported gains on large-scale instances, which address practical scalability in electric vehicle logistics.

major comments (2)
  1. [Abstract] Abstract: The central claim of setting 9/10 new best-known results and 1.07% average improvement on large-scale IEEE WCCI-2020 instances under fixed budget lacks any mention of run counts, statistical significance tests (e.g., Wilcoxon or t-tests), variance across runs, or exact comparison protocols against the eight prior algorithms; without these, the robustness of superiority cannot be assessed and the bilevel contribution remains hard to isolate from the base LAHC.
  2. [Abstract] Abstract and experimental results: The surrogate objective is qualified as having 'strong correlation (though not universal)' with the complete cost to justify the upper-level guidance; this directly bears on the premise that the bilevel structure accelerates convergence without quality loss, yet no quantitative correlation values, per-instance breakdowns, or analysis of failure cases are referenced, risking that observed gains stem mainly from the final joint refinement phase rather than the hierarchical surrogate mechanism.
minor comments (2)
  1. [Abstract] The abstract and introduction would benefit from a brief explicit statement of the fixed evaluation budget (e.g., number of solution evaluations) and how it is enforced uniformly across compared algorithms for reproducibility.
  2. Notation for the surrogate objective and its relation to the true cost function should be introduced earlier with a clear equation reference to aid readers in following the bilevel separation.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments, which help strengthen the presentation of our empirical results and the justification for the bilevel framework. We respond to each major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract: The central claim of setting 9/10 new best-known results and 1.07% average improvement on large-scale IEEE WCCI-2020 instances under fixed budget lacks any mention of run counts, statistical significance tests (e.g., Wilcoxon or t-tests), variance across runs, or exact comparison protocols against the eight prior algorithms; without these, the robustness of superiority cannot be assessed and the bilevel contribution remains hard to isolate from the base LAHC.

    Authors: We agree that the abstract would be improved by explicitly referencing the experimental protocol. The full manuscript specifies that all methods operate under the fixed evaluation budget defined by the IEEE WCCI-2020 benchmark, with results for b-LAHC averaged over multiple independent runs and direct comparisons drawn to the eight competing algorithms via their published best-known values. An ablation against standard LAHC is included to help isolate the bilevel contribution. We will revise the abstract to state the run count and fixed-budget protocol, and we will add a statistical significance analysis (including Wilcoxon signed-rank tests) to the experimental results section in the revised manuscript. revision: yes

  2. Referee: [Abstract] Abstract and experimental results: The surrogate objective is qualified as having 'strong correlation (though not universal)' with the complete cost to justify the upper-level guidance; this directly bears on the premise that the bilevel structure accelerates convergence without quality loss, yet no quantitative correlation values, per-instance breakdowns, or analysis of failure cases are referenced, risking that observed gains stem mainly from the final joint refinement phase rather than the hierarchical surrogate mechanism.

    Authors: We acknowledge that the current abstract and results section present the correlation only qualitatively. The manuscript does discuss the surrogate's role across search phases and notes that it is not universally correlated, thereby motivating the final joint-refinement step. We agree that quantitative metrics, instance-level breakdowns, and explicit treatment of weaker-correlation cases would better substantiate the bilevel contribution and rule out that gains arise solely from refinement. In the revision we will expand the experimental section with these details and update the abstract to reference the quantitative support for the surrogate-guided phases. revision: yes

Circularity Check

0 steps flagged

No significant circularity: performance claims rest on external benchmarks and empirical correlation checks

full rationale

The paper's central claims concern empirical performance of b-LAHC on the IEEE WCCI-2020 benchmark instances, measured against eight external state-of-the-art algorithms and existing best-known results. The surrogate upper-level objective is introduced after analyzing routing-charging interactions and is justified post-hoc by an observed (though qualified) correlation with the true complete cost; this correlation is an empirical measurement on the test instances rather than a definitional or fitted reduction. No equations or steps reduce the reported improvements to self-fitted parameters, self-citations, or ansatzes that presuppose the target result. The algorithm description (three-phase LAHC with fixed parameters) and bilevel separation are presented as design choices validated by external comparison, not derived tautologically from the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The central claim rests on standard assumptions of the vehicle routing problem domain and the empirical effectiveness of the proposed heuristic; no new free parameters, mathematical axioms, or invented entities are introduced beyond the algorithm design itself.

pith-pipeline@v0.9.0 · 5539 in / 1046 out tokens · 24781 ms · 2026-05-10T14:40:20.976636+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

38 extracted references · 38 canonical work pages

  1. [1]

    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

  2. [2]

    Toth and D

    P. Toth and D. Vigo,Vehicle routing: problems, methods, and applica- tions. SIAM, 2014

    work page 2014

  3. [3]

    A green vehicle routing problem,

    S. Erdo ˘gan and E. Miller-Hooks, “A green vehicle routing problem,” Transportation research part E: logistics and transportation review, vol. 48, no. 1, pp. 100–114, 2012

    work page 2012

  4. [4]

    Vehicle routing and location routing with intermediate stops: A review,

    M. Schiffer, M. Schneider, G. Walther, and G. Laporte, “Vehicle routing and location routing with intermediate stops: A review,”Transportation Science, vol. 53, no. 2, pp. 319–343, 2019

    work page 2019

  5. [5]

    Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions,

    A. Froger, J. E. Mendoza, O. Jabali, and G. Laporte, “Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions,”Computers & Operations Research, vol. 104, pp. 256–294, 2019

    work page 2019

  6. [6]

    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

  7. [7]

    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

  8. [8]

    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

  9. [9]

    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

  10. [10]

    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

  11. [11]

    The electric vehicle routing problem with nonlinear charging function,

    A. Montoya, C. Gu ´eret, J. E. Mendoza, and J. G. Villegas, “The electric vehicle routing problem with nonlinear charging function,” Transportation Research Part B: Methodological, vol. 103, pp. 87–110, 2017. JOURNAL TITLE 14

    work page 2017

  12. [12]

    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

  13. [13]

    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

  14. [14]

    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

  15. [15]

    A new formulation of the electric vehicle routing problem with time windows considering concave nonlinear charging function,

    X. Zuo, Y . Xiao, M. You, I. Kaku, and Y . Xu, “A new formulation of the electric vehicle routing problem with time windows considering concave nonlinear charging function,”Journal of Cleaner Production, vol. 236, p. 117687, 2019

    work page 2019

  16. [16]

    Electric vehicle routing problem with non-linear charging and load-dependent discharging,

    S. R. Kancharla and G. Ramadurai, “Electric vehicle routing problem with non-linear charging and load-dependent discharging,”Expert Sys- tems with Applications, vol. 160, p. 113714, 2020

    work page 2020

  17. [17]

    Exact approaches for routing capacitated electric vehicles,

    H. Tahami, G. Rabadi, and M. Haouari, “Exact approaches for routing capacitated electric vehicles,”Transportation Research Part E: Logistics and Transportation Review, vol. 144, p. 102126, 2020

    work page 2020

  18. [18]

    Branch-and-cut-and-price for the electric vehicle routing problem with time windows, piecewise- linear recharging and capacitated recharging stations,

    E. Lam, G. Desaulniers, and P. J. Stuckey, “Branch-and-cut-and-price for the electric vehicle routing problem with time windows, piecewise- linear recharging and capacitated recharging stations,”Computers & Operations Research, vol. 145, p. 105870, 2022

    work page 2022

  19. [19]

    Branch-price-and-cut for the electric vehicle routing problem with heterogeneous recharging technologies and nonlinear recharging functions,

    G. M. Nafstad, G. Desaulniers, and M. St ˚alhane, “Branch-price-and-cut for the electric vehicle routing problem with heterogeneous recharging technologies and nonlinear recharging functions,”Transportation Sci- ence, vol. 59, no. 3, pp. 628–646, 2025

    work page 2025

  20. [20]

    Evolutionary-based ant system algo- rithm to solve the dynamic electric vehicle routing problem

    S. Caillard and R. B. Chabane, “Evolutionary-based ant system algo- rithm to solve the dynamic electric vehicle routing problem.” inICORES, 2024, pp. 285–293

    work page 2024

  21. [21]

    Electric vehicle route optimization considering time-of-use electricity price by learnable partheno-genetic algorithm,

    H. Yang, S. Yang, Y . Xu, E. Cao, M. Lai, and Z. Dong, “Electric vehicle route optimization considering time-of-use electricity price by learnable partheno-genetic algorithm,”IEEE Transactions on smart grid, vol. 6, no. 2, pp. 657–666, 2015

    work page 2015

  22. [22]

    Hybrid electric vehicle routing problem with mode selection,

    L. Zhen, Z. Xu, C. Ma, and L. Xiao, “Hybrid electric vehicle routing problem with mode selection,”International Journal of Production Research, vol. 58, no. 2, pp. 562–576, 2020

    work page 2020

  23. [23]

    A heuristic ap- proach for the green vehicle routing problem with multiple technologies and partial recharges,

    ´A. Felipe, M. T. Ortu ˜no, G. Righini, and G. Tirado, “A heuristic ap- proach for the green vehicle routing problem with multiple technologies and partial recharges,”Transportation Research Part E: Logistics and Transportation Review, vol. 71, pp. 111–128, 2014

    work page 2014

  24. [24]

    Granular tabu search for the pickup and delivery problem with time windows and electric vehicles,

    D. Goeke, “Granular tabu search for the pickup and delivery problem with time windows and electric vehicles,”European Journal of Opera- tional Research, vol. 278, no. 3, pp. 821–836, 2019

    work page 2019

  25. [25]

    Multi-mode hybrid electric vehicle routing problem,

    M. Seyfi, M. Alinaghian, E. Ghorbani, B. C ¸ atay, and M. S. Sabbagh, “Multi-mode hybrid electric vehicle routing problem,”Transportation Research Part E: Logistics and Transportation Review, vol. 166, p. 102882, 2022

    work page 2022

  26. [26]

    A matheuristic method for the electric vehicle routing problem with time windows and fast chargers,

    M. Keskin and B. C ¸ atay, “A matheuristic method for the electric vehicle routing problem with time windows and fast chargers,”Computers & operations research, vol. 100, pp. 172–188, 2018

    work page 2018

  27. [27]

    The consistent electric-vehicle routing problem with backhauls and charging manage- ment,

    P. C. Nolz, N. Absi, D. Feillet, and C. Seragiotto, “The consistent electric-vehicle routing problem with backhauls and charging manage- ment,”European Journal of Operational Research, vol. 302, no. 2, pp. 700–716, 2022

    work page 2022

  28. [28]

    A new bilevel formu- lation for the vehicle routing problem and a solution method using a genetic algorithm,

    Y . Marinakis, A. Migdalas, and P. M. Pardalos, “A new bilevel formu- lation for the vehicle routing problem and a solution method using a genetic algorithm,”Journal of Global Optimization, vol. 38, pp. 555– 580, 2007

    work page 2007

  29. [29]

    A bi-level voronoi diagram-based metaheuristic for a large-scale multi-depot vehicle rout- ing problem,

    W. Tu, Z. Fang, Q. Li, S.-L. Shaw, and B. Chen, “A bi-level voronoi diagram-based metaheuristic for a large-scale multi-depot vehicle rout- ing problem,”Transportation Research Part E: Logistics and Trans- portation Review, vol. 61, pp. 84–97, 2014

    work page 2014

  30. [30]

    A heuristic algorithm for the vehicle- dispatch problem,

    B. E. Gillett and L. R. Miller, “A heuristic algorithm for the vehicle- dispatch problem,”Operations research, vol. 22, no. 2, pp. 340–349, 1974

    work page 1974

  31. [31]

    Bilevel memetic search approach to the soft-clustered vehicle routing problem,

    Y . Zhou, Y . Kou, and M. Zhou, “Bilevel memetic search approach to the soft-clustered vehicle routing problem,”Transportation Science, vol. 57, no. 3, pp. 701–716, 2023

    work page 2023

  32. [32]

    Order-first split-second methods for vehicle routing problems: A review,

    C. Prins, P. Lacomme, and C. Prodhon, “Order-first split-second methods for vehicle routing problems: A review,”Transportation Research Part C: Emerging Technologies, vol. 40, pp. 179–200, 2014

    work page 2014

  33. [33]

    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

  34. [34]

    A simple and effective evolutionary algorithm for the vehicle routing problem,

    C. Prins, “A simple and effective evolutionary algorithm for the vehicle routing problem,”Computers & operations research, vol. 31, no. 12, pp. 1985–2002, 2004

    work page 1985

  35. [35]

    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

  36. [36]

    A greedy search based evolutionary algorithm for electric vehicle routing problem,

    V . Q. Hien, T. C. Dao, and H. T. T. Binh, “A greedy search based evolutionary algorithm for electric vehicle routing problem,”Applied Intelligence, vol. 53, no. 3, pp. 2908–2922, 2023

    work page 2023

  37. [37]

    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

  38. [38]

    A cutoff time strategy based on the coupon collector’s problem,

    F. G. Lobo, M. Bazargani, and E. K. Burke, “A cutoff time strategy based on the coupon collector’s problem,”European Journal of Operational Research, vol. 286, no. 1, pp. 101–114, 2020

    work page 2020