# SVD Enhanced Metaheuristic for Plug-In Hybrid Electric Vehicle Routing Problem
## 4 Methodology
### Memetic Algorithm
Delete Stations: A delete station means randomly taking out a power station from solution \(x\) Before performing this operation, it is necessary to determine whether there is an power stations in the solution, if there are power stations in the solution, select a deletion from the existing power station, and if not, the operation does not make any changes to the solution. Figure 2: Neighborhood structures. ### Hybrid Memetic Algorithm Based on SVND for Solving PHEV Routing Problem

In conjunction with the above sections, the overall scheme of the proposed algorithm in this paper is shown in Figure 3. To make our solution more applicable to the PHEV routing problem, we made some customized improvement on the Memetic algorithm. First, for population initialization, we proposed a new algorithm based on the nearest neighborhood heuristic, it takes the factors of time, vehicle capacitance and fuel capacity as well as the access to the energy station into account. Secondly, we introduced penalty mechanism to maintain the diversity of population. Last, we improved the traditional 2_opt method with a cyclic comparison technique. The algorithm can be summarized as the following steps. 1. Initialization operation is used to generate a set of solutions, an initial solution is generated by rules and others are generated randomly. The total number of initial solutions is defined as \(P_{s}\). 2. The 2_opt method is used to improve the generated solutions. 3. The objective function evaluation is carried out on these solutions. 4. The binary tournament selection operation is applied to choose the parents, then recombine operator or mutate operator is executed to generate new offspring. This step is repeated \(P_{s}\) times, in order to generate a new population with \(P_{s}\) individuals. 5. Evaluating the new population by using objective evaluation. 6. The SVND procedure is used to further improve the best individual at each generation, which searches all its neighborhoods according to a sequence and returns the best individual among all the searched neighbors. 7. Select the best individuals from the current population and the offsprings, they are considered as the population for the next generation, and the population size are always kept to \(P_{s}\). 8. If the stopping criterion is satisfied, the algorithm will be terminated and export the result, otherwise go to step 4. Steps 4 to 7 are executed in the iteration loop, in which the better solutions have a larger probability to be selected for the recombine operator or the mutate operator. It is noted that the recombine and mutation operators are used in a mutually exclusive manner, each offspring is generated by a recombine operator or a mutate operator but not both. The former is employed with probability \(P_{c}\), otherwise the latter operator is used. The number of new individuals generated in step 4 of each iteration is \(P_{s}\). In step 7, we arrange the total solutions in ascending order and select the non-repetitive \(P_{s}\) individuals in turn, if the objective values of the two solutions are identical but the compositions of the solutionsare different, then both solutions should be retained, provided that they will be arranged in \(P_{\rm s}\). Finally, the termination of the algorithm needs to satisfy the stopping condition. ## 5 Computational Experiments

The experimental results and analysis are described in detail in this section. A comparative study is also conducted with the work of [PERSON] et al. [8]. The proposed method was coded in C++ language and compiled on Microsoft Visual Studio 2017. the computing platform configuration are as following: Intel (R) Core (TM) i7 at 4.20 GHz, 16 GB of RAM with 64-bit platform under Windows 10 Operating System. The vehicle data used in this paper are the same as the work of [PERSON] et al. [8]. The relevant data are shown in Table 1. The test data we used for testing is a classic example of open source vehicle routing problem. It is an extension of the classical benchmark of VRP.