A two-stage adaptive variable neighborhood search approach for electric vehicle routing problem with fuzzy demand

This paper addresses the electric vehicle routing problem under fuzzy demand (EVRPFD), which is widespread in real-world logistics scenarios. To solve it, a chance-constrained model is formulated based on credibility theory, aiming to minimize the total distance traveled by all vehicles. Subsequently, a two-stage adaptive variable neighborhood search (TAVNS) metaheuristic is proposed, which consists of a pre-optimization phase and a rescheduling phase. In the pre-optimization phase, a series of search mechanisms are designed to construct pre-optimized routes. Particularly, an adaptive shaking operator is developed to dynamically guide the algorithm’s search direction. In the rescheduling phase, a stochastic simulation method is adopted to identify route failures in the pre-optimized routes generated from the pre-optimization phase, and a reallocation strategy is then proposed to address these failures. Experimental results demonstrate that the proposed TAVNS outperforms its competitors significantly and updates the known optimal solutions for several cases. Additionally, a feasibility analysis focusing on route repair strategies validates that the proposed reallocation strategy can efficiently tackle route failures, and the additional costs generated are lower compared to those of the traditional repair strategy. Finally, by examining results derived from different preference values, this study explores how decision-makers’ varying attitudes impact delivery costs and concludes that the optimal delivery plan is achieved when they adopt a relatively conservative attitude.