Abstract
By encouraging passengers to share taxi trips, taxi ridesharing is of significant social and environmental benefit, such as saving energy consumption and satisfying people’s commute in peak hours. Despite the great potential, the taxi ridesharing, especially with dynamic queries, is not well studied. In this paper, we formally define the dynamic ridesharing problem and present a large-scale taxi ridesharing service, which efficiently serves real-time requests sent by taxi users and generates ridesharing schedules that reduce the total travel distance significantly. In our method, we first propose a taxi searching algorithm using a spatio-temporal index to quickly retrieve candidate taxies that could satisfy a user query. A schedule allocation algorithm is then proposed to check each candidate taxi so as to insert the user’s trip into the schedule of the taxi which satisfies the query with minimum incurred travel distance for the ridesharing. To tackle the heavy computational load, a lazy shortest path calculation strategy is devised to speed up this schedule allocation algorithm. We evaluated our service with a GPS trajectory dataset generated by over 33,000 taxies during a period of 3 months. By learning the spatio-temporal distributions and the stochastic process of real user queries from this dataset, we built an experimental platform that can simulate user behaviours in taking a taxi in the real-world. Tested on this platform with extensive experiments, our approach demonstrates its efficiency, effectiveness, and scalability. For example, our proposed service can serve 40% additional taxi users while saving 15% travel distance over no ridesharing (when the ratio between the number of queries and the number of taxies is 5).
