# Where to Split in Hybrid Genetic Search for the Capacitated Vehicle Routing Problem
## 5 Computational Study
### Comparison with Former Splitting Procedure  
We now thoroughly compare the performances of OX (the original hybrid genetic search), AOX (using the modified crossover operator), and SP4 (using the modified crossover operator and the new preprocessing for the splitting procedure). First, Figure 8 shows the primal gaps as a function of normalized running time. From the figure, it is clear that SP4 is an improvement over AOX, which again is an improvement over OX. The final primal gaps are 0.110% for OX, 0.105% for AOX, and 0.101% for SP4. The reduction of 0.004 percentage points when going from AOX to SP4 corresponds to a 3.9% reduction in the average primal gap. A paired \(t\)-test shows that the difference in final primal gaps is significant: the average difference is 0.0041 percentage points, with a standard deviation of 0.063 percentage points, leading to a test statistic of 2.047, and a two-way \(p\)-value of 0.041. Compared to the original implementation of hybrid genetic search, this comes on top of the previous improvement of 4.2% in primal gaps when using AOX instead of OX, for a total improvement of 7.9% in terms of the primal gap. Adding to this, Figure 8 illustrates that the SP4 variant has a lower average primal gap throughout the entire runs. Table 10 in the appendix shows the average objective function values obtained by each of the three methods for each instance. There are other angles from which to evaluate the performance of a heuristic than the average gaps obtained. Next, we consider the ability to match the best-known solutions, as it may be possible to obtain small average gaps without necessarily finding the best solution in many runs. Figure 9 shows the number of best-known solutions found, out of 1000 runs, for OX, AOX, and SP4. The number of best-known solutions found is increasing faster for SP4 near the end of the runs, and it just surpasses AOX at the end, with 372 best-known solutions found, compared to 371 for AOX and 347 for OX. Since SP4 has the best average gaps of the three methods, the similarity in terms of number of best-known solutions found suggests that there is a larger variance in the quality of the results for AOX than for SP4. This is  
Figure 7: Primal gaps as a function of time when considering all 100 instances, comparing the five new variants for deciding the initial customer of the giant tour in the splitting procedure. supported by the standard deviations of the final primal gaps, which are 0.143% for OX, 0.141% for AOX, and 0.136% for SP4. This means that the performances of OX and AOX are less predictable than the performance of SP4, and this unpredictability makes AOX more likely to obtain the very best solution, but also on average to obtain worse solutions. Instead of comparing the methods to the best-known solutions, we can also compare the methods directly to each other. Figure 10 shows the number of runs for which each method has found the best solution during the runs. Based on the figure, out of the three methods, SP4 looks to be more likely to find the best solution if we run all three methods in parallel. This happens despite AOX being equally likely to find the best-known solution in any given run. Figure 8: Primal gaps as a function of time when considering all 100 instances, comparing the previous versions of hybrid genetic search with the new version. Figure 9: Number of best-known solutions identified as a function of time, out of 1000 total runs. While Figure 10 suggests some differences between the three methods in terms of finding the best solution at the end of the run, these differences are not necessarily significant. To determine this, we use a non-parametric sign test [38]. In particular, we consider pairs of methods and count the number of runs where a given method performs better than another method. We consider a method to perform better if it either finds a better solution, or if it finds the same solution but uses less computational time to find it. Table 8 shows the results of pair-wise tests between SP4, AOX, and OX.