# 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  
Table 6 presents the performance of AASA against VRPHAS, ILS-MIP, and the no-splitting strategies for the instances of SET-1. First, we observe that the no-splitting method results in very low-quality solutions as the resulting optimality gap obtained by this method is very high compared to the VRPHAS, AASA, and ILS-MIP heuristics. Moreover, we observe that while the ILS-MIP strategy outperforms the AASA and VRPHAS solution approaches in terms of optimality gap for almost all instances of SET-1, it requires very large computation times. The average runtime for ILS-MIP is 992.38 s as opposed to the \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Instance** & \multicolumn{2}{c}{**CVRP Size**} & \multicolumn{2}{c}{**Number of Routes**} \\ \hline  & **VRPHAS** & **AASA** & **VRPHAS** & **AASA** \\ \hline p02\_1050 & 297 & 283 & 27 & 27 \\ p02\_1090 & 382 & 377 & 48 & 47 \\ p02\_3070 & 370 & 293 & 48 & 48 \\ p02\_7090 & 462 & 377 & 75 & 75 \\ p03\_110 & 346 & 244 & 6 & 6 \\ p03\_1030 & 411 & 333 & 23 & 23 \\ p03\_1050 & 471 & 376 & 37 & 37 \\ p03\_1090 & 608 & 476 & 67 & 67 \\ p03\_3070 & 571 & 369 & 66 & 66 \\ p03\_7090 & 711 & 591 & 100 & 99 \\ p04\_110 & 516 & 315 & 10 & 10 \\ p04\_1030 & 613 & 467 & 34 & 34 \\ p04\_1050 & 705 & 547 & 55 & 55 \\ p04\_1090 & 915 & 676 & 98 & 98 \\ p04\_3070 & 855 & 649 & 98 & 98 \\ p04\_7090 & 1063 & 879 & 149 & 149 \\ p05\_110 & 657 & 475 & 12 & 12 \\ p05\_1030 & 804 & 616 & 43 & 43 \\ p05\_1050 & 920 & 621 & 67 & 69 \\ p05\_1090 & 1169 & 824 & 123 & 124 \\ p05\_3070 & 1119 & 806 & 124 & 126 \\ p05\_7090 & 1401 & 1082 & 199 & 197 \\ p11\_110 & 422 & 233 & 8 & 8 \\ p11\_1030 & 489 & 388 & 27 & 27 \\ p11\_1050 & 560 & 475 & 42 & 43 \\ p11\_1090 & 722 & 543 & 78 & 78 \\ p11\_3070 & 680 & 500 & 77 & 76 \\ p11\_7090 & 849 & 663 & 119 & 119 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: \(Cont.\) \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Instance** & \multicolumn{2}{c}{**CVRP Size**} & \multicolumn{2}{c}{**Number of Routes**} \\ \hline  & **VRPHAS** & **AASA** & **VRPHAS** & **AASA** \\ \hline eil22 & 69 & 47 & 4 & 4 \\ eil23 & 74 & 44 & 3 & 3 \\ eil30 & 110 & 57 & 4 & 4 \\ eil33 & 108 & 72 & 4 & 4 \\ eil51 & 157 & 139 & 6 & 6 \\ eilA76 & 228 & 215 & 10 & 10 \\ eilB76 & 254 & 215 & 15 & 15 \\ eilC76 & 231 & 201 & 8 & 8 \\ eilD76 & 216 & 215 & 7 & 7 \\ eilA101 & 347 & 248 & 8 & 8 \\ eilB101 & 265 & 248 & 14 & 14 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: CVRP instance attributes: VRPHAS vs. AASA on SET-4. average runtime of 86.14 s and 30.56 s corresponding to the VRPHAS and AASA solution approaches, respectively. This huge time complexity hinders the practical application of the ILS-MIP approach in real-world problems with time sensitivity or scalability requirements. Figures 4 and 5 illustrate the per-instance optimality gap and runtime of our proposed splitting rule against the fixed splitting rule introduced in VRPHAS. Our proposed method outperforms the VRPHAS in terms of time complexity for all instances, and it also improves upon the average optimality gap of VRPHAS. Moreover, while the VRPHAS method results in the 5.50% optimality gap in the worst-case scenario (\(SD16\)), AASA achieves the maximum optimality gap of 3.81% for the same instance. We also observe that AASA finds the best-known solution for four instances as opposed to the VRPHAS method obtaining the best-known solution for three instances of SET-1. Table 7 shows the results of VRPHAS, AASA, and the no-splitting methodologies for the instances of SET-2. According to Table 7, the no-splitting approach results in a higher gap compared to both the VRPHAS and AASA rules. Furthermore, our proposed AASA strategy outperforms the VRPHAS method in terms of the average optimality gap, as well as runtime. Moreover, the per-instance results depicted in Figures 6 and 7 indicate that the AASA strategy improves upon the optimality gap and solver runtime of the VRPHAS method for almost all instances of SET-2.