## 4 The Algorithms
### The DSR-Fle Variant Algorithm
#### 4.2.3 Improvement on the Spl-DSR-Fle Algorithm
Recall that a metric TSP problem is as follows: given a weighted complete graph \(G=(V,W)\), where \(v_{i}\in V\) (\(|V|=n\)) is the vertex and \(w_{ij}\in\mathbb{N}_{+}\) is the non-negative cost associated with the edge \(e_{ij}\) between \(v_{i}\) and \(v_{j}\), the TSP asks if there exists a Hamiltonian path (i.e., a path visiting each vertex exactly once) with a cost equal to \(K\). For any metric TSP instance \(\mathcal{I}=\langle G,K\rangle\), we construct a DSS-Fix instance as follows. For each vertex \(v_{i}\in V\), we create an order \(r_{i}=(v_{i},v^{-},K)\), where \(v_{i}\) indicates the pickup region, \(v^{-}\) is the created auxiliary region indicating the drop-off region of \(r_{i}\), and \(K\) indicates the drop-off period. The weight of the edge \(w_{ij}\) corresponds to the time distance between the pickup regions of \(r_{i}\) and \(r_{j}\). Moreover, for each order \(r_{i}\), the time distance between its pickup region \(v_{i}\) and its fixed drop-off region \(v^{-}\) is zero. In DSS-Fix, there is only one courier with capacity \(n\). The courier stats from the depot region \(v_{0}\) and the time distance between \(v_{0}\) and any other region is zero. This construction can be done in polynomial time. We can conclude that the DSS-Fix can serve \(n\) orders within the period horizon \(K\) iff TSP has a Hamiltonian path with cost \(K\). #### 4.3.2 The Heuristic Algorithm

The main idea behind the heuristic algorithm for DSS-Fix is that we first search these orders that can be shared, then package the shared orders as a virtual order, and finally insert the virtual order into the DSR-Fix CSN. **Order Sharing Search. ** For two orders \(r_{j}\) and \(r_{k}\) whose pickup (resp. drop-off) regions that are proximal, it will be beneficial to pick up (resp. drop off) \(r_{j}\) and \(r_{k}\) consecutively. Imposing a bound of \(c\) implies that at most \(c\) orders can be shared and served by a courier at a time. In the following, we consider the case \(c=2\), i.e., search 2-order sharing where two orders can be served in a sharing manner. **Definition 2**. : 2-order sharing \(\langle r_{j},r_{k}\rangle\). _Given two orders \(r_{j}\) and \(r_{k}\) with fixed time window \(t_{j}\) and \(t_{k}\), and assuming that \(t_{j}\leq t_{k}\) without loss of generality, it is beneficial for serving the two orders in a sharing manner if these two orders satisfy the following two properties: (1) it is not feasible to serve \(r_{j}\) and \(r_{k}\) consecutively, i.e., \(t_{j}+\tau_{jk}>t_{k}\), and (2) it is feasible to execute one of the following two sharing delivery plans \(\langle v_{j}^{p},v_{k}^{p},v_{j}^{d},v_{k}^{d}\rangle\) and \(\langle v_{k}^{p},v_{j}^{p},v_{j}^{d},v_{k}^{d}\rangle\). In particular, property (2) requires that a courier can start from certain period \(t_{s}\) and certain region \(v_{s}\), and one of the following inequations should satisfy:_

\[\left\{ \begin{array}{l}t_{s}+d_{v_{s}v_{j}^{p}}+d_{v_{j}^{p}v_{k}^{p}}+d_{v_ {k}^{p}v_{j}^{d}}\leq t_{j},\\ t_{s}+d_{v_{s}v_{j}^{p}}+d_{v_{j}^{p}v_{k}^{p}}+d_{v_{k}^{p}v_{j}^{d}}+d_{v_{j}^ {d}v_{k}^{d}}\leq t_{k}.\end{array} \right. \tag{6}\]

\[\left\{ \begin{array}{l}t_{s}+d_{v_{s}v_{k}^{p}}+d_{v_{k}^{p}v_{j}^{p}}+d_{v_ {j}^{p}v_{j}^{d}}\leq t_{j},\\ t_{s}+d_{v_{s}v_{k}^{p}}+d_{v_{k}^{p}v_{j}^{p}}+d_{v_{j}^{p}v_{j}^{d}}+d_{v_{j}^ {d}v_{k}^{d}}\leq t_{k}.\end{array} \right. \tag{7}\]

Equation (6) corresponds to the sharing plan \(\langle v_{j}^{p},v_{k}^{p},v_{j}^{d},v_{k}^{d}\rangle\), and Equation (7) corresponds to the sharing plan \(\langle v_{k}^{p},v_{j}^{p},v_{j}^{d},v_{k}^{d}\rangle\). The motivation of the property (1) is shown as follows. In DSS-Fix, for two orders \(r_{j}\) and \(r_{k}\) that can be served consecutively, it does not take any advantage of sharing them by picking them up (resp. dropping off) consecutively. This is because, with the fixed drop-off period \(t_{j}\) and \(t_{k}\), the sharing plan cannot finish \(r_{j}\) and \(r_{k}\) earlier, but might need the earlier pick up period.