交通流分配分解优秀PPT.ppt

《交通流分配分解优秀PPT.ppt》由会员分享，可在线阅读，更多相关《交通流分配分解优秀PPT.ppt（99页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、交通流支配交通流支配（Traffic Assignment）交通流支配是本课程的重点和难点之一。最优化理论、图论、交通流支配是本课程的重点和难点之一。最优化理论、图论、计算机技术的发展，为交通流支配模型和算法的探讨及开发计算机技术的发展，为交通流支配模型和算法的探讨及开发供应了坚实的基础，通过几十年的发展，交通流支配是交通供应了坚实的基础，通过几十年的发展，交通流支配是交通规划诸问题中被国内外学者探讨得最深化、取得探讨成果最规划诸问题中被国内外学者探讨得最深化、取得探讨成果最多的部分。多的部分。本章主要讲解并描述交通流支配的基本概念、基本原理和基本章主要讲解并描述交通流支配的基本概念、基本原理

2、和基本方法，交通流支配的非平衡支配、平衡支配的模型和算法本方法，交通流支配的非平衡支配、平衡支配的模型和算法等内容。等内容。概概 述述两种机制相互作用直至平衡：两种机制相互作用直至平衡：一种机制是：各种车辆试图通过在网络上选择最佳一种机制是：各种车辆试图通过在网络上选择最佳行驶路途来达到自身出行费用最小的目标；行驶路途来达到自身出行费用最小的目标；另一种机制是：道路上的车流量越大，用户遇到的另一种机制是：道路上的车流量越大，用户遇到的阻力即对应的行驶阻抗越高。阻力即对应的行驶阻抗越高。用确定的模型来描述这两种机制及其相互作用，并用确定的模型来描述这两种机制及其相互作用，并求解网络上交通流量在平

3、衡状态下的合理分布，即求解网络上交通流量在平衡状态下的合理分布，即交通流支配。交通流支配。就是将预料得出的就是将预料得出的ODOD交通量，依据已知的道路网交通量，依据已知的道路网描述，依据确定的规则符合实际地支配到路网中描述，依据确定的规则符合实际地支配到路网中的各条道路上去，进而求出路网中各路段的交通的各条道路上去，进而求出路网中各路段的交通流量、所产生的流量、所产生的ODOD费用矩阵，并籍此对城市交通费用矩阵，并籍此对城市交通网络的运用状况做出分析和评价。网络的运用状况做出分析和评价。交通配流路径路径n路径路径1路径路径2ODOD最初的交通流支配探讨，多接受全有全无方法。最初的交通流支配探

4、讨，多接受全有全无方法。该方法处理的是特殊志向化的城市交通网络，即假设该方法处理的是特殊志向化的城市交通网络，即假设网络上没有交通拥挤，路阻是固定不变的，一个网络上没有交通拥挤，路阻是固定不变的，一个ODOD对对间的流量都支配在间的流量都支配在“一条径路一条径路”，即最短径路上。，即最短径路上。但对于既有的城市内部拥挤的交通网络，该方法的结但对于既有的城市内部拥挤的交通网络，该方法的结果与网络实际状况出入甚大。果与网络实际状况出入甚大。交通配流的发展阶段在在19521952年，著名交通问题专家年，著名交通问题专家WardropWardrop提出了网络平衡支配的提出了网络平衡支配的第一、其次定理

5、，人们起先接受系统分析方法和平衡分析方第一、其次定理，人们起先接受系统分析方法和平衡分析方法来探讨交通拥挤时的交通流支配。法来探讨交通拥挤时的交通流支配。确定性的平衡配流：其前提是假设出行者能够精确计算出每确定性的平衡配流：其前提是假设出行者能够精确计算出每条径路的阻抗，从而能作出完全正确的选择确定，且每个出条径路的阻抗，从而能作出完全正确的选择确定，且每个出行者的计算实力和水平是相同的。行者的计算实力和水平是相同的。现实中出行者对路段阻抗的驾驭只能是估计而得。对同一路现实中出行者对路段阻抗的驾驭只能是估计而得。对同一路段，不同出行者的估计值不会完全相同，因为出行者的计算段，不同出行者的估计值

6、不会完全相同，因为出行者的计算实力和水平是各异的。实力和水平是各异的。交通配流的发展阶段在在19771977年，对交通流支配理论探讨最主动、活跃的美国加州年，对交通流支配理论探讨最主动、活跃的美国加州高校伯克利分校的高校伯克利分校的DaganzoDaganzo教授及麻省理工学院的教授及麻省理工学院的SheffiSheffi教教授提出了随机性支配的理论。授提出了随机性支配的理论。随机性支配的前提是认为出行者对路段阻抗的估计值与实际随机性支配的前提是认为出行者对路段阻抗的估计值与实际值之间的差别是一个随机变量，出行者会在值之间的差别是一个随机变量，出行者会在“多条路径多条路径”中中选择，同一起迄点

