Automated Design of Heuristics with Genetic Programming for the Electric Vehicle Routing Problem with Partial Recharging

The electric vehicle routing problem (EVRP) is a complex optimisation problem concerned with constructing efficient routes for electric vehicles, while considering constraints such as battery capacity and charging station availability. Due to the inherent difficulty of the problem, heuristics are the most common method used for solving them. Routing policies (RPs) are simple constructive heuristics that solve the problem by incrementally constructing the solution to it. This means that whenever a decision needs to be made, RPs determine it. Although this makes RPs well-suited for solving dynamic and large-scale problems, it is difficult to design such heuristics manually. For this reason, genetic programming is usually used, as it can generate better RPs than those designed manually. However, until now, most of the RPs were designed using the full recharging strategy for batteries. However, a lot of research demonstrated that this is suboptimal, and that better results can be obtained by using different partial recharging strategies. Therefore, in this study we use GP to generate RPs that incorporate several partial recharging strategies, including both fixed and adaptive recharging rates. The experimental study demonstrates that RPs that use partial recharging strategies outperform the full recharging strategy, leading to more efficient solutions.