# A Heuristic Approach for a Real-World Electric Vehicle Routing Problem
## 4 Solution Approach  
Considering the complexity of the proposed problem, we devise a heuristic approach based on the ALNS and IP to solve it. The ALNS was first proposed by [PERSON] and [PERSON] [25]. Its basic idea is to use a leaning mechanism to bias the selection of a variety of removal and insertion operators that are used to generate new solutions. It has been widely used to solve various variants of VRPs [26; 27; 28; 29; 30; 31; 32; 33; 34; 35]. In this paper, we incorporate the features of the proposed problem into the ALNS. Its details are described in Algorithm 1.  
An initial solution \(s_{0}\) is first generated at the beginning of the ALNS. Then, at each iteration, as on Line 5, a removal and insertion heuristic pair is chosen based on their scores and weights in previous iterations. On Line 6, a given number of customers are first removed from current solution \(s_{\text{current}}\) using the chosen removal heuristic and put into the set of removed customers. The locations of charging stations and depot in the partial solution remain unchanged. Using the corresponding insertion heuristic, the removed customers are reinserted into the partial solution to generate a new solution \(s^{\prime}\). On Lines 7 and 8, solution \(s^{\prime}\) is first improved by a local search, and then the charging stations and departure time of all routes are optimized. On Lines 9-17, if \(s^{\prime}\) is better than current best infeasible solution \({s_{\text{inf}}}^{*}\) or current solution \(s_{\text{current}}\) or meets the acceptance criteria, then it replaces \(s_{\text{current}}\). Accordingly, the route set \(R_{\text{model}}\) is updated with new feasible routes in \(s^{\prime}\). On Lines 18-20, the current best feasible solution \({s_{\text{fea}}}^{*}\) is updated. Then, on Lines 21 and 22, the scores and weights of the selected removal and insertion heuristics are updated, and the penalty coefficients of the generalized cost function are also updated. The search is repeated until some stopping criterion is satisfied. The stopping criterion is that the runtime of the ALNS exceeds the given value \(T_{\text{ALNS}}\). Then, a set-partitioning mathematical model based on the routes in set \(R_{\text{model}}\) is constructed and solved by optimization software. Finally, the solution obtained from the model is outputted as the solution of the problem.  
```
1: generate an initial solution \(s_{0}\)
2:\(s_{\text{fea}}\) := \(s_{0}\), \(s_{\text{init}}\) := \(s_{0}\), \(s_{\text{current}}\) := \(s_{0}\)
3: update route set \(R_{\text{model}}\) with feasible routes of \(s_{\text{current}}\)
4:repeat
5: choose a removal-insertion heuristic pair according to adaptive weights
6: apply selected heuristic pair to \(s_{\text{current}}\), yielding \(s^{\prime}\)
7: apply local search to \(s^{\prime}\)
8: adjust vehicle type, charging stations, and first departure time of all the routes of \(s^{\prime}\)
9:if\(s^{\prime}\) is better than \(s_{\text{init}}\)then
10:\(s_{\text{init}}\) := \(s^{\prime}\), \(s_{\text{current}}\) := \(s^{\prime}\)
11: update the route set with feasible routes of \(s_{\text{current}}\)
12:elseif\(s^{\prime}\) is better than \(s_{\text{current}}\)then
13:\(s_{\text{current}}\) := \(s^{\prime}\)
14: update the route set with feasible routes of \(s_{\text{current}}\)
15:elseif\(s^{\prime}\) meets the acceptance criteria then
16:\(s_{\text{current}}\) := \(s^{\prime}\)
17:endif
18:if\(s^{\prime}\) is feasible and is better than \(s_{\text{fea}}\)\({}^{*}\)then
19:\(s_{\text{fea}}\) := \(s^{\prime}\)
20:endif
21: update scores and weights of selected heuristics
22: update penalty coefficients of generalized cost function
23:until some stopping criterion is satisfied
24: construct the set-partitioning model using routes in \(R_{\text{model}}\) and solve it
25: update \(s_{\text{fea}}\)\({}^{*}\) with solution of the model
26:return\(s_{\text{fea}}\)\({}^{*}\)
```  
**Algorithm 1**Solution approach for the proposed problem.