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

Ishara Hewa Pathiranange; Aneta Neumann

cs.NEOct 3, 2026

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

Authors: Ishara Hewa Pathiranange, Aneta Neumann

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

Abstract

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.

Figures & tables

Variant	State	History	Selection
BI-LNS-Greedy	No	No	Fixed greedy
BI-LNS-Regret	No	No	Fixed regret- $k$
BI-LNS-Random	No	No	Uniform random
BI-LNS-Rule	Yes	No	Fixed thresholds
BI-LNS-ALNS	No	Yes	Adaptive weights
BI-LNS-LLM	Yes	No	Model preference

Table 1: Insertion-operator selection strategies.

Feature	Definition
rejected	Number of currently rejected requests.
rejected_ratio	Ratio of rejected requests to all requests.
delta_rejected	Normalized change in the rejected-request count from the previous iteration.
delta_obj	Normalized objective improvement from the previous iteration.
stagnation	Normalized number of consecutive iterations without improvement.
progress	Fraction of completed inner-search iterations.

Table 2: Search-state features supplied to the LLM selector.

Figure 1: Role of the LLM selector in the BI-LNS inner-level repair process.

Instance	BI-LNS-Greedy [ 18 ]				BI-LNS-Regret				BI-LNS-Random				BI-LNS-Rule				BI-LNS-ALNS				BI-LNS-LLM
Instance	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.
a2-16	$257.6$	$258.0$	$0.4$	10/10	$256.4$	$257.6$	$0.8$	10/10	$256.6$	$\mathbf{257.4}$	$0.5$	10/10	$256.7$	$257.9$	$0.7$	10/10	$256.5$	$258.1$	$0.8$	10/10	$257.3$	$257.9$	$0.6$	10/10
a3-18	$250.1$	$\mathbf{250.3}$	$0.1$	10/10	$250.3$	$\mathbf{250.3}$	$0.0$	10/10	$250.1$	$\mathbf{250.3}$	$0.1$	10/10	$250.1$	$\mathbf{250.3}$	$0.1$	10/10	$250.2$	$\mathbf{250.3}$	$0.1$	10/10	$250.1$	$\mathbf{250.3}$	$0.1$	10/10
a3-24	$276.3$	$276.3$	$0.0$	10/10	$275.2$	$276.2$	$0.3$	10/10	$275.2$	$276.2$	$0.3$	10/10	$275.2$	$276.2$	$0.3$	10/10	$275.2$	$\mathbf{275.9}$	$0.5$	10/10	$276.3$	$276.3$	$0.0$	10/10
a4-16	$226.8$	$227.4$	$0.8$	10/10	$226.8$	$227.4$	$0.8$	10/10	$226.8$	$227.3$	$0.8$	10/10	$226.8$	$\mathbf{227.0}$	$0.5$	10/10	$226.8$	$\mathbf{227.0}$	$0.5$	10/10	$226.8$	$227.5$	$0.7$	10/10
a4-24	$322.8$	$324.5$	$3.8$	10/10	$322.4$	$\mathbf{322.8}$	$0.2$	10/10	$322.4$	$\mathbf{322.8}$	$0.2$	10/10	$322.4$	$\mathbf{322.8}$	$0.2$	10/10	$322.8$	$322.9$	$0.1$	10/10	$322.8$	$323.0$	$0.1$	10/10

Table 3: Final best feasible objective values for the deterministic EADARP on the Cordeau and Ropke instances with

\gamma=0.7

. For each method, we report the minimum, mean, and standard deviation over the feasible runs among 10 independent runs, together with the feasibility count. Best conditional mean values per instance are highlighted in bold. NA indicates that no feasible run was obtained, and - indicates that the standard deviation is undefined because only one feasible run was obtained.

Figure 2: Mean objective values over feasible runs for the Ropke instances under different minimum final battery ratios $\gamma\in\{0.2,0.4,0.5,0.7,0.8,0.9\}$ . Colours are scaled independently within each instance. Rows represent BI-LNS variants and columns represent battery levels. Lower values are better, and - indicates that no feasible run was obtained.

Panel of Figure 3 — Figure 3: Convergence behavior over time on representative hard instances (a6-72 and a7-84), comparing BI-LNS-Greedy, BI-LNS-ALNS, and BI-LNS-LLM. The plots show median best feasible objective values over 10 runs with IQR bands. Only feasible solutions are considered; curves start at the first feasible solution.

