交通流分配9474.pptx

《交通流分配9474.pptx》由会员分享，可在线阅读，更多相关《交通流分配9474.pptx（194页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、交通运输规划与设计刘杨将预测获得机动车将预测获得机动车OD交通量，根据交通量，根据已知的道路网描述，按照一定的规则，已知的道路网描述，按照一定的规则，符合实际地分配到路网的各条道路上，符合实际地分配到路网的各条道路上，并求出各条道路的交通量、所产生的并求出各条道路的交通量、所产生的OD费用矩阵，并据此对城市交通网费用矩阵，并据此对城市交通网络的使用状况做出分析和评价。络的使用状况做出分析和评价。交通流分配交通流分配第八章 交通流分配(Traffic Assignment)第一节第一节 交通流分配理论发展历程交通流分配理论发展历程第二节第二节 交通流分配中的基本概念交通流分配中的基本概念第三节第

2、三节 非平衡分配方法非平衡分配方法第四节第四节 平衡分配方法平衡分配方法第五节第五节 随机分配方法随机分配方法第六节第六节 动态交通流分配动态交通流分配第一节交通流分配理论发展历程交通流分配理论发展历程人们当初进行交通流分配的研究时，多采人们当初进行交通流分配的研究时，多采用全有全无用全有全无(all-or-nothing)的最短路径方法，的最短路径方法，该方法处理的是非常理想化的城市交通网该方法处理的是非常理想化的城市交通网络，即假设网络上没有交通拥挤，路阻是络，即假设网络上没有交通拥挤，路阻是固定不变的，一个固定不变的，一个OD对间的流量都分配在对间的流量都分配在“一条径路一条径路”，即最

3、短径路上。，即最短径路上。研究人员发现该最短径路方法对于城市之间研究人员发现该最短径路方法对于城市之间非拥挤公路网的规划设计过程中的交通流分非拥挤公路网的规划设计过程中的交通流分配是比较合适的配是比较合适的但对于既有的城市内部拥挤的交通网络，该但对于既有的城市内部拥挤的交通网络，该方法的结果与网络实际情况出入甚大方法的结果与网络实际情况出入甚大实际网络中，路网上存在着较严重的拥挤，实际网络中，路网上存在着较严重的拥挤，路阻是随着交通流量的增加而递增的，出行路阻是随着交通流量的增加而递增的，出行的流量会在的流量会在“多条径路多条径路”中权衡选择。中权衡选择。一、交通网络均衡理论发展历程一、交通网

4、络均衡理论发展历程(Rd-1488,1955)Martin Beckmann,1924 ,出生于出生于 GermanyDoctorate,Economics,University of Freiburg,Germany,1950Research Associate,Cowles Commission,1951-1954C.Bartlett McGuire,1925 2006,出生于出生于 Minnesota,U.S.AA.M.,Economics,University of Chicago,1952Research Associate,Cowles Commission,1952-1954Ch

5、ristopher B.Winsten,1923 2005,出生于出生于 EnglandB.A.,University of Cambridge Research Associate,Cowles Commission,1952-1954Tjalling C.Koopmans,1910 1985,出生于出生于 NetherlandsDoctorate,Economics,University of Leiden,Netherlands,1936Research Director,Cowles Commission for Research in Economics,and Professor,

6、University of Chicago,1948-1954Later,Co-Recipient Nobel Prize in Economic Sciences in 1975 四位贡献者四位贡献者源于资源分配的研究源于资源分配的研究在在1940年到年到1954年期间，年期间，Cowles Commission 是当时在数是当时在数理经济学以及运用数学规划来分析经济问题等方面最领先理经济学以及运用数学规划来分析经济问题等方面最领先的学术研究中心。的学术研究中心。Cowles的经济学家在经济科学方面共有的经济学家在经济科学方面共有12名名Nobel获得者，其中获得者，其中8位在位在19401

