Route Optimization of Electric Vehicles Based on Reinsertion Genetic Algorithm

The “mileage anxiety” of electric vehicles (EVs) has led to do the study on the EV routing problem (EVRP). In this article, the remove–reinsert genetic algorithm (RI-GA) is applied to the EVRP with a time window (EVRPTW) for saving energy and reducing transportation costs. The initialization and the variation of the genetic algorithm are improved to obtain a routing schedule with less energy consumption. The neighborhood search method improves the population initialization to obtain high-quality initialized populations. Removal and reinsertion methods are proposed to destruct and repair the routing. During the removal process of RI-GA, the relevance removal strategy is designed. By comparing the correlation between nodes, the nodes with high correlation are removed simultaneously, providing directionality for the removal of the customer stops. The relationship between individual fitness and population average fitness is compared and the number of nodes removed is automatically adjusted. The minimum energy consumption incremental reinsertion method is employed in the reinsertion process of RI-GA to obtain the routing schedule with less energy consumption. Compared to the least-cost convergence of the original GA and RI-GA, the convergence speed of RI-GA is faster by five times, and the routing cost is reduced by 6%. The comparison with Solomons data demonstrates the advantages of the RI-GA, with a reduction of about 10% in route distance. The superiority of this improved algorithm becomes more apparent as the number of customer stops increases and the transportation routes become more complex, and the reduction in energy consumption increases from 7.95% to 12.33%. Finally, the performance of the RI-GA is verified in the apple transportation problem in Hudson Valley, New York, which proves the practicality of this algorithm.