research-article

Locality Filtering for Efficient Ride Sharing Platforms

Authors:

Francesco Tosoni,

Paolo Ferragina,

Giovanni Resta,

Paolo SantiAuthors Info & Claims

IEEE Transactions on Intelligent Transportation Systems, Volume 23, Issue 7

Pages 7785 - 7804

https://doi.org/10.1109/TITS.2021.3072830

Published: 01 July 2022 Publication History

Abstract

Ride sharing has a tremendous potential to reduce the number of vehicles needed to serve a certain mobility demand. However, although ride sourcing services have flourished in recent years and are widely available worldwide (e.g. Uber, Didi, Lyft, Via), known ride sharing techniques still suffer severe scalability limitations, especially if the goal is combining multiple on-demand ride requests into a single trip within a large urban area. In the context of on-demand mobility systems, a complete enumeration of all candidate trip requests is unfortunately not a practical approach to find the optimal ride sharing solution. An efficient filtering approach is therefore needed in order to avoid both the storage of quadratic shortest-path lookup tables, as well as the exhaustive pairwise comparison of all mobility requests, with their GPS coordinates and time constraints. In this paper we present a ride sharing algorithm, which combined with the shareability networks method, is able to substantially speed up known approaches while only minimally impacting on the quality of the computed solution. The key building block is a novel <italic>locality filter</italic>, which allows to build a pruned version of the shareability network more efficiently in time and space than previous works. We corroborate this novel proposal with a large set of experiments executed over a dataset consisting of one month of trip requests (~10<sup>6</sup>) performed in two different urban areas, namely Manhattan (NYC) and Singapore. Our experiments show that our approach achieves a <inline-formula> <tex-math notation="LaTeX">$5\times $ </tex-math></inline-formula> speed-up, or even more during so-called “rush times”, and it is robust under different traffic conditions.

References

[1]

H. Wang and H. Yang, “Ridesourcing systems: A framework and review,” Transp. Res. B, Methodol., vol. 129, pp. 122–155, Nov. 2019. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S019126151831172X

[2]

M. W. Levin, K. M. Kockelman, S. D. Boyles, and T. Li, “A general framework for modeling shared autonomous vehicles with dynamic network-loading and dynamic ride-sharing application,” Comput., Environ. Urban Syst., vol. 64, pp. 373–383, Jul. 2017. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S019897151630237X

[3]

J. Alonso-Mora, S. Samaranayake, A. Wallar, E. Frazzoli, and D. Rus, “On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment,” Proc. Nat. Acad. Sci. USA, vol. 114, no. 3, pp. 462–467, Jan. 2017.

[4]

A. Mourad, J. Puchinger, and C. Chu, “A survey of models and algorithms for optimizing shared mobility,” Transp. Res. B, Methodol., vol. 123, pp. 323–346, May 2019. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0191261518304776

[5]

V. Ghilas, E. Demir, and T. Van Woensel, “The pickup and delivery problem with time windows and scheduled lines,” INFOR, Inf. Syst. Oper. Res., vol. 54, no. 2, pp. 147–167, Apr. 2016. 10.1080/03155986.2016.1166793.

[6]

B. Li, D. Krushinsky, H. A. Reijers, and T. Van Woensel, “The share-a-ride problem: People and parcels sharing taxis,” Eur. J. Oper. Res., vol. 238, no. 1, pp. 31–40, Oct. 2014. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0377221714002173

[7]

P. Santi, G. Resta, M. Szell, S. Sobolevsky, S. H. Strogatz, and C. Ratti, “Quantifying the benefits of vehicle pooling with shareability networks,” Proc. Nat. Acad. Sci. USA, vol. 111, no. 37, pp. 13290–13294, 2014. [Online]. Available: https://www.pnas.org/content/111/37/13290

[8]

M. M. Vazifeh, P. Santi, G. Resta, S. H. Strogatz, and C. Ratti, “Addressing the minimum fleet problem in on-demand urban mobility,” Nature, vol. 557, no. 7706, pp. 534–538, May 2018.

[9]

M. Potamias, F. Bonchi, C. Castillo, and A. Gionis, “Fast shortest path distance estimation in large networks,” in Proc. 18th ACM Conf. Inf. Knowl. Manage. (CIKM). New York, NY, USA: Association Computing Machinery, 2009, pp. 867–876. 10.1145/1645953.1646063.

Digital Library

[10]

H. Bastet al., “Route planning in transportation networks,” in Algorithm Engineering, vol. 9220. Cham, Switzerland: Springer, 2016, pp. 19–80.

[11]

I. Abraham, A. Fiat, A. V. Goldberg, and R. F. Werneck, “Highway dimension, shortest paths, and provably efficient algorithms,” in Proc. 21st Annu. ACM-SIAM Symp. Discrete Algorithms. Philadelphia, PA, USA: Society Industrial Applied Mathematics, Jan. 2010, pp. 782–793. [Online]. Available: http://dl.acm.org/citation.cfm?id=1873601.1873665

