# A Heuristic Approach for a Real-World Electric Vehicle Routing Problem
## 4 Solution Approach
### Labeling Algorithm
The heuristic relies on the difference between the arrival time and time window of each customer. Taking a route \(\{v_{0},\,v_{1},\,\ldots\,v_{i},\,\ldots\,\,,v_{n_{s}},\,v_{n_{s}+1}\}\) as an example, where \(v_{i}\) and \(n_{s}\) are the \(i\)th node and the number of nodes except the starting and ending nodes. The details of the heuristic are described as Algorithm 6. It first sets the departure time from the depot \(t_{0}^{a}\) to zero on Line 1, and then on Lines 2-11 calculates the difference between the arrival time and time window of each customer \(v_{i}\), i.e., \(t_{v_{i}}^{e}\max\{a_{v_{i}}-t_{v_{i}}^{a},\,0\}\) and \(t_{v_{i}}^{l}\max\{b_{v_{i}}-t_{v_{i}}^{a},\,0\}\). The adjustment iterative process is described on Lines 12-35. In each iteration, the first customer that incurs a waiting cost and the maximal allowable adjustment time \(t^{min}\) are found on Lines 14-22, and the values of \(t_{0}^{a}\), \(t_{v_{i}}^{e}\), and \(t_{v_{i}}^{l}\) are updated on Lines 23-33. The iterative process continues until the value of \(t_{v_{i}}^{l}\) at customer \(v_{i}\) is zero. ```
1:\(t_{0}^{a}:=0\)
2:for\(i=0\) to \(n_{s}\)do// initialize \(t_{v_{i}}^{a}\) and \(t_{v_{i}}^{l}\)
3:\(t_{v_{i+1}}^{a}:=t_{v_{i}}^{a}+t_{v_{i}\oplus_{i+1}}\), \(t_{v_{i+1}}^{a}:=\max\{a_{v_{i+1}}-t_{v_{i+1}}^{a},\,0\}\), \(t_{v_{i+1}}^{a}:=\max\{b_{v_{i+1}}-t_{v_{i+1}}^{a},\,0\}\)
4:if\(v_{i+1}\) is a customer node then
5:\(t_{v_{i+1}}^{a}:=t_{v_{i+1}}^{a}+t_{v_{i+1}}^{a}\)
6:else if\(v_{i+1}\) is a depot node then
7:\(t_{v_{i+1}}^{a}:=t_{v_{i+1}}^{a}+t^{w}\)
8:else if\(v_{i+1}\) is a charging station then
9:\(t_{v_{i+1}}^{a}:=t_{v_{i+1}}^{a}+t^{e}\)
10:endif
11:endfor
12:repeat
13:\(t^{min}:=+\infty\), \(t^{min}:=0\)
14:for\(i=0\) to \(n_{s}\)do
15:if\(t_{v_{i}}^{e}>0\)then// find the first customer which incurs waiting cost
16:\(i^{min}:=i\)
17:break
18:endif
19:if\(t^{min}>t_{v_{i}}^{l}\)then// determine the maximal adjustment time
20:\(t^{min}:=t_{v_{i}}^{l}\)
21:endif
22:endfor
23:if\(t^{min}\
eq 0\)then// update the first departure time
24:if\(t^{min}\leq t_{v_{i}^{min}}^{a}\)then
25:\(t_{0}^{a}:=t_{0}^{a}+t^{min}\)
26:break
27:else
28:for\(i=1\) to \(i^{min}\)do
29:\(t_{v_{i}}^{l}:=t_{v_{i}}^{l}-t_{v_{min}}^{e}\)
30:endfor
31:\(t_{0}^{a}:=t_{0}^{a}+t_{v_{min}}^{e}\), \(t_{v_{min}}^{e}:=0\)
32:endif
33:endif
34:endif
35:until\(t^{min}=0\)
36:return\(t_{0}^{a}\)
```

**Algorithm 6**Departure time adjustment heuristic. ### Set-Partitioning Model

The set \(R_{\text{model}}\) is populated during the iterations of the ALNS using feasible routes of the local optimum at each iteration. When adding the routes in \(R_{\text{model}}\), we check their feasibility and remove the routes with the same set of customers and larger route costs. After the iterative process of the ALNS, we use the set \(R_{\text{model}}\) to construct a set-partitioning model as follows. \[\min\;\sum_{r\in R_{\text{model}}}c_{r}\cdot x_{r} \tag{3}\]

\[\text{s.t.}\;\sum_{r\in R_{\text{model}}}\alpha_{ri}\cdot x_{r}=1\forall i\in N \tag{4}\]

\[x_{r}=\{0,\;1\}\;\forall r\in R_{\text{model}} \tag{5}\]

where \(c_{r}\) is the route cost of route \(r\); \(\alpha_{ri}\) is 1 if customer \(i\) is visited by route \(r\) and otherwise 0; and \(x_{r}\) is a 0-1 decision variable that is 1 if route \(r\) is selected in the optimal solution and otherwise 0. When the travel time and distance between two customers respect the triangle inequality, the \"=\" in the constraints in Equation (4) can be replaced by \"\(\geq\)\" (i.e., the set-covering model). We solve such a model using optimization software and expect that some better solutions missed by the ALNS can be found. To reduce the runtime of solving the model, the best solution obtained by the ALNS is used as an initial solution of the model. Meanwhile, the optimization software continues until the optimal solution of the model is obtained or the maximal runtime exceeds the predefined time \(T_{\text{IP}}\).