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

交通流分派_图

发布时间:2019-07-17

  交通流分派_数学_天然科学_专业材料。交通流分派 (Traffic Assignment) 交通流分派是本课程的沉点和难点之一。最优化理论、图论、 计较机手艺的成长,为交通流分派模子和算法的研究及开辟 供给了的根本,通过几十年的发

  交通流分派 (Traffic Assignment) 交通流分派是本课程的沉点和难点之一。最优化理论、图论、 计较机手艺的成长,为交通流分派模子和算法的研究及开辟 供给了的根本,通过几十年的成长,交通流分派是交通 规划诸问题中被国表里学者研究得最深切、取得研究最 多的部门。 本章次要讲述交通流分派的根基概念、根基道理和根基方式, 交通流分派的非均衡分派、均衡分派的模子和算法等内容。 交通配流 就是将预测得出的OD交通量,按照已知的道网 描述,按照必然的法则合适现实地分派到网中 的各条道上去,进而求出网中各段的交通 流量、所发生的OD费用矩阵,并籍此对城市交通 收集的利用情况做出阐发和评价。 径1 O 径2 D 径n D O 交通配流的成长阶段 最后的交通流分派研究,多采用全有全无方式。 该方式处置的常抱负化的城市交通收集,即假设 收集上没有交通拥堵,阻是固定不变的,一个OD 对间的流量都分派正在“一条径”,即最短径上。 但对于既有的城市内部拥堵的交通收集,该方式的结 果取收集现实环境收支甚大。 交通配流的成长阶段 正在1952年,出名交通问题专家Wardrop提出了收集均衡分派 的第一、第二,人们起头采用系统阐发方式和均衡阐发 方式来研究交通拥堵时的交通流分派。 确定性的均衡配流:其前提是假设出行者可以或许切确计较出每 条径的,从而能做出完全准确的选择决定,且每个出 行者的计较能力和程度是不异的。 现实中出行者对段的控制只能是估量而得。对统一 段,分歧出行者的估量值不会完全不异,由于出行者的计较 能力和程度是各别的。 交通配流的成长阶段 正在1977年,对交通流分派理论研究最积极、活跃的美国 大学伯克利分校的Daganzo传授及麻省理工学院的Sheffi传授 提出了随机性分派的理论。 随机性分派的前提是认为出行者对段的估量值取现实 值之间的不同是一个随机变量,出行者会正在“多条径”中 选择,统一路迄点的流量会通过分歧的径达到目标地。 随机性分派理论和方式的提出,正在拟合、反映现实交通收集 现实的历程中又推进了一大步。 交通配流的成长阶段 网上的拥堵性、径选择的随机性、交通需求的动态性是 同时存正在并交互感化的,其机理是纷繁复杂的。 实正地合适网现实环境,还有更主要更根基的交通需求的 时变性(即动态性)需要反映出来。 需要一种交通流分派方式可以或许将网通流的拥堵性、 径选择的随机性、交通需求的时变性分析集成地描绘反映出 来,这是研究交通问题的学者一曲积极摸索的问题。 两种机制彼此感化曲至均衡: 一种机制是:各类车辆试图通过正在收集上选择最佳行驶线 来达到本身出行费用最小的方针; 另一种机制是:道上的车流量越大,用户碰到的阻力即对 应的行驶越高。 用必然的模子来描述这两种机制及其彼此感化,并求解收集 通流量正在均衡形态下的合理分布,即交通流分派。 基 本 概 念 交通流分派的几种模式 (1) 将现状 OD 交通量分派到现状交通收集上,以阐发目前交 通收集的运转情况,若是有某些段的交通量不雅测值,还可 以将这些不雅测值取正在响应段的分派成果进行比力,以查验 模子的精度。 (2) 将规划年 OD 交通量预测值分派到现状交通收集上,以发 现对规划年的交通需求来说,现状交通收集的缺陷,为交通 收集的规划设想供给根据。 (3)将规划年OD交通量预测值分派到规划交通收集上,以评 价交通收集规划方案的合。 交通流分派的根基数据 (1)暗示需求的OD交通量。正在拥堵的城市道网中凡是 采用高峰期OD交通量,正在城市间公网中凡是采用年平均 日交通量(AADT)的OD交通量; (2) 网定义,即段及交叉口特征和属性数据,同时 还包罗当时间—流量函数; (3)段函数。 从交通流分派的特点来说,能够分为两类: 交通东西的运转线固定类型和运转线不固定类型。 线固定类型有公共交通网和轨道交通网,这些是集体 搭客运输; 线不固定类型有城市道网、公网,这一般是指个 体搭客运输或货色运输,这类收集中,车辆是选择 运的。 交通(交通费用) 交通或者称为阻是交通流分派中经常提到的概念, 也是一项主要目标,它间接影响到交通流径的选择和流 量的分派。 道正在交通流分派中能够通过阻函数来描述。 所谓阻函数是指段行驶时间取段交通负荷,交叉口 耽搁取交叉口负荷之间的关系。 交通收集上的阻(费用),应包含反映出行时间、出行 费用、平安、舒服程度、便利性和准时性等等很多要素。 颠末大量的理论阐发和工程实践,人们得出影响阻的从 要要素是时间,因而出行时间常常被做为计量阻的次要 尺度。 交通有两部门构成:段上的、节点处的。 段 出行时间取流量的关系比力复杂,能够广表达为: 即段a上的费用 不只仅是段本身流量的函数,并且是整 个网上流量V的函数。 对于公网而言,因为段比力长,大部门出行时间是正在 段上而不是正在交叉口上,费用和流量的关系能够简化为: 即段的费用只取该段的流量及其特征相关。 美国道局(BPR—Bureau of public road)开辟的函数,被称 为BPR函数: :段 上的; :零流,即段 上为空静形态时车辆行驶所需 要的时间; :段 上的交通量; :段 的现实通过能力,即单元时间内段现实可通过 的车辆数; :正在美国公局交通流分派法式中,这两个参数的取值别离 为 0.15、4。也可由现实数据用回归阐发求得。 节点 车辆正在交通收集节点处次要指正在交叉口处的。 交叉口取交叉口的型式,信号节制系统的配时,交叉口 的通过能力等要素相关。 正在城市交通收集的现实出行时间中,除段行驶时间外,交 叉口耽搁拥有较大的比沉,出格是正在交通高峰期间,交叉口 拥堵堵塞比力严沉时,交叉口耽搁将跨越段行驶时间。 1958年英国TRRL研究所的F.V. Webster 等人按照列队论理论, 提出了一个计较交叉口耽搁的模子。该模子中次要包罗两部门: 一部门是车辆达到率为固定均值时发生的一般相位耽搁即平均 耽搁; 另一部门是车辆达到率随机波动时所发生的附加耽搁。 T:信号周期长度; ?:进口道无效绿灯时间取信号周期长度之比,即绿信比; Q:进口道的交通流量; X:饱和度,X=Q/S ,S为进口道通过能力。 交通均衡问题 Wardrop提出的第一道理定义: 正在道的操纵者都切当晓得收集的交通形态并选择最短径 时,收集将会达到均衡形态。正在考虑拥堵对行驶时间影响的 收集中,当收集达到均衡形态时,每个 OD对的各条被利用 的径具有相等并且最小的行驶时间;没有被利用的径的 行驶时间大于或等于最小行驶时间。 这条定义凡是简称为Wardrop均衡,正在现实交通流分派中也 称为用户平衡(UE, User Equilibrium)或用户最优。 Wardrop提出的第二道理: 正在系统均衡前提下,拥堵的网通流该当按照平均或 总的出行成本最小为根据来分派。 Wardrop第二道理,正在现实交通流分派中也称为系统最优 道理(SO,System Optimization)。 第一道理次要是成立每个道操纵者使其本身出行成本 (时间)最小化的行为模子,而第二道理则是旨正在使交通 流正在最小出行成本标的目的上分派,从而达到出行成本最小的 系统均衡。 第二个道理做为一个设想道理,是面向交通办理工程师的。 正在现实交通中,人们更期望交通流可以或许按照Wardrop第一 道理,即用户均衡的近似解来分派。 例子: 设OD之间交通量为q=2000辆,有两条径a取b。径a行 驶时间短,可是通行能力小,径b行驶时间长,但通行能 力大。假设各自的行驶时间(分钟)取流量的关系是: 按照 Wardrop均衡第一道理的定义,很容易成立下列的方 程组: 则有: 明显 只要正在非负解时才成心义,即 也就是说,当OD交通量小于250时, ,则 即所有OD 都沿着径a走行。 当OD交通量大于250时,两条径上都有必然数量的车辆行 驶。当 时,均衡流量为: 即均衡时两条径的行驶时间均为22分钟。 ? 从1952年Wardrop提出道网均衡的概念和定义之后,如 何求解Wardrop均衡成了研究者的主要课题。 ? 1956年,Beckmann等提出了描述均衡交通流分派的一个数 学规划模子。 ? 颠末20年之后,即到1975年才由LeBlanc等学者设想出了求 解Beckmann模子的算法(将Frank-Wolfe算法用于求解该模 型),从而构成了现正在的适用解法。 Wardrop道理—Beckmann模子—LeBlanc算法这些冲破是交通 流分派问题研究的严沉前进,也是现正在交通流分派问题的根本。 对于完全满脚Wardrop道理定义的均衡形态,则称 为均衡分派方式。 对于采用式方式或其它近似方式的分派模子, 则称为非均衡分派方式。 非均衡分派方式 非均衡分派方式按其分派体例可分为变化阻和固定阻两 类,按分派形态可分为单径取多径两类。 分派形态\分派体例 固定阻 变化阻 单径 多径 全有全无方式 静态多径方式 容量方式 容量多径方式 全有全无分派方式(all-or-nothing) 将OD交通量T加载到网的最短径树上,从 而获得网中各段流量的过程。 第1步:初始化,使网中所有段的流量为0, 并求出各段流形态时的; 第2步:计较网中每个出发地O到每个目标地D 的最短径; 第3步:将O、D间的OD交通量全数分派到响应 的最短径上。 增量分派法(incremental assignment method) 该方式是正在全有全无分派方式的根本上,考虑了 段交通流量对的影响,进而按照道的变 化来调整网交通量的分派,是一种“变化阻” 的交通量分派方式。 增量分派法有容量-增量加载分派、容量迭代均衡分派两种形式。 容量-增量加载分派方式 ?将OD交通量分成若干份(等分或不等分); ?轮回地分派每一份的OD交通量到收集中; ?每次轮回分派一份OD交通量到响应的最短径; 每次轮回均计较、更新各段的行驶时间,然后 按更新后的行驶行驶时间从头计较最短径; ?下一轮回中按更新后的最短径分派下一份OD 交通量。 第1步:初始化。朋分OD交通量: = 令n=1 。 第2步:计较、更新段费用: 第3步:用全有全无分派法将第n个朋分OD交通量 到最短经上。获得每条段上的流量 。 第4步:计较 。 分派 第5步:若是n=N,则竣事计较。反之,令n=n+1前往第2 步。 当朋分数 N=1 时即是全有全无分派方式,当 N 趋势于无限 大时,该方式趋势于均衡分派法的成果。 长处: 简单可行,切确度能够按照朋分数N的大小来调整;实践 中经常被采用,且有比力成熟的贸易软件可供利用。 错误谬误: 取均衡分派法比拟,仍然是一种近似方式;当阻函数不 是很时,会将过多的交通量分派到某些通行能力很小 的段上。 容量-迭代均衡分派 增量加载和迭代均衡分派形式的道理根基是不异的。但增量 加载方式事先无法估量迭代次数及计较工做量,对于较复杂 的收集,可能会由于个体段的迭代精度无法满脚要求而使 迭代进入死轮回,呈现算法不的环境。 美国联邦公局对这一算法进行了改良: ? ? 事先设定一个最大迭代次数N(N4) 当前迭代的值为前两次值的加权值 均衡流解即取最初四次迭代的段流量的平均值。 第1步:初始化。令 ,用全有全无方式将OD矩阵 加载到交通收集上,获得段流量 ,设置迭代次数n=1。 第2步:计较 。 , 第3步:加权滑润。计较 此中权值0.75和0.25是由经验获得的。 第4步:收集加载。按照段的值 ,用全有全无方式将 OD矩阵加载到交通收集上,获得段流量 。 第5步:若是n=N,则竣事计较。反之,令n=n+1前往第2步。 迭代平均法(MSA算法) 不竭调整各段分派的流量而逐步接衡分派成果。每步循 环中,按照各段分派到的流量进行一次全有全无分派,获得 一组各段的附加流量; 然后用该轮回中各段已分派的交通量和该轮回中获得的附加 交通量进行加权平均,获得下一轮回中的分派交通量; 当相邻两次轮回平分配的交通量十分接近时,即遏制运算,最 后一次轮回中获得的交通量即为最终成果。 第1步:初始化。令 。按照各段行驶时间 进行全有全无分派,获得初始解 。令迭代次数n=1。 第2步:更新段的,按照当前各段的交通量计较各 段的阻 。 第3步:按照段行驶 将OD交通量进行全有全无分 配。获得各段的附加交通量 。 第4步:更新段流量。计较 第5步:若是持续两次迭代的成果相差不大,则遏制计较。 即为最终分派成果。不然令n=n+1,前往第2步。 持续平均法是介于增量分派法和均衡分派法之间的 一种轮回分派方式。 MSA方式是既简单合用,又最接近于均衡分派法 的一种分派方式;若是每步轮回中1/n的严酷按照 数学规划模子取值时,即可获得均衡分派的解。 例题 设图示交通收集的OD交通量为 交通费用函数别离为: 辆,各径上的 试用全有全无分派法、增量分派法法求出分派成果,并 进行比力。 1 2 3 i j 全有全无分派法 由段费用函数可知,正在段交通量为零时,径1最短。根 据全有全无准绳,交通量全数分派到径1上,获得以下成果: 很较着,按照Wardrop道理,收集没有达到均衡形态。 此时网总费用为5000。 增量分派法(假定N=2) 第1次分派:取全有全无分派法不异,径1最短。获得下 面成果: 第2次分派:此时最短径变为径2,获得下面成果: 此时网总费用为2750。 均衡配流模子及算法 ?Wardrop均衡分派道理的数学模子 ?均衡分派模子的求解算法 ?用户均衡分派模子 ?系统最优均衡分派模子 模子中所用变量和参数 :段a上的交通流量; :段a的交通,也称为行驶时间; :段a的函数,也称为行驶时间函数; :出发地为r,目标地为s的OD间的第k条径上的流量; :出发地为r,目标地为s的OD间的第k条径的; :出发地为r,目标地为s的OD间的最短径的; :段-径相关变量,即0-1变量。若是段a属于 从出发地为r目标地为s的OD间的第k条径,则为1,否 则为0。 R:收集中出发地的调集; S:收集中目标地的调集; :出发地r和目标地s之间的所有径的调集; :出发地r和目标地s之间的OD交通量。 Wardrop用户均衡原则 当交通收集达到均衡时,如有 0,必有 申明若是从r到s有两条及其以上的径被选中,那么它们的行 驶时间最小且相等; 如有 =0,必有 申明若是某条从r到s的径流量等于零,那么该径的行驶时 间必然不小于被选中的径的行驶时间。 根基守恒前提 (1)OD间各条径上的交通量之和应等于OD交通总量 (2)段上的流量等于利用该段的各条径的流量之和 ?k ? Wrs (3)径的等于构成该径的各个段的之和 (4)径流量满脚非负束缚 用户均衡配流模子(Beckmann模子 ) 用户平衡的概念 例题 如图所示,一个有两条径(同时也是段)、毗连一 个出发地和一个目标地的简单交通收集,两个段的阻 抗函数别离是: t1=2+x1,t2=1+2x2 OD量为q=5,别离求该收集的Beckmann均衡模子的解 和均衡形态的解。 1 R 2 S 将函数带入模子,得: s.t. x1+x2=5 x1,x2≥0 将 x1=5-x2带入方针函数并进行积分,获得下面极小值问题: min:Z(X)=1.5x12-9x1+30 令dZ/dx1=0 解得x1*=3,x2*=2。 求均衡形态的解 按照Wardrop用户均衡道理: t1=t2 x1+x2=5。 求解这个方程组,很容易求得x1=3,x2=2。 此时,t1=t2=5。 可见,Beckmann模子的解和均衡形态的解完全不异。 等价性证明 按照非线性规划理论,对模子构制拉格朗日( Lagrange ) 函数: 此中, 是拉格朗日乘子,也是rs之间的最小。 按照非线性规划理论中的库恩· 塔克(Kuhn-Tucher)前提, 拉格朗日函数正在极值点必需满脚下列前提: 库恩· 塔克前提能够简化暗示为: 对于某个特定的毗连r和s的径,某径k的流量 种可能: ①若是 ,得 ; 有两 ②若是 ,得 。 求解方式 步调1:初始化:按照 获得各段的流量 步调2:更新各段的 步调3:寻找下一步迭代标的目的:按照更新后的 再进行一次0-1交通流分派,获得一组附加流量 步调4:确定迭代步长:用二分法求满脚下式的λ ,进行0-1交通流分派, ;令n=1; : , ; 步调5:确定新的迭代起点 步调6:性查验。若是满脚: ; 此中ε 是事后给定的误差限值,则 就是要求的均衡 解,计较竣事;不然,令n=n+1,前往步调2。 系统最优模子 该模子称为系统最优模子SO(System Optimization)。 Beckmann模子称为用户均衡模子UE(User Equilibrium)。 系统最优分派取用户最优分派的关系: 对函数进行变换,令: 若是用 做为函数,则此时用户最优分派模子完全 能够转换为系统最优分派模子,所以进行该函数下的用 户最优分派,获得的解就是系统最优分派的解。 2 1 1 1 2 3 3 1 3 4 4 2 1 1 2 5 3 3 4 4 最短径算法 好的交通量分派法必需有一种好的最短径计较方式 寻找O-D对之间的最小费用径,简称最短径,是求 解交通收集均衡配流问题的焦点。 ? 任何一种交通量分派法都是成立正在最短径的根本上; ? 任何一个分派法中,最短径的计较占领了全数计较 时间的次要部门。至多有90%的计较时间花正在最短径 的寻找上。 求解最短径算法 迪杰斯特拉(Dijkstra)算法,即标点法(Labelcorrecting method) 矩阵迭代法 标点法 根基思惟: 频频扫描收集的节点,正在每次扫描中,该方式试图 发觉从根节点到正正在扫描的节点之间的、比现有 径更好的径,当从根节点到所有其它节点之间没 有更好的径时,算法就遏制搜刮。 正在此算法中,为每一个节点设置两个记实: (1) 标号 ,暗示沿着最短径从根节点到节点 的最小 费用; (2)紧前节点 的节点。 ,暗示沿着最短径达到节点 且最接近 正在每次扫描中,将紧前节点都记实下来,构成紧前节点 序列,这是为了遏制扫描时,能反馈地找出最短径的 轨迹。 查抄列中包含正正在和需要进一步查抄的节点,控制节点被 查抄的动态; 标号列中记录各节点的标号; 紧前节点列中记录各节点的紧前节点,按照紧前节点列可 以找到节点之间的最短径; 每进行一步新的扫描,标号列、紧前节点列和查抄列就要 更新一次,当查抄列中不再有节点时,算法遏制。 算法步调: 第一步:初始化,置所有标号为无限大(或一个很大的正 数),置所有的紧前节点为零,将根节点 放入查抄列 中,并令 ; 第二步:从查抄列中任选一个节点,例如节点 ,扫描 所有从 节点出发只颠末一条弧便可达到的节点,例如 节点,若是: 则更新节点 上的标号,令 到节点 的弧上的值。 若是式子不成立,则节点 , 是从节点 的标号不变。 第三步:正在改叛变点 的标号的同时,点窜 ,且将 插手到查抄列中(由于从节点 出发还可能达到其它节 点)。当从 出发只颠末一条弧便可达到的所有节点都被检 查过时,就从查抄列中删除 节点。 第四步:当查抄列中不再有节点时,算法遏制。从根节点到 其它肆意节点的最短径可通过反向搜刮最初的紧前节点序 列识别出来。 例:包含4条弧的简单收集,此中根节点为1,弧上的数 字暗示弧的。 1 2 3 1 1 1 4 4 第一步:所有节点的标号都置为 ,其紧前节点都置 为零。然后,节点1的标号变为0,且把它放到查抄列中。 第二步:从节点1出发能够达到节点2和4,先考虑节点4, 由于 ,则节点4的标号变为4,且被 放入到查抄列中。 迭 代 0 1 2 3 标号列 节点 1 0 0 0 0 1 1 2 节点 2 节点 3 节点 4 节点1 0 4 4 4 0 0 0 紧前节点列 节点 2 0 0 1 1 节点 3 0 0 0 2 节点 4 0 1 1 1 查抄 列 1 1,4 2,4 3,4 4 5 0 0 1 1 2 2 3 3 0 0 1 1 2 2 3 3 4 矩阵迭代法 根基思惟: (1)是借帮距离(权)矩阵的迭代运算来求解 最短权的算法。 (2)该方式能一次获得肆意两点之间的最短权 矩阵。 算法步调: (1)起首构制距离矩阵(以距离为权的权矩阵) (2)矩阵给出了节点间只颠末一步(一条边)达到某一 点的最短距离 (3)对距离矩阵进行如下的迭代运算,便能够获得颠末 两步达到某一点的最短距离: k=1,2,3…,n n:收集节点数; *:矩阵逻辑运算符; dik,dkj :距离矩阵D中的响应元素。 例题:用矩阵迭代法计较下图所示网肆意节点之间的最短 值。 2 2 2 1 2 2 3 2 4 2 1 2 5 1 6 2 7 2 8 2 9 (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 (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) 其它元素按同样方式计较,获得D2 (3)进行矩阵迭代运算,颠末三步达到某一节点的最短 距离为: D3= D2 *D=[d3ij] [d3ij] =min[d2ik+dkj] k=1,2,3…,n d2ik :距离矩阵D2中的元素; dkj:距离矩阵D中的元素。 迭代不竭进行,曲到: Dm= Dm-1。即:Dm中的每个元素等 于Dm-1 中的每个元素为止,此时的Dm即是肆意两点之间的 最短权矩阵。 距离矩阵 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 3 4 2 0 4 3 2 6 5 4 4 2 3 4 0 1 2 2 3 4 5 3 2 3 1 0 1 3 2 3 6 4 3 2 2 1 0 4 3 2 7 4 5 6 2 3 4 0 2 4 8 5 4 5 3 2 3 2 0 2 9 6 5 4 4 3 2 4 2 0 随机分派方式 随机用户均衡的问题 任何一个道操纵者均不成能通过片面改变其 径来降低其所估量的行驶时间时,达到了均衡 形态,这就是所说的“随机用户均衡(stochastic user equilibrium)”即SUE问题。 非均衡随机分派方式 模仿随机分派法(simulation-based):使用 Monte-Carlo等随机模仿方式发生段的估量 值,然后进行全有全无分派; 概率随机分派法(proportion-based):操纵Logit 等模子计较分歧径上承担的出行量比例,并由 此进行分派。 3、Dial算法以及其缺陷 Dial算法 Dial算义无效径为:O-D对rs之间的径是无效的, 是指它所包含的所有段都令出行者离起始点越来越远,离 终结点越来越近。 只要当O-D对rs之间的径上肆意段(i,j)满脚以下前提 时,该径才算是无效径。 且 (1) 3、Dial算法以及其缺陷 第一步:对于每一节点,采用最短算法计较 第二步:对于段(i,j),计较段似然值: 和 , ; 第三步:向前计较段权沉。从起点起头,按照 的上升挨次 对每一个节点,计较分开它的所有段的权沉值。 当达到终节点时遏制计较。 3、Dial算法以及其缺陷 第四步:向后计较段流量。从起点起头,按照 s( j ) 的上升顺 序顺次考虑节点,对于每一个节点,计较进入它的所有段上 的流量。 3、Dial算法以及其缺陷 Dial算法对无效径的定义过于 严酷,将导致分派成果中较 低的径不被利用,而较高 的径反被利用的现象。 按照Dial 算法的初始化阶段,计 算成果如表所示: 节点 1 0 4 2 2 2 3 2 2 4 2 2.5 5 4 0 按照Dial算法,段(2,3)不属于无效径的段,如许,径1-2-35就被解除正在无效径之外,但这条径的均为4.5,而被认为是有 效径1-4-5的值为5,明显,这是不合理的。若是按照“一步走过 ”算法,则所有连通径城市被看做为无效径,而此时径1-2-3-4-5 的为6,为最小的1.5倍,明显,这正在现实中也是不合理的。 3、Dial算法以及其缺陷 Dial算法假定径的选择概率取该径所包含的所有段似然 值的乘积成反比例关系,即 这种假定前提申明,径所包含的段数量越多,那么该径 被出行者选择的概率就越小。可是正在现实的道交通收集中, 可能会呈现如许的环境,正在某个O-D间的某条径上,虽然此 径所包含的段数量较多,但这些段的费用都较小,那么该 条径被选择的概率就会响应的较大。因为Dial算法正在判断有 效径的原则中没有考虑段费用的消息,从而可能发生取实 际环境有较大误差的配流成果。 随机均衡分派方式 考虑拥堵要素下的随机用户均衡( SUE )分派问 题,即段是随交通量变化的,假设 段的期望值是段交通量的函数。 随机用户均衡分派中道操纵者的径选择行为 仍遵照Wardrop第一道理,只不外他(她)们选择的 是本人估量最小的径来出行。 随机均衡分派模子 随机均衡分派算法 步调1:初始化。按照各段的初始行驶时间 (能够取零 流时间)进行一次随机分派,获得各段的分派交通量 , 令n=1。 步调2: 按照当前各段的分派交通量 计较各段的行驶 时间。 步调3: 按照第二步计较的各段行驶时间和OD交通量进行 随机分派,获得各段的附加交通量 。 步调4: 用迭代加权的方式计较各段的当前交通量: 步调5: 判断。若是满脚要求,则遏制计较;不然, 令n=n+1,前往步调2。 n ?1 xa Fisk模子 Fisk 于 1980 年提出了一个最优化问题 , 该问题中 O-D 矩阵 ( )已知,段流量( )被间接视为变量。能够证明最优 化问题的解对应于Logit形式的径选择公式,故它也是 一个SUE前提解. s.t. 式中 是一个非负的校正参数。它控制了整个模子的随机特 性。当 时,方针函数的第二项就会节制整个函数,模子 就变为一个尺度的UE问题。当 时, O-D矩阵( )将均 匀的分布到收集上,相当于令所有径的都相等。现实 上, 它申明 增大时,段方差减小,整个模子向确定性的 UE接近。可是,模子从外表上看,不是一个随机配流模子, 却含有Logit形式随机配流问题的全数特征。 Fisk模子有几个问题至今没有很益处理: (1)若何完成径列出; (2)若何校正参数; (3)若何设想无效的算法. ? Dial算法; 求解尺度UE问题,每次迭代中都要寻找一次最短径 并实行配流,将每一次迭代过程中的最短径都存贮 起来,最初进行比力:两次迭代成果不异的,去掉一 个;值较着大大高于一般径的,也去掉。 最初剩下的径就认为是无效径. 求解方式 第一步:确定无效径的调集。 第二步:按照 , ,计较无效径的,然后按照Logit模 型计较初始径流量 , 。置迭代次数 。 第三步:由( )计较新的径,再用Logit模子计较新的径 流量( )。 第四步:确定搜刮步长。解一维搜刮问题,确定迭代步长 更新的径流量是 第五步:性查抄。若满脚,则遏制迭代;不然,令 第三步。 ,转