# Computational Approaches for Grocery Home Delivery Services
## 5 Computational Study and Analysis
### Comparing Approaches for the Improvement Step
#### 5.3.2 Dealing with Large-Problem Instances  
Large supermarket chains offer their services across the whole country. Caused by the different geographies, the sizes of the delivery regions that are covered by a depot strongly vary ranging from a few hundred up to around 2000 customers per day. Dealing with such large delivery regions is especially challenging during periods where many customer requests arrive within a short time frame. To accommodate these periods of high request frequency, we propose to run the improvement step only after each \(i\)th successful insertion step, instead of after each. We want to validate this idea by running computational experiments. We consider instances with 2000 customers (the largest number we encountered in practice) and 80 vehi \begin{table}
\begin{tabular}{l r r r r r r r r r} \hline \hline  & \multicolumn{6}{c}{**Average-Sized Grocery Home Delivery Problems**} \\ \hline  & \multicolumn{3}{c}{\(\mathcal{W}_{\text{NO}}\)} & \multicolumn{3}{c}{\(\mathcal{W}_{\text{OV1.5}}\)} & \multicolumn{3}{c}{\(\mathcal{W}_{\text{OV2}}\)} \\ \hline Vehicles & 16 & 18 & 20 & 16 & 18 & 20 & 16 & 18 & 20 \\ \hline Avg. \(\beta\) & 450.80 & 491.60 & 498.00 & 459.60 & 495.80 & 499.20 & 453.00 & 496.60 & 499.00 \\ Avg. number of & & & & & & & & & \\ time windows offered & 9.01 & 9.84 & 9.97 & 9.21 & 9.93 & 9.98 & 10.83 & 11.92 & 12.00 \\ \hline Avg. run time & & & & & & & & & \\ time & 00.0015 & 00.0099 & 00.00108 & 000.0097 & 000.00124 & 00.00134 & 00.0000 & 000.00111 & 000.1106 \\ 1 move+iswap & 00.00262 & 000.776 & 000.0056 & 000.00592 & 000.11030 & 000.001145 & 000.00295 & 001.106 & 0001.106 \\ 1 move+iswap+T(s)TW(s)TW & 00.00678 & 00.00383 & 000.0021 & 000.4881 & 000.7357 & 003.6455 & 001.314 & 0001.478 & 0001.485 \\ \hline Avg. improvement & & & & & & & & & \\ time & 0.30 & 0.29 & 0.29 & 0.37 & 0.37 & 0.37 & 0.34 & 0.34 & 0.34 \\ 1 move+iswap & 0.41 & 0.40 & 0.39 & 0.52 & 0.50 & 0.50 & 0.50 & 0.50 & 0.48 \\ 1 move+iswap+T(s)TW & 0.45 & 0.43 & 0.42 & 0.60 & 0.57 & 0.56 & 0.55 & 0.54 & 0.53 \\ \hline Avg. improvement & & & & & & & & & \\ of out of Insertion (\%) & 35.82 & 380.00 & 38.76 & 38.36 & 40.75 & 41.66 & 37.11 & 39.39 & 39.58 \\ 1 move+iswap & 49.88 & 51.34 & 51.44 & 53.62 & 55.37 & 55.64 & 54.65 & 57.42 & 57.23 \\ 1 move+iswap+T(s)TW & 33.83 & 53.34 & 55.26 & 61.80 & 63.33 & 63.48 & 95.53 & 62.37 & 61.90 \\ \hline Avg. number of & & & & & & & & & \\ MIPS solved & & & & & & & & & & \\ move+iswap+T(s)TW & 2.01 & 2.09 & 2.11 & 2.36 & 2.49 & 2.48 & 2.32 & 2.42 & 2.42 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Summary of the computational experiments for the improvement approaches considering instances with 500 customers. cles for these experiments and report the results in Table 5. Each column shows results for different values of \(i\). For these experiments we can only report the average improvement of the schedule when applying the respective improvement strategy. First, we notice that the run time of the improvement step increases with \(i\): the more often we skip an improvement step, the longer it takes to improve the schedule's total travel time. Moreover, we observe an increased improvement per step with increasing \(i\). Apparently, the improvement that was omitted can be made up (up to a certain extent), by applying the improvement step at a later point in time. It shows that performing the improvement step only after every \(i\)th successful insertion is a viable option. While 1 move stays below 6 s for \(i=10\), its run time increases up to 13 s for \(i=30\). The run times of 1 move + 1 swap are between 1 min and 2 min (overlapping time windows), which is still acceptable. We observe that solving the TSP(s)TW MILP does increase the run times (on top of the local search heuristics) insignificantly while still showing some additional improvements of the objective. In general, the observations from the previous experiments with 500 customers carry over to this experiment.