PPVF: A Novel Framework for Supporting Path Planning over Carpooling

With the rapid development of mobile Internet and sharing economy, carpooling over real-time taxi-calling service has attracted more and more attention. Many popular taxi-calling service platforms, e.g., didi and Uber, have developed carpooling service to the passengers. Their goal is maximizing overall profit while meeting passengers' convenience and economic benefits. Many researchers have deeply studied this problem. They usually focus on minimizing the total travel distance of drivers or making passengers' cost as fair as possible. However, these efforts ignore the fact that a 'high quality' planning path crowed with potential passengers is more valuable than a 'low quality' path for both workers and passengers. An effective high quality path planning algorithm is more desired. In this paper, we propose an efficient framework, named PPVF(short for path prediction and verification-based framework) for path planning over the road network. We first select a group of high quality paths from the historical transaction record set and manage them by proposing a novel index named PCR-Tree. Then we use them for supporting the path planning. Furthermore, we propose a searching and verification-based algorithm for further improving the path planning quality. Theoretical analysis and extensive experimental results demonstrate the effectiveness of the proposed algorithms.