7、的流量会通过不同的径路到达目的地。选择，同一起迄点的流量会通过不同的径路到达目的地。随机性支配理论和方法的提出，在拟合、反映现实交通网络随机性支配理论和方法的提出，在拟合、反映现实交通网络实际的进程中又推动了一大步。实际的进程中又推动了一大步。交通配流的发展阶段路网上的拥挤性、路径选择的随机性、交通需求的动态性是路网上的拥挤性、路径选择的随机性、交通需求的动态性是同时存在并交互作用的，其机理是纷繁困难的。同时存在并交互作用的，其机理是纷繁困难的。真正地符合路网实际状况，还有更重要更基本的交通需求的真正地符合路网实际状况，还有更重要更基本的交通需求的时变性（即动态性）须要反映出来。时变性（即动态

8、性）须要反映出来。须要一种交通流支配方法能够将路网上交通流的拥挤性、路须要一种交通流支配方法能够将路网上交通流的拥挤性、路径选择的随机性、交通需求的时变性综合集成地刻画反映出径选择的随机性、交通需求的时变性综合集成地刻画反映出来，这是探讨交通问题的学者始终主动探究的问题。来，这是探讨交通问题的学者始终主动探究的问题。交通配流的发展阶段基基 本本 概概 念念(1)(1)将将现状状ODOD交交通通量量支支配配到到现状状交交通通网网络上上，以以分分析析目目前前交交通通网网络的的运运行行状状况况，假假如如有有某某些些路路段段的的交交通通量量观测值，还可可以以将将这些些观测值与与在在相相应路路段段的的支

9、支配配结果果进行行比比较，以以检验模模型的精度。型的精度。(2)(2)将将规划划年年ODOD交交通通量量预料料值支支配配到到现状状交交通通网网络上上，以以发觉对规划划年年的的交交通通需需求求来来说，现状状交交通通网网络的的缺缺陷陷，为交交通通网网络的的规划划设计供供应依据。依据。(3)(3)将将规划划年年ODOD交交通通量量预料料值支支配配到到规划划交交通通网网络上上，以以评价价交通网交通网络规划方案的合理性。划方案的合理性。交通流支配的几种模式（1）表表示示需需求求的的OD交交通通量量。在在拥拥挤挤的的城城市市道道路路网网中中通通常常接接受受高高峰峰期期OD交交通通量量，在在城城市市间间马马

10、路路网网中中通通常常接接受受年年平平均均日交通量（日交通量（AADT）的）的OD交通量；交通量；（2）路路网网定定义义，即即路路段段及及交交叉叉口口特特征征和和属属性性数数据据，同同时时还包括其时间还包括其时间流量函数；流量函数；（3）路段阻抗函数。）路段阻抗函数。交通流支配的基本数据从交通流支配的特点来说，可以分为两类从交通流支配的特点来说，可以分为两类:交通工具的运行线路固定类型和运行线路不固定类型。交通工具的运行线路固定类型和运行线路不固定类型。线路固定类型有公共交通网和轨道交通网，这些是集体线路固定类型有公共交通网和轨道交通网，这些是集体旅客运输；旅客运输；线路不固定类型有城市道路网、

11、马路网，这一般是指个线路不固定类型有城市道路网、马路网，这一般是指个体旅客运输或货物运输，这类网络中，车辆是自由选择体旅客运输或货物运输，这类网络中，车辆是自由选择运行径路的。运行径路的。交通阻抗（交通费用）交通阻抗或者称为路阻是交通流支配中常常提到的概念，交通阻抗或者称为路阻是交通流支配中常常提到的概念，也是一项重要指标，它干脆影响到交通流路径的选择和流也是一项重要指标，它干脆影响到交通流路径的选择和流量的支配。量的支配。道路阻抗在交通流支配中可以通过路阻函数来描述。道路阻抗在交通流支配中可以通过路阻函数来描述。所谓路阻函数是指路段行驶时间与路段交通负荷，交叉口所谓路阻函数是指路段行驶时间与

12、路段交通负荷，交叉口延误与交叉口负荷之间的关系。延误与交叉口负荷之间的关系。交通网络上的路阻（费用），应包含反映出行时间、出行交通网络上的路阻（费用），应包含反映出行时间、出行费用、平安、舒适程度、便捷性和准时性等等很多因素。费用、平安、舒适程度、便捷性和准时性等等很多因素。经过大量的理论分析和工程实践，人们得出影响路阻的主经过大量的理论分析和工程实践，人们得出影响路阻的主要因素是时间，因此出行时间常常被作为计量路阻的主要要因素是时间，因此出行时间常常被作为计量路阻的主要标准。标准。交通阻抗有两部分组成：路段上的阻抗、节点处的阻抗。交通阻抗有两部分组成：路段上的阻抗、节点处的阻抗。出行时间与流

