# SVD Enhanced Metaheuristic for Plug-In Hybrid Electric Vehicle Routing Problem
## 4 Methodology
### Memetic Algorithm  
Memetic Algorithm (MA), a population-based metaheuristic, is an improvement of the evolutionary algorithm (EA). It is defined by the collaboration between cultural evolution and natural evolution to explore and exploit the search [36]. The concept of MA was inspired by [PERSON]'s notion of memes (a unit of cultural evolution), which consists of self-improvement [37]. The classical memetic algorithm is a combination of EA and local search procedure (LSP). The pseudo code of standard MA is given in Algorithm 1. Firstly, an initial population is generated randomly and a local search procedure is applied to optimize it. Then, the fitness values of all the individuals are calculated by using an evaluation process. Afterwards, during the whole loop, the selection, crossover and mutate operators are employed to generate new offsprings. These offsprings are further optimized through the local search procedure, then these solutions are evaluated through the evaluation process. After that, the SelectNewPop operator tries to choose the best individuals for the population of the next generation. These steps are repeated until the stopping criterion is satisfied. ```
Input: Data of problem and parameters of algorithm Output: The best individual Begin \(t\gets 0\) P(t)\(\leftarrow\)InitPop() P(t)\(\leftarrow\)LocalSearch(P(t)) Evaluate Fitness(P(t)) Whilestopping criterion is not satisfied DO P(t)\(\leftarrow\)Selection(P(t)) P(t)\(\leftarrow\)Crossover(P'(t)) P(t)\(\leftarrow\)Mutate(P'(t)) P(t)\(\leftarrow\)LocalSearch(P'(t)) Evaluate Fitness(P'(t)) P(t+1)\(\leftarrow\)SelectNewPop(P(t),P'(t)) t\(\leftarrow\)t+1 EndWhile End

### Representation and Evaluation

The solution consists of \(n\) customers and \(q(q\geq 0)\) selected fuel or electric stations, where the power stations come from sets \(S_{e}\) and \(S_{f}\). Each customer must be visited and can only visited once, but each electric station and fuel station may be visited more than once or not at all. Therefore, the number of visited power stations in solutions may be different. Index 0 represents the depot, the \(i^{th}\) number in \(1,2,...,n\) denotes the \(i^{th}\) customer to be served. The following number of \(n+1,n+2,...,n+m\) then denotes the index of power stations. Figure 1 shows two feasible solutions. An example in Figure 1 shows the representation for an instance where 15 customers need to be visited and 4 power stations were considered, indexes 1 to 15 represent the customers, 16 and 17 electric stations, 18 and 19 fuel stations. As can be seen from Figure 0(a),b, we adopt a chromosome coding method in which \(-1\) is used as the delimiter between routes. In Figure 0(a) only 15 customers were visited without access to the energy station and 4 vehicles were used to visit all customers. In Figure 0(b), all customers were visited by 3 vehicles, and the second vehicle and the third vehicle visit a electric station and a fuel station in their tour, respectively. Comparing two representations, the latter uses fewer vehicles because there are vehicles visiting the power station on the way, their driving distance capacity was extended. Of course, their driving time still should not exceed \(T_{max}\). As we considered more constrains than GVRP [5] and HVRP [6] in this work, there would be more infeasible solutions during the computation of the objective function; however, the elimination of all infeasible solutions would harm the diversity of the population and the solution would highly likely fall into local optimum. Therefore, we introduced a penalty mechanism to maintain the diversity of population. The evaluation of the solution can be described as follows--the delimiter is a sign to distinguish different routes. For each route, we need to determine whether time constraint and vehicle energy capacity constraint are satisfied. We set the time constraint as a soft time constraint, and the solution beyond \(T_{max}\) is also acceptable.