交通流分配分解.pptx

交通流分配交通流分配（Traffic Assignment）交通流分配是本课程的重点和难点之一。最优化理论、图论、交通流分配是本课程的重点和难点之一。最优化理论、图论、计算机技术的发展，为交通流分配模型和算法的研究及开发计算机技术的发展，为交通流分配模型和算法的研究及开发提供了坚实的基础，通过几十年的发展，交通流分配是交通提供了坚实的基础，通过几十年的发展，交通流分配是交通规划诸问题中被国内外学者研究得最深入、取得研究成果最规划诸问题中被国内外学者研究得最深入、取得研究成果最多的部分。多的部分。本章主要讲述交通流分配的基本概念、基本原理和基本方法，本章主要讲述交通流分配的基本概念、基本原理和基本方法，交通流分配的非平衡分配、平衡分配的模型和算法等内容。交通流分配的非平衡分配、平衡分配的模型和算法等内容。概概 述述两种机制相互作用直至平衡：两种机制相互作用直至平衡：一种机制是：一种机制是：各种车辆试图通过在网络上选择最佳行驶路线各种车辆试图通过在网络上选择最佳行驶路线来达到自身出行费用最小的目标；来达到自身出行费用最小的目标；另一种机制是：另一种机制是：道路上的车流量越大，用户遇到的阻力即对道路上的车流量越大，用户遇到的阻力即对应的行驶阻抗越高。应的行驶阻抗越高。用一定的模型来描述这两种机制及其相互作用，并求解网络用一定的模型来描述这两种机制及其相互作用，并求解网络上交通流量在平衡状态下的合理分布，即交通流分配。上交通流量在平衡状态下的合理分布，即交通流分配。就是将预测得出的就是将预测得出的OD交通量，根据已知的道路网交通量，根据已知的道路网描述，按照一定的规则符合实际地分配到路网中描述，按照一定的规则符合实际地分配到路网中的各条道路上去，进而求出路网中各路段的交通的各条道路上去，进而求出路网中各路段的交通流量、所产生的流量、所产生的OD费用矩阵，并籍此对城市交通费用矩阵，并籍此对城市交通网络的使用状况做出分析和评价。网络的使用状况做出分析和评价。交通配流路径路径n路径路径1路径路径2ODOD最初的交通流分配研究，多采用最初的交通流分配研究，多采用全有全无全有全无方法。方法。该方法处理的是非常理想化的城市交通网络，即假设该方法处理的是非常理想化的城市交通网络，即假设网络上没有交通拥挤，路阻是固定不变的，一个网络上没有交通拥挤，路阻是固定不变的，一个OD对间的流量都分配在对间的流量都分配在“一条径路一条径路”，即最短径路上。，即最短径路上。但对于既有的城市内部拥挤的交通网络，该方法的结但对于既有的城市内部拥挤的交通网络，该方法的结果与网络实际情况出入甚大。果与网络实际情况出入甚大。交通配流的发展阶段在在1952年，著名交通问题专家年，著名交通问题专家Wardrop提出了提出了网络平衡分配网络平衡分配的第一、第二定理的第一、第二定理，人们开始采用系统分析方法和平衡分析，人们开始采用系统分析方法和平衡分析方法来研究交通拥挤时的交通流分配。方法来研究交通拥挤时的交通流分配。确定性的平衡配流：其前提是假设出行者能够精确计算出每确定性的平衡配流：其前提是假设出行者能够精确计算出每条径路的阻抗，从而能作出完全正确的选择决定，且每个出条径路的阻抗，从而能作出完全正确的选择决定，且每个出行者的计算能力和水平是相同的。行者的计算能力和水平是相同的。现实中出行者对路段阻抗的掌握只能是估计而得。对同一路现实中出行者对路段阻抗的掌握只能是估计而得。对同一路段，不同出行者的估计值不会完全相同，因为出行者的计算段，不同出行者的估计值不会完全相同，因为出行者的计算能力和水平是各异的。能力和水平是各异的。交通配流的发展阶段在在1977年，对交通流分配理论研究最积极、活跃的美国加州年，对交通流分配理论研究最积极、活跃的美国加州大学伯克利分校的大学伯克利分校的Daganzo教授及麻省理工学院的教授及麻省理工学院的Sheffi教授教授提出了随机性分配的理论。提出了随机性分配的理论。随机性分配的前提是认为出行者对路段阻抗的估计值与实际随机性分配的前提是认为出行者对路段阻抗的估计值与实际值之间的差别是一个随机变量，出行者会在值之间的差别是一个随机变量，出行者会在“多条路径多条路径”中中选择，同一起迄点的流量会通过不同的径路到达目的地。选择，同一起迄点的流量会通过不同的径路到达目的地。随机性分配理论和方法的提出，在拟合、反映现实交通网络随机性分配理论和方法的提出，在拟合、反映现实交通网络实际的进程中又推进了一大步。实际的进程中又推进了一大步。交通配流的发展阶段路网上的拥挤性、路径选择的随机性、交通需求的动态性是路网上的拥挤性、路径选择的随机性、交通需求的动态性是同时存在并交互作用的，其机理是纷繁复杂的。同时存在并交互作用的，其机理是纷繁复杂的。真正地符合路网实际情况，还有更重要更基本的交通需求的真正地符合路网实际情况，还有更重要更基本的交通需求的时变性（即动态性）需要反映出来。时变性（即动态性）需要反映出来。需要一种交通流分配方法能够将路网上交通流的拥挤性、路需要一种交通流分配方法能够将路网上交通流的拥挤性、路径选择的随机性、交通需求的时变性综合集成地刻画反映出径选择的随机性、交通需求的时变性综合集成地刻画反映出来，这是研究交通问题的学者一直积极探索的问题。来，这是研究交通问题的学者一直积极探索的问题。交通配流的发展阶段基基 本本 概概 念念(1)(1)将将现现状状ODOD交交通通量量分分配配到到现现状状交交通通网网络络上上，以以分分析析目目前前交交通通网网络络的的运运行行状状况况，如如果果有有某某些些路路段段的的交交通通量量观观测测值值，还还可可以以将将这这些些观观测测值值与与在在相相应应路路段段的的分分配配结结果果进进行行比比较较，以以检检验验模模型的精度。型的精度。(2)(2)将将规规划划年年ODOD交交通通量量预预测测值值分分配配到到现现状状交交通通网网络络上上，以以发发现现对对规规划划年年的的交交通通需需求求来来说说，现现状状交交通通网网络络的的缺缺陷陷，为为交交通通网网络的规划设计提供依据。络的规划设计提供依据。(3)将规划年将规划年OD交通量预测值分配到规划交通网络上，以评交通量预测值分配到规划交通网络上，以评价交通网络规划方案的合理性。价交通网络规划方案的合理性。交通流分配的几种模式（1）表表示示需需求求的的OD交交通通量量。在在拥拥挤挤的的城城市市道道路路网网中中通通常常采采用用高高峰峰期期OD交交通通量量，在在城城市市间间公公路路网网中中通通常常采采用用年年平平均均日交通量（日交通量（AADT）的）的OD交通量；交通量；（2）路路网网定定义义，即即路路段段及及交交叉叉口口特特征征和和属属性性数数据据，同同时时还包括其时间还包括其时间流量函数；流量函数；（3）路段阻抗函数。）路段阻抗函数。交通流分配的基本数据从交通流分配的特点来说，可以分为两类从交通流分配的特点来说，可以分为两类:交通工具的交通工具的运行线路固定类型运行线路固定类型和和运行线路不固定运行线路不固定类型。类型。线路固定类型有公共交通网和轨道交通网，这些是集体线路固定类型有公共交通网和轨道交通网，这些是集体旅客运输；旅客运输；线路不固定类型有城市道路网、公路网，这一般是指个线路不固定类型有城市道路网、公路网，这一般是指个体旅客运输或货物运输，这类网络中，车辆是自由选择体旅客运输或货物运输，这类网络中，车辆是自由选择运行径路的。运行径路的。交通阻抗（交通费用）交通阻抗或者称为路阻是交通流分配中经常提到的概念，交通阻抗或者称为路阻是交通流分配中经常提到的概念，也是一项重要指标，它直接影响到交通流路径的选择和流也是一项重要指标，它直接影响到交通流路径的选择和流量的分配。量的分配。道路阻抗在交通流分配中可以通过道路阻抗在交通流分配中可以通过路阻函数路阻函数来描述。来描述。所谓所谓路阻函数路阻函数是指路段行驶时间与路段交通负荷，交叉口是指路段行驶时间与路段交通负荷，交叉口延误与交叉口负荷之间的关系。延误与交叉口负荷之间的关系。交通网络上的路阻（费用），应包含反映出行时间、出行交通网络上的路阻（费用），应包含反映出行时间、出行费用、安全、舒适程度、便捷性和准时性等等许多因素。费用、安全、舒适程度、便捷性和准时性等等许多因素。经过大量的理论分析和工程实践，人们得出影响路阻的主经过大量的理论分析和工程实践，人们得出影响路阻的主要因素是时间，因此要因素是时间，因此出行时间出行时间常常被作为计量路阻的主要常常被作为计量路阻的主要标准。标准。交通阻抗有两部分组成交通阻抗有两部分组成：路段上的阻抗、节点处的阻抗。路段上的阻抗、节点处的阻抗。出行出行时间与流量的关系比较复杂，可以广义地表达为：时间与流量的关系比较复杂，可以广义地表达为：即路段即路段a上的费用上的费用 不仅仅是路段本身流量的函数，而且是整不仅仅是路段本身流量的函数，而且是整个路网上流量个路网上流量V的函数。的函数。对对于于公公路路网网而而言言，由由于于路路段段比比较较长长，大大部部分分出出行行时时间间是是在在路路段上而不是在交叉口上，费用和流量的关系可以简化为：段上而不是在交叉口上，费用和流量的关系可以简化为：即路段的费用只与该路段的流量及其特性相关。即路段的费用只与该路段的流量及其特性相关。路段阻抗美美国国道道路路局局(BPRBureauofpublicroad)开开发发的的函函数数，被被称称为为BPR函数函数:：路段：路段 上的阻抗；上的阻抗；：零流阻抗，即路段：零流阻抗，即路段 上为空静状态时车辆自由行驶所需上为空静状态时车辆自由行驶所需 要的时间；要的时间；：路段：路段 上的交通量；上的交通量；：路段：路段 的实际通过能力，即单位时间内路段实际可通过的实际通过能力，即单位时间内路段实际可通过 的车辆数；的车辆数；：在美国公路局交通流分配程序中，这两个参数的取值分别：在美国公路局交通流分配程序中，这两个参数的取值分别为为0.15、4。也可由实际数据用回归分析求得。也可由实际数据用回归分析求得。车辆在交通网络节点处主要指在交叉口处的阻抗。车辆在交通网络节点处主要指在交叉口处的阻抗。交叉口阻抗与交叉口的型式，信号控制系统的配时，交叉口交叉口阻抗与交叉口的型式，信号控制系统的配时，交叉口的通过能力等因素有关。的通过能力等因素有关。在城市交通网络的实际出行时间中，除路段行驶时间外，交在城市交通网络的实际出行时间中，除路段行驶时间外，交叉口延误占有较大的比重，特别是在交通高峰期间，交叉口叉口延误占有较大的比重，特别是在交通高峰期间，交叉口拥挤阻塞比较严重时，交叉口延误将超过路段行驶时间。拥挤阻塞比较严重时，交叉口延误将超过路段行驶时间。节点阻抗1958年英国年英国TRRL研究所的研究所的F.V.Webster 等人根据排队论理论，等人根据排队论理论，提出了一个计算交叉口延误的模型。该模型中主要包括两部分：提出了一个计算交叉口延误的模型。该模型中主要包括两部分：一部分是车辆到达率为固定均值时产生的正常相位延误即均匀一部分是车辆到达率为固定均值时产生的正常相位延误即均匀延误；延误；另一部分是车辆到达率随机波动时所产生的附加延误。另一部分是车辆到达率随机波动时所产生的附加延误。T T：信号周期长度；：信号周期长度；：进口道有效绿灯时间与信号周期长度之比，即绿信比；进口道有效绿灯时间与信号周期长度之比，即绿信比；Q Q：进口道的交通流量；：进口道的交通流量；X X：饱和度，：饱和度，X=Q/S X=Q/S，S S为进口道通过能力。为进口道通过能力。交通平衡问题Wardrop提出的第一原理定义：提出的第一原理定义：在在道道路路的的利利用用者者都都确确切切知知道道网网络络的的交交通通状状态态并并选选择择最最短短径径路路时时，网网络络将将会会达达到到平平衡衡状状态态。在在考考虑虑拥拥挤挤对对行行驶驶时时间间影影响响的的网网络络中中，当当网网络络达达到到平平衡衡状状态态时时，每每个个OD对对的的各各条条被被使使用用的的径径路路具具有有相相等等而而且且最最小小的的行行驶驶时时间间；没没有有被被使使用用的的径径路路的的行驶时间大于或等于最小行驶时间。行驶时间大于或等于最小行驶时间。这条定义通常简称为这条定义通常简称为Wardrop平衡，在实际交通流分配中也平衡，在实际交通流分配中也称为用户均衡称为用户均衡(UE,UserEquilibrium)或用户最优。或用户最优。Wardrop提出的第二原理：提出的第二原理：在系统平衡条件下，拥挤的路网上交通流应该按照平均或在系统平衡条件下，拥挤的路网上交通流应该按照平均或总的出行成本最小为依据来分配。总的出行成本最小为依据来分配。Wardrop第二原理，在实际交通流分配中也称为系统最优第二原理，在实际交通流分配中也称为系统最优原理（原理（SO，SystemOptimization）。）。第一原理主要是建立每个道路利用者使其自身出行成本第一原理主要是建立每个道路利用者使其自身出行成本（时间）最小化的行为模型，而第二原理则是旨在使交通（时间）最小化的行为模型，而第二原理则是旨在使交通流在最小出行成本方向上分配，从而达到出行成本最小的流在最小出行成本方向上分配，从而达到出行成本最小的系统平衡。系统平衡。第二个原理作为一个设计原理，是面向交通管理工程师的。第二个原理作为一个设计原理，是面向交通管理工程师的。在实际交通中，人们更期望交通流能够按照在实际交通中，人们更期望交通流能够按照Wardrop第一第一原理，即用户平衡的近似解来分配。原理，即用户平衡的近似解来分配。例子：设设OD之间交通量为之间交通量为q=2000辆，有两条路径辆，有两条路径a与与b。路径。路径a行驶行驶时间短，但是通行能力小，路径时间短，但是通行能力小，路径b行驶时间长，但通行能力行驶时间长，但通行能力大。假设各自的行驶时间（分钟）与流量的关系是：大。假设各自的行驶时间（分钟）与流量的关系是：根根据据Wardrop平平衡衡第第一一原原理理的的定定义义，很很容容易易建建立立下下列列的的方方程组：程组：则有：则有：显然显然只有在非负解时才有意义，即只有在非负解时才有意义，即也就是说，当也就是说，当OD交通量小于交通量小于250时，时，则，则即所有即所有OD都沿着路径都沿着路径a走行。走行。当当OD交交通通量量大大于于250时时，两两条条径径路路上上都都有有一一定定数数量量的的车车辆辆行行驶。当驶。当时，平衡流量为：时，平衡流量为：即平衡时两条径路的行驶时间均为即平衡时两条径路的行驶时间均为22分钟。分钟。q从从1952年年Wardrop提出道路网平衡的概念和定义之后，如提出道路网平衡的概念和定义之后，如何求解何求解Wardrop平衡成了研究者的重要课题。平衡成了研究者的重要课题。q1956年，年，Beckmann等提出了描述平衡交通流分配的一个数等提出了描述平衡交通流分配的一个数学规划模型。学规划模型。q经过经过20年之后，即到年之后，即到1975年才由年才由LeBlanc等学者设计出了求等学者设计出了求解解Beckmann模型的算法（将模型的算法（将Frank-Wolfe算法用于求解该模型）算法用于求解该模型），从而形成了现在的实用解法。，从而形成了现在的实用解法。Wardrop原理原理Beckmann模型模型LeBlanc算法这些突破是交通算法这些突破是交通流分配问题研究的重大进步，也是现在交通流分配问题的基础。流分配问题研究的重大进步，也是现在交通流分配问题的基础。对于完全满足对于完全满足Wardrop原理定义的平衡状态，则称原理定义的平衡状态，则称为平衡分配方法。为平衡分配方法。对于采用启发式方法或其它近似方法的分配模型，对于采用启发式方法或其它近似方法的分配模型，则称为非平衡分配方法。则称为非平衡分配方法。非平衡分配方法非平衡分配方法非非平平衡衡分分配配方方法法按按其其分分配配方方式式可可分分为为变变化化路路阻阻和和固固定定路路阻阻两两类，按分配形态可分为单路径与多路径两类。类，按分配形态可分为单路径与多路径两类。分配形态分配形态 分配方式分配方式固定路阻固定路阻变化路阻变化路阻单路径单路径全有全无方法全有全无方法容量限制方法容量限制方法多路径多路径静态多路径方法静态多路径方法容量限制多路径方法容量限制多路径方法全有全无分配方法（all-or-nothing）将将OD交通量交通量T加载到路网的最短径路树上，从而加载到路网的最短径路树上，从而得到路网中各路段流量的过程。得到路网中各路段流量的过程。第第1步：步：初始化，使路网中所有路段的流量为初始化，使路网中所有路段的流量为0，并求出各路段自由流状态时的阻抗；并求出各路段自由流状态时的阻抗；第第2步：步：计算路网中每个出发地计算路网中每个出发地O到每个目的地到每个目的地D的最短路径；的最短路径；第第3步：步：将将O、D间的间的OD交通量全部分配到相应交通量全部分配到相应的最短径路上。的最短径路上。该该方方法法是是在在全全有有全全无无分分配配方方法法的的基基础础上上，考考虑虑了了路路段段交交通通流流量量对对阻阻抗抗的的影影响响，进进而而根根据据道道路路阻阻抗抗的的变变化化来来调调整整路路网网交交通通量量的的分分配配，是是一一种种“变变化化路路阻阻”的的交交通通量分配方法。量分配方法。增量分配法有增量分配法有容量限制容量限制-增量加载分配增量加载分配、容量限制容量限制-迭迭代平衡分配代平衡分配两种形式。两种形式。增量分配法（incremental assignment method）容量限制-增量加载分配方法q将将OD交通量分成若干份（等分或不等分）；交通量分成若干份（等分或不等分）；q循环地分配每一份的循环地分配每一份的OD交通量到网络中；交通量到网络中；q每次循环分配一份每次循环分配一份OD交通量到相应的最短路径交通量到相应的最短路径;每次循环均计算、更新各路段的行驶时间，然后每次循环均计算、更新各路段的行驶时间，然后按更新后的行驶行驶时间重新计算最短径路；按更新后的行驶行驶时间重新计算最短径路；q下一循环中按更新后的最短径路分配下一份下一循环中按更新后的最短径路分配下一份OD交通量。交通量。第第1步：初始化。分割步：初始化。分割OD交通量：交通量：令令n=1。第第2步：计算、更新路段费用：步：计算、更新路段费用：第第3步：用全有全无分配法将第步：用全有全无分配法将第n个分割个分割OD交通量交通量分配分配到最短经路上。得到每条路段上的流量到最短经路上。得到每条路段上的流量。第第4步：计算步：计算。第第5步：如果步：如果n=N，则结束计算。反之，令，则结束计算。反之，令n=n+1返回第返回第2步。步。=当当分分割割数数N=1时时便便是是全全有有全全无无分分配配方方法法，当当N趋趋向向于于无无穷穷大时，该方法趋向于平衡分配法的结果。大时，该方法趋向于平衡分配法的结果。优点：优点：简单可行，精确度可以根据分割数简单可行，精确度可以根据分割数N的大小来调整；实践的大小来调整；实践中经常被采用，且有比较成熟的商业软件可供使用。中经常被采用，且有比较成熟的商业软件可供使用。缺点：缺点：与平衡分配法相比，仍然是一种近似方法；当路阻函数不与平衡分配法相比，仍然是一种近似方法；当路阻函数不是很敏感时，会将过多的交通量分配到某些通行能力很小是很敏感时，会将过多的交通量分配到某些通行能力很小的路段上。的路段上。增增量量加加载载和和迭迭代代平平衡衡分分配配形形式式的的原原理理基基本本是是相相同同的的。但但增增量量加加载载方方法法事事先先无无法法估估计计迭迭代代次次数数及及计计算算工工作作量量，对对于于较较复复杂杂的的网网络络，可可能能会会因因为为个个别别路路段段的的迭迭代代精精度度无无法法满满足足要要求求而而使使迭代进入死循环，出现算法不收敛的情况。迭代进入死循环，出现算法不收敛的情况。美国联邦公路局对这一算法进行了改进：美国联邦公路局对这一算法进行了改进：q 事先设定一个最大迭代次数事先设定一个最大迭代次数N（N4）q 当前迭代的阻抗值为前两次阻抗值的加权值当前迭代的阻抗值为前两次阻抗值的加权值平衡流解即取最后四次迭代的路段流量的平均值。平衡流解即取最后四次迭代的路段流量的平均值。容量限制-迭代平衡分配 第第1步步：初初始始化化。令令，用用全全有有全全无无方方法法将将OD矩矩阵阵加载到交通网络上，得到路段流量加载到交通网络上，得到路段流量，设置迭代次数，设置迭代次数n=1。第第2步：计算步：计算。第第3步：加权平滑。计算步：加权平滑。计算，其中权值其中权值0.75和和0.25是由经验得到的。是由经验得到的。第第4步：网络加载。根据路段的阻抗值步：网络加载。根据路段的阻抗值，用全有全无方法将，用全有全无方法将OD矩阵加载到交通网络上，得到路段流量矩阵加载到交通网络上，得到路段流量。第第5步：如果步：如果n=N，则结束计算。反之，令，则结束计算。反之，令n=n+1返回第返回第2步。步。迭代平均法（MSA算法）不不断断调调整整各各路路段段分分配配的的流流量量而而逐逐渐渐接接近近平平衡衡分分配配结结果果。每每步步循循环环中中，根根据据各各路路段段分分配配到到的的流流量量进进行行一一次次全全有有全全无无分分配配，得得到到一组各路段的附加流量；一组各路段的附加流量；然后用该循环中各路段已分配的交通量和该循环中得到的附加然后用该循环中各路段已分配的交通量和该循环中得到的附加交通量进行加权平均，得到下一循环中的分配交通量；交通量进行加权平均，得到下一循环中的分配交通量；当相邻两次循环中分配的交通量十分接近时，即停止运算，最当相邻两次循环中分配的交通量十分接近时，即停止运算，最后一次循环中得到的交通量即为最终结果。后一次循环中得到的交通量即为最终结果。第第1步步：初初始始化化。令令。根根据据各各路路段段自自由由行行驶驶时时间间进行全有全无分配，得到初始解进行全有全无分配，得到初始解。令迭代次数。令迭代次数n=1。第第2步步：更更新新路路段段的的阻阻抗抗，按按照照当当前前各各路路段段的的交交通通量量计计算算各各路段的路阻路段的路阻。第第3步步：按按照照路路段段行行驶驶阻阻抗抗将将OD交交通通量量进进行行全全有有全全无无分分配。得到各路段的附加交通量配。得到各路段的附加交通量。第第4步：步：更新路段流量。计算更新路段流量。计算第第5步：步：如果连续两次迭代的结果相差不大，则停止计算。如果连续两次迭代的结果相差不大，则停止计算。即为最终分配结果。否则令即为最终分配结果。否则令n=n+1，返回第，返回第2步。步。连续平均法是介于增量分配法和平衡分配法之间的连续平均法是介于增量分配法和平衡分配法之间的一种循环分配方法。一种循环分配方法。MSA方方法是既简单适用，又最接近于平衡分配法法是既简单适用，又最接近于平衡分配法的一种分配方法；如果每步循环中的一种分配方法；如果每步循环中1/n的严格按照的严格按照数学规划模型取值时，即可得到平衡分配的解。数学规划模型取值时，即可得到平衡分配的解。例题例题设设图图示示交交通通网网络络的的ODOD交交通通量量为为 辆辆，各各路路径径上上的的交通费用函数分别为：交通费用函数分别为：试用全有全无分配法、增量分配法法求出分配结果，并试用全有全无分配法、增量分配法法求出分配结果，并进行比较。进行比较。ij123全有全无分配法全有全无分配法 由由路路段段费费用用函函数数可可知知，在在路路段段交交通通量量为为零零时时，路路径径1 1最最短短。根根据全有全无原则，交通量全部分配到路径据全有全无原则，交通量全部分配到路径1 1上，得到以下结果：上，得到以下结果：很明显，根据很明显，根据WardropWardrop原理，网络没有达到平衡状态。原理，网络没有达到平衡状态。此时路网总费用为此时路网总费用为50005000。增量分配法增量分配法(假定假定N=2)第第1次次分分配配：与与全全有有全全无无分分配配法法相相同同，路路径径1最最短短。得得到到下下面结果：面结果：第第2次分配：此时最短路径变为路径次分配：此时最短路径变为路径2，得到下面结果：，得到下面结果：此时路网总费用为此时路网总费用为2750。平衡配流模型及算法平衡配流模型及算法Wardrop平衡分配原理的数学模型平衡分配原理的数学模型平衡分配模型的求解算法平衡分配模型的求解算法用户平衡分配模型用户平衡分配模型系统最优平衡分配模型系统最优平衡分配模型模型中所用变量和参数模型中所用变量和参数：路段：路段a上的交通流量；上的交通流量；：路段：路段a的交通阻抗，也称为行驶时间；的交通阻抗，也称为行驶时间；：路段：路段a的阻抗函数，也称为行驶时间函数；的阻抗函数，也称为行驶时间函数；：出发地为：出发地为r，目的地为，目的地为s的的OD间的第间的第k条径路上的流量；条径路上的流量；：出发地为：出发地为r，目的地为，目的地为s的的OD间的第间的第k条径路的阻抗；条径路的阻抗；：出发地为：出发地为r，目的地为，目的地为s的的OD间的最短径路的阻抗；间的最短径路的阻抗；：路路段段-路路径径相相关关变变量量，即即0-1变变量量。如如果果路路段段a属属于于从从出出发发地地为为r目目的的地地为为s的的OD间间的的第第k条条路路径径，则则为为1，否否则为则为0。R：网络中出发地的集合；：网络中出发地的集合；S：网络中目的地的集合；：网络中目的地的集合；：出发地：出发地r和目的地和目的地s之间的所有径路的集合；之间的所有径路的集合；：出发地：出发地r和目的地和目的地s之间的之间的OD交通量。交通量。Wardrop用户平衡准则用户平衡准则当交通网络达到平衡时，若有当交通网络达到平衡时，若有0，必有，必有说明如果从说明如果从r到到s有两条及其以上的路径被选中，那么它们的行有两条及其以上的路径被选中，那么它们的行驶时间最小且相等；驶时间最小且相等；若有若有=0，必有，必有说明如果某条从说明如果某条从r到到s的路径流量等于零，那么该路径的行驶时的路径流量等于零，那么该路径的行驶时间一定不小于被选中的路径的行驶时间。间一定不小于被选中的路径的行驶时间。基本守恒条件基本守恒条件（1）OD间各条路径上的交通量之和应等于间各条路径上的交通量之和应等于OD交通总量交通总量（2）路段上的流量等于使用该路段的各条路径的流量之和）路段上的流量等于使用该路段的各条路径的流量之和（3）路径的阻抗等于组成该路径的各个路段的阻抗之和）路径的阻抗等于组成该路径的各个路段的阻抗之和（4 4）路径流量满足非负约束）路径流量满足非负约束用户平衡配流模型（用户平衡配流模型（Beckmann模型模型）用户均衡的概念用户均衡的概念如图所示，一个有两条路径（同时也是路段）、连接一如图所示，一个有两条路径（同时也是路段）、连接一个出发地和一个目的地的简单交通网络，两个路段的阻个出发地和一个目的地的简单交通网络，两个路段的阻抗函数分别是：抗函数分别是：t1=2+x1，t2=1+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=2。此时，此时，t1=t2=5。可见，可见，Beckmann模型的解和平衡状态的解完全相同。模型的解和平衡状态的解完全相同。等价性证明等价性证明根根据据非非线线性性规规划划理理论论，对对模模型型构构造造拉拉格格朗朗日日（Lagrange）函数：函数：其中，其中，是拉格朗日乘子，也是是拉格朗日乘子，也是rs之间的最小阻抗。之间的最小阻抗。根据非线性规划理论中的库恩根据非线性规划理论中的库恩塔克（塔克（Kuhn-Tucher）条件，）条件，拉格朗日函数在极值点必须满足下列条件：拉格朗日函数在极值点必须满足下列条件：库恩库恩塔克条件可以简化表示为：塔克条件可以简化表示为：对于某个特定的连接对于某个特定的连接r和和s的路径，某路径的路径，某路径k的流量的流量 有两有两种可能：种可能：如果如果 ，得，得；如果如果 ，得，得 。求解方法求解方法步骤步骤1：初始化：按照初始化：按照 ，进行，进行0-1交通流分配，交通流分配，得到各路段的流量得到各路段的流量 ；令；令n=1；步骤步骤2：更新各路段的阻抗更新各路段的阻抗 ：步骤步骤3：寻找下一步迭代方向：按照更新后的寻找下一步迭代方向：按照更新后的 ，再进行一次再进行一次0-1交通流分配，得到一组附加流量交通流分配，得到一组附加流量 ；步骤步骤4：确定迭代步长：用二分法求满足下式的确定迭代步长：用二分法求满足下式的步骤步骤5：确定新的迭代起点确定新的迭代起点 ；步骤步骤6：收敛性检验。如果满足：收敛性检验。如果满足：其中其中是预先给定的误差限值，则是预先给定的误差限值，则 就是要求的平衡就是要求的平衡解，计算结束；否则，令解，计算结束；否则，令n=n+1，返回步骤，返回步骤2。系统最优模型系统最优模型该模型称为系统最优模型该模型称为系统最优模型SO(SystemOptimization)。Beckmann模型称为用户平衡模型模型称为用户平衡模型UE(UserEquilibrium)。系统最优分配与用户最优分配的关系：系统最优分配与用户最优分配的关系：对阻抗函数进行变换，令：对阻抗函数进行变换，令：如果用如果用 作为阻抗函数，则此时用户最优分配模型完全可作为阻抗函数，则此时用户最优分配模型完全可以转换为系统最优分配模型，所以进行该阻抗函数下的用户以转换为系统最优分配模型，所以进行该阻抗函数下的用户最优分配，得到的解就是系统最优分配的解。最优分配，得到的解就是系统最优分配的解。131113131最短路径算法最短路径算法好的交通量分配法必须有一种好的最短路径计算方法好的交通量分配法必须有一种好的最短路径计算方法寻找寻找O-D对之间的最小费用路径，简称最短路径，是求解对之间的最小费用路径，简称最短路径，是求解交通网络平衡配流问题的核心。交通网络平衡配流问题的核心。v任何一种交通量分配法都是建立在最短路径的基础上；任何一种交通量分配法都是建立在最短路径的基础上；v任何一个分配法中，最短路径的计算占据了全部计算任何一个分配法中，最短路径的计算占据了全部计算时间的主要部分。至少有时间的主要部分。至少有90%的计算时间花在最短路径的计算时间花在最短路径的寻找上。的寻找上。求解最短路径算法求解最短路径算法迪杰斯特拉迪杰斯特拉(Dijkstra)算法，即标点法（算法，即标点法（Label-correctingmethod）矩阵迭代法矩阵迭代法基本思想：基本思想：反复扫描网络的节点，在每次扫描中，该方法试图反复扫描网络的节点，在每次扫描中，该方法试图发现从根节点到正在扫描的节点之间的、比现有路发现从根节点到正在扫描的节点之间的、比现有路径更好的路径，当从根节点到所有其它节点之间没径更好的路径，当从根节点到所有其它节点之间没有更好的路径时，算法就停止搜索。有更好的路径时，算法就停止搜索。标点法标点法在此算法中，为每一个节点设置两个记录：在此算法中，为每一个节点设置两个记录：（1）标号标号，表示沿着最短路径从根节点到节点，表示沿着最短路径从根节点到节点的最小的最小费用；费用；（2）紧前节点）紧前节点，表示沿着最短路径到达节点，表示沿着最短路径到达节点且最靠近且最靠近的节点。的节点。在每次扫描中，将紧前节点都记录下来，形成紧前节点在每次扫描中，将紧前节点都记录下来，形成紧前节点序列，这是为了停止扫描时，能反馈地找出最短路径的序列，这是为了停止扫描时，能反馈地找出最短路径的轨迹。轨迹。检查列中包含正在和需要进一步检查的节点，掌握节点被检查列中包含正在和需要进一步检查的节点，掌握节点被检查的动态；检查的动态；标号列中记载各节点的标号；标号列中记载各节点的标号；紧前节点列中记载各节点的紧前节点，根据紧前节点列可紧前节点列中记载各节点的紧前节点，根据紧前节点列可以找到节点之间的最短路径；以找到节点之间的最短路径；每进行一步新的扫描，标号列、紧前节点列和检查列就要每进行一步新的扫描，标号列、紧前节点列和检查列就要更新一次，当检查列中不再有节点时，算法停止。更新一次，当检查列中不再有节点时，算法停止。算法步骤：算法步骤：第一步：第一步：初始化，置所有标号为无穷大（或一个很大的正初始化，置所有标号为无穷大（或一个很大的正数），置所有的紧前节点为零，将根节点数），置所有的紧前节点为零，将根节点 放入检查列放入检查列中，并令中，并令 ；第第二二步步：从从检检查查列列中中任任选选一一个个节节点点，例例如如节节点点，扫扫描描所有从所有从节点出发只经过一条弧便可到达的节点，例如节点出发只经过一条弧便可到达的节点，例如节点，如果：节点，如果：则更新节点则更新节点 上的标号，令上的标号，令 ，是从节点是从节点 到节点到节点 的弧上的阻抗值。的弧上的阻抗值。如果上面式子不成立，则节点如果上面式子不成立，则节点 的标号不变。的标号不变。第三步：第三步：在改变节点在改变节点 的标号的同时，修改的标号的同时，修改 ，且将，且将 加入到检查列中（因为从节点加入到检查列中（因为从节点 出发还可能到达其它节点）出发还可能到达其它节点）。当从。当从 出发只经过一条弧便可到达的所有节点都被检查过出发只经过一条弧便可到达的所有节点都被检查过时，就从检查列中删除时，就从检查列中删除 节点。节点。第四步：第四步：当检查列中不再有节点时，算法停止。从根节点到当检查列中不再有节点时，算法停止。从根节点到其它任意节点的最短路径可通过反向搜索最后的紧前节点序其它任意节点的最短路径可通过反向搜索最后的紧前节点序列识别出来。列识别出来。例例：包含：包含4条弧的简单网络，其中根节点为条弧的简单网络，其中根节点为1，弧上的数，弧上的数字表示弧的阻抗。字表示弧的阻抗。14231114第一步：所有节点的标号都置为第一步：所有节点的标号都置为 ，其紧前节点都置，其紧前节点都置为零。然后，节点为零。然后，节点1的标号变为的标号变为0，且把它放到检查列中。，且把它放到检查列中。第二步：从节点第二步：从节点1出发可以到达节点出发可以到达节点2和和4，先考虑节点，先考虑节点4，因为，因为 ，则节点，则节点4的标号变为的标号变为4，且，且被放入到检查列中。被放入到检查列中。迭迭代代检查检查列列节点节点1节点节点2节点节点3节点节点4节点节点1节点节点2节点节点3节点节点4000000110400011,4201401012,43012401213,44012301234501230123标号列标号列紧前节点列紧前节点列基本思想：基本思想：（1 1）是借助距离（路权）矩阵的迭代运算来求解）是借助距离（路权）矩阵的迭代运算来求解最短路权的算法。最短路权的算法。（2 2）该方法能一次获得任意两点之间的最短路权）该方法能一次获得任意两点之间的最短路权矩阵。矩阵。矩阵迭代法矩阵迭代法算法步骤：算法步骤：（1 1）首先构造距离矩阵（以距离为权的权矩阵）首先构造距离矩阵（以距离为权的权矩阵）（2 2）矩阵给出了节点间只经过一步（一条边）到达某一）矩阵给出了节点间只经过一步（一条边）到达某一点的最短距离点的最短距离（3 3）对距离矩阵进行如下的迭代运算，便可以得到经过）对距离矩阵进行如下的迭代运算，便可以得到经过两步达到某一点的最短距离：两步达到某一点的最短距离：k=1,2,3,nn：网络节点数；：网络节点数；*：矩阵逻辑运算符；：矩阵逻辑运算符；dik，dkj：距离矩阵：距离矩阵D中的相应元素。中的相应元素。例题：用例题：用矩阵迭代矩阵迭代法计算下图所示路网任意节点之间的最短法计算下图所示路网任意