AI summaryⓘ
The authors study a problem where electric vehicles need to be routed efficiently while managing their charging, called the Electric Capacitated Vehicle Routing Problem (E-CVRP). They propose a two-level approach that separates routing and charging decisions but also looks at how they affect each other. Their method, called b-LAHC, uses a simple and stable algorithm that works in phases to find good solutions quickly. Tests show their approach matches or beats current top methods, especially on large problems, and their strategy of using a simpler surrogate measure helps guide the search effectively. This work suggests their two-level framework is a promising way to handle complex routing problems with charging needs.
Electric Capacitated Vehicle Routing Problembilevel optimizationroutingcharging decisionsLate Acceptance Hill Climbingsurrogate objectivebenchmarklarge-scale optimizationgreedy descent
Authors
Yinghao Qin, Mosab Bazargani, Edmund K. Burke, Carlos A. Coello Coello, Zhongmin Song, Jun Chen
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.