# A Heuristic Approach for a Real-World Electric Vehicle Routing Problem
## 4 Solution Approach
### Labeling Algorithm  
The removal and insertion heuristics and local search do not alter the charging stations of routes in the solution. To obtain the optimal charging stations or intermediate depots for a given sequence of customers, we first construct an auxiliary graph by adding all charging stations and the depot into the customer sequence. Taking a customer sequence {0, 1, 2, 3, 4, 5, 0} as an example, its auxiliary graph is illustrated in Figure 2, where node \(E_{i}\) denotes the charging station and \(m\) is the number of charging stations. We need to find a path with minimal cost that starts at Node 0, visits all customers and returns to Node 0. Such a problem can be solved by the labeling algorithm [PERSON] and [PERSON] (2015); [PERSON] and [PERSON] (2015). The label algorithm uses labels to construct a partial path from Node 0 to any customer in the sequence. The label \(l=\left(t_{i}^{a},q_{i}^{p},q_{i}^{q},q_{i}^{max},d_{i},f_{i}^{o},f_{i}^{a},i\right)\) at node \(i\) is defined as: \(t_{i}^{a}\) is the arrival time at node  
Figure 2: Auxiliary graph in the labeling algorithm. \(i\); \(q_{i}^{p}\) and \(q_{i}^{d}\) are the total pickup and delivery demand after the last departure from Node 0, respectively; \(q_{i}^{max}\) is the maximal demand after the last departure from Node 0; \(d_{i}\) is the total travel distance after the last charge; \(f_{i}^{o}\) is the cost from the starting point to node \(i\); \(f_{i}^{a}\) is the adjustment cost used and calculated in the dominance rule; and \(i\) is the last reached node. At the starting point \(0\), \(\left(t_{0}^{a},q_{0}^{p},q_{0}^{d},q_{0}^{max},d_{0},f_{0}^{o},f_{0}^{a},0\right)\) are initialized to zero. When a label \(\left(t_{i}^{a},q_{i}^{p},q_{i}^{d},q_{i}^{max},d_{i},f_{i}^{o},f_{i}^{a},i\right)\) of customer \(i\) is extended to customer \(j\), (\(m\)+2) labels \(\left(t_{j}^{a},q_{j}^{p},q_{j}^{d},q_{j}^{max},d_{j},f_{j}^{o},f_{j}^{a},j\right)\) are generated, including one label associated with a path directly traveling from customers \(i\) to \(j\) using the extension rule in Algorithm 2, \(m\) labels associated with each path going though one charging station using the extension rule in Algorithm 3, and one label associated with a path going through the depot using the extension rule in Algorithm 4. ```
1:\(t_{j}^{a}:=\max\{a_{i},t_{i}^{a}\}+t_{i}^{s}+t_{ij}\)
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_{j}:=d_{i}+d_{ij}\)
10:if\(j\) is the depot then
11:\(f_{j}^{o}:=f_{i}^{o}+c_{d}\cdot d_{ij}+\beta\cdot\max\{0,q_{j}^{max}+q_{j}^{d} -Q\}+\gamma\cdot\max\{0,d_{j}-D\}\)
12:else
13:\(f_{j}^{o}:=f_{i}^{o}+c_{d}\cdot d_{ij}+c_{w}\cdot\max\{0,a_{j}-t_{j}^{a}\}+ \alpha\cdot\max\{0,t_{j}^{a}-b_{j}\}\)
14:endif
```  
**Algorithm 2****Extension rule for directly traveling from customers \(i\) to \(j\). **  
```
1:\(t_{j}^{a}:=\max\{a_{i},t_{i}^{a}\}+t_{i}^{s}+t_{ij}\)
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:if\(j\) is the depot then
11:\(f_{j}^{o}:=f_{k}^{o}+c_{d}\cdot(d_{ik}+d_{kj})+\beta\cdot\max\{0,q_{j}^{max}+q_{ j}^{d}-Q\}+\gamma\cdot\max\{0,d_{j}-D\}\)
12:else
13:\(f_{j}^{o}:=f_{k}^{o}+c_{d}\cdot(d_{ik}+d_{kj})+c_{w}\cdot\max\{0,a_{j}-t_{j}^{a }\}+\alpha\cdot\max\{0,t_{j}^{a}-b_{j}\}\)
14:endif
```  
**Algorithm 3****Extension rule considering charging stations between a pair of nodes.