{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:58:13Z","timestamp":1760144293738,"version":"build-2065373602"},"reference-count":42,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2024,3,22]],"date-time":"2024-03-22T00:00:00Z","timestamp":1711065600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Australian Government through the Australian Research Council\u2019s Discovery Projects","award":["DP190100013"],"award-info":[{"award-number":["DP190100013"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>Ridesharing effectively tackles urban mobility challenges by providing a service comparable to private vehicles while minimising resource usage. Our research primarily concentrates on dynamic ridesharing, which conventionally involves connecting drivers with passengers in need of transportation. The process of one-to-one matching presents a complex challenge, particularly when addressing it on a large scale, as the substantial number of potential matches make the attainment of a global optimum a challenging endeavour. This paper aims to address the absence of an optimal approach for dynamic ridesharing by refraining from the conventional heuristic-based methods commonly used to achieve timely solutions in large-scale ride-matching. Instead, we propose a novel approach that provides snapshot-optimal solutions for various forms of one-to-one matching while ensuring they are generated within an acceptable timeframe for service providers. Additionally, we introduce and solve a new variant in which the system itself provides the vehicles. The efficacy of our methodology is substantiated through experiments carried out with real-world data extracted from the openly available New York City taxicab dataset.<\/jats:p>","DOI":"10.3390\/info15040174","type":"journal-article","created":{"date-parts":[[2024,3,22]],"date-time":"2024-03-22T10:58:02Z","timestamp":1711105082000},"page":"174","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Snapshot-Optimal Real-Time Ride Sharing"],"prefix":"10.3390","volume":"15","author":[{"given":"Afzaal","family":"Hassan","sequence":"first","affiliation":[{"name":"School of Science, Computing and Engineering Technologies, Swinburne University of Technology, Melbourne, VIC 3122, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7326-8110","authenticated-orcid":false,"given":"Mark","family":"Wallace","sequence":"additional","affiliation":[{"name":"Faculty of Information Technology, Monash University, Melbourne, VIC 3800, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1345-3901","authenticated-orcid":false,"given":"Irene","family":"Moser","sequence":"additional","affiliation":[{"name":"School of Science, Computing and Engineering Technologies, Swinburne University of Technology, Melbourne, VIC 3122, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6828-7712","authenticated-orcid":false,"given":"Daniel D.","family":"Harabor","sequence":"additional","affiliation":[{"name":"Faculty of Information Technology, Monash University, Melbourne, VIC 3800, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,3,22]]},"reference":[{"key":"ref_1","unstructured":"Goodwin, P. (2004). The Economic Costs of Road Traffic Congestion, UCL (University College London), The Rail Freight Group."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"107080","DOI":"10.1016\/j.cie.2020.107080","article-title":"Optimizing ride-sharing operations in smart sustainable cities: Challenges and the need for agile algorithms","volume":"153","author":"Martins","year":"2021","journal-title":"Comput. Ind. Eng."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1287\/serv.2020.0258","article-title":"Frontiers in service science: Ride matching for peer-to-peer ride sharing: A review and future directions","volume":"12","author":"Tafreshian","year":"2020","journal-title":"Serv. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1137\/0202019","article-title":"An n5\/2 algorithm for maximum matchings in bipartite graphs","volume":"2","author":"Hopcroft","year":"1973","journal-title":"SIAM J. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","article-title":"Fibonacci heaps and their uses in improved network optimization algorithms","volume":"34","author":"Fredman","year":"1987","journal-title":"J. ACM"},{"key":"ref_6","first-page":"55","article-title":"Maximum matching and a polyhedron with 0, 1-vertices","volume":"69","author":"Edmonds","year":"1965","journal-title":"J. Res. Natl. Bur. Stand. B"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1145\/115234.115366","article-title":"Faster scaling algorithms for general graph matching problems","volume":"38","author":"Gabow","year":"1991","journal-title":"J. ACM"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/j.trb.2017.10.006","article-title":"A real-time algorithm to solve the peer-to-peer ride-matching problem in a flexible ridesharing system","volume":"106","author":"Masoud","year":"2017","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1287\/trsc.2018.0832","article-title":"A ride-sharing problem with meeting points and return restrictions","volume":"53","author":"Chen","year":"2019","journal-title":"Transp. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/j.ejor.2012.05.028","article-title":"Optimization for dynamic ride-sharing: A review","volume":"223","author":"Agatz","year":"2012","journal-title":"Eur. J. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1016\/j.trc.2020.02.008","article-title":"Trip-based graph partitioning in dynamic ridesharing","volume":"114","author":"Tafreshian","year":"2020","journal-title":"Transp. Res. Part C Emerg. Technol."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/2876480.2876483","article-title":"Dynamic ridesharing","volume":"7","author":"Shen","year":"2016","journal-title":"Sigspatial Spec."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Xu, Y., Qi, J., Borovica-Gajic, R., and Kulik, L. (2020, January 7\u20139). Geoprune: Efficiently matching trips in ride-sharing through geometric properties. Proceedings of the 32nd International Conference on Scientific and Statistical Database Management, Vienna, Austria.","DOI":"10.1145\/3400903.3400912"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2587","DOI":"10.1109\/TITS.2015.2413453","article-title":"A partition-based match making algorithm for dynamic ridesharing","volume":"16","author":"Pelzer","year":"2015","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1073\/pnas.1611675114","article-title":"On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment","volume":"114","author":"Samaranayake","year":"2017","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/j.tre.2017.10.009","article-title":"Novel dynamic formulations for real-time ride-sharing systems","volume":"108","author":"Najmi","year":"2017","journal-title":"Transp. Res. Part E Logist. Transp. Rev."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Ketabi, R., Alipour, B., and Helmy, A. (2018, January 6\u20139). Playing with matches: Vehicular mobility through analysis of trip similarity and matching. Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Seattle, WA, USA.","DOI":"10.1145\/3274895.3274992"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1109\/TKDE.2017.2760880","article-title":"An efficient ride-sharing framework for maximizing shared route","volume":"30","author":"Ta","year":"2017","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"106601","DOI":"10.1016\/j.cie.2020.106601","article-title":"Ride-sharing under travel time uncertainty: Robust optimization and clustering approaches","volume":"149","author":"Li","year":"2020","journal-title":"Comput. Ind. Eng."},{"key":"ref_20","unstructured":"Kleiner, A., Nebel, B., and Ziparo, V. (2011, January 16\u201322). A mechanism for dynamic ride sharing based on parallel auctions. Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), Barcelona, Spain."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/j.trc.2015.07.016","article-title":"Agent based model for dynamic ridesharing","volume":"64","author":"Nourinejad","year":"2016","journal-title":"Transp. Res. Part C Emerg. Technol."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Aissat, K., and Oulamara, A. (2014, January 9\u201312). Dynamic ridesharing with intermediate locations. Proceedings of the 2014 IEEE Symposium on Computational Intelligence in Vehicles and Transportation Systems (CIVTS), Orlando, FL, USA.","DOI":"10.1109\/CIVTS.2014.7009475"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1080\/15472450.2022.2121651","article-title":"Large-scale online ridesharing: The effect of assignment optimality on system performance","volume":"28","author":"Fiedler","year":"2022","journal-title":"J. Intell. Transp. Syst."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"103061","DOI":"10.1016\/j.trc.2021.103061","article-title":"On-demand ridesharing with optimized pick-up and drop-off walking locations","volume":"126","author":"Fielbaum","year":"2021","journal-title":"Transp. Res. Part C Emerg. Technol."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"3963","DOI":"10.14778\/3565838.3565849","article-title":"Online Ridesharing with Meeting Points","volume":"15","author":"Wang","year":"2022","journal-title":"Proc. VLDB Endow."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"969","DOI":"10.1080\/19427867.2022.2116674","article-title":"The ridesharing problem without predetermined drivers and riders: Formulation and heuristic","volume":"15","author":"Lu","year":"2023","journal-title":"Transp. Lett."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.trb.2013.08.012","article-title":"Ridesharing: The state-of-the-art and future directions","volume":"57","author":"Furuhata","year":"2013","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Jabbari, P., and MacKenzie, D. (2020). Ride sharing attitudes before and during the COVID-19 pandemic in the United States. Transp. Find., 26.","DOI":"10.32866\/001c.17991"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"102714","DOI":"10.1016\/j.scs.2021.102714","article-title":"Shared mobility in post-COVID era: New challenges and opportunities","volume":"67","author":"Shokouhyar","year":"2021","journal-title":"Sustain. Cities Soc."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1368","DOI":"10.1177\/03611981221123801","article-title":"Strangers On This Road We Are On: A Literature Review of Pooling in On-Demand Mobility Services","volume":"2677","author":"Hansen","year":"2023","journal-title":"Transp. Res. Rec."},{"key":"ref_31","unstructured":"Uber Technologies, Inc (2024, March 17). UberX Share. Available online: https:\/\/www.uber.com\/gb\/en\/ride\/uberx-share\/."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_33","unstructured":"Ma, S., Zheng, Y., and Wolfson, O. (2013, January 8\u201312). T-share: A large-scale dynamic taxi ridesharing service. Proceedings of the 2013 IEEE 29th International Conference on Data Engineering (ICDE), Brisbane, QLD, Australia."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Thangaraj, R.S., Mukherjee, K., Raravi, G., Metrewar, A., Annamaneni, N., and Chattopadhyay, K. (2017, January 19\u201322). Xhare-a-ride: A search optimized dynamic ride sharing system with approximation guarantee. Proceedings of the 2017 IEEE 33rd International Conference on Data Engineering (ICDE), San Diego, CA, USA.","DOI":"10.1109\/ICDE.2017.156"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"13290","DOI":"10.1073\/pnas.1403657111","article-title":"Quantifying the benefits of vehicle pooling with shareability networks","volume":"111","author":"Santi","year":"2014","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_36","unstructured":"Donovan, B., and Work, D. (2014). New York City Taxi Trip Data (2010\u20132013), University of Illinois Urbana-Champaign. Technical Report."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"103852","DOI":"10.1016\/j.trc.2022.103852","article-title":"Reinforcement learning for ridesharing: An extended survey","volume":"144","author":"Qin","year":"2022","journal-title":"Transp. Res. Part C Emerg. Technol."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Mah\u00e9o, A., Zhao, S., Hassan, A., Harabor, D.D., Stuckey, P.J., and Wallace, M. (2021, January 26\u201330). Customised Shortest Paths Using a Distributed Reverse Oracle. Proceedings of the International Symposium on Combinatorial Search, Gugangzhou, China.","DOI":"10.1609\/socs.v12i1.18554"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1016\/j.sbspro.2011.04.530","article-title":"Dynamic ride-sharing: A simulation study in metro Atlanta","volume":"17","author":"Agatz","year":"2011","journal-title":"Procedia-Soc. Behav. Sci."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3381449","article-title":"JGraphT\u2013A Java Library for Graph Data Structures and Algorithms","volume":"46","author":"Michail","year":"2020","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_41","unstructured":"Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., and Tack, G. (2007, January 23\u201327). MiniZinc: Towards a standard CP modelling language. Proceedings of the International Conference on Principles and Practice of Constraint Programming, Providence, RI, USA."},{"key":"ref_42","unstructured":"Gurobi Optimization, LLC (2022). Gurobi Optimizer Reference Manual, Gurobi Optimization, LLC."}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/15\/4\/174\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:18:15Z","timestamp":1760105895000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/15\/4\/174"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,22]]},"references-count":42,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2024,4]]}},"alternative-id":["info15040174"],"URL":"https:\/\/doi.org\/10.3390\/info15040174","relation":{},"ISSN":["2078-2489"],"issn-type":[{"type":"electronic","value":"2078-2489"}],"subject":[],"published":{"date-parts":[[2024,3,22]]}}}