Investigation of Structures for Routing Rules Designed by Genetic Programming for the Electric Vehicle Routing Problem

The electric vehicle routing problem (EVRP) is becoming an increasingly important in today’s world. Its relevance stems from the fact that logistic processes play a pivotal role in many industries, but also since they have a negative influence on the environment. This motivates research on new methods that can solve such problems more efficiently. Routing rules (RRs) represent simple heuristics that can efficiently construct solutions for large or dynamic EVRPs. However, manual design of such heuristics is a tedious and time consuming process, because of which it is being automatised with the use of genetic programming (GP). Although GP can generate efficient RRs, their performance can be significantly influenced by the design choices performed when defining their structure. Therefore, in this study, we investigate how different design choices in the design of RRs influence their performance. We examine 4 design decisions, which concern the selection of customers, charging stations and vehicles during the process of solution construction. Through an extensive experimental analysis we investigate the influence of these design decisions on the performance of RRs for problems with different properties and structures. The obtained results demonstrate that the performance of RRs is heavily influenced by the different design choices, however, there is no single combination of those design choices that works best for all problem variants, and thus it is imperative to select them according to the problem variant that is being optimised.