The electric vehicle routing problem with travel time and energy consumption uncertainty

With the development of green logistics and the promotion of new energy vehicle policies, electric vehicles (EVs) have been put into the logistics and distribution area and offered numerous benefits. However, EVs are more susceptible to unpredictable exogenous and endogenous factors than traditional fuel vehicles. One of the issues is the uncertain fluctuations in travel time and energy consumption, which not only affect the safety of the route but potentially yield extra operation costs. This paper emphasizes the electric vehicle routing problem with travel time and energy consumption uncertainty (EVRP-TTECU). The objective is to develop risk-resistant routing and recharging decisions with the lowest conservatively estimated costs for EV fleet operators. A two-stage adaptive robust optimization framework is proposed, where the degree of uncertainty of a route depends on the number of arcs the vehicle passes through, and the recharging amount at stations and the service start time at customers can be adjusted depending on the circumstance. The problem is resolved by a proposed bi-level search method, which is coupled with a set-based heuristic method to find robust routes and a bidirectional labeling algorithm to provide a conservative estimation of the routes’ cost. The algorithm is examined by comparing it with commercial solver and several heuristics based on benchmark instances. Additionally, sensitivity analysis is performed to show the tradeoff between the operation cost and robustness, and a real distribution case is solved to illustrate the practical feasibility. This study can also offer some references to specific EV delivery scenarios, such as supermarkets and cold-chain distribution.