7、954期间从事研究。期间从事研究。“资源分配理论资源分配理论(Theory of Resources Allocation)”研究开研究开始于始于1951年，由兰德公司年，由兰德公司(Rand Corporation)提供支持提供支持.研究小组在进行道路网络的有效性研究时，提出了研究小组在进行道路网络的有效性研究时，提出了“网络网络均衡均衡”。研究论文研究论文 BMW共完成了共完成了8篇论文，从中可以看出他们研究的篇论文，从中可以看出他们研究的起点起点和和方方向向。按照时间的顺序，他们是，。按照时间的顺序，他们是，Beckmann,Optimum Transportation on Netwo

8、rks,Aug 1951McGuire,Highway Capacity and Traffic Congestion,Jul 1952Beckmann with McGuire,Efficient Transportation in Networks,Aug 1952Beckmann,Efficient Transportation in Networks,Nov 1952Beckmann,Efficient Transportation in Networks Contd,Apr 1953Beckmann and McGuire,Determination of Traffic in a

9、Road Network An Economic Approach,Rand Corporation,Oct 1953研究论文 Winsten,Some Models of Traffic Congestion,1953Winsten,Mean Delay at a Traffic Intersection,1953另外，另外，Beckmann and McGuire,Road Utilization Under Conditions of Individual Choice,被被McGuire(1952)所引所引用用,但这篇文章没有被发表但这篇文章没有被发表.u在在这些工作的基础上，他们开始

10、撰写这些工作的基础上，他们开始撰写Studies.uRand Corporation 在在1955年年5月月12日发表报告日发表报告 RM-1488,Studies in the Economics of Transportation,on May 12,1955.接下来，该手稿被耶鲁大学出版社接受出版。接下来，该手稿被耶鲁大学出版社接受出版。1955年年12月月27日，日，McGuire和和Beckmann收到来信，信收到来信，信上建议上建议Studies将付印，将付印，售价售价4美元。该书同时也被美元。该书同时也被Oxford大学出版社出版，售价大学出版社出版，售价32先令。到先令。到19

11、59为止，该为止，该书已被书已被3次印刷。次印刷。1959年，该书的西班牙版问世。年，该书的西班牙版问世。2005年年9月，月，WorldCat List of Records 的研究表明，全的研究表明，全世界世界373个图书馆收藏了个图书馆收藏了Studies，13个图书馆拥有该书个图书馆拥有该书的兰德版本。的兰德版本。7个图书馆拥有该书的西班牙版本。个图书馆拥有该书的西班牙版本。2005年年10月通过月通过Web of Science 搜索发现，搜索发现，321篇文章引篇文章引用了用了Studies Studies出版之前有关出版之前有关网络均衡的研究网络均衡的研究Knight1924Du

12、ffin194719561951Nash1952Wardrop1954Prager相关研究Knight(1924)Knight(1924)描述了一个包含两条路径的路网中的描述了一个包含两条路径的路网中的均衡和有效性均衡和有效性条件，同时纠正了条件，同时纠正了Pigou(1918)Pigou(1918)文中的一个错误文中的一个错误。“Suppose that between two points there are two highways,one of which is broad enough to accommodate without crowding all the traffic w

13、hich may care to use it,but is poorly graded and surfaced,while the other is a much better road,but narrow and quite limited in capacity.If a large number of trucks operate between the two termini and are free to choose either of the two routes,they will tend to distribute themselves between the roa

14、ds in such proportions that the cost per unit of transportation,or effective returns per unit of investment,will be the same for every truck on both routes.As more trucks use the narrower and better road,congestion develops,until a certain point it becomes equally profitable to use the broader but p

15、oorer highway.”Duffin(1947)Duffin(1947)表明一个半线性传导体的电表明一个半线性传导体的电路网络有稳定的电流状态的关键在于定义路网络有稳定的电流状态的关键在于定义在每条导线上在每条导线上“传导体函数传导体函数”的积分。的积分。Nash(1951)Nash(1951)提出了非合作关系下的提出了非合作关系下的博弈博弈论论，UEUE可看作是它的一个特例。可看作是它的一个特例。Wardrop(1952)Wardrop(1952)提出了提出了两条准则两条准则，但没有，但没有给出数学描述。给出数学描述。Charnes&Cooper195819561965Jorgense

