# Evolving Dispatching Rules for Dynamic Vehicle Routing with Genetic Programming
## 6 Solving VRPTW with the Hyper-Heuristic Approach
### Creating Heuristics for VRPTW with Soft Time Windows  
As an example of adaptability of the proposed approach, we tackle the VRPTW variant with soft time constraints [55; 56]. In this case, we allow the requests to be serviced outside the defined time window, but which induces additional cost. This cost is usually proportional to the time window violation, but the actual cost estimate may be formulated in any possible way.  
To accommodate for soft time window constraints, the only change that must be made is the definition of a \"valid customer\" in the meta-algorithm. Instead of disregarding all customers that cannot be reached before the due date, we can introduce an additional amount of tolerance. In our experiments, the maximum time window tolerance is set to be twice as large as the denoted service time. This is completely arbitrary and may be defined to match the customer preferences, and even be modeled after individual customer constraints (e.g., delays at different types of customers incur different costs). Additionally, a variable _tard_ is added to the GP set of terminals; this variable represents the tardiness of service if the current customer is selected (the value is zero if no tardiness is incurred if this customer is selected).  
With these changes, the user can define a modified fitness function to measure the impact of tardiness of customers services. For the GP algorithm, the fitness function was modified as outlined in Equation (3), in which _totalTardiness_ denotes the amount of time that the service at all customers has been delayed.  
\[\text{objectiveVRPTWS}=(\text{nVehicles}\times 10,000)+\text{totalDistance}+w_{T} \times\text{totalTardiness}, \tag{3}\]  
The weight factor \(w_{T}\) denotes the magnitude of tardiness in relation to travelled distance, and equals 1 in this study. Note that this is also completely arbitrary and adaptive, since  
Figure 5: Total travelled distance in dynamic VRPTW—GP dispatching rules.  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Heuristic** & **Static** & **Dynamic 5\%** & **Dynamic 25\%** & **Dynamic 50\%** \\ \hline earliest first (EF) & 3552.1 & 3736.4 & 3772.1 & 3393.9 \\ urgent first (UF) & 4414.3 & 4416.3 & 4358.3 & 4367.1 \\ GP—min & 2586.1 & 2600.9 & 2574.2 & 3051.5 \\ GP—median & 2964.5 & 2870.8 & 3004.2 & 3246.0 \\ GP—max & 3553.1 & 3480.1 & 3555.8 & 3602.1 \\ \hline \hline \end{tabular}
\end{table}
Table 8: Total travelled distance—dynamic VRPTW.  
the tardiness cost may be additionally scaled to have a greater or smaller impact relative to other elements in the fitness.  
The learning process with soft time windows was repeated on the same learning set as for the regular VRPTW. The results for this experiment were validated on the same test set of 10 problem instances with 200 customers and are shown in Table 9. The results are compared to best known values with hard time window constraints, as well as GP heuristic results (given in the first two rows of the table). When soft time constraints are introduced, we can perceive a slight decrease in the number of vehicles, which means the heuristic is able to reduce vehicle count with the increase in total service tardiness. At the same time, the total distance is not changed substantially, which shows the applicability of the devised priority functions. To further reduce the number of vehicles, an appropriate scaling factor associated with tardiness could be introduced by the user in the objective function.