13、量的关系比较困难，可以广义地表达为：出行时间与流量的关系比较困难，可以广义地表达为：即即路路段段a a上上的的费费用用 不不仅仅仅仅是是路路段段本本身身流流量量的的函函数数，而而且且是是整整个路网上流量个路网上流量V V的函数。的函数。对对于于马马路路网网而而言言，由由于于路路段段比比较较长长，大大部部分分出出行行时时间间是是在在路路段上而不是在交叉口上，费用和流量的关系可以简化为：段上而不是在交叉口上，费用和流量的关系可以简化为：即路段的费用只与该路段的流量及其特性相关。即路段的费用只与该路段的流量及其特性相关。路段阻抗美美国国道道路路局局(BPRBureauofpublicroad)开开发

14、的的函函数数，被被称称为BPR函数函数:：路段：路段 上的阻抗；上的阻抗；：零流阻抗，即路段：零流阻抗，即路段 上为空静状态时车辆自由行驶所需上为空静状态时车辆自由行驶所需 要的时间；要的时间；：路段：路段 上的交通量；上的交通量；：路段：路段 的实际通过实力，即单位时间内路段实际可通过的实际通过实力，即单位时间内路段实际可通过 的车辆数；的车辆数；：在在美美国国马马路路局局交交通通流流支支配配程程序序中中，这这两两个个参参数数的的取取值值分分别别为为 0.15 0.15、4 4。也可由实际数据用回来分析求得。也可由实际数据用回来分析求得。车辆在交通网络节点处主要指在交叉口处的阻抗。车辆在交通

15、网络节点处主要指在交叉口处的阻抗。交交叉叉口口阻阻抗抗与与交交叉叉口口的的型型式式，信信号号限限制制系系统统的的配配时时，交交叉叉口口的通过实力等因素有关。的通过实力等因素有关。在在城城市市交交通通网网络络的的实实际际出出行行时时间间中中，除除路路段段行行驶驶时时间间外外，交交叉叉口口延延误误占占有有较较大大的的比比重重，特特殊殊是是在在交交通通高高峰峰期期间间，交交叉叉口口拥挤堵塞比较严峻时，交叉口延误将超过路段行驶时间。拥挤堵塞比较严峻时，交叉口延误将超过路段行驶时间。节点阻抗1958年英国年英国TRRL探讨所的探讨所的F.V.Webster 等人依据排队论理论，等人依据排队论理论，提出了

16、一个计算交叉口延误的模型。该模型中主要包括两部分：提出了一个计算交叉口延误的模型。该模型中主要包括两部分：一部分是车辆到达率为固定均值时产生的正常相位延误即匀整一部分是车辆到达率为固定均值时产生的正常相位延误即匀整延误；延误；另一部分是车辆到达率随机波动时所产生的附加延误。另一部分是车辆到达率随机波动时所产生的附加延误。T T：信号周期长度；：信号周期长度；：进口道有效绿灯时间与信号周期长度之比，即绿信比；：进口道有效绿灯时间与信号周期长度之比，即绿信比；Q Q：进口道的交通流量；：进口道的交通流量；X X：饱和度，：饱和度，X=Q/S X=Q/S，S S为进口道通过实力。为进口道通过实力。交

17、通平衡问题Wardrop提出的第一原理定义：提出的第一原理定义：在在道道路路的的利利用用者者都都精精确确知知道道网网络络的的交交通通状状态态并并选选择择最最短短径径路路时时，网网络络将将会会达达到到平平衡衡状状态态。在在考考虑虑拥拥挤挤对对行行驶驶时时间间影影响响的的网网络络中中，当当网网络络达达到到平平衡衡状状态态时时，每每个个OD对对的的各各条条被被运运用用的的径径路路具具有有相相等等而而且且最最小小的的行行驶驶时时间间；没没有有被被运运用用的的径径路路的的行驶时间大于或等于最小行驶时间。行驶时间大于或等于最小行驶时间。这这条条定定义义通通常常简简称称为为Wardrop平平衡衡，在在实实际

18、际交交通通流流支支配配中中也也称为用户均衡称为用户均衡(UE,UserEquilibrium)或用户最优。或用户最优。Wardrop提出的其次原理：提出的其次原理：在在系系统统平平衡衡条条件件下下，拥拥挤挤的的路路网网上上交交通通流流应应当当依依据据平平均均或或总的出行成本最小为依据来支配。总的出行成本最小为依据来支配。Wardrop其其次次原原理理，在在实实际际交交通通流流支支配配中中也也称称为为系系统统最最优优原理（原理（SO，SystemOptimization）。）。第一原理主要是建立每个道路利用者使其自身出行成本第一原理主要是建立每个道路利用者使其自身出行成本（时间）最小化的行为模型

