short-paper

Designing an on-line ride-sharing system

Authors:

SIGSPATIAL '15: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems

Article No.: 60, Pages 1 - 4

https://doi.org/10.1145/2820783.2820850

Published: 03 November 2015 Publication History

Get Access

Abstract

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 known in advance and they become available a few minutes before departure. In this paper, we design an online ride sharing system, where drivers and passengers send their requests for a ride in advance, possibly on a short notice. Our design is efficient and optimal. This is achieved by dividing the system into two components: the constraint satisfier and the matching module. The constraint satisfier takes as input the spatio-temporal constraints of drivers and passengers and provides feasible (driver, passenger) pairs in real time, and the matching module takes as input the feasible pairs and provides a maximum cardinality matching of drivers and passengers. Our preliminary evaluation shows that the constraint satisfier can resolve the most expensive queries (matching of passenger to en-route drivers) in 2 seconds (on average), while the matching module can achieve a matching ratio of 78% when the offline upper-bound is 80%.

References

[1]

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

Google Scholar

[2]

"Ridesharing: The state-of-the-art and future directions," Transportation Research Part B: Methodological, vol. 57, no. 0, pp. 28--46, 2013.

Google Scholar

[3]

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.

Google Scholar

[4]

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, 2014.

Digital Library

Google Scholar

[5]

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

Google Scholar

[6]

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, Massachusetts Institute of Technology, 2010.

Google Scholar

[7]

"Optimization for dynamic ride-sharing: A review," European Journal of Operational Research, vol. 223, no. 2, pp. 295--303, 2012.

Crossref

Google Scholar

[8]

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

Crossref

Google Scholar

[9]

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

Google Scholar

[10]

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

Google Scholar

[11]

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

Google Scholar

[12]

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

Google Scholar

[13]

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

Google Scholar

Cited By

View all

Gong ZZeng YChen L(2024)Real-Time Insertion Operator for Shared Mobility on Time-Dependent Road NetworksProceedings of the VLDB Endowment10.14778/3654621.365463317:7(1669-1682)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.14778/3654621.3654633
Jin QLi BCheng YZhao X(2024)Real-time Multi-platform Route Planning in ridesharingExpert Systems with Applications10.1016/j.eswa.2024.124819255(124819)Online publication date: Dec-2024
https://doi.org/10.1016/j.eswa.2024.124819
Nasr Azadani MAbolhassani A(2023)Multi-objective Optimization in a “Specified Driver’s Origin and Destination” Ridesharing SystemSAE International Journal of Sustainable Transportation, Energy, Environment, & Policy10.4271/13-05-01-00035:1Online publication date: 27-Apr-2023
https://doi.org/10.4271/13-05-01-0003
Show More Cited By

Index Terms

Designing an on-line ride-sharing 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

SORS: a scalable online ridesharing system
IWCTS '16: Proceedings of the 9th ACM SIGSPATIAL International Workshop on Computational Transportation Science

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: ...
Intelligent automatic overtaking system using vision for vehicle detection

Highlights We have implemented an autonomous overtaking system in a commercial car. The system performs the maneuver as humans do, i.e., depending on the leading vehicle. Vision system is use to detect obstacles and to determine its length and width. ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIGSPATIAL '15: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 2015

646 pages

ISBN:9781450339674

DOI:10.1145/2820783

General Chairs:
Mohamed Ali
University of Washington, Tacoma
,
Yan Huang
University of North Texas
,
Program Chairs:
Michael Gertz
Heidelberg University, Germany
,
Matthias Renz
LMU Munich, Germany
,
Jagan Sankaranarayanan
NEC Labs

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]

In-Cooperation

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 November 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper

Conference

SIGSPATIAL'15

Sponsor:

SIGSPATIAL

SIGSPATIAL'15: 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 3 - 6, 2015

Washington, Seattle

Acceptance Rates

SIGSPATIAL '15 Paper Acceptance Rate 38 of 212 submissions, 18%;

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
371
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gong ZZeng YChen L(2024)Real-Time Insertion Operator for Shared Mobility on Time-Dependent Road NetworksProceedings of the VLDB Endowment10.14778/3654621.365463317:7(1669-1682)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.14778/3654621.3654633
Jin QLi BCheng YZhao X(2024)Real-time Multi-platform Route Planning in ridesharingExpert Systems with Applications10.1016/j.eswa.2024.124819255(124819)Online publication date: Dec-2024
https://doi.org/10.1016/j.eswa.2024.124819
Nasr Azadani MAbolhassani A(2023)Multi-objective Optimization in a “Specified Driver’s Origin and Destination” Ridesharing SystemSAE International Journal of Sustainable Transportation, Energy, Environment, & Policy10.4271/13-05-01-00035:1Online publication date: 27-Apr-2023
https://doi.org/10.4271/13-05-01-0003
Nabila SHashem TAnwar SIslam A(2023)Efficient algorithms for community aware ridesharingGeoInformatica10.1007/s10707-023-00509-128:3(403-432)Online publication date: 23-Nov-2023
https://doi.org/10.1007/s10707-023-00509-1
Chen YWang L(2022)P-Ride: A Shareability Prediction Based Framework in RidesharingElectronics10.3390/electronics1107116411:7(1164)Online publication date: 6-Apr-2022
https://doi.org/10.3390/electronics11071164
Wang JCheng PZheng LChen LZhang W(2022)Online Ridesharing with Meeting PointsProceedings of the VLDB Endowment10.14778/3565838.356584915:13(3963-3975)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.14778/3565838.3565849
Haliem MAggarwal VBhargava B(2022)AdaPool: A Diurnal-Adaptive Fleet Management Framework Using Model-Free Deep Reinforcement Learning and Change Point DetectionIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2021.310961123:3(2471-2481)Online publication date: Mar-2022
https://doi.org/10.1109/TITS.2021.3109611
Wu HChen YWang LMa G(2022) E -Ride: An Adaptive Event-Driven Windowed Matching Framework in Ridesharing IEEE Access10.1109/ACCESS.2022.316703310(43799-43811)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3167033
Khaturia RWicaksono HFatahi Valilai O(2022)SRP: A Sustainable Dynamic Ridesharing Platform Utilizing Blockchain TechnologyDynamics in Logistics10.1007/978-3-031-05359-7_24(301-313)Online publication date: 5-May-2022
https://doi.org/10.1007/978-3-031-05359-7_24
Haliem MMani GAggarwal VBhargava B(2021)A Distributed Model-Free Ride-Sharing Approach for Joint Matching, Pricing, and Dispatching Using Deep Reinforcement LearningIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2021.309653722:12(7931-7942)Online publication date: Dec-2021
https://doi.org/10.1109/TITS.2021.3096537
Show More Cited By

View Options

Login options

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

Cited By

Index Terms

Recommendations

SORS: a scalable online ridesharing system

Intelligent automatic overtaking system using vision for vehicle detection

Dynamic intersections and self-driving vehicles