[12]

R. Geisberger, P. Sanders, D. Schultes, and C. Vetter, “Exact routing in large road networks using contraction hierarchies,” Transp. Sci., vol. 46, no. 3, pp. 388–404, Aug. 2012. 10.1287/trsc.1110.0401.

Digital Library

[13]

M. Furuhata, M. Dessouky, F. Ordóñez, M.-E. Brunet, X. Wang, and S. Koenig, “Ridesharing: The state-of-the-art and future directions,” Transp. Res. B, Methodol., vol. 57, pp. 28–46, Nov. 2013. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0191261513001483

[14]

X. M. Chen, M. Zahiri, and S. Zhang, “Understanding ridesplitting behavior of on-demand ride services: An ensemble learning approach,” Transp. Res. C, Emerg. Technol., vol. 76, pp. 51–70, Mar. 2017. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0968090X16302728

[15]

R. Abe, “Introducing autonomous buses and taxis: Quantifying the potential benefits in japanese transportation systems,” Transp. Res. A, Policy Pract., vol. 126, pp. 94–113, Aug. 2019. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0965856418312795

[16]

L. Rayle, D. Dai, N. Chan, R. Cervero, and S. Shaheen, “Just a better taxi? A survey-based comparison of taxis, transit, and ridesourcing services in San Francisco,” Transp. Policy, vol. 45, pp. 168–178, Jan. 2016. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0967070X15300627

[17]

Y. M. Nie, “How can the taxi industry survive the tide of ridesourcing? Evidence from shenzhen, China,” Transp. Res. C, Emerg. Technol., vol. 79, pp. 242–256, Jun. 2017. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0968090X17301018

[18]

Y. Wang, B. Zheng, and E.-P. Lim, “Understanding the effects of taxi ride-sharing—A case study of Singapore,” Comput., Environ. Urban Syst., vol. 69, pp. 124–132, May 2018. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0198971517301886

[19]

P. M. Boesch, F. Ciari, and K. W. Axhausen, “Autonomous vehicle fleet sizes required to serve different levels of demand,” Transp. Res. Rec., J. Transp. Res. Board, vol. 2542, no. 1, pp. 111–119, Jan. 2016. 10.3141/2542-13.

[20]

A. Simonetto, J. Monteil, and C. Gambella, “Real-time city-scale ridesharing via linear assignment problems,” Transp. Res. C, Emerg. Technol., vol. 101, pp. 208–232, Apr. 2019. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0968090X18302882

[21]

V. Pandey, J. Monteil, C. Gambella, and A. Simonetto, “On the needs for MaaS platforms to handle competition in ridesharing mobility,” Transp. Res. C, Emerg. Technol., vol. 108, pp. 269–288, Nov. 2019. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0968090X19303353

[22]

R. Geisberger, P. Sanders, D. Schultes, and D. Delling, “Contraction hierarchies: Faster and simpler hierarchical routing in road networks,” in Experimental Algorithms, C. C. McGeoch, Ed. Berlin, Germany: Springer, 2008, pp. 319–333.

[23]

H. Hosni, J. Naoum-Sawaya, and H. Artail, “The shared-taxi problem: Formulation and solution methods,” Transp. Res. B, Methodol., vol. 70, pp. 303–318, Dec. 2014. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0191261514001659

[24]

N. Agatz, A. Erera, M. Savelsbergh, and X. Wang, “Optimization for dynamic ride-sharing: A review,” Eur. J. Oper. Res., vol. 223, no. 2, pp. 295–303, Dec. 2012. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0377221712003864

[25]

Z. Bian, X. Liu, and Y. Bai, “Mechanism design for on-demand first-mile ridesharing,” Transp. Res. B, Methodol., vol. 138, pp. 77–117, Aug. 2020. [Online]. Available: https://ideas.repec.org/a/eee/transb/v138y2020icp77-117.html

[26]

A. Biswas, R. Gopalakrishnan, T. Tulabandhula, K. Mukherjee, A. Metrewar, and R. S. Thangaraj, “Profit optimization in commercial ridesharing,” in Proc. 16th Conf. Auto. Agents MultiAgent Syst. Richland, SC, USA: International Foundation Autonomous Agents Multiagent Systems, 2017, pp. 1481–1483.

[27]

M. Asghari and C. Shahabi, “An on-line truthful and individually rational pricing mechanism for ride-sharing,” in Proc. 25th ACM SIGSPATIAL Int. Conf. Adv. Geographic Inf. Syst. New York, NY, USA: Association Computing Machinery, Nov. 2017, pp. 1–10. 10.1145/3139958.3139991.

Digital Library

[28]

J. Hall, C. Kendrick, and C. Nosko, “The effects of Uber’s surge pricing: A case study,” Univ. Chicago Booth School Bus., Uber, San Francisco, CA, USA, Working Paper, 2015.

[29]

