# Computational Approaches for Grocery Home Delivery Services
## 5 Computational Study and Analysis
### Design of the Instances  
The benchmark instances are derived from those originally proposed by reference [13]. They are designed to reproduce the characteristics of an online grocery shopping service offered by an international grocery retailer.  
Each instance corresponds to one delivery region that is served by one depot, which has its assigned fleet of vehicles. All instances are based on a 20 km \(\times\) 20 km square grid. A total of 80% of the customer locations have been randomly assigned to 15 clusters. The center (location) of each cluster \(\mu=(\mu_{x},\mu_{y})\) is sampled from a two-dimensional uniform distribution. The shape of each cluster is defined by the covariance matrix \(\Sigma=\begin{pmatrix}\sigma_{x}{}^{2}&0\\ 0&\sigma_{y}{}^{2}\end{pmatrix}\), where \(\sigma_{x}{}^{2}\) and \(\sigma_{y}{}^{2}\) both follow a uniform distribution. Furthermore, the clusters have been rotated by a random angle between 0 and 2\(\pi\). Customer locations have been sampled from the multivariate normal distribution \(N(\mu,\Sigma)\) of the assigned cluster and all coordinates have been rounded to integers. The remaining 20% of the locations are sampled from a two-dimensional uniform distribution. The numbering of the customers is randomly permuted.  
We consider two different placements of the depot: (a) at the center of the grid; (b) at the center of the top-left quadrant. In each test set-up, there are equally many instances for both variants. Each vehicle has a loading capacity of 200 units. The order weights of customers have been sampled from a truncated normal distribution with a mean of 7 and standard deviation of 2, where the lower bound is 1 and the upper bound is 15. The service time of each customer is 5 min. All tours have the same start and end times while vehicle operation times are set such that they do not overly restrict the problem.  
We apply a very simple customer choice model to simulate the customer's choice if they place an order or not after being presented the selection of time windows. Similar to [PERSON] and [PERSON] [28], every customer has just one desired delivery time window (defined in the benchmark instance). The customer refuses to place an order if this preferred time window is not offered. Furthermore, we assume that all delivery time windows are equally prominent among customers (randomly selected from \(\mathcal{W}\)) to obtain unbiased results that allow for an easier identification and clearer interpretation of the key findings.  
We define three sets of delivery time windows \(\mathcal{W}\): (a) \(\mathcal{W}_{\text{NO}}\): 10 non-overlapping time windows with a length of 1 h each, e.g., 08:00-09:00, 09:00-10:00, etc. (b) \(\mathcal{W}_{\text{OV1.5}}\): 10 overlapping time windows with a length of 1.5 h each (except for the last time window, which has a 1 h length), where each window overlaps the preceding time window by 30 min, e.g., 08:00-09:30, 09:00-10:30, etc. (c) \(\mathcal{W}_{\text{OV3}}\): 12 overlapping time windows, consisting of nine windows with a length of 1 h each, 08:00-09:00, 10:00-11:00,..., 16:00-17:00 and (as used by [PERSON] et al. [21]) three time windows of 3 h length, morning: 08:00-11:00, noon: 11:00-14:00, afternoon: 14:00-17:00.  
In summary, our assumptions were chosen to find a good compromise between realistic instances and enabling a concise description and interpretation of the experimental set-up. All experiments were performed on an Ubuntu 14.04 machine powered by an Intel Xeon E5-2630V3 @ 2.4 GHz 8 core processor and 132 GB RAM. We implemented all algorithms in Java Version 8 and used Gurobi 8.1.0 as the MILP solver in single-thread mode. Parallelization of the applied methods is not considered. We run each experimental configuration on 100 instances and report average values. Note that the absence of overlapping time windows allows for the use of a more efficient MILP formulation of the TSPTW for \(\mathcal{W}_{\text{NO}}\) than for \(\mathcal{W}_{\text{OV1.5}}\) and \(\mathcal{W}_{\text{OV3}}\) (see Section 4.4).