交通规划8课件

第八章交通流分配第一节概述第二节交通流分配中的基本概念第三节非平衡分配方法第四节平衡分配方法第五节随机分配方法第六节动态交通流分配本章内容2/6/2023第一节概述城市交通网络上形成的交通流量分布是两种机制相互作用直至平衡的结果。实际中路阻是常量还是变量？路径选择的随机性表现在哪些方面，在交通分配时将会有何思路解决。明确几个问题：？2/6/2023邓建华第二节交通流分配中的基本概念一、交通分配交通流分配涉及到以下几个方面:可将现状OD交通量分配到现状交通网络上，以分析目前交通网络的运行状况。也可以是将规划年OD交通量分布预测值分配到现状交通网络上，以得到规划年交通需求，为交通网络的规划设计提供依据。还可以将规划年OD交通量分布预测值分配到规划交通网络上，以评价交通网络规划方案合理性。2/6/2023邓建华二、交通阻抗交通阻抗（或者称为路阻）在交通流分配中通过路阻函数来描述，所谓路阻函数是指路段行驶时间与路段交通负荷，交叉口延误与交叉口负荷之间的关系。在具体分配过程中，由路段行驶时间及交叉口延误共同组成出行交通阻抗。2/6/2023邓建华二、交通阻抗交通阻抗由两部分组成：路段阻抗和节点阻抗。城市道路：1.路段阻抗公路：BPR公路行驶时间函数：2/6/2023邓建华2.节点阻抗公路：因为路段比较长，路段延误占绝大 多数，一般不计交叉口延误。城市道路：可以计算分流向的、不分流的 交通流的延误，但是在实际操 作中比较困难，所以也可忽略 不计，或简单估计。2/6/2023邓建华

（二）最短径路算法最短径路算法是交通流分配中最基本也最重要的算法，几乎所有交通流分配方法都是以它作为一个基本子过程反复调用。最短路算法问题包含两个子问题：两点间最小阻抗的计算和两点间最小阻抗径路的辨识。在各类文献中，有关交通流分配最短径路的算法很多，如Dijkstra法、矩阵迭代法、Floyd-Warshall法等。2/6/2023邓建华1．Dijkstra法（标号法）(1)算法思想

①首先从起点O开始，给每个节点一个标号,分为T标号和P标号两类；

T是临时标号，表示从起点O到该点的最短路权上限；

P标号是固定标号，表示从起点O到该点的最短路权。

②标号过程中，T标号一直在改变，P标号不再改变，凡是没有标上P标号的点，都标上T标号。

③算法的每一步把某一点的T标号改变为P标号，直到所有的T标号都改变为P标号。即得到从始点O到其他各点的最短路权，标号过程结束。2/6/2023邓建华1．Dijkstra法（标号法）(2)算法步骤

Step1

初始化：给起点1标上P标号P(1)=0，其余各点均表标上T标号T1(j)=∞，j=2,3…,.n。即表示从起点1到1的最短路权为0，到其他各点的最短路权的上限临时定为∞。标号中括号内数字表示节点号，下标表示第几步标号。经过第一步标号得到一个P标号P(1)=0。2/6/2023邓建华1．Dijkstra法（标号法）(2)算法步骤

在所有的T标号（包括没有被修改的）中，比选出最小的T标号Tk（j0）：

