Utility-aware Dynamic Matching For Real-time Ridesharing Service

Ridesharing refers to a new travel mode in which multiple passengers with the same or similar itinerary travel with the same car.This model has many advantages such as improving resource utilization efficiency,alleviating traffic congestion,sharing travel expenses,and protecting the environment.With the increasing popularity of ridesharing travel,people’s travel needs have begun to show a diversified and hierarchical development trend.The existing travel service only considers itinerary match can no longer meet the residents’ safety,comfort,and convenience needs.Based on this,this thesis studies the "utility-aware dynamic matching for real-time Ridesharing Service",trying to solve the key problems in utility-aware ridesharing in the real-time road network environment,and provide new ideas for systematic and practical vehicle sharing service research in theories and new methods.The research content is introduced as follows:First of all,to solve the problem that the ridesharing preference model is difficult to express and generalize in a unified form,a universal multi-passenger matching framework based on utility-aware is proposed.It evaluates the matching between passengers and vehicles participating in the ridesharing service from the perspective of social relations,interest and price.At the same time,for passengers and vehicles that dynamically enter the ridesharing system,the multi-passenger matching mode is used to improve the efficiency of vehicles.In this regard,this thesis proposes three ridesharing algorithms and a new graph structure describing the relationship between passengers and vehicles.And use this graph to further optimize the search process,and improve the matching efficiency of the utility-aware ridesharing.Finally,the experiment verifies the effectiveness of the algorithm and model proposed in this thesis.Secondly,on the basis of the ridesharing matching framework,the utility-aware dynamic ridesharing matching under energy constraints is studied.Electric vehicles are an important direction for the transformation,upgrading and green development of the automobile industry,and will become an important part of ridesharing services.Compared with traditional fuel vehicles,electric vehicles are more susceptible to energy constraints,such as a serious shortage of charging stations and long charging time,which leads to the need to ensure vehicle energy constraints and consider the route planning of the charging station layout during the driving.Therefore,this thesis defines and models the problem,and proposes three matching algorithms to improve the efficiency of path planning and vehicle matching through spatio-temporal constraint pruning and grid index structure.Finally,the effectiveness of the proposed model and algorithms are verified in the simulation system.In the last,simulation experiments that carried out on the real data sets based on the order data set of Didi and NYCTaxi verified the performance of the proposed matching algorithms.The experimental results show that the algorithm proposed in this thesis can effectively improve the quality and balance in speed.