## 4 The Algorithms
### The DSR-Fle Variant Algorithm
#### 4.2.3 Improvement on the Spl-DSR-Fle Algorithm
By extending the DSR-Fix variant algorithm, we further propose an approximation algorithm (i.e., Ite-DSR-Fle) for the DSR-Fle problem and a heuristic algorithm (i.e., Ite-DSS-Fix) for the DSS-Fix problem. The Ite-DSR-Fle algorithm splits the flexible time windows into multiple fixed time windows, and the DSR-Fix variant algorithm can then be employed to serve orders at the desirable drop-off period. The Ite-DSS-Fix algorithm searches and inserts the sharing orders, and the DSR-Fix variant algorithm then can be employed to generate the desirable sharing plan. Finally, using Ite-DSR-Fle to generate the \"fixed\" orders and using Ite-DSS-Fix to search order sharing together yield the polynomial time DSS-Fle algorithm for order service rate optimization. Simulation results show that the proposed DSS-Fle algorithm is efficient both on improving order service rate and applying to city-scale scenarios with thousands of regions and customer orders. [PERSON] proposed the problem; [PERSON] and [PERSON] designed the algorithms and performed the simulation; [PERSON] and [PERSON] contributed in analyzing the performance and writing this paper. All authors have read and agreed to the published version of the manuscript. This research is supported by the National Key Research and Development Project of China (2019 YFB1405000), the National Natural Science Foundation of China (61932007, 61806053 and 61807008), the Natural Science Foundation of Jiangsu Province of China (BK20171363, BK20180356, and BK20180369), and the \"Zhishan Young Scholar\" Program of Southeast University. The authors declare no conflict of interest. Figure 3: Order service rates of algorithms. ## References

* [PERSON] (1987) [PERSON] Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. _Oper. Res._**1987**, _35_, 254-265. [CrossRef]
* [PERSON] and [PERSON] (2007) [PERSON]; [PERSON] Waiting and Relocation Strategies in Online Stochastic Vehicle Routing. In Proceedings of the 20 th International Joint Conference on Artificial Intelligence, IJCAI 2007, Hyderabad, India, 6-12 January 2007; pp. 1816-1821. * [PERSON] and [PERSON] (2009) [PERSON]; [PERSON] [PERSON] Collaboration and Shared Plans in the Open World: Studies of Ridesharing. In Proceedings of the 21 st International Joint Conference on Artificial Intelligence, IJCAI 2009, Pasadena, CA, USA, 11-17 July 2009; p. 187. * [PERSON] et al. (2017) [PERSON]; [PERSON]; [PERSON]; [PERSON] [PERSON] STARS: Simulating Taxi Ride Sharing at Scale. _IEEE Trans. Big Data_**2017**, \(3\), 349-361. [CrossRef]
* [PERSON] et al. (2018) [PERSON]; [PERSON]; [PERSON]; [PERSON] On Ridesharing Competition and Accessibility: Evidence from Uber, Lyft, and Taxi. In Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018, Lyon, France, 23-27 April 2018; pp. 863-872. * [PERSON] et al. (2018) [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] Addressing the minimum fleet problem in on-demand urban mobility. _Nature_**2018**, _557_, 534-538. [CrossRef] [PubMed]
* [PERSON] and [PERSON] (2019) [PERSON]; [PERSON]; [PERSON] Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications. _Oper. Res._**2019**, _67_, 143-162. [CrossRef]
* [PERSON] et al. (2014) [PERSON]; [PERSON]; [PERSON] The shared-taxi problem: Formulation and solution methods. _Transp. Res. Part B Methodol._**2014**, _70_, 303-318. [CrossRef]
* [PERSON] and [PERSON] (2018) [PERSON]; [PERSON] Algorithms for Trip-Vehicle Assignment in Ride-Sharing. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), New Orleans, LA, USA, 2-7 February 2018; pp. 3-9. * [PERSON] et al. (2015) [PERSON]; [PERSON]; [PERSON] Real-Time City-Scale Taxi Ridesharing. _IEEE Trans. Knowl. Data Eng._**2015**, _27_, 1782-1795. [CrossRef]
* [PERSON] (1995) [PERSON]; [PERSON] An Exchange Heuristic for Routeing Problems with Time Windows. _J. Oper. Res. Soc._**1995**, _46_, 1433-1446. [CrossRef]
* [PERSON] et al.