# Computational Approaches for Grocery Home Delivery Services
## 5 Computational Study and Analysis
### Interplay of Approaches for the Determination and the Improvement Step
This effect is most evident when overlapping time windows are used (\(\mathcal{W}_{\text{OV1,5}}\) and \(\mathcal{W}_{\text{OV3}}\)), especially for the 1 move + 1 swap + TSP(s)TW approach where a reduction of the run time of up to 71.4% is observed. Presumably, ANS creates better schedules when inserting the new customer, and therefore the improvement approaches have a better starting solution. In summary, we can conclude that using the ANS for the time window determination (and the insertion) step is preferred as long as the instances are sufficiently small (as in our use case) such that it can still be performed in accordance with the run-time requirements of the considered AHD service. However, the ANS gives a slight improvement compared to the simple insertion heuristic (as already shown in Section 5.3) and should therefore be \begin{table}
\begin{tabular}{l r r r r r r r r r} \hline \hline \multicolumn{10}{c}{**Average-Sized Grocery Home Delivery Problems**} \\ \hline  & & \(\mathcal{W}_{\text{No}}\) & & \(\mathcal{W}_{\text{OV1,5}}\) & & & \(\mathcal{W}_{\text{OV3}}\) & \\ Vehicles & 16 & 18 & 20 & 16 & 18 & 20 & 16 & 18 & 20 \\ \hline \multicolumn{10}{c}{**Determination: simple insertion, Improvement: move**} \\ \hline Avg. \(\hat{p}\) & 453.35 & 491.80 & 498.65 & 455.75 & 495.10 & 498.65 & 451.00 & 495.50 & 499.60 \\ Avg. number of time windows offered & 9.07 & 9.84 & 9.97 & 9.15 & 9.90 & 9.98 & 10.81 & 11.88 & 11.99 \\ \hline Avg. run time (mms.zz) & & & & & & & & & \\ Determination & 0.00.001 & 0.00.001 & 0.00.001 & 0.00.001 & 0.00.001 & 0.00.001 & 0.00.001 & 0.00.001 \\ Improvement & 0.00.076 & 0.00.103 & 0.00.114 & 0.00.103 & 0.00.134 & 0.00.138 & 0.00.096 & 0.00.123 & 0.00.127 \\ \hline \multicolumn{10}{c}{**Determination: simple insertion, Improvement: move**} \\ \hline Avg. \(\hat{p}\) & 454.25 & 494.00 & 499.05 & 456.95 & 499.95 & 499.00 & 452.80 & 496.00 & 499.65 \\ Avg. number of time windows offered & 9.09 & 9.87 & 9.98 & 9.15 & 9.92 & 9.98 & 10.86 & 11.91 & 12.00 \\ \hline Avg. run time (mms.zz) & & & & & & & & & \\ Determination & 0.00.001 & 0.00.001 & 0.00.001 & 0.00.001 & 0.00.001 & 0.00.001 & 0.00.001 & 0.00.001 \\ Improvement & 0.00.758 & 0.00.852 & 00.00.957 & 0.03.139 & 0.234.03 & 0.013.345 & 0.01.672 & 0.01.998 \\ \hline \multicolumn{10}{c}{**Determination: ANS, Improvement: move**} \\ \hline Avg. \(\hat{p}\) & 455.35 & 498.50 & 499.55 & 458.00 & 499.05 & 499.75 & 453.10 & 499.44 & 499.80 \\ Avg. number of time windows offered & 9.11 & 9.97 & 9.99 & 9.16 & 9.98 & 9.99 & 10.88 & 11.99 & 12.00 \\ \hline Avg. run time (mms.zz) & & & & & & & & & \\ Determination & 0.00.098 & 0.00.022 & 0.00.017 & 0.00.00 & 0.00.014 & 0.00.012 & 0.00.002 & 0.00.0017 \\ Improvement & 0.00.060 & 0.00.077 & 0.00.086 & 0.00.003 & 0.00.091 & 0.00.100 & 0.00.073 & 0.00.092 & 0.00.008 \\ \hline \multicolumn{10}{c}{**Determination: ANS, Improvement: move**} \\ \hline Avg. \(\hat{p}\) & 455.55 & 498.95 & 499.65 & 457.85 & 499.15 & 499.75 & 452.90 & 499.55 & 499.80 \\ Avg. number of time windows offered & 9.12 & 9.98 & 9.99 & 9.16 & 9.99 & 9.99 & 10.87 & 11.99 & 12.00 \\ \hline Avg. run time (mms.zz) & & & & & & & & & \\ Determination & 0.00.104 & 0.00.026 & 0.00.020 & 0.00.088 & 0.00.014 & 0.00.014 & 0.00.114 & 0.00.023 & 0.00.019 \\ Improvement & 0.00.713 & 0.00.889 & 0.00.862 & 0.00.898 & 0.01.138 & 0.00.099 & 0.00.883 & 0.01.158 & 0.01.161 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Summary of the computational experiments for different combinations of time window determination (simple insertion, ANS) and improvement approaches (1 move, 1 move + 1 swap + TSP(s)TW) considering instances with 500 customers. utilized if the frequency of incoming orders is sufficiently low, such that the additionally required run times do not cause issues. If the expected time between incoming order requests temporarily increases, e.g., during peak times, one can switch to the 1 move heuristic without having to fear major drawbacks.