## 4 The Algorithms
### The DSR-Fle Variant Algorithm
#### 4.2.3 Improvement on the Spl-DSR-Fle Algorithm

Table 2: OSR and running time on small-scale instances. To make the table clear, we omit the statistical errors, and each cell is statistically significant at a 95% confidence level. #### 5.2.2 Validate the Advantage over Existing Heuristics

**Comparison Methods and Metrics. ** We compare the proposed **DSS-Fle** with the following two existing heuristics:

* Greedy: Each customer order \(r_{j}\) is assigned with its latest drop-off period \(t_{j}^{*}=t_{j}^{l}\) as its fixed drop-off period, based on which the CSN-DSR-Fix (i.e., Algorithm 1) is employed to return the solution. * Insertion-based Heuristics (**Insert-Heu**): The Greedy algorithm is first employed to derive a solution of \(n\) delivery sharing plans \(\mathcal{P}=\{P_{1},P_{2},\cdots,P_{n}\}\). For any order \(r_{j}\in R\) that is not served in \(\mathcal{P}\), a re-optimization of inserting \(r_{j}\) into a sharing plan \(P_{i}\in\mathcal{P}\) is elaborated. Given the delivery plan \(P_{i}=\langle v_{1}^{p},v_{1}^{d},v_{h}^{p},v_{h}^{d}\rangle\) of a temporally-ordered route of pickup and drop-off regions of \(h\) orders, the insertion heuristic attempts to insert \(r_{j}\) pick-up region \(v_{j}^{p}\) and drop-off region \(v_{j}^{p}\) into these \(2h\) regions. A feasible insertion of \(r_{j}\) into \(P_{i}\) must satisfy (1) without violating the order service in the rest of the plan \(P_{i}\), and (2) the number of on-board orders is smaller than the courier's capacity \(c\) (\(c=2\) in this experiment). There are \(O(l^{2})\) possible ways of insertion for each order and each plan, where \(l\) is the number of orders. Given these \(n\) delivery plans and \(l\) orders in total, there are \(O(nl^{3})\) insertion computations. **Experimental Results. ** Figure 3 shows the OSRs of these algorithms with varying customer order demands. From Figure 3, we can observe that DSS-Fle can always serve the most orders, which is followed by Insert-Heu and Greedy. This result can validate (1) the advantage of flexible drop-off time selection mechanism (i.e., Algorithm 3) over a fixed drop-off time selection mechanism (i.e., Insert-Heu and Greedy), and (2) the advantage of insertion mechanism (i.e., Insert-Heu) over the one-short Greedy solution on improving OSR. Moreover, inspired by the advantage of Insert-Heu, it is interesting for the future work to combine the proposed DSR-Fle with the insertion mechanism for the online delivery services' applications. In summary, the proposed DSS-Fle can maximize system throughput in the tolerable time in the city-scale order delivery applications with thousands of couriers and customers. Moreover, the more computation time available, the larger system throughput that will be achieved. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \multirow{2}{*}{**Demand**} & \multicolumn{4}{c}{**Order Service Rate (OSR)**} & \multicolumn{4}{c}{**Runtime (Second)**} \\ \cline{2-9}  & **DSS-Fle** & **Ite-DSS-Fix** & **Ite-DSR-Fle** & **DSR-Fix** & **DSS-Fle** & **Ite-DSS-Fix** & **Ite-DSR-Fle** & **DSR-Fix** \\ \hline
2000 & **0.572** & 0.554 & 0.563 & 0.544 & 3.20 & 0.38 & 3.02 & 0.36 \\
4000 & **0.326** & 0.307 & 0.313 & 0.302 & 18.4 & 1.83 & 16.2 & 1.33 \\
6000 & **0.239** & 0.222 & 0.227 & 0.219 & 44.6 & 4.01 & 43.9 & 3.67 \\
8000 & **0.196** & 0.184 & 0.189 & 0.180 & 95.4 & 9.48 & 75.1 & 6.78 \\
10,000 & **0.172** & 0.159 & 0.163 & 0.155 & 134.6 & 19.73 & 124.5 & 12.9 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Order Service Rate (OSR) and running time on large-scale instances. To make the table clear, we omit the statistical errors, and each cell is statistically significant at a 95% confidence level. ## 6 Conclusions

This paper studies the practical DSS-Fle problem, where customer orders have flexible drop-off time windows and can be served in a sharing manner. To address such a NP-hard problem, we first study the special DSR-Fix variant, which can be addressed by the CSN and Hopcroft-Karp maximum matching algorithm.