Mitigate the range anxiety: two-stage optimization for the electric vehicle routing problem with time windows and battery status uncertainty

Electric vehicles are widely regarded as a sustainable alternative to conventional freight vehicles due to their environmental benefits and lower emissions. However, uncertainty in battery status, arising from both external factors such as temperature and internal factors such as payload, poses a significant challenge for electric logistics operations. This paper addresses the electric vehicle routing problem with time windows under battery status uncertainty (EVRPTW-BSU) by proposing a two-stage stochastic programming framework. The uncertainty is modeled using scenario-based stochasticity, where each scenario represents a possible realization of external and internal factors that affect battery status. In the first stage, the routes are generated based on expected battery status. In the second stage, recourse actions, such as penalties for skipping customers or for late returns to the depot, are applied if the realized battery status results in infeasibility. To solve this model efficiently, we developed a two-stage metaheuristic based on the adaptive large neighborhood search (ALNS), incorporating problem-specific operators. Extensive computational experiments on benchmark instances demonstrate that the proposed method reduces average cost by 10.3% relative to deterministic models while maintaining stable performance across scenarios. By explicitly addressing battery uncertainty in electric vehicle routing, this study provides methodological and managerial insights for robust and sustainable urban freight operations.