[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Log in

A two-stage dispatching approach for one-to-many ride-sharing with sliding time windows

  • Original Article
  • Published:
Neural Computing and Applications Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Algorithm 1
Fig. 8
Algorithm 2
Fig. 9
Fig. 10
Algorithm 3
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19

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

  1. 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

  2. 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

    Article  Google Scholar 

  3. 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

    Article  MathSciNet  Google Scholar 

  4. 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

  5. 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

    Article  Google Scholar 

  6. 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

    Article  Google Scholar 

  7. 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

  8. 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

    Article  Google Scholar 

  9. 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

    Article  MathSciNet  Google Scholar 

  10. 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

    Article  MathSciNet  Google Scholar 

  11. Plante RD, Lowe TJ, Chandrasekaran R (1987) The product matrix traveling salesman problem: an application and solution heuristic. Oper Res 35(5):772–783

    Article  MathSciNet  Google Scholar 

  12. 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

    Article  MathSciNet  Google Scholar 

  13. 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

    Article  Google Scholar 

  14. Hall RW, Qureshi A (1997) Dynamic ride-sharing: theory and practice. J Transp Eng 123(4):308–315

    Article  Google Scholar 

  15. 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

    Article  MathSciNet  Google Scholar 

  16. 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

    Article  Google Scholar 

  17. 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

    Article  Google Scholar 

  18. 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

    Article  MathSciNet  Google Scholar 

  19. Ö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

    Article  MathSciNet  Google Scholar 

  20. 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

    Article  Google Scholar 

  21. 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

  22. 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

    Article  Google Scholar 

  23. 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

  24. 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

    Article  Google Scholar 

  25. 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

    Article  MathSciNet  Google Scholar 

  26. 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

    Article  Google Scholar 

  27. 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

    Article  Google Scholar 

  28. 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

    Article  Google Scholar 

  29. 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

    Article  MathSciNet  Google Scholar 

  30. 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

    Article  Google Scholar 

  31. 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

    Article  Google Scholar 

  32. 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

    Article  Google Scholar 

  33. 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

    Article  Google Scholar 

  34. 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

    Article  MathSciNet  Google Scholar 

  35. 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

    Article  Google Scholar 

  36. 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

    Article  Google Scholar 

  37. 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

    Article  Google Scholar 

  38. 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

    Article  Google Scholar 

  39. 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

  40. 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

    Article  Google Scholar 

  41. 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

  42. 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

    Article  Google Scholar 

  43. 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

    Article  Google Scholar 

  44. 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

    Article  Google Scholar 

  45. 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

    Article  Google Scholar 

  46. Sun L, Teunter RH, Babai MZ, Hua G (2019) Optimal pricing for ride-sourcing platforms. Eur J Oper Res 278(3):783–795

    Article  MathSciNet  Google Scholar 

  47. 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

    Article  Google Scholar 

  48. 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

    Article  Google Scholar 

  49. 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

    Article  Google Scholar 

  50. 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

    Article  Google Scholar 

  51. 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

    Article  Google Scholar 

  52. 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

  53. 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

    Article  Google Scholar 

  54. 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

    Article  Google Scholar 

  55. 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

    Article  Google Scholar 

  56. 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

    Article  Google Scholar 

  57. 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

    Article  MathSciNet  Google Scholar 

Download references

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

Authors

Corresponding author

Correspondence to Binglei Xie.

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:

$$\begin{aligned} \eta _{<A, OB>}= \left\{ \begin{array}{l} \theta _{<A, C>},\ if \ \measuredangle AOB \le 90^{\circ } \\ \theta _{<A, C>}+ \theta _{<C, O>}, \ otherwise \end{array}\right. \end{aligned}$$
(30)
Fig. 20
figure 20

Three cases of calculating path distance degree in real-time order matching stage

Variable symbol

Table 7 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.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00521-024-09631-z

Keywords

Navigation