###### Abstract  
Compared to fossil fuel-based internal combustion vehicles, electric vehicles with lower local pollution and noise are becoming more and more popular in urban logistic distribution. When electric vehicles are involved, high-quality delivery depends on energy consumption. This research proposes an electric vehicle routing problem considering time windows under energy consumption uncertainty. A mixed-integer programming model is established. The robust optimization method is adopted to deal with the uncertainty. Based on the modification of adaptive large neighborhood search algorithm, a metaheuristic procedure, called novel hybrid adaptive large neighborhood search, is designed to solve the problem, and some new operators are proposed. The numerical experiments show that the proposed metaheuristic can obtain high-performance solutions with high efficiency for large-scale instances. Furthermore, the robust solution based on the proposed model can achieve a satisfactory tradeoff between performance and risk.  
vehicle routing problems; electric vehicles; robust optimization; time windows; adaptive large neighborhood search 2020 IEEEexample: accepted: 12 2021 IEEEexample: accepted: 12 2021 IEEEexample: accepted: 8 2021 IEEEexample  
In academic research, some scholars have focused on taking emission costs into account for routing problems [8], while others have had their eyes on how to deal with the problem of route planning with the involvement of environmentally friendly EVs, named the electric vehicle routing problem (EVRP) [9; 10]. Research on EVRP began with the study of the green vehicle routing problem, which was first introduced by [PERSON] and [PERSON] [11]. The topic has been the object of great concern since it was first raised. The EVRP considering time windows (EVRPTW) assumes that each EV can become fully charged at the depot or RSs and must serve each customer during the given time window. In the existing research, most papers assume that the energy consumption of an EV for a unit travel distance or travel time is fixed [12; 13]. However, the energy consumption of an EV is usually uncertain, e.g., unfavorable external factors such as a damaged or bumpy road can greatly affect energy consumption. Several parameters used to calculate the energy consumption of an EV are difficult to measure; this issue was presented by [PERSON] et al. [14]. Hence, it is almost impossible to eliminate uncertainty in estimating energy consumption. [PERSON] and [PERSON] [15] illustrated that environmental factors can significantly influence the battery capacity of an EV. Due to uncertainty, EVs need more or less time to become fully charged at RSs, which might lead to them not being able to provide services to customers within the agreed time window.  
In this paper, we studied a new problem called the electric vehicle routing problem, considering time windows and recharging stations under energy consumption uncertainty (EVRPTW-ECU). To deal with the uncertainty, the robust optimization theory proposed by [PERSON] et al. [16] was applied. The contributions of our work can be identified as follows:  
1. We propose a robust optimization model for the EVRPTW-ECU.
2. A hybrid metaheuristic, which combines an adaptive large neighborhood search (ALNS) heuristic with a local search (denoted as the NHALNS), is developed to deal with large-scale instances.
3. The extensive numerical experiments reveal that the proposed NHALNS can solve small-scale instances optimally and obtain high-quality solutions for large-scale instances.  
The rest of this paper is organized as follows. The related literature is reviewed in Section 2. The description and robust optimization model for the proposed EVRPTW-ECU are shown in Section 3. We also introduce the developed NHALNS in detail in Section 4. An extensive computational study and a comprehensive analysis of the results are presented in Section 5. Finally, the paper's conclusion and several managerial insights are illustrated in Section 6.