第08章交通分配基础

长沙理工大学交通运输工程学院第八章交通分配基础长沙理工大学交通运输工程学院8.1交通分配的概念交通分配是“四阶段”交通需求预测法的最后一个环节，所谓交通分配就是将各种出行方式的空间OD量分配到具体的交通网络上，通过交通分配所得到的路段、交叉口交通量资料是检验道路规划网络是否合理的主要依据之一。进行交通分配的前提条件是已知OD交通量、网络图和网络中各路段的走行时间（或走行时间函数）。对于各种出行方式的OD量的获取已在“Chap04～Chap07章”中获得了很好的解决，本章主要讨论交通网络的计算机表示方法、交通阻抗分析和路网最短路算法道路等交通分配的基础问题。下章再讨论交通分配的模型和算法。长沙理工大学交通运输工程学院8.2交通网络的计算机表示交通网络的抽象即是把交通网络抽象为点（交叉口）与边（路段）的集合，节点一般代表道路网络中道路的交叉点以及交通小区的形心，边则代表在两点之间存在一条道路。对交通网络进行计算机处理，常用的方法有：关联矩阵法、邻接矩阵法、权矩阵法、边编目录法和邻接目录表法5种。长沙理工大学交通运输工程学院8.2.1关联矩阵法关联矩阵表示的是节点和边之间的关联情况。关联矩阵的每一列仅有两个元素为1，其余元素全部为0。因此，利用此种方法来存储网络信息，效率不高，浪费的计算机内存空间大。其它是相关联的和边如果节点01jiijg64111000010110001101100011G长沙理工大学交通运输工程学院8.2.2邻接矩阵法邻接矩阵是一个方阵，其元素表示的是网络中节点与节点之间的一般邻接关系。有效元素（非零元素）的比例在提高，但矩阵中绝大部分的元素仍为0，是个稀疏矩阵，存储时要浪费大量的计算机内存空间。之间有边连接与节点节点之间无边连接或与节点节点jijijiijl10440111101111011110L长沙理工大学交通运输工程学院8.2.3权矩阵法间有边直接相连与节点节点给定权间无边直接连接与节点节点jijiijwji0770232081038061106041402312061360D长沙理工大学交通运输工程学院8.2.4边编目录法边顺序号12345边起迄点（1,2）（2,3）（2,4）（1,3）（3,4）边顺序号6789边起迄点（1,5）（3,5）（5,4）（4,5）长沙理工大学交通运输工程学院8.2.5邻接目录表法234013501240135624674570560074V节点号i1234567NADJ(i)3334432NEAR(i,j)2,3,41,3,51,2,41,3,5,62,4,6,74,5,75,6长沙理工大学交通运输工程学院8.3道路交通阻抗分析交通阻抗是指交通网络上路段或路径之间的运行距离、时间、费用或这些因素的综合。交通阻抗通常由两部分组成：路段上的阻抗、节点处的阻抗。在诸多交通阻抗因素中，时间因素是最主要的。有些交通网络，路段上的走行时间与距离成正比，与路段上的流量无关，如城市轨道交通网；有些交通网络，路段上的走行时间与距离不一定成正比，与路段上的交通流量有关，此时应选用时间作为阻抗。道路交通阻抗分析就是确定路段走行时间（交叉口延误）与路段（交叉口）交通负荷之间的函数关系。长沙理工大学交通运输工程学院8.3.1常用的路段特性函数路段特性函数的一般形式当流量充分小时，行程时间接近于平均“零流量”行程时间。在流量远小于道路的通行能力时，流量的缓慢变化导致行程时间的缓慢变化。在“稳态”系统状态下，曲线变成饱和流量纵坐标的渐近线。另外，在函数的构造上，还要求其满足单调递增、连续可微性，同时对模型参数也要求易于标定。()aatfq长沙理工大学交通运输工程学院常用的路段特性函数模型模型1（BPR模型）0()[1()]aaaaaqtqtC121201212[1()()]aaaaaaqqttCC1201212[1()()]aaaaaaqqttCC长沙理工大学交通运输工程学院模型2（Davidson模型）模型3（TRRL模型）0(1)aaaaaqttjCq1638/49.90.163(430)()aaaaaaaaLLtVkmhVqWR3256/67.60.123(1000)()aaaaaaaaLLtVkmhVqWR长沙理工大学交通运输工程学院模型4（中国交通部模型）模型5模型6aaVqaaaaaLLtqVaaaaaLLtVq)1(fjVVKKmfqqVV112136001112aafaamaLtVqq长沙理工大学交通运输工程学院8.3.2常用的交叉口延误模型信号交叉口延误计算模型模型121ddd)1()1(38.021xTd])(16)1()1[(173222TxxxxdTgCqx长沙理工大学交通运输工程学院模型2模型3模型4)1(2)1(2xTd)1(23600)1(2)1(22xqxxTd)1(23600)1(2)1()1(2)1(222xqxxTxTd长沙理工大学交通运输工程学院模型5（Webster延误）模型6)52(31222)(65.0)1(2)1(2)1(xqTxqxxTdqxQxTd02)1(2)1(000001)(5.1xxxxxxxQ60067.00Sgx长沙理工大学交通运输工程学院其它类型交叉口延误计算方法)(1)(信号无控ijijdkd)(2)(信号环交ijijdkd)(3)(信号立交ijijdkd长沙理工大学交通运输工程学院8.3.3路权的计算交通分配中的路权等于路段行驶时间与交叉口延误之和。8.3.4节点带权路网的描述当存在交叉口转向延误或交叉口转向限制时，对于路网的连通性要重新进行描述，常用的方法有增设虚拟边法和对偶图法。ijijijTtd长沙理工大学交通运输工程学院增设虚拟边法基本思想是将每个交叉口扩展为一个子网络，即增加虚拟节点和虚拟边。一个虚拟节点对应到交叉口的一个进口或出口方向，连接虚拟节点的一条虚拟边对应到交叉口的一个可能转向，其边权则对应到相应的转向延误。优点：能解决转向延误和转向限制问题，可以利用现有的最短路算法。缺点：要增加大量的虚拟节点和虚拟边，而大量虚拟节点和虚拟边的增加又导致问题规模的剧增，对于大型网络这种存储空间和运行时间上的额外开销是无法承受的。长沙理工大学交通运输工程学院虚拟边虚拟节点图a图b长沙理工大学交通运输工程学院对偶图法对偶图法的实质是进行节点和边的相互转化来表达网络的连通性。在进行边转化为节点时，原图中的一条边就转化为对偶图中的一个节点；而在节点转化为边时，则需要根据网络的连通性而定。通过转化得到的对偶图有2个主要特性。对偶图中的对偶节点代表了原图中的边，并保持了原图中边的所有特性。如对偶节点包含了原图中边的起点、末点号信息；对偶节点的权重对应原图中边的权重。对偶图中的对偶边代表了原图中邻接边之间的转向以及转向的附属特征，如对偶边的权重对应到原转向的延误值等。长沙理工大学交通运输工程学院图a实际道路网络图b路网的一般表达方法1235412345图c对偶图的生成机制图d整理后的对偶图4-11-41-22-11-55-13-11-312543长沙理工大学交通运输工程学院图a实际道路网络图b路网的一般表达方法1235412345图c对偶图的生成机制图d整理后的对偶图4-11-41-22-11-55-13-11-312543长沙理工大学交通运输工程学院8.4路网最短路算法最短路算法是交通分配的最基本算法。绝大部分的交通分配模型都以最短路交通分配为基础，并将其作为一个基本子过程反复调用。最短路算法的设计合理与否，将直接影响到整个交通分配的运算效率。最短路问题包含着两个子问题：一是网络中任意两个节点之间的最短路权计算，另一是网络中任意两个节点之间的最短路径的辨识。记网络为(,)GVA，12{,,,}nVvvv为节点的集合，12{,,,}mAaaa为路段的集合。对路段aA，有起点和终点(,)ijvv与其对应，并有相应的阻抗()ijwaw。给定V中的两个节点sv、tv，设P是以sv为起点tv为终点的一条路径，定义路径P的阻抗为()()aPwPwa。最短路问题为：在所有以sv为起点tv为终点的路径中，找出一条阻抗最小的路径0P，并满足0()min()PwPwP，称0P为从sv到tv的最短路，0()wP为从sv到tv的最短路权。长沙理工大学交通运输工程学院8.4.1Dijkstra算法（标号法）适用条件1959年提出，路权都必须为正，不允许出现负权。对无向网络，也可以按照此算法来执行，只不过认为各边都是可以双向行驶的路段。假定P是从Vs到Vt的最短路，Vi是路线上的某一个节点，那么从Vs沿P到Vi的路线就是从Vs到Vi的最短路线。主要获得起点到终点之间的最短路，同时可以获得网络中其它某些节点与起点之间的最短路，但具体是哪些节点，事先并不知道。长沙理工大学交通运输工程学院算法简介计算从某一指定节点到另一指定节点之间的最短路算法首先从源点开始，给每一个节点记一标号，标号分为P标号和T标号两种，T标号表示从源点到该点的最短路权的上界（临时标号）；P标号表示从源点到该点的最短路权，又称固定标号。在标号过程中，T标号一直在改变，已得到P标号的节点其标号不再改变，凡是没有标上P标号的节点，都标上T标号。算法每执行一步，将把某一节点的T标号改变为P标号，当终点获得P标号时，标号过程结束。计算从某一指定节点到网络中其它所有节点之间的最短路前面的过程相同。经过有限步运算之后，当把所有的T标号都改变成P标号，即获得了从源点到网络中任一节点的最短路，标号过程结束。长沙理工大学交通运输工程学院算法描述记V为节点集合；iS为第i步时具有P标号节点的集合；记)(vr为节点v的父节点（到节点v的最短路线上的前一节点）；ijw为路段（ji,）的权重；),(jivvd为节点iv到节点jv的最短路权。Step0：初试化。令0i，}{0svS，0)(svP，0)(svr。Vv且svv，令)(vT，Mvr)(（M表示一个很大的正数）。置sk（ksvv代表起点）。长沙理工大学交通运输工程学院Step1：若VSi，迭代停止，转入Step4，此时对Vv，均有)(),(vPvvds。否则转入Step2。Step2：考察每个使Avvjk),(且ijSv的节点jv，如果kjkjwvPvT)()(，则令kjkjwvPvT)()(，kvrj)(；否则转入Step3。Step3：在所有的T标号节点中寻找一个最小的T标号值，并将该节点标为P标号，即令)}({min)(jSvjvTvTiji、)()(iijjvTvP、}{1ijiivSS，同时置ijk，令1ii，转入Step1中继续进行迭代计算。Step4：根据)(vr并利用反向追踪的方法即可以获得指定节点sv到网络中其它任意节点v的最优路径以及最短距离),(vvds，算法终止。长沙理工大学交通运输工程学院算例12453653423475126求V1→V6的最短路。1246576132161083234求V1→V7的最短路。长沙理工大学交通运输工程学院8.4.2矩阵迭代算法矩阵迭代法是一种借助于权矩阵迭代运算来求解最短路权和最短路径的算法，利用该算法可以很简单地获得交通网络中任意2个节点之间的最短路权（径）。该算法的基本思想是，记