Design And Implementation Of Multi-Objective Driving Route Planning Algorithm

As the economy grows and living conditions improve,the number of cars increases dramatically and urban traffic becomes more and more congested.Therefore,how to compute an efficient route based on the user’s multi-objectives and effectively reduce travel costs while ensuring that the vehicle avoids traffic congestion has become a hot problem to be solved.Traditional route planning algorithms can only generate an efficient shortest path based on simple traffic scenarios.However,in the face of the complex and diverse traffic scenarios and users’ needs for different objectives such as time,distance and cost,traditional route planning algorithms can no longer satisfy.In this paper,we propose a multi-objective driven vehicle route planning algorithm(MODVRP),which can give an efficient travel path that fully satisfies the user’s requirements in complex traffic scenarios according to the user’s different objectives such as time,distance and cost.The specific work in this paper is as follows:(1)A two-weighted directed graph model with traffic scene information is constructed.The graph model used in traditional planning algorithms is relatively simple and can not effectively simulate real physical traffic scenarios.In order to simulate the physical traffic scenario more realistically,we obtain the traffic network data of the real physical scenario and constructs it into a two-weighted directed graph model with traffic scenario information.Where nodes represent individual cities(or junctions,towns or villages)and the weights of the nodes represent whether the node has tourist attractions or rest areas; The edges represent the road sections between intersections and the weights of the edges represent the distance,time or cost travelled by the vehicle through the section.(2)A multi-objective driven vehicle route planning algorithm(MODVRP)is developed.In this paper,we firstly implement three improved A~* route planning algorithms for each of the three demand objectives: shortest distance,shortest time and least cost.Then,we develop an optimal route planning algorithm by considering these three objectives together.Finally,we combine these four algorithms into a multi-objective driven vehicle route planning algorithm so that it can invoke the corresponding planning algorithm according to the user’s needs.In order to verify the effectiveness of the MODVRP algorithm,we compare the MODVRP algorithm with bi-Dijkstra algorithm based on real road network information data.The obtained results show that the MODVRP algorithm proposed in this paper has a better performance than bi-Dijkstra algorithm in terms of the quality of the generated paths,which can meet different requirements.(3)A multi-objective-driven vehicle route planning tool is posed.In order to make it easier for users to use the MODVRP algorithm to plan driving route and to clearly and intuitively view the driving route planned by the MODVRP algorithm,we pose a multiobjective-driven vehicle route planning tool based on the MODVRP algorithm and UML system analysis.The tool has the ability to input the start location and target locations and select the route planning strategy to obtain the route.The graphical results of the route planning are showed directly in the map.In order to demonstrate the effectiveness of the tool,we compare the tool with Gaode Navigation in various scenarios.The results of the comparison show that the tool has a better performance compared to Gaode Navigation in certain scenarios.