16、n1963OvergaardJewell1966其它有关网络均衡研究其它有关网络均衡研究(StudiesStudies出版之后出版之后)1959Charnes&Cooper1968Braess除了 Studies之外的相关研究uCharnes and Cooper(1958)Charnes and Cooper(1958)按照总路段流的积分函数按照总路段流的积分函数形式，提出了形式，提出了固定需求下交通网络均衡配流固定需求下交通网络均衡配流模型。后来，模型。后来，他们利用求解线性规划的方法，针对费用函数的分段线他们利用求解线性规划的方法，针对费用函数的分段线性形式，给出求解小规模网络下的模型算

17、法。性形式，给出求解小规模网络下的模型算法。uJorgensen(1963)Jorgensen(1963)描述了描述了固定固定ODOD需求下的网络均衡配需求下的网络均衡配流流以及以及网络有效性网络有效性问题。利用问题。利用Kuhn-TuckerKuhn-Tucker定理和定理和Wardrops Wardrops 的的UEUE均衡原理，推导了均衡原理，推导了目标函数积分和目标函数积分和的的形式。形式。uBraess(1968)Braess(1968)独立提出了独立提出了网络均衡配流网络均衡配流模型，并发现模型，并发现了与直觉相反的结果：在一个交通网络中增加一条路段了与直觉相反的结果：在一个交通网

18、络中增加一条路段可能导致总出行费用增加可能导致总出行费用增加(Braess Braess 网络网络)。Network Equilibrium ResearchBased on Studies 1956MurchlandEvansPotts&OliverWalters1961Johnson1964Tomlin1967Variable OD FlowsFlorian et al.1975Erlander1977Dafermos1968Almond1965Bruynooghe et al.1969Leventhal/LeBlanc1973Nguyen1974Fixed OD FlowsNetter1

19、971基于 Studies 的研究一些年轻的研究者分析了一些年轻的研究者分析了固定需求的用户均衡问题固定需求的用户均衡问题，并，并提出提出和和检验检验了了求解算法求解算法在在19601960年期间，有一些想进一步年期间，有一些想进一步推广推广BeckmannBeckmann描述的成果，描述的成果，但但没有人没有人能从能从实质上改进实质上改进他的描述。他的描述。Evans(1973)Evans(1973)研究了研究了组合出行需求和分配模型组合出行需求和分配模型，重新发现了，重新发现了BeckmannBeckmann的模型，并得到了一个的模型，并得到了一个有效有效的并的并收敛收敛的的算法算法。Er

20、lander(1977)Erlander(1977)重新重新描述描述了了EvansEvans模型模型，并提供了一个，并提供了一个半行半行为化为化的的解释解释。之后，之后，BoyceBoyce及其学生及其学生实现实现了这些了这些算法算法，并，并探索探索了它们的了它们的计计算性质算性质。从从1968-20001968-2000，超过，超过数十篇博士论文数十篇博士论文源自这一研究。源自这一研究。标志性著作标志性著作：SheffiSheffi（19841984）在在1952年，著名交通问题专家年，著名交通问题专家Wardrop提出提出了网络平衡分配的第一、第二定理，人们了网络平衡分配的第一、第二定理，

21、人们开始采用系统分析方法和平衡分析方法来开始采用系统分析方法和平衡分析方法来研究交通拥挤时的交通流分配，带来了交研究交通拥挤时的交通流分配，带来了交通流分配理论的一次大的飞跃。通流分配理论的一次大的飞跃。首先，人们进行了确定性的分配研究，其首先，人们进行了确定性的分配研究，其前提是假设出行者能够精确计算出每条径前提是假设出行者能够精确计算出每条径路的阻抗，从而能作出完全正确的选择决路的阻抗，从而能作出完全正确的选择决定，且每个出行者的计算能力和水平是相定，且每个出行者的计算能力和水平是相同的。同的。确定性分配反映了网络的拥挤特性，反映确定性分配反映了网络的拥挤特性，反映了路阻随流量变化的实际，

22、该方法是理论了路阻随流量变化的实际，该方法是理论的一次进步。的一次进步。但是，进一步研究实际网络中出行者的出但是，进一步研究实际网络中出行者的出行行为发现，现实中出行者对路段阻抗的行行为发现，现实中出行者对路段阻抗的掌握只能是估计而得。掌握只能是估计而得。对同一路段，不同出行者的估计值不会完对同一路段，不同出行者的估计值不会完全相同，因为出行者的计算能力和水平是全相同，因为出行者的计算能力和水平是各异的。各异的。在在1977年，对交通流分配理论研究最积极、活年，对交通流分配理论研究最积极、活跃的美国加州大学伯克利分校的跃的美国加州大学伯克利分校的Daganzo教授教授及麻省理工学院的及麻省理工

