## 4 Reduced Variable Neighborhood Search
### Local Search and Shake Procedure
: _From Proposition 2 we find that if the time windows \(\left[e_{i_{1}},h_{i_{1}}\right]\) and \(\left[e_{i_{2}},h_{i_{2}}\right]\) satisfy \(h_{i_{1}}<h_{i_{2}}\), prioritizing the service of request \(i_{1}\) leads to a smaller probability of time window violation._  
To obtain solutions within a limited time, we propose three operators, namely swap*, 2-opt*, and relocation*, based on Proposition 1 and Proposition 2. 1. The swap* operator: Figure 2a illustrates a scenario where Request 5 violates its time window constraints at its current position, while the upper bound of the time window for Request 2 is looser. Consequently, Requests 2 and 5 are chosen for swapping. On the other hand, to avoid getting stuck in local optima when all requests on the current route to satisfy their time window constraints, two requests from the current solution are randomly selected for position swapping, while the remaining requests remain unchanged. Figure 2b displays an example where Requests 3 and 6 are selected, resulting in a new solution generated through the swap operation. 2. The 2-opt* operator: as shown in Figure 3a, a declining trend is observed in the upper bound of time windows for the sub-route between Request 2 and Request 5 in the existing route. Therefore, we reverse the order of this sub-route between Requests 2 and 5 to improve the solution. For cases where there is no sub-route with decreasing time window upper bounds in the current solution, we randomly select two requests from the incumbent solution and reverse the order of points between them before inserting them back into the service route. As shown in Figure 3b, Requests 3 and 6 are randomly selected, and their routes are reversed to create a new feasible solution. Figure 2: Swap* operator: (**a**) position swapping for the requests with violated time windows, (**b**) random selection for position swapping. 5. Charging insertion: if a service route is not feasible due to insufficient electricity, a charging station is inserted before the point whose remaining electricity is lower than the lower bound of battery level \(\alpha\). Let \(\alpha=0\). As shown in Figure 6a, route \(d\)\(\rightarrow\)\(1\)\(\rightarrow\)\(2\)\(\rightarrow\)\(3\)\(\rightarrow\)\(4\)\(\rightarrow\)\(\cdots\) is not feasible due to insufficient electricity, where the number above each circled node represents the remaining battery level of the AMR. The first request with non-positive remaining electricity in the current route is Request 5. The charging station \(c\) is inserted before Request 5, as shown in Figure 5b. The modified feasible route is \(d\)\(\rightarrow\)\(1\)\(\rightarrow\)\(2\)\(\rightarrow\)\(3\)\(\rightarrow\)\(4\)\(\rightarrow\)\(c\)\(\rightarrow\)\(5\)\(\rightarrow\)\(6\)\(\rightarrow\)\(d\). **Proposition 3**. : _If the time windows and the battery level constraints are satisfied, reducing the number of AMRs participating in service by combining the paths of different AMRs can reduce the total cost._  
Proof. : Assume that the requests are served by \(m\) AMRs and the solution is \(x=\left\{\left.x_{pij}^{k}\right|x_{pij}^{k}=0,1\right\}\). The corresponding objective value is \(f(m,x)=\xi_{1}m+\xi_{2}\sum\limits_{k=1}^{m}\sum\limits_{p\in\mathbb{L}_{k}} \sum\limits_{ \begin{array}{c}i\in V_{1}\\ j\in V_{2}\\ i\
eq j\end{array} }d_{ij}x_{pij}^{k}\). If the time windows and the battery level constraints are satisfied, assume that the paths of two AMRs can be completed by a single AMR. The new solution is denoted by \(\widetilde{x}=\left\{\left.\widetilde{x}_{pij}^{k}\right|\widetilde{x}_{pij}^{ k}=0,1\right\}\). We have \(f(m-1,\widetilde{x})=\xi_{1}(m-1)+\xi_{2}\sum\limits_{k=1}^{m-1}\sum\limits_{p \in\mathbb{L}_{k}}\sum\limits_{ \begin{array}{c}i\in V_{1}\\ j\in V_{2}\\ i\
eq j\end{array} }d_{ij}\widetilde{x}_{pij}^{k}\). \(j\in V_{2}\)  
Figure 5: Depot insertion operator: (**a**) infeasible route violating load capacity, (**b**) feasible route after repair.