The Research On Optimal Path Planning Algorithm For Large-scale Ridesharing Trip

With the development and popularization of mobile phones,ridesharing has become more and more acceptable.Although ridesharing has been proposed for less than 80 years,it has been encouraged and supported by government departments because of its convenience,ease of urban traffic congestion,energy saving and weight loss,and improvement of environmental quality.In our ridesharing scenario,both of passengers and drivers have their own schedules.In order to ensure that their schedules are not affected by the ridesharing when they are in the ridesharing services,passengers and drivers will indicate their time constraints and cost constraints before the ridesharing.When more than one passengers ride together during the same ridesharing service,it is necessary to meet all constraints of the passengers and the driver in the car.Besides,taking into account factors such as mitigation of traffic pressure,energy saving and emission reduction,for the passenger,we aim to find a diver,who can satisfy all ridesharing requirements of the driver and passengers with the minimum detour distance,and the corresponding optimal ridesharing path.The existing ridesharing algorithms have the following drawbacks.(1)The settings of ridesharing are not humanized.Existing ridesharing algorithms only consider the requirements of the passengers,but do not consider that the driver also has the constraints of time.(2)The price cost model is unreasonable.The existing model is a simple and crude way to give all passengers a certain rate discount,ignoring the reality that ridesharing has a greater impact on existing passengers.(3)The ridesharing route is unreasonable.Existing ridesharing algorithms only search the drivers near the passengers to provide services,regardless the drivers' destinations.Therefore,the difficulties in this paper include the following two points.Firstly,it is necessary to propose a reasonable ridesharing price cost model.Secondly we should ensure the real-time and high-efficiency of the optimal route planning algorithm in a large-scale ridesharing scenario.In order to make up these deficiencies and solve corresponding difficulties,we firstly propose a price cost model that is suitable for ridesharing scenarios.The price cost model is applicable to the ridesharing scenarios where one driver transfers one passenger and one driver transfer many passengers.Besides,balancing the interests of drivers and passengers,our model takes into account the impact of the delay on the existing passengers after the new passenger joins the car,and designs a compensation mechanism for existing passengers.Then we design the corresponding optimal path planning algorithm,named URoad,based on the model.Firstly,the algorithm adopts the departure time pruning and Euclidean distance pruning.In this way,a large number of drivers who can not meet the requirements are removed with a small time cost.Then we use greedy strategies in path planning to speed up the overall operating efficiency of the algorithm.At the end of this paper,we design a series of experiments to verify the efficiency and effectiveness of URoad.Through extensive experiments,we prove that URoad can find the optimal driver for a given passenger from more than one hundred thousand drivers within 0.5 second in average.