【作者】 倪安宁；

【导师】 隽志才；

【作者基本信息】 吉林大学 ， 交通运输规划与管理， 2004， 硕士

【摘要】 交通网络分析是指通过一定的方法，评价网络特征的区位特性及特征之间的相互关系，分析个体在交通网络中一定时间内可能的活动范围。交通网络分析的重点是路径分析，而路径分析的核心为最优路径算法。以最短路径为主的最优路径问题一直是计算机科学、运筹学、交通工程学、地理信息科学等学科领域的一个研究热点。它是资源分配、路线设计及分析等优化问题的基础。随着计算机处理数据量的逐渐增多，传统的串行计算机的负荷也逐渐加重，已经不能满足大规模最短路径求解的实时要求。如在交通平衡问题中用到的Frank-Wolfe算法就需要在每一步迭代中求解最短路径来分配交通流。最短路径的求解在交通平衡应用的运行时间中占了很大的比重。针对通常的串行计算机的串行最短路径算法，几乎已经到达了理论上的时间复杂度极限。运行在服务器端的最短路径算法必须向基于图分解的并行算法的方向发展，以满足诸如ITS中的车辆诱导、先进的出行者信息系统（ATIS）及实时的动态交通分配（DTA）等交通应用中大量的实时最短路径查询的需要。并行计算所提供的存储与计算资源使得可以在合理的时间内来求解交通平衡问题。用并行的方法来进行交通平衡分析的主要目的就是减少运行时间，以便有更多时间来进行更深层次的分析。虽然目前单个处理器的速度在飞速提升，但仍不能满足交通问题中的计算需求。而并行计算非常有利于求解这类问题，更进一步来说，就是很有必要研究出一种较优的最短路径并行算法来大大减少求解交通问题时所需的计算时间。本研究正是基于这种需要而展开的。本论文分六章对研究内容，研究过程中的关键技术及所得出的结论进行了阐述，下面简要介绍一下各章的结构及主要内容：第一章绪论中主要介绍了论文研究的目的、意义、国内外研究现状及主要研究内容及研究方法。第二章中首先对最短路径算法进行了系统分类，接着对近年来所提出的各种具有较高效率的串行最短路径算法进行了理论上的时间复杂度比较，对国内外一些相关研究进行了详细评述。从而为最短路径并行算法的研究中高效串行算法的选择提供了理论依据。 <WP=81>第三章中首先阐述了最短路径算法在交通网络平衡分析中的应用，接着对当前应用最为广泛的最短路径标号算法——LS算法与LC算法及它们的并行化实现进行了深入探讨。最后讨论了分布式最短路径并行算法中的网络分割算法及终止检测方法。第四章中介绍了并行算法的基本概念及一般的并行算法实现模型，并对各种并行算法模型进行了对比；描述了并行算法的设计方法以及针对不同的硬件环境应该采用的并行模式，同时对本研究的实验环境及分布式网络并行计算平台PVM的基本原理进行了详细介绍。针对本研究的主要研究内容——最短路径并行算法的程序设计过程及实现细节，如网络的存储方式、所采用的并行算法模型及网络复制策略及网络分割策略下的程序实现等进行了详细说明。最后介绍了本研究中使用交通规划软件TransCAD采集网络数据的方法，并分析了实际交通网络的稀疏特征。第五章中首先介绍了一般并行算法与串行算法在设计思想上的不同，然后基于这种不同，描述了并行算法性能评价方法与指标。接下来，对本研究实现最短路径并行算法中所采用的三种串行算法的性能在实际路网及模拟路网上进行了对比，并得出在大多数本研究的测试网络中，LC-2q算法的性能要好于其他两种。最后对我们所实现的网络复制及网络分割策略下的并行算法的并行效益及各自的性能通过大量的实验进行了深入的对比，并根据实验结果对它们各自的优缺点进行了细致的分析。第六章是全文总结，概括了本论文的主要研究内容及有待进一步研究的地方。本研究的独到之处在于：实现了网络复制策略及网络分割策略下的最短路径并行算法，并通过详细的实验分析比较了它们各自的效率及优缺点。采用模拟退火算法对交通网络进行分割。提出了一种从交通规划软件TransCAD中提取路网数据的方法，这为以后将宏观交通模拟与微观交通模拟结合起来研究交通问题提供了一种技术途径。将实际的路网作为最短路径并行算法性能测试网络，为最短路径并行算法在交通运输问题中的应用提供了实验依据。更多还原

【Abstract】 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. <WP=83>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更多还原