第八讲交通流分配课件

第八讲交通流分配课件1【本章主要内容】8.5交通分配模型中存在的问题8.2交通网络平衡与非平衡分配理论8.1概述交通流分配8.3非平衡分配法8.4平衡分配法【本章主要内容】8.5交通分配模型中存在的问题8.2交通2重点问题：

1、Wardrop第一、第二原理

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

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

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

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

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

交通网络的抽象与简化简化时主要考虑以下几点：交通网的抽象11

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

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

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

交通阻抗交通网络上的路阻，应包含反映交通时间、交13路段阻抗

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

：路段a上通过的交通流量。路段阻抗对于单种交通网络，出行者在进行路径选14路段阻抗美国道路局BPR函数：

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

：阻滞系数；

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

路段阻抗理想的路段阻抗函数应该具备下列的性质：16节点阻抗

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

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

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

交通流分配最短路径的算法有:(1)Dijkstra法、(2)矩阵迭代法、(2)Floyd-Warshall法。最短路径算法问题包含两个子问题：19（一）Dijkstra法

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

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

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

T标号是临时标号，表示从起点O到该该点的最短路权的上限；P标号是固定标号，表示从起点O到该点的最短路权。②标号过程中，T标号一直在改变，P标号不再改变，凡是没有标上P标号的点，都标上T标号。③算法的每一步把某一点的T标号改变为P标号，直到所有的T标号都改变为P标号。即得到从起点O到其它各点的最短路权，标号过程结束。1、Dijkstra法—算法思想①首212、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到其它各点的最短路权；否则返回第二步。2、Dijkstra法—算法步骤步骤122例题8.1

用Dijkstra法计算图7-1所示路网从节点1到各节点的最短路权。22①②③112222④2⑤⑥2⑦⑧⑨22图7-1交通网络示意图例题8.1

用Dijkstra法计算图7-123步骤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。【解】步骤1：给定起点1的P标号：P(1)=0，其他节点标上24步骤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。步骤3：节点2刚得到P标号。节点3、5与2相邻25

步骤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。步骤5：节点5刚得到P标号。节点6、8与5相邻，且均26步骤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。步骤7：节点6刚得到P标号。节点9与6相邻，且27步骤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。步骤9节点8刚得到P标号。节点9与8相邻，28交通规划实际中，需要求出路网中任意两个节点之间的最短路权矩阵（n×n阶）；尽管Dijkstra算法一次能够算出从起点到其它各节点的最短路权，但仍不能满足要求，用此方法求最短路权矩阵，需要反复运算n次，导致计算效率不高，且速度较慢，所需存储空间较多，在大规模交通规划中应用受到一定限制。Dijkstra算法的局限性交通规划实际中，需要求出路网中任意两个节点之间的29①借助距离（路权）矩阵的迭代运算来求解最短路权的算法。②该方法能一次获得任意两点之间的最短路权矩阵。（二）矩阵迭代算法

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

（k=1,2,3,…,n）式中，n——网络节点数；——矩阵逻辑运算符；——距离矩阵D中的相应元素。2、矩阵迭代法—算法步骤①首先构造距离矩阵（以距离为权的权矩31例题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交通网络示意图例题8.2:

