# Computational Approaches for Grocery Home Delivery Services
## 4 Algorithms for the VRPTW
### Adaptive Neighborhood Search Heuristic
#### 4.3.3. Loss and Free Time  
For a tour \(\mathcal{A}\) and a new customer \(j\) who has to be inserted into time slot \(u\), we define  
\[\chi_{u}^{-}(j,\mathcal{A}) :=\max\left(e_{f(u)},\ \max_{i\in\Theta(j,\mathcal{A}),\ i\leq f (u)}\bar{e}_{j,i}\right)-B_{u},\] \[\chi_{u}^{+}(j,\mathcal{A}) :=E_{u}-\min\left(\ell_{l(u)},\ \min_{i\in\Theta(j,\mathcal{A}),\ i \geq l(u)}\bar{\ell}_{j,i}\right).\]  
The value \(\chi_{u}^{-}\) corresponds to the amount of time that is \"lost\" at the beginning of time slot \(u\). This can be caused by the service time required for the last customer order before (outside) \(u\) or the travel time needed for going from that customer to the first customer inside \(u\). Similarly, \(\chi_{u}^{+}\) corresponds to the loss of time at the end of time slot \(u\) caused by the time required for traveling to the first customer after (outside) \(u\) or the service time at the last customer inside \(u\).  
Further, we denote \(\chi_{u}(j,\mathcal{A}):=\chi_{u}^{-}(\mathcal{A},j)+\chi_{u}^{+}(j,\mathcal{ A})\) as the _loss time_ of time window \(u\). In case that \([f(u),l(u)]=\emptyset\), the _loss time_ is given by  
\[\chi_{u}(j,\mathcal{A})=\max_{i\in\Theta(j,\mathcal{A})}\big{(}(\bar{e}_{j,i }-s_{u})+(e_{u}-\bar{\ell}_{j,i})\big{)}.\]  
Figure 4 illustrates the values \(\chi_{u}^{-}(j,\mathcal{A})\) and \(\chi_{u}^{+}(j,\mathcal{A})\) for a tour with non-overlapping time windows. Clearly, if \(\chi_{u}(j,\mathcal{A})=0\), then a violation of \(\mathtt{TEAS}(\mathcal{A})\) for \(j\) can only be repaired by removing (exchanging) customers that are inside \(u\).  
Figure 3: The first \(f(u)\) and the last customer \(l(u)\) of time window \(u\) in case of overlapping time windows. We indicate the positions of the insertion points \(\Theta^{-}(j,\mathcal{A})\) and \(\Theta^{+}(j,\mathcal{A})\) (vertical lines).  
Furthermore, we want to quantify the amount of service and travel time that is needed for inserting \(j\) during time window \(u\). For a given tour \(\mathcal{A}\), the _free time_ of time slot \(u\) is defined as  
\[\lambda_{u}(\mathcal{A}):=\underbrace{(E_{u}-B_{u})}_{(I)}- \underbrace{l(u)-1}_{(II)}\big{(}s(i)+t(i,i+1)\big{)},\]  
where \((I)\) is the length of \(u\) and \((II)\) is the amount of service and travel time that must be handled within \(u\). In case that the indices \(f(u)\) and \(l(u)\) are not defined, i.e., \(in(u,\mathcal{A})=\emptyset\), term \((II)\) is set to 0. In Figure 5, we provide an illustration of the free time.  
Considering non-overlapping time windows, the insertion of customer \(j\) after a customer \(i\in\{f(u)-1,\ldots,l(u)\}\) requires an additional amount of (travel and service) time that must be handled within time window \(u\) and can be calculated by \(\lambda_{u}(\mathcal{A})-\lambda_{u}(\mathcal{A}+_{i}j)\). This assumes that all customers between \(f(u)\) and \(l(u)\) can be moved arbitrarily (while maintaining their sequence) within time slot \(u\), i.e., all customers assigned to \(u\) can be seen as one consecutive block, the length of which is given by \((II)\). Hence, the above statement is weakened in the case of overlapping time windows, as some customers inside \(u\) may be restricted by their assigned time windows such that no consecutive block of customers can be formed. Therefore, a larger amount of time than \((II)\) may be required for tour \(\mathcal{A}\) after the insertion of customer \(j\).