# Computational Approaches for Grocery Home Delivery Services
## 5 Computational Study and Analysis
### Comparing Approaches for the Determination Step  
In this subsection, we evaluate the performance of different approaches for the time window determination step, i.e., we compare the simple insertion heuristic, the ANS heuristic, and the TSP(s)TW insertion approach in terms of run time and solution quality. To allow a proper comparison of the methods for solving the SOP, we constructed instances which consist of (a) a feasible schedule that contains \(p\) customers, and (b) a new customer order for which the availability of delivery time slots must be decided. Tocreate SOP instances for benchmarking, we had to create feasible delivery schedules that are already filled with orders. Hence, we created delivery schedules by iteratively trying to insert 2000 customers into each schedule. The simple insertion heuristic was used to conduct the feasibility checks. The number of customers that are contained in the resulting schedule is denoted by \(\hat{p}\). We consider \(\hat{p}\) as being a sufficiently good approximation of the maximal number that can be inserted into a schedule considering a given configuration. Hence, we distinguish two scenarios: (i) in the first scenario, we perform no optimization between the insertion steps, and (ii) in the second scenario, the schedule is re-optimized by applying improve after each customer insertion. This reduces the total travel time of the schedule. We restrict the improvement step to the most simple approach to avoid unwanted bias when evaluating the performance of the different approaches for the determination step. In general, the schedules in the second scenario contain more orders while utilizing the same number of vehicles. Since the practical hardness of the SOP increases as the schedules are filled up with customers, we consider SOP instances with different fill levels. The _fill level_\(f\) of a schedule is defined as the ratio between the number of customers \(p\) in the schedule and the maximal number of customers \(\hat{p}\) that can be inserted into the schedule. For benchmarking at a given fill level \(f\), we select the schedule that was generated by above described process, which contained \(p=\lceil f\cdot\hat{p}\rceil\) orders. For each generated instance, we solve the SOP using the simple insertion heuristic, the TSP(s)TW insertion n approach, and the proposed ANS heuristic. In order to investigate the differences between the considered methods, we analyze their performance on all three sets of time windows (\(\mathcal{W}_{\text{NO}}\), \(\mathcal{W}_{\text{OV1,5}}\), \(\mathcal{W}_{\text{OV3}}\)), instance sizes, and fill levels. Hence, we run tests on benchmark instances with 60 tours (vehicles) and consider fill levels of 85%, 90%, 95%, and 99%. We report the number of feasible time slots found by each method and required run times (mm:ss.zzz) for all scenarios, i.e., optimized and non-optimized schedules. We report the results for \(\mathcal{W}_{\text{NO}}\) in Table 1, for \(\mathcal{W}_{\text{OV1,5}}\) in Table 2, and for \(\mathcal{W}_{\text{OV3}}\) in Table 3. Moreover, we report the number of feasible time slots that are found by combining the findings of all three methods, denoted as \"combined\" in the tables. Additionally, we report \(\hat{p}\), the number of customers at a 100% fill level. All reported numbers are average values over 100 instances each.