19、，而其次原理则是旨在使交通（时间）最小化的行为模型，而其次原理则是旨在使交通流在最小出行成本方向上支配，从而达到出行成本最小的流在最小出行成本方向上支配，从而达到出行成本最小的系统平衡。系统平衡。其次个原理作为一个设计原理，是面对交通管理工程师的。其次个原理作为一个设计原理，是面对交通管理工程师的。在实际交通中，人们更期望交通流能够依据在实际交通中，人们更期望交通流能够依据Wardrop第一第一原理，即用户平衡的近似解来支配。原理，即用户平衡的近似解来支配。例子：设OD之间交通量为q=2000辆，有两条路径a与b。路径a行驶时间短，但是通行实力小，路径b行驶时间长，但通行实力大。假设各自的行驶

20、时间（分钟）与流量的关系是：依依据据Wardrop平平衡衡第第一一原原理理的的定定义义，很很简简洁洁建建立立下下列列的的方方程组：程组：则有：则有：明显明显只有在非负解时才有意义，即只有在非负解时才有意义，即也就是说，当也就是说，当OD交通量小于交通量小于250时，时，则，则即全部即全部OD都沿着路径都沿着路径a走行。走行。当当OD交交通通量量大大于于250时时，两两条条径径路路上上都都有有确确定定数数量量的的车车辆辆行行驶。当驶。当时，平衡流量为：时，平衡流量为：即平衡时两条径路的行驶时间均为即平衡时两条径路的行驶时间均为22分钟。分钟。q从从1952年年Wardrop提出道路网平衡的概念和

21、定义之后，如提出道路网平衡的概念和定义之后，如何求解何求解Wardrop平衡成了探讨者的重要课题。平衡成了探讨者的重要课题。q1956年，年，Beckmann等提出了描述平衡交通流支配的一个数等提出了描述平衡交通流支配的一个数学规划模型。学规划模型。q经过经过20年之后，即到年之后，即到1975年才由年才由LeBlanc等学者设计出了求等学者设计出了求解解Beckmann模型的算法（将模型的算法（将Frank-Wolfe算法用于求解该模型）算法用于求解该模型），从而形成了现在的好用解法。，从而形成了现在的好用解法。qWardrop原理原理Beckmann模型模型LeBlanc算法这些突破是交算

22、法这些突破是交通流支配问题探讨的重大进步，也是现在交通流支配问题的基通流支配问题探讨的重大进步，也是现在交通流支配问题的基础。础。对于完全满足对于完全满足WardropWardrop原理定义的平衡状态，则称为原理定义的平衡状态，则称为平衡支配方法。平衡支配方法。对于接受启发式方法或其它近似方法的支配模型，对于接受启发式方法或其它近似方法的支配模型，则称为非平衡支配方法。则称为非平衡支配方法。非平衡支配方法非平衡支配方法非非平平衡衡支支配配方方法法按按其其支支配配方方式式可可分分为为变变更更路路阻阻和和固固定定路路阻阻两两类，按支配形态可分为单路径与多路径两类。类，按支配形态可分为单路径与多路径

23、两类。分配形态分配形态 分配方式分配方式固定路阻固定路阻变化路阻变化路阻单路径单路径全有全无方法全有全无方法容量限制方法容量限制方法多路径多路径静态多路径方法静态多路径方法容量限制多路径方法容量限制多路径方法全有全无支配方法（all-or-nothing）将将OD交通量交通量T加载到路网的最短径路树上，从而加载到路网的最短径路树上，从而得到路网中各路段流量的过程。得到路网中各路段流量的过程。第第1步：初始化，使路网中全部路段的流量为步：初始化，使路网中全部路段的流量为0，并求出各路段自由流状态时的阻抗；并求出各路段自由流状态时的阻抗；第第2步：计算路网中每个动身地步：计算路网中每个动身地O到每

24、个目的地到每个目的地D的最短路径；的最短路径；第第3步：将步：将O、D间的间的OD交通量全部支配到相应交通量全部支配到相应的最短径路上。的最短径路上。该该方方法法是是在在全全有有全全无无支支配配方方法法的的基基础础上上，考考虑虑了了路路段段交交通通流流量量对对阻阻抗抗的的影影响响，进进而而依依据据道道路路阻阻抗抗的的变变更更来来调调整整路路网网交交通通量量的的支支配配，是是一一种种“变变更更路路阻阻”的的交交通通量支配方法。量支配方法。增增量量支支配配法法有有容容量量限限制制-增增量量加加载载支支配配、容容量量限限制制-迭迭代平衡支配两种形式。代平衡支配两种形式。增量支配法（increment

25、al assignment method）容量限制-增量加载支配方法q将将OD交通量分成若干份（等分或不等分）；交通量分成若干份（等分或不等分）；q循环地支配每一份的循环地支配每一份的OD交通量到网络中；交通量到网络中；q每次循环支配一份每次循环支配一份OD交通量到相应的最短路径交通量到相应的最短路径;每次循环均计算、更新各路段的行驶时间，然后按每次循环均计算、更新各路段的行驶时间，然后按更新后的行驶行驶时间重新计算最短径路；更新后的行驶行驶时间重新计算最短径路；q下一循环中按更新后的最短径路支配下一份下一循环中按更新后的最短径路支配下一份OD交通量。交通量。第第1步：初始化。分割步：初始化。

