## 4 Reduced Variable Neighborhood Search
### Local Search and Shake Procedure  
The local search procedure is the core component of VNS, as shown in lines 4-11 of Algorithm 2. The neighborhood of a solution \(x\) is denoted by \(N_{k}(x)\), \(k=1,\cdots,3\). ```
Input: the initialized solution \(x\), \(k\) neighborhoods \(N_{k}(x)\), \(k=1,\cdots,3\). Output: a solution \(x_{l}\)
1. \(k\gets 1\)
2. \(x^{\prime}\gets N_{k}(x)\)
3. Repeat
4. If\(f(x^{\prime})<f(x)\)then
5. \(x\gets x^{\prime}\)//update the current best solution
6. \(k\gets 1\) //initial neighborhood
7. \(x^{\prime}\gets N_{k}(x)\) //update the current solution
8. Else
9. \(k\gets k+1\) //next neighborhood
10. \(x^{\prime}\gets N_{k}(x)\) //update the current solution
11. End if
12. \(x_{l}\gets x\) //output the best solution
13. Returns \(x_{l}\)
```  
**Algorithm 2** Local Search  
It is commonly observed that the operators used for generating neighborhood solutions exhibit a stochastic nature, and the generated neighborhoods may include infeasible solutions or tend towards suboptimal outcomes due to constraint violations. In order to minimize the generation of infeasible neighboring solutions, particularly those violating time window constraints, we propose Proposition 1 and Proposition 2 for this model. **Proposition 1**. : _Let the time windows of two requests \(i_{1}\) and \(i_{2}\) be \(\left[e_{i_{1}},h_{i_{1}}\right]\) and \(\left[e_{i_{2}},h_{i_{2}}\right]\), respectively, and \(e_{i_{1}}<h_{i_{1}}<e_{i_{2}}<h_{i_{2}}\). If request \(i_{2}\) is served before \(i_{1}\) by the \(k\)th AMR on its \(p\)th route, then we have \(P\left\{X_{p,i_{1}}^{k}>h_{i_{1}}\right\}=1\) and \(P\left\{Y_{p,i_{1}}^{k}>h_{i_{1}}\right\}=1\)._  
**Proof. ** Because request \(i_{2}\) is served before \(i_{1}\) by the \(k\)th AMR on its \(p\)th route, we have \(Y_{p,i_{1}}^{k}\geq X_{p,i_{1}}^{k}>Y_{p,i_{2}}^{k}\). Since \(Y_{p,i_{2}}^{k}=\max\left\{X_{p,i_{2}}^{k},e_{i_{2}}\right\}\geq e_{i_{2}}>h_{ i_{1}}\), it follows that  
\(P\left\{X_{p,i_{1}}^{k}>h_{i_{1}}\right\}=P\left\{X_{p,i_{1}}^{k}>Y_{p,i_{2}}^{ k}>h_{i_{1}}\right\}=1\) and \(P\left\{Y_{p,i_{1}}^{k}>h_{i_{1}}\right\}=P\left\{Y_{p,i_{1}}^{k}>Y_{p,i_{2}}^{ k}>h_{i_{1}}\right\}=1\). \(\square\)  
**Remark 1**. : _From Proposition 1, we find that if the time windows satisfy \(e_{i_{1}}<h_{i_{1}}<e_{i_{2}}<h_{i_{2}}\), serving request \(i_{1}\) first is preferred, otherwise the time window of request \(i_{1}\) is broken definitely._  
**Proposition 2**. : _Let the time windows of two requests \(i_{1}\) and \(i_{2}\) be \(\left[e_{i_{1}},h_{i_{1}}\right]\) and \(\left[e_{i_{2}},h_{i_{2}}\right]\), respectively, and \(h_{1}<h_{2}\). The arrival times of the two requests are \(X_{p,i_{1}}^{k}\) and \(X_{p,i_{2}}^{k}\), which follow the same distribution. Then we have \(P\left\{Y_{p,i_{1}}^{k}>h_{i_{1}}\right\}>P\left\{Y_{p,i_{2}}^{k}>h_{i_{2}}\right\}\)._  
**Proof. ** The probability that request \(i_{1}\) breaks its time window is  
\[P\left\{Y_{p,i_{1}}^{k}>h_{i_{1}}\right\}=P\left\{\max\left(X_{p,i_{1}}^{k},e_ {i_{1}}\right)>h_{i_{1}}\right\}=1-P\left\{X_{p,i_{1}}^{k}\leq h_{i_{1}}\right\} P\left\{e_{i_{1}}\leq h_{i_{1}}\right\}=1-P\left\{X_{p,i_{1}}^{k}\leq h_{i_{1}}\right\}.\]The probability that request \(i_{2}\) breaks its time window is  
\[P\Big{\{}Y_{p,i_{2}}^{k}>h_{i_{2}}\Big{\}}=P\Big{\{}\text{max}\Big{(}X_{p,i_{2}}^ {k},e_{i_{2}}\Big{)}>h_{i_{2}}\Big{\}}=1-P\Big{\{}X_{p,i_{2}}^{k}\leq h_{i_{2}} \Big{\}}P\big{\{}e_{i_{2}}\leq h_{i_{2}}\big{\}}=1-P\Big{\{}X_{p,i_{2}}^{k}\leq h _{i_{2}}\Big{\}}.\]  
Note that \(X_{p,i_{1}}^{k}\) and \(X_{p,i_{2}}^{k}\) follow the same distribution. Let the density of \(X_{p,i_{1}}^{k}\) and \(X_{p,i_{2}}^{k}\) be \(p(x)\), then  
\[P\Big{\{}X_{p,i_{1}}^{k}\leq h_{i_{1}}\Big{\}}=\int_{0}^{h_{i_{1}}}p(x)dx<\int _{0}^{h_{i_{2}}}p(x)dx=P\Big{\{}X_{p,i_{2}}^{k}\leq h_{i_{2}}\Big{\}}.\]  
Therefore, \(P\Big{\{}Y_{p,i_{1}}^{k}>h_{i_{1}}\Big{\}}>P\Big{\{}Y_{p,i_{2}}^{k}>h_{i_{2}} \Big{\}}\). \(\square\)  
**Remark 2**.