# A Heuristic Approach for a Real-World Electric Vehicle Routing Problem
## 4 Solution Approach
### Labeling Algorithm
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Instance** & **Customers** & **Charging** & **Company’s Algorithm** & **Proposed Algorithm** & **Gap (\%)** \\ \hline R1 & 110 & 10 & 13,035.38 & 12,021.57 & 8.43 \\ R2 & 101 & 10 & 13,828.70 & 12,581.40 & 9.91 \\ R3 & 110 & 6 & 9328.13 & 8642.34 & 7.94 \\ R4 & 108 & 7 & 11,653.22 & 10,952.90 & 6.39 \\ R5 & 103 & 8 & 14,400.21 & 13,529.20 & 6.44 \\ R6 & 104 & 5 & 13,421.89 & 12,845.00 & 4.49 \\ R7 & 100 & 8 & 11,689.32 & 10,745.00 & 8.79 \\ R8 & 106 & 6 & 13,872.90 & 12,750.30 & 8.80 \\ R9 & 108 & 3 & 8654.32 & 7912.21 & 9.38 \\ R10 & 109 & 14 & 16,287.23 & 15,310.40 & 6.38 \\ R11 & 101 & 3 & 10,532.45 & 9770.27 & 7.80 \\ R12 & 108 & 12 & 15,321.65 & 14,428.20 & 6.19 \\ R13 & 105 & 12 & 18,632.21 & 17,733.80 & 5.07 \\ R14 & 104 & 4 & 12,123.22 & 11,197.50 & 8.27 \\ R15 & 106 & 14 & 15,321.22 & 14,170.40 & 8.12 \\ R16 & 111 & 5 & 13,140.23 & 12,082.80 & 8.75 \\ R17 & 108 & 7 & 11,823.12 & 10,952.90 & 7.95 \\ R18 & 101 & 11 & 17,019.22 & 16,180.90 & 5.18 \\ R19 & 103 & 10 & 11,992.23 & 11,156.10 & 7.49 \\ R20 & 110 & 10 & 13,056.98 & 12,021.60 & 8.61 \\ Avg & - & - & 13,256.69 & 12,349.24 & 7.52 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Results of instances obtained by company’s algorithm and the proposed algorithm. algorithm to the managers in the company, and they were very satisfied with these solutions, which can be directly used in practice. These results clearly show the effectiveness of our proposed algorithm. ## 6 Conclusions and Future Research Works

This paper develops a heuristic approach to solve a real-world EVRP proposed by a logistics company in Wuhan, China. In the approach, the ALNS is followed by solving a set-partitioning mathematical model that strengthens its effectiveness. Meanwhile, to reduce charging costs and waiting costs, two problem-specific heuristics, including the charging station adjustment heuristic and the departure time adjustment heuristic, are devised. The performance of the proposed algorithm was validated by 20 test instances generated from real-world data. The contributions of this paper are summarized as follows. First, this paper investigates a new variant of VRPs that originates from a real-world application and combines the features of different VRPs. Second, an efficient approach based on the ALNS and IP is developed to solve it. In the approach, a charging station adjustment heuristic and a departure time adjustment heuristic are devised to accommodate the features of the proposed problem. Third, the superiority of the proposed approach over the original ALNS is validated through computational experiments. This work also offers several directions for future research. First, different charge strategies, such as allowing partial charges, will be included in the proposed problem. Second, different charge techniques, such as different charging modes, will be considered in the proposed problem. Finally, different meta-heuristics, such as the genetic algorithm [38] and the VNS [39], will be developed to enrich the solution approaches to the proposed problem. Conceptualization, Y.L. ; methodology, Y.L. and M.Z. ; investigation, M.Z. ; writing--original draft preparation, M.Z. ; writing--review and editing, Y.L. ; supervision, Y.L. ; and funding acquisition, Y.L. This work was supported by the research grant from the National Natural Science Foundation of China (71801058) and Guangxi Natural Science Foundation (2018)JB110017). The authors declare no conflict of interest. ## References

* [PERSON] (2002) [PERSON]; [PERSON] Models, Relaxations and Exact Approaches for the Capacitated Vehicle Routing Problem. _Discrete. Appl. Math._**2002**, _123_, 487-512. [CrossRef]
* [PERSON] and [PERSON] (2005) [PERSON]; [PERSON] Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms. _Transp. Sci._**2005**, _39_, 104-118. [CrossRef]
* [PERSON] and [PERSON] (2005) [PERSON]; [PERSON] Vehicle Routing Problem with Time Windows, Part II: Metaheuristics. _Transp. Sci._**2005**, _39_, 119-139.