Efficient Post-Disaster Emergency Energy Delivery Under Dynamic Constraints: An Electric Vehicle Routing Approach

This paper investigates a novel post-disaster power recovery scenario in which shelter batteries are subject to dynamic charging time constraints determined by their state-of-charge ($SoC$) dynamics. In this context, electric vehicles (EVs) serve as both transportation resources and mobile energy storage units. The objective is to determine an EV delivery plan that satisfies the power demand of shelter batteries within their dynamic charging time constraints while minimizing the total fleet travel costs. In addition, road-grade effects on EV energy consumption during travel are incorporated. In the first phase, a reduced graph is extracted from the original disaster-affected network to simplify the network topology. In the second phase, the problem is formulated as a mixed-integer linear programming (MILP) model. To obtain a high-quality delivery plan, an adaptive large neighborhood search (ALNS) algorithm is developed with problem-specific destroy and repair operators. The performance of the proposed ALNS is evaluated through comprehensive numerical experiments on benchmark instances of varying sizes constructed from a public road network. The results demonstrate that the proposed ALNS outperforms state-of-the-art methods. Finally, sensitivity analyses are conducted to quantify the impacts of uncertainties, time constraints, road grades, and reduced-graph construction.