In recent years, the growing interest in environmental sustainability has led to Electric Vehicle Routing Problems (EVRPs) attracting more and more attention. EVRPs involve the use of electric vehicles, which have additional constraints, such as range and recharging time, compared to conventional Vehicle Routing Problems (VRPs). The complexity and dynamic nature of solving VRPs often lead to the introduction of Routing Policies (RPs), simple heuristics that incrementally build routes. However, manually designing efficient RPs proves to be a challenging and time-consuming task. Therefore, there is a pressing need to explore the application of hyper-heuristics, in particular Genetic Programming (GP), to automatically generate new RPs. Since this method has not yet been investigated in the literature in the context of EVRPs, this study explores the applicability of GP to automatically generate new RPs for EVRP. To this end, three RP variants (serial, semiparallel, and parallel) are introduced in this study, along with a set of domain-specific terminal nodes to optimise three criteria: the number of vehicles, energy consumption, and total tardiness. The experimental analysis shows that the serial variant performs best in terms of energy consumption and number of vehicles, while the parallel variant is most effective in minimising the total tardiness. A comprehensive analysis of the proposed method is conducted to determine its convergence properties and the impact of the proposed terminal nodes on performance and to describe several generated RPs. The results show that the automatically generated RPs perform commendably compared to traditional methods such as metaheuristics and exact methods, which usually require significantly more runtime. More specifically, depending on the scenario in which they are used, the generated RPs achieve results that are about 20%-37% worse compared to the best known results for the number of vehicles in almost negligible time, in just some milliseconds.

The Travelling Salesman Problem (TSP) is a well-known optimisation problem that has been widely studied over the last century. As a result, a variety of exact and approximate algorithms have been proposed in the literature. When it comes to solving large instances in real-time, greedy algorithms guided by priority rules represent the most common approach, being the nearest neighbour (NN) heuristic one of the most popular rules. NN is quite general but it is too simple and so it may not be the best choice in some cases. Alternatively, we may design more sophisticated heuristics considering the particular features of families of instances. To do that, we have to consider problem attributes other than the proximity of the next city to build priority rules. However, this process may not be easy for humans and so it is often addressed by some learning procedure. In this regard, hyper-heuristics as Genetic Programming (GP) stands as one of the most popular approaches. Furthermore, a single heuristic, even being good in average, may not be good for a number of instances of a given set. For this reason, the use of ensembles of heuristics is often a good alternative, which raises the problem of building ensembles from a given set of heuristic rules. In this paper, we study the application of two kinds of ensembles to the TSP. Given a set of TSP instances having similar characteristics, we firstly exploit a GP to build a set of heuristics involving a number of problem attributes, and then we build ensembles combining these heuristics by means of a Genetic Algorithm (GA). The experimental study provided valuable insights into the construction and utilisation of single rules and ensembles. It clearly demonstrated that the performance of ensembles justifies the time invested when compared to using individual heuristics.