## 4 The Algorithms
### The DSR-Fle Variant Algorithm
#### 4.2.3 Improvement on the Spl-DSR-Fle Algorithm
Existing public delivery datasets such as the New York City taxi-trip dataset ([[https://www1.nyc.gov/site/tlc/about/tlc-trip-record-data.page](https://www1.nyc.gov/site/tlc/about/tlc-trip-record-data.page)]([https://www1.nyc.gov/site/tlc/about/tlc-trip-record-data.page](https://www1.nyc.gov/site/tlc/about/tlc-trip-record-data.page))) only includes the order's pick-up region, drop-off region, and request time, and does not include the flexible drop-off time windows. Thus, we use the synthetic data to validate the proposed algorithms. **Comparison Metrics. ** We mainly compare the running time and the order service rate (**OSR**) of the algorithms. The OSR is computed as follows: we compare the number of orders served with the total number of orders \(|R|\), e.g., the OSR of the algorithm \(Alg\) is computed as \(\frac{NoS(Alg)}{|R|}\), where \(NoS(Alg)\) is the number of orders served by the algorithm \(Alg\). ### Validate the Ite-DSR-Fle Variant Algorithm

In this section, we mainly focus on the DSR variant without considering order sharing and validate the efficiency of the proposed Ite-DSR-Fle approximation algorithm. **Experimental Setup. ** Each period consists of 5 min and the horizon \(T=36\), which might represent the food-delivery peak-hour at noon ranging from 10:30 a.m. to 1:30 p.m. The city network consists of 100 regions; each region has four neighbors, connected by a small-world network [28]. The traveling period between adjacent neighbors follows \(U(1,4)\), where \(U(a,b)\) indicates the uniform distribution between \(a\) and \(b\). The time distance between two regions can be computed by the shortest path. There are 200 couriers starting routing with uniformly distributed initial regions. Customer orders are randomly generated as a Poisson process \(P(\lambda)\) with a fixed arrival rate \(\lambda\). The origin and destination of each order is uniformly drawn across the regions. By setting the arrival rate of the Poisson process so that the expectation of the total number of orders is 200, 500, 1000, respectively, these three levels of customer order demand correspond to the low, medium, and high demands. We give all customers a constant time window around their preferred drop-off period (that follows \(U(1,T)\)), from one to five periods. **Comparison Methods. ** We compare the proposed approximation **Ite-DSR-Fle** with the following two benchmarks. * The integer-programming-based optimal solution (IPopt): We use the CPLEX (version 12.6) to solve this IPopt (i.e., Equations (1)-(5)) to return the optimal solution. * 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. **Experiment Results. ** Table 2 shows the OSR and running time of these algorithms with varying order demands and window lengths. From Table 2, we can observe that (1) the proposed Ite-DSR-Fle can perform close to the optimal IPopt with respect to maximizing OSR. For example, in the worst scenario with high order demand and the five periods flexible time window, Ite-DSR-Fle finishes \(\sim\)5% less OSRs than that of the optimal IPopt. This result is consistent with the theoretical approximation of the Ite-DSR-Fle algorithm. (2) Ite-DSR-Fle achieves nearly \(\sim\)6% more OSRs than that of the greedy heuristic in average. The potential reason is that the orders' drop-off periods should be coordinated rather than chosen by their latest period independently. Considering that there are thousands of customer orders, such an improvement is desirable. (3) Since IPopt needs to solve the IP Equations (1)-(5), the running time prevents it from scaling to large instances. For example, in the scenario with high demand, it will take a couple of minutes (e.g., 80.4 s) to return the routing plan. However, the Ite-DSR-Fle can generate the routing plan within about 1.4 s. (4) The more flexible time windows, the more OSR will be achieved by the Ite-DSR-Fle.