Research On The Constrained K-shortest Paths Algorithm Within A Dynamic Restricted Searching Area

With the increasing development of society and economy, the traffic congestion is gradually becoming one of the most serious social problems currently. An important characteristic of the traffic congestion is randomness, which implies that it is unreasonable for travelers to make routing decisions totally depending on their previous traveling experience because relying on such experience will not only result in some loss to individuals but also to deteriorate the whole traffic condition. One of the most effective solutions to this problem is to establish the advance Urban Traffic Flow Guidance System (UTFGS), providing the real time traffic information in the road network by employing the path planning technology to help the pre-trip or/ and en-route travelers make the right routing decisions.The most valuable function of the UTFGS is to redistribute the traffic volume when it is not in equilibrium or the traffic congestion occurs in some part of the road network. Its ultimate goal is to maximize the efficiency of roads and network and to minimize the travel cost of travelers. Path planning technology helps people to optimize the routes before or during the trip. It has been recognized as one the core problems of the UTFGS. Commonly, the optimal path provided to the travelers is a unique one, so that it may cause the overreaction and concentration of drives and lead to a result of congestion shifting. Shifting of congestion may cause a unbalance state of traffic volume in road network. Aiming at avoiding driving into a congestion area, drivers are forced to choose a alternative path, as a matter of fact, this may cause the secondary congestion of other paths. Obviously, the route recommended by the UTFGS is not the real optimal one. If user follows such routes, he may be guided onto the seriously congested links and waste much time. Even worse, such case will degrade user's trust in the UTFGS, which has bad impacts on the application and promotion of it.Stemming from the National High-tech Research and Development Program (863 Program): Research and development of intelligent navigation software and its application system based on the dynamic information with No. 2007AA12Z242 and the 863 Program: Feature extraction and integration technology of regional traffic system state with No. 2007AA11Z245, this thesis emphatically analyses the root causes of the congestion shifting problem, then develops a constrained K-shortest paths algorithm within a dynamic restricted searching area in consideration of road network spatial distribution features which is suitable for the travelers and realizes its program on the basis of MAPX Control. By providing proper experimental scheme, the actual effect of this algorithm is tested with the micro simulation tool VISSIM. Some conclusions have been drawn as follows, the constrained K-shortest paths algorithm can not only decrease the searching scale and improve its running efficiency but also efficiently balance the traffic flow and prevent the congestion shifting problem, so that both the travelers and the whole system could benefit a lot from this.The thesis comprises of 6 chapters and their contents are as follows:Chapter One: Introduction. First, explain what and why to be investigated in the thesis. Point out the thesis's value both from the perspective of theory and practice, and then summarize the key technologies of the route optimization by introducing the history and status quo of the UTFGS at home and abroad. After that, the main content and structure of the thesis is given.Chapter Two: Representation and storage method of road Network. The principles to produce the electronic map special for vehicle guidance are proposed and the general methods to represent the road network are introduced in this chapter, then improve the data structure to store the guidance information based on the previous achievements.Chapter Three: Rsearch on simple source path planning algorithm. With an analysis of the research status of path planning technology at home and abroad, the improved dijkstra algorithm is determined as a core of the constrained K-shortest path algorithm to compute the single source shortest path.Chapter Four: Constrained K-shortest paths algorithm within a dynamic restricted searching area. A constrained K-shortest paths algorithm within a dynamic restricted searching area in consideration of road network spatial distribution features is proposed on basis of some achievements at home and abroad, and at the same time the complexity of the algorithm is analyzed.Chapter Five: Realization and test of the algorithm. After the analysis of real road network spatial distribution features, this chapter realizes the program of the algorithm on the basis of MAPX Control, and at the same time the sensitivity analysis of the overlap constraint and the detour constraint is given. Later, by providing proper experimental scheme, the actual effect of this algorithm is tested with the micro simulation tool VISSIM.Chapter Six: Conclusions and the future work. The thesis is summed up and the research process and the main contents of the thesis are looked back. At the same time, point out the innovation and the existing problems, as well as the problems that need to further study in the future.