第八讲+交通流分配

第八讲交通流分配

(TrafficDistributionForecast)Producedby:SaiorbeyondE-mail:sailorbeyond@工程学院【本章主要内容】8.5交通分配模型中存在的问题8.2交通网络平衡与非平衡分配理论8.1概述交通流分配8.3非平衡分配法8.4平衡分配法重点问题：

1、Wardrop第一、第二原理

2、简单平衡分配模型的求解

3、非平衡分配中的增量分配方法

4、简单的随机分配问题求解8.1概述交通流分配是交通需求预测四阶段法的第四阶段，任务是将各种出行方式的OD矩阵按照一定的路径选择原则分配到交通网络中的各条道路上，求出各路段上的流量及相关的交通指标，从而为交通网络的设计、评价等提供依据。一、交通流分配概述8.1概述OD矩阵

OD矩阵反映了各种方式的交通需求在不同时段的空间分布形态，这是需求预测前三个阶段得到的结果。在进行交通分配之前，需要将OD矩阵的单位转换为交通量或运量的单位（如出行次数转换为车辆数）。此外还需要进行时段的转换（如全日OD矩阵转换为高峰小时OD矩阵）。交通量分配即是将已经预测得出的OD交通量，根据已知的道路网描述，按照一定的规则符合实际地分配到道路网中的各条道路上，进而求出路网中各路段的交通流量。一般的道路网中，O与D之间有很多条道路，如何将OD交通量正确合理地分配到O与D之间的各条道路上即是交通分配模型要解决的问题。交通分配涉及以下几个方面1、将现状OD交通量分配到现状交通网络上，以分析目前交通网络的运行状况。若有某些路段的交通量观测值，还可以将观测值与分配结果进行比较，以检验模型精度。2、将规划年OD交通量预测值分配到现状交通网络上，以发现对规划年的交通需求而言的现状交通网络的缺陷，为交通网络的规划设计提供依据。3、将规划年OD交通量预测值分配到规划交通网络上，以评价交通网络规划方案的合理性。交通分配所需基本数据1、表示需求的OD交通量。在拥挤的城市道路交通网中通常采用高峰期OD交通量，在城市间公路网中通常采用年平均日交通量（AADT）的OD交通量。2、路网定义，即路段及交叉口特征和属性数据，同时还包括其时间—流量函数。3、路径选择原则。运行线路固定类型、运行线路不固定类型。交通网络8.1概述交通网络是交通需求作用的载体。在交通分配前，需要将现状（或规划）的交通网络抽象为数学中的有向图模型，以表达交通网络的拓扑关系和交通供给的各种特性。二、交通网络概述交通网络的抽象与简化

交通分配中所使用的网络是图论中抽象的网络图，由节点和连线组成。节点一般代表道路网中道路的交叉点以及交通小区的重心，连线则代表在两点之间存在一条道路。交通网络的抽象与简化简化时主要考虑以下几点：

①窄而容量小的道路可不予考虑；②小的道路交叉点不作节点考虑，而在与之相关的道路的行驶时间函数中恰当地考虑其影响；③可将几条平行道路合并成一条道路，并修改其容量；④分级构成网络。交通网的抽象与简化是由分析费用与分析精度的平衡决定的。

交通阻抗（或者称为路阻）直接影响到交通流路径的选择和流量的分配。道路阻抗在交通分配中可以通过路阻函数来描述。

路阻函数是指路段行驶时间与路段交通负荷、交叉口延误与交叉口负荷之间的关系。在具体分配过程中，由路段行驶时间及交叉口延误共同组成出行交通阻抗。三、交通阻抗交通阻抗交通网络上的路阻，应包含反映交通时间、交通安全、交通成本、舒适程度、便捷性和准时性等等许多因素。交通时间常常被作为计算路阻的主要标准：

（1）理论研究和实际观测表明，交通时间是出行者所考虑的首要因素，尤其在城市道路交通中；（2）几乎所有的影响路阻的其它因素都与交通时间密切相关，且呈现出与交通时间相同的变化趋势；（3）交通时间比其它因素更易于测量，即使有必要考虑到其它因素，也常常是将其转换为时间来度量。

路段阻抗

对于单种交通网络，出行者在进行路径选择时，一般都是以时间最短为目标。有些交通网络，路段上的行驶时间与距离成正比，与路段上的流量无关，如城市轨道交通网络，可选距离为阻抗。有些交通网络，如公路网、城市道路网，路段上的行驶时间与距离不一定成正比，而与路段上的交通流量有关，选用时间作为阻抗，可表达为：：路段a的所需时间；