23、学院的Sheffi教授提出了随机性分教授提出了随机性分配的理论。配的理论。其前提是认为出行者对路段阻抗的估计值与实其前提是认为出行者对路段阻抗的估计值与实际值之间的差别是一个随机变量，出行者会在际值之间的差别是一个随机变量，出行者会在“多条径路多条径路”中选择，同一起迄点的流量会通中选择，同一起迄点的流量会通过不同的径路到达目的地。过不同的径路到达目的地。随机性分配理论和方法的提出，在拟合、反映随机性分配理论和方法的提出，在拟合、反映现实交通网络实际的进程中又推进了一大步。现实交通网络实际的进程中又推进了一大步。.Carlos Daganzo.htm.Professor Yossi Sheff

24、i-Home.htm.Professor Yossi Sheffi Books Urban Transportation.htm随着近年来交通拥挤的进一步加重和拥挤随着近年来交通拥挤的进一步加重和拥挤在时间和空间范围上的扩大，以及智能交在时间和空间范围上的扩大，以及智能交通系统通系统(ITS)研究的进展，人们在由注意新研究的进展，人们在由注意新路网的规划设计逐步转向重视既有路网的路网的规划设计逐步转向重视既有路网的管理控制管理控制人们意识到：路网上的拥挤性、路径选择人们意识到：路网上的拥挤性、路径选择的随机性、交通需求的动态性是同时存在的随机性、交通需求的动态性是同时存在并交互作用的，其机理是

25、纷繁复杂的。并交互作用的，其机理是纷繁复杂的。确定性分配能够较好的反映网络的拥挤性，确定性分配能够较好的反映网络的拥挤性，随机性分配能够较好地反映出行选择行为随机性分配能够较好地反映出行选择行为的随机性，但是要真正地符合路网实际情的随机性，但是要真正地符合路网实际情况，还有更重要更基本的交通需求的时变况，还有更重要更基本的交通需求的时变性需要反映出来。性需要反映出来。需要一种交通流分配方法能够将路网上交需要一种交通流分配方法能够将路网上交通流的拥挤性、路径选择的随机性、交通通流的拥挤性、路径选择的随机性、交通需求的时变性综合集成地刻画反映出来，需求的时变性综合集成地刻画反映出来，这是研究交通问

26、题的人们一直积极探索的这是研究交通问题的人们一直积极探索的问题问题。.Ran,Bin.htmAll-or-NothingUE、SOSUEDTA第二节 交通分配中的基本概念一、交通流分配二、交通阻抗三、径路与最短径路四、交通平衡问题一、交通流分配一、交通流分配OD交通量是两点之间的交通量，即从出发交通量是两点之间的交通量，即从出发地到目的地之间的交通量。地到目的地之间的交通量。一般的道路网中，两点之间一般的道路网中，两点之间(即即O与与D之间之间)有很多条道路，如何将有很多条道路，如何将OD交通量正确合理交通量正确合理地分配到地分配到O与与D之间的各条道路上即是交通之间的各条道路上即是交通流分配

27、要解决的问题。流分配要解决的问题。交通流分配涉及到以下几个方面交通流分配涉及到以下几个方面:(1)可以是将现状可以是将现状OD交通量分配到现状交通网络上，以分析目前交通网络的运行状况，如果有某些路段的交通量观测值，还可以将这些观测值与在相应路段的分配结果进行比较，以检验四阶段预测模型的精度。交通量分配到现状交通网络上，以分析目前交通网络的运行状况，如果有某些路段的交通量观测值，还可以将这些观测值与在相应路段的分配结果进行比较，以检验四阶段预测模型的精度。(2)也可以是将规划年也可以是将规划年OD交通量分布预测值分配到现状交通网络上，以发现对规划年的交通需求来说，现状交通网络的缺陷，为后面交通网

