Abstract
Dynamic ride-sharing services such as UberPool or MOIA are becoming increasingly popular as they offer a cheap and flexible mode of transportation and reduce traffic compared to traditional taxi and ride-hailing services. One key optimization problem when operating ride-sharing services is the assignment of trip requests to vehicles to maximize the service rate while minimizing operational costs. In this work, we propose a real-time dispatching algorithm capable of quickly processing incoming trip requests. This dispatching algorithm is combined with a local search that aims to improve the current routing plan. Both algorithms are embedded into a planning and simulation framework for dynamic ride-sharing and evaluated through simulation studies on real-world datasets from Hamburg, New York City, and Chengdu. The results show that the local search improvement phase can improve the request acceptance rate as well as vehicle travel times. We achieve an average reduction of the request rejection rate by 1.62% points and a decrease in vehicle travel time per served request of 6.5%. We also study the influence of pre-booked rides and show that the local search yields even larger benefits when part of the trip requests are known in advance.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Provided by PTV Group, Haid-und-Neu-Str. 15, 76131 Karlsruhe, Germany.
- 2.
- 3.
References
Alonso-Mora, J., Samaranayake, S., Wallar, A., Frazzoli, E., Rus, D.: On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment. Proc. Natl. Acad. Sci. 114(3), 462–467 (2017). https://doi.org/10.1073/pnas.1611675114
Alonso-Mora, J., Wallar, A., Rus, D.: Predictive routing for autonomous mobility-on-demand systems with ride-sharing. In: 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3583–3590. IEEE, Vancouver (September 2017). https://doi.org/10.1109/IROS.2017.8206203
Berbeglia, G., Cordeau, J.F., Laporte, G.: Dynamic pickup and delivery problems. Eur. J. Oper. Res. 202(1), 8–15 (2010). https://doi.org/10.1016/j.ejor.2009.04.024
Chen, L., Gao, Y., Liu, Z., Xiao, X., Jensen, C.S., Zhu, Y.: PTrider: a price-and-time-aware ridesharing system. Proc. VLDB Endow. 11(12), 1938–1941 (2018). https://doi.org/10.14778/3229863.3236229
Cordeau, J.F., Laporte, G.: The dial-a-ride problem: models and algorithms. Ann. Oper. Res. 153(1), 29–46 (2007). https://doi.org/10.1007/s10479-007-0170-8
Dibbelt, J., Strasser, B., Wagner, D.: Customizable contraction hierarchies. J. Exp. Algorithmics 21(1), 1–49 (2016). https://doi.org/10.1145/2886843
Funke, B., Grünert, T., Irnich, S.: Local search for vehicle routing and scheduling problems: review and conceptual integration. J. Heuristic 11(4), 267–306 (2005). https://doi.org/10.1007/s10732-005-1997-2
Huang, Y., Bastani, F., Jin, R., Wang, X.S.: Large scale real-time ridesharing with service guarantee on road networks. Proc. VLDB Endow. 7(14), 2017–2028 (2014). https://doi.org/10.14778/2733085.2733106
Lowalekar, M., Varakantham, P., Jaillet, P.: ZAC: A zone path construction approach for effective real-time ridesharing. In: Proceedings of the International Conference on Automated Planning and Scheduling, vol. 29, no. 1, pp. 528–538 (2019)
Lowalekar, M., Varakantham, P., Jaillet, P.: Zone pAth Construction (ZAC) based approaches for effective real-time ridesharing. J. Artif. Intell. Res. 70, 119–167 (2021). https://doi.org/10.1613/jair.1.11998
Ma, S., Zheng, Y., Wolfson, O.: T-share: a large-scale dynamic taxi ridesharing service. In: 2013 IEEE 29th International Conference on Data Engineering (ICDE), Brisbane, QLD, pp. 410–421. IEEE(April 2013). https://doi.org/10.1109/ICDE.2013.6544843
Ma, S., Zheng, Y., Wolfson, O.: Real-time city-scale taxi ridesharing. IEEE Trans. Knowl. Data Eng. 27(7), 1782–1795 (2015). https://doi.org/10.1109/TKDE.2014.2334313
Molenbruch, Y., Braekers, K., Caris, A.: Typology and literature review for dial-a-ride problems. Ann. Oper. Res. 259(1–2), 295–325 (2017). https://doi.org/10.1007/s10479-017-2525-0
Pouls, M., Meyer, A., Ahuja, N.: Idle vehicle repositioning for dynamic ride-sharing. In: Lalla-Ruiz, E., Mes, M., Voß, S. (eds.) ICCL 2020. LNCS, vol. 12433, pp. 507–521. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-59747-4_33
Riley, C., Legrain, A., Van Hentenryck, P.: Column generation for real-time ride-sharing operations. In: Rousseau, L.-M., Stergiou, K. (eds.) CPAIOR 2019. LNCS, vol. 11494, pp. 472–487. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-19212-9_31
Shah, S., Lowalekar, M., Varakantham, P.: Neural approximate dynamic programming for on-demand ride-pooling. Proc. AAAI Conf. Artif. Intell. 34(01), 507–515 (2020). https://doi.org/10.1609/aaai.v34i01.5388
Uber: Uberpool (2021). https://www.uber.com/us/en/ride/uberpool. Accessed 08 Jan 2021
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Pouls, M., Meyer, A., Glock, K. (2021). Real-Time Dispatching with Local Search Improvement for Dynamic Ride-Sharing. In: Mes, M., Lalla-Ruiz, E., Voß, S. (eds) Computational Logistics. ICCL 2021. Lecture Notes in Computer Science(), vol 13004. Springer, Cham. https://doi.org/10.1007/978-3-030-87672-2_20
Download citation
DOI: https://doi.org/10.1007/978-3-030-87672-2_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-87671-5
Online ISBN: 978-3-030-87672-2
eBook Packages: Computer ScienceComputer Science (R0)