式中j0—最小T标号所对应的节点号；T(r)—与i点不相邻点r的T标号。给点j0标上P标号：P(j0)=Tk(j0)，第K步标号结束。Step3当所有节点中已经没有T标号，算法结束，得到从起点1到其他各点的最短路权；否则返回Step2。2/6/2023邓建华【例8－1】步骤1给定起点1的P标号：P[1]=0，其他节点标上T标号：T1(2)=…=T1(9)=∞。步骤2节点1刚得到P标号。节点2、4与1相邻，且均为T标号，修改这两点的T标号： T2(2)=min[T1(2),P(1)+d12]=min[∞,0+2]=2 T2(4)=min[T1(4),P(1)+d14]=min[∞,0+2]=2在所有（包括没修改的）T标号中，找出最小标号。2、4为最小，任选其一，如节点2，即P[2]=T2(2)=2。步骤3节点2刚得到P标号。节点3、5与2相邻，且均为T标号，修改这两点的T标号：T3(3)=min[T(3),P(2)+d23]=min[∞,2+2]=4T3(5)=min[T(5),P(2)+d25]=min[∞,2+2]=4在所有T标号（点3,4,5…9）中，节点4为最小，给节点4标上P标号，即P[4]=T2(4)=2。2/6/2023邓建华所有节点均标上了P标号，计算结束。得到节点1到其他各节点的最短路权（P标号）表8.2-1例题8-1计算结果交通规划实际中，需要求出路网中任意两个节点之间的最短路权矩阵（n×n阶）；尽管Dijkstra算法一次能够算出从起点到其他各节点的最短路权，但仍不能满足要求，用此方法求最短路权矩阵，需要反复运算n次，导致计算效率不高，且速度较慢，所需存储空间较多，在大规模交通规划中应用受到一定限制。节点1234567891024234456P标号P(1)P(2)P(3)P(4)P(5)P(6)P(7)P(8)P(9)2/6/2023邓建华2．矩阵迭代法(2)算法步骤

①首先构造距离矩阵（以距离为权的权矩阵）。②矩阵给出了节点间只经过一步（一条边）到达某一点的最短距离。③对距离矩阵进行如下的迭代运算，便可以得到经过两步达到某一点的最短距离：2/6/2023邓建华【例8－2】(1)距离矩阵如表（构造矩阵）

2/6/2023邓建华(2)矩阵给出了节点间只经过一步（一条边）到达某一点的最短距离。

2/6/2023邓建华（3）进行矩阵迭代运算经过三步到达某一节点的最短距离为：（4）再进行矩阵迭代运算，运算方法同上2/6/2023邓建华3．最短径路辨识通过Dijkstra算法或矩阵迭代法得到最短路权矩阵后，还需要把每一个节点对之间具体的最短径路寻找出来，将交通流分配上去，进而进行网络的规划。

最短径路辨识采用追踪法：从每条最短径路的起点开始，根据起点到各节点的最短路权搜索最短径路上的各个交通节点，直至径路终点。2/6/2023邓建华算法思想：设某最短径路起点是r，终点是s。径路辨识算法如下：

（1）从起点r开始，寻找与r相邻的一节点i，满足： dri+Lmin(i,s)=Lmin(r,s) 式中：dri—路段r到i的距离； Lmin(i,s)—节点i到s的最短路权； Lmin(r,s)—节点r到s的最短路权。则路段[r，i]便是从r到s最短径路上的一段。（2）寻找与i相邻的一点j，使其满足： dij+Lmin(j,s)=Lmin(i,s)则路段[i，j]便是从r到s最短径路上的一段。（3）如此不断反复，直到终点s。把节点r,i,j…s连接起来，便得到从r到s的最短路线。2/6/2023邓建华四、交通平衡问题（一）Wardrop平衡原理:第一原理：在道路的利用者都确切知道网络的交通状态并试图选择最短径路时，网络将会达到平衡状态。在考虑拥挤对行走行驶时间影响的网络中，当网络达到平衡状态时，每个OD对的各条被使用的径路具有相等而且最小的走行时间行驶时间；没有被使用的径路的走行时间行驶时间大于或等于最小走行时间行驶时间。2/6/2023邓建华第一原理（用户均衡(UserEquilibrium，UE)或用户最优）：在道路的利用者都确切知道网络的交通状态并试图选择最短径路时，网络将会达到平衡状态。在考虑拥挤对行走行驶时间影响的网络中，当网络达到平衡状态时，每个OD对的各条被使用的径路具有相等而且最小的走行时间行驶时间；没有被使用的径路的走行时间行驶时间大于或等于最小走行时间行驶时间。2/6/2023邓建华这时需要求径路a与b上分配的交通量。根据Wardrop平衡第一原理的定义，很容易建立下列的方程组：

