# Evolving Dispatching Rules for Dynamic Vehicle Routing with Genetic Programming
## 3 Hyper-Heuristic Approach for VRP
### Creating Priority Functions with GP  
In this paper, genetic programming is used to automatically create the priority function used in the above meta-algorithms. The priority function is represented as a syntax tree, where inner nodes are operators and leaves are terminals (function inputs, domain variables). The operator and terminal set must be previously defined and they should give the GP information needed to construct an adequate priority function. In this work, we use the following operators (functional elements and inner nodes of a tree) listed in Table 1.  
This function set is based on our previous experience with GP, as well as on a small set of tuning experiments to estimate the efficiency of individual operators. Aside from these, we define a separate terminal set (set of variables, tree leaves) for each considered VRP variant. For example, all the variants will include the terminal _dist_, which simply gives the distance of the current considered vehicle to the current considered customer. This way, the GP is able to create new priority functions that match the current conditions and user-defined criteria. GP uses the standard tree representation to encode priority functions. An example of a random GP tree that denotes a potential priority function of a DR is shown in Figure 1 (the terminal sets are defined below). GP creates a set of priority functions (individuals) in each generation, and each of those must be evaluated. The initial population is generated using the standard ramped half-and-half solution initialisation method. After the whole generation is evaluated, genetic operators (crossover, mutation and selection) are performed, thus producing the next generation of individuals (new candidate functions). The whole process is repeated until a predefined stopping criterion is met. \begin{table}
\begin{tabular}{c c} \hline \hline
**Function** & **Definition** \\ \hline + & binary addition \\ - & binary subtraction \\ * & binary multiplication \\ / & \(a/b=\begin{cases}1,&\text{if }|b|<0.000001\\ a/b,&\text{otherwise}\\ pos(a)=\max(a,0)\\ \end{cases}\) \\ \(\text{ifgt}\) & \(\text{ifgt}(a,b,c,d)=\begin{cases}c,&\text{if }a\geq b\\ d,&\text{otherwise}\\ \end{cases}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Functional elements used by GP. Figure 1: An example GP tree representing a priority function \((\text{dist}+\text{dist})*\text{pos}(\text{d})\). The evolutionary algorithm in this work uses a steady-state selection process, shown in Algorithm 3, where in each iteration only one individual from the population is replaced with a new one. The selection of the individual to be replaced is performed in a tournament of size three: the algorithm selects three individuals at random and eliminates the worst of those. The remaining tournament survivors are then used as parents to create a new individual using crossover. The crossover operators used are simple tree crossover, uniform crossover, size fair, one-point, and context preserving crossover [5], selected at random each time a crossover is performed. Following its creation, the new individual immediately undergoes mutation, which depends on the mutation rate parameter. In our experiments, this parameter equals 0.5, which results in five out of ten new individuals being mutated on average, and the operator is sub-tree mutation [5]. This kind of algorithm is convenient since it eliminates the need for specifying the crossover rate, and based on our previous experience provides a steady rate of convergence. Regarding the choice of genetic operators, in our previous experience with hyper-heuristic applications, different operators did not have a significant impact.