28、络的规划设计提供依据。交通量分布预测值分配到现状交通网络上，以发现对规划年的交通需求来说，现状交通网络的缺陷，为后面交通网络的规划设计提供依据。(3)还可以是将规划年还可以是将规划年OD交通量分布预测值分配到规划交通网络上，以评价交通网络规划方案的优劣。交通量分布预测值分配到规划交通网络上，以评价交通网络规划方案的优劣。（1）表示需求的）表示需求的OD交通量出行矩阵。在交通量出行矩阵。在拥挤的城市道路网中通常采用高峰期拥挤的城市道路网中通常采用高峰期OD交交通量出行矩阵，在城市间公路网中通常采通量出行矩阵，在城市间公路网中通常采用年平均日交通量（用年平均日交通量（AADT）的）的OD交通量交通

29、量出行矩阵；出行矩阵；（2）路网定义，即路段及交叉口特征和属）路网定义，即路段及交叉口特征和属性数据，同时还包括其时间性数据，同时还包括其时间-流量函数；流量函数；（3）径路选择原则。）径路选择原则。进行交通流分配时所需要的基本数据有：进行交通流分配时所需要的基本数据有：对于城市道路网来说，需要特别指出三点对于城市道路网来说，需要特别指出三点:（1）由于道路的主要承载对象是车辆，）由于道路的主要承载对象是车辆，交通分配交通分配 交通流分配交通流分配 中的出行分布量一般是指机动车，以标准小汽车中的出行分布量一般是指机动车，以标准小汽车(Passenger Count Unit，PCU)为单位。交

30、通需求预测的第一步是预测交通为单位。交通需求预测的第一步是预测交通 发生量与和吸引量，这个预测值一般是以发生量与和吸引量，这个预测值一般是以“人人”为单位的，经过方式划分，将以人为单位的出行量转化成了以车为单位的出行量。为单位的，经过方式划分，将以人为单位的出行量转化成了以车为单位的出行量。（2）由于公共电汽车是按固定路线行驶的，不能自由选择行驶）由于公共电汽车是按固定路线行驶的，不能自由选择行驶 径路径路，故，故 交通分配交通流分配交通分配交通流分配 不包括这部分车辆，交通分配交通流分配不包括这部分车辆，交通分配交通流分配 的对象只是走行线路不固定的机动车辆的对象只是走行线路不固定的机动车辆

31、 的分布量。的分布量。（3）本章所讨论的分配方法也适用于人员对固定线路的公共交通）本章所讨论的分配方法也适用于人员对固定线路的公共交通 径路和工具的选择。径路和工具的选择。二、交通阻抗道路阻抗在交通流分配中可以通过路阻函数来描述。道路阻抗在交通流分配中可以通过路阻函数来描述。所谓路阻函数是指路段行驶时间与路段交通负荷，交所谓路阻函数是指路段行驶时间与路段交通负荷，交叉口延误与交叉口负荷之间的关系。叉口延误与交叉口负荷之间的关系。在具体分配过程中，由路段行驶时间及交叉口延误共在具体分配过程中，由路段行驶时间及交叉口延误共同组成出行交通阻抗。同组成出行交通阻抗。交通网络上的路阻，应包含反映交通时间

32、、交通安全、交通网络上的路阻，应包含反映交通时间、交通安全、交通成本、舒适程度、便捷性和准时性等许多因素。交通成本、舒适程度、便捷性和准时性等许多因素。延误延误是由于交通干扰以及交通管理与控制设施等因延误是由于交通干扰以及交通管理与控制设施等因素引起的运行时间损失素引起的运行时间损失信号交叉口延误是反映车辆在信号交叉口上受阻、信号交叉口延误是反映车辆在信号交叉口上受阻、行驶时间损失的评价指标行驶时间损失的评价指标延误须对交叉口各进口道分别估算各车道的每车平延误须对交叉口各进口道分别估算各车道的每车平均信控延误；均信控延误；进口道每车平均延误是进口道中各车道延误之加权进口道每车平均延误是进口道中