：路段a上通过的交通流量。路段阻抗美国道路局BPR函数：

：路段a的交通容量，即单位时间内路段a可通过的最大车辆数；

：阻滞系数；

：零流阻抗，即路段a上为空静状态时车辆自由行驶所需时间。最早的BPR函数中，，，指实用交通容量；后来经过改进的BPR函数为，。指稳定交通容量。路段阻抗理想的路段阻抗函数应该具备下列的性质：1、真实性，用它计算出来的行驶时间应具有足够的真实性。2、函数应该是单调调递增与连续可导的。3、函数应该允许一定的“超载”，即当流量等于或超过通过能力时，行驶时间不应该为无穷大。应该反馈一个行驶时间，否则一个无穷大的数可能会导致计算机死机。。4、从实际应用的角度出发，阻抗函数应该具有很强的移植性，所以采用工程参数如自由流车速、通过能力等就比使用通过标定而得到的参数要好些。

节点阻抗

节点阻抗——指车辆在交通网络节点处（主要指在交叉口处）的阻抗。交叉口阻抗与交叉口的形式、信号控制系统的配时、交叉口的通过能力等因素有关。在城市交通网络的实际出行时间中，除路段行驶时间外，交叉口延误占有很大的比重。高峰期间交叉口延误可能会超过路段行驶时间。由于不同流向车辆在交叉口的不同延误在最短路径算法中的表达没能得到很好的解决，已有的城市道路交通流分配中一直忽略节点阻抗问题。四、最短路径的计算方法交通网络上任意一OD点对之间，从发生点到吸引点一串连通的路段的有序排列叫做这一OD点对之间的路径。一OD点对之间可以有多条路径，总阻抗最小的路径叫“最短路径”。

最短路径的计算是交通量分配中最基本也是最重要的计算：

任何一种交通量分配法都是建立在最短路径的基础上；几乎所有交通量分配方法中都是以它作为一个基本子过程反复调用，最短路径的计算占据了全部计算时间的主要部分。最短路径算法问题包含两个子问题：1、两点间最小阻抗的计算；2、两点间最小阻抗路径的辨识。前者是解决后者的前提。许多算法都是将这两个子问题分开考虑，设计出来的算法是分别单独求出最小阻抗和最短路径。

交通流分配最短路径的算法有:(1)Dijkstra法、(2)矩阵迭代法、(2)Floyd-Warshall法。（一）Dijkstra法

Dijkstra法也称标号法。常用于计算从某一指定点（起点）到另一指定点（终点）之间的最小阻抗。Dijkstra法可以同时求出网络中所有节点到某一个节点的全部最短路径或最短路径树。

标号的基本特点是：从网络中的某一个目的地节点开始，同时寻找网络中所有节点到该目的地节点的最短路径树，算法以一种循环的方式检查网络中所有的节点。在每一步循环中，总试图找到一条从被检查节点到目的地节点的更短路线。直到没有更短的路线可能被发现为止。1、Dijkstra法—算法思想

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

T标号是临时标号，表示从起点O到该该点的最短路权的上限；P标号是固定标号，表示从起点O到该点的最短路权。②标号过程中，T标号一直在改变，P标号不再改变，凡是没有标上P标号的点，都标上T标号。③算法的每一步把某一点的T标号改变为P标号，直到所有的T标号都改变为P标号。即得到从起点O到其它各点的最短路权，标号过程结束。2、Dijkstra法—算法步骤步骤1初始化。给起点1标上P标号P（1）=0，其余各点均标上T标号T1（j）=∞，j=2，3，…，n。即表示从起点1到起点1最短路权为0，到其各点的最短路权的上限临时定为∞。标号中括号内数字表示节点号，下标表示第几步标号。经过第一步标号得到一个P标号P（1）=0。步骤2设经过了（K-1）步标号，节点i是刚得到P标号的点，则对所有没有得到P标号的点进行下一步新的标号（第K步）；考虑所有与节点i相邻且没有标上P标号的点｛j｝，修改它们的T标号：Tk（j）=min[T（j），P（i）+dij]式中，dij——i到j的距离（路权）；

T（j）——第K步标号前j点的T标号。在所有的T标号（包括没有被修改的）中，比选出最小的T标号Tk（j0）：

Tk（j0）=min[Tk（j），T（r）]式中，j0——最小T标号所对应的节点；

T（γ）——与i点不相邻点r的T标号。给点j0标上P标号：P（j0）=Tk（j0），第K步标号结束。步骤3当所有节点中已经没有T标号，算法结束，得到从起点1到其它各点的最短路权；否则返回第二步。例题8.1

