19
最短路权计算方法
最短路权计算是指计算出给定节点或任意节点间的 最短路长度（时间、距离或费用）。 1、Dijkstra算法 Dijkstra 在1959年首先提出，称为标号法。 常用于计算从某一指定点（起点）到另一指定（终 点）之间的最短路权。 2、矩阵迭代法（逐次逼近算法） 是借助距离（路权）矩阵的迭代运算来求解最短路 权的算法。能一次获得任意两点之间的最短路权。
2、节点处的阻抗
车辆在交通网络节点处主要指在交叉口处的阻抗。 交叉口阻抗与交叉口的型式，信号控制系统的配时， 交叉口的通行能力等因素有关。 在城市交通网络的实际出行时间中，除路段行驶时间 外，交叉口延误占有较大的比重，特别是在交通高峰 期间，交叉口延误可能会超过路段行驶时间。 已有的城市道路交通流分配理论一直忽略节点阻抗这 个问题，只借用从城市间公路上获得的行驶时间BPR 函数作为城市道路网上的阻抗，只计算路段上的阻 抗。
9
确定性分配能够较好的反映网络的拥挤性，随机性 分配能够较好地反映出行选择行为的随机性，但是 要真正地符合路网实际情况，还有更重要更基本的 交通需求的时变性需要反映出来。 也就是说，需要一种交通流分配方法能够将路网上 交通流的拥挤性、路径选择的随机性、交通需求的 时变性综合集成地刻画反映出来，这正是研究交通 问题的人们一直积极探索的问题。
27
矩阵迭代法例题：
3、进行矩阵迭代运算（第3步） 经过三步到达某一节点的最短距离为： D3= D2 *D=[d3ij] [d3ij] =min[d2ik+dkj] 式中：d2ik d2kj k=1,2,3…,n ---距离矩阵D2中的元素； ---距离矩阵D2中的元素。
28
矩阵迭代法例题
4、进行矩阵迭代运算（第m步） 经过m步到达某一节点的最短距离为： Dm= Dm-1 *D=[dmij] [dmij] =min[dm-1ik+dkj] k=1,2,3…,n 式中：dm-1ik ---距离矩阵Dm-1中的元素； dkj ---距离矩阵D中的元素。 l 迭代不断进行，直到： Dm= Dm-1。即：
8 9
7 4 5 6 2 3 4 0 2 4
25
矩阵迭代法例题：
2、进行矩阵迭代运算（第2步） d212=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) d213、 d214、 d215….. D219计算同理，如d215：
4
l
所以在1952年，著名交通问题专家Wardrop提 出了网络平衡分配的第一、第二定理，人们开 始采用系统分析方法和平衡分析方法来研究交 通拥挤时的交通流分配，带来了交通流分配理 论的一次大的飞跃。
5
首先，人们进行了确定性的分配研究，其前提是假 设出行者能够精确计算出每条径路的阻抗，从而能 作出完全正确的选择决定，且每个出行者的计算能 力和水平是相同的。 可见确定性分配反映了网络的拥挤特性，反映了路 阻随流量变化的实际，该方法是一次理论的进步。
第八章 交通流分配(Traffic Assignment)
主要内容: 第一节 概述 第二节 交通流分配中的基本概念 第三节 非平衡分配方法 第四节 平衡分配方法 第五节 随机分配方法 第六节 动态交通流分配
1
交通流分配的含义
将预测获得机动车OD交通量，按照一定的规 则，符合实际地分配到路网的各条道路上，并 求出各条道路的交通量。
美国道路局(BPR—Bureau of public road)开发 的函数，被称为BPR函数，形式为:
qa b t =t [1+a ( ) ] a 0 c a
式中： t ­­­­ ：路段a上的阻抗； a t ­­­­ ：零流阻抗，即路段上为空静状态时车 0 辆自由行驶所需要的时间； q ­­­­： 路段a上的交通量； a c ­­­­ ：路段a的实际通行能力，即单位时间内 a 路段实际可通过的车辆数； a、b：­­­­­阻滞系数。在美国公路局交通分配 程序中， a、b参数的取值分别为 a=0.15、b=4。也 可由实际数据用回归分析求得。
20
最短路计算方法2：矩阵迭代法
算法基本介绍：
l 是借助距离（路权）矩阵的迭代运算来求
解最短路权的算法。
l 该方法能一次获得任意两点之间的最短路
权矩阵。
21
矩阵迭代法算法思想： 矩阵迭代法算法思想：
1. 首先构造距离矩阵（以距离为权的权矩阵） 2. 矩阵给出了节点间只经过一步（一条边）到 达某一点的最短距离 3. 对距离矩阵进行如下的迭代运算，便可以得 到经过两步达到某一点的最短距离：
26
矩阵迭代法例题：
d215=min[d11+d15,d12+d25,d13+d35,d14+d45,d15 +d55,d16+d65,d17+d75,d18+d85,d19+d95] =min[0+∞,2+2,∞+∞,2+1,∞+0,∞+1, ∞+∞,∞+2,∞+∞]=3 (i=1,j=5;k=1,2…9) 从节点1经过两步到达5的最短路权为3。 其它元素按同样方法计算，得到D2
进行交通流分配时所需要的基本数据有：
（1）表示需求的OD交通量出行矩阵。在拥挤的 城市道路网中通常采用高峰期OD交通量出行矩 阵，在城市间公路网中通常采用年平均日交通量 （AADT）的OD交通量出行矩阵； （2）路网定义，即路段及交叉口特征和属性数 据，同时还包括其时间—流量函数； （3）径路选择原则。
6
l
但是，进一步研究实际网络中出行者的出行行 为发现，现实中出行者对路段阻抗的掌握只能 是估计而得。对同一路段，不同出行者的估计 值不会完全相同，因为出行者的计算能力和水 平是各异的。
7
所以，在1977年，对交通流分配理论研究最积极、 活跃的美国加州大学伯克利分校的Daganzo教授及麻 省理工学院的Sheffi教授提出了随机性分配的理论， 其前提是认为出行者对路段阻抗的估计值与实际值 之间的差别是一个随机变量，出行者会在“多条径 路”中选择，同一起迄点的流量会通过不同的径路到 达目的地。 随机性分配理论和方法的提出，在拟合、反映现实 交通网络实际的进程中又推进了一大步。
29
矩阵迭代法例题
Dm中的每个元素等于 Dm-1 中的每个元素为 止，此时的Dm便是任意两点之间的最短路权矩阵。
l
本例中， D8 = D9，如下所示：
i\j 1 2 3 4 5 6 7 8 9 1 0 2 4 2 3 4 4 5 6 2 2 0 2 3 2 3 5 4 5 距离矩阵 D , D 3 4 5 6 4 2 3 4 2 3 2 3 0 4 3 2 4 0 1 2 3 1 0 1 2 2 1 0 6 2 3 4 5 3 2 3 4 4 3 2
2 2
2
2
2
3
2
4
2
1
5
2
1
6
2
7
2
8
2
9
24
矩阵迭代法例题：
解： 1. 距离矩阵如下：
i\j 1 2 3 4 5 6 7 8 9 1 0 2 ∞ 2 ∞ ∞ ∞ ∞ ∞ 2 2 0 2 ∞ 2 ∞ ∞ ∞ ∞ 3 ∞ 2 0 ∞ ∞ 2 ∞ ∞ ∞ 4 2 ∞ ∞ 0 1 ∞ 2 ∞ ∞ 5 ∞ 2 ∞ 1 0 1 ∞ 2 ∞ 6 ∞ ∞ 2 ∞ 1 0 ∞ ∞ 2 7 ∞ ∞ ∞ 2 ∞ ∞ 0 2 ∞ 8 ∞ ∞ ∞ ∞ 2 ∞ 2 0 2 9 ∞ ∞ ∞ ∞ ∞ 2 ∞ 2 0
22
矩阵迭代法算法思想：
D2=D*D=[d2ij] [d2…,n 式中： n---网络节点数； *---矩阵逻辑运算符； dik，dkj ---距离矩阵D中的相应元素。
23
矩阵迭代法例题：
例题1：求下图所示网络中任意节点间的最 短路权
1
11
(1)可以是将现状OD交通量分配到现状交通网络 上，以分析目前交通网络的运行状况，如果有某些 路段的交通量观测值，还可以将这些观测值与在相 应路段的分配结果进行比较，以检验四阶段预测模 型的精度。 (2)也可以是将规划年OD交通量分布预测值分配到 现状交通网络上，以发现对规划年的交通需求来 说，现状交通网络的缺陷，为后面交通网络的规划 设计提供依据。 (3)还可以是将规划年OD交通量分布预测值分配到 规划交通网络上，以评价交通网络规划方案的优 劣。
18
（二）最短径路算法
最短径路算法是交通流分配中最基本也最重要的算法，几乎 所有交通流分配方法都是以它作为一个基本子过程反复调 用。 最短径路算法的设计问题是图论、运筹学和交通规划领域的 学者们广为关注的问题，因此已经设计出了多种方法。 最短路算法问题包含两个子问题：两点间最小阻抗的计算和 两点间最小阻抗径路的辨识，前者是解决后者的前提。 许多算法都是将这两个子问题分开考虑，设计出来的算法是 分别单独求出最小阻抗和最短径路。
8
然而，随着近年来交通拥挤的进一步加重和拥挤 在时间和空间范围上的扩大，以及智能交通系统 (ITS)研究的进展，人们在由注意新路网的规划设 计逐步转向重视既有路网的管路控制的进程中。 更加意识到：路网上的拥挤性、路径选择的随机 性、交通需求的动态性是同时存在并交互作用 的，其机理是纷繁复杂的。
2
第一节 概述
• 人们当初进行交通流分配的研究时，多采用全 有全无(all­or­nothing)的最短路径方法，该方 法处理的是非常理想化的城市交通网络，即假 设网络上没有交通拥挤，路阻是固定不变的， 一个OD对间的流量都分配在“一条径路”，即最 短径路上。