Research On Optimization Of Ride-Sharing Matching Algorithm Based On Historical Order Data

In recent years,ride-sharing have been regarded as an important solution to alleviate traffic congestion and reduce air pollution in cities.Travelers with similar routes use ride-sharing to save money or reduce fuel consumption,and improve vehicle utilization.At the same time,the road utilization rate is reduced.However,the current ride-sharing service also faces many problems,including not limited to the insignificant effect of reducing the amount of travel on the road network and the low matching rate of ride-sharing.Based on this background,this paper conducts research on the trajectory matching problem of ride-sharing.First,the large-capacity and complex historical order data provided by the "Di Di" GAIA plan is used to detect noise points,stagnant points,and reconstruct missing trajectories,and convert the fully processed order coordinate point trajectory data into the form of grid area division.Grid area node trajectory data,and based on betweenness centrality,closeness centrality,eigenvector centrality and intersection flow as the screening index of key intersections in the research area,by comparing key intersections in different grid divisions Select the most suitable grid area for the precise coverage of the mouth.Then,based on the characteristics of different co-matching scenes in the improved longest common subsequence algorithm,the grid node trajectory data is matched with temporal and spatial similarity,and an integer programming model is established with the objective function of maximizing travel reduction on the road network.In order to calculate the model results more efficiently,the trajectory time-space similarity matching of hundreds of thousands of constraints is converted to the maximum weight problem of non-bipartite graph matching,and the flowering algorithm and the original dual algorithm are used to solve the problem.Finally,by comparing the matching rate and travel reduction of historical orders and the improved carpooling algorithm,the improvement of the improved ride-sharing matching algorithm on traffic travel is analyzed.In order to more accurately evaluate the improvement effect of the improved ride-sharing matching algorithm on traffic travel,this paper combines the passengers’ willingness to ride in actual travel to further analyze.The results show that in the matching mode of the abc car sharing scene(the most common car sharing scenes),as the maximum waiting time threshold for boarding increases,the car sharing matching rate rises from 28.04% to 46.73%,and the amount of travel is reduced.From 23.54% to 41.87%.If the application of “detour” ride-sharing scenario d is considered,the corresponding improvement effect is more obvious.In addition,the survey and analysis calculated that the actual willingness of Chengdu residents to ride together was about 52%,and it was applied to the waiting time threshold combination ≈120、γ≤300s,which is relatively suitable for residents to ride together,and ride together in the abc carpool scene matching mode The matching rate is roughly the same as the 19.74%matching rate of historical orders,and the reduction in itinerary is much higher than that of historical orders.Moreover,with the expansion of ride-sharing scenarios and the increase of the maximum waiting time threshold for boarding,the ride-sharing effect becomes more significant.