Abstract
Ride-sharing has transformed people’s travel habits with the development of various ride-sharing platforms, which can enhance the utilization of transportation resources, alleviate traffic congestion, and reduce carbon emissions. However, the development of a general and efficient matching framework is challenging due to the dynamic real-time conditions and uncertainty of ride-sharing problems in the real world. Additionally, previous research has identified limitations in terms of model practicability and algorithmic solution speed. To address these issues, a two-stage dispatching approach for one-to-many ride-sharing with sliding time windows is proposed. The dynamic ride-sharing problem is formally defined, and an integer programming model is constructed to solve it. A multi-rider distance and time constraint algorithm uses a distance matrix and sliding time windows to preprocess data before matching is proposed, thereby optimizing data quality and improving computational efficiency. The ride-sharing process is divided into a reservation order matching stage based on path similarity and a real-time order matching stage based on path distance degree. A two-stage collaborative mechanism is designed to guide the collaboration of the two stages. Furthermore, numerical experiments are conducted using two real-world datasets from developing and developed country regions to verify the efficiency and practicability of the proposed approach.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Data availability
The datasets analyzed during the current study are available from (https://sts.didiglobal.com/) and (https://www.nyc.gov/site/tlc/about/data.page/).
References
Walsh B (2011) Today’s smart choice: don’t own. share. Time international. https://content.time.com/time/specials/packages/article/0,28804,2059521_2059717_2059710,00.html
Agatz N, Erera A, Savelsbergh M, Wang X (2012) Optimization for dynamic ride-sharing: a review. Eur J Oper Res 223(2):295–303. https://doi.org/10.1016/j.ejor.2012.05.028
Gaul D, Klamroth K, Stiglmayr M (2022) Event-based MILP models for ridepooling applications. Eur J Oper Res 301(3):1048–1063. https://doi.org/10.1016/j.ejor.2021.11.05
Javidi H, Simon D, Zhu L, Wang Y (2021) A multi-objective optimization framework for online ridesharing systems. In: 2021 IEEE international conference on big data and smart computing (BigComp), pp 252–259. https://doi.org/10.1109/BigComp51126.2021.00054
Tafreshian A, Masoud N (2020) Trip-based graph partitioning in dynamic ridesharing. Transp Res Part C Emerg Technol 114:532–553. https://doi.org/10.1016/j.trc.2020.02.008
Liang X, Almeida Correia GH, An K, van Arem B (2020) Automated taxis’ dial-a-ride problem with ride-sharing considering congestion-based dynamic travel times. Transp Res Part C: Emerg Technol 112:260–281. https://doi.org/10.1016/j.trc.2020.01.024
Bathla K, Raychoudhury V, Saxena D, Kshemkalyani AD (2018) Real-time distributed taxi ride sharing. In: 2018 21st international conference on intelligent transportation systems (ITSC), pp 2044–2051. https://doi.org/10.1109/ITSC.2018.8569315
Gómez-Lobo A, Tirachini A, Gutierrez I (2022) Optimal prices for ridesourcing in the presence of taxi, public transport and car competition. Transp Res Part C: Emerg Technol 137:103591. https://doi.org/10.1016/j.trc.2022.103591
Guo Y, Zhang Y, Boulaksil Y (2020) Real-time ride-sharing framework with dynamic timeframe and anticipation-based migration. Eur J Oper Res 288(3):810–828. https://doi.org/10.1016/j.ejor.2020.06.038
Gilmore PC, Gomory RE (1964) Sequencing a one state-variable machine: a solvable case of the traveling salesman problem. Oper Res 12(5):655–679
Plante RD, Lowe TJ, Chandrasekaran R (1987) The product matrix traveling salesman problem: an application and solution heuristic. Oper Res 35(5):772–783
Cleophas C, Cottrill C, Ehmke JF, Tierney K (2019) Collaborative urban transportation: recent advances in theory and practice. Eur J Oper Res 273(3):801–816. https://doi.org/10.1016/j.ejor.2018.04.037
Ma R, Yao L, Song L, Jin M (2019) A novel algorithm for peer-to-peer ridesharing match problem. Neural Comput Appl 31(1):247–258. https://doi.org/10.1007/s00521-018-3733-5
Hall RW, Qureshi A (1997) Dynamic ride-sharing: theory and practice. J Transp Eng 123(4):308–315
Zhang C, Xie J, Wu F, Gao X, Chen G (2020) Pricing and allocation algorithm designs in dynamic ridesharing system. Theor Comput Sci 803:94–104. https://doi.org/10.1016/j.tcs.2019.05.045
Ta N, Li G, Zhao T, Feng J, Ma H, Gong Z (2018) An efficient ride-sharing framework for maximizing shared route. IEEE Trans Knowl Data Eng 30(2):219–233. https://doi.org/10.1109/TKDE.2017.2760880
Zhan X, Szeto WY, Shui CS, Chen XM (2021) A modified artificial bee colony algorithm for the dynamic ride-hailing sharing problem. Transp Res Part E: Logist Transp Rev 150:102124. https://doi.org/10.1016/j.tre.2020.102124
Enzi M, Parragh SN, Pisinger D, Prandtstetter M (2021) Modeling and solving the multimodal car- and ride-sharing problem. Eur J Oper Res 293(1):290–303. https://doi.org/10.1016/j.ejor.2020.11.046
Özkan E (2020) Joint pricing and matching in ride-sharing systems. Eur J Oper Res 287(3):1149–1160. https://doi.org/10.1016/j.ejor.2020.05.028
Ma S, Zheng Y, Wolfson O (2015) Real-time city-scale taxi ridesharing. IEEE Trans Knowl Data Eng 27(7):1782–1795. https://doi.org/10.1109/TKDE.2014.2334313
Wang D, Cao W, Li J, Ye J (2017) Deepsd: supply-demand prediction for online car-hailing services using deep neural networks. In: 2017 IEEE 33rd international conference on data engineering (ICDE), pp 243–254. https://doi.org/10.1109/ICDE.2017.83
Alisoltani N, Leclercq L, Zargayouna M (2021) Can dynamic ride-sharing reduce traffic congestion? Transp Res Part B: Methodol 145:212–246. https://doi.org/10.1016/j.trb.2021.01.004
Li M, Qin Z, Jiao Y, Yang Y, Wang J, Wang C, Wu G, Ye J (2019) Efficient ridesharing order dispatching with mean field multi-agent reinforcement learning. In: The world wide web conference. WWW ’19, pp 983–994. Association for Computing Machinery, New York, NY, USA. https://doi.org/10.1145/3308558.3313433
Ghilas V, Cordeau J-F, Demir E, Woensel TV (2018) Branch-and-price for the pickup and delivery problem with time windows and scheduled lines. Transp Sci 52(5):1191–1210. https://doi.org/10.1287/trsc.2017.0798
Vidal T, Laporte G, Matl P (2020) A concise guide to existing and emerging vehicle routing problem variants. Eur J Oper Res 286(2):401–416. https://doi.org/10.1016/j.ejor.2019.10.010
Zhou Y, Wang R, Zhao C, Luo Q, Metwally MA (2019) Discrete greedy flower pollination algorithm for spherical traveling salesman problem. Neural Comput Appl 31(7):2155–2170. https://doi.org/10.1007/s00521-017-3176-4
Dong Y, Wu Q, Wen J (2021) An improved shuffled frog-leaping algorithm for the minmax multiple traveling salesman problem. Neural Comput Appl 33(24):17057–17069. https://doi.org/10.1007/s00521-021-06298-8
Ke J, Zheng Z, Yang H, Ye J (2021) Data-driven analysis on matching probability, routing distance and detour distance in ride-pooling services. Transp Res Part C: Emerg Technol 124:102922. https://doi.org/10.1016/j.trc.2020.102922
Zajac S, Huber S (2021) Objectives and methods in multi-objective routing problems: a survey and classification scheme. Eur J Oper Res 290(1):1–25. https://doi.org/10.1016/j.ejor.2020.07.005
Zhang W, Wang Q, Shi D, Yuan Z, Liu G (2022) Dynamic order dispatching with multiobjective reward learning. IEEE Trans Intell Transp Syst. https://doi.org/10.1109/TITS.2022.3167030
Ren T, Jiang Z, Cai X, Yu Y, Xing L, Zhuang Y, Li Z (2021) A dynamic routing optimization problem considering joint delivery of passengers and parcels. Neural Comput Appl 33(16):10323–10334. https://doi.org/10.1007/s00521-021-05794-1
Guo J, Long J, Xu X, Yu M, Yuan K (2022) The vehicle routing problem of intercity ride-sharing between two cities. Transp Res Part B: Methodol 158:113–139. https://doi.org/10.1016/j.trb.2022.02.013
Aydinalp Birecik Z, Özgen D (2023) An interactive possibilistic programming approach for green capacitated vehicle routing problem. Neural Comput Appl 35(12):9253–9265. https://doi.org/10.1007/s00521-022-08180-7
Guo Y, Zhang Y, Boulaksil Y, Qian Y, Allaoui H (2023) Modelling and analysis of online ride-sharing platforms–A sustainability perspective. Eur J Oper Res 304(2):577–595. https://doi.org/10.1016/j.ejor.2022.04.035
Beirigo BA, Negenborn RR, Alonso-Mora J, Schulte F (2022) A business class for autonomous mobility-on-demand: modeling service quality contracts in dynamic ridesharing systems. Transp Res Part C: Emerg Technol 136:103520. https://doi.org/10.1016/j.trc.2021.103520
Xu Z, Yin Y, Chao X, Zhu H, Ye J (2021) A generalized fluid model of ride-hailing systems. Transp Res Part B: Methodol 150:587–605. https://doi.org/10.1016/j.trb.2021.05.014
Zhu Z, Ke J, Wang H (2021) A mean-field markov decision process model for spatial-temporal subsidies in ride-sourcing markets. Transp Res Part B: Methodol 150:540–565. https://doi.org/10.1016/j.trb.2021.06.014
Nair GS, Bhat CR, Batur I, Pendyala RM, Lam WHK (2020) A model of deadheading trips and pick-up locations for ride-hailing service vehicles. Transp Res Part A: Policy Pract 135:289–308. https://doi.org/10.1016/j.tra.2020.03.015
Ma T-Y (2017) On-demand dynamic bi-/multi-modal ride-sharing using optimal passenger-vehicle assignments. In: 2017 IEEE international conference on environment and electrical engineering and 2017 IEEE industrial and commercial power systems Europe (EEEIC / I &CPS Europe), pp 1–5. https://doi.org/10.1109/EEEIC.2017.7977646
Wang H (2019) Routing and scheduling for a last-mile transportation system. Transp Sci 53(1):131–147. https://doi.org/10.1287/trsc.2017.0753
Chaturvedi M, Srivastava S (2022) A multi-modal ride sharing framework for last mile connectivity. In: 2022 14th international conference on communication systems & NETworkS (COMSNETS), pp 824–829. IEEE, Bangalore, India. https://doi.org/10.1109/COMSNETS53615.2022.9668583
Wang X, Liu W, Yang H, Wang D, Ye J (2020) Customer behavioural modelling of order cancellation in coupled ride-sourcing and taxi markets. Transp Res Part B: Methodol 132:358–378. https://doi.org/10.1016/j.trb.2019.05.016
Li Y, Liu Y, Xie J (2020) A path-based equilibrium model for ridesharing matching. Transp Res Part B: Methodol 138:373–405. https://doi.org/10.1016/j.trb.2020.05.007
Wang J, Wang X, Yang S, Yang H, Zhang X, Gao Z (2021) Predicting the matching probability and the expected ride/shared distance for each dynamic ridepooling order: a mathematical modeling approach. Transp Res Part B: Methodol 154:125–146. https://doi.org/10.1016/j.trb.2021.10.005
Goel P, Kulik L, Ramamohanarao K (2017) Optimal pick up point selection for effective ride sharing. IEEE Trans Big Data 3(2):154–168. https://doi.org/10.1109/TBDATA.2016.2599936
Sun L, Teunter RH, Babai MZ, Hua G (2019) Optimal pricing for ride-sourcing platforms. Eur J Oper Res 278(3):783–795
Guo G, Xu Y (2022) A deep reinforcement learning approach to ride-sharing vehicle dispatching in autonomous mobility-on-demand systems. IEEE Intell Transp Syst Mag 14(1):128–140. https://doi.org/10.1109/MITS.2019.2962159
Agussurja L, Cheng S-F, Lau HC (2019) A state aggregation approach for stochastic multiperiod last-mile ride-sharing problems. Transp Sci 53(1):148–166. https://doi.org/10.1287/trsc.2018.0840
Feng S, Duan P, Ke J, Yang H (2022) Coordinating ride-sourcing and public transport services with a reinforcement learning approach. Transp Res Part C: Emerg Technol 138:103611. https://doi.org/10.1016/j.trc.2022.103611
Urata J, Xu Z, Ke J, Yin Y, Wu G, Yang H (2021) Ye J (2021) Learning ride-sourcing drivers’ customer-searching behavior: a dynamic discrete choice approach. Transp Res Part C: Emerg Technol 130:103293. https://doi.org/10.1016/j.trc.2021.103293
Singh A, Al-Abbasi AO, Aggarwal V (2021) A distributed model-free algorithm for multi-hop ride-sharing using deep reinforcement learning. IEEE Trans Intell Transp Syst. https://doi.org/10.1109/TITS.2021.3083740
Riley C, van Hentenryck P, Yuan E (2020) Real-time dispatching of large-scale ride-sharing systems: Integrating optimization, machine learning, and model predictive control. In: Proceedings of the Twenty-Ninth international joint conference on artificial intelligence, pp 4417–4423. International joint conferences on artificial intelligence organization, Yokohama, Japan. https://doi.org/10.24963/ijcai.2020/609
Singh A, Al-Abbasi AO, Aggarwal V (2022) A distributed model-free algorithm for multi-hop ride-sharing using deep reinforcement learning. IEEE Trans Intell Transp Syst 23(7):8595–8605. https://doi.org/10.1109/TITS.2021.3083740
Liu Y, Wu F, Lyu C, Li S, Ye J, Qu X (2022) Deep dispatching: a deep reinforcement learning approach for vehicle dispatching on online ride-hailing platform. Transp Res Part E: Logist Transp Rev 161:102694. https://doi.org/10.1016/j.tre.2022.102694
Guo Y, Li W, Xiao L, Allaoui H (2023) A prediction-based iterative Kuhn-Munkres approach for service vehicle reallocation in ride-hailing. Int J Prod Res. https://doi.org/10.1080/00207543.2023.2247092
Wang D, Wang Q, Yin Y, Cheng TCE (2023) Optimization of ride-sharing with passenger transfer via deep reinforcement learning. Transp Res Part E: Logist Transp Rev 172:103080. https://doi.org/10.1016/j.tre.2023.103080
Kuhn HW (1955) The Hungarian method for the assignment problem. Naval Res Logist Q 2(1–2):83–97. https://doi.org/10.1002/nav.3800020109
Acknowledgements
This work was supported by the Shenzhen Knowledge Innovation Program, China [grant number JCYJ20210324133202006]; the National Natural Science Foundation of China [grant number 71974043]; the Shenzhen Philosophy and Social Sciences Project, China [grant number SZ2023B007].
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Proof
In this appendix, we explain the three cases that occur in the TOS when calculating the path distance degree. That is, when calculating the shortest vertical path from a point to a path, three different cases arise due to the angle between the point and the path. As shown in Fig. 20, in case 1, the \(\measuredangle AOB\) is an obtuse angle: The shortest vertical distance between the point A and the path \(<O, B>\) is \(\theta _{<A, C>} + \theta _{<C, O>}\), where \(\theta _{<C, O>}\) is the extra detour distance. In case 2, the \(\measuredangle AOB\) is a right angle: The shortest vertical distance between the point A and the path \(<O, B>\) is \(\theta _{<A, O>}\). In case 3, the \(\measuredangle AOB\) is an acute angle: The shortest vertical distance between the point A and the path \(<O, B>\) is \(\theta _{<A, C>}\). Then, the shortest vertical distance between point A and the path \(<O, B>\) is:
Variable symbol
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Liu, Y., Xie, B., Xu, G. et al. A two-stage dispatching approach for one-to-many ride-sharing with sliding time windows. Neural Comput & Applic 36, 11213–11239 (2024). https://doi.org/10.1007/s00521-024-09631-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00521-024-09631-z