当前位置:www.hg28.com > www.hg28.com >

2、Dijkstra法—算法步调 步调1 初始化

发布时间:2019-10-16

第八讲 交通流分派 (Traffic Distribution Forecast) 8.1 概述 交通流分派是交通需求预测四阶段法的第四阶段,使命是将各类出行体例的OD矩阵按照必然的径选择准绳分派到交通收集中的各条道上,求出各段上的流量及相关的交通目标,从而为交通收集的设想、评价等供给根据。 8.1 概述 交通量分派便是将曾经预测得出的OD交通量,按照已知的道网描述,按照必然的法则合适现实地分派到道网中的各条道上,进而求出网中各段的交通流量。 一般的道网中,O取D之间有良多条道,若何将OD交通量准确合理地分派到O取D之间的各条道上便是交通分派模子要处理的问题。 交通分派涉及以下几个方面 1、将现状OD交通量分派到现状交通收集上,以阐发目前交通收集的运转情况。如有某些段的交通量不雅测值,还能够将不雅测值取分派成果进行比力,以查验模子精度。 2、将规划年OD交通量预测值分派到现状交通收集上,以发觉对规划年的交通需求而言的现状交通收集的缺陷,为交通收集的规划设想供给根据。 3、将规划年OD交通量预测值分派到规划交通收集上,以评价交通收集规划方案的合。 交通分派所需根基数据 1、暗示需求的OD交通量。正在拥堵的城市道交通网中凡是采用高峰期OD交通量,正在城市间公网中凡是采用年平均日交通量(AADT)的OD交通量。 2、网定义,即段及交叉口特征和属性数据,同时还包罗当时间—流量函数。 3、径选择准绳。运转线固定类型、运转线 概述 交通收集的笼统取简化 交通分派中所利用的收集是图论中笼统的收集图,由节点和连线构成。节点一般代表道网中道的交叉点以及交通小区的沉心,连线则代表正在两点之间存正在一条道。 交通收集的笼统取简化 简化时次要考虑以下几点: ① 窄而容量小的道可不予考虑; ② 小的道交叉点不做节点考虑,而正在取之 相关的道的行驶时间函数中得当地考虑其影响; ③ 可将几条平行道归并成一条道,并修 改其容量; ④ 分级形成收集。 交通(或者称为阻)间接影响到交通流径的选择和流量的分派。 道正在交通分派中能够通过阻函数来描述。 阻函数是指段行驶时间取段交通负荷、交叉口耽搁取交叉口负荷之间的关系。正在具体分派过程中,由段行驶时间及交叉口耽搁配合构成出行交通。 交通 交通收集上的阻,应包含反映交通时间、交通平安、交通成本、舒服程度、便利性和准时性等等很多要素。 交通时间常常被做为计较阻的次要尺度: (1)理论研究和现实不雅测表白,交通时间是出行者所考虑的首要要素,特别正在城市道交通中; (2)几乎所有的影响阻的其它要素都取交通时间亲近相关,且呈现出取交通时间不异的变化趋向; (3)交通时间比其它要素更易于丈量,即便有需要考虑到其它要素,也常常是将其转换为时间来怀抱。 段 对于单种交通收集,出行者正在进选择时,一般都是以时间最短为方针。 有些交通收集,段上的行驶时间取距离成反比,取段上的流量无关,如城市轨道交通收集,可选距离为。 有些交通收集,如公网、城市道网,段上的行驶时间取距离不必然成反比,而取段上的交通流量相关,选用时间做为,可表达为: 段 美国道局BPR函数: 段 抱负的段函数该当具备下列的性质: 1、实正在性,用它计较出来的行驶时间应具有脚够的线、函数该当是枯燥调递增取持续可导的。 3、函数该当答应必然的“超载”,即当流量等于或跨越通过能力时,行驶时间不应当为无限大。该当反馈一个行驶时间,不然一个无限大的数可能会导致计较机死机。。 4、从现实使用的角度出发,函数该当具有很强的移植性,所以采用工程参数如流车速、通过能力等就比利用通过标定而获得的参数要好些。 节点 节点——指车辆正在交通收集节点处(次要指正在交叉口处)的。 交叉口取交叉口的形式、信号节制系统的配时、交叉口的通过能力等要素相关。 正在城市交通收集的现实出行时间中,除段行驶时间外,交叉口耽搁拥有很大的比沉。高峰期间交叉口耽搁可能会跨越段行驶时间。 因为分歧流向车辆正在交叉口的分歧耽搁正在最短径算法中的表达没能获得很好的处理,已有的城市道交通流分派中一曲忽略节点问题。 四、最短径的计较方式 交通收集上肆意一OD点对之间,从发生点到吸引点一通的段的有序陈列叫做这一OD点对之间的径。一OD点对之间能够有多条径,总最小的径叫“最短径”。 最短径的计较是交通量分派中最根基也是最主要的计较: 任何一种交通量分派法都是成立正在最短径的根本上;几乎所有交通量分派方式中都是以它做为一个根基子过程频频挪用,最短径的计较占领了全数计较时间的次要部门。 最短径算法问题包含两个子问题: 1、两点间最小的计较; 2、两点间最小径的辨识。 前者是处理后者的前提。 很多算法都是将这两个子问题分隔考虑,设想出来的算法是别离零丁求出最小和最短径。 交通流分派最短径的算法有:(1)Dijkstra法、(2)矩阵迭代法、(2)Floyd-Warshall法。 (一)Dijkstra法 Dijkstra法也称标号法。常用于计较从某一指定点(起点)到另一指定点(起点)之间的最小。Dijkstra法能够同时求出收集中所有节点到某一个节点的全数最短径或最短径树。 标号的根基特点是:从收集中的某一个目标地节点起头,同时寻找收集中所有节点到该目标地节点的最短径树,算法以一种轮回的体例查抄收集中所有的节点。正在每一步轮回中,总试图找到一条从被查抄节点到目标地节点的更短线。曲到没有更短的线、Dijkstra法—算法思惟 ①起首从起点O起头,给每个节点一个标号,分为T标号和P标号两类。 T标号是姑且标号,暗示从起点O到该该点的最短权的上限;P标号是固定标号,暗示从起点O到该点的最短权。 ②标号过程中,T标号一曲正在改变,P标号不再改变,凡是没有标上P标号的点,都标上T标号。 ③算法的每一步把某一点的T标号改变为P标号,曲到所有的T标号都改变为P标号。即获得从起点O到其它各点的最短权,标号过程竣事。 2、Dijkstra法—算法步调 步调1 初始化。给起点1标上P标号P(1)=0,其余各点均标上T标号 T1(j)=∞,j=2,3,…,n。即暗示从起点1到起点1最短权为0,到其 各点的最短权的上限姑且定为∞。标号中括号内数字暗示节点号,下标 暗示第几步标号。颠末第一步标号获得一个P标号P(1)=0。 步调2 设颠末了(K-1)步标号,节点i是刚获得P标号的点,则对所有没有 获得P标号的点进行下一步新的标号(第K步);考虑所有取节点i相邻且没 有标上P标号的点{j},点窜它们的T标号: Tk(j)=min[T(j),P(i)+dij] 式中, dij——i到j的距离(权); T(j)——第K步标号前j点的T标号。 正在所有的T标号(包罗没有被点窜的)中,比选出最小的T标号Tk(j0): Tk(j0)=min[Tk(j),T(r)] 式中, j0——最小T标号所对应的节点; T(γ)——取i点不相邻点r的T标号。 给点j0标上P标号:P(j0)= Tk(j0),第K步标号竣事。 步调3 当所有节点中曾经没有T标号,算法竣事,获得从起点1到其它各点 的最短权;不然前往第二步。 例题8.1 用Dijkstra法计较图7-1所示网从节点1到各节点的最短权。 步调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)+d24]=min[∞,2+2]=4 正在所有T标号(点3,4,5,…9)中,节点4为最小,给节点4标上P标号,即P(4)=T2(4)=2。 步调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标号中,节点5为最小,给节点5标上P标号,即P(5)= T4(5)=3。 步调7:节点6刚获得P标号。节点9取6相邻,且为T标号,点窜9的T标号: T7(9)=min[T(9),P(6)+d69]=min[∞,4+2]=6 正在所有T标号中,节点7为最小,给节点7标上P标号,即P(7)= T4(7)=4。 步调8:节点7刚获得P标号。节点8取7相邻,且为T标号,点窜8的T标号: T8(8)=min[T(8),P(7)+d78]=min[5,4+2]=5 正在所有T标号中,节点8为最小,给节点8标上P标号,即P(8)= T8(8)=5。 步调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。 (二)矩阵迭代算法 ①借帮距离(权)矩阵的迭代运算来求解最短权的算法。 ②该方式能一次获得肆意两点之间的最短权矩阵。 2、矩阵迭代法—算法步调 ①起首构制距离矩阵(以距离为权的权矩阵)。 ②矩阵给出了节点间只颠末一步(一条边)达到某一点的最短距离。 ③对距离矩阵进行如下的迭代运算,便能够获得颠末两步达到某一点的最短距离。 (k=1,2,3,…,n) 式中,n——收集节点数; ——矩阵逻辑运算符; ——距离矩阵D中的响应元素。 例题8.2: 求解例题7-1收集肆意节点间的最短径。 3、最短径辨识 获得最短权矩阵后,还需把每一个节点对之间具体的最短径寻找出来,将交通流分派上去。 最短径辩识采用逃踪法:从每条最短径的起点起头,按照起点到各节点的最短权搜刮最短径上的各个交通节点,曲至径起点。 3.最短径辨识——算法思惟 设某最短径的起点是r,起点是s。径辩识算法如下: (1)从起点r起头,寻找取r相邻的节点i,满脚: 式中, ——段r到i的距离; ——节点i到s的最短权; ——节点r到s的最短权。 则段[r,i]即是从r到s最短径上的一段。 (2)寻找取i相邻的一点j,使其满脚: 则段[i,j]即是从r到s最短径上的一段。 (3)如斯不竭频频,曲到起点s。把节点r,i,j,…,s毗连起来,便得 到从r到s的最短径。 8.2 交通收集均衡取非均衡分派 一、概述 若两点之间有良多条道而这两点之间的交通量又很少的话,这些交通量明显会沿着最短的道行走。 跟着交通量的添加,最短径上的交通流量也会随之添加。添加到必然程度之后,这条最短径的行驶时间会由于拥堵或堵塞而变长,最短径发生变化,一部门道操纵者会选择次短的道。跟着两点之间的交通量继续添加,两点之间的所有道都有可能被操纵。 若所有的道操纵者都精确晓得各条道所需的行驶时间,并选择行驶时间最短的道,最终两点之间被操纵的各条道的行驶时间会相等。没有被操纵的道的行驶时间更长。这种形态被称之为道网的均衡形态。 正在交通流分派中,一个现实道网中一般有良多个OD对,每个OD对间都有多条径。且各组OD之间的径也互相堆叠。 1952年出名学者Wardrop提出了交通收集均衡定义的第一道理和第二道理,奠基了交通流分派的根本。 二、Wardrop均衡道理 1、Wardrop第一道理——用户最优道理(UE) 正在道网的操纵者都切当晓得收集的交通形态并试图选择最短径时,收集会达到均衡形态。正在考虑拥堵对走行时间影响的收集中,当收集达到均衡形态时,每个OD对的各条被操纵的径具有相等并且最小的走行时间;没有被操纵的径的走行时间大于或等于最小走行时间。——Wardrop均衡 现实交通流分派中称为用户平衡(UE)或用户最优。 收集拥堵的存正在是均衡构成的前提。 二、Wardrop均衡道理 2、Wardrop第二道理——系统最优道理(SO) 道理:系统均衡前提下,拥堵的网通流该当按照平均或总的出行成本最小为根据来分派。 第二道理是一个设想道理,是面向交通运输规划师和工程师的。 第一道理次要是成立每个道操纵者使其本身出行成本(时间)最小化的行为模子,而第二道理则是旨正在使交通流正在最小出行成本标的目的上分派,从而达到出行成本最小的系统均衡。 一般来说,两个道理下的均衡成果不会是一样的,可是正在现实交通中,人们更期望交通流可以或许按照Wardrop第一道理,即用户均衡的近似解来分派。 3、Wardrop均衡道理比力阐发 第一道理反映了道用户选择线的一种原则。按照第一道理分派出来的成果该当是网上用户现实径选择的成果。 第二道理则反映了一种方针,即按照什么样的体例分派是最好的(系统最优)。正在现实收集中很难呈现第二道理所描述的形态,除非所有的驾驶员彼此协做,为系统最优化而勤奋。这正在现实中是不太可能的。但第二道理为交通办理人员供给了一种决策方式。 三、均衡和非均衡分派 1952年Wardrop提出道网均衡的概念和定义之后,若何求解Wardrop均衡成了主要的研究课题。 1956年,Beckmann等提出了描述均衡交通分派的一种数学规划模子。 1975年由LeBlanc等学者将Frank—Wolfe算法用于求解Beckmann模子获得成功,从而构成了现正在的适用解法。 Wardrop道理—Beckmann模子—LeBlanc算法这些冲破是交通分派问题研究的严沉前进,也是交通分派问题的根本。 交通流分派方式分为均衡分派和非均衡分派两大类。 对于完全满脚Wardrop道理定义的均衡形态,则称为均衡分派法; 对于采用式方式或其他近似方式的分派模子,则称为非均衡分派方式。 非均衡分派方式按其分派体例可分为变化阻和固定阻两类; 按分派形态可分为单径取多径两类。 7.3.1 全有全无分派法 (All-or-Nothing Assignment Method) 全有全无方式(0-1分派法)不考虑网的拥堵结果,取阻为,即假设车辆的段行驶速度、交叉口耽搁不受段、交叉通负荷的影响。每一个OD点对的OD交通量被全数分派正在毗连OD点对的最短径上,其他径上分派不到交通量。 长处是计较相当简洁,分派只需一次完成;不脚之处是出行量分布不服均,出行量全数集中正在最短径上。 全有全无分派法 ——算法思惟和计较步调 算法思惟:将OD交通量T加载到网的最短径树上,从而获得网中各段流量的过程。 计较步调 Step 0:初始化,使网中所有段的流量为0,并求出各段流形态时的; Step 1:计较收集中每个出发地O到每个目标地D的最短径; Step 2:将O、D间的OD交通量全数分派到响应的最短径上。 因为0-1分派法不克不及反映拥堵结果,次要是用于某些非拥堵网,用于没有通行能力的收集的环境。 利用范畴是:正在城际之间道通行能力不受的地域能够采用;一般城市道网的交通量分派不宜采用该方式。 正在现实中因为其简单适用的特征,一般做为其他各类分派手艺的根本,正在增量分派法和均衡分派法等方式中频频利用。 7.3.2 增量分派法 (Incremental Assignment Method) 增量分派法(简称IA分派法)是一种近似的均衡分派法。正在全有全无分派方式的根本上,考虑了段交通流量对的影响,进而按照道的变化来调整网交通量的分派,是一种“变化阻”的交通量分派方式。 起首需将OD表分化成N个分表(N个分层),然后分N次利用最短分派方式,每次分派一个OD分表,而且每分派一次,阻就按照阻函数批改一次,曲到把N个OD分表全数分派到网上。 增量分派法 —算法思惟 将OD交通量分成若干份(等分或不等分); 轮回地分派每一份的OD交通量到收集中; 每次轮回分派一份OD交通量到响应的最短径上; 每次轮回均计较、更新各段的走行时间,然后按更新后的走行时间从头计较最短径; 下一轮回中按更新后的最短径分派下一份的OD交通量。 增量分派法 —算法步调 复杂程度息争的切确性都介于0-1分派法和后述的均衡分派法之间。 时便取0-1分派法的成果分歧; 时,其解取均衡分派法的解分歧。 长处:简单可行,切确度能够按照朋分数N的大小来调整。正在现实的道网交通量分派中经常被采用,并且也有比力成熟的商用软件可供利用。 错误谬误:仍然是一种近似方式,当阻函数不是很时,有时会将过多的交通流量分派到某些容量很小的段上。一般环境下,得不到均衡解。 7.3.3 迭代加权法 (Method of Successive Average, MSA) 算法思惟 不竭调整已分派到各段上的交通流量而逐步达到或接衡分派。 正在每步轮回中,按照已分派到各段上的交通流量进行一次0-1分派,获得一组各段的附加交通量。 然后用该轮回中各段的分派交通流量和该轮回中获得的附加交通量进行加权平均,获得下一轮回中的分派交通流量。 当相邻两个轮回平分配的交通流量十分接近时,即可遏制计较。最初一次轮回中获得的分派交通量便是最终的交通量。 7.3.3 迭代加权法 (Incremental Assignment Method) 正在Step4中,判别 取 差值大小时可节制它们的相对误差正在百分之几以内。但用得更多的原则是轮回几多次当前令其遏制。 正在Step3中,权沉系数 需由计较者本人定。 既可定为,也可定为变数。定为时,最遍及的环境是令 。定为变数时,最遍及的环境是令 (n为轮回次数)。有研究表白 时,会使分派尽快接衡解。 二次加权平均法是一种简单适用却又最接近于均衡分派法的一种分派方式。若是每步轮回中权沉系数 严酷按照数学规划模子取值时,即可获得均衡分派的解。 8.4 均衡分派法 用户均衡分派模子和系统最优均衡分派模子 一、用户均衡分派模子及其求解算法 用户均衡分派模子(UE) 1956年Beckmann等学者提出了一种满脚Wardrop原则的数学规划模子,奠基了研究交通分派问题的理论根本。 后来的很多分派模子,诸如弹性需求交通分派模子、分布—分派组合模子等都是正在Beckmann模子的根本上扩展获得的。 用户均衡分派模子 ——Bechmann模子 用户均衡分派模子 1、模子中利用的变量和参数 :段a上的交通流量; :段a的交通,也称为走行时间; :段a的函数,因此 ; :出发地为r,目标地为s的OD间的第k条径上的交通 流量; :出发地为r,目标地为s的OD间的第k条径的; :出发地为r,目标地为s的OD间的最短径的; :段-径变量,即0-1变量,若是段a正在出发地为r 目标地为s的OD间的第k条径上,则, 不然, 。 :收集中节点的调集; :收集中段的调集; :收集中出发地的调集; :收集中目标地的调集; :r取s之间的所有径的调集; :r取s间的OD交通量。 用户均衡分派模子 用数学言语间接表达Wardrop用户均衡原则,则能够描述为: 当交通收集达到均衡时, 如有 ,必有 ,申明若从r到s有两条及其以上的径被选中,则它们的行驶时间相等; 如有 ,必有 ,申明若某条从r到s的径流量等于零,则该径的行驶时间必然跨越被选中的径的行驶时间。 用户均衡分派模子 2.模子的根基束缚前提阐发 均衡分派过程中应满脚交通流守恒的前提,即OD间各条径上的交通之和应等于OD交通总量: 段交通量 应是由各个(r,s)对的路子该段的径的流量 累加而成: 径应是该径路子的各段的的累加: 用户均衡分派模子 3.模子的根基束缚前提阐发—— 用户均衡分派模子 ——Bechmann模子 Beckmann模子的解就是交通流分派达到均衡形态时的解—— 三、系统最优化分派模子 系统最优分派模子 系统最优分派(SO):正在拥堵的收集中,交通量该当按照使得收集中总即总走行时间最小的准绳进行分派。 第二道理反映了一种方针,是交通系统办理者的客不雅希望,即按什么样的体例分派是最好的。 能够做为对系统评价的目标,为办理者供给一种决策方式。从此种意义上说,第二道理是道系统办理者所但愿的分派准绳,特别正在智能交通系统获得普遍使用之后。 系统最优分派模子 8.5 交通分派模子中存正在的问题 一、对交通流量的近似假定 只要正在OD交通流量都是不变不变的的前提前提下,才会有道网的“均衡”,前述的各类交通分派方式才成立。而现实的交通量是动态的。 正在现实交通量分派中,一般以一天为单元,对一天的平均交通流量进行分派,而获得每条道一天的平均流量。发生两个问题。一是交通分派问题非线性问题,用一天的平均OD交通流量进行分派获得的成果取用现实的动态OD交通量进行分派获得的成果必定会有不同。二是正在现实的道网规划中,有时不只是需要一天的平均环境,并且需要晓得某个特按时间段的道交通情况,而静态交通量分派模子无法推定某个特按时间段的道网情况。 二、操纵者径选择方式的假定 正在交通分派模子中,假定道网的操纵者都晓得道网中各条线的拥堵情况和所需走行时间,而且具有不异的选择尺度。 径选择取交通量分派的研究一曲各自互不相关地进行着,没有很好地连系正在一路。 三、交通收集的局限性 利用的收集是经简化后的收集。正在收集中简化掉狭小道有可能使干线道的分派交通量大于现实交通流量。 正在现实道网中,交通量一般是正在区域内平均地发生和吸引。正在目前的交通量分派模子中,都是将OD交通量集中正在区域的某一点——核心节点上发生和吸引。形成的误差是接近该点的线大将可能被分派到多于现实流量的交通流量,而离该点较远的线上分派的交通流量则较少。 阻函数的简化。交通量分派模子中的阻函数一般涉及到两个量,即段交通量和交通容量。但现实道中影响走行时间的远不止这两种要素。道的几何外形、坡度、信号节制情况、摆布转等都对走行时间有影响。 总 结 8.3 非均衡分派方式 8.3 非均衡分派方式 Step 0:初始化。按照各段的走行时间进行一次0-1分派,获得 各段的分派交通流量 。令 Step 1:令 ,按照当前各段的交通量 Step 2:按照Step 1计较的段走行时间和OD交通量进行0-1分派,获得 Step 3:用加权平均的方式计较各段的当前交通量 : Step 4:若是 取 的差值不大,则遏制计较, 不然前往Step 1。 。 计较各段的阻。 各段的附加交通流量 。 即为最终分派成果。 8.3 非均衡分派方式 算法步调: 总 结 8.3 非均衡分派方式 【本章次要内容】 8.5 交通分派模子中存正在的问题 8.2 交通收集均衡取非均衡分派理论 8.1 概述 8.3 非均衡分派法 8.4 均衡分派法 交通流分派 St: Subject to: 两个段的函数别离是: OD量为q=5,别离求该收集的Beckmann模子的解和均衡形态的解。 s.t. 【解】先求Beckmann模子的解。将函数带入模子,得: x1, x2≥0 例 证 将 代入方针函数并进行积分,转换为无束缚的 极小值问题: Min: 令dZ/dx1=0,解得 , 。 下面求均衡形态的解。 按照Wardrop用户均衡道理,收集达到均衡时该当有: t1=t2 和 联立求解这个方程组,很容易求得 , 此时,t1=t2=5。 可见,对于该网,Beckmann模子的解和均衡形态的解完全不异。 束缚前提: 对函数进行分歧的点窜,UE模子取SO模子能够互相转换。 【本章次要内容】 8.5 交通分派模子中存正在的问题 8.2 交通收集均衡取非均衡分派理论 8.1 概述 8.3 非均衡分派法 8.4 均衡分派法 交通流分派 交通规划现实中,需要求出网中肆意两个节点之间的最短权矩阵(n×n阶); 虽然Dijkstra算法一次可以或许算出从起点到其它各节点的最短权,但仍不克不及满脚要求,用此方式求最短权矩阵,需要频频运算n次,导致计较效率不高,且速度较慢,所需存储空间较多,正在大规模交通规划中使用遭到必然。 Dijkstra算法的局限性 1、矩阵迭代法—算法思惟 【解】 (1)构制距离矩阵,如下表所示。 (第1步) 0 2 ∞ 2 ∞ ∞ ∞ ∞ ∞ 9 2 0 2 ∞ 2 ∞ ∞ ∞ ∞ 8 ∞ 2 0 ∞ ∞ 2 ∞ ∞ ∞ 7 2 ∞ ∞ 0 1 ∞ 2 ∞ ∞ 6 ∞ 2 ∞ 1 0 1 ∞ 2 ∞ 5 ∞ ∞ 2 ∞ 1 0 ∞ ∞ 2 4 ∞ ∞ ∞ 2 ∞ ∞ 0 2 ∞ 3 ∞ ∞ ∞ ∞ 2 ∞ 2 0 2 2 ∞ ∞ ∞ ∞ ∞ 2 ∞ 2 0 1 9 8 7 6 5 4 3 2 1 i/j 2 2 ① ② ③ 1 1 2 2 2 2 ④ 2 ⑤ ⑥ 2 ⑦ ⑧ ⑨ 2 2 图7-1 交通收集示企图 (2)进行矩阵迭代运算(第2步) = min[0+2,2+0,∞+2,2+∞,∞+2,∞+∞,∞+∞,∞+∞,∞+∞]=2 (i=1,j=2;k=1,2,…,9) 计较同理,如 : = min[0+∞,2+2,∞+∞,2+1,∞+0,∞+1,∞+∞,∞+2,∞+∞]=3 (i=1,j=5;k=1,2,…,9) 从节点1颠末两步达到5的最短权为3。其他元素按同样方式计较,获得D2。 (3)进行矩阵迭代运算(第3步) 颠末三步达到某一节点的最短距离为: (k=1,2,3,…,n) 式中, ——距离矩阵D2中的元素; ——距离矩阵D中的元素。 (k=1,2,3,…,n) 式中, ——距离矩阵Dm-1中的元素; ——距离矩阵D中的元素。 迭代不竭进行,曲到 ,即 中每个元素等于 此时的 即是肆意两点之间的最短权矩阵。 中的每个元素为止, (4)进行矩阵迭代运算(第m步) 颠末m步达到某一节点的最短距离为: 本例中, ,如下表所示。 0 2 4 2 3 4 4 5 6 9 2 0 2 3 2 3 5 4 5 8 4 2 0 4 3 2 6 5 4 7 2 3 4 0 1 2 2 3 4 6 3 2 3 1 0 1 3 2 3 5 4 3 2 2 1 0 4 3 2 4 4 5 6 2 3 4 0 2 4 3 5 4 5 3 2 3 2 0 2 2 6 5 4 4 3 2 4 2 0 1 9 8 7 6 5 4 3 2 1 i/j 用矩阵迭代法求解收集的最短,可以或许一次获得n×n阶的最短权矩阵,简洁快速。软件的开辟比Dijkstra方式节流内存,速度快。收集越复杂,该方式的优越性越较着。 例题7.3: 辨识出例题7-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.5 交通分派模子中存正在的问题 8.2 交通收集均衡取非均衡分派理论 8.1 概述 交通流分派 8.3 非均衡分派法 8.4 均衡分派法 背 景 总 结 例题8.4:设O D之间交通量q=2000veh/h,有两条径a取b。径a行驶时间短, 可是通行能力小,径b行驶时间长,但通行能力大。假设各自的行驶时间(min)取流量的关系为: 这时需要求径a,b上分派的交通流量。 按照Wardrop第一道理的定义,很容易成立下列的方程组: 则有: 【本章次要内容】 8.3 非均衡分派法 8.5 交通分派模子中存正在的问题 8.2 交通收集均衡取非均衡分派理论 8.1 概述 8.4 均衡分派法 交通流分派 容量多径方式 静态多径方式 多径 容量方式 全有全无方式 单径 变化阻 固定阻 8.3 非均衡分派方式 8.3 非均衡分派方式 8.3 非均衡分派方式 例题 7.5: 设图7-2所示交通收集的OD交通量为t=200辆,各径的交通费用函数别离为: 试用全有全无分派法求出分派成果。 8.3 非均衡分派方式 【解】: 全有全无分派法 由段费用函数可知,正在段交通量为零时,径1最短。 按照全有全无准绳,交通量全数分派到径1上,获得以下成果: 由于, ,按照 Wardrop 道理,收集没有达到均衡形态, 没有获得平衡解。此时网总费用为: 8.3 非均衡分派方式 8.3 非均衡分派方式 8.3 非均衡分派方式 8.3 非均衡分派方式 ,遏制计较。当前的段交通流量便是最终解; Step 0:初始化。将每组OD交通量等分成N等分,即便 同时,令 。 。 Step l:更新, 。 Step 2:增量分派。按Step 1计较所得 ,用0-1分派法将 的OD交通量 分派到收集中去。如许获得一组附加交通流量 。 Step 3:交通流量累加。即令 。 step 4:鉴定。若是 ,令 ,前往step l。 若是 8.3 非均衡分派方式 例题 7.6: 设图7-2所示交通收集的OD交通量为t=200辆,各径的交通费用函数别离为: 试用增量分派法求出分派成果。 8.3 非均衡分派方式 【解】: 增量分派法 采用2等分。 ①第1次分派 取全有全无分派法不异,径1最短。 ②第2次分派,此时最短径变为径2 这时,按照 Wardrop 道理,各条径的费用接近相等,网接衡形态,成果接近于均衡解。此时网总费用为: 8.3 非均衡分派方式 * * * * Produced by: Saiorbeyond E-mail: sailorbeyond@ 【本章次要内容】 8.5 交通分派模子中存正在的问题 8.2 交通收集均衡取非均衡分派理论 8.1 概述 交通流分派 8.3 非均衡分派法 8.4 均衡分派法 沉点问题: 1、Wardrop第一、第二道理 2、简单均衡分派模子的求解 3、非均衡分派中的增量分派方式 4、简单的随机分派问题求解 一、交通流分派概述 OD矩阵 ?? OD矩阵反映了各类体例的交通需求正在分歧时段的空间分布形态,这是需求预测前三个阶段获得的成果。 正在进行交通分派之前,需要将OD矩阵的单元转换为 交通量或运量的单元(如出行次数转换为车辆数)。 此外还需要进行时段的转换(如全日OD矩阵转换为 高峰小时OD矩阵)。 交通收集 交通收集是交通需求感化的载体。正在交通分派前,需要将现状(或规划)的交通收集笼统为 数学中的有向图模子,以表达交通收集的拓扑 关系和交通供给的各类特征。 二、交通收集概述 交通网的笼统取简化是由阐发费用取阐发精度的均衡决定的。 三、交通 :段a的所需时间; :段a上通过的交通流量。 :段a的交通容量,即单元时间内段a可通过的最大车辆数; :阻畅系数; :零流,即段a上为空静形态时车辆行驶所需时间。 最早的BPR函数中, , , 指适用交通容量; 后来颠末改良的BPR函数为 , 。 指不变交通容量。 2 2 ① ② ③ 1 1 2 2 2 2 ④ 2 ⑤ ⑥ 2 ⑦ ⑧ ⑨ 2 2 图7-1 交通收集示企图 步调1:给定起点1的P标号:P(1)=0,其他节点标上T标号: T1(2)=…=T1(9)=∞。 步调2:节点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、4为最小,任选其一,如节点2,即P(2)= T2(2)=2。 【解】 步调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为最小,给节点3标上P标号,即P(3)= T3(3)=4。 步调6:节点3刚获得P标号。节点6取3相邻,且为T标号,点窜6的T标号: T6(6)=min[T(6),P(3)+d36]=min[4,4+2]=4 正在所有T标号中,节点6为最小,给节点6标上P标号,即P(6)= T6(6)=4。 P(9) P(8) P(7) P(6) P(5) P(4) P(3) P(2) P(1) P标号 6 5 4 4 3 2 4 2 0 权 9 8 7 6 5 4 3 2 1 节点 采用逆序法寻求最小径,可得最短径为: 1-4-5-6-9,总的最小权为6。

请盲目恪守互联网相关的政策律例,严禁发布、、的言论。用户名:验证码:匿名?颁发评论

不预览、不比对内容而间接下载发生的问题本坐不予受理。1.本坐不应用户上传的文档完整性,