2/6/2023邓建华第三节非平衡分配方法非平衡分配方法按其分配方式可分为变化路阻和固定路阻两类，按分配形态可分为单径路径径路与多径路径径路两类2/6/2023邓建华一、全有全无分配方法其优点是计算相当简便，分配只需一次完成，其最大的弱点不足之处是出行量分布不均匀，出行量全部集中在最短径路上。显然这是与实际交通情况不符合的，因为当最短路上车流逐渐增加时，它的路阻会随之而增大，意味着这条路有可能不再是最短路，车流会转移到其他可行径路上行走，因此，其它路径上也会有流量。2/6/2023邓建华一、全有全无分配方法算法思想和计算步骤如下：算法思想

是将OD矩阵交通量T加载到路网的最短径路树上，从而得到路网中各路段流量的过程。计算步骤

Step0初始化，使路网中所有路段的流量为0，并求出各路段自由流状态时的阻抗。Step1计算路网中每个出发地O到每个目的地D的最短径路。Step2将O、D间的OD交通量全部分配到相应的最短径路上。2/6/2023邓建华增量分配法是一种近似的平衡分配方法。该方法是在全有全无分配方法的基础上，考虑了路段交通流量对阻抗的影响，进而根据道路阻抗的变化来调整路网交通量的分配，是一种“变化路阻”的交通量分配方法。增量分配法有容量限制—增量分配、容量限制—迭代平衡分配两种形式。二、增量分配法2/6/2023邓建华采用容量限制—增量分配方式，首先需先将OD表分解成N个分表(N个分层)，然后分N次使用最短路分配方法，每次分配一个OD分表，并且每分配一次，路阻就根据路阻函数修正一次，直到把N个OD分表全部分配到路网上。算法思想

将OD交通量分成若干份；循环地分配每一份的OD交通量到网络中；每次循环分配一份OD交通量到相应的最短径路上；每次循环均计算、更新各路段的走行行驶时间，然后按更新后的走行行驶行驶时间重新计算最短径路；下一循环按更新后的最短径路分配下一份OD量OD交通量。1.容量限制—增量分配2/6/2023邓建华容量限制—增量分配计算步骤

Step0初始化。以适当的形式分割OD交通量，即，令Step1计算、更新路段费用。Step2用全有全无分配法将第n个分割OD交通量 分配到最短经路上。Step3如果n=N，则结束计算。反之，令n=n+1返回Step1。这里，N-为分割次数；n为-循环次数。2/6/2023邓建华算法思想该法不需要将OD表分解，先假设路网中各路段上的流量为零，按零流量计算初始路阻，并分配这个OD表，然后按分配流量计算路阻，重新分配整个OD表，最后比较新分配的路段流量与原来分配的路段流量、新计算的路阻与原来计算的路阻，若分别比较接近，满足迭代精度要求，则停止迭代，获得最后的分配的交通量。否则，根据新计算的路权，再次分配，直到满足精度为止。2.容量限制—迭代平衡分配2/6/2023邓建华计算步骤

原理基本是相同的，分配过程中最主要的是确定路阻和计算最短路阻矩阵。理论上，若迭代精度控制得合理，迭代平衡分配的结果优于增量分配的结果。但迭代平衡方法事先无法估计迭代次数及计算工作量，对于较复杂的网络，可能会因为个别路段的迭代精度无法满足要求而使迭代进入死循环，出现算法不收敛的情况。为避免出现算法不收敛的情况，美国联邦公路局（FHWA，U.S）对这一算法进行了改进。2/6/2023邓建华迭代加权法（MethodofSuccessiveAverages，简称MSA法）是介于增量分配法和平衡分配法之间的一种循环分配方法。也称连续平均法或二次加权平均法。三、迭代加权法2/6/2023邓建华不断调整各路段分配的流量而逐渐接近平衡分配结果。每步循环中，根据各路段分配到的流量进行一次0-1全有全无分配，得到一组各路段的附加流量；然后用该循环中各路段已分配的交通量和该循环中得到的附加交通量进行加权平均，得到下一循环中的分配交通量；当相邻两次循环中分配的交通量十分接近时，即停止运算，最后一次循环中得到的交通量即为最终结果。算法思想2/6/2023邓建华计算步骤

