第六章-交通分配课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,径路,n,径路,1,径路,2,O,D,O,D,第一节 概述,径路n径路1径路2ODOD第一节 概述,1,第六章-交通分配课件,2,路径与最短路径,1,）路段：交通网络上相邻两个节点之间的交通线路称作“路段”。,2,）路径：交通网络上任意一对,OD,点之间，从产生点到吸引点一串连通的路段的有序排列叫作这对,OD,点之间的路径。一对,OD,点之间可以有多条路径。,3,）最短路径：一对,OD,点之间的路径中总阻抗最小的路径叫“最短路径”,路径与最短路径,3,交通阻抗,交通阻抗是指交通网络上路段或路径之间的运行距离、时间、费用、舒适度，或这些因素的综合。,路段上的阻抗,节点处的阻抗,交通阻抗,4,路段阻抗-美国公路局BPR函数,路段阻抗-美国公路局BPR函数,5,节点阻抗,节点阻抗,6,交通均衡问题,Wardrop,第一原理：在道路网的利用者都知道网络的状态并试图选择最短路径时，网络会达到这样一种均衡状态，每对,OD,点之间各条被利用的路径的走行时间都相等而且是最小的走行时间，而没有被利用的的路径的走行时间都大于或等于这个最小的走行时间。,Wardrop,第二原理：系统平衡条件下，拥挤的路网上的交通流应该按照平均或者总的出行成本最小为依据来分配。,交通均衡问题,7,非均衡模型,非均衡模型,8,交通网络的表示,邻接矩阵,邻接目录表,阻抗矩阵,交通网络的表示,9,邻接矩阵,邻接矩阵,L,是一个,n,阶方阵（,n,是节点的数目），其中的元素,l,ij,表示交通网络中节点的,邻接关系，定义为：,邻接矩阵,10,邻接目录表,所谓邻接目录表也是一个矩阵,V,，是,n,k,阶的，此处,k,表示图中街道最多邻接的节点,数。元素,v,ij,表示第,i,个节点的第,j,个邻接的节点，不足的用虚拟节点,0,表示。,邻接目录表,11,阻抗矩阵,邻接矩阵和邻接目录表都只能表达节点之间是否相邻，而没能表达相邻节点之间交通线路的阻抗。针对带阻抗的交通网络图可定义阻抗矩阵：,其中，矩阵中的元素,阻抗矩阵,12,第六章-交通分配课件,13,第二节 最短路径,最短路径算法是交通分配的最基本的算法，几乎所有交通分配方法都要以它作为一个基本子过程反复调用。,DIJKSTRA,法（标号法）,矩阵迭代法,FloydWarshall,法,第二节 最短路径 最短路径算法是交通分配的最基本的算法，,14,DIJKSTRA,法（标号法）,算法思想：,（,1,）首先从起点,O,开始，给每一个节点一个标号，分为,T,标号和,P,标号；,T,标号表示从起点,O,到该点的最短路权的上限；,P,标号是固定标号，表示,O,到该点的最短路权。,（,2,）标号过程中，,T,标号一直不在改变，,P,标号不再改变，凡是没有表示,P,标号的点，都标上,T,标号；,（,3,）算法的每一步就是把某一点的,T,标号改变为,P,标号，直到所有的,T,标号都改变为,P,标号。即得到从起点,O,到其他各点的最短路权，标号过程结束,DIJKSTRA法（标号法）,15,算法步骤：,（,1,）初始化。给起点,1,标上,P,（,1,）,=0,，其余各点标上,T,标号,T,1,(j)=,表示从起点,1,到,1,的最短路权为,0,，到其他各点的最短路权的上限临时值为。标号中括号内数字表示节点号，下标表示第几步标号。,（,2,）设经过了（,K-1,）步标号，节点,i,是刚得到,P,标号的点，则对所有没有得到,P,标号的点进行下一步新的标号，（第,K,步）；考虑所有与节点,i,相邻且没有标上,P,标号的点,j,，修改它们的标号：,算法步骤：,16,式中,d,ij,i,到,j,的路权；,T,（,j,）第,K,步标号前,j,点的,T,标号,在所有的,T,标号中，必选出最小的,T,标号,Tk,（,j,0,）,式中,j,0,最小,T,标号所对应的节点号,T,（,r,） 与,i,点不相邻点,r,的,T,标号,给点,j,0,标上,P,标号：,第,K,步标号结束。,式中 diji到j的路权；,17,矩阵迭代法,算法思想,（,1,）借助距离（路权）矩阵的迭代运算来求解最短路权的算法,（,2,）该方法能一次获得任意两点之间的最短路权矩阵,矩阵迭代法,18,算法步骤,（,1,）首先构造路权矩阵，矩阵给出了节点间只经过一条边到达某点的最短距离,（,2,）对矩阵进行如下的迭代运算，便可得到经过两步达到某一点的最短距离,式中,n,网络节点数,*,矩阵逻辑运算符号,d,ik,，,d,kj,矩阵,D,的相应元素,算法步骤式中 n 网络节点数,19,最短路径辨识,追踪法：从每条最短路径的起点开始，根据起点到各个节点的最短路权搜索最短路径上的各个交通节点，直至径路终点。,最短路径辨识,20,算法步骤：,设某路径的起点是,r,，终点是,s,（,1,）从起点,r,开始，寻找与,r,相邻的节点,i,满足：,则路段,【r,，,i】,便是从,r,到,s,最短路径上的一段；,（,2,）寻找与,i,相邻的一点,j,，使其满足,则,【i,，,j】,便是从,r,到,s,最短路径上的一段,（,3,）如此反复不断，直到终点,s,。,算法步骤：,21,第三节 非均衡分配方法,非平衡分配按其分配方式可分为变化路阻和固定路阻两类，按其分配形态可分为单路径与多路径两类。,第三节 非均衡分配方法 非平衡分配按其分配方式可分为变化,22,全有全无分配方法,全有全无分配法是将,OD,交通需求沿最短经路一次分配到路网上去的方法，也被称为交通需求分配。顾名思义，全有（,all,）指将,OD,交通需求一次性地全部分配到最短径路上。全无（,nothing,）指对最短径路以外的径路不分配交通需求量。,全有全无分配法应用于没有通行能力限制的网络交通交通量分配等场合。在美国芝加哥城交通解析中，首次获得应用。另外，后述增量分配法和均衡分配法中频繁使用。,全有全无分配方法,23,算法思想,将,OD,交通量加载到路网的最短路径上，从而得到各个路段流量的过程。,A,B,100,100,100,出行量,T(A-B)=100,辆,算法思想AB100100100出行量 T(A-B)=100,24,计算步骤,（,1,）初始化，使路网中所有路段的流量为,0,，并求得各路段自由流状态时的阻抗；,（,2,）计算路网中每个,OD,点对的最短路径；,（,3,）将,OD,间的交通量全部分配到相应的最短路径上。,计算步骤,25,输入,OD,矩阵及网络几何信息,计算路权,计算最短路权矩阵,辨别各,OD,点对间的最短路线并分配该,OD,量,累加交叉口、路段交通量,最后一,OD,点对？,输出各路段、交叉口总分配交通量,转入下一,OD,点对,N,Y,最短路分配方法流程图,输入OD矩阵及网络几何信息计算路权计算最短路权矩阵辨别各OD,26,例,1,：交通网络及路段行驶时间如图所示，交通节点,1,、,3,、,7,、,9,分别为,A,、,B,、,C,、,D,四个交通区的作用点，四个交通区的出行,OD,矩阵如表,6,所示。试用最短路法分配该,OD,矩阵。,A,B,D,C,图,p179,终点,起点,A,B,C,D,A,0,200,200,500,B,200,0,500,100,C,200,500,0,250,D,500,100,250,0,表,OD,矩阵（辆,/h,）,例1：交通网络及路段行驶时间如图所示，交通节点1、3、7、9,27,解,：（,1,）确定最短路线如表所示：,OD,点对,最短路线节点号,OD,点对,最短路线节点号,AB,123,CA,741,AC,147,CB,74563,AD,14569,CD,789,BA,321,DA,96541,BC,36547,DB,963,BD,369,DC,987,表 最短路线,（,2,）分配,OD,量：将,OD,点对的,OD,量分配到该,OD,点对相对应的最短路线上，并进行累加，得到图所示。,解：（1）确定最短路线如表所示：OD点对最短路线节点号OD点,28,A,B,D,C,图 分配交通量（辆,/h,）,200,200,200,500,200,500,500,500,100,200,200,500,100,500,500,200,500,200,100,500,250,250,100,500,250,250,700,700,700,600,600,1000,1000,1000,1000,500,500,500,500,500,500,600,600,700,ABDC图 分配交通量（辆/h）2002,29,容量限制单路径分配方法,将,OD,分布矩阵分成若干份（,N,份），各份比重由大到小，具体比重值可以人为任意确,定；从大份开始，每次取一份进行全有全无分配，每次分配前根据前一次的分配结果用走行时间公式修正各路段的阻抗值,容量限制单路径分配方法,30,容量限制单路径交通分配,A,B,40,+,20,20,30,+10,10,40,10,20,+,40,30,+10,30,出行量,T(A-B) =,40,+,30,+,20,+10,容量限制单路径交通分配 AB40+202030+101,31,输入,OD,矩阵及网络几何信息,分解原,OD,表成,K,个,OD,分表,确定路段行驶时间,确定交叉口延误,计算路权,最后一,OD,点对？,累加交叉口、路段交通量,转入下一,OD,点对,N,Y,确定网络最短路权矩阵,按最短路法分配每一,OD,点对,OD,量,按最短路法分配每一,OD,点对,OD,量,最后一,OD,点对？,转入下一,OD,分表,Y,N,输入OD矩阵及网络几何信息分解原OD表成K个OD分表确定路段,32,径路,3,径路,1,D,径路,2,径路3径路1D径路2,33,第六章-交通分配课件,34,第六章-交通分配课件,35,最短路和容量限制分配的小结,1.,共同点,最短路（全无全有分配）和容量限制分配都是建立在最短路径的基础上。,说明出行者有网络中所有路径的出行时间的正确信息；并且能基于信息做出正确路径选择决定，即属于确定性的路径选择行为,2.,区别,最短路径选择其路权是常数，即没有考虑通行能力限制和交通拥挤的影响，是一种理想化的交通分配方法，尤其不适用于拥挤状态下的交通网络的分配,容量限制交通分配方法其路权是网络中交通量和通行能力的函数，即考虑了通行能力和交通拥挤的影响。,最短路和容量限制分配的小结1.共同点2.区别,36,问题,出行者能否完全掌握网络中所有路径的出行时间的正确信息？能否根据信息做出正确的路径选择决定？,1.,出行者渴望选择出行时间最短的路径；,最短路因素,2.,出行者不可能掌握网络中所有路径出行时间的正确信息；,3.,出行者社会经济属性的不同，做出的决定也会有一定的差别；,随机性的因素,由此引出了另一种非平衡算法,多路径交通分配方法,问题出行者能否完全掌握网络中所有路径的出行时间的正确信息？能,37,静态多路径分配方法,由于交通网络的复杂性和路段上交通状况的多变性，以及各个出行者主观判断的多样性，某,OD,点对之间不同出行者所感知的最短路径将是不同的、随机的，因此这些出行者所选择的“最短路径”不一定是同一条，从而出现多路径选择的现象,.,静态多路径分配方法,38,多路径交通分配方法,分配模型,出行者在选择出行线路时带有随机性，因此，各出行线路被选用的概率可用,Logit,路径选择模型计算。,P(r,s,k)OD,量,T(r,s),在第,k,条出行路径上的分配率；,t(k),第,k,条出行线路的路权；,各出行路线的平均路权，,分配参数；,m,有效出行线路条数。,多路径交通分配方法 分配模型,39,多路径概率交通分配,A,B,30,P=0.3,P=0.5 20,P=0.2,50,T=100,多路径概率交通分配AB30P=0.3P=0.5,40,阻抗可变的多路径分配方法,无容量限制多路径分配方法是假设路段实际阻抗为一个常数，没有考虑路段阻抗与流量的关系，现在我们研究在考虑路段上的流量对路段实际阻抗存在影响的情况下的多路径分配方法，即阻抗可变的多路径分配方法。这将会使分配结果更加接近实际情况。,阻抗可变的多路径分配方法,41,第六章-交通分配课件,42,1,5,4,2,3,2,1,3,4,道路网络,终点,起点,1,2,3,1,0,300,150,2,300,0,450,3,150,450,0,154232134道路网络终点1231030015023,43,