A hybrid adaptive large neighborhood search algorithm for two-echelon electric vehicle routing problem

Abstract

The efficient management of urban logistics is important for smart production and service systems, requiring coordinated optimization and planning for sustainable and responsive operations. This study investigates a two-echelon electric vehicle routing problem with time windows (2E-EVRPTW), an important optimization problem in urban delivery networks. The problem involves using fuel-powered trucks for the first-echelon transport from a warehouse to satellites and electric vehicles (EVs) with limited range and charging needs for the second-echelon, time-sensitive last-mile delivery. To tackle this NP-hard problem, we first formulate it as a mixed-integer linear programming (MIP) model. We then propose a hybrid heuristic algorithm, CL-ALNS, which integrates clustering and adaptive metaheuristic search. Specifically, CL-ALNS combines K-means clustering for strategic facility allocation in the first echelon with an adaptive large neighborhood search (ALNS) to support routing and charging scheduling in the second echelon. This algorithm is designed to reduce total cost while obtaining efficient, high-quality solutions. Computational experiments and benchmarks against a commercial solver and heuristic baselines show that our CL-ALNS framework obtains competitive results under the tested settings. Furthermore, sensitivity analysis examines how key operational parameters influence the system, providing valuable insights for managers of smart logistics services.