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

May 1, 2026

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

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.

Yinghao Qin, Xinwei Wang, Mosab Bazargani +1

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

Ask PDF

Feb 26, 2026

Enhancing CVRP Solver through LLM-driven Automatic Heuristic Design

The Capacitated Vehicle Routing Problem (CVRP), a fundamental combinatorial optimization challenge, focuses on optimizing fleet operations under vehicle capacity constraints. While extensively studied in operational research, the NP-hard nature of CVRP continues to pose significant computational challenges, particularly for large-scale instances. This study presents AILS-AHD (Adaptive Iterated Local Search with Automatic Heuristic Design), a novel approach that leverages Large Language Models (LLMs) to revolutionize CVRP solving. Our methodology integrates an evolutionary search framework with LLMs to dynamically generate and optimize ruin heuristics within the AILS method. Additionally, we introduce an LLM-based acceleration mechanism to enhance computational efficiency. Comprehensive experimental evaluations against state-of-the-art solvers, including AILS-II and HGS, demonstrate the superior performance of AILS-AHD across both moderate and large-scale instances. Notably, our approach establishes new best-known solutions for 8 out of 10 instances in the CVRPLib large-scale benchmark, underscoring the potential of LLM-driven heuristic design in advancing the field of vehicle routing optimization.

Zhuoliang Xie, Fei Liu, Zhenkun Wang +1

Southern University of Science and Technology · City University of Hong Kong

Vehicle Routing Automated Heuristic Design Metaheuristic Optimization Large Language Model-Guided Optimization

Ask PDF

Oct 3, 2026

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

The electric autonomous dial-a-ride problem (EADARP) extends the classical dial-a-ride problem by incorporating battery and charging constraints for electric vehicles. In practice, travel-time uncertainty can cause violations of time-window constraints. Large neighborhood search is effective for solving the EADARP, but its performance can depend on the choice of insertion operator during the repair phase. This paper investigates insertion-operator selection within a bilevel large neighborhood search framework for deterministic and chance-constrained variants of the EADARP. In the chance-constrained variant, arc travel times are modeled as independent normally distributed random variables, and upper time-window constraints are enforced probabilistically. We consider six selection methods, namely fixed greedy insertion, fixed regret-based insertion, random selection, a deterministic state-based rule, performance-adaptive ALNS selection, and LLM-based state-aware selection. Experimental results show comparable performance on smaller instances, while differences become more evident on larger and more constrained instances. There is no single strategy that performs best across all instances, and the relative performance of the LLM-based, rule-based, and ALNS strategies varies with the problem instance and experimental setting.

Ishara Hewa Pathiranange, Aneta Neumann

Machine Learning and Optimisation, School of Computer Science and Information Technology, Adelaide University, Adelaide, Australia

Vehicle Routing Large Neighborhood Search

Ask PDF

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