# Computational Approaches for Grocery Home Delivery Services
## 5 Computational Study and Analysis
### Comparing Approaches for the Determination Step
\begin{table}
\begin{tabular}{l r r r r r r r r r} \hline \hline  & \multicolumn{6}{c}{\(\mathcal{W}_{\text{OV3}}\) (10 Windows)–60 Vehicles} \\ \hline  & \multicolumn{6}{c}{**Non-Optimized Schedules**} & \multicolumn{6}{c}{**Optimized Schedules**} \\ Avg. \(\beta\) & \multicolumn{6}{c}{628.0} & \multicolumn{6}{c}{1880.0} \\ Fill level & 85\% & 90\% & 95\% & 99\% & 85\% & 90\% & 95\% & 99\% \\ \hline Avg. run time (mmss.zzz) & & & & & & & & \\ Simple insertion & 00:00.001 & 00:00.001 & 00:00.001 & 00:00.001 & 00:00.001 & 00:00.001 & 00:00.001 & 00:00.001 \\ TSP(s)TW insertion & 00:02.645 & 00:15.541 & 01:27.422 & 05:02.061 & 00:56.969 & 00:54.045 & 01:04.239 & 00:17.879 \\ ANS & 00:00.012 & 00:00.112 & 00:00.847 & 00:08.412 & 00:00.052 & 00:00.057 & 00:00.073 & 00:08.981 \\ \hline Avg. number & & & & & & & & \\ Simple insertion & 9.57 & 9.05 & 7.40 & 0.76 & 9.98 & 9.98 & 9.68 & 0.72 \\ TSP(s)TW insertion & 9.84 & 9.68 & 8.96 & 5.04 & 10.00 & 10.00 & 9.84 & 0.70 \\ ANS & 9.99 & 9.95 & 9.83 & 8.43 & 10.00 & 10.00 & 9.84 & 6.36 \\ \hline Combined & 9.99 & 9.95 & 9.87 & 8.76 & 10.00 & 10.00 & 10.00 & 6.36 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Summary of the computational experiments concerning the approaches for the determination step using \(\mathcal{W}_{\text{OV1.5}}\) considering non-optimized and 1 move-optimized schedules. \begin{table}
\begin{tabular}{l r r r r r r r r} \hline \hline  & \multicolumn{6}{c}{**\(\mathcal{W}_{\text{OV3}}\) (12 Windows)–60 Vehicles**} \\ \hline  & \multicolumn{6}{c}{**Non-Optimized Schedules**} & \multicolumn{6}{c}{**Optimized Schedules**} \\ Avg. \(\beta\) & \multicolumn{6}{c}{406.0} \\ Full level & 85\% & 90\% & 95\% & 99\% & 85\% & 90\% & 95\% & 99\% \\ \hline Avg. run time (mmss.zzz) & & & & & & & \\ Simple insertion & 00:00.001 & 00:00.001 & 00:00.001 & 00:00.001 & 00:00.001 & 00:00.001 & 00:00.001 & 00:00.001 \\ TSP(s)TW insertion & 00:02.645 & 00:15.541 & 01:27.422 & 05:02.061 & 00:56.969 & 00:54.045 & 01:04.239 & 00:17.879 \\ ANS & 00:00.012 & 00:00.112 & 00:00.847 & 00:08.412 & 00:00.052 & 00:00.057 & 00:00.073 & 00:08.981 \\ \hline Avg. number & & & & & & & & \\ Simple insertion & 11.84 & 11.02 & 8.54 & 1.21 & 12.00 & 12.00 & 11.90 & 0.73 \\ TSP(s)TW insertion & 11.93 & 11.73 & 10.78 & 6.65 & 12.00 & 12.00 & 11.92 & 0.69 \\ ANS & 12.00 & 11.98 & 11.94 & 10.16 & 12.00 & 12.00 & 12.00 & 7.59 \\ \hline Combined & 12.00 & 11.99 & 11.97 & 10.73 & 12.00 & 12.00 & 12.00 & 7.59 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Summary of the computational experiments concerning the approaches for the determination step using \(\mathcal{W}_{\text{OV3}}\) considering non-optimized and 1 move-optimized schedules. schedules at 99%. The run times of the ANS stay below 1 s for nearly all experiments with up to a 95% fill level. The ANS clearly performs best in terms of solution quality on instances having a 99% fill level, resulting in up to 11 times more available delivery time windows than with simple insertion. However, on those instances its run time reaches up to 9 s. It is worth pointing out that the performance of the ANS is nearly constant over all three sets of time windows, showing that it can also deal with instances having overlapping delivery time windows. In general, we notice a slight performance drop of the ANS (compared to the TSP(s)TW insertion approach) when being applied non-optimized schedules compared to optimized schedules. This can be explained by the fact that identifying feasible time windows is less hard for non-optimized schedules as they contain less orders on average. Additionally, there is more potential for improvement when applying TSP(s)TW insertion as the single tours have not been improved in any way after inserting the customers. Additionally, we observe that \"combined\" shows only a marginal improvement over the ANS for optimized schedules. On the other hand, we notice a strong improvement of \"combined\" compared to the TSP(s)TW insertion approach and ANS for non-optimized schedules at a 99% fill level.