用Dijkstra法计算图7-1所示路网从节点1到各节点的最短路权。22①②③112222④2⑤⑥2⑦⑧⑨22图7-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]=2T2(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)+d24]=min[∞,2+2]=4在所有T标号（点3,4,5，…9）中，节点4为最小，给节点4标上P标号，即P(4)=T2(4)=2。步骤4：节点4刚得到P标号。节点5、7与4相邻，且均为T标号，修改这两点的T标号：T4(5)=min[T(5)，P(4)+d45]=min[4,2+1]=3T4(7)=min[T(7)，P(4)+d47]=min[∞,2+2]=4在所有T标号中，节点5为最小，给节点5标上P标号，即P(5)=T4(5)=3。

步骤5：节点5刚得到P标号。节点6、8与5相邻，且均为T标号，修改这两点的T标号：T5(6)=min[T(6)，P(5)+d56]=min[∞,3+1]=4T5(8)=min[T(8)，P(5)+d58]=min[∞,3+2]=5在所有T标号中，节点3为最小，给节点3标上P标号，即P(3)=T3(3)=4。步骤6：节点3刚得到P标号。节点6与3相邻，且为T标号，修改6的T标号：T6(6)=min[T(6)，P(3)+d36]=min[4,4+2]=4在所有T标号中，节点6为最小，给节点6标上P标号，即P(6)=T6(6)=4。步骤7：节点6刚得到P标号。节点9与6相邻，且为T标号，修改9的T标号：T7(9)=min[T(9)，P(6)+d69]=min[∞,4+2]=6在所有T标号中，节点7为最小，给节点7标上P标号，即P(7)=T4(7)=4。步骤8：节点7刚得到P标号。节点8与7相邻，且为T标号，修改8的T标号：T8(8)=min[T(8)，P(7)+d78]=min[5,4+2]=5在所有T标号中，节点8为最小，给节点8标上P标号，即P(8)=T8(8)=5。步骤9节点8刚得到P标号。节点9与8相邻，且为T标号，修改9的T标号：T9(9)=min[T(9)，P(8)+d89]=min[6,5+2]=6在所有T标号中，节点9为最小，给节点9标上P标号，即P(9)=T9(9)=6。节点123456789路权024234456P标号P(1)P(2)P(3)P(4)P(5)P(6)P(7)P(8)P(9)采用逆序法寻求最小路径，可得最短路径为：1-4-5-6-9，总的最小路权为6。交通规划实际中，需要求出路网中任意两个节点之间的最短路权矩阵（n×n阶）；尽管Dijkstra算法一次能够算出从起点到其它各节点的最短路权，但仍不能满足要求，用此方法求最短路权矩阵，需要反复运算n次，导致计算效率不高，且速度较慢，所需存储空间较多，在大规模交通规划中应用受到一定限制。Dijkstra算法的局限性①借助距离（路权）矩阵的迭代运算来求解最短路权的算法。②该方法能一次获得任意两点之间的最短路权矩阵。（二）矩阵迭代算法

1、矩阵迭代法—算法思想2、矩阵迭代法—算法步骤①首先构造距离矩阵（以距离为权的权矩阵）。②矩阵给出了节点间只经过一步（一条边）到达某一点的最短距离。③对距离矩阵进行如下的迭代运算，便可以得到经过两步达到某一点的最短距离。

（k=1,2,3,…,n）式中，n——网络节点数；——矩阵逻辑运算符；——距离矩阵D中的相应元素。例题8.2:

求解例题7-1网络任意节点间的最短路径。【解】

（1）构造距离矩阵，如下表所示。（第1步）i/j123456789102∞2∞∞∞∞∞2202∞2∞∞∞∞3∞20∞∞2∞∞∞42∞∞01∞2∞∞5∞2∞101∞2∞6∞∞2∞10∞∞27∞∞∞2∞∞02∞8∞∞∞∞2∞2029∞∞∞∞∞2∞2022①②③112222④2⑤⑥2⑦⑧⑨22图7-1交通网络示意图（2）进行矩阵迭代运算（第2步）=min[0+2,2+0,∞+2,2+∞,∞+2,∞+∞,∞+∞,∞+∞,∞+∞]=2（i=1,j=2；k=1,2，…,9）计算同理，如：=min[0+∞,2+2,∞+∞,2+1,∞+0,∞+1,∞+∞,∞+2,∞+∞]=3（i=1,j=5；k=1,2，…,9）从节点1经过两步到达5的最短路权为3。其他元素按同样方法计算，得到D2。（3）进行矩阵迭代运算（第3步）经过三步到达某一节点的最短距离为：（k=1,2,3,…,n）式中，——距离矩阵D2中的元素；

