# AAGA: A Priori Adaptive Splitting Algorithm for the Split Delivery Vehicle Routing Problem
## 3 Performance Evaluation
### Numerical Results
#### 3.4.2 Optimality Gap and Runtime Comparison: AASA against Baselines
It can also be observed that while the VRPHAS method exhibits an optimality gap of 2.51% in the worst-case scenario (576D4),  
Similarly, the comparison of the results for SET-3 and SET-4 provided in Tables 8 and 9 show that our proposed splitting algorithm again improves both average optimality gap and runtime of the VRPHAS splitting mechanism and, therefore, it can effectively generate higher-quality solutions, faster than VRPHAS. The improvement in the runtime is mainly owing to the rule granularity consideration introduced in AASA as discussed in Section 2.2, which results in smaller instances to be solved by the CVRP solver compared to the VRPHAS method. Figures 8 and 9 illustrate the per-instance optimality gap and runtime of SET-3. According to Table 8 and Figure 8, although the VRPHAS method results in the maximum optimality gap of 3.27% (\(p11\_1090\)), the worst-case optimality gap achieved by AASA is 2.54% (\(p02\_7090\)). The optimality gap and run-time of SET-4 instances are presented in Figures 10 and 11. Table 9 and Figure 10 illustrate that the AASA method improves the worst-case optimality gap of VRPHAS in SET-4, since AASA achieves the maximum optimality gap of 2.02% (\(eilA101\)) as opposed to the maximum gap of 2.35% obtained by VRPHAS for the same instance. Figure 6: Per-instance gap of SET-2. Figure 7: Per-instance solver runtime of SET-2. Figure 8: Per-instance gap of SET-3. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline
**Instance** & **Best-Known** & \multicolumn{2}{c}{**VRPHAS**} & \multicolumn{2}{c}{**AASA**} & \multicolumn{2}{c}{**No Splitting**} \\ \hline  & **Solution** & **Gap (\%)** & **Time (s)** & **Cost** & **Gap (\%)** & **Time (s)** & **Gap (\%)** \\ \hline p01\_110 & 459.50 & 0.00 & 9.84 & 459.50 & 0.00 & 6.63 & 0.00 \\ p01\_1030 & 757.17 &  
Figure 10: Per-instance AASA gap of SET-4. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline
**Instance** & **Best-Known** & \multicolumn{2}{c}{**VRPHAS**} & \multicolumn{2}{c}{**AASA**} & \multicolumn{2}{c}{**No Splitting**} \\ \hline  & **Solution** & **Gap (\%)** & **Time (s)** & **Cost** & **Gap (\%)** & **Time (s)** & **Gap (\%)** \\ \hline eil22 & 375.28 & 0.00 & 3.28 & 375.28 & 0.00 & 3.11 & 0.00 \\ eil23 & 568.56 & 0.00 & 5.92 & 568.56 & 0.00 & 2.92 & 0.00 \\ eil30 & 497.53 & 1.50 & 6.89 & 505.01 & 1.50 & 3.64 & 1.48 \\ eil33 & 826.41 & 1.36 & 6.89 & 837.67 & 1.36 & 5.08 & 1.36 \\ eil51 & 524.61 & 0.00 & 12.58 & 524.61 & 0.00 & 10.95 & 0.00 \\ eilA76 & 823.89 & 0.43 & 24.60 & 830.97 & 0.86 & 19.77 & 1.61 \\ eilB76 & 1009.04 & 1.96 & 31.86 & 1025.24 & 1.60 & 18.65 & 1.86 \\ eilC76 & 738.67 & 0.52 & 26.78 & 742.49 & 0.55 & 17.48 & 0.64 \\ eilD76 & 684.53 & 0.81 & 23.82 & 689.47 & 0.72 & 19.41 & 0.82 \\ eilA101 & 812.51 & 2.35 & 55.39 & 828.98 & 2.02 & 23.37 & 1.92 \\ eilB101 & 1076.26 & 1.57 & 30.90 & 1087.70 & 1.06 & 23.76 & 1.53 \\ \hline Average & & 0.96 & 20.80 & & 0.88 & 13.63 & 1.02 \\ \hline \hline \end{tabular}
\end{table} 
Table 9: Performance of VRPHAS, AASA, and the no-splitting methodologies on SET-4. Figure 9: Per-instance solver runtime of SET-3.