第08章 交通分配基础

长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院第八章交通分配基础长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院8.1 交通分配的概念交通分配的概念 v 交通分配是交通分配是“四阶段四阶段”交通需求预测法的最后一个环节，所谓交交通需求预测法的最后一个环节，所谓交通分配就是将各种出行方式的空间通分配就是将各种出行方式的空间OD量分配到具体的交通网络量分配到具体的交通网络上，通过交通分配所得到的路段、交叉口交通量资料是检验道路上，通过交通分配所得到的路段、交叉口交通量资料是检验道路规划网络是否合理的主要依据之一。规划网络是否合理的主要依据之一。v 进行交通分配的前提条件是进行交通分配的前提条件是已知已知OD交通量、网络图和网络中各交通量、网络图和网络中各路段的走行时间（或走行时间函数）路段的走行时间（或走行时间函数）。v 对于各种出行方式的对于各种出行方式的OD量的获取已在量的获取已在“Chap04Chap07章章”中中获得了很好的解决，本章主要讨论交通网络的计算机表示方法、获得了很好的解决，本章主要讨论交通网络的计算机表示方法、交通阻抗分析和路网最短路算法道路等交通分配的基础问题。下交通阻抗分析和路网最短路算法道路等交通分配的基础问题。下章再讨论交通分配的模型和算法。章再讨论交通分配的模型和算法。 长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院8.2 交通网络的计算机表示交通网络的计算机表示 v 交通网络的抽象即是把交通网络抽象为点（交叉口）与边（路段）交通网络的抽象即是把交通网络抽象为点（交叉口）与边（路段）的集合，节点一般代表道路网络中道路的交叉点以及交通小区的的集合，节点一般代表道路网络中道路的交叉点以及交通小区的形心，边则代表在两点之间存在一条道路。形心，边则代表在两点之间存在一条道路。v 对交通网络进行计算机处理，常用的方法有：对交通网络进行计算机处理，常用的方法有：关联矩阵法、邻接关联矩阵法、邻接矩阵法、权矩阵法、边编目录法和邻接目录表法矩阵法、权矩阵法、边编目录法和邻接目录表法5种种。 长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院8.2.1 关联矩阵法关联矩阵法 v 关联矩阵表示的是节点和边之间的关联情况。关联矩阵表示的是节点和边之间的关联情况。v 关联矩阵的每一列仅有两个元素为关联矩阵的每一列仅有两个元素为1，其余元素全部为，其余元素全部为0。因此，利。因此，利用此种方法来存储网络信息，效率不高，浪费的计算机内存空间大。用此种方法来存储网络信息，效率不高，浪费的计算机内存空间大。其它是相关联的和边如果节点01jiijg64111000010110001101100011G长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院8.2.2 邻接矩阵法邻接矩阵法 v 邻接矩阵是一个方阵，其元素表示的是网络中节点与节点之间的邻接矩阵是一个方阵，其元素表示的是网络中节点与节点之间的一般邻接关系。一般邻接关系。v 有效元素（非零元素）的比例在提高，但矩阵中绝大部分的元素有效元素（非零元素）的比例在提高，但矩阵中绝大部分的元素仍为仍为0，是个稀疏矩阵，存储时要浪费大量的计算机内存空间。，是个稀疏矩阵，存储时要浪费大量的计算机内存空间。 之间有边连接与节点节点之间无边连接或与节点节点jijijiijl10440111101111011110L长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院8.2.3 权矩阵法权矩阵法 间有边直接相连与节点节点给定权间无边直接连接与节点节点jijiijwji 0770232081038061106041402312061360D长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院8.2.4 边编目录法边编目录法 长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院8.2.5 邻接目录表法邻接目录表法 长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院8.3 道路交通阻抗分析道路交通阻抗分析 v 交通阻抗是指交通网络上路段或路径之间的运行距离、时间、费交通阻抗是指交通网络上路段或路径之间的运行距离、时间、费用或这些因素的综合。用或这些因素的综合。v 交通阻抗通常由两部分组成：路段上的阻抗、节点处的阻抗。交通阻抗通常由两部分组成：路段上的阻抗、节点处的阻抗。v 在诸多交通阻抗因素中，时间因素是最主要的。在诸多交通阻抗因素中，时间因素是最主要的。v 有些交通网络，路段上的走行时间与距离成正比，与路段上的流有些交通网络，路段上的走行时间与距离成正比，与路段上的流量无关，如城市轨道交通网；有些交通网络，路段上的走行时间量无关，如城市轨道交通网；有些交通网络，路段上的走行时间与距离不一定成正比，与路段上的交通流量有关，此时应选用时与距离不一定成正比，与路段上的交通流量有关，此时应选用时间作为阻抗。间作为阻抗。v 道路交通阻抗分析就是确定路段走行时间（交叉口延误）与路段道路交通阻抗分析就是确定路段走行时间（交叉口延误）与路段（交叉口）交通负荷之间的函数关系。（交叉口）交通负荷之间的函数关系。 长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院8.3.1 常用的路段特性函数常用的路段特性函数 路段特性函数的一般形式路段特性函数的一般形式v 当流量充分小时，行程时间接近于平均当流量充分小时，行程时间接近于平均“零流量零流量”行程时间。行程时间。v 在流量远小于道路的通行能力时，流量的缓慢变化导致行程时间在流量远小于道路的通行能力时，流量的缓慢变化导致行程时间的缓慢变化。的缓慢变化。v 在在“稳态稳态”系统状态下，曲线变成饱和流量纵坐标的渐近线。系统状态下，曲线变成饱和流量纵坐标的渐近线。v 另外，在函数的构造上，还要求其满足单调递增、连续可微性，另外，在函数的构造上，还要求其满足单调递增、连续可微性，同时对模型参数也要求易于标定。同时对模型参数也要求易于标定。()aatf q长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院 常用的路段特性函数模型常用的路段特性函数模型 v 模型模型1（BPR模型）模型）0()1() aaaaaqtqtC1212012121()() aaaaaaqqttCC12012121()()aaaaaaqqttCC长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院v 模型模型2（Davidson模型）模型）v 模型模型3（TRRL模型）模型）0(1)aaaaaqttjCq 1638/49.90.163 (430) ()aaaaaaaaLLtVkm hVqWR 3256/67.60.123 (1000) ()aaaaaaaaLLtVkm hVqWR长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院v 模型模型4（中国交通部模型）（中国交通部模型）v 模型模型5v 模型模型6aaVqaaaaaLLtqVaaaaaLLtVq)1 (fjVVKKmfqqVV112136001112aafaamaLtVqq长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院8.3.2 常用的交叉口延误模型常用的交叉口延误模型 信号交叉口延误计算模型信号交叉口延误计算模型 v 模型模型1 21ddd)1 ()1 (38. 021xTd )(16) 1() 1(173222TxxxxdTgCqx 长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院v 模型模型2v 模型模型3v 模型模型4)1 (2)1 (2xTd)1 (23600)1 (2)1 (22xqxxTd)1 (23600)1 (2)1 ()1 (2)1 (222xqxxTxTd长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院v 模型模型5（Webster延误）延误）v 模型模型6)52(31222)(65. 0)1 (2)1 (2)1 (xqTxqxxTdqxQxTd02)1 (2)1 (0000 0 1)(5 . 1xxxxxxxQ60067. 00Sgx长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院 其它类型交叉口延误计算方法其它类型交叉口延误计算方法 )(1)(信号无控ijijdkd)(2)(信号环交ijijdkd)(3)(信号立交ijijdkd长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院8.3.3 路权的计算路权的计算 v 交通分配中的路权等于路段行驶时间与交叉口延误之和。交通分配中的路权等于路段行驶时间与交叉口延误之和。8.3.4 节点带权路网的描述节点带权路网的描述 v 当存在交叉口转向延误或交叉口转向限制时，对于路网的连通性当存在交叉口转向延误或交叉口转向限制时，对于路网的连通性要重新进行描述，常用的方法有增设虚拟边法和对偶图法。要重新进行描述，常用的方法有增设虚拟边法和对偶图法。ijijijTtd长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院 增设虚拟边法增设虚拟边法 v 基本思想是将每个交叉口扩展为一个子网络，即增加虚拟节点和基本思想是将每个交叉口扩展为一个子网络，即增加虚拟节点和虚拟边。一个虚拟节点对应到交叉口的一个进口或出口方向，连虚拟边。一个虚拟节点对应到交叉口的一个进口或出口方向，连接虚拟节点的一条虚拟边对应到交叉口的一个可能转向，其边权接虚拟节点的一条虚拟边对应到交叉口的一个可能转向，其边权则对应到相应的转向延误。则对应到相应的转向延误。v 优点：能解决转向延误和转向限制问题，可以利用现有的最短路优点：能解决转向延误和转向限制问题，可以利用现有的最短路算法。算法。v 缺点：要增加大量的虚拟节点和虚拟边，而大量虚拟节点和虚拟缺点：要增加大量的虚拟节点和虚拟边，而大量虚拟节点和虚拟边的增加又导致问题规模的剧增，对于大型网络这种存储空间和边的增加又导致问题规模的剧增，对于大型网络这种存储空间和运行时间上的额外开销是无法承受的。运行时间上的额外开销是无法承受的。长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院 对偶图法对偶图法 v 对偶图法的实质是进行节点和边的相互转化来表达网络的连通性。对偶图法的实质是进行节点和边的相互转化来表达网络的连通性。在进行边转化为节点时，原图中的一条边就转化为对偶图中的一在进行边转化为节点时，原图中的一条边就转化为对偶图中的一个节点；而在节点转化为边时，则需要根据网络的连通性而定。个节点；而在节点转化为边时，则需要根据网络的连通性而定。v 通过转化得到的对偶图有通过转化得到的对偶图有2个主要特性。个主要特性。n 对偶图中的对偶节点代表了原图中的边，并保持了原图中边对偶图中的对偶节点代表了原图中的边，并保持了原图中边的所有特性。如对偶节点包含了原图中边的起点、末点号信的所有特性。如对偶节点包含了原图中边的起点、末点号信息；对偶节点的权重对应原图中边的权重。息；对偶节点的权重对应原图中边的权重。n 对偶图中的对偶边代表了原图中邻接边之间的转向以及转向对偶图中的对偶边代表了原图中邻接边之间的转向以及转向的附属特征，如对偶边的权重对应到原转向的延误值等。的附属特征，如对偶边的权重对应到原转向的延误值等。长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院8.4 路网最短路算法路网最短路算法 v 最短路算法是交通分配的最基本算法。绝大部分的交通分配模型都以最短路最短路算法是交通分配的最基本算法。绝大部分的交通分配模型都以最短路交通分配为基础，并将其作为一个基本子过程反复调用。交通分配为基础，并将其作为一个基本子过程反复调用。v 最短路算法的设计合理与否，将直接影响到整个交通分配的运算效率。最短路算法的设计合理与否，将直接影响到整个交通分配的运算效率。v 最短路问题包含着两个子问题：一是网络中任意两个节点之间的最短路权计最短路问题包含着两个子问题：一是网络中任意两个节点之间的最短路权计算，另一是网络中任意两个节点之间的最短路径的辨识。算，另一是网络中任意两个节点之间的最短路径的辨识。长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院8.4.1 Dijkstra算法（标号法）算法（标号法） 适用条件适用条件 v 1959年提出，路权都必须为正，不允许出现负权。年提出，路权都必须为正，不允许出现负权。v 对无向网络，也可以按照此算法来执行，只不过认为各边都是可对无向网络，也可以按照此算法来执行，只不过认为各边都是可以双向行驶的路段。以双向行驶的路段。v 假定假定 P 是从是从 Vs 到到 Vt 的最短路，的最短路，Vi 是路线上的某一个节点，那么是路线上的某一个节点，那么从从 Vs 沿沿 P 到到 Vi 的路线就是从的路线就是从 Vs 到到 Vi 的最短路线。的最短路线。v 主要获得起点到终点之间的最短路，同时可以获得网络中其它某主要获得起点到终点之间的最短路，同时可以获得网络中其它某些节点与起点之间的最短路，但具体是哪些节点，事先并不知道。些节点与起点之间的最短路，但具体是哪些节点，事先并不知道。 长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院 算法简介算法简介 v 计算从某一指定节点到另一指定节点之间的最短路计算从某一指定节点到另一指定节点之间的最短路n 算法首先从源点开始，给每一个节点记一标号，标号分为算法首先从源点开始，给每一个节点记一标号，标号分为 P 标号和标号和 T 标号两种，标号两种，T 标号表示从源点到该点的最短路权的标号表示从源点到该点的最短路权的上界（临时标号）；上界（临时标号）； P 标号表示从源点到该点的最短路权，标号表示从源点到该点的最短路权，又称固定标号。在标号过程中，又称固定标号。在标号过程中，T 标号一直在改变，已得到标号一直在改变，已得到 P 标号的节点其标号不再改变，凡是没有标上标号的节点其标号不再改变，凡是没有标上 P 标号的节点，标号的节点，都标上都标上 T 标号。算法每执行一步，将把某一节点的标号。算法每执行一步，将把某一节点的 T 标号改标号改变为变为 P 标号，当终点获得标号，当终点获得 P 标号时，标号过程结束。标号时，标号过程结束。 v 计算从某一指定节点到网络中其它所有节点之间的最短路计算从某一指定节点到网络中其它所有节点之间的最短路 n 前面的过程相同。经过有限步运算之后，当把所有的前面的过程相同。经过有限步运算之后，当把所有的 T 标号标号都改变成都改变成 P 标号，即获得了从源点到网络中任一节点的最短标号，即获得了从源点到网络中任一节点的最短路，标号过程结束。路，标号过程结束。 长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院 算法描述算法描述 长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院 算例算例 求求V1V6的最短路。的最短路。求求V1V7的最短路。的最短路。长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院8.4.2 矩阵迭代算法矩阵迭代算法 v 矩阵迭代法是一种借助于权矩阵迭代运算来求解最短路权和最短矩阵迭代法是一种借助于权矩阵迭代运算来求解最短路权和最短路径的算法，利用该算法可以很简单地获得交通网络中任意路径的算法，利用该算法可以很简单地获得交通网络中任意2个个节点之间的最短路权（径）。节点之间的最短路权（径）。v 该算法的基本思想是，记初始的权矩阵为该算法的基本思想是，记初始的权矩阵为 D，该矩阵经过若干次，该矩阵经过若干次迭代运算后满足终止条件，那么迭代运算后满足终止条件，那么 D*中的每个元素中的每个元素 dij 则表示从节则表示从节点点 i 到节点到节点 j 的最短路权，基于矩阵的最短路权，基于矩阵 D*通过前向（后向）搜索可通过前向（后向）搜索可获得最短路径。获得最短路径。 v 基本思想：不是直接考虑从节点基本思想：不是直接考虑从节点 i 到节点到节点 j 的最短路，而是考虑的最短路，而是考虑经过中间某个节点经过中间某个节点 k 后，距离是否有所减少。后，距离是否有所减少。 nkmkjdmikdmijd 321) 1() 1(min)(，( )(1)stopmmDD！长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院算法特点算法特点 v 当网络中存在负权时，可以用该算法来计算。当网络中存在负权时，可以用该算法来计算。v 采用矩阵迭代法来计算最短路权，可一次性地获得阶最短路权矩采用矩阵迭代法来计算最短路权，可一次性地获得阶最短路权矩阵，并且同阵，并且同Dijkstra算法相比更节省内存，计算速度更快。算法相比更节省内存，计算速度更快。v 对于复杂网络迭代次数比简单网络多；对于无向网络迭代次数比对于复杂网络迭代次数比简单网络多；对于无向网络迭代次数比有向网络多。有向网络多。v 矩阵迭代法易获得最短路权，但不易获得最短路径。矩阵迭代法易获得最短路权，但不易获得最短路径。 长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院算例：用距离矩阵迭代算法求各节点之间的最短路权。算例：用距离矩阵迭代算法求各节点之间的最短路权。 0327041050D长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院最短路径的搜索最短路径的搜索 v 使用矩阵迭代法运算时，不仅可以获得最短路权矩阵，同时还可使用矩阵迭代法运算时，不仅可以获得最短路权矩阵，同时还可以获得网络中任意以获得网络中任意2个节点之间的最短路径。个节点之间的最短路径。v 最短路径的获得采用搜索法，即从每条最短路线的起点开始，根最短路径的获得采用搜索法，即从每条最短路线的起点开始，根据起点至各节点的最短路权搜索最短路径上的各交通节点，直至据起点至各节点的最短路权搜索最短路径上的各交通节点，直至路径终点。路径终点。v 也可以采用反向搜索法，即从终点搜索到起点以获得最短路径。也可以采用反向搜索法，即从终点搜索到起点以获得最短路径。 长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院算例：算例：0310213204140610160310023207 756 11 956643866963511 6 8594 69D求求V1V7的最短路？的最短路？长沙理工大学交通运输工程学院长沙理工大学交通运输工程学院8.5 路段和交叉口的通行能力路段和交叉口的通行能力 v 道路路段的通行能力分析计算包括道路路段的通行能力分析计算包括n 城市道路路段通行能力分析计算；城市道路路段通行能力分析计算；n 高速公路基本路段通行能力分析计算；高速公路基本路段通行能力分析计算；n 高速公路交织区通行能力分析计算；高速公路交织区通行能力分析计算；n 高速公路匝道与主线连接点通行能力分析计算；高速公路匝道与主线连接点通行能力分析计算；n 双车道公路路段通行能力分析计算等。双车道公路路段通行能力分析计算等。v 交叉口的通行能力分析计算包括交叉口的通行能力分析计算包括n 信号控制交叉口的通行能力分析；信号控制交叉口的通行能力分析；n 无控交叉口的通行能力分析；无控交叉口的通行能力分析；n 环形交叉口的通行能力分析；环形交叉口的通行能力分析；n 立体交叉口的通行能力分析等。立体交叉口的通行能力分析等。