Dynamic Ride-sharing Matching Strategy For Optimal Traveler Utility

On the premise of not increasing the load of urban infrastructure,ride-sharing can give full play to vehicle transport capacity,improve the utilization rate of vehicle seats,alleviate the problem of urban traffic congestion and provide efficient travel services for people.With the continuous development and popularization of mobile terminal equipment,ride-sharing becomes possible.In the ride-sharing mode,how to improve the overall travel efficiency of passengers is a hot topic of current research.Existing studies on taxi services are divided into two categories: one-to-one mode and much-to-one mode.The much-to-one mode is the ride-sharing mode.In one-to-one mode,there are a lot of researches on dynamic matching strategies between requests and vehicles,but there is still a gap in researches on ride-sharing mode.In order to improve the overall travel efficiency of passengers,this paper studies the dynamic matching strategy between requests and vehicles in the ride-sharing mode.Based on the research ideas of dynamic matching strategy between requests and vehicles in one-to-one mode,this paper proposes three dynamic matching strategies for ride-sharing:(1)Unscheduled requests are matched with idle vehicles;(2)Unscheduled requests are matched with all vehicles;(3)Unscheduled and scheduled requests are matched with all vehicles.In this paper,the mixed-integer nonlinear programming models are established for dynamic ride-sharing matching problem under three strategies.In order to solve the dynamic ride-sharing matching problem under the three strategies,this article presents a dynamic ride-sharing matching algorithm based on feasible tasks.Requests is incrementally matched with the feasible tasks of vehicles,and requests cannot be matched is constantly filtered in the process to reduce judgment whether task is feasible.Then,based on the feasible task,the original mixed-integer nonlinear programming model is transformed into the integer linear programming model,and the original problem is solved by a solver.Considering the imbalance of regional supply and demand,this paper proposes the forced matching after ride-sharing matching to make the algorithm more reasonable.Finally,this paper uses the travel dataset of working and non-working days in Manhattan,New York City,to simulate single-day requests,and uses the dynamic ride-sharing matching algorithm to conduct experiments under three strategies respectively.Experimental results show that the dynamic ride-sharing matching algorithm proposed in this paper can effectively achieve ride-sharing matching between requests and vehicles in dynamic scenarios.By comparing the performance indexes of the three strategies,when adopting the strategy that unscheduled and scheduled requests are matched with all vehicles,it is found that the fleet service rate and the average waiting time of passengers are better than the other two strategies,and the average travel delay of passengers is also well.Therefore,this paper determines that the matching of unscheduled and scheduled requests with all vehicles is the optimal strategy for dynamic ride-sharing matching.The experiment also shows the great potential of the optimal strategy: under this strategy,500 vehicles can satisfy 91.73% and 96.39% of the requests,which are respectively served by 3258 and 3103 vehicles on the working day and the non-working day,with a maximum waiting time of five minutes(maximum delay to ten minutes)tolerance value.This confirmed that the optimal matching strategy proposed in this article is of positive significance for improving vehicle seat utilization and alleviating traffic congestion.