26、分割OD交通量：交通量：令令n=1。第第2步：计算、更新路段费用：步：计算、更新路段费用：第第3步：用全有全无支配法将第步：用全有全无支配法将第n个分割个分割OD交通量交通量支配支配到最短经路上。得到每条路段上的流量到最短经路上。得到每条路段上的流量。第第4步：计算步：计算。第第5步：假如步：假如n=N，则结束计算。反之，令，则结束计算。反之，令n=n+1返回第返回第2步。步。=当当分分割割数数N=1时时便便是是全全有有全全无无支支配配方方法法，当当N趋趋向向于于无无穷穷大时，该方法趋向于平衡支配法的结果。大时，该方法趋向于平衡支配法的结果。优点：优点：简简洁洁可可行行，精精确确度度可可以以依

27、依据据分分割割数数N的的大大小小来来调调整整；实实践践中常常被接受，且有比较成熟的商业软件可供运用。中常常被接受，且有比较成熟的商业软件可供运用。缺点：缺点：与与平平衡衡支支配配法法相相比比，照照旧旧是是一一种种近近似似方方法法；当当路路阻阻函函数数不不是是很很敏敏感感时时，会会将将过过多多的的交交通通量量支支配配到到某某些些通通行行实实力力很很小小的路段上。的路段上。增增量量加加载载和和迭迭代代平平衡衡支支配配形形式式的的原原理理基基本本是是相相同同的的。但但增增量量加加载载方方法法事事先先无无法法估估计计迭迭代代次次数数及及计计算算工工作作量量，对对于于较较困困难难的的网网络络，可可能能会

28、会因因为为个个别别路路段段的的迭迭代代精精度度无无法法满满足足要要求求而而使使迭代进入死循环，出现算法不收敛的状况。迭代进入死循环，出现算法不收敛的状况。美国联邦马路局对这一算法进行了改进：美国联邦马路局对这一算法进行了改进：事先设定一个最大迭代次数事先设定一个最大迭代次数N N（N4N4）当前迭代的阻抗值为前两次阻抗值的加权值当前迭代的阻抗值为前两次阻抗值的加权值平衡流解即取最终四次迭代的路段流量的平均值。平衡流解即取最终四次迭代的路段流量的平均值。容量限制-迭代平衡支配 第第1步步：初初始始化化。令令，用用全全有有全全无无方方法法将将OD矩矩阵阵加载到交通网络上，得到路段流量加载到交通网络

29、上，得到路段流量，设置迭代次数，设置迭代次数n=1。第第2步：计算步：计算。第第3步：加权平滑。计算步：加权平滑。计算，其中权值其中权值0.75和和0.25是由阅历得到的。是由阅历得到的。第第4步步：网网络络加加载载。依依据据路路段段的的阻阻抗抗值值，用用全全有有全全无无方方法法将将OD矩阵加载到交通网络上，得到路段流量矩阵加载到交通网络上，得到路段流量。第第5步：假如步：假如n=N，则结束计算。反之，令，则结束计算。反之，令n=n+1返回第返回第2步。步。迭代平均法（MSA算法）不不断断调调整整各各路路段段支支配配的的流流量量而而渐渐渐渐接接近近平平衡衡支支配配结结果果。每每步步循循环环中中

30、，依依据据各各路路段段支支配配到到的的流流量量进进行行一一次次全全有有全全无无支支配配，得得到到一组各路段的附加流量；一组各路段的附加流量；然然后后用用该该循循环环中中各各路路段段已已支支配配的的交交通通量量和和该该循循环环中中得得到到的的附附加加交通量进行加权平均，得到下一循环中的支配交通量；交通量进行加权平均，得到下一循环中的支配交通量；当当相相邻邻两两次次循循环环中中支支配配的的交交通通量量特特殊殊接接近近时时，即即停停止止运运算算，最最终一次循环中得到的交通量即为最终结果。终一次循环中得到的交通量即为最终结果。第第1步步：初初始始化化。令令。依依据据各各路路段段自自由由行行驶驶时时间间

31、进行全有全无支配，得到初始解进行全有全无支配，得到初始解。令迭代次数。令迭代次数n=1。第第2步步：更更新新路路段段的的阻阻抗抗，依依据据当当前前各各路路段段的的交交通通量量计计算算各各路段的路阻路段的路阻。第第3步步：依依据据路路段段行行驶驶阻阻抗抗将将OD交交通通量量进进行行全全有有全全无无支支配。得到各路段的附加交通量配。得到各路段的附加交通量。第第4步：更新路段流量。计算步：更新路段流量。计算第第5步步：假假如如连连续续两两次次迭迭代代的的结结果果相相差差不不大大，则则停停止止计计算算。即为最终支配结果。否则令即为最终支配结果。否则令n=n+1，返回第，返回第2步。步。连续平均法是介于

