交通分配PAS算法的研究与应用

发布时间：2018-01-03 16:39

本文关键词：交通分配PAS算法的研究与应用　出处：《东南大学》2015年硕士论文　论文类型：学位论文

【摘要】：Bar-gera提出了一种新的求解交通分配问题的算法,用以获得高精度的解。算法主要是通过基于起点的子网络上构建和存储PAS结构,然后在PAS结构上进行流量转移。这种高效的算法被称为交通分配PAS算法,其巨大的优势也使得对其研究称为一件迫切的工作。本文的目标就是系统研究交通分配PAS算法的原理,尤其是其关键步骤的计算过程。然后在这些基础上将算法用程序实现,再用不同规模的路网对该算法检验,评价算法的效率。论文主要分为三个部分：第一部分,系统研究算法的原理,主要是指算法的三个主要内容,包括建立PAS结构,转移流量和均衡起点比例。而对于其中的关键步骤如广度优先搜索法和转移流量值的方法,更是采用实例加以详细描述。在充分掌握算法原理基础之上,为程序实现PAS算法奠定基础。第二部分,为了用程序实现算法,设计了路网信息和交通需求的数据存储结构,以及算法当中关键步骤的计算策略。在这些基础之上,用C#程序语言编写了算法的主程序,在计算机上实现了PAS算法。第三部分,在程序实现算法的基础之上,用不同规模的路网对算法加以验算,对算法的运行效率以及收敛精度有了一个直观的认识。在检验之前,还对算法的收敛标准和收敛精度进行了设计,采用平均额外费用指标更易于算法的实现。最后,还将PAS算法与牛顿算法(GP)进行了比较,分析了两种算法的运行效率与收敛精度,得出了在精度要求不高时,两种算法的效率基本一样,但是PAS算法在求解高精度解的情况下效率更高。
[Abstract]:Bar-gera proposed a new algorithm to solve traffic assignment problem to obtain high precision solution. The algorithm is mainly based on the starting point of the sub-network to construct and store the PAS structure. Then flow transfer is carried out on the PAS structure. This efficient algorithm is called traffic assignment PAS algorithm. Because of its great advantages, it is an urgent task to study it. The goal of this paper is to systematically study the principle of traffic assignment PAS algorithm. Especially the calculation process of its key steps. Then the algorithm is realized by program on the basis of these, and then the algorithm is tested with different scale road network. The paper is divided into three parts: the first part, the principle of the algorithm, mainly refers to the three main contents of the algorithm, including the establishment of PAS structure. The key steps, such as breadth-first search method and transfer-flow value method, are described in detail by examples, and on the basis of fully mastering the principle of the algorithm. In the second part, in order to realize the algorithm by program, the data storage structure of road network information and traffic requirement is designed. On the basis of these, the main program of the algorithm is written in C # programming language, and the PAS algorithm is implemented on the computer. The third part. On the basis of the implementation of the algorithm in the program, the algorithm is checked with different scales of road network, which has an intuitive understanding of the efficiency and convergence accuracy of the algorithm. The convergence standard and convergence accuracy of the algorithm are also designed. It is easier to implement the algorithm by using the average extra cost index. Finally, the PAS algorithm is compared with the Newton algorithm. The efficiency and convergence accuracy of the two algorithms are analyzed. It is concluded that the efficiency of the two algorithms is basically the same when the precision is not high, but the PAS algorithm is more efficient in solving the high-precision solution.
【学位授予单位】：东南大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：U491.123

【相似文献】