## 4 The Algorithms
### The DSR-Fle Variant Algorithm
#### 4.2.3 Improvement on the Spl-DSR-Fle Algorithm  
We extend Algorithm 3 and propose an iterative algorithm to further improve system throughput. At each iteration \(g\), let \(R_{g}^{fix}\) denote \"fixed\" orders, i.e., the set of orders whose drop-off period is determined and fixed, and \(R_{g}^{fle}\) denote the \"flexible\" orders, i.e., the set of orders whose drop-off period is flexible within windows \([t_{j}^{e},\ t_{j}^{l}]\). For each flexible order \(r_{j}\in R_{g}^{fle}\), we split its flexible time windows 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\kappa_{j}}\}\), and each \(\tilde{r}_{jh}\) has the fixed drop-off period \(t_{j}^{e}+h-1\), \(1\leq h\leq\kappa_{j}\). At each iteration \(g\), let \(\tilde{R}_{g}^{fle}\) denote the virtual orders split from \(R_{g}^{fle}\) and \(\tilde{R}_{g}=R_{g}^{fix}\bigcup\tilde{R}_{g}^{fle}\) denote all of the orders. Given \(\tilde{R}_{g}\), we construct the corresponding CSN \(G(\tilde{R}_{g},E)\) and invoke Algorithm 3 to return the fixed orders \(R_{g}^{fix}\) that are served at the current iteration \(g\). The details of the iterative DSR-Fle are proposed in Algorithm 4. In Step 3, the set of orders \(\tilde{R}_{g}\) is constructed, which includes the set of fixed orders \(R_{g}^{fix}\) whose drop-off period is fixed, and the set of virtual orders \(\tilde{R}_{g}^{fle}\) split from \(R_{g}^{fle}\). In Step 4, the CSN \(G=(\tilde{R}_{g},E)\) is constructed with respect to \(\tilde{R}_{g}\). In Step 5, Algorithm 3 is invoked to return the fixed orders served, \(R_{g}^{fix}\). In Step 6, the set of flexible orders \(R_{g}^{fle}\) is updated by removing the fixed orders \(R_{g}^{fix}\  
+++ ==WARNING: Truncated because of repetitions==
) whose drop-off period has been determined. The iteration terminates until there is no improvement over previous iteration \(g-1\) on the number of orders served. ```


++
```
Input :Customer orders \(R\). Output :Served orders \(R^{\prime}\subseteq R\). 1\(g=0\), \(R_{g}^{fix}=\emptyset\), and \(R_{g}^{fe}=R\setminus R_{g}^{fix}\);
2 repeat
3\(g\)=\(g\)+1;
4 Construct orders \(\tilde{R}_{g}=R_{g-1}^{fix}\bigcup\tilde{R}_{g-1}^{fe}\);
5 Construct the CSN \(G=(\tilde{R}_{g},E)\);
6 Invoke Algorithm 3 to return the \"fixed\" orders \(R_{g}^{fix}\);
7\(R_{g}^{fe}=R\setminus R_{g}^{fix}\);
8 until\(|R_{g-1}^{fix}|=|R_{g}^{fix}|\);
9 Return \(R^{\prime}=R_{g}^{fix}\). ```
**Algorithm 4**Iterative Improvement over Spl-DSR-Fle (**Ite-DSR-Fle**). ### The DSS-Fix Variant Algorithm

In this section, we formulate the DSS-Fix problem, prove the DSS-Fix problem is NP-hard, and propose an efficient heuristic algorithm for DSS-Fix. #### 4.3.1 Problem Formulation and Complexity Analysis

In DSS-Fix, each order \(r_{j}\) has the fixed drop-off time window \(t_{j}\), but multiple orders can be shared and served by a courier at a time. For example, orders \(r_{j}\) and \(r_{k}\) with proximal pickup regions can be picked up consecutively by a courier, and the sharing delivery plan can be \(v_{j}^{p}\to v_{k}^{p}\to v_{j}^{d}\to v_{k}^{p}\). We say such a sharing plan is feasible if and only if (1) at any region, the number of orders in service is smaller than the courier capacity \(c\), and (2) the courier can drop-off the order \(r_{j}\) (resp. \(r_{k}\)) at \(v_{j}^{d}\) (resp. \(v_{k}^{d}\)) no later than \(t_{j}\) (resp. \(t_{k}\)), but can before \(t_{j}\) (resp. \(t_{k}\)) while waiting until \(t_{j}\) (resp. \(t_{k}\)). The DSS-Fix problem is to find the optimal \(n\) sharing delivery plans to maximize the order service rate. Theorem 3.2: _The DSS-Fix problem is NP-hard._

Proof: We show a reduction from the metric Traveling Salesman Problem (**TSP**), which is known to be NP-hard.