R-Sharing: Rendezvous for Personalized Taxi Sharing

Dynamic taxi sharing is an effective approach to reducing travel cost and conserving energy resources. Existing taxi sharing frameworks fail to consider personal preferences of passengers on taxi-sharing and unable to group them with compatible preferences for generating the optimal sharing schedule. In this paper, we propose a novel taxi-sharing framework called R-Sharing to provide a personalized rendezvous-sharing service. It enables passengers to set their preferences on four essential sharing experience, i.e., walking distance, waiting time, travel fare, and extra travel time. Given a sharing request, R-Sharing searches the optimal set of nearby companions with compatible personal preferences and similar destination directions, recommends a rendezvous point for them to meet, and plans the shortest sharing route, such that these passengers' probability of accepting the sharing schedule is maximized. Specifically, a companion candidate searching algorithm is proposed for searching nearby potential candidates to sharing a taxi for the request. To select the optimal subset of candidates and generate their optimal sharing schedule, we propose an exact taxi-sharing scheduling algorithm, in which, the rendezvous point is set by considering passengers' personal preference on walking distance and road network factors, and the shortest sharing route is planned by dynamic programming. Further, a heuristic sharing scheduling algorithm is developed to improve the efficiency. Extensive experiments are conducted using a one-month taxi trajectory data set collected in Nanjing, China. Experimental results show that R-Sharing is not only effective in terms of achieving better sharing ratio and reduced total travel distance, but also provides superior sharing experiences.