# A Heuristic Approach for a Real-World Electric Vehicle Routing Problem
## 4 Solution Approach
### Labeling Algorithm
**  
```
1:\(t_{j}^{a}:=\max\{a_{i},t_{i}^{a}\}+t_{i}^{s}+t_{ik}+t^{c}+t_{kj}\)
2:if customer \(j\) is a delivery node then
3:\(q_{j}^{d}:=q_{i}^{d}+q_{j}\), \(q_{j}^{p}:=q_{i}^{p}\)
4:endif
5:if customer \(j\) is a pickup node then
6:\(q_{j}^{d}:=q_{i}^{d}\), \(q_{j}^{p}:=q_{i}^{p}+q_{j}\)
7:endif
8:\(q_{j}^{max}:=\max\{q_{i}^{max},q_{j}^{d}+q_{j}^{p}\}\)
9:\(d_{k}:=d_{i}+d_{ik},f_{k}^{o}:=f_{i}^{o}+c_{c}\cdot t^{c}+\gamma\cdot\max\{0,d_ {k}-D\}\), \(d_{j}:=d_{kj}\)
10
```
1:\(l_{j}^{q}:=\max\{a_{i},t_{j}^{q}\}+t_{i0}+t^{w}+t_{0j}\)
2:\(d_{0}:=d_{i}+d_{i0}\)
3:\(f_{0}^{0}:=f_{i}^{0}+c_{w}\cdot t^{w}+\beta\cdot\max\{0,q_{i}^{max}+q_{i}^{d}-Q \}+\gamma\cdot\max\{0,d_{0}-D\}\)
4:\(d_{j}:=d_{0j}\)
5:if customer \(j\) is a delivery node then
6:\(q_{j}^{t}:=q_{j}\), \(q_{j}^{p}:=0\)
7:endif
8:if customer \(j\) is a pickup node then
9:\(q_{j}^{t}:=0\), \(q_{j}^{p}:=q_{j}\)
10:endif
11:\(q_{j}^{max}:=\max\{0,q_{j}^{d}+q_{j}^{p}\}\)
12:\(f_{j}^{0}:=f_{0}^{0}+c_{d^{*}}(d_{i0}+d_{0j})+c_{w}\cdot\max\{0,a_{j}-t_{j}^{ q}\}+\alpha\cdot\max\{0,t_{j}^{q}-b_{j}\}\)
```
**Algorithm 4**Extension rule considering depot between a pair of nodes. An exponential number of labels will be generated during the extension process. Therefore, a dominance rule is essential to remove the labels that cannot lead to optimal paths. The rule is defined as follows. Definition 1 (Dominance rule): If two labels \(l=\left(t_{i}^{a}\), \(q_{i}^{p}\), \(q_{i}^{d}\), \(q_{i}^{max}\), \(d_{i}\), \(f_{i}^{o}\), \(f_{i}^{a}\), \(i\right)\) and \(l^{\prime}=\left(t_{i}^{a\prime}\), \(q_{i}^{p\prime}\), \(q_{i}^{d\prime}\), \(q_{i}^{max^{\prime}}\), \(d_{i}^{\prime}\), \(f_{i}^{o}\), \(f_{i}^{a\prime}\), \(i\right)\) end at customer \(i\), then label \(l\) dominates \(l^{\prime}\) if \(t_{i}^{a}\leq t_{i}^{a\prime}\), \(q_{i}^{max}\leq q_{i}^{max^{\prime}}\), \(d_{i}\leq d_{i}^{\prime}\), \(f_{i}^{o}\leq f_{i}^{o\prime}\), \(f_{i}^{a}\leq f_{i}^{o\prime}\), and at least one of the inequalities is strict. The arrival time of label \(l\) is earlier than that of label \(l^{\prime}\), which does not guarantee that the cost of the former is smaller than that of the latter during the later extension. Therefore, we adjust the arrival time of label \(l\) to the same as that of label \(l^{\prime}\), compute the adjustment cost \(f_{i}^{a}\), and identify the dominance relationship between the two labels. The adjustment cost \(f_{i}^{a}\) is computed as follows. \[f_{i}^{a}=\left\{ \begin{array}{ll}f_{i}^{o}+c_{w}\cdot\left(t_{i}^{a\prime}- t_{i}^{a}\right),a_{i}\leq t_{i}^{a}\leq t_{i}^{a\prime}\\ f_{i}^{o}+c_{w}\cdot\left(t_{i}^{a\prime}-e_{i}\right),&t_{i}^{a}\leq a_{i} \leq t_{i}^{a\prime}\\ f_{i}^{o},&t_{i}^{a}\leq t_{i}^{a\prime}\leq a_{i}\end{array} \right. \tag{2}\]

The notation used in the labeling algorithm is listed as: \(L_{i}\) is the set of labels associated with customer \(i\); \(l_{i}\) is one label associated with customer \(i\); and \(v_{i}\) and \(n_{s}\) are the \(i\)th node and the number of customers in the sequence \(\{v_{0}\), \(v_{1}\),..., \(v_{i}\),..., \(v_{n_{s}+1}\}\), where \(v_{0}\) and \(v_{n_{s}+1}\) denote depot 0. The pseudo code of the labeling algorithm is presented as Algorithm 5. ```
1:\(L_{0}:=\{(0,\ 0,\ 0,\ 0,\ 0,\ 0,\ 0,\ 0,\ 0)\}\)
2:for\(i=1\) to \(n_{s}+1\)do
3:\(L_{v_{0}}:=\varnothing\)
4:endfor
5:for\(i=1\) to \(n_{s}\)do
6:for\(l_{v_{i}}\in L_{v_{i}}\)do
7: extend \(l_{v_{i}}\) to generate \(l_{v_{i+1}}\) using extension rules in Algorithms 2, 3 and 4
8: add \(l_{v_{i+1}}\) into \(L_{v_{i+1}}\) using dominance rule in Definition 1
9:enddo
10:enddo
11:return the path corresponding to the least-cost label in \(L_{v_{n_{s}+1}}\)
```
**Algorithm 5**Labeling algorithm. ### Departure Time Adjustment Heuristic

The waiting cost in the objective function depends on the first departure time from the depot. We devise a departure time adjustment heuristic to compute the optimal departure time for a given route whose first departure time is zero.