# Computational Approaches for Grocery Home Delivery Services
## 4 Algorithms for the VRPTW
### Solution Approaches  
In this subsection, we describe how we combine the heuristics and MILPs presented above such that we can conduct the different steps of the ordering phase sufficiently fast.  
First, in the determination step, we aim to quickly identify all time windows \(\mathcal{T}_{j}\subseteq\mathcal{W}\) during which a new customer \(j\) can be inserted into (at least one of) the current tours. We compare to the following approaches.  
* Simple insertion heuristic;
* ANS heuristic;
* A feasibility version of the suggested MILPs for solving the TSP(s)TW, which are applied for each time slot \(u\in\mathcal{W}\) and for each \(\mathcal{A}\in\mathcal{T}_{u}\).  
Once customer \(j\) has selected a time window \(u\in\mathcal{T}_{j}\), in the insertion step we double-check its availability in the same way as in the determination step and then immediately insert \(j\) into \(u\) at the best insertion point found. In contrast to the determination step, we run the simple insertion heuristic or the ANS over all tours and all insertion points and select the feasible insertion point that results in the lowest increase of the total travel time of the schedule. Thus, we do not stop the algorithm once the first feasible insertion point is found. In the case of the TSP(s)TW MILPs we apply their standard formulations for finding an optimal tour after the insertion of \(j\), rather than their corresponding feasibility versions.  
In the improvement step, we aim to reduce the total travel time of the schedule. We compare the following approaches.  
* 1 move + (1 swap). The computationally cheap yet quite effective local search heuristic builds the foundation of the improvement step. We apply 1 move (and 1 swap) operations, where we focus on the 1 move operations if possible, because they are computationally cheaper and, in general, more effective than 1 swap operations. We stop our local search heuristic once we reach a local minimum of the objective function with respect to the selected neighborhood;
* 1 move + 1 swap + TSP(s)TW. After applying the local search heuristic, we additionally run our TSP(s)TW MILP on all tours that have changed since the last improvement step. We use the current tours of our delivery schedule as the initial solution for TSP(s)TW MILP. While 1 move and 1 swap exchange customers between different tours, the TSP(s)TW MILP re-orders them within the tours, which makes it a useful complement to the local search heuristics. In practice, optimizing the single tours of a schedule to optimality has proven to be critical to ensure driver satisfaction as it guarantees that drivers do not encounter any inefficiencies on their routes.  
Above presented improvement procedures are arranged in ascending order with respect to their computational effort.  
During the ordering phase, the proposed local search procedures only perform improving operations. However, the algorithms can be simply altered to a simulated annealing approach [41] by allowing also _non-improving_ operations. However, this is more suitable for the preparation phase, when more time is available for improving the delivery schedule.