求解例题7-1网络任意节点间的最短32（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中的元素。（2）进行矩阵迭代运算（第2步）=min[0+2,2+0,33（k=1,2,3,…,n）式中，——距离矩阵Dm-1中的元素；

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

本例中，，如下表所示。i/j1234567891024234353、最短路径辨识

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

设某最短路径的起点是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的最短路径。3.最短路径辨识——算法思想设某最短路径的起点是r，终点是37例题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。例题7.3：【解】从起点1开始，由于38【本章主要内容】8.5交通分配模型中存在的问题8.2交通网络平衡与非平衡分配理论8.1概述交通流分配8.3非平衡分配法8.4平衡分配法【本章主要内容】8.5交通分配模型中存在的问题8.2交通398.2交通网络平衡与非平衡分配一、概述若两点之间有很多条道路而这两点之间的交通量又很少的话，这些交通量显然会沿着最短的道路行走。随着交通量的增加，最短路径上的交通流量也会随之增加。增加到一定程度之后，这条最短路径的行驶时间会因为拥挤或堵塞而变长，最短路径发生变化，一部分道路利用者会选择次短的道路。随着两点之间的交通量继续增加，两点之间的所有道路都有可能被利用。若所有的道路利用者都准确知道各条道路所需的行驶时间，并选择行驶时间最短的道路，最终两点之间被利用的各条道路的行驶时间会相等。没有被利用的道路的行驶时间更长。这种状态被称之为道路网的平衡状态。背景8.2交通网络平衡与非平衡分配一、概述背40在交通流分配中，一个实际道路网中一般有很多个OD对，每个OD对间都有多条路径。且各组OD之间的路径也互相重叠。1952年著名学者Wardrop提出了交通网络平衡定义的第一原理和第二原理，奠定了交通流分配的基础。在交通流分配中，一个实际道路网中一般有很多个OD对，每个OD41二、Wardrop平衡原理1、Wardrop第一原理——用户最优原理(UE)

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

总结3、Wardrop平衡原理比较分析第一原理反映了道路用户选择44

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

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

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

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

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

（All-or-NothingAssignmentMethod）

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

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

（All-or-Nothing51全有全无分配法

——算法思想和计算步骤

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

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

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

Step2：将O、D间的OD交通量全部分配到相应的最短路径上。8.3非平衡分配方法全有全无分配法

——算法思想和计算步骤52例题7.5:设图7-2所示交通网络的OD交通量为t=200辆，各径路的交通费用函数分别为：试用全有全无分配法求出分配结果。

8.3非平衡分配方法例题7.5:设图7-2所示交通网络的OD交通量为t=2053【解】：

全有全无分配法

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

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

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

（IncrementalAssignmentMethod）增量分配法（简称IA分配法）是一种近似的平衡分56增量分配法

—算法思想

将OD交通量分成若干份（等分或不等分）；循环地分配每一份的OD交通量到网络中；每次循环分配一份OD交通量到相应的最短路径上；每次循环均计算、更新各路段的走行时间，然后按更新后的走行时间重新计算最短路径；下一循环中按更新后的最短路径分配下一份的OD交通量。

8.3非平衡分配方法增量分配法

—算法思想57，停止计算。当前的路段交通流量即是最终解；

Step0：初始化。将每组OD交通量平分成N等分，即使同时，令。

。Stepl：更新，。

Step2：增量分配。按Step1计算所得，用0-1分配法将的OD交通量分配到网络中去。这样得到一组附加交通流量。

Step3：交通流量累加。即令。

step4：判定。如果，令，返回stepl。

如果8.3非平衡分配方法增量分配法

—算法步骤

，停止计算。当前的路段交通流量即是最终解；Step0：初58例题7.6:设图7-2所示交通网络的OD交通量为t=200辆，各径路的交通费用函数分别为：试用增量分配法求出分配结果。

8.3非平衡分配方法例题7.6:设图7-2所示交通网络的OD交通量为t=2059【解】：

增量分配法采用2等分。①第1次分配与全有全无分配法相同，径路1最短。②第2次分配，此时最短径路变为径路2这时，根据Wardrop原理，各条径路的费用接近相等，路网接近平衡状态，结果接近于平衡解。此时路网总费用为：8.3非平衡分配方法【解】：增量分配法②第2次分配，此时最短径路变为径路260复杂程度和解的精确性都介于0-1分配法和后述的平衡分配法之间。时便与0-1分配法的结果一致；时，其解与平衡分配法的解一致。优点：简单可行，精确度可以根据分割数N的大小来调整。在实际的道路网交通量分配中经常被采用，而且也有比较成熟的商用软件可供使用。缺点：仍然是一种近似方法，当路阻函数不是很敏感时，有时会将过多的交通流量分配到某些容量很小的路段上。一般情况下，得不到平衡解。

总结8.3非平衡分配方法复杂程度和解的精确性都介于0-1分配法和后述61算法思想不断调整已分配到各路段上的交通流量而逐渐到达或接近平衡分配。在每步循环中，根据已分配到各路段上的交通流量进行一次0-1分配，得到一组各路段的附加交通量。然后用该循环中各路段的分配交通流量和该循环中得到的附加交通量进行加权平均，得到下一循环中的分配交通流量。当相邻两个循环中分配的交通流量十分接近时，即可停止计算。最后一次循环中得到的分配交通量即是最终的交通量。

8.3非平衡分配方法7.3.3迭代加权法

（MethodofSuccessiveAverage,MSA）算法思想8.3非平衡分配方法7.3.3迭代加权法

（Me62Step0：初始化。按照各路段的自由走行时间进行一次0-1分配，得到各路段的分配交通流量。令Step1：令，按照当前各路段的交通量

Step2：按照Step1计算的路段走行时间和OD交通量进行0-1分配，得到Step3：用加权平均的方法计算各路段的当前交通量：Step4：如果与的差值不大，则停止计算，否则返回Step1。。计算各路段的路阻。各路段的附加交通流量。即为最终分配结果。8.3非平衡分配方法算法步骤：Step0：初始化。按照各路段的自由走行时间进行一次0-63在Step4中，判别与差值大小时可控制它们的相对误差在百分之几以内。但用得更多的准则是循环多少次以后令其停止。在Step3中，权重系数需由计算者自己定。既可定为常数，也可定为变数。定为常数时，最普遍的情况是令。定为变数时，最普遍的情况是令(n为循环次数)。有研究表明时，会使分配尽快接近平衡解。二次加权平均法是一种简单实用却又最接近于平衡分配法的一种分配方法。如果每步循环中权重系数严格按照数学规划模型取值时，即可得到平衡分配的解。

总结8.3非平衡分配方法7.3.3迭代加权法

（IncrementalAssignmentMethod）在Step4中，判别与差值大小时可控制它64【本章主要内容】8.5交通分配模型中存在的问题8.2交通网络平衡与非平衡分配理论8.1概述8.3非平衡分配法8.4平衡分配法交通流分配【本章主要内容】8.5交通分配模型中存在的问题8.2交通658.4平衡分配法用户平衡分配模型和系统最优平衡分配模型一、用户平衡分配模型及其求解算法用户平衡分配模型（UE）1956年Beckmann等学者提出了一种满足Wardrop准则的数学规划模型，奠定了研究交通分配问题的理论基础。后来的许多分配模型，诸如弹性需求交通分配模型、分布—分配组合模型等都是在Beckmann模型的基础上扩展得到的。8.4平衡分配法用户平衡分配模型和系统最优平衡分配模型66用户平衡分配模型

——Bechmann模型St:用户平衡分配模型

67用户平衡分配模型1、模型中使用的变量和参数：路段a上的交通流量；：路段a的交通阻抗，也称为走行时间；：路段a的阻抗函数，因而；：出发地为r，目的地为s的OD间的第k条路径上的交通流量；：出发地为r，目的地为s的OD间的第k条路径的阻抗；：出发地为r，目的地为s的OD间的最短路径的阻抗；：路段-路径变量，即0-1变量，如果路段a在出发地为r目的地为s的OD间的第k条路径上，则，否则，。用户平衡分配模型1、模型中使用的变量和参数68

：网络中节点的集合；：网络中路段的集合；：网络中出发地的集合；：网络中目的地的集合；：r与s之间的所有路径的集合；：r与s间的OD交通量。第八讲交通流分配课件69用户平衡分配模型用数学语言直接表达Wardrop用户平衡准则，则可以描述为：当交通网络达到平衡时，若有，必有，说明若从r到s有两条及其以上的路径被选中，则它们的行驶时间相等；若有，必有，说明若某条从r到s的路径流量等于零，则该路径的行驶时间一定超过被选中的路径的行驶时间。

用户平衡分配模型用数学语言直接表达War70用户平衡分配模型2.模型的基本约束条件分析平衡分配过程中应满足交通流守恒的条件，即OD间各条路径上的交通之和应等于OD交通总量：路段交通量应是由各个（r，s）对的途径该路段的路径的流量累加而成：路径阻抗应是该路径途径的各路段的阻抗的累加：

用户平衡分配模型2.模型的基本约束条件分析713.模型的基本约束条件分析——例证用户平衡分配模型3.模型的基本约束条件分析——例证用户平衡分配模型72用户平衡分配模型

——Bechmann模型Subjectto:用户平衡分配模型

73Beckmann模型的解就是交通流分配达到平衡状态时的解——例证两个路段的阻抗函数分别是：

OD量为q=5，分别求该网络的Beckmann模型的解和平衡状态的解。s.t.【解】先求Beckmann模型的解。将阻抗函数带入模型，得：x1,

x2≥0例证Beckmann模型的解就是交通流分配达到平衡74将代入目标函数并进行积分，转换为无约束的极小值问题：Min:

令dZ/dx1=0，解得，。下面求平衡状态的解。根据Wardrop用户平衡原理，网络达到平衡时应该有：

t1=t2和联立求解这个方程组，很容易求得，此时，t1=t2=5。可见，对于该路网，Beckmann模型的解和平衡状态的解完全相同。将代入目标函数并进行积分，转换为无约束的极小值问题：Min:75三、系统最优化分配模型系统最优分配模型

系统最优分配（SO）：在拥挤的网络中，交通量应该按照使得网络中总阻抗即总走行时间最小的原则进行分配。第二原理反映了一种目标，是交通系统管理者的主观愿望，即按什么样的方式分配是最好的。可以作为对系统评价的指标，为管理者提供一种决策方法。从此种意义上说，第二原理是道路系统管理者所希望的分配原则，尤其在智能交通系统获得广泛应用之后。

三、系统最优化分配模型系统最优分配模型76系统最优分配模型约束条件：对阻抗函数进行不同的修改，UE模型与SO模型可以互相转换。

系统最优分配模型约束条件：对阻抗函数进行不同77【本章主要内容】8.5交通分配模型中存在的问题8.2交通网络平衡与非平衡分配理论8.1概述8.3非平衡分配法8.4平衡分配法交通流分配【本章主要内容】8.5交通分配模型中存在的问题8.2交通788.5交通分配模型中存在的问题一、对交通流量的近似假定只有在OD交通流量都是稳定不变的的前提条件下，才会有道路网的“平衡”，前述的各种交通分配方法才成立。而实际的交通量是动态的。在实际交通量分配中，一般以一天为单位，对一天的平均交通流量进行分配，而得到每条道路一天的平均流量。产生两个问题。一是交通分配问题非线性问题，用一天的平均OD交通流量进行分配得到的结果与用实际的动态OD交通量进行分配得到的结果肯定会有差别。二是在实际的道路网规划中，有时不只是需要一天的平均情况，而且需要知道某个特定时间段的道路交通状况，而静态交通量分配模型无法推定某个特定时间段的道路网状况。8.5交通分配模型中存在的问题一、对交通流量的近似假定79二、利用者路径选择方法的假定在交通分配模型中，假定道路网的利用者都知道道路网中各条路线的拥挤状况和所需走行时间，并且具有相同的选择标准。路径选择与交通量分配的研究一直各自独立互不相干地进行着，没有很好地结合在一起。二、利用者路径选择方法的假定在交通分配模型中，80三、交通网络的局限性使用的网络是经简化后的网络。在网络中简化掉狭小道路有可能使干线道路的分配交通量大于实际交通流量。在实际道路网中，交通量一般是在区域内均匀地发生和吸引。在目前的交通量分配模型中，都是将OD交通量集中在区域的某一点——中心节点上发生和吸引。造成的误差是靠近该点的路线上将可能被分配到多于实际流量的交通流量，而离该点较远的路线上分配的交通流量则较少。路阻函数的简化。交通量分配模型中的路阻函数一般涉及到两个量，即路段交通量和交通容量。但实际道路中影响走行时间的远不止这两种因素。道路的几何形状、坡度、信号控制状况、禁止左右转等都对走行时间有影响。

三、交通网络的局限性使用的网络是经简化后的网络。在网81【课后作业】

如图所示的交通网络，从A到B有两条路径1、2，两条路径上的交通阻抗函数分别为：路径1：t1=15+0.005x1路径2：t2=10+0.02x2现从A到B有3000辆车，分别用以下方法进行交通流分配：（1）UE分配方法（2）全有全无分配方法（3）增量分配方法（OD三等分）。【课后作业】如图所示的交通网络，从A到B有两条路径1、82

谢谢大家谢谢大家83第八讲交通流分配课件84【本章主要内容】8.5交通分配模型中存在的问题8.2交通网络平衡与非平衡分配理论8.1概述交通流分配8.3非平衡分配法8.4平衡分配法【本章主要内容】8.5交通分配模型中存在的问题8.2交通85重点问题：

1、Wardrop第一、第二原理

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

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

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

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

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

交通网络的抽象与简化简化时主要考虑以下几点：交通网的抽象94

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

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

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

交通阻抗交通网络上的路阻，应包含反映交通时间、交96路段阻抗

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

：路段a上通过的交通流量。路段阻抗对于单种交通网络，出行者在进行路径选97路段阻抗美国道路局BPR函数：

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

：阻滞系数；

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

路段阻抗理想的路段阻抗函数应该具备下列的性质：99节点阻抗

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

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

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

交通流分配最短路径的算法有:(1)Dijkstra法、(2)矩阵迭代法、(2)Floyd-Warshall法。最短路径算法问题包含两个子问题：102（一）Dijkstra法

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

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

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

T标号是临时标号，表示从起点O到该该点的最短路权的上限；P标号是固定标号，表示从起点O到该点的最短路权。②标号过程中，T标号一直在改变，P标号不再改变，凡是没有标上P标号的点，都标上T标号。③算法的每一步把某一点的T标号改变为P标号，直到所有的T标号都改变为P标号。即得到从起点O到其它各点的最短路权，标号过程结束。1、Dijkstra法—算法思想①首1042、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到其它各点的最短路权；否则返回第二步。2、Dijkstra法—算法步骤步骤1105例题8.1

用Dijkstra法计算图7-1所示路网从节点1到各节点的最短路权。22①②③112222④2⑤⑥2⑦⑧⑨22图7-1交通网络示意图例题8.1

用Dijkstra法计算图7-1106步骤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。【解】步骤1：给定起点1的P标号：P(1)=0，其他节点标上107步骤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。步骤3：节点2刚得到P标号。节点3、5与2相邻108

步骤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。步骤5：节点5刚得到P标号。节点6、8与5相邻，且均109步骤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。步骤7：节点6刚得到P标号。节点9与6相邻，且110步骤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。步骤9节点8刚得到P标号。节点9与8相邻，111交通规划实际中，需要求出路网中任意两个节点之间的最短路权矩阵（n×n阶）；尽管Dijkstra算法一次能够算出从起点到其它各节点的最短路权，但仍不能满足要求，用此方法求最短路权矩阵，需要反复运算n次，导致计算效率不高，且速度较慢，所需存储空间较多，在大规模交通规划中应用受到一定限制。Dijkstra算法的局限性交通规划实际中，需要求出路网中任意两个节点之间的112①借助距离（路权）矩阵的迭代运算来求解最短路权的算法。②该方法能一次获得任意两点之间的最短路权矩阵。（二）矩阵迭代算法

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

（k=1,2,3,…,n）式中，n——网络节点数；——矩阵逻辑运算符；——距离矩阵D中的相应元素。2、矩阵迭代法—算法步骤①首先构造距离矩阵（以距离为权的权矩114例题8.2: