More Web Proxy on the site http://driver.im/

research-article

Public Access

SORS: a scalable online ridesharing system

Authors:

Athina Markopoulou,

Nikolaos LaoutarisAuthors Info & Claims

IWCTS '16: Proceedings of the 9th ACM SIGSPATIAL International Workshop on Computational Transportation Science

Pages 13 - 18

https://doi.org/10.1145/3003965.3003971

Published: 31 October 2016 Publication History

Abstract

In this paper, we design and evaluate SORS- a scalable online ridesharing system, where drivers and passengers send their requests for a ride in advance, possibly on a short notice. SORS is modular and consists of two main, loosely coupled, components: the Constraint Satisfier and the Matching Module. The Constraint Satisfier takes as input information about the desired trajectories and spatio-temporal constraints of drivers and passengers and it returns a list of feasible (driver, passenger) pairs. We use a road networks data structure, optimized for the specific spatio-temporal queries in the context of ridesharing, and we show that our Constraint Satisfier has a 4.65x more scalable query time than a general-purpose database. We represent the feasible pairs of drivers and passengers as a weighted bipartite graph with edge weight being the length of the shared trip of the pair, which captures the revenue in real-world ridesharing systems, such as Lyft Carpool. The Matching Module then takes as input this weighted bipartite graph and returns the maximum weighted matching (MWM), using an algorithm that solves the problem online and efficiently, by incrementally updating the matching solution in real-time. We show that our algorithm achieves 51% larger weight (i.e., total revenue) compared to greedy heuristics used by many real systems today. We also evaluate the SORS system as a whole, using mobile datasets to extract driver trajectories and passenger locations in urban environments. We show that SORS can provide a ridesharing recommendation to individual users within a sub-second query response time, even at high workloads.

References

[1]

B. McKenzie and M. Rapino, "Commuting in the united states: 2009." American Community Survey Reports, 2009.

[2]

"More people in fewer cars." https://newsroom.uber.com/us-washington/more-people-in-fewer-cars/, 2016.

[3]

"Meet lyft carpool: A new way to commute." http://blog.lyft.com/posts/meet-lyft-carpool, 2016.

[4]

"Announcing uberpool." https://newsroom.uber.com/announcing-uberpool/, 2014.

[5]

M. Furuhata, M. Dessouky, F. Ordónez, M.-E. Brunet, X. Wang, and S. Koenig, "Ridesharing: The state-of-the-art and future directions," Transportation Research Part B: Methodological, vol. 57, no. 0, pp. 28--46, 2013.

[6]

H. S., "Implementing Real-Time Ridesharing in the San Francisco Bay Area.," Master's thesis, Mineta Transportation Institute, San Jose State University, CA, USA, 2010.

[7]

"Scoop." https://www.takescoop.com/, 2015.

[8]

S. Ma, Y. Zheng, and O. Wolfson, "T-Share: A Large-Scale Dynamic Taxi Ridesharing Service.," in Proc. of ICDE, 2013.

Digital Library

[9]

J. F. Cordeau and G. Laporte, "The Dial-a-Ride Problem (DARP): Variants, modeling issues and algorithms," 4OR, vol. 1, 2003.

[10]

N. Agatz, A. Erera, M. Savelsbergh, and X. Wang, "Optimization for dynamic ride-sharing: A review," European Journal of Operational Research, vol. 223, no. 2, pp. 295 -- 303, 2012.

[11]

R. Teal, "Carpooling: Who, how and why," Transportation Research, vol. 21A, no. 3, pp. 203--214, 1987.

[12]

K. D., "Carpooling: Status and potential." Final Report U.S. Department of Transportation, DOT-TSC-OST-75-23, 1975.

[13]

A. M. Amey, "Real-Time Ridesharing: Exploring the Opportunities and Challenges of Designing a Technology-based Rideshare Trial for the MIT Community," Master's thesis, MIT, 2010.

[14]

B. Cici, A. Markopoulou, E. Frias-Martinez, and N. Laoutaris, "Assessing the Potential of Ride-Sharing Using Mobile and Social Data: A Tale of Four Cities," in Proc. of UbiComp (Best Paper Nominee Award), 2014.

Digital Library

[15]

B. Cici, A. Markopoulou, and N. Laoutaris, "Designing an On-Line Ride-Sharing System," in Proc. of SIGSPATIAL (short paper), 2015.

Digital Library

[16]

"Mongodb." http://www.mongodb.org/.

[17]

"Scaling mongodb at foursquare." http://www.10gen.com/presentations/mongonyc-2012-scaling-mongodb-foursquare.

[18]

