# Evolving Dispatching Rules for Dynamic Vehicle Routing with Genetic Programming
## 6 Solving VRPTW with the Hyper-Heuristic Approach  
When considering the static VRPTW model, we use the fitness function denoted in Equation (2) (same as for the CVRP) for optimisation of priority functions.  
\[\text{objectiveVRPTW}=(\text{nVehicles}\times 10,000)+\text{totalDistance} \tag{2}\]  
The experiments for VRPTW were conducted on Gehring and Homberger benchmark [53] containing problems with 200 to 1000 customers. For all problem instances, travel time and distance are equal to the corresponding Euclidean distance [54]. Separate experiments were conducted on groups with 200, 400, 600, 800 and 1000 customers; out of each group, 40 test instances were selected as the learning set, and 10 of the remaining instances were used as the test set. The learning process is performed in static conditions, while the dynamic variant is evaluated in the following subsection.  
In addition to functional elements in Table 1, we define the following terminals for GP in the VRPTW environment, as given in Table 6. This terminal set is an extension of the terminals used in CVRP, with the addition of time-dependent information for each vehicle. The terminal waiting time denotes the amount of time the vehicle will have to wait for customer's ready time (window opening) if it selects this customer for servicing next.  
After the learning phase, the resulting solutions were evaluated on the test set. Figure 3 shows the results obtained on a test set with 200 customers, but also presents the results of each group of priority functions obtained by learning on different learning set sizes. Since the results suggest that learning on a larger set of customers does not bring an improvement, we have evaluated the solutions, obtained on the learning set with a given number of customers, on each test set with a different number of customers. The purpose of this cross-evaluation was to identify any dependence of the number of customers in the learning phase on the effectiveness of priority functions on problem instances with a different customer number. The results in terms of box plots on the test set are given in Figure 4, with the circles representing outliers and the '+' symbol representing the average value.  
Figure 2: Total travelled distance in dynamic CVRP—GP dispatching rules.  
It can be observed that the number of customers in the learning set does not influence the final effectiveness to a great extent, which can be considered a good trait for scalability to larger instances. It is interesting to note, however, that the priority functions learned on a smaller number of customers generally achieve the best results, regardless of the number of customers in the test set. This is encouraging, since less time can be spent on learning with smaller number of customers, and still be able to obtain solutions that cope well with different problem sizes. To illustrate the absolute quality of the generated solutions, we compare the obtained number of vehicles on the test set with best known results for the chosen test set instances [[https://www.sintef.no/projectweb/top/vrptw/homberger-benchmark](https://www.sintef.no/projectweb/top/vrptw/homberger-benchmark)]([https://www.sintef.no/projectweb/top/vrptw/homberger-benchmark](https://www.sintef.no/projectweb/top/vrptw/homberger-benchmark)) (29 May 2023); the results are shown in Table 7.  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Terminal** & **Description** \\ \hline dist & distance to the customer being considered \\ d & customer demand \\ rc & vehicle remaining capacity \\ drc & ratio of demand to remaining capacity \\ ncc & ‘next closest customer’ \\ st & customer service time \\ trtt & amount of time till the customer becomes ready \\ ttdd & amount of time till customer due date \\ wt & ‘waiting time’ \\ \hline \hline \end{tabular}
\end{table}
Table 6: GP terminals for VRPTW.  
Figure 3: Test results on VRPTW instances with 200 customers.