F. Wang and Y. Xu, “Estimating O–D travel time matrix by Google maps API: Implementation, advantages, and implications,” Ann. GIS, vol. 17, no. 4, pp. 199–209, Dec. 2011. 10.1080/19475683.2011.625977.

[30]

P. Amirian, A. Basiri, and J. Morley, “Predictive analytics for enhancing travel time estimation in navigation apps of apple, Google, and Microsoft,” in Proc. 9th ACM SIGSPATIAL Int. Workshop Comput. Transp. Sci. (IWCTS). New York, NY, USA: Association Computing Machinery, 2016, pp. 31–36. 10.1145/3003965.3003976.

Digital Library

[31]

T. Akiba, Y. Iwata, and Y. Yoshida, “Fast exact shortest-path distance queries on large networks by pruned landmark labeling,” in Proc. Int. Conf. Manage. Data (SIGMOD). New York, NY, USA: ACM, 2013, pp. 349–360. 10.1145/2463676.2465315.

Digital Library

[32]

P. Sanders and D. Schultes, “Highway hierarchies hasten exact shortest path queries,” in Algorithms—ESA 2005, G. S. Brodal and S. Leonardi, Eds. Berlin, Germany: Springer, 2005, pp. 568–579.

[33]

R. Tachetet al., “Scaling law of urban ride sharing,” Sci. Rep., vol. 7, no. 1, pp. 1–6, Mar. 2017. [Online]. Available: https://www.nature.com/articles/srep42868

[34]

H. Bast, S. Funke, D. Matijevic, P. Sanders, and D. Schultes, “In transit to constant time shortest-path queries in road networks,” in Proc. 9th Workshop Algorithm Eng. Exp. (ALENEX). Philadelphia, PA, USA: SIAM, 2007, pp. 46–59.

[35]

J. Arz, D. Luxen, and P. Sanders, “Transit node routing reconsidered,” in Experimental Algorithms, V. Bonifaci, C. Demetrescu, and A. Marchetti-Spaccamela, Eds. Berlin, Germany: Springer, 2013, pp. 55–66.

[36]

I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck, “A hub-based labeling algorithm for shortest paths in road networks,” in Experimental Algorithms, P. M. Pardalos and S. Rebennack, Eds. Berlin, Germany: Springer, 2011, pp. 230–241.

[37]

T. Columbus and R. Bauer, “On the complexity of contraction hierarchies,” Student Thesis, Karlsruhe Inst. Technol., Karlsruhe, Germany, 2009. [Online]. Available: https://i11www.iti.kit.edu/_media/teaching/theses/studienarbeittobiascolumbus.pdf

Cited By

Ge SZhou XQiu TWu GWang X(2023)Towards Supply-Demand Equilibrium With Ridesharing: An Elastic Order Dispatching Algorithm in MoD SystemIEEE Transactions on Mobile Computing10.1109/TMC.2023.330309023:5(5229-5244)Online publication date: 7-Aug-2023
https://dl.acm.org/doi/10.1109/TMC.2023.3303090

Index Terms

Locality Filtering for Efficient Ride Sharing Platforms
1. Human-centered computing
  1. Visualization
    1. Visualization application domains
      1. Geographic visualization
2. Information systems
  1. Information systems applications

Index terms have been assigned to the content through auto-classification.

Recommendations

Congestion-Aware Ride-Sharing
Special Issue on SIGSPATIAL 2017

In its current form, ride-sharing is responsible for a small fraction of traffic load compared to other transportation modes, especially private vehicles. As its benefits became more evident, and obstacles, e.g., lack of liability legislation, that may ...
Real-Time Distributed Taxi Ride Sharing
2018 21st International Conference on Intelligent Transportation Systems (ITSC)
Taxicabs play an important role in urban public transportation. Analyzing taxi traffic of Shanghai, San Francisco, and New York City, we have found that the short trips within city are mostly of commuters during office hours and span a specific city area. ...
Dynamic Taxi Ride Sharing using Localized Communication
ICDCN '20: Proceedings of the 21st International Conference on Distributed Computing and Networking

With the rise of on-demand taxi services, like Uber, Lyft, etc., urban public transportation started to heavily depend on taxicabs. While increasing demand leads to passenger stranding, higher supply may result in traffic congestion. In order to strike ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Intelligent Transportation Systems

IEEE Transactions on Intelligent Transportation Systems Volume 23, Issue 7

July 2022

3987 pages

ISSN:1524-9050

Issue’s Table of Contents

1558-0016 © 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.

Publisher

IEEE Press

Publication History

Published: 01 July 2022

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ge SZhou XQiu TWu GWang X(2023)Towards Supply-Demand Equilibrium With Ridesharing: An Elastic Order Dispatching Algorithm in MoD SystemIEEE Transactions on Mobile Computing10.1109/TMC.2023.330309023:5(5229-5244)Online publication date: 7-Aug-2023
https://dl.acm.org/doi/10.1109/TMC.2023.3303090

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents