Abstract
The key to a successful ridesharing service is an efficient allocation and routing of vehicles and customers. In this paper, relevant aspects from practice, like customer waiting times, are integrated into a mathematical programming model for the operational optimization of a dynamic ridesharing system, improving existing models from the literature. Moreover, a new heuristic solution method for the optimization of a dynamic ridepooling system is developed and compared with the exact solution derived by a MIP solver based on the above-mentioned model.
In a case study consisting of 30 customers who request different rides and can be transported by a fleet of 10 vehicles in the area of Hamburg, both approaches are tested. The results show that the heuristic solution method is superior to the exact solution method, especially with respect to the required solution time.
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
References
MOIA GmbH: Ridesharing in Hamburg. https://www.moia.io/de-DE/hamburg. Accessed 22 Jun 2019
Krafcik, J.: Waymo One. https://medium.com/waymo/waymo-one-the-next-step-on-our-self-driving-journey-6d0c075b0e9b. Accessed 22 Jun 2019
WunderCar Mobility Solutions GmbH. https://www.wundermobility.com/. Accessed 22 Jun 2019
Schaller Consulting, The New Automobility: Lyft, Uber and the Future of American Cities. http://www.schallerconsult.com/rideservices/automobility.pdf. Accessed 22 Jun 2019
Hou, L., Li, D., Zhang, D.: Ride-matching and routing optimisation: models and a large neighbourhood search heuristic. Transp. Res. E Logist. Transp. Rev. 118, 143–162 (2018)
Agatz, N., Erera, A., Savelsbergh, M., Wang, X.: Optimization for dynamic ride-sharing. Eur. J. Oper. Res. 223(2), 295–303 (2012)
Hosni, H., Naoum-Sawaya, J., Artail, H.: The shared-taxi problem: formulation and solution methods. Transp. Res. B Methodol. 70, 303–318 (2014)
Masoud, N., Jayakrishnan, R.: A decomposition algorithm to solve the multi-hop peer-to-peer ride-matching problem. Transp. Res. B Methodol. 99, 1–29 (2017)
Furuhata, N., Dessouky, M., Ordóñez, F., Brunet, M.-E., Wang, X., Koenig, S.: Ridesharing. The state-of-the-art and future directions. Transp. Res. B Methodol. 57, 28–46 (2013)
Herbawi, W., Weber, M.: A Genetic and Insertion Heuristic Algorithm for Solving the Dynamic Ridematching Problem with Time Windows. In: Soule, T., Moore, J. (eds.) Proceedings of the Fourteenth International Conference on Genetic and Evolutionary Computation Conference, pp. 385–392. ACM, New York City, NY (2012)
Kleiner, A., Nebel, B., Ziparo, V.: A mechanism for dynamic ride sharing based on parallel auctions. In: Walsh, T. (ed.) Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, pp. 266–272. AAAI, Menlo Park, CA (2011)
Santos, D., Xavier, E.: Taxi and ride sharing. A dynamic dial-a-ride problem with money as an incentive. Expert Syst. Appl. 42(19), 6728–6737 (2015)
Agatz, N., Erera, A., Savelsbergh, M., Wang, X.: Sustainable passenger transportation: dynamic ride-sharing. ERIM Report Series Reference No. ERS-2010-010-LIS (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Rückert, N., Sturm, D., Fischer, K. (2020). A Heuristic Solution Approach for the Optimization of Dynamic Ridesharing Systems. In: Neufeld, J.S., Buscher, U., Lasch, R., Möst, D., Schönberger, J. (eds) Operations Research Proceedings 2019. Operations Research Proceedings. Springer, Cham. https://doi.org/10.1007/978-3-030-48439-2_89
Download citation
DOI: https://doi.org/10.1007/978-3-030-48439-2_89
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-48438-5
Online ISBN: 978-3-030-48439-2
eBook Packages: Business and ManagementBusiness and Management (R0)