Research On Ridesharing Group Discovery And Optimization Based On Location Prediction

Quickly discovering users with similar travel characteristics to form a communal group and minimizing the cost of urban transportation is a research hotspot in the field of ridesharing.Aiming at the problem of ridesharing group discovery,and the location prediction technology is used to predict the destination of the traveler and plan the common multiplication group with the maximum multiplication ratio in advance for optimizing the shared travel in this paper.Firstly,due to the GPS trajectories of urban travelers are uneven distribution,a quantile strategy is proposed to map the grids,and the travel characteristics of pedestrians are constructed by using spatial grid calibration method.Then,the LP-Markov(Location and POI Based Markov)destination prediction algorithm is proposed to solve the sparse problem of the trajectory data.The algorithm can be divided into two parts,regional prediction and destination refine.The trajectory splitting and synthesis is used to extend original trajectory datasets,and Markov Model is constructed for regional prediction.In the destination refine the POI datasets is introduced,and the popularity of different POI types at different times is analyzed to find the position corresponding to the most popular POI in the region as the final predicted results.At last,in order to solve the problem of low efficiency and low accuracy in the ridesharing group discovery,the trajectory index technology is introduced to construct the GeoOD-Tree(Geographic OD-Tree)index by extending R-tree for the Origin-Destination(OD)trajectory feature.On the basis of this,a group discovery strategy with maximizing the ridesharing rate is proposed to transform ridesharing group discovery into finding travelers with similar OD trajectories,and K nearest neighbor query(K-NN)was introduced to prune and compress search space,and optimize the efficiency of ridesharing group discovery.The taxi trajectory datasets and POI datasets covering the main urban area of Xi’an were used in this paper,and the influence of the meshing strategy and grid density were analyzed on LP-Markov Prediction Model.In addition,compared with existing destination prediction algorithms,the experiment results showed the LP-Markov destination prediction algorithm is superior to weightd-MM and syn-sub prediction algorithm in the predicted error,coverage and efficiency.At the same time,the related parameters m of GeoOD-tree was analyzed,and the performance of the algorithm was compared with other traditional groups discovery algorithm,the experiment results showed the group discovery algorithm based on GeoOD-Tree index is better than DTW and ByPOI algorithm in the accuracy,recall rate and efficiency.