"Geospatial indexes in mongodb." http://docs.mongodb.org/manual/core/geospatial-indexes/.

[19]

E. Frentzos, "Indexing objects moving on fixed networks," in Proc. of SSTD, 2003.

[20]

K. Mouratidis and M. L. Yiu, "Anonymous query processing in road networks," IEEE Trans. Knowl. Data Eng., vol. 22, no. 1, 2010.

Digital Library

[21]

"9th dimacs implementation challenge - shortest paths." http://www.dis.uniroma1.it/challenge9/download.shtml, 2015.

[22]

C. H. Papadimitriou and K. Steiglitz, "Algorithms for matching," in Combinatorial Optimization, Algorithms and Complexity, ch. 10, pp. 221--226, 1998.

Cited By

(2019)SharYInternational Journal of Knowledge Engineering and Data Mining10.5555/3309420.33094216:1(1-31)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.5555/3309420.3309421
Chen JDoryab AHanrahan BYousfi ABeck JWang XBellotti VDey ACarroll J(2019)Context-Aware Coproduction: Implications for Recommendation AlgorithmsInformation in Contemporary Society10.1007/978-3-030-15742-5_54(565-577)Online publication date: 13-Mar-2019
https://doi.org/10.1007/978-3-030-15742-5_54
Svangren MSkov MKjeldskov JMandryk RHancock MPerry MCox A(2018)Passenger Trip Planning using Ride-Sharing ServicesProceedings of the 2018 CHI Conference on Human Factors in Computing Systems10.1145/3173574.3174054(1-12)Online publication date: 21-Apr-2018
https://dl.acm.org/doi/10.1145/3173574.3174054

Index Terms

SORS: a scalable online ridesharing system
1. Human-centered computing
  1. Visualization
    1. Visualization application domains
      1. Geographic visualization
2. Information systems
  1. Information systems applications
    1. Data mining
    2. Spatial-temporal systems

Recommendations

Designing an on-line ride-sharing system
SIGSPATIAL '15: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems

Ride-sharing systems have the potential to match travelers with similar itineraries and time schedules, and to bring significant benefits to individual users and the city as a whole. However, this is a challenging task, since users' requests are not ...
Dynamic intersections and self-driving vehicles
ICCPS '18: Proceedings of the 9th ACM/IEEE International Conference on Cyber-Physical Systems

Connected and automated vehicles are expected to be at the core of future intelligent transportation systems. One of the main practical challenges for self-driving vehicles on public roads is safe cooperation and collaboration among multiple vehicles ...
Autonomous Vehicles Empty Cruising Impact on Parking Dynamics
IWCTS '23: Proceedings of the 16th ACM SIGSPATIAL International Workshop on Computational Transportation Science

As development and utilization of autonomous vehicles is gaining momentum, it is expected to be decades of mixed environment where autonomous and human-driven vehicles will co-exist. Autonomous vehicles' ability to perform empty cruising can impact the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

IWCTS '16: Proceedings of the 9th ACM SIGSPATIAL International Workshop on Computational Transportation Science

October 2016

65 pages

ISBN:9781450345774

DOI:10.1145/3003965

General Chair:
Stephan Winter
The University of Melbourne, Australia
,
Program Chairs:
Gautam S. Thakur
Oak Ridge National Laboratory
,
Nicole Ronald
Swinburne University of Technology, Australia

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 October 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF

Conference

SIGSPATIAL'16

SIGSPATIAL'16: 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

October 31 - November 3, 2016

California, Burlingame

Acceptance Rates

Overall Acceptance Rate 42 of 57 submissions, 74%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
323
Total Downloads

Downloads (Last 12 months)66
Downloads (Last 6 weeks)4

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

(2019)SharYInternational Journal of Knowledge Engineering and Data Mining10.5555/3309420.33094216:1(1-31)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.5555/3309420.3309421
Chen JDoryab AHanrahan BYousfi ABeck JWang XBellotti VDey ACarroll J(2019)Context-Aware Coproduction: Implications for Recommendation AlgorithmsInformation in Contemporary Society10.1007/978-3-030-15742-5_54(565-577)Online publication date: 13-Mar-2019
https://doi.org/10.1007/978-3-030-15742-5_54
Svangren MSkov MKjeldskov JMandryk RHancock MPerry MCox A(2018)Passenger Trip Planning using Ride-Sharing ServicesProceedings of the 2018 CHI Conference on Human Factors in Computing Systems10.1145/3173574.3174054(1-12)Online publication date: 21-Apr-2018
https://dl.acm.org/doi/10.1145/3173574.3174054

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Table of Contents