第八讲+交通流分配

•
（一）Dijkstra法
• Dijkstra法也称标号法。常用于计算从某一指定
点（起点）到另一指定点（终点）之间的最小阻抗。
Dijkstra法可以同时求出网络中所有节点到某一个节 点的全部最短路径或最短路径树。 • 标号的基本特点是：从网络中的某一个目的地节 点开始，同时寻找网络中所有节点到该目的地节点的
权。
②标号过程中，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到其它各点 的最短路权；否则返回第二步。
交通阻抗
• 交通网络上的路阻，应包含反映交通时间、交通安 全、交通成本、舒适程度、便捷性和准时性等等许多 因素。
• 交通时间常常被作为计算路阻的主要标准： （1）理论研究和实际观测表明，交通时间是出行者 所考虑的首要因素，尤其在城市道路交通中； （2）几乎所有的影响路阻的其它因素都与交通时间 密切相关，且呈现出与交通时间相同的变化趋势；
例题8.1
用Dijkstra法计算图7-1所示路网从节点1到各 节点的最短路权。
①
2 2
②
2
2
③
2
④
2
1
⑤
2
1
⑥
2
2
⑦
2
⑧
⑨
图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]=2 T2(4)=min[T1(4)，P(1)+d14]=min[∞,0+2]=2
• T7(9)=min[T(9)，P(6)+d69]=min[∞,4&#，给节点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
交通网络的抽象与简化
• 简化时主要考虑以下几点：
① 窄而容量小的道路可不予考虑；
② 小的道路交叉点不作节点考虑，而在与之 相关的道路的行驶时间函数中恰当地考虑其影响； ③ 可将几条平行道路合并成一条道路，并修 改其容量；
④ 分级构成网络。
交通网的抽象与简化是由分析费用与分析精度的平衡决定的。
三、交通阻抗 • 交通阻抗（或者称为路阻）直接影响到交通 流路径的选择和流量的分配。 • 道路阻抗在交通分配中可以通过路阻函数来 描述。 • 路阻函数是指路段行驶时间与路段交通负荷、 交叉口延误与交叉口负荷之间的关系。在具体分 配过程中，由路段行驶时间及交叉口延误共同组 成出行交通阻抗。
（3）交通时间比其它因素更易于测量，即使有必要 考虑到其它因素，也常常是将其转换为时间来度量。
路段阻抗
•
•
对于单种交通网络，出行者在进行路径选择时，一 般都是以时间最短为目标。
有些交通网络，路段上的行驶时间与距离成正比， 与路段上的流量无关，如城市轨道交通网络，可选距离 为阻抗。 有些交通网络，如公路网、城市道路网，路段上的 行驶时间与距离不一定成正比，而与路段上的交通流量 有关，选用时间作为阻抗，可表达为：
最短路径树，算法以一种循环的方式检查网络中所有
的节点。在每一步循环中，总试图找到一条从被检查 节点到目的地节点的更短路线。直到没有更短的路线 可能被发现为止。
1、Dijkstra法—算法思想
①首先从起点O开始，给每个节点一个标号，分为T标
号和P标号两类。
T标号是临时标号，表示从起点O到该该点的最短路权 的上限；P标号是固定标号，表示从起点O到该点的最短路
•
节点阻抗
• • • 节点阻抗——指车辆在交通网络节点处（主 要指在交叉口处）的阻抗。 交叉口阻抗与交叉口的形式、信号控制系统 的配时、交叉口的通过能力等因素有关。 在城市交通网络的实际出行时间中，除路段 行驶时间外，交叉口延误占有很大的比重。高峰 期间交叉口延误可能会超过路段行驶时间。 由于不同流向车辆在交叉口的不同延误在最 短路径算法中的表达没能得到很好的解决，已有 的城市道路交通流分配中一直忽略节点阻抗问题。
步骤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标号：
•
taf (qa )
t a ：路段a的所需时间； qa ：路段a上通过的交通流量。
路段阻抗
• 美国道路局BPR函数：
qa t a (q a ) t a (0) 1 C a


, ：阻滞系数；
Ca ：路段a的交通容量，即单位时间内路段a可通过的最大车辆数；
•
• •
在所有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]=3
•
•
T4(7)=min[T(7)，P(4)+d47]=min[∞,2+2]=4
在所有（包括没修改的）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]=4 T3(5)=min[T(5)，P(2)+d24]=min[∞,2+2]=4
t a (0) ：零流阻抗，即路段a上为空静状态时车辆自由行驶所需时间。
最早的BPR函数中，
0.15 ， 4 ， Ca 指实用交通容量； 后来经过改进的BPR函数为 2.26 ， 5 。Ca 指稳定交通容量。
路段阻抗
理想的路段阻抗函数应该具备下列的性质： • • • 1、真实性，用它计算出来的行驶时间应具有足够的真 实性。 2、函数应该是单调调递增与连续可导的。 3、函数应该允许一定的“超载”，即当流量等于或超 过通过能力时，行驶时间不应该为无穷大。应该反馈一个 行驶时间，否则一个无穷大的数可能会导致计算机死机。。 4、从实际应用的角度出发，阻抗函数应该具有很强的 移植性，所以采用工程参数如自由流车速、通过能力等就 比使用通过标定而得到的参数要好些。
• 最短路径算法问题包含两个子问题： • 1、两点间最小阻抗的计算；
•
2、两点间最小阻抗路径的辨识。
• 前者是解决后者的前提。
•
许多算法都是将这两个子问题分开考虑，设 计出来的算法是分别单独求出最小阻抗和最短路 径。
交通流分配最短路径的算法有:(1)Dijkstra 法、(2)矩阵迭代法、(2)Floyd-Warshall法。
•
四、最短路径的计算方法
• 交通网络上任意一OD点对之间，从发生点到吸引点 一串连通的路段的有序排列叫做这一OD点对之间的路径。 一OD点对之间可以有多条路径，总阻抗最小的路径叫 “最短路径”。
最短路径的计算是交通量分配中最基本也是最重 要的计算：
•
任何一种交通量分配法都是建立在最短路径的基础 上；几乎所有交通量分配方法中都是以它作为一个基本 子过程反复调用，最短路径的计算占据了全部计算时 间的主要部分。
在所有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]=4 T5(8)=min[T(8)，P(5)+d58]=min[∞,3+2]=5 在所有T标号中，节点3为最小，给节点3标上P标号，即 P(3)= T3(3)=4。
8.1 概述
OD矩阵
������ OD矩阵反映了各种方式的交通需求在不同时段 在进行交通分配之前，需要将OD矩阵的单位转换为 交通量或运量的单位（如出行次数转换为车辆数）。 此外还需要进行时段的转换（如全日OD矩阵转换为 高峰小时OD矩阵）。