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

cs.AIApr 14, 2026

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

Authors: Yinghao Qin, Mosab Bazargani, Edmund K. Burke, Carlos A. Coello Coello, Zhongmin Song, Jun Chen

Organizations: Centre for Intelligent Transport, QMUL, London, U.K. · School of Computer Science and Engineering, Bangor University, Bangor, U.K. · Department of Computer Science, Evolutionary Computation Group, CINVESTAV-IPN, Mexico City, Mexico. · Basque Center for Applied Mathematics & Ikerbasque, Spain. ·

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.

Figures & tables

Panel of Figure 1 — Fig. 1: Illustrative solution to the E-CVRP, featuring one depot, four charging stations, and ten customer locations.

	Symbol	Description
General	$G=(V,A)$	Complete graph representing the E-CVRP instance.
	$V=\{d\}\cup\mathcal{V}_{c}\cup\mathcal{V}_{f}$	Node set consisting of the depot $d$ , customer set $\mathcal{V}_{c}$ , and charging station set $\mathcal{V}_{f}$ .
	$A=\{(i,j)\mid i\neq j,\ i,j\in V\}$	Set of arcs representing all possible connections between distinct nodes.
	$\delta_{i}$	Demand of customer $i\in\mathcal{V}_{c}$ . ( $\delta_{i}>0$ )
	$d_{ij}$	Distance between nodes $i$ and $j$ , for all $(i,j)\in A$ . ( $d_{ij}\geq 0$ )
	$h$	Battery consumption rate per unit distance. ( $h>0$ )

TABLE I: Summary of notation used in the bilevel E-CVRP model.

Fig. 2: An illustrative example of a solution representation for the E-CVRP.

Panel of Figure 4 — Fig. 3: The eight move operators illustrated by simplified route segments.

name	$\|\mathcal{V}_{c}\|$	$\|\mathcal{V}_{f}\|$	$M$	$Q_{c}$	$Q_{b}$	$h$	$UB$
E22	21	8	4	6000	94	1.2	384.67
E23	22	9	3	4500	190	1.2	573.13
E30	29	6	4	4500	178	1.2	511.25
E33	32	6	4	8000	209	1.2	869.89
E51	50	5	5	160	105	1.2	570.17
E76	75	7	7	220	98	1.2	723.36

TABLE II: Details of the IEEE WCCI-2020 benchmark set

Methods	Stop Criteria	Language/Tool	Code Available
MILP [ 1 ]	Max Evals	Gurobi	No
VNS [ 35 ]	Max Evals	C++	Yes
SA	Max Evals	C++	No
GA [ 36 ]	Max Evals	C++	Yes
HHASA-TS [ 8 ]	Max Evals	MATLAB	Yes
BACO [ 6 ]	Max Time	C++	Yes

TABLE III: Overview of Methods for the WCCI-2020 EVRP Benchmark

Parameter	Description	Value
$L_{h}$	History length	5723
$\eta_{\max}$	Maximum attempts	60
$\gamma$	Follower activation threshold	1.01

TABLE IV: Main parameters of the b-LAHC algorithm

Instance	#Samples	$\boldsymbol{\tau_{b}}$	Recall@1%	Recall@5%	Recall@10%	Recall@20%
E22	60,163	0.9245	0.7425	0.8136	0.8764	0.9253
E23	100,717	0.9646	0.8978	0.9255	0.9387	0.9646
E30	182,830	0.9750	0.9043	0.9354	0.9567	0.9745
E33	115,460	0.9529	0.8823	0.9531	0.9671	0.9792
E51	391,533	0.9802	0.7439	0.9279	0.9631	0.9814
E76	712,352	0.9755	0.7650	0.8990	0.9157	0.9676

TABLE V: Rank correlation and Top-

k

% set overlap between

\phi(x)

and

F(x,y^{*}(x))

Instance	Index	BKS	VNS	SA	GA	HHASA-TS	BACO	CBACO-I	CBMA	b-LAHC	Gap
E22	best	384.67	384.67	384.67	384.67	384.67	384.67	384.67	384.67	384.67	–
	mean	384.67	384.67	384.67	384.67	384.67	384.67	384.67	384.67	385.25	0.15%
	std.	–	2.11	0.00	0.00	0.00	0.00	0.00	0.00	0.28	–
E23	best	571.94	571.94	571.94	571.94	571.94	571.94	571.94	571.94	571.94	–
	mean	571.94	571.94	571.94	571.94	571.94	571.94	571.94	571.94	571.94	0.00%
	std.	–	0.00	0.00	0.00	0.00	0.00	0.00	0.00	0.00	–

TABLE VI: Objective value comparison with state-of-the-art algorithms using the Max Evals stop criterion

Fig. 4: Convergence trends on the large-scale instances.

Instance	Index	Baseline	Remove $\mathcal{G}$		Remove $\mathcal{F}$		$\gamma=0$
Instance	Index	Baseline	Obj	Gap	Obj	Gap	Obj	Gap
E22	best	384.67	384.67	–	384.67	–	385.39	–
	mean	385.25	384.96	-0.08%	385.25	0.00%	394.81	2.48%
	std.	0.28	0.35	–	0.30	–	13.61	–
E23	best	571.94	571.94	–	571.94	–	571.94	–
	mean	571.94	571.94	0.00%	571.94	0.00%	579.39	1.30%

TABLE VII: Ablation study on the effects of Greedy Descent (

\mathcal{G}

), Charging Refinement (

\mathcal{F}

), and Bilevel framework

Fig. 5: Comparative solution with and without M8 operator on E30.

Vehicle Routing

Vehicle routing studies how to assign and sequence trips for fleets while meeting capacity, time, energy, and service constraints.

See all 135 papers

Instance-Aware Parameter Configuration in Bilevel Late Acceptance Hill Climbing for the Electric Capacitated Vehicle Routing Problem
May 1, 2026Yinghao Qin, Xinwei Wang, Mosab Bazargani +1Metaheuristic Optimization Vehicle Routing
Centre for Intelligent Transport Queen Mary, University of London London, UK · School of Computer Science and Engineering Bangor University Bangor, UK
Enhancing CVRP Solver through LLM-driven Automatic Heuristic Design
Feb 26, 2026Zhuoliang Xie, Fei Liu, Zhenkun Wang +1Vehicle Routing Automated Heuristic Design
Southern University of Science and Technology · City University of Hong Kong
Adaptive Operator Selection in Bilevel Large Neighborhood Search for Electric Autonomous Dial-a-Ride Problem under Uncertainty
Oct 3, 2026Ishara Hewa Pathiranange, Aneta NeumannVehicle Routing Large Neighborhood Search
Machine Learning and Optimisation, School of Computer Science and Information Technology, Adelaide University, Adelaide, Australia

May 1, 2026J/K move · Enter open · S save

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

Centre for Intelligent Transport Queen Mary, University of London London, UK · School of Computer Science and Engineering Bangor University Bangor, UK

Metaheuristic Optimization Vehicle Routing Hyperparameter Optimization

Open paper AskPDF arXiv

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.

Abstract

Vehicle Routing

Explore similar work

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

Enhancing CVRP Solver through LLM-driven Automatic Heuristic Design

Adaptive Operator Selection in Bilevel Large Neighborhood Search for Electric Autonomous Dial-a-Ride Problem under Uncertainty