# SVD Enhanced Metaheuristic for Plug-In Hybrid Electric Vehicle Routing Problem
## 4 Methodology
### Memetic Algorithm
The SVND method starts from a given solution \(x\), and the \(l\)th neighborhood structure is applied to generate a new solution \(x^{\prime}\), then the fitness value \(f(x^{\prime})\) is compared with the current value \(f(x)\). If the new value is better, the solution \(x\) moves to \(x^{\prime}\) and continue the search with premier neighborhood (\(l\gets 1\)), otherwise the next neighborhood structure is applied with \(l\gets l+1\). If the search operation runs \(l_{max}\) times without finding better values. The process will be terminated. Specifically, during the search process, an extra search technique 2_opt is applied when the new solution \(x^{\prime}\) is better than the incumbent, it generates \(x^{\prime\prime}\) and update the solution \(x\) only when \(f(x^{\prime\prime})<f(x)\). The 2_opt method and the neighborhood structure in the SVND algorithm are described in the following. ```
Input: the best offspring individual \(x\) Output: The new offspring individual \(x^{\prime}\) Begin \(l\gets 1\) while\(l<l_{max}\)do \(x^{\prime}\leftarrow\)lth_neighborhoodmove(\(x\)) if\(f(x^{\prime})<f(x)\)then \(x\gets x^{\prime}\), \(f(x)\gets f(x^{\prime})\) \(l\gets 1\) else \(l\gets l+1\) end if \(x^{\prime\prime}\gets 2\_opt(x)\) if\(f(x^{\prime\prime})<f(x)\)then \(x\gets x^{\prime\prime}\), \(f(x)\gets f(x^{\prime\prime})\) end while  return \(x\)
```

**Algorithm 7** The pseudo-code of SVND

#### 4.7.1 2_Opt Method

The 2_opt method used in this paper was proposed by [PERSON] et al. [45]. It is a simplified form of the Lin-Kernighan algorithm [46], which is known as the k-opt method. In this paper, we can get a better solution by constantly comparing the distances of customers in the cycle. If the following equation is satisfied, then the indices of targets \(i+1\) and \(j\) should be swapped. Such comparisons can be repeated many times over a route, number of repetitions equals to the length of route-2. The same operation finally updates all routes. The pseudo-code for the 2_opt method is given in Algorithm 8. \[d_{i,j+1}+d_{j,j+1}>d_{i,j}+d_{i+1,j+1} \tag{20}\]

#### 4.7.2 Neighborhood Search Structure

The performance of the local search procedure depends on the choice of neighborhood structures. The size of the neighborhood is a key factor; the larger the neighborhood, the more likely it could contain better solutions [46]. We utilize five neighborhood structures in this work, for example, Swap, Insertion, Reverse, Insertion stations and Delete stations. The first three neighborhood structures are common changes in other VRP papers, and the latter two are unique to the hybrid vehicle routing problem in this paper. These operators are briefly explained below and illustrated in Figure 2.

1. Swap: The swap move is carried out by exchanging the positions of randomly selected \(i\) and \(j\) nodes of solution \(x\). It should be noted that \(i\) and \(j\) may come from the same route or may come from different routes. That is to say, the swap operation may be an Intra-route movement or an Inter-route movement. Insertion: The insertion is implemented by randomly selecting a node from index \(i\) and inserting it immediately following a randomly selected \(j\) node of \(x\). Similar to swap, insertion operation may be an Intra-route movement or an Inter-route movement. 3. Reverse: A reverse is performed by randomly selecting \(i\) and \(j\) nodes from the same route of solution \(x\) and then reversing the substring in-between them. 4. Insertion Stations: An insert station is executed by choosing a station each from \(S_{e}\) and \(S_{f}\), and then inserting them into the preceding random \(i\) index on solution \(x\). Fuel stations, electric stations and insertion locations are randomly selected. 5.