33、各车道延误之加权平均值；平均值；整个交叉口的每车平均延误是各进口道延误之加权整个交叉口的每车平均延误是各进口道延误之加权平均值平均值19581958年英国年英国TRRLTRRL（Transport and Road Research Laboratory Transport and Road Research Laboratory）研）研究所的究所的F.V.Webster F.V.Webster 等人根据排队论理论，提出了一个计算交叉口等人根据排队论理论，提出了一个计算交叉口延误的模型。该模型中主要包括两部分，一部分是车辆到达率为固延误的模型。该模型中主要包括两部分，一部分是车辆到达率为固定均

34、值时产生的正常相位延误即均匀延误，另一部分是车辆到达率定均值时产生的正常相位延误即均匀延误，另一部分是车辆到达率随机波动时所产生的附加延误。其具体形式为：随机波动时所产生的附加延误。其具体形式为：式中式中T-T-信号周期长度；信号周期长度；-进口道有效绿灯时间与信号周期长度之比，即绿信比；进口道有效绿灯时间与信号周期长度之比，即绿信比；Q-Q-进口道的交通流量；进口道的交通流量；X-X-饱和度，饱和度，X=Q/SX=Q/S，S S为进口道通过能力。为进口道通过能力。上式是上式是 WebsterWebster在在Monter-CarloMonter-Carlo模拟结果的基础上，校正了当初模拟结果

35、的基础上，校正了当初由排队论理论推导出的交通工程师们常用的延误公式的形式。由排队论理论推导出的交通工程师们常用的延误公式的形式。三、径路与最短径路（一）定义（一）定义1、路段、路段(Link):交通网络上相邻两个节点之间交通网络上相邻两个节点之间的交通线路称作的交通线路称作“路段路段”。2、径路、径路(Path):交通网络上任意一对交通网络上任意一对OD点对之点对之间，从发生点到吸引点一串连通的路段的有序间，从发生点到吸引点一串连通的路段的有序排列叫做这一排列叫做这一OD点对之间的径路。一个点对之间的径路。一个OD点点对之间可以有多条径路。对之间可以有多条径路。3、最短径路、最短径路:一对一对

36、OD点之间的径路中总阻抗点之间的径路中总阻抗最小的径路叫最小的径路叫“最短径路最短径路”。Shortest path ProblemAlgorithm:Dijkstras AlgorithmDials Algorithm（二）最短径路算法最短径路算法是交通流分配中最基本也最重要最短径路算法是交通流分配中最基本也最重要的算法，几乎所有交通流分配方法都是以它作的算法，几乎所有交通流分配方法都是以它作为一个基本子过程反复调用。为一个基本子过程反复调用。最短径路算法的设计问题是图论、运筹学和交最短径路算法的设计问题是图论、运筹学和交通规划领域的学者们广为关注的问题，因此已通规划领域的学者们广为关注的问

37、题，因此已经设计出了多种方法。经设计出了多种方法。最短路算法问题包含两个子问题：两点间最小最短路算法问题包含两个子问题：两点间最小阻抗的计算和两点间最小阻抗径路的辨识，前阻抗的计算和两点间最小阻抗径路的辨识，前者是解决后者的前提。者是解决后者的前提。许多算法都是将这两个子问题分开考虑，设计许多算法都是将这两个子问题分开考虑，设计出来的算法是分别单独求出最小阻抗和最短径出来的算法是分别单独求出最小阻抗和最短径路。路。最短路权计算方法最短路权计算是指计算出给定节点或任意节点最短路权计算是指计算出给定节点或任意节点间的最短路长度（时间、距离或费用）。间的最短路长度（时间、距离或费用）。1、Dijks

38、tra算法算法Dijkstra 在在1959年首先提出，称为标号法。年首先提出，称为标号法。常用于计算从某一指定点（起点）到另一指定常用于计算从某一指定点（起点）到另一指定（终点）之间的最短路权。（终点）之间的最短路权。Dijkstra算法主要特点是以起始点为中心向外算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。于它遍历计算的节点很多，所以效率低。Dijkstra算法思想算法思想 首先从起点首先从起点O开始，给每个节点一个标号开始，给

