Dynamic and Distributed Taxi Ride-Sharing System
(An amazing Ride-Sharing System without a Centeral Server)
Due to the rise of on-demand taxicab services, like Uber and Lyft, the paradigm of urban public transportation has been redefined. However, with increasing traffic in major cities, road congestion becomes more common during peak hours. Trajectory analysis of individual taxi trips has shown unique patterns as well as hot-spots for passenger pick and drop locations in any metropolitan area around the world (Chicago, Shanghai, San Francisco, New York City, etc.). These regular trip patterns establish the postulate that passengers following the same route can travel via ride-sharing as long as their trips are spatio-temporally co-located.
Ride-sharing is fast emerging as the new cost-effective mode of transport which can (1) ensure higher taxi occupancy while lowering the total number of on-road vehicles, thereby reducing overall road congestion; and (2) increase the profit for taxi drivers while reducing cost for passengers. However, dynamically scheduling taxi rides is non-trivial given the wide variety of spatio-temporal constraints.
Moreover, existing ride-sharing systems operate in a centralized manner that is non-scalable, fault-prone and they are mostly proprietary. We propose a novel dynamic and distributed shared ride scheduling system for taxicabs that ensure a ride-sharing success rate of 97.6%. We have developed 4 different ride matching algorithms which work by peer-to-peer interaction between taxi drivers and passengers. We have carried out extensive simulations using large-scale taxi trip data from Chicago metropolitan area and established the efficiency of our proposed algorithms. We have also developed a proof-of-concept prototype to show the viability of the ride-sharing system using a number of mobile hand-held devices.