| The Traffic Network Analysis is defined as the process that the correlativity between the regional characteristic and character of traffic network is estimated in some method and then the most possible range of individual in traffic network within some time is analyzed. Path analysis is the most important to Traffic network analysis, while optimal path algorithm is the core of path analysis.The optimal path problem which is mainly to computer the shortest path is all the while research focus in such subjects as Computer Science, Operation Research, Traffic Engineering and Geographic Information science. Additionally it is the basis of optimizing problem such as Resource Assignment, Route Design and Analysis and so on. With the increasing data required to be processed the amount of work of sequential computers become too large to meet the request to compute large-scale shortest path in real-time. For example, traffic equilibrium problems using the Frank-Wolfe algorithm require a shortest path solution for the assignment of traffic flow during each iteration of the algorithm. Consequently, this shortest path computation accounts for a large percentage of the overall execution time of the traffic equilibrium application. The usual sequential shortest path algorithms executing on sequential computer have nearly reached their time complexity limits. Shortest path algorithms running on servers have to be improved to parallel algorithms based on graph partitions to meet the requirements for inquiring real-time shortest path in such traffic applications as vehicle routing in ITS, Advanced Traveler Information System(ATIS), Dynamic Traffic Assignment(DTA) etc..Parallel processing provides the memory and computational power needed to solve the equilibrium problems in a reasonable amount of time. The primary goal of using parallel machines for traffic equilibrium applications is to reduce the execution time so that it is possible to conduct more in-depth analysis. Increases in uniprocessor speeds are significant, but insufficient for the computing requirements of traffic problems. parallel processing is beneficial for this class of applications; furthermore, it is necessary to focus on optimizing the parallel shortest path algorithms in order to improve the overall execution time of the application, which is the main goal of our research.In this dissertation, methods used in study, key technologies involved and our results from researches are described in detail in six chapters and introduced respectively as following. Chapter 1 is introduction. It includes study purpose, study signification, current research status in domestic and foreign countries, study contents and methods, and so on.In Chapter 2, firstly, all kinds of shortest algorithms are classified systemically. Then the effective sequential shortest path algorithms are compared on time complexity theoretically and domestic and foreign investigations on these algorithms are described at length. Accordingly, strong theoretical basis is provided to the choice of faster sequential shortest algorithms in the research on parallel algorithms.In Chapter 3, the application of shortest algorithm to traffic network equilibrium analysis is introduced firstly. Secondly, the most extensively applied labeling methods recently, i.e. Label Setting (LS) and Label Correcting (LC), and their parallelization processes are investigated in depth. Finally, network partition algorithm and termination detection method which both are parts of distributed parallel shortest path algorithm are given.In Chapter 4, at the beginning, the essential conceptions of parallel algorithms and models of their implements are introduced. In addition, these models are compared with each other. And the design methods to parallel algorithm and different parallel modes fit to every hardware structures are described. The hardware and software used in our experiments are then introduced, including the fundmental theory of message passing library—Parallel Virtual Machine (PVM). The way in which... |
PDF Full Text Request