32、增量支配法和平衡支配法之间的连续平均法是介于增量支配法和平衡支配法之间的一种循环支配方法。一种循环支配方法。MSA方法是既简洁适用，又最接近于平衡支配法的方法是既简洁适用，又最接近于平衡支配法的一种支配方法；假如每步循环中一种支配方法；假如每步循环中1/n的严格依据数的严格依据数学规划模型取值时，即可得到平衡支配的解。学规划模型取值时，即可得到平衡支配的解。例题例题设设图图示示交交通通网网络络的的OD交交通通量量为为辆辆，各路径上的交通费用函数分别为：各路径上的交通费用函数分别为：试试用用全全有有全全无无支支配配法法、增增量量支支配配法法法法求求出出支配结果，并进行比较。支配结果，并进行比较。

33、ij123全有全无支配法全有全无支配法 由由路路段段费费用用函函数数可可知知，在在路路段段交交通通量量为为零零时时，路路径径1 1最最短短。依依据全有全无原则，交通量全部支配到路径据全有全无原则，交通量全部支配到路径1 1上，得到以下结果：上，得到以下结果：很明显，依据很明显，依据WardropWardrop原理，网络没有达到平衡状态。原理，网络没有达到平衡状态。此时路网总费用为此时路网总费用为50005000。增量支配法增量支配法(假定假定N=2)第第1次次支支配配：与与全全有有全全无无支支配配法法相相同同，路路径径1最最短短。得得到到下下面结果：面结果：第第2次支配：此时最短路径变为路径次

34、支配：此时最短路径变为路径2，得到下面结果：，得到下面结果：此时路网总费用为此时路网总费用为2750。平衡配流模型及算法平衡配流模型及算法Wardrop平衡支配原理的数学模型平衡支配原理的数学模型平衡支配模型的求解算法平衡支配模型的求解算法用户平衡支配模型用户平衡支配模型系统最优平衡支配模型系统最优平衡支配模型模型中所用变量和参数模型中所用变量和参数：路段：路段a上的交通流量；上的交通流量；：路段：路段a的交通阻抗，也称为行驶时间；的交通阻抗，也称为行驶时间；：路段：路段a的阻抗函数，也称为行驶时间函数；的阻抗函数，也称为行驶时间函数；：动身地为：动身地为r，目的地为，目的地为s的的OD间的第

35、间的第k条径路上的流量；条径路上的流量；：动身地为：动身地为r，目的地为，目的地为s的的OD间的第间的第k条径路的阻抗；条径路的阻抗；：动身地为：动身地为r，目的地为，目的地为s的的OD间的最短径路的阻抗；间的最短径路的阻抗；：路路段段-路路径径相相关关变变量量，即即0-1变变量量。假假如如路路段段a属属于于从从动动身身地地为为r目目的的地地为为s的的OD间间的的第第k条条路路径径，则则为为1，否则为否则为0。R：网络中动身地的集合；：网络中动身地的集合；S：网络中目的地的集合；：网络中目的地的集合；：动身地：动身地r和目的地和目的地s之间的全部径路的集合；之间的全部径路的集合；：动身地：动身

36、地r和目的地和目的地s之间的之间的OD交通量。交通量。Wardrop用户平衡准则用户平衡准则当交通网络达到平衡时，若有当交通网络达到平衡时，若有0，必有，必有说明假如从说明假如从r到到s有两条及其以上的路径被选中，那么它们的行有两条及其以上的路径被选中，那么它们的行驶时间最小且相等；驶时间最小且相等；若有若有=0，必有，必有说明假如某条从说明假如某条从r到到s的路径流量等于零，那么该路径的行驶时的路径流量等于零，那么该路径的行驶时间确定不小于被选中的路径的行驶时间。间确定不小于被选中的路径的行驶时间。基本守恒条件基本守恒条件（1）OD间各条路径上的交通量之和应等于间各条路径上的交通量之和应等于

37、OD交通总量交通总量（2）路段上的流量等于运用该路段的各条路径的流量之和）路段上的流量等于运用该路段的各条路径的流量之和（3）路径的阻抗等于组成该路径的各个路段的阻抗之和）路径的阻抗等于组成该路径的各个路段的阻抗之和（4）路径流量满足非负约束）路径流量满足非负约束用户平衡配流模型（用户平衡配流模型（Beckmann模型模型）用户均衡的概念用户均衡的概念如图所示，一个有两条路径（同时也是路段）、连接一如图所示，一个有两条路径（同时也是路段）、连接一个动身地和一个目的地的简洁交通网络，两个路段的阻个动身地和一个目的地的简洁交通网络，两个路段的阻抗函数分别是：抗函数分别是：t1=2+x1，t2=1+

