# A Heuristic Approach for a Real-World Electric Vehicle Routing Problem
## 4 Solution Approach
### Labeling Algorithm
Meanwhile, the average standard deviation of the objective function values obtained by the original ALNS was also larger than that obtained by the proposed algorithm. These results demonstrate the effectiveness of the improved strategies (i.e., the local search component and the IP component) used in the proposed algorithm. For all instances, in the proposed algorithm, the minimal and average of the total operational cost obtained by the ALNS was not smaller than that improved by the IP; the relative gap between the two algorithm components in the proposed algorithm was between 0% (R7 and R9) and 1.49% (R6), and the average relative gap was 0.40%. These results underline the necessity of the IP components employed in the proposed algorithm. The runtime for both the original ALNS and the ALNS phase in the proposed algorithm was 600 s. The runtime for solving the set-partitioning model by CPLPEX varied between 0.48 (R9) and 180 s (the maximal runtime set for solving the model, R12), meaning that CPLEX did not solve the model optimally for all test runs. According to our experiments, if CPLEX solved the model to optimality, it might take several hours without improving the solution obtained in the current runtime setting. As shown in Table 1, the acquisition cost and travel cost per kilometer of type-2 vehicles are larger than that of type-1 vehicles. If all demands of customers do not exceed the capacity of type-1 vehicles, customers are always visited by type-1 vehicles according to our experiments. Taking the best solution of R1 as an example, it uses 10 type-1 vehicles, charges six times, waits 509 min, and travels 949.707 km. Then, the total acquisition cost is 2000 Yuan, the total charging cost is 270 Yuan, the total waiting cost is 254.5 Yuan, and the total travel cost is 9497.07 Yuan. As shown in Figure 3, the total travel cost is 79% of the total operational cost, indicating that designing reasonable visiting routes is essential for companies to save operational cost. \begin{table}
\begin{tabular}{c c c c c c c c c c c c c c} \hline \hline \multicolumn{1}{c}{\multirow{3}{*}{**Instance Customers**}} & \multicolumn{6}{c}{**Original ALNS**} & \multicolumn{6}{c}{**Proposed Algorithm**} \\ \cline{3-14}  & \multirow{2}{*}{**Customers**} & \multirow{2}{*}{**Charging**} & \multirow{2}{*}{**Min**} & \multirow{2}{*}{**Avg**} & \multirow{2}{*}{**Std**} & \multirow{2}{*}{**Gap (\%)**} & \multicolumn{2}



### Comparison with Company's Algorithm

The logistics company uses optimization software developed by a consulting company to address the proposed EVRP. To further demonstrate the performance of our algorithm, we compared the results obtained by it with that by optimization software. Due to the confidentiality agreement, the core algorithm embedded in the software cannot be described in detail. The results of instances obtained by the software and the ALNS are listed in Table 5. In the table, the column \"Customers\" presents the number of customers included in the instance; the column \"Charging Stations\" denotes the number of charging stations that can be used in the instance; the column \"Company's Algorithm\" shows the results of instances obtained by the software; the column \"Proposed Algorithm\" lists the best results of instances obtained by our algorithm; and the column \"Gap\" demonstrates the relative gap between the software and our algorithm and equals (Proposed Algorithm -- Company's Algorithm)/Proposed Algorithm \(\times\) 100%. Table 5 shows that for all instances the proposed algorithm outperformed the optimization software used in the company. The minimal and maximal relative gaps between the two approaches were 4.49% (R6) and 9.91% (R2), respectively, and the average relative gap was 7.52%, indicating that using our algorithm could save 7.52% of operational cost. We showed the solutions obtained by our

Figure 3: Percentages of costs of the best solution of R1.