# SVD Enhanced Metaheuristic for Plug-In Hybrid Electric Vehicle Routing Problem
## 4 Methodology
### Memetic Algorithm
```
Input: Two parent individuals \(x_{1}\) and \(x_{2}\) Output: The new offspring individual \(x^{\prime}\) Begin  Sort the tours of \(x_{1}\) and \(x_{2}\) according to their distance \(mR\)=the minimum tour number of \(x_{1}\) and \(x_{2}\) for\(i=1\) to \(mR\)do  r=random() If\(r>0.5\)then \(S\)=get tour \(i\) from \(x_{1}\) Else \(S\)=get tour \(i\) from \(x_{2}\) End  add \(S\) to \(x^{\prime}\)  Delete the same city of \(S\) from both \(x_{1}\) and \(x_{2}\) End  unassigned list\(\leftarrow\)Unallocated city for\(j=1\) to the size of unassigned list do  Insert city \(j\) from unassigned list to a tour of \(x^{\prime}\) by minimum distance increment End If there is only the depot in a tour then \(x^{\prime}\)=repair(\(x^{\prime}\)) End  return \(x^{\prime}\) End
```
**Algorithm 5** The pseudo-code of recombine. ### Mutate Operator

In the mutate operator, all tours in \(x\) are sorted in ascending order. Each customer from a tour \(i\) is moved to \(x^{\prime}\) with varied probability \(P_{copy}\), otherwise the customers are moved to the unassigned list. This process is repeated until all customers are moved from \(x\). Then, the customers in the unassigned list will be reassigned to \(x^{\prime}\) by the same process in the recombine operator. [PERSON] and [PERSON] [41] explained why they did not use the constant probability, but the probability related to the number of iterations and they defined \(P_{copy}\) in detail, it can be determined by the following equation:

\[P_{copy}=\frac{(P_{maxcopy}-P_{mincopy})}{iter_{max}}\times iter+P_{mincopy}. \tag{19}\]

Where \(iter\) is the running time or the number of iterations, \(iter_{max}\) is the maximum running time or the maximum number of iterations, \(P_{maxcopy}\) and \(P_{mincopy}\) represent respectively the maximum value and the minimum value of \(P_{copy}\). The algorithm for mutate is given in Algorithm 6. ```
Input: Two selected individuals \(x\) Output: The new offspring individual \(x^{\prime}\) Begin  Sort the tours of \(x\) according to their distance \(TN\)=the tour number of \(x\) for\(i=1\) to \(TN\)do  r=random() If\(r<P_{copy}\)then \(S\)=get tour \(i\) from \(x\) Else  unassigned list=get tour \(i\) from \(x\) End  add \(S\) to \(x^{\prime}\)  Delete the same city of \(S\) from \(x\) End for\(j=1\) to the size of unassigned list do  Insert city \(j\) from unassigned list to a tour of \(x^{\prime}\) by minimum  distance increment  End If there is only the depot in a tour then \(x^{\prime}\)=repair(\(x^{\prime}\))  End  return \(x^{\prime}\) End
```
**Algorithm 6** The pseudo-code of mutate

### Sequential Variable Neighborhood Descent

Variable Neighborhood Search (VNS) is a metaheuristic based on a systematic change of the neighborhood structures within a search introduced by [PERSON] and [PERSON] [42]. It is based on the idea of a systematic change of neighborhood both in a descent phase to find a local optimum and in a perturbation phase to get out of the corresponding valley [43]. It has been proved that it could solve various combinatorial optimization problems. The Sequential Variable Neighborhood Descent (SVND) is a sample variant of the basic VNS where the systematic changes of the neighborhood structures are performed in a deterministic way. The pseudo code of SVND is shown in Algorithm 7. It should be noted that there are two ways to explore local search, one is called first improvement strategy (a move made when an improvement in the neighborhood is once found) and the other is called the best improvement strategy (a move to the best solution in the neighborhood) [44]. In this work, we adopted the former. The SVND in this paper is applied as a local search algorithm to improve the performance of a global search algorithm, and five neighborhood structures are proposed in this study (\(l_{max}=5\)). Among all the new individuals produced, the SVND is used to improve the best one among them.