38、2x2 OD量为量为q=5，分别求该网络的，分别求该网络的Beckmann平衡模型的解平衡模型的解和平衡状态的解。和平衡状态的解。RS12例题例题将阻抗函数带入模型，得：将阻抗函数带入模型，得：x1,x20s.t.x1+x2=5将将x1=5-x2带入目标函数并进行积分，得到下面微小值问题：带入目标函数并进行积分，得到下面微小值问题：min:Z(X)=1.5x12-9x1+30令令dZ/dx1=0解得解得x1*=3，x2*=2。求平衡状态的解求平衡状态的解依据依据Wardrop用户平衡原理：用户平衡原理：t1=t2x1+x2=5。求解这个方程组，很简洁求得求解这个方程组，很简洁求得x1=3，x2

39、=2。此时，此时，t1=t2=5。可见，可见，Beckmann模型的解和平衡状态的解完全相同。模型的解和平衡状态的解完全相同。等价性证明等价性证明依依据据非非线线性性规规划划理理论论，对对模模型型构构造造拉拉格格朗朗日日（Lagrange）函数：函数：其中，其中，是拉格朗日乘子，也是是拉格朗日乘子，也是rs之间的最小阻抗。之间的最小阻抗。依据非线性规划理论中的库恩依据非线性规划理论中的库恩塔克（塔克（Kuhn-TucherKuhn-Tucher）条）条件，拉格朗日函数在极值点必需满足下列条件：件，拉格朗日函数在极值点必需满足下列条件：库恩库恩塔克条件可以简化表示为：塔克条件可以简化表示为：对于

40、某个特定的连接对于某个特定的连接r和和s的路径，某路径的路径，某路径k的流量的流量 有两有两种可能：种可能：假如假如 ，得，得 ；假如假如 ，得，得 。求解方法求解方法步骤步骤1 1：初始化：依据：初始化：依据 ，进行，进行0-10-1交通流支配，交通流支配，得到各路段的流量得到各路段的流量 ；令；令n=1n=1；步骤步骤2：更新各路段的阻抗更新各路段的阻抗 ：步骤步骤3 3：找寻下一步迭代方向：依据更新后的：找寻下一步迭代方向：依据更新后的 ，再进行一次再进行一次0-10-1交通流支配，得到一组附加流量交通流支配，得到一组附加流量 ；步骤步骤4：确定迭代步长：用二分法求满足下式的：确定迭代步

41、长：用二分法求满足下式的步骤步骤5：确定新的迭代起点确定新的迭代起点 ；步骤步骤6：收敛性检验。假如满足：收敛性检验。假如满足：其其中中是是预预先先给给定定的的误误差差限限值值，则则就就是是要要求求的的平平衡衡解解，计算结束；否则，令计算结束；否则，令n=n+1，返回步骤，返回步骤2。系统最优模型系统最优模型该模型称为系统最优模型该模型称为系统最优模型SO(SystemOptimization)。Beckmann模型称为用户平衡模型模型称为用户平衡模型UE(UserEquilibrium)。系统最优支配与用户最优支配的关系：系统最优支配与用户最优支配的关系：对阻抗函数进行变换，令：对阻抗函数进

42、行变换，令：假如用假如用 作为阻抗函数，则此时用户最优支配模型完全可作为阻抗函数，则此时用户最优支配模型完全可以转换为系统最优支配模型，所以进行该阻抗函数下的用户以转换为系统最优支配模型，所以进行该阻抗函数下的用户最优支配，得到的解就是系统最优支配的解。最优支配，得到的解就是系统最优支配的解。131113131最短路径算法最短路径算法好的交通量支配法必需有一种好的最短路径计算方法好的交通量支配法必需有一种好的最短路径计算方法找寻找寻O-D对之间的最小费用路径，简称最短路径，是求解对之间的最小费用路径，简称最短路径，是求解交通网络平衡配流问题的核心。交通网络平衡配流问题的核心。任何一种交通量支配

43、法都是建立在最短路径的基础上；任何一种交通量支配法都是建立在最短路径的基础上；任何一个支配法中，最短路径的计算占据了全部计算时任何一个支配法中，最短路径的计算占据了全部计算时间的主要部分。至少有间的主要部分。至少有90%的计算时间花在最短路径的的计算时间花在最短路径的找寻上。找寻上。求解最短路径算法求解最短路径算法迪杰斯特拉迪杰斯特拉(Dijkstra)算法，即标点法（算法，即标点法（Label-correctingmethod）矩阵迭代法矩阵迭代法基本思想：基本思想：反复扫描网络的节点，在每次扫描中，该方法试图反复扫描网络的节点，在每次扫描中，该方法试图发觉从根节点到正在扫描的节点之间的、比

44、现有路发觉从根节点到正在扫描的节点之间的、比现有路径更好的路径，当从根节点到全部其它节点之间没径更好的路径，当从根节点到全部其它节点之间没有更好的路径时，算法就停止搜寻。有更好的路径时，算法就停止搜寻。标点法标点法在此算法中，为每一个节点设置两个记录：在此算法中，为每一个节点设置两个记录：（1）标号标号，表示沿着最短路径从根节点到节点，表示沿着最短路径从根节点到节点的最小的最小费用；费用；（2）紧前节点）紧前节点，表示沿着最短路径到达节点，表示沿着最短路径到达节点且最靠近且最靠近的节点。的节点。在每次扫描中，将紧前节点都记录下来，形成紧前节点在每次扫描中，将紧前节点都记录下来，形成紧前节点序列