——距离矩阵D中的元素。（k=1,2,3,…,n）式中，——距离矩阵Dm-1中的元素；

——距离矩阵D中的元素。迭代不断进行，直到，即中每个元素等于此时的便是任意两点之间的最短路权矩阵。中的每个元素为止，（4）进行矩阵迭代运算（第m步）经过m步到达某一节点的最短距离为：本例中，，如下表所示。i/j123456789102423445622023235453420432654423401223453231013236432210432745623402485453232029654432420用矩阵迭代法求解网络的最短路，能够一次获得n×n阶的最短路权矩阵，简便快速。软件的开发比Dijkstra方法节省内存，速度快。网络越复杂，该方法的优越性越明显。

3、最短路径辨识

得到最短路权矩阵后，还需把每一个节点对之间具体的最短路径寻找出来，将交通流分配上去。最短路径辩识采用追踪法：从每条最短路径的起点开始，根据起点到各节点的最短路权搜索最短路径上的各个交通节点，直至路径终点。3.最短路径辨识——算法思想

设某最短路径的起点是r，终点是s。路径辩识算法如下：（1）从起点r开始，寻找与r相邻的节点i，满足：

式中，——路段r到i的距离；——节点i到s的最短路权；——节点r到s的最短路权。则路段[r,i]便是从r到s最短路径上的一段。（2）寻找与i相邻的一点j，使其满足：

则路段[i,j]便是从r到s最短路径上的一段。（3）如此不断反复，直到终点s。把节点r,i,j,…,s连接起来，便得到从r到s的最短路径。例题7.3：

辨识出例题7-2所求得的从节点1到节点9的最短路径。【解】从起点1开始，由于

d14+Lmin(4,9)=2+4=6=Lmin(1,9)所以[1,4]在最短路径上。由于d45+Lmin(5,9)=1+3=4=Lmin(4,9)所以[4,5]在最短路径上。由于d56+Lmin(6,9)=1+2=3=Lmin(5,9)所以[5,6]在最短路径上。由于d69+Lmin(9,9)=2+0=2=Lmin(6,9)所以[6,9]在最短路径上。则从节点1到节点9的最短路径是：1—4—5—6—9。【本章主要内容】8.5交通分配模型中存在的问题8.2交通网络平衡与非平衡分配理论8.1概述交通流分配8.3非平衡分配法8.4平衡分配法8.2交通网络平衡与非平衡分配一、概述若两点之间有很多条道路而这两点之间的交通量又很少的话，这些交通量显然会沿着最短的道路行走。随着交通量的增加，最短路径上的交通流量也会随之增加。增加到一定程度之后，这条最短路径的行驶时间会因为拥挤或堵塞而变长，最短路径发生变化，一部分道路利用者会选择次短的道路。随着两点之间的交通量继续增加，两点之间的所有道路都有可能被利用。若所有的道路利用者都准确知道各条道路所需的行驶时间，并选择行驶时间最短的道路，最终两点之间被利用的各条道路的行驶时间会相等。没有被利用的道路的行驶时间更长。这种状态被称之为道路网的平衡状态。背景在交通流分配中，一个实际道路网中一般有很多个OD对，每个OD对间都有多条路径。且各组OD之间的路径也互相重叠。1952年著名学者Wardrop提出了交通网络平衡定义的第一原理和第二原理，奠定了交通流分配的基础。二、Wardrop平衡原理1、Wardrop第一原理——用户最优原理(UE)

在道路网的利用者都确切知道网络的交通状态并试图选择最短路径时，网络会达到平衡状态。在考虑拥挤对走行时间影响的网络中，当网络达到平衡状态时，每个OD对的各条被利用的路径具有相等而且最小的走行时间；没有被利用的路径的走行时间大于或等于最小走行时间。——Wardrop平衡实际交通流分配中称为用户均衡（UE）或用户最优。网络拥挤的存在是平衡形成的条件。2、Wardrop第二原理——系统最优原理（SO）原理：系统平衡条件下，拥挤的路网上交通流应该按照平均或总的出行成本最小为依据来分配。第二原理是一个设计原理，是面向交通运输规划师和工程师的。第一原理主要是建立每个道路利用者使其自身出行成本（时间）最小化的行为模型，而第二原理则是旨在使交通流在最小出行成本方向上分配，从而达到出行成本最小的系统平衡。一般来说，两个原理下的平衡结果不会是一样的，但是在实际交通中，人们更期望交通流能够按照Wardrop第一原理，即用户平衡的近似解来分配。二、Wardrop平衡原理3、Wardrop平衡原理比较分析第一原理反映了道路用户选择路线的一种准则。按照第一原理分配出来的结果应该是路网上用户实际路径选择的结果。第二原理则反映了一种目标，即按照什么样的方式分配是最好的（系统最优）。在实际网络中很难出现第二原理所描述的状态，除非所有的驾驶员相互协作，为系统最优化而努力。这在实际中是不太可能的。但第二原理为交通管理人员提供了一种决策方法。

