Research On Dynamic Carpool Path Planning Of Online Car-hailing

Carpool refers to multiple passengers traveling in a car together.As a new type of green travel mode,carpool can effectively alleviate problems such as difficulty in taxiing and traffic congestion.After the emergence of the Internet ride-hailing model,carpool began to take off in a big way.At the same time,the problem of carpool path planning has also changed from static carpool path planning to dynamic carpool path planning.The problem studied in this paper is the dynamic carpool path planning problem of online car-hailing.Among them,passengers send their carpool requests to the platform in real-time.Online car-hailing accepts orders and route planning from the platform and provides travel services for ride-sharing passengers.The thesis first defines the concepts that appear in the carpool model.In the model,two innovations are proposed:(1)For the shortest path between any two nodes,the query method of calling map software is adopted to simplify the model.(2)Introduce time redundancy parameters.On the one hand,it is more in line with the real scene,and on the other hand,it can deliver passengers to the destination in a reasonable time while taking into account the efficiency of the system.The optimization goal of the model is to minimize the total travel distance of online car-hailing based on maximizing the completion of orders.The thesis first designs a path planning model that inserts a single passenger into a given ride-hailing travel route.After that,a traversal algorithm was designed to solve the model.After analyzing the algorithm complexity,it is found that the algorithm complexity of the traversal algorithm is relatively high,so the dynamic programming algorithm is introduced to reduce the algorithm complexity.Finally,a solution to the dynamic carpooling problem of online car-hailing in a region was designed.The paper uses Python software to simulate simulation examples to verify the effectiveness of the algorithm.The results show that the insertion method model based on the dynamic programming algorithm can effectively solve the problem of dynamic carpool path planning for online car-hailing.By comparing the simulation results of the carpooling mode and the non-carpooling mode,it is concluded that the adoption of the carpooling mode can effectively increase the order completion rate and reduce the total travel distance of the vehicle.