## 4 The Algorithms
### The DSR-Fle Variant Algorithm
#### 4.2.3 Improvement on the Spl-DSR-Fle Algorithm
1 Initialize \(g=0\) and \(R^{{}^{\prime}}_{g}=\emptyset\);
2 Search the set of 2-order sharing orders \(\tilde{R}^{s}\);
3 Construct the CSN \(G^{s}_{g}=(R\cup\tilde{R}^{s},E)\);
4 repeat
5\(g=g+1\);
6 Invoke the Algorithm 2 to return the set of orders \(R^{{}^{\prime}}_{g}\) served on \(G^{s}_{g-1}\);
7 Update the CSN \(G^{s}_{g}\) using the CSN update rule;
8 until\(|R^{{}^{\prime}}_{g-1}|=|R^{{}^{\prime}}_{g}|\);
9 Return \(R^{{}^{\prime}}_{g}\). ```
**Algorithm 5**Iterative Algorithm for DSS-Fix (Ite-DSS-Fix). **Lemma 2**. : _Algorithm 5 can always converge within finite iterations._

The proof is similar to that in Lemma 1 and is omitted here for space limitation. **Lemma 3**. : _Given the set of customer orders \(R\), the number of orders served by the DSS-Fix algorithm (i.e., Algorithm 5) is not less than that served by the DSR-Fix algorithm (i.e., Algorithm 1)._

Proof. : In DSS-Fix, the CSN \(G^{s}=(R\cup\tilde{R}^{s},E)\) not only includes the real orders \(R\), but also includes the virtual shared orders \(\tilde{R}^{s}\). Therefore, the number of orders served in the DSR-Fix variant CSN \(G=(R,E)\) must not be larger than that in the DSS-Fix variant CSN \(G^{s}=(R\cup\tilde{R}^{s},E)\). Moreover, the CSN update rule always deletes the real order \(r_{j}\) that has been served in the virtual shared orders \(r^{s}_{jk}\) (resp. \(r^{s}_{kj}\)), which will not reduce the number of orders served in \(G=(R,E)\). In other words, for each served order \(r_{j}\) in \(G=(R,E)\) that is not served in \(G^{s}=(R\cup\tilde{R}^{s},E)\), there must be another one real order \(r_{k}\) or virtual orders \(r^{s}_{jk}\) (resp. \(r^{s}_{kj}\)) replacing \(r_{j}\) in \(G^{s}=(R\cup\tilde{R}^{s},E)\). Therefore, we have this conclusion. Lemma 3 theoretically guarantees the advantage of delivery _sharing_ plan over delivery _routing_ plan. ### The DSS-Fle Variant Algorithm

On one hand, the DSS-Fle problem, where the order has flexible drop-off time windows, is a general variant of the DSS-Fix problem. On the other hand, the DSS-Fle problem, where orders can be served in a sharing manner, is also a general variant of the DSR-Fle problem. To solve such an NP-hard DSS-Fle problem, we can combine the DSR-Fle variant algorithm (i.e., Algorithm 4) and the DSS-Fix variant algorithm (i.e., Algorithm 5). The main idea of the DSS-Fle variant algorithm is that we first employ Ite-DSR-Fle algorithm (i.e., Algorithm 4) to return \"fixed\" orders whose drop-off periods are determined and fixed. Given the \"fixed\" orders, we then employ the Ite-DSS-Fix algorithm (i.e., Algorithm 5) to search the order-sharing and generate the sharing delivery plan. The details of the DSS-Fle algorithm are shown in Algorithm 6. In Step 2, the Ite-DSR-Fle algorithm is employed to determine the fixed drop-off period of each order (For the order whose drop-off period cannot determined, a greedy heuristic of choosing its latest drop-off period is employed). Let \(R^{fix}\) denote the set of \"fix\" orders. In Step 3, the Ite-DSS-Fix algorithm is employed to optimize the set of fixed orders \(R^{fix}\). ```
Input :Customer orders \(R\). Output :Served orders \(R^{\prime}\subseteq R\). 1 Initialize \(R^{fix}=\emptyset\);
2 Invoke the Ite-DSR-Fle algorithm (i.e., Algorithm 4) to generate \"fixed\" orders \(R^{fix}\) with fixed drop-off periods;
3 Invoke the Ite-DSS-Fix(\(R^{fix}\)) algorithm (i.e, Algorithm 5) to return the served orders \(R^{\prime}\);
4 Return \(R^{\prime}\). ```

**Algorithm 6**The DSS-Fle Variant Algorithm (**DSS-Fle**). **Lemma 4**: _Algorithm 6 can always converge within finite iterations._

This proof can be derived from the convergence results of Algorithms 4 and 5. ## 5 Experimental Evaluation

We generate synthetic datasets to validate the performance of proposed algorithms. All computations are performed on a 64-bit PC with 16 GB RAM and a Dual core 3.5 GHz processor. All records are averaged over 40 instances, and each record is statistically significant at a 95% confidence level.