Ridesharing

Ridesharing Potential (Offline Analysis)

Ridesharing is a great idea that can reduce car usage, especially during the commuting hours. Ridesharing works by matching users with similar commuting profiles, and it has great benefits both for individuals, due to reduced commuting expenses, and the city as a whole (e.g. reduced traffic and reduced pollution). Recent technological innovations, such Smartphones and social media, can make scheduling of ride-sharing trips much easier. However, despite that the idea has been around for some time now, and that the technology required to enable it is there, the full potential of ride-sharing remains unknown. When we say potential, we mean how many cars can be removed from the streets of a city thanks to ridesharing.

To assess the potential of ridesharing we use spatio-temporal and social information extracted from mobile phone data. Thanks to CDRs (Call Description Records), we can find samples of trajectories for a large population of users, and their partial social media graphs. We used CDRs for Madrid and Barcelona, for the period of September to December of 2009. For Madrid we had more than 8 hundred million calls, from 5 million users, and for Barcelona more than 4 hundred and 50 million calls from 2 million users. We also looked at different types of data sets, that are publically available. Using the Twitter Streaming API, we obtained geo-tagged tweets for 2 US cities: New York and Los Angeles. We obtain more than 5 million tweets for New York from more than 200K users, and more than 3 million tweets for more than 150K users in Los Angeles.

From our mobile data we extract: (1) home/work locations, (2) departure time distribution, (3) social graphs (e.g. from the phone calls), and we assess the potential of ridesharing assuming a distance tolerance of 1km, and a delay tolerance of 10 minutes. We find that, if users are willing to share a ride with strangers then ridesharing can have a great potential (more than 50%) . Ridesharing also has a significant potential even when social constraints are introduced; if users are willing to share a ride with one-hop friends (friends-of-friends) then potential of ridesharing can be as high as 31%.

An Online Ridesharing System

We design and build an online ridesharing system, where drivers and passengers send their requests for a ride in advance, possibly on a short notice. The system consists of two components: the constraint satisfier and the matching module.

  • Constraint Satisfier: matches a passenger (<source, destination>) with a driver (trajectory) subject to temporal and spatial constraints. Our system supports real-time queries and responses, using a specialized spatio-temporal data structure that exploits the underlying road network.
  • Matching Module: Selects pairs to share a ride among all candidate (driver, passenger) pairs. We formulate the matching problem as maximum cardinality matching allows for efficient algorithmic solution and dynamic updates.

Publications

  • Designing an On-Line Ride-Sharing System
    Blerim Cici, Athina Markopoulou, Nikolaos Laoutaris
    SIGSPATIAL (short paper) 2015 (3-6 of November, in Seattle)
    short paper
  • Assessing the Potential of Ride-Sharing Using Mobile and Social Data – A Tale of Four Cities
    Blerim Cici, Athina Markopoulou, Enrique Frías-Martínez, Nikolaos Laoutaris
    Ubicomp 2014 (13-17 of September, in Seattle), Best Paper Nominee Award (5% of the papers)
    pdf, slides
  • Quantifying the Potential of Ride-Sharing using Call Description Records
    Blerim Cici, Athina Markopoulou, Enrique Frías-Martínez, Nikolaos Laoutaris
    HotMobile 2013, Jekyll Island, GA, Feb. 2013
    pdf, slides

People