# A Heuristic Approach for a Real-World Electric Vehicle Routing Problem
## 4 Solution Approach
### Labeling Algorithm
## 5 Computational Experiments

In this section, we first introduce the construction of test instances from real-world data provided by a logistics company in Wuhan, China. Then, we report the values of major parameters in the proposed algorithm. Finally, we validate the effectiveness of the proposed algorithm by testing the instances. The algorithm was coded in C++ language. The mathematical model was solved by IBM ILOG CPLEX 12.6.3. All experiments were run on a computer with Intel Xeon E5-1620 V4 3.50 GHz CPU and 32 GB RAM under Windows 10 operating system. ### Construction of Test Instances

The test instances were obtained from real-life data provided by a logistics company in Wuhan, China. The company uses two types of electric vehicles to provide logistics services for customers. The details of electric vehicles are listed in Table 1. The company also has detailed information about customers and charging stations, such as their locations. To generate the instances, we randomly selected approximately 100 customers and 10 charging stations around a distribution center. The loading or unloading time (\(t_{i}\)) at each customer is 20 min. If a vehicle returns to the distribution center, it must wait 40 min (\(t_{w}\)) to prepare for the next trip. The waiting cost per minute (\(c_{w}\)) is 0.5. Twenty instances were generated to validate the effectiveness of the proposed algorithm. Instances are represented in the following format: R1 indicates the first instance in the set. \begin{table}
\begin{tabular}{c c c c c c c} \hline \multirow{2}{*}{**Type**} & **Load** & **Range \(D^{k}\)** & **Charging Cost** & **Acquisition** & **Travel Cost per** \\  & **Capacity \(Q^{k}\)** & **(Kilometer)** & **Time \(t_{c}^{k}\)** & **per Minute \(c_{c}^{k}\)** & **Cost \(c_{f}^{k}\)** & **Kilometer \(c_{w}^{k}\)** \\  & **(Ton)** & **(Kilometer)** & **(Minute)** & **(Yuan)** & **(Yuan)** & **(Yuan)** \\ \hline
1 & 2.0 & 100 & 30 & 1.5 & 200 & 10 \\
2 & 2.5 & 150 & 30 & 1.5 & 400 & 12 \\ \hline \end{tabular}
\end{table} 
Table 1: Parameters of electric vehicles. ### Parameter Settings

The parameters of the proposed algorithm are listed in Table 2. To set all parameters, each parameter in turn took several values, while the others were fixed. We ran the proposed algorithm 10 times for each parameter setting, and the parameter setting producing the best average results was selected. Table 2 also shows the best parameter setting for the proposed algorithm. According to a series of preliminary experiments, the number of customers removed by removal heuristics (\(q\)) had the largest influence on the performance of the proposed algorithm. To give a sensitivity analysis to this parameter, six different intervals were tested: \([0.05\,|\,N\,|\,0.25\,|\,N\,|\,]\), \([0.1\,|\,N\,|\), \(0.31\,|\,]\), \([0.05\,|\,N\,|\,0.35\,|\,N\,|\,]\), \([0.1\,|\,N\,|\,0.4\,|\,N\,|\,]\), \([0.15\,|\,N\,|\,0.35\,|\,N\,|\,]\), and \([0.15\,|\,N\,|\,0.45\,|\,N\,|\,]\). At each iteration of the ALNS, \(q\) was selected uniformly at random in corresponding interval. Table 3 shows the average of the objective function value of all instances in different intervals. The results prove that \([0.1\,|\,N\,|\,0.4\,|\,N\,|\,]\) was among the best of all intervals. ### Performance Analysis of ALNS

In the proposed algorithm, the best solution obtained by the ALNS is further improved by set-partitioning-based integer programming. To validate the effectiveness of such an algorithm design, we compared the results only using the ALNS with those improved by integer programming (IP). Meanwhile, in the original framework of ALNS, the local search component does not exist. Therefore, we also tested the original ALNS without using the improvement strategies. For each instance, we ran the algorithms ten times. In Table 4, the column \"Customers\" presents the number of customers included in the instance; the column \"Charging Stations\" denotes the number of charging stations