Instance	$\alpha$	$\gamma=0.4$									$\gamma=0.7$
		BI-LNS-Greedy [ 18 ]			BI-LNS-ALNS			BI-LNS-LLM			BI-LNS-Greedy [ 18 ]			BI-LNS-ALNS			BI-LNS-LLM
		Mean	Std	Feas.	Mean	Std	Feas.	Mean	Std	Feas.	Mean	Std	Feas.	Mean	Std	Feas.	Mean	Std	Feas.
a3-18	0.99	$\mathbf{253.1}$	$0.0$	10/10	$\mathbf{253.1}$	$0.0$	10/10	$\mathbf{253.1}$	$0.0$	10/10	$\mathbf{255.1}$	$2.2$	10/10	$255.2$	$1.9$	10/10	$255.3$	$2.0$	10/10
	0.9999	$\mathbf{255.7}$	$0.0$	10/10	$\mathbf{255.7}$	$0.0$	10/10	$\mathbf{255.7}$	$0.0$	10/10	$258.5$	$2.3$	10/10	$\mathbf{257.8}$	$1.9$	10/10	$\mathbf{257.8}$	$1.9$	10/10
	0.999999	$\mathbf{255.7}$	$0.0$	10/10	$\mathbf{255.7}$	$0.0$	10/10	$\mathbf{255.7}$	$0.0$	10/10	$\mathbf{257.9}$	$2.0$	10/10	$258.8$	$2.6$	10/10	$258.1$	$1.8$	10/10
a3-24	0.99	$278.9$	$1.4$	10/10	$279.9$	$2.2$	10/10	$\mathbf{278.5}$	$1.2$	10/10	$282.4$	$3.5$	10/10	$\mathbf{280.3}$	$2.3$	10/10	$281.3$	$3.8$	10/10

Table 4: Final best feasible objective values for the chance-constrained EADARP with

CV=0.1

and

\gamma\in\{0.4,0.7\}

. For each method and confidence level

\alpha

, we report the mean and standard deviation over the feasible runs among 10 independent runs, together with the feasibility count. Best conditional mean values per

(\text{instance},\gamma,\alpha)

combination are highlighted in bold.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Instance	BI-LNS-Greedy				BI-LNS-Regret				BI-LNS-Random				BI-LNS-Rule				BI-LNS-ALNS				BI-LNS-LLM
	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.
a5-60	$723.9$	$\mathbf{731.7}$	$4.3$	10/10	$726.0$	$731.8$	$3.2$	10/10	$724.7$	$733.5$	$8.9$	10/10	$727.5$	$733.5$	$4.1$	10/10	$724.9$	$732.4$	$4.5$	10/10	$726.3$	$732.2$	$6.2$	10/10
a6-48	$522.9$	$525.6$	$1.9$	10/10	$522.0$	$524.3$	$3.4$	10/10	$521.8$	$524.5$	$2.3$	10/10	$522.0$	$\mathbf{523.1}$	$1.5$	10/10	$522.0$	$523.7$	$2.1$	10/10	$521.8$	$523.7$	$2.1$	10/10
a6-60	$720.0$	$\mathbf{726.3}$	$4.4$	10/10	$723.9$	$727.4$	$2.5$	10/10	$721.1$	$726.5$	$4.0$	10/10	$724.3$	$728.0$	$3.9$	10/10	$722.8$	$728.5$	$5.0$	10/10	$722.1$	$726.4$	$4.9$	10/10
a6-72	$829.5$	$840.6$	$9.5$	10/10	$828.1$	$836.6$	$5.8$	10/10	$828.8$	$837.0$	$6.0$	10/10	$824.7$	$839.3$	$10.9$	10/10	$830.0$	$835.4$	$3.4$	10/10	$827.0$	$\mathbf{835.2}$	$6.7$	10/10
a7-56	$635.4$	$640.3$	$4.1$	10/10	$634.2$	$\mathbf{636.8}$	$2.6$	10/10	$632.1$	$640.2$	$4.5$	10/10	$633.1$	$637.8$	$2.6$	10/10	$635.9$	$638.4$	$2.8$	10/10	$634.4$	$637.2$	$2.0$	10/10

Appendix

