K-regret Query Based Dynamic Ridesharing Service

With the development of economy and the advancement of urbanization,urban trans-portation is becoming more and more congested,travel problem has aroused widely concern of public and relevant management departments.At present,there is low occupancy rate of vehicle in urban traffic,ridesharing is an effective solution to increase occupancy rate and alleviate traffic congestion.Now,some travel apps provide services including taking-a-ride and carpooling,such as Didi and Uber.They not only provide convenience for people,but also ease the traffic congestion to a certain degree.While carpooling service needs to be booked in advance and plan route artificially,it fails to process real-time committed carpooling request and complete the dynamic ridesharing service.The research content of this paper is dynamic ridesharing,which can match real-time trip requests with running vehicles dynamically.The research framework is mainly com-posed of vehicle index construction,path planning,vehicle filtering,vehicle-request match-ing.The research works of this paper concentrate on the vehicle filtering and vehicle request matching modules.In vehicle index construction,we use the grid index,which is simple but efficient and can meet the requirement of fast dynamic updating of vehicle position.In path planning,due to the path planning with multi-passengers is a form of traveling salesman problem,we use the insertion path planning strategy.In vehicle filtering,the original planning path of the vehicle can be regarded as a simplified trajectory of the planned path after inserting the new request when the insertion strategy in path planning is adopted.Based on the idea of direction-preserving trajectory simplification,a filtering algorithm that satisfies the direction constraint is proposed.Basic idea is that the feasible range of the directional constraint can be determined by the existing path of the vehicle,only the request whose destination contains within the scope of the feasible range may match the vehicle.Using this range to complete the vehicle filtering and get candidate vehicle set.Then we prove the validity of the exploration range in theory.In order to complete the vehicle-request matching,existing algorithms can not meet the personalized travel needs of passengers,we can use the Skyline query to select a match-ing vehicle,but the size of Skyline query set is not constrained.The vehicle with the highest score at this time may be selected for the vehicle-request matching according to the prefer-ence selected by the passenger or the preference function determined by their previous travel habit.we propose a matching algorithm based on k-regret query.Algorithm estimates loss of candidate vehicles,which complete the path planning,from the two dimensions of total fare and arrival delay,then selects the passenger with the biggest loss as representation to represent the entire vehicle and uses k-regret query to get the result set with the minimized maximum loss.We can improve the passengers’ travel quality by choosing a more willing vehicle according their preference.Furthermore,we consider the preference information contained in vehicle and improve query efficiency by deleting some non-optimal solutions and forming the strongly constrained k-regret query.In the experimental part,the prototype system is designed and implemented.Then,the effectiveness and efficiency of the proposed algorithm are verified by using the real road network data and the request data set.