Adaptive Large Neighborhood Search Algorithm for Electric Vehicle Routing Problem with Capacitated Charging Stations and Queueing

Abstract

With growing emphasis on green and low-carbon development and rising urban delivery demand, electric vehicles (EVs) have been increasingly adopted in logistics distribution systems. However, their limited driving range, relatively long charging durations, and the limited capacity of charging stations pose substantial challenges to real-world electric delivery operations. When multiple vehicles arrive at a station with a limited number of chargers, queueing delays may disrupt subsequent customer service and increase total operating costs. To address this issue, this study investigates an electric vehicle routing problem with capacitated charging stations and queueing delays. A mixed-integer linear programming model is formulated, and an enhanced adaptive large neighborhood search (ALNS) algorithm is developed to efficiently solve medium- and large-scale instances. In the proposed model, each vehicle visit to a charging station is represented as a charging event, while finite station capacity is enforced through charging-event assignment and temporal non-overlap constraints. Computational results show that the enhanced ALNS matches the proven optimal solution for the 10-customer instance. For the 15- and 20-customer instances, the best objective values obtained by the enhanced ALNS were 0.39% and 4.84% lower than the corresponding time-limited Gurobi incumbents, respectively. For the 30-, 50-, and 100-customer instances, the enhanced ALNS consistently generates feasible solutions within the prescribed computational budget, whereas Gurobi does not obtain a feasible incumbent within substantially longer time limits. Compared with the baseline ALNS, the enhanced version generally achieves lower mean objective values and more favorable convergence behavior. Sensitivity analyses further show that increasing the number of chargers and improving the charging rate can reduce queueing delays and total charging duration. The proposed approach provides practical decision support for reliable and sustainable urban electric freight operations.