39、每个节点一个标号,分为分为T标号和标号和P标号两类；标号两类；T标号是临时标号，表示从起点标号是临时标号，表示从起点O到该点的最短路权到该点的最短路权的上限；的上限；P标号是固定标号，表示从起点标号是固定标号，表示从起点O到该点的最短路权。到该点的最短路权。标号过程中，标号过程中，T标号一直在改变，标号一直在改变，P标号不再改变，标号不再改变，凡是没有标上凡是没有标上P标号的点，都标上标号的点，都标上T标号。标号。算法的每一步把某一点的算法的每一步把某一点的T标号改变为标号改变为P标号，直标号，直到所有的到所有的T标号都改变为标号都改变为P标号。即得到从始点标号。即得到从始点O到到其他各点的最

40、短路权，标号过程结束。其他各点的最短路权，标号过程结束。Dijkstra算法求最短路径算法求最短路径 创建两个表，创建两个表，OPEN,CLOSE。OPEN表保存所有已生成而未考察的节点，表保存所有已生成而未考察的节点，CLOSED表表中记录已访问过的节点。中记录已访问过的节点。1 访问路网中里起始点最近且没有被检查过的点，把访问路网中里起始点最近且没有被检查过的点，把这个点放入这个点放入OPEN组中等待检查。组中等待检查。2 从从OPEN表中找出距起始点最近的点，找出这个点表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到的所有子节点，把这个点放到CLOSE表中。表中。3 遍历考

41、察这个点的子节点。求出这些子节点距起始遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到点的距离值，放子节点到OPEN表中。表中。4 重复重复2，3步。直到步。直到OPEN表为空，或到目标点。表为空，或到目标点。四、交通平衡问题（一）（一）Wardrop平衡原理平衡原理需求是由需求是由OD对的出行量和某一服务水平的交对的出行量和某一服务水平的交通方式来表示的。通方式来表示的。在运输系统中，存在不同条件下的平衡点。在运输系统中，存在不同条件下的平衡点。道路网络中最简单的平衡是给定出行矩阵中的道路网络中最简单的平衡是给定出行矩阵中的出行者按照最小出行费用来选择路线。出行者按照最小出

42、行费用来选择路线。通常，出行者会尝试各种线路方案，在多次尝通常，出行者会尝试各种线路方案，在多次尝试后可确定一个相对固定的方式。试后可确定一个相对固定的方式。当出行者找不到更好的路线抵达其目的地时，当出行者找不到更好的路线抵达其目的地时，此时对应的路径就反映了一种平衡：此时对应的路径就反映了一种平衡：出行者已经在最佳路线上出行，这就是路网平出行者已经在最佳路线上出行，这就是路网平衡。衡。1)多方式平衡随着拥挤的加剧，线路上的公共汽车的运随着拥挤的加剧，线路上的公共汽车的运行时间会增加，从而导致某些使用公共交行时间会增加，从而导致某些使用公共交通的乘客改变其出行线路。通的乘客改变其出行线路。这类

43、选择与小汽车等方式结合考虑，这就这类选择与小汽车等方式结合考虑，这就是多方式平衡问题。是多方式平衡问题。2)路径选择路径选择如果两点之间有多条道路且之间的交通量如果两点之间有多条道路且之间的交通量又很少的情况下又很少的情况下交通量显然沿最短径路交通量显然沿最短径路走；走；交通量增加交通量增加最短路上流量增加最短路上流量增加走行走行时间增加；时间增加；一部分交通量将选择次短路径，随着两点一部分交通量将选择次短路径，随着两点之间交通量的继续增加，两点之间的所有之间交通量的继续增加，两点之间的所有路径都有可能被利用。路径都有可能被利用。3）平衡状态）平衡状态如果所有的道路利用者（驾驶员）都能够如果所

44、有的道路利用者（驾驶员）都能够准确知道各条道路的走行时间，并选择走准确知道各条道路的走行时间，并选择走行时间最短的道路，最终两点之间所有被行时间最短的道路，最终两点之间所有被利用的道路的走行时间会相等，没有被利利用的道路的走行时间会相等，没有被利用道路的走行时间会更长。此称为路网平用道路的走行时间会更长。此称为路网平衡状态。衡状态。4）实际路网分析）实际路网分析实际路网一般有多个实际路网一般有多个OD对，对，OD之间的路径由之间的路径由很多路段组成，这些路段又可排列组合成多条很多路段组成，这些路段又可排列组合成多条不同的路径，每个不同的路径，每个OD 对间都有多条路径，且对间都有多条路径，且每

