## 4 The Algorithms
### The DSR-Fle Variant Algorithm
#### 4.2.2 The Approximation Algorithm  
The main idea behind the approximation algorithm is that, for the order \(r_{j}\), we split its flexible windows \([t_{j}^{e},\ t_{j}^{l}]\) into \(\kappa_{j}=t_{j}^{l}-t_{j}^{e}+1\) virtual orders \(\tilde{r}_{j}=\{\tilde{r}_{j1},\tilde{r}_{j2},\cdots,\tilde{r}_{j_{k}}\}\), each virtual order \(\tilde{r}_{jh}\) has the fixed drop-off window \(t_{j}^{e}+h-1\), \(1\leq h\leq\kappa_{j}\). For DSR-Fix with the set of virtual orders \(\tilde{R}=\{\tilde{r}_{1},\tilde{r}_{2},\cdots,\tilde{r}_{m}\}\), we can adopt Algorithm 1 to optimize the order service. Let \(\tilde{R}^{\prime}\subseteq\tilde{R}\) denote the set of virtual orders served by Algorithm 1. For these virtual orders \(\{\tilde{r}_{j1}^{{}^{\prime}},\tilde{r}_{j2}^{{}^{\prime}},\cdots,\tilde{r}_ {j_{k}^{{}^{\prime}}}\}\) that are served in \(\tilde{R}^{{}^{\prime}}\) and belong to the same real order \(r_{j}\), randomly choosing one virtual order \(\tilde{r}_{jh}^{{}^{\prime}}\) (\(1\leq h\leq\kappa_{j}\)) as the real order \(r_{j}\)'s drop-off period, i.e., \(t_{j}^{e}+h-1\). The details of the approximation algorithm are presented in Algorithm 3. In Steps 2-3, each real order \(r_{j}\in R\) is split into \(\kappa_{j}\) virtual orders, and the set of virtual orders is denoted by \(\tilde{R}\). In Step 4, Algorithm 1 is utilized to return the served orders \(\tilde{R}^{\prime}\in\tilde{R}\). Finally, in Steps 5-6, one of these virtual orders \(\tilde{r}_{j}^{h}\) that belongs to the same real order \(r_{j}\) is chosen such that \(r_{j}\) is finished at the drop-off period \(t_{jh}=t_{j}^{e}+h-1\). ```
Input :Customer Orders \(R\). Output :Served orders \(R^{\prime}\subseteq R\). 1\(R^{\prime}=\emptyset\);
2 for\(r_{j}\in R\)do
3 Split \(r_{j}\) into \(\kappa_{j}=t_{j}^{l}-t_{j}^{e}+1\) virtual orders \(\tilde{r}_{j}=\{\tilde{r}_{j1},\tilde{r}_{j2},\cdots,\tilde{r}_{j_{k}j}\}\);
4 Invoke Algorithm 1 to return the served orders \(\tilde{R}^{\prime}\)=CSN-DSR-Fix(\(\tilde{R}\));
5 for\(r_{j}\in R:\exists\tilde{r}_{jh}^{{}^{\prime}}\in\tilde{R}^{{}^{\prime}}\)do
6\(R^{\prime}=R^{\prime}\cup r_{j}\) and the drop-off period of \(r_{j}\) is \(t_{j}^{e}+h-1\);
```  
**Algorithm 3**Splitting-Based Approximation Algorithm for DSR-Fle (**Spl-DSR-Fle**). **Theorem 2**. : _Let \(\kappa=\max_{r_{j}\in R}\kappa_{j}\) denote the maximum window length of orders \(R\), then the number of orders achieved from the Algorithm 3 at least \(\frac{1}{\kappa}\) of the optimal value returned by Equations (1)-(5)._  
Proof. : Let \(Opt\) denote the optimal number of orders served in DSR-Fle, \(Opt_{spl}\) denote the optimal number of orders served in the \"split\" DSR-Fle variant, where each order \(r_{j}\) is split into \(\kappa_{j}\) virtual orders, and \(Alg_{spl}\) denotes the number of orders served by Algorithm 3. When no ambiguity is possible, we let \(Opt,Opt_{spl}\) and \(Alg_{spl}\) denote the number of orders served as well the order delivery plan. In the following, we will prove that \(Opt\leq Opt_{spl}\) and \(Alg_{spl}\geq\frac{Opt_{spl}}{\kappa}\), respectively. \(Opt\leq Opt_{spl}\). Let \(Opt=\{Opt^{1},Opt^{2},\cdots,Opt^{n}\}\), where \(Opt^{i}\) denotes the order delivery plan of the courier \(a_{i}\). It should be noted that \(Opt\) is also a feasible delivery plan in the \"split\" DSR-Fle variant. On the other hand, virtual orders served in \(Opt_{spl}\) might belong to the same real orders, and a feasible deliveryplan of \(Opt_{spl}\) does not necessarily correspond to a feasible delivery plan of \(Opt\). Therefore, we have \(Opt\leq Opt_{spl}\). \(Alg_{spl}\geq\frac{Opt_{spl}}{\kappa}\). Let \(Opt_{spl}=\{Opt_{spl}^{1},Opt_{spl}^{2},\cdots,Opt_{spl}^{n}\}\), where \(Opt_{spl}^{i}\) denotes the order delivery plan as well as the orders served by \(a_{i}\) in the \"split\" DSR-Fle.