# Computational Approaches for Grocery Home Delivery Services
## 5 Computational Study and Analysis
### Interplay of Approaches for the Determination and the Improvement Step  
In this final experiment, we want to find out which combinations of the different approaches for the determination and the improvement step are most beneficial and which should be avoided. From Section 5.2, we learn that simple insertion is the fastest method for the determination step, showing a solid performance, while the ANS is the best method in terms of solution quality. However the ANS has the drawback that it can only be applied when the customer request rate is moderate (or on small instances). In Section 5.3, we observe that 1 move is a solid approach for the improvement step that scales well for larger problem instances. The application of more sophisticated local search operations in combination with an exact approach for a selected sub-problem (1 move + 1 swap + TSP(s)TW) shows the best performance in terms of solution quality at the price of high (but still acceptable) run times. \begin{table}
\begin{tabular}{l r r r r r r r r r} \hline \hline  & \multicolumn{6}{c}{**Large-Scale Problem Instances–60 Vehicles**} \\ \hline  & \multicolumn{6}{c}{\({}^{\text{Five}}\)} & \multicolumn{6}{c}{\({}^{\text{Five}}\)} & \multicolumn{6}{c}{\({}^{\text{Five}}\)} & \multicolumn{6}{c}{\({}^{\text{Five}}\)} \\ \(i\) & 10 & 20 & 30 & 10 & 20 & 30 & 10 & 10 & 20 & 30 \\ \hline Avg. \(p\) & 1997.20 & 1998.50 & 1998.50 & 1999.40 & 1999.40 & 1999.40 & 1999.80 & 1999.80 & 1999.80 \\ Avg. number of & & & & & & & & & \\ \hline time windows offered & 9.99 & 9.99 & 9.99 & 9.99 & 9.99 & 9.99 & 9.99 & 9.99 & 9.99 \\ \hline Avg. run time & & & & & & & & & \\ (mmaxs.zz) & & & & & & & & & \\ (move*isaps) & 00:04.303 & 00:06:907 & 00:10:578 & 00:05:340 & 00:08:930 & 00:12:567 & 00:04:939 & 00:08:126 & 00:01:1208 \\ move*isaps & 00:59.003 & 01:28:161 & 01:57:892 & 01:25:017 & 02:02:721 & 02:01:010 & 01:13:388 & 01:04:070 & 02:10:396 \\ move*isaps*t=ST(s)TW & 00:59.980 & 01:29:274 & 01:59:241 & 01:09:592 & 02:05:107 & 02:56:644 & 01:16:316 & 01:05:040 & 02:14:499 \\ \hline Avg. improvement & & & & & & & & & \\ (move*isaps) & 1.62 & 3.27 & 4.93 & 1.69 & 3.54 & 5.12 & 1.60 & 3.29 & 4.82 \\ move*isaps*t=ST(s)TW & 2.29 & 4.16 & 5.94 & 2.46 & 4.57 & 6.28 & 2.33 & 4.26 & 5.92 \\ move*isaps*t=ST(s)TW & 2.35 & 4.24 & 6.05 & 2.56 & 4.73 & 6.48 & 2.39 & 4.35 & 6.03 \\ \hline Avg. number of & & & & & & & & & \\ (mallers solved) & & & & & & & & & \\ (move*isaps*t=ST(s)TW & 23.43 & 30.64 & 33.58 & 24.65 & 31.41 & 34.48 & 24.09 & 31.09 & 34.22 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Summary of the computational experiments for the improvement approaches considering instances with 2000 customers served by 80 vehicles. The improvement step is triggered after every \(i\)th (\(i=10,20,30\)) successful insertions. Further evaluations are based on the average-sized grocery delivery-use case (Section 5.3) and will focus on aforementioned time window determination and improvement approaches. Hence, we compare the resulting four combinations {simple insertion, ANS} \(\times\) {1 move, 1 move + 1 swap + TSP(s)TW} concerning the following key figures:  
* Average run time of the determination and improvement step;
* Average number of offered delivery time windows;
* Average total number of customer orders that have been inserted into the final schedules. In Table 6, we report the results of this experiment. First, we notice that now when analyzing the interplay of the determination and the improvement step the differences between ANS and the simple insertion heuristic become less evident. ANS shows little benefit compared to the simple insertion heuristic in terms of the number accepted orders \(\hat{p}\) (at most a 0.4% improvement) and the number of offered time windows. The use of ANS reduces the run time of the improvement step.