# SVD Enhanced Metaheuristic for Plug-In Hybrid Electric Vehicle Routing Problem
## 4 Methodology
### Memetic Algorithm
```
Input: The data of problem Output: An initial solution \(R\) Begin \(i=0\), \(count=0\), \(R=NULL\) \(vn=1\), \(route_{vn}=NULL\) While\(count\leq n\) DO  j=the nearest unassigned node from i If\(i=0\)then \(time\_spent=T_{ij}+T_{ji}\) Else \(time\_spent=time\_spent-T_{i0}+T_{ij}+T_{j0}\) End If\(time\_spent\leq T_{max}\)then \(route_{vn}=route_{vn}+j\) \(i=j\) \(count++\) Else \(i=0\), \(vn++\) \(route_{vn}=NULL\) End End While for\(i=1\) to \(mR\)do  Calculate \(EP_{i}\) and \(FP_{i}\) of route i If\(EP_{i}\) and \(FP_{i}\)?vehicle capacity then \(route_{vn}=route_{vn}+S_{v}\) or \(S_{f}\) \(R=R+route_{vn}\) End End  end return \(R\) End
```
**Algorithm 3**Method to generate a signal individual
```
Input: Individual population Output: new population \(X\) Begin  Select two employed solution \(S_{1}\) and \(S_{2}\) from the population  r=random() If\(r<p_{better}\)then  Xleftarrow the best of \(S_{1}\) and \(S_{2}\) Else  Xleftarrow the worst of \(S_{1}\) and \(S_{2}\) End  return X End
```
**Algorithm 4**The pseudo-code of binary tournament selection

### Recombine Operator

Before the recombine operator, we obtained two parent individuals by using binary tournament selection method. In this paper we attempt to exchange memes between two parents to obtain new individuals. The recombine operator was proposed firstly by [PERSON] and [PERSON] [39] to solve a multiple traveling salesperson problem (MTSP) where the number of vehicles is fixed. In our studied problem, due to the uncertainty of vehicle number and the choice of the power station, the individual may have different tour numbers and different individual lengths. Thus, a new revised recombine operator is proposed to solve the studied problem, the details of the reorganization operation are as follows:

Let \(x_{1}\) and \(x_{2}\) be the two selected parents to recombine operator and let \(m_{1}\) and \(m_{2}\) be the number of tours present in \(x_{1}\) and \(x_{2}\), and \(mR\) is defined as the minimum tour number \(mR=min(m_{1},m_{2})\). The recombine operator can be divided into the following steps. The first step, sorting all tours by their distances in an ascending way within \(x_{1}\) and \(x_{2}\), and then it constructs a offspring individual \(x^{\prime}\) in an iterative way. In each iteration, it selects one of the two parent individuals randomly and moves the \(i^{th}\) tour to \(x^{\prime}\). This process is repeated in \(mR\) times in our case and the parents are selected with equal probability. Clearly, at the end of first stage, some customers still remain unassigned and they will be moved into an unassigned list. In the second stage, we adopt the method proposed by [PERSON] and [PERSON] [39] to generate good solutions. During each iteration, the customers in the unassigned list are reassigned one by one to \(x^{\prime}\). Each time it assigns a customer to a particular tour whose distance increases the least by this reassignment. To achieve this, we have to check all possible insertion positions in every tour. Simultaneously, in order to avoid having only the depot in the route of the generated offspring \(x^{\prime}\), a repair operation is performed. In this repair operation, we choose a tour randomly that has more than two customers, and move one customer to the route which has only one depot. The pseudo code of the recombine algorithm is given in Algorithm 5.