A greedy search based evolutionary algorithm for electric vehicle routing problem

Abstract

Over the years, there have been many variations of the Vehicle Routing Problem created to fit the actual needs of society, one of which is the Electric Vehicle Routing Problem (EVRP). EVRP is a more complex and challenging combinatorial optimization than the conventional vehicle routing problem. This paper considers a specific model for the tram routing problem and proposes a clustering-inspired greedy search algorithm GS. GS algorithm aims to cluster charging routes and greedily search charging stations for the optimal route output. In this paper, we purposely implement GS into a meta-heuristic genetic algorithm GA to utilize GA’s finding a globally optimal, leading to the formulation of the GSGA algorithm. To evaluate performance, we use a benchmark dataset found in the CEC-12 Tram Routing Problem CEC-12 Competition at the World Congress on Computational Intelligence (WCCI) 2020. The experiment evaluates GS’s effectiveness when applied to other algorithms such as genetic algorithms and simulated annealing. The experiments results show that our proposed algorithm has better solution quality than previous algorithms.