Table 5: Final best feasible objective values for Ropke instances for unlimited CS visits (

\gamma=0.2

Instance	BI-LNS-Greedy				BI-LNS-Regret				BI-LNS-Random				BI-LNS-Rule				BI-LNS-ALNS				BI-LNS-LLM
	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.
a5-60	$731.1$	$738.9$	$7.6$	10/10	$728.6$	$737.2$	$5.4$	10/10	$728.6$	$739.8$	$9.5$	10/10	$731.3$	$739.0$	$4.4$	10/10	$726.8$	$741.2$	$8.1$	10/10	$731.4$	$\mathbf{736.0}$	$3.2$	10/10
a6-48	$521.8$	$524.0$	$1.6$	10/10	$522.0$	$523.8$	$1.5$	10/10	$522.9$	$524.7$	$0.9$	10/10	$521.8$	$\mathbf{523.4}$	$1.5$	10/10	$521.8$	$523.5$	$1.0$	10/10	$521.8$	$524.2$	$1.6$	10/10
a6-60	$722.6$	$728.1$	$4.3$	10/10	$721.4$	$727.8$	$3.7$	10/10	$720.8$	$\mathbf{726.7}$	$4.0$	10/10	$722.6$	$727.2$	$2.7$	10/10	$725.9$	$731.1$	$3.6$	10/10	$722.2$	$730.3$	$4.9$	10/10
a6-72	$834.6$	$844.8$	$8.1$	10/10	$835.2$	$846.2$	$7.5$	10/10	$837.0$	$847.1$	$7.6$	10/10	$830.7$	$\mathbf{842.3}$	$7.3$	10/10	$838.1$	$848.5$	$7.7$	10/10	$831.1$	$846.0$	$11.4$	10/10
a7-56	$633.5$	$639.4$	$3.6$	10/10	$633.5$	$637.7$	$3.5$	10/10	$634.2$	$636.5$	$2.0$	10/10	$632.5$	$638.9$	$4.8$	10/10	$634.4$	$638.2$	$4.2$	10/10	$631.8$	$\mathbf{636.2}$	$2.9$	10/10

Appendix

Table 6: Final best feasible objective values for Ropke instances for unlimited CS visits (

\gamma=0.4

Instance	BI-LNS-Greedy				BI-LNS-Regret				BI-LNS-Random				BI-LNS-Rule				BI-LNS-ALNS				BI-LNS-LLM
	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.
a5-60	$741.8$	$759.1$	$10.9$	10/10	$733.0$	$758.6$	$20.8$	10/10	$731.4$	$751.8$	$13.5$	10/10	$735.4$	$744.6$	$6.0$	10/10	$732.7$	$\mathbf{744.0}$	$6.7$	10/10	$738.0$	$748.3$	$6.5$	10/10
a6-48	$523.8$	$526.4$	$2.3$	10/10	$521.8$	$524.0$	$1.7$	10/10	$522.0$	$525.9$	$2.9$	10/10	$522.3$	$524.7$	$2.0$	10/10	$521.8$	$\mathbf{523.9}$	$1.4$	10/10	$522.3$	$525.9$	$2.6$	10/10
a6-60	$733.1$	$738.8$	$4.4$	10/10	$724.6$	$735.8$	$8.0$	10/10	$728.3$	$734.1$	$4.2$	10/10	$725.4$	$733.6$	$5.7$	10/10	$724.4$	$\mathbf{731.3}$	$4.8$	10/10	$727.1$	$732.5$	$3.4$	10/10
a6-72	$840.1$	$\mathbf{851.9}$	$9.6$	9/10	$841.1$	$859.4$	$12.5$	10/10	$844.8$	$852.9$	$6.7$	10/10	$840.2$	$860.0$	$11.1$	10/10	$844.4$	$860.8$	$12.9$	10/10	$845.8$	$861.4$	$8.8$	10/10
a7-56	$633.5$	$637.2$	$2.5$	10/10	$631.7$	$\mathbf{636.2}$	$3.2$	10/10	$633.2$	$638.7$	$3.1$	10/10	$633.3$	$637.4$	$3.3$	10/10	$634.5$	$638.0$	$3.1$	10/10	$635.2$	$638.2$	$3.1$	10/10

Appendix

Table 7: Final best feasible objective values for Ropke instances for unlimited CS visits (

\gamma=0.5

Instance	BI-LNS-Greedy				BI-LNS-Regret				BI-LNS-Random				BI-LNS-Rule				BI-LNS-ALNS				BI-LNS-LLM
	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.
a5-60	$770.5$	$794.8$	$30.6$	8/10	$769.6$	$782.3$	$16.5$	8/10	$753.1$	$779.7$	$15.0$	8/10	$756.4$	$783.5$	$15.0$	9/10	$755.9$	$\mathbf{776.6}$	$17.2$	10/10	$770.3$	$790.3$	$21.5$	8/10
a6-48	$528.6$	$534.6$	$5.1$	10/10	$527.6$	$534.6$	$4.8$	10/10	$527.7$	$535.2$	$5.0$	10/10	$529.8$	$533.1$	$3.2$	10/10	$530.4$	$537.0$	$5.0$	10/10	$527.6$	$\mathbf{532.9}$	$2.4$	10/10
a6-60	$738.4$	$755.2$	$15.2$	10/10	$741.7$	$757.3$	$10.2$	10/10	$743.1$	$753.3$	$11.0$	10/10	$739.7$	$754.2$	$19.6$	10/10	$743.2$	$\mathbf{752.3}$	$7.2$	10/10	$741.6$	$758.7$	$15.1$	10/10
a6-72	$874.1$	$888.7$	$18.3$	5/10	$875.2$	$894.5$	$16.5$	8/10	$877.8$	$899.5$	$15.5$	10/10	$859.8$	$891.5$	$19.6$	10/10	$859.4$	$901.9$	$29.4$	9/10	$867.6$	$\mathbf{888.6}$	$18.8$	9/10
a7-56	$647.4$	$667.5$	$13.7$	10/10	$651.7$	$661.2$	$5.1$	10/10	$646.0$	$\mathbf{658.5}$	$6.3$	10/10	$649.0$	$665.9$	$13.2$	10/10	$656.9$	$667.2$	$11.7$	10/10	$653.8$	$666.0$	$8.2$	10/10

Appendix

Table 8: Final best feasible objective values for Ropke instances for unlimited CS visits (

\gamma=0.7

Instance	BI-LNS-Greedy				BI-LNS-Regret				BI-LNS-Random				BI-LNS-Rule				BI-LNS-ALNS				BI-LNS-LLM
	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.
a5-60	NA	NA	NA	0/10	NA	NA	NA	0/10	$781.9$	$798.7$	$23.7$	2/10	$781.9$	$781.9$	-	1/10	$778.1$	$\mathbf{778.9}$	$1.1$	2/10	$801.3$	$829.2$	$39.5$	2/10
a6-48	$537.0$	$548.1$	$10.0$	10/10	$533.3$	$543.6$	$7.5$	10/10	$536.3$	$544.1$	$7.0$	10/10	$535.3$	$\mathbf{542.6}$	$3.7$	10/10	$535.7$	$543.9$	$6.0$	10/10	$538.5$	$552.0$	$14.9$	10/10
a6-60	$754.7$	$782.8$	$25.4$	9/10	$748.1$	$765.0$	$15.0$	10/10	$747.8$	$\mathbf{764.0}$	$10.3$	10/10	$750.7$	$764.8$	$9.0$	10/10	$759.3$	$775.4$	$17.6$	10/10	$749.5$	$773.5$	$20.7$	10/10
a6-72	$928.6$	$929.7$	$1.7$	2/10	$864.0$	$922.6$	$48.2$	5/10	$861.4$	$\mathbf{910.8}$	$32.4$	6/10	$901.6$	$914.1$	$11.9$	3/10	$900.2$	$922.2$	$19.2$	5/10	$913.1$	$920.9$	$11.1$	2/10
a7-56	$685.4$	$710.4$	$19.0$	7/10	$655.9$	$692.9$	$23.1$	8/10	$670.9$	$697.6$	$18.3$	7/10	$684.7$	$712.9$	$25.1$	5/10	$673.7$	$\mathbf{689.7}$	$13.5$	7/10	$682.6$	$708.4$	$16.0$	7/10

Appendix

Table 9: Final best feasible objective values for Ropke instances for unlimited CS visits (

\gamma=0.8

Instance	BI-LNS-Greedy				BI-LNS-Regret				BI-LNS-Random				BI-LNS-Rule				BI-LNS-ALNS				BI-LNS-LLM
	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.	Min	Mean	Std	Feas.
a5-60	NA	NA	NA	0/10	NA	NA	NA	0/10	$801.5$	$801.5$	-	1/10	NA	NA	NA	0/10	NA	NA	NA	0/10	NA	NA	NA	0/10
a6-48	$554.8$	$567.2$	$12.2$	6/10	$551.5$	$567.6$	$11.5$	8/10	$554.0$	$566.2$	$9.2$	9/10	$551.4$	$571.1$	$20.7$	8/10	$555.0$	$570.4$	$10.4$	8/10	$551.9$	$\mathbf{564.6}$	$7.5$	8/10
a6-60	$779.7$	$786.6$	$6.8$	7/10	$768.9$	$\mathbf{780.7}$	$8.9$	5/10	$777.3$	$792.7$	$20.4$	6/10	$768.0$	$783.5$	$12.2$	8/10	$760.2$	$787.1$	$21.4$	10/10	$763.4$	$782.1$	$20.6$	5/10
a6-72	NA	NA	NA	0/10	NA	NA	NA	0/10	$946.8$	$946.8$	-	1/10	NA	NA	NA	0/10	NA	NA	NA	0/10	NA	NA	NA	0/10
a7-56	$737.6$	$737.6$	-	1/10	NA	NA	NA	0/10	$729.9$	$729.9$	-	1/10	NA	NA	NA	0/10	NA	NA	NA	0/10	NA	NA	NA	0/10

Appendix

Table 10: Final best feasible objective values for Ropke instances for unlimited CS visits (

\gamma=0.9

Instance	$\alpha$	$\gamma=0.4$									$\gamma=0.7$
		BI-LNS-Greedy			BI-LNS-ALNS			BI-LNS-LLM			BI-LNS-Greedy			BI-LNS-ALNS			BI-LNS-LLM
		Mean	Std	Feas.	Mean	Std	Feas.	Mean	Std	Feas.	Mean	Std	Feas.	Mean	Std	Feas.	Mean	Std	Feas.
a3-18	0.99	$\mathbf{263.2}$	$0.0$	10/10	$\mathbf{263.2}$	$0.0$	10/10	$\mathbf{263.2}$	$0.0$	10/10	$\mathbf{265.1}$	$0.0$	10/10	$\mathbf{265.1}$	$0.0$	10/10	$\mathbf{265.1}$	$0.0$	10/10
	0.9999	-	-	0/10	-	-	0/10	-	-	0/10	-	-	0/10	-	-	0/10	-	-	0/10
	0.999999	-	-	0/10	-	-	0/10	-	-	0/10	-	-	0/10	-	-	0/10	-	-	0/10
a4-24	0.99	$\mathbf{342.4}$	$0.0$	10/10	$\mathbf{342.4}$	$0.0$	10/10	$\mathbf{342.4}$	$0.0$	10/10	$363.8$	$6.4$	4/10	$357.5$	$5.0$	5/10	$\mathbf{357.3}$	$5.4$	3/10

Appendix

Table 11: Final best feasible objective values for the chance-constrained EADARP under

CV=0.3

and

\gamma\in\{0.4,0.7\}

. For each method and confidence level

\alpha

, the mean and standard deviation over 10 runs are reported together with the feasibility rate (feasible runs / total runs). Best mean values per (instance,

\gamma

\alpha

) combination are highlighted in bold.

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

Bilevel Late Acceptance Hill Climbing for the Electric Capacitated Vehicle Routing Problem
Apr 14, 2026Yinghao Qin, Mosab Bazargani, Edmund K. Burke +3Vehicle Routing Bilevel Optimization
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. +2
Learning to Route Electric Trucks Under Operational Uncertainty
Apr 29, 2026Stavros Orfanoudakis, Ziyan Li, Ruixiao Yang +4Sequential Decision Making Electric Vehicle Charging
Delft University of Technology, Intelligent Electrical Power Grids, Delft, The Netherlands · Massachusetts Institute of Technology, Center of Transportation and Logistics, Cambridge, MA, United States of America · Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, Cambridge, MA, United States of America
Selective Ambulance Dispatch Under Contextual Travel-Time Uncertainty
May 22, 2026Zikun Lin, Daniel Zhuoyu Long, Viet Anh Nguyen
Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong

Apr 14, 2026J/K move · Enter open · S save

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

Yinghao Qin, Mosab Bazargani, Edmund K. Burke, Carlos A. Coello Coello+2

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.+2

Vehicle Routing Bilevel Optimization Electric Vehicle Charging

Open paper AskPDF arXiv

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.

Abstract

Vehicle Routing

Explore similar work

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

Learning to Route Electric Trucks Under Operational Uncertainty

Selective Ambulance Dispatch Under Contextual Travel-Time Uncertainty