A Dynamic Ridesplitting Method With Potential Pick-Up Probability Based on GPS Trajectories

Ridesplitting is a convenient and budget-friendly for-hire transportation service to arrange one-time shared rides on-the-fly. One crucial component for a ridesplitting system is the effective and efficient rider allocation method to match drivers to riders. Due to the uncertainty of ride requests, the difficulty in locating new riders is one of the problems in rider allocations. In this paper, a dynamic ridesplitting method based on the potential pick-up probability named DRPP is proposed. Given drivers and riders, DRPP aims to allocate the riders to maximize the drivers’ potential pick-up probability, subject to the riders’ time constraints and drivers’ capacity constraint. In DRPP, a grid network is first constructed to predict each grid’s pick-up probability and the traveling time between grids from historical GPS trajectories. To allocate multiple riders, an iterated local search method called ILSAS is proposed to find the solution with overall maximized potential pick-up probability for the drivers. Moreover, we propose the data structure TKdS-tree to improve the rider allocation efficiency. DRPP is evaluated on two real trajectory datasets. The experiment shows that DRPP performed better than other methods in service rate, share rate, and rider waiting time.