Research And Implementation Of Key Algorithms For Dynamic Ridesharing

Dynamic ridesharing is a way of collecting passengers with similar travel needs in the same car to complete services.Compared with traditional taxi services,it can significantly improve the efficiency of car travel.It is expected to solve problems such as traffic congestion caused by the more and more cars in the city.Therefore,dynamic ridesharing technology has received extensive attention at home and abroad.At present,some progress has been made on the research of ridesharing,and good results have been achieved in the ridesharing matching,path planning and related algorithms.How ever,the current research still has the following two difficulties:the real-time performance of the matching algorithm between the car and the request needs to be improved;the personalized travel theory in the matching process needs to be improved,which greatly affects the development and application of dynamic ridesharing.Therefore,this thesis will focus on the above problems and study the key algorithms in dynamic ridesharing.The research content and main contributions of this thesis are as follows:Firstly,for the real-time problem of dynamic ridesharing,the Filter and Refine framework is introduced.By using the idea of hierarchical filtering,the dynamic ridesharing matching process is divided into two stages of filtering and matching,which simplifies the work of each stage and improves the real-time matching process.Secondly,in the filtering stage,a vehicle filtering algorithm based on line fit is proposed.The innovation of this algorithm is that a new line fitting degree calculation method is proposed and applied to the grid index,which is to achieve the purpose of enhancing vehicle filtering.And then,in the matching stage,a vehicle matching algorithm based on individualized requirements is proposed.The innovation of the algorithm is to introduce individualized utility functions to evaluate the individualized requirements of different passengers in different scenarios,which is to meet the passengers in matching process.Finally,the simulation experiments are designed on the Beijing road network.The experimental results verify the effectiveness of the proposed algorithms in this thesis.