Step0初始化。根据各路段自由行驶时间进行全有全无分配，得到初始解。令迭代次数n=0，路阻函数。Step1令n=n+1，按照当前各路段的交通量计算各路段的路阻。Step2按照Step1求得的行驶时间和OD交通量进行全有全无分配。得到各路段的附加交通量。Step3用MSA方法计算各路段当前交通量

Step4如果相差不大，则停止计算。即为最终分配结果。否则返回Step1。2/6/2023邓建华第四节平衡分配方法本节中，讨论讲述描述Wardrop平衡分配原理的数学模型，并在数学模型的基础上探讨平衡分配模型的求解算法。如在Wardrop平衡原理基本概念中所介绍的，满足Wardrop平衡分配原理的模型有用户平衡分配模型和系统最优平衡分配模型。2/6/2023邓建华一、用户平衡分配模型及其求解算法（一）用户平衡分配模型－Beckmann模型数学语言直接表达Wardrop用户平衡准则：当交通网络达到平衡时，若有，必有，说明如果从r到s有两条及其以上的径路被选中，那么它们的行驶时间相等；若有，必有，说明如果某条从r到s的径路流量等于零，那么该径路行驶时间一定超过被选中的径路的行驶时间。2/6/2023邓建华1、模型基本约束条件的分析交通流守恒：径路流量与路段流量关系：阻抗条件：2/6/2023邓建华2、Beckmann交通平衡分配模型为验证模型与理论的解的一致性，现举例说明2/6/2023邓建华【例8－6】已知：先用模型求解：具体模型如下将x1=5-x2代入目标函数并积分，转换为无约束极小值问题：2/6/2023邓建华【例8－6】根据平衡原理求解：根据Wardrop

用户平衡原理，网络达到平衡是应该有：

t1=t2

和x1+x2=5。联立求解这个方程组，很容易求得x1=3，x2=2。此时，t1=t2=5。可见，对于该路网，Beckmann模型的解和平衡状态的解完全相同。2/6/2023邓建华（二）用户平衡分配模型求解方法

Frank-Wolfe算法Beckmann模型是一个非线性规划模型，F-W方法的前提是模型的约束条件必须都是线性的。该方法是用线性规划逐步逼近非线性规划的方法，它是一种迭代法。在每步迭代中，先找到目标函数的一个最速下降方向，然后再找到一个最优步长，在最速下降(梯度法)方向上截取最优步长得到下一步迭代的起点，重复迭代直到找到最优解为止。概括而言，该方法的基本思路就是根据一个线性规划的最优解而确定下一步的迭代方向，然后根据目标函数的一维极值问题求最优迭代步长。2/6/2023邓建华（二）用户平衡分配模型求解方法

Frank-Wolfe算法1.Frank-Wolfe算法的基本原理设有非线性规划模型：min：Z(X)=f（X） s.t.AX=B，X≥0式中：X、B—向量；A—矩阵。对目标函数f（X）进行在X0处的一阶泰勒展开，得： f（X）=f（X0）+▽f（X0）(X-X0)这样将f（X）近似地表达成线性函数，则将其近似转化为下列线性规划模型： min：Z（X）=f（X0）+▽f（X0）(X-X0) s.t.AX=B，X≥02/6/2023邓建华（二）用户平衡分配模型求解方法

Frank-Wolfe算法1.Frank-Wolfe算法的基本原理再去掉目标函数的常数项，简化得：min：Z（X）=▽f（X0）Xs.t.AX=B，X≥0解此线性规划问题，可以得到最优解。F-W方法认定X0和的连线为目标函数的最速下降方向。然后由：求得λ为最优步长。令，从而得到下一步迭代的起点。如此循环，直到为止。2/6/2023邓建华（二）用户平衡分配模型求解方法

Frank-Wolfe算法2.Frank-Wolfe求解方法首先，我们考虑已知迭代起点而求决定下一步迭代方向的线性规划问题，该线性规划的目