Research On The Construction And Algorithm Of Multi-vehicle Path Planning

With the development of modern cities and the increase in the number of vehicles per capita,traffic jams have gradually become an important bottleneck affecting the development of cities.The long commuting time,waste of resources and environmental pollution caused by traffic congestion are increasingly concerned.In daily life,a lot of congestion is due to mistakes in the planning of vehicle driving routes,and many vehicles focus on the main roads to drive,resulting in a drop in traffic efficiency.If the vehicles are all planned by the dispatch center,the congestion problem will be greatly alleviated or even solved completely.In fact,this technology has been widely used in industrial fields such as mining vehicles,unmanned warehouses,etc.,but at present,private vehicles on the roads cannot be uniformly planned.In the future,the combination of autonomous driving technology and the Internet of Things technology will make the dawn of a complete solution to this problem.Through the Internet of Things technology to obtain the vehicle’s starting point,destination,departure time and other information,the vehicle travels according to the route planned by the dispatch center,which can effectively alleviate the problem of congestion.Therefore,studying the scheduling problem of multi-vehicle routes by the dispatch center will help us to reasonably dispatch vehicle routes and alleviate road congestion.In this dissertation,the model and algorithm of multi vehicle scheduling problem are studied.The main research contents are as follows:In the aspect of model building,aiming at the common traffic network and vehicle information,this dissertation establishes a model of vehicle path problem in the traffic network based on time slice drive to simulate the real traffic situation.Through the detailed description of traffic rules and vehicle scheduling sequence,the real traffic road rules are simulated,which can increase the effectiveness of the calculated vehicle path for increasing driving efficiency.By increasing the deadlock state of vehicles in the scheduling process,the solution process can be parallelized,so as to shorten the operation time of the algorithm,and solve the priority problem of vehicles passing through the intersection and the priority problem of the intersection scheduling sequence.In terms of solving algorithms,considering the road congestion in actual operation and the frequent use of core roads,the entire transportation network is layered,and a heuristic algorithm with path congestion is used to calculate the vehicle’s route selection in real time.For the path situation of the deadlock,the path selection of the deadlock is prohibited,and the path without deadlock is calculated through the backtracking algorithm,so as to achieve the purpose of removing the deadlock.The data experiment through the simulation traffic network shows that the proposed algorithm can effectively reduce the total dispatching time and total vehicle waiting time.Finally,by analyzing the possibility of algorithm parallelization,a parallelized version of the algorithm is proposed.