45、个每个OD对之间的路径又互相重叠。所以使得对之间的路径又互相重叠。所以使得实际道路网的平衡远远比上述描述的要复杂。实际道路网的平衡远远比上述描述的要复杂。正是由于这种复杂性，人们一直探索能够严密正是由于这种复杂性，人们一直探索能够严密定义这种平衡并能进行数学表示的途径。定义这种平衡并能进行数学表示的途径。1952年著名学者年著名学者Wardrop提出了交通网络平衡提出了交通网络平衡的定义，奠定了交通分配的基础。的定义，奠定了交通分配的基础。1.Wardrop第一原理第一原理（User Equilibrium）在道路的利用者都确切知道网络的交通状态并试图在道路的利用者都确切知道网络的交通状态并试

46、图选择最短径路时，网络将会达到平衡状态。在考虑选择最短径路时，网络将会达到平衡状态。在考虑拥挤对行驶时间影响的网络中，当网络达到平衡状拥挤对行驶时间影响的网络中，当网络达到平衡状态时，每个态时，每个OD对的各条被使用的径路具有相等而对的各条被使用的径路具有相等而且最小的行驶时间；而没有被使用的径路的行驶时且最小的行驶时间；而没有被使用的径路的行驶时间大于或等于最小行驶时间。间大于或等于最小行驶时间。For each O-D pair,at user equilibrium,the travel time on all used paths is equal,and(also)less than

47、 or equal to the travel time that would be experienced by a single vehicle on any unused path.2.Wardrop第二原理第二原理（System Optimization）系统平衡条件下，在拥挤网络中，交通流系统平衡条件下，在拥挤网络中，交通流应按照平均或总的出行成本最小的方式来应按照平均或总的出行成本最小的方式来分配。分配。Under social equilibrium conditions traffic should be arranged in congested networks in su

48、ch a way that the average(or total)travel cost is minimized.第一、第二原理的比较第一原理主要是建立个体驾驶员使其自身第一原理主要是建立个体驾驶员使其自身出行费用最小化的行为模型出行费用最小化的行为模型第二原理是面向交通规划师和工程师的第二原理是面向交通规划师和工程师的一般来说，这两个原理所得到的流量是不一般来说，这两个原理所得到的流量是不同的。同的。人们只能期望实际交通流按照人们只能期望实际交通流按照Wardrop第一第一原理原理(即用户平衡即用户平衡)的近似解来分配，第二原的近似解来分配，第二原理为交通管理人员提供了一种决策方法。理

49、为交通管理人员提供了一种决策方法。（二）平衡和非平衡分配在交通分配过程中：在交通分配过程中：如果交通分配模型采用如果交通分配模型采用Wardrop第一、第二第一、第二原理，则该模型为平衡模型；原理，则该模型为平衡模型；如果交通分配模型不使用如果交通分配模型不使用Wardrop第一、第第一、第二原理，而是采用二原理，而是采用启发式启发式方法或其它近似方法或其它近似方法的分配模型，则该模型为非平衡模型。方法的分配模型，则该模型为非平衡模型。由于复杂性，从由于复杂性，从1952年年Wardrop提出道路网平提出道路网平衡的概念和定义之后，如何求解衡的概念和定义之后，如何求解Wardrop平衡平衡成了

50、研究者的重要课题。成了研究者的重要课题。1956年，年，Beckmann等提出了描述平衡交通分等提出了描述平衡交通分配的一个数学规划模型。配的一个数学规划模型。经过经过20年之后，即到年之后，即到1975年才由年才由LeBlanc等学等学者设计出了求解者设计出了求解Beckmann模型的算法（将模型的算法（将Frank-Wolfe算法用于求解该模型），从而形算法用于求解该模型），从而形成了现在的实用解法。成了现在的实用解法。Wardrop原理原理Beckmann模型模型LeBlanc算法算法这些突破是交通分配问题研究的重大进步，也这些突破是交通分配问题研究的重大进步，也是现在交通分配问题的基础