8.1概述8.2交通流分配的基本概念8.3 路网最短路算法8.4 路段和交叉口的通行能力 第八章 交通分配基础 交通分配是“四阶段”交通需求预测法的最后一个环节所谓交通分配就是将各种出行方式的空间OD量分配到具体的交通网络上本课程的重点、难点、核心问题之一基础知识：最优化理论、图论、计算机技术8.18.1概述概述 通过交通分配所得到的路段、交叉口交通量资料是检验道路规划网络是否合理的主要依据之一进行交通分配的前提条件是:◦已知OD交通量，高峰期OD 交通量或年平均日交通量（AADT）；◦网络图；◦路径选择原则，分为线路固定类型和线路不固定类型；◦网络中各路段的走行时间（或走行时间函数） 两种机制：系统用户试图通过在网络上选择最佳行驶路线来达到自身出行费用最小的目标；路网服务水平与系统被使用的情况密切相关，道路上的车流量越大，用户遇到的阻力越高，运营方试图通过服务使得系统资源利用效率最高交互作用结果：路网上的流量分布系统用户运营方路网服务水平选择反馈平衡平衡 交通流分配问题= 网络环境下的径路选择问题交通流分配理论的产生与发展◦全有全无0-1(All-or-Nothing)的最短路径方法◦Dail (Multi-Route)的多径路选择方法◦基于Logit模型(Multi-Route)的多径路选择方法◦J. G. Wordrop：第一、第二平衡原理(1952)◦Beckmann：数理规划表示(1956)◦LeBlanc：将Frank-Wolfe法用于求解数理规划模型(1975)◦Daganzo, Sheffi(1977)：随机 一、路阻函数或交通阻抗函数(Cost Function)◦1.路段上的阻抗路段： ta=f(qa)美国联邦道路局(Bureau of Public Road，BPR)开发的BPR函数：式中 ： ta—路段a上的阻抗； t0—零流阻抗，即路段上为无流量状态时车辆自由行驶所需要的时间； qa — 路段a上的交通量； ca—路段a的实际通过能力，即单位时间内路段实际可通过的车辆数； α、β—阻滞系数，在美国公路局 交通分配程序中， α、β参数的取值分别为 α=0.15、 β =4。
也可由实际数据用回归分析求得8.28.2交通流交通流分配的基本概念分配的基本概念 理想的路段阻抗函数应该具备下列的性质： ◦(1)真实性；◦(2)单调递增；◦(3)连续可微；◦(4)允许一定的“超载” ；◦(5)阻抗函数应该具有很强的移植性 2、节点处的阻抗 ◦1958年英国TRRL（Transport and Road Research Laboratory ）研究所式中 ：T—信号周期长度； λ —进口道有效绿灯时间与信号周期长度之比，即绿信比； Q— 进口道的交通流量； X— 饱和度，X=Q/ S，S为进口道通行能力上式由F.V. Webster 提出 (公式适用范围X<0.67)在具体分配过程中，由路段行驶时间及交叉口延误共同组成出行交通阻抗 Wardrop第一平衡原理：每个OD对的各条被使用的径路具有相等而且最小的行驶时间；没有被使用的径路的行驶时间大于或等于最小行驶时间用户平衡( User Equilibrium，UE) ◦前提条件：准确完备的信息、理智的选择行为Wardrop第二平衡原理：在系统平衡条件下，拥挤的路网上交通流应该按照平均或总的出行成本最小为依据来分配。
系统最优原理（System Optimization，SO）二二、、交通平衡问题交通平衡问题 （一）径路与最短径路定义（一）径路与最短径路定义1.路段：交通网络上相邻两个节点之间的交通线路称作“路段”2.径路：交通网络上任意一OD点对之间，从发生点到吸引点一串连通的路段的有序排列叫做这一OD点对之间的径路3.最短径路：一对OD点之间的径路中总阻抗最小的径路叫“最短径路”三、径路与最短径路三、径路与最短径路径路1径路2径路1OD 一、Dijkstra法二、矩阵迭代法三、最短径路辨识8.3 8.3 路网最短路算法路网最短路算法 Dijkstra在1959年首先提出，也称为标号法（Label-correcting Method）常用于计算从某一指定点（起点）到另一指定点（终点）之间的最小阻抗Dijkstra法可以同时求出网络中所有节点到某一节点的全部最小阻抗一、一、DijkstraDijkstra算法（标号法）算法（标号法） (1)算法思想◦①首先从起点O开始，给每个节点一个标号,分为T标号和P标号两类；T标号是临时标号，表示从起点O到该点的最短路权的上限；P标号是固定标号，表示从起点O到该点的最短路权。
◦②标号过程中，T标号一直在改变，P标号不再改变，凡是没有标上P标号的点，都标上T标号◦③算法的每一步把某一点的T标号改变为P标号，直到所有的T标号都改变为P标号即得到从始点O到其他各点的最短路权，标号过程结束 (2)算法步骤Step1， 初始化：◦给起点1标上P标号P(1)=0，其余各点均标上T标号T1(j)=∞，j=2,3,…, n即表示从起点1到1的最短路权为0，到其他各点的最短路权的上限临时定为∞标号中括号内数字表示节点号，下标表示第几步标号经过第一步标号得到一个P标号P(1)=0Step2， 设经过了（k -1）步标号，节点i是刚得到P标号的点，则对所有没有得到P标号的点进行下一步新的标号（第k步）；考虑所有与节点i相邻且没有标上P标号的点{j}，修改它们的T标号：式中： dij— i到j的距离（路权）； Tk(j)—第k步标号前j点的T标号 ◦在所有的 T标号（包括没有被修改的）中，比选出最小的T标号Tk(j0)：式中： j0 —最小T标号所对应的节点号； T(r)—与i点不相邻点r的T标号◦给点j0标上P标号：P(j0)=Tk(j0) ，第k步标号结束。
Step3，当所有节点中已经没有T标号，算法结束，得到从起点1到其他各点的最短路权；否则返回步骤2 【【 例例题题 8-1】】用 Dijkstra法计算下图8-1所示路网从节点1到节点9的最短径路 解：step1 给定起点1的P标号：P(1)=0，其他节点标上T标号：T1(2)=…= T1(9)=∞step2 节点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,3,4…9 ）中，找出最小标号2、4为最小，任选其一，如选节点2，即P(2)= T2(2)= 2 step 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)+d25 ]=min[∞ ,2+2]=4 在所有 T标号（点3,4,5…9）中，节点4为最小，给节点4标上P标号，即P(4)= T2 (4)=2。
step 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标号(点3, 5…9)中，节点5为最小，给节点5标上P标号，即P(5)=T4(5)=3 step 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, 6…9)中，节点3为最小，给节点3标上P标号，即P(3)=T3(3)=4 step 6 节点3 刚得到P标号节点6与3相邻，且为T标号，修改6的T标号： ◦T6(6)=min[T(6),P(3)+d36 ]=min[4,4+2]=4 在所有 T标号(点6…9)中，节点6为最小，给节点6标上P标号，即P(6)=T6(6)=4 step 7 节点6 刚得到P标号节点9与6相邻，且为T标号，修改9的T标号： ◦T7(9)=min[T(9),P(6)+d69 ]=min[∞,4+2]=6 在所有 T标号(点7,8,9)中，节点7为最小，给节点7标上P标号，即P(7)=T4(7)=4。
step 8 节点7 刚得到P标号节点8与7相邻，且为T标号，修改8的T标号： ◦T8(8)=min[T(8),P(7)+d78 ]=min[5,4+2]=5 在所有 T标号(点8,9)中，节点8为最小，给节点8标上P标号，即P(8)=T8(8)=5 step 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 所有节点均标上了 P标号,计算结束得到节点1到其他各节点的最短路权（P标号），如表8-1所示 最短径路为1->4->5->6->9节点 1 2 3 4 5 6 7 8 9 P0 2 4 2 3 4 4 5 6 P标号 P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9) 表 8-1 例题8-1计算结果 （ 1）算法思想： ◦① 是借助距离（路权）矩阵的迭代运算来求解最短路权的算法 ◦② 该方法能一次获得任意两点之间的最短路权矩阵二、矩阵迭代算法二、矩阵迭代算法 （ 2）算法步骤： ① 首先构造距离矩阵（以距离为权的权矩阵）。
② 矩阵给出了节点间只经过一步（一条边）到达某一点的最短距离 ③ 对距离矩阵进行 如下的迭代运算，便可以得到经过两步达到某一点的最短距离：◦式中 ： n—网络节点数； ◦*—矩阵逻辑运算符； ◦dik ，dkj—距离矩阵 D 中的相应元素 k=1,2,3，…,n） 【例题 8-2】求解例题 8 -1网络任节点间的最短路权 ◦【 解 】 ： ◦(1) 根据交通网络结构，距离矩阵表示如下表 8-2 交通网络的距离矩阵 （2）进行矩阵迭代运算（第2步）◦d122 =min[d11 +d12 , d12 + d22, d13 + d32 , d14 + d42 , d15 + d52 , d16 + d62 , d17 + d72 , d18 + d82 , d19 + d92 ] =min[0+2,2+0,∞+2,2+∞,∞+2,∞+∞,∞+∞, ∞+∞, ∞+∞]=2 (i=1,j=2;k=1,2，…9) ◦d132 、 d142 、 d152 … d192计算同理从节点1经过两步到达5的最短路权为3其他元素按同样方法计算，得到 D2 （3）进行矩阵迭代运算 经过三步到达某一节点的最短距离为：◦D3 = D2 *D=[dij3 ] ◦[dij3 ] =min[dik2 +dkj ] （k=1,2,3，…,n） 式中 ：dik2— 距离矩阵 D2 中的元素 ； dkj— 距离矩阵 D 中的元素。
（4）进行矩阵迭代运算（第 m 步） 经过 m 步到达某一节点的最短距离为： ◦Dm = Dm-1 *D=[dijm] ◦[dijm] =min[dikm-1 +dkj] （k=1,2,3，…,n） 式中 ： dikm-1—距离矩阵Dm-1中的元素 ； dkj — 距离矩阵 D 中的元素 迭代不断进行 ， 直到Dm =Dm-1 即Dm中的每个元素等于Dm-1中的每个元素为止，此时的Dm便是任意两点之间的最短路权矩阵本例中， D8 = D9 ， 如表8-3所示：用矩阵迭代法求解网络的最短路，能够一次获得 n×n 阶的最短路权矩阵，简便快速软件的开发比 Dijkstra 方法节省内存网络越复杂，该方法的优越性越明显 通过Dijkstra算法或矩阵迭代法得到最短路权矩阵后，还需要把每一个节点对之间具体的最短径路寻找出来，将交通流分配上去，进而进行网络的规划最短径路辨识采用追踪法：从每条最短径路的起点开始，根据起点到各节点的最短路权搜索最短径路上的各个交通节点，直至径路终点三、最短径路辨识三、最短径路辨识 算法思想：设某最短径路的起点是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的最短路线 【例 题 8-3】： 辨识出例 题 8-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.4 8.4 路段和交叉口的通行能力路段和交叉口的通行能力 道路路段的通行能力分析计算包括◦单车道路段理论通行能力分析计算；◦单车道路段可能通行能力分析计算；◦多车道道路通行能力的计算。
交叉口的通行能力分析计算包括◦信号控制交叉口的通行能力分析计算；◦无控交叉口的通行能力分析计算； 。