# Computational Approaches for Grocery Home Delivery Services
## 5 Computational Study and Analysis
### Comparing Approaches for the Determination Step
\begin{table}
\begin{tabular}{l c c c c c c c c} \hline \hline  & \multicolumn{6}{c}{\(\mathcal{W}_{\text{NO}}\) **(10 Windows)–60 Vehicles**} \\ \hline  & \multicolumn{6}{c}{**Non-Optimized Schedules**} & \multicolumn{6}{c}{**Optimized Schedules**} \\ Avg. \(\hat{p}\) & \multicolumn{6}{c}{408.0} & \multicolumn{6}{c}{1907.3} \\ Fill level & 85\% & 90\% & 95\% & 99\% & 85\% & 90\% & 95\% & 99\% \\ \hline Avg. run time & & & & & & & & \\ (mm:ss.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 \\ TS(s)TW insertion & 00:00.223 & 00:00.422 & 00:01.112 & 00:01.970 & 00:00.592 & 00:00.580 & 00:00.743 & 00:00.455 \\ ANS & 00:00.024 & 00:00.089 & 00:00.468 & 00:04.031 & 00:00.049 & 00:00.052 & 00:00.077 & 00:01.377 \\ \hline Avg. number & & & & & & & & \\ of feasible slots & & & & & & & & \\ Simple insertion & 9.82 & 9.47 & 7.67 & 2.00 & 9.98 & 9.98 & 9.83 & 4.20 \\ TSPs(s)TW insertion & 9.85 & 9.62 & 8.60 & 4.30 & 9.98 & 9.98 & 9.83 & 4.29 \\ ANS & 9.96 & 9.94 & 9.93 & 9.39 & 9.98 & 9.98 & 9.98 & 9.63 \\ \hline Combined & 9.96 & 9.94 & 9.93 & 9.43 & 9.98 & 9.98 & 9.98 & 9.63 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Summary of the computational experiments concerning the approaches for the determination step using \(\mathcal{W}_{\text{NO}}\) considering non-optimized and imove-optimized schedules. As a reference to compare against, we select the simple insertion heuristic. Both other methods, TSP(s)TW insertion and ANS, are entitled to find at least the delivery time slots that are determined by the simple insertion heuristic. This property is guaranteed due to the construction of those methods. Unfortunately, we can not provide an upper bound for the number of feasible delivery time slots as, to the best of our knowledge, there is no more powerful search method applicable for the SOP in the current literature. In our experiments, we restrict the ANS to move operations, as preliminary experiments showed that allowing 1 swap operations yields unacceptably long run times (up to some minutes). Additionally, the results are only insignificantly better. Primarily, we notice that the simple insertion heuristic returns solutions for the SOP in less than one millisecond for all considered instances. At fill level (85%) the instances are still rather easy and, hence, the simple insertion heuristic determines nearly all time slots as being feasible. While the simple insertion heuristic still performs well at 90% and 95% on optimized schedules, it performs poorly on non-optimized schedules with the same fill levels due to the lower quality of the schedules. Furthermore, we observe that the TSP(s)TW insertion approach yields a slight improvement over the simple insertion heuristic in terms of available time windows at 85-95%. However, a significant improvement can be observed when it is applied to non-optimized schedules at a 99% fill level. TSP(s)TW insertion shows acceptable run times for \(\mathcal{W}_{\text{NO}}\). In contrast, run times for \(\mathcal{W}_{\text{OV1.5}}\) and \(\mathcal{W}_{\text{OV3}}\) are between 3 s and nearly 4 min and are thus unacceptable. Hence, considering these findings, the TSP(s)TW insertion turns out to be impractical for AHD systems. Moreover, we notice that the ANS yields significantly more feasible time slots than the simple insertion heuristic (and TSP(s)TW insertion) on non-optimized schedules at 95% and 99%. Similar behavior can be observed on optimized