Algorithm Research On Dynamic Ridesharing Problem

Ridesharing,characterized by sharing one's transportation,has been emerged as an effective means of reducing the number of cars on roads.And it is of great significance to save transport cost while reducing the amount of traffic and also the burden on the environment.The availability of multi-source data in big data era paves the way for dynamic ridesharing that matches between requests and moving vehicles at real time.Yet studied in academia for a few years,it is still lack of popularity in practice due to the complexity of real road networks,the inflexibility of off-line booking,limited resources and so on.Large road networks are usually more complicated;there are many one-way roads and viaduct sections,especially in the modern city traffic networks.Motivated by this observation,this thesis considers real road information that has not been thoroughly studied in the dynamic matching algorithm for dynamic ridesharing.And the main work results are listed as follows:(1)The current situation development trend and relevant theory about ridesharing are introduced.(2)The model and matching algorithms of dynamic ridesharing are studied,the deficiencies in the matching algorithm of SHAREK system are modified,and the one-way viaduct section is added to the matching algorithm as heuristic information for preprocessing,through a two-framework pruning algorithm to screen some drivers who can not become Skyline results to reduce complex actual road network calculationsand improve the efficiency of matching algorithm.(3)This paper evaluate the proposed method through the experiments with the data sets generated by the website MNTG.Results show that,the proposed algorithm achieves a very high success ratio compare with SHAREK.At the same time,the experiments verified that considering the one-way road factor can effectively shorten the response time of the system.It can be concluded that the proposed framework is more effective for solving practical application problems.(4)The prototype dynamic rideshaing system is designed and implemented,and the OpenStreetMap is used to provide an intuitive display for riders.