45、，这是为了停止扫描时，能反馈地找出最短路径的序列，这是为了停止扫描时，能反馈地找出最短路径的轨迹。轨迹。检查列中包含正在和须要进一步检查的节点，驾驭节点被检查列中包含正在和须要进一步检查的节点，驾驭节点被检查的动态；检查的动态；标号列中记载各节点的标号；标号列中记载各节点的标号；紧前节点列中记载各节点的紧前节点，依据紧前节点列可紧前节点列中记载各节点的紧前节点，依据紧前节点列可以找到节点之间的最短路径；以找到节点之间的最短路径；每进行一步新的扫描，标号列、紧前节点列和检查列就要每进行一步新的扫描，标号列、紧前节点列和检查列就要更新一次，当检查列中不再有节点时，算法停止。更新一次，当检查列中不再

46、有节点时，算法停止。算法步骤：算法步骤：第一步：初始化，置全部标号为无穷大（或一个很大的正第一步：初始化，置全部标号为无穷大（或一个很大的正数），置全部的紧前节点为零，将根节点数），置全部的紧前节点为零，将根节点 放入检查列放入检查列中，并令中，并令 ；其其次次步步：从从检检查查列列中中任任选选一一个个节节点点，例例如如节节点点，扫扫描描全部从全部从节点动身只经过一条弧便可到达的节点，例如节点动身只经过一条弧便可到达的节点，例如节点，假如：节点，假如：则则更更新新节节点点上上的的标标号号，令令，是是从从节节点点到到节节点点的弧上的阻抗值。的弧上的阻抗值。假如上面式子不成立，则节点假如上面式子不

47、成立，则节点的标号不变。的标号不变。第三步：在变更节点第三步：在变更节点 的标号的同时，修改的标号的同时，修改 ，且将，且将 加入到检查列中（因为从节点加入到检查列中（因为从节点 动身还可能到达其它节点）动身还可能到达其它节点）。当从。当从 动身只经过一条弧便可到达的全部节点都被检查过动身只经过一条弧便可到达的全部节点都被检查过时，就从检查列中删除时，就从检查列中删除 节点。节点。第四步：当检查列中不再有节点时，算法停止。从根节点到第四步：当检查列中不再有节点时，算法停止。从根节点到其它随意节点的最短路径可通过反向搜寻最终的紧前节点序其它随意节点的最短路径可通过反向搜寻最终的紧前节点序列识别出

48、来。列识别出来。例：包含例：包含4条弧的简洁网络，其中根节点为条弧的简洁网络，其中根节点为1，弧上的数，弧上的数字表示弧的阻抗。字表示弧的阻抗。14231114第一步：全部节点的标号都置为第一步：全部节点的标号都置为 ，其紧前节点都置，其紧前节点都置为零。然后，节点为零。然后，节点1 1的标号变为的标号变为0 0，且把它放到检查列中。，且把它放到检查列中。其次步：从节点其次步：从节点1 1动身可以到达节点动身可以到达节点2 2和和4 4，先考虑节点，先考虑节点4 4，因为，因为 ，则节点，则节点4 4的标号变为的标号变为4 4，且，且被放入到检查列中。被放入到检查列中。迭迭代代检查检查列列节点

49、节点1节点节点2节点节点3节点节点4节点节点1节点节点2节点节点3节点节点4000000110400011,4201401012,43012401213,44012301234501230123标号列标号列紧前节点列紧前节点列基本思想：基本思想：（1 1）是借助距离（路权）矩阵的迭代运算来求解）是借助距离（路权）矩阵的迭代运算来求解最短路权的算法。最短路权的算法。（2 2）该方法能一次获得随意两点之间的最短路权）该方法能一次获得随意两点之间的最短路权矩阵。矩阵。矩阵迭代法矩阵迭代法算法步骤：算法步骤：（1 1）首先构造距离矩阵（以距离为权的权矩阵）首先构造距离矩阵（以距离为权的权矩阵）（2 2

50、）矩阵给出了节点间只经过一步（一条边）到达某一）矩阵给出了节点间只经过一步（一条边）到达某一点的最短距离点的最短距离（3 3）对距离矩阵进行如下的迭代运算，便可以得到经过）对距离矩阵进行如下的迭代运算，便可以得到经过两步达到某一点的最短距离：两步达到某一点的最短距离：k=1,2,3,nn：网络节点数；：网络节点数；*：矩阵逻辑运算符；：矩阵逻辑运算符；dik，dkj：距离矩阵：距离矩阵D中的相应元素。中的相应元素。例题：用矩阵迭代法计算下图所示路网随意节点之间的最短例题：用矩阵迭代法计算下图所示路网随意节点之间的最短阻抗值。阻抗值。123695847222222222211（1 1）距离矩阵如