# Evolving Dispatching Rules for Dynamic Vehicle Routing with Genetic Programming
## 3 Hyper-Heuristic Approach for VRP
### Generating Heuristics for VRP  
The scheduling method applied in this work is priority scheduling, in which certain elements of the system are assigned priority values. In the classic scheduling theory, the typical elements are jobs (activities) and machines (resources), but the same logic can be applied to VRP scheduling with customers and vehicles. The choice of the next customer for a particular vehicle is based on the customer's priority value, which may be determined dynamically. This type of scheduling algorithm is also called, variously, 'dispatching rule','scheduling rule' or just 'heuristic'. The term dispatching rule (DR), in a narrow sense, often represents only the priority function that assigns values to system elements [45]. For instance, in classic scheduling a scheduling process may be described with the statement'scheduling is performed usingthe shortest processing time (SPT) rule', in which case jobs are sequenced in increasing order of their processing times. In VRP, a very simple heuristic may be the one that, for every vehicle, chooses the current closest customer as the next one. In terms of priority scheduling, we can say that the priority function applied to each customer is equal to that customer's current distance. While the method of assigning vehicles to customers based on priority values may be trivial, in some environments it is not necessarily so. This is particularly true in dynamic conditions, where orders may arrive over time or may not be serviced before some condition is met. Even when the priority function is defined, an additional procedure must be defined dictating how customers are serviced based on their priorities and possible system constraints. In accordance to existing scheduling nomenclature, we name this component a meta-algorithm [9; 10; 46], or alternatively a schedule generation scheme (SGS) [47; 48], which is a term commonly used in production scheduling. A meta-algorithm encapsulates the priority function, but the same meta-algorithm may be used with different priority functions and vice versa. In this work, the meta-algorithm is defined manually; the priority function, on the other hand, is evolved automatically with genetic programming and represented using appropriate functions and variables. This way, using the same meta-algorithm, different scheduling heuristics best suited for various criteria can be devised. We propose two meta-algorithms, which differ by the way they construct the entire schedule, and consequently by the conditions they can be used in. The first meta-algorithm is a serial one, which builds the schedule incrementally by constructing routes one vehicle at a time. This approach is most commonly used in existing VRPs and is depicted in Algorithm 1. ```
1:while customers there are customers to serve do
2: start new route;
3:while unvisited valid customers do
4:nextCustomer\(\leftarrow\) customer with the best value of the priority function;
5: add nextCustomer to current route;
6:endwhile
7: end route by returning the vehicle to the depot;
8:endwhile
```  
**Algorithm 1** Serial VRP meta-algorithm  
We emphasise that the same meta-algorithm may be used for any VRP flavor; at the same time, the meta-algorithm does not depend on any concrete priority function, which means that many different priority functions can be used with the given meta-algorithm. As a consequence, the meta-algorithm can use priority functions which optimise different objectives. Note that the condition \"valid customer\" may have a very different meaning for different VRP variants. For instance, in CVRP this will only constrain the available choices to those customers whose demand does not exceed the remaining capacity of the current vehicle. For VRPTW, on the other hand, this will also constrain the choice to those customers which can be serviced in the defined time frame. The selection of the next valid customer to service is left entirely to the priority function.