Feature Analysis for Designing Heuristics for the Electric Vehicle Routing Problem with Genetic Programming
Marko Ðurasević, Francisco Javier Gil-Gala · 2025
The electric vehicle routing problem (EVRP) is an important combinatorial optimisation problem gaining attention due to the growing environmental concerns. Like many other relevant combinatorial optimisation problems, this one is also NP-hard, meaning that an efficient algorithm to solve the problem optimally in reasonable time does not exist. Therefore, these problems are often solved using various heuristic methods. One type of heuristics that can efficiently solve various EVRPs are routing policies (RPs). RPs are simple greedy constructive heuristics that incrementally construct the solution to the problem. These heuristics can construct the solution simultaneously as it is being executed since they can quickly perform the next decision, but also react to unexpected situations that can occur in the problem. RPs are difficult to design manually, which prompted the application of hyper-heuristics to design them automatically, most notably genetic programming (GP). However, to be able to design RPs efficiently it is required to select an appropriate set of features that will be used to construct them. This study proposes a set of 30 features that should be used to construct RPs, and divides them into several sets based on their characteristics. Through an experimental analysis, different combinations of these terminal node sets were investigated to determine which features are the most relevant for GP to obtain the best RPs. Furthermore, the examined terminal sets are also analysed considering aspects such as execution time required by GP to calculate these terminal nodes and the size of the RPs that were obtained.