总结

例题8.4：设OD之间交通量q=2000veh/h，有两条路径a与b。路径a行驶时间短，但是通行能力小，路径b行驶时间长，但通行能力大。假设各自的行驶时间（min）与流量的关系为：

这时需要求路径a，b上分配的交通流量。根据Wardrop第一原理的定义，很容易建立下列的方程组：则有：

三、平衡和非平衡分配1952年Wardrop提出道路网平衡的概念和定义之后，如何求解Wardrop平衡成了重要的研究课题。1956年，Beckmann等提出了描述平衡交通分配的一种数学规划模型。1975年由LeBlanc等学者将Frank—Wolfe算法用于求解Beckmann模型获得成功，从而形成了现在的实用解法。Wardrop原理—Beckmann模型—LeBlanc算法这些突破是交通分配问题研究的重大进步，也是交通分配问题的基础。

交通流分配方法分为平衡分配和非平衡分配两大类。对于完全满足Wardrop原理定义的平衡状态，则称为平衡分配法；对于采用启发式方法或其他近似方法的分配模型，则称为非平衡分配方法。

【本章主要内容】8.3非平衡分配法8.5交通分配模型中存在的问题8.2交通网络平衡与非平衡分配理论8.1概述8.4平衡分配法交通流分配非平衡分配方法按其分配方式可分为变化路阻和固定路阻两类；按分配形态可分为单路径与多路径两类。固定路阻变化路阻单路径全有全无方法容量限制方法多路径静态多路径方法容量限制多路径方法8.3非平衡分配方法7.3.1全有全无分配法

（All-or-NothingAssignmentMethod）

全有全无方法（0-1分配法）不考虑路网的拥挤效果，取路阻为常数，即假设车辆的路段行驶速度、交叉口延误不受路段、交叉口交通负荷的影响。每一个OD点对的OD交通量被全部分配在连接OD点对的最短路径上，其他路径上分配不到交通量。优点是计算相当简便，分配只需一次完成；不足之处是出行量分布不均匀，出行量全部集中在最短路径上。

8.3非平衡分配方法全有全无分配法

——算法思想和计算步骤

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

Step0：初始化，使路网中所有路段的流量为0，并求出各路段自由流状态时的阻抗；

Step1：计算网络中每个出发地O到每个目的地D的最短路径；

Step2：将O、D间的OD交通量全部分配到相应的最短路径上。8.3非平衡分配方法例题7.5:设图7-2所示交通网络的OD交通量为t=200辆，各径路的交通费用函数分别为：试用全有全无分配法求出分配结果。

8.3非平衡分配方法【解】：

全有全无分配法

由路段费用函数可知，在路段交通量为零时，径路1最短。根据全有全无原则，交通量全部分配到径路1上，得到以下结果：因为，，根据Wardrop原理，网络没有达到平衡状态，没有得到均衡解。此时路网总费用为：8.3非平衡分配方法由于0-1分配法不能反映拥挤效果，主要是用于某些非拥挤路网，用于没有通行能力限制的网络的情况。

建议使用范围是：在城际之间道路通行能力不受限制的地区可以采用；一般城市道路网的交通量分配不宜采用该方法。在实际中由于其简单实用的特性，一般作为其他各种分配技术的基础，在增量分配法和平衡分配法等方法中反复使用。8.3非平衡分配方法

增量分配法（简称IA分配法）是一种近似的平衡分配法。在全有全无分配方法的基础上，考虑了路段交通流量对阻抗的影响，进而根据道路阻抗的变化来调整路网交通量的分配，是一种“变化路阻”的交通量分配方法。首先需将OD表分解成N个分表（N个分层），然后分N次使用最短分配方法，每次分配一个OD分表，并且每分配一次，路阻就根据路阻函数修正一次，直到把N个OD分表全部分配到路网上。8.3非平衡分配方法7.3.2增量分配法

（IncrementalAssignmentMethod）增量分配法

—算法思想

将OD交通量分成若干份（等分或不等分）；循环地分配每一份的OD