基于路网可达性的城市交通离散网络设计模型及算法

基于路网可达性的城市交通离散网络 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 模型及算法 基于路网可达性的城市交通离散网络设计 模型及算法 基于路网可达性的城市交通离散网络设计模型及算法——邓克涛63 基于路网可达性的城市交通离散 网络设计模型及算法 邓克涛 (铁道警官高等专科学校铁路与公安基础教研部郑州450053) 摘要根据城市交通路网分区理论,把分成的子区看成一个节点,考虑所有节点的可达性,以此度 量整个路网的可达性,设计了基于路网可达性最大为目标的城市交通离散网络设计模型.采用粒子 群算法,并给出一个简单的算例,算例表明,合理的添加路段,能使城市路网可达性达到最大. 关键词可达性;城市交通;离散网络设计;粒子群算法 中图分类号:U412文献标志码:ADOI:10.3963/j.ISSN1674—4861.2012.O1.014 O引言 城市交通网络设计问题在一定的投资约束条 件下,通过在现有的城市交通网络中增加新的路 段或更新,改善已有路段的通行能力,从而使整个 交通网络某种系统性能指标达到最优.网络设计 问题(networkdesignproblem,NDP)可分为2 类:?对已有路段改造以增加其通行能力,称作连 续网络设计问题(continuousNDP,CNDP),这里 的连续是指路段通行能力的增加量是连续的;? 添加新路段,被称作离散网络设计问题(discre— tionNDP,DNDP).高自友等以城市交通网络 设计问题中的双层规划模型,方法及应用等方面 做过大量的研究E1-~3;许良,高自友从路网可靠性 研究城市交通网络设计问题,从路网连通性可靠 性,行程时间可靠性和路网容量可靠性3方面来 考虑交通网络设计问题[6_8].路网评价指标包括 路网可靠性,路网可达性等,而基于路网可达性的 城市交通网络设计问题国内学者很少有人涉及 到,基于此,本文从路网可达性,设计了一个双层 规划模型,研究了城市交通网络设计问题. 1可达性涵义 本文研究可达性的目的主要是通过考察路网 中单个结点的可达性来进一步确定整个路网的可 达性,以便研究路网在空间布局和路线的等级配 置及其分布上的合理性,保证新修建的路段使路 网可达性达到最大.因而研究的思路是从单个结 点扩展到整个道路网.与此相对应,结点可达性 的定义大体上有2种:?将结点可达性定义为在 规划区域内从该点出发抵达其他各点的平均行程 距离或行程时间;?首先定义理想路网,并定义结 点的什贝尔指数为某结点到路网中其他所有结点 的最短距离之和,在此基础上将可达性定义为结 点相对于实际路网的什贝尔指数与相对于理想路 网的什贝尔指数之比值.根据以上对可达性的理 解,本文可以简单认为可达性是指一个地方到达 另一个地方的容易程度,可以用旅行距离,旅行时 间或感知距离来衡量. 2城市交通路网分区理论 城市交通网络是城市交通的动脉,按道路在 城市中的地位,作用,交通性质,交通速度及交通 流量等指标,可将道路分为高速干道,主干道,次 于道及支路4类.为了研究问题的方便,对城市 交通路网进行如下三级分区.以道路等级为依据 的一级分区,以城市整体布局和功能分区的二级 分区,以子区为基础的三级分区.其中,二级分区 和三级分区是针对普通道路区进行的,见图1. 具体做法如下. 1)依据道路等级原则进行一级分区,将整个 城市交通网络分为3大区域:高速干道区,普通道 路区,交汇区. 2)对于普通道路区,依据区域功能原则进行 收稿日期:201卜O6—09修回日期:2011-09—3O 第一作者简介:邓克涛(1982),硕士.研究方向:警用铁道技术及交通安全研究.E— mail:0206257@163.com 64交通信息与安全2012年1期第30卷总166期 二级分区,将普通道路区分为:居民区,工业区,商 业区等;对于高速干道区和交汇区,主要依据入口 匝道的位置和它们之间的距离进行子区的进一步 划分. 3)最后,对普通道路区在第2步的基础上结 合交通控制子区,根据实际交叉口的位置和交叉 口之间的距离进行进,步的划分子区. 城市道路网络 高速于道区ll普通道路区ll交汇区 l随叁垦I 囱囱崮囱囱 图1城市交通分区体系结构 Fig.1Urbantransportationdivisionarchitecture 3数学模型 3.1可达性模型 3.1_1节点可达性一考虑时间阻抗函数的节点 的可达性 根据城市交通路网分区理论,把考虑的城市 交通路网分成个分区.这里,交通分区用其质 心表示,在交通网路中,它是个节点.考察路网中 单个结点的可达性来进一步确定整个路网的可达 性.假定节点i与节点J之间共有m条路径,z 表示2点之间实际距离,km,则节点i到节点.『的 最大可达性忌为2点之间最短路径距离与2点 之间所有路径距离之和的比值,k可表示为: 曼一—gij(sh— ortest)— 1,2,…,;Vi,J(1) ?z 式中:学为节点i与节点J之间第s条路径距离; ?学为节点i与节点J之间所有条路径的总 距离;s=1,2,…,/Tt;i,一1,2,…,.当2点之间 的实际距离l取最小值时,即2点之间距离为 z是取最小,此时节点i到节点J具有最大 可达性. 考虑路网所有节点到节点i可达性K,进行 简单的求和,则K可表示为 K一?愚=? i ?to|?|芋t,l s一1,2,…,m;Vi,J(2) 3.1.2考虑时间阻抗函数的节点的可达性 在实际情况中,可达性往往以时间最小为衡 量指标,此时虽然路径最小,但是在交通主体选择 最短路径导致交通拥挤时,很有可能使得车速降 低,时间延续加长,导致可达性降低.为此引入了 道路阻抗函数,更加全面的衡量路网所有节点到 节点i可达性K.将时间概念体现到模型中,则 式(2)可改进为如下,得到考虑时间阻抗函数的节 点i的可达性K: K一?点,一?, s一1,2,…,m,Vi,(3) 式中:K为考虑时间阻抗函数的节点i的可达 性,h,t为节点i到节点J之间的最短出行时间, h.路网阻抗函数采用美国道路局开发的BPR函 数,形式为 ta(0)f_1+a(芑)]V口EA(4) 式中:t(O)为路段n零交通量行走时间,h;Co为 路段a的通过能力,辆/d;aEA;a,J9为待定参数, 建议取0t一0.15,一4.0,也可由实际数据用回归 分析取得.对于参数和t.(0)可由路段a的实 测数据分析得到.则t可表示为 t=?t.(z),VaEA(5) 式中:A.为节点i到节点之间的最短出行时间 的走行路段集合. 3.1_3路网可达性 把考虑的城市交通路网分成n个分区,交通 分区用其质心表示,在交通网路中,认为它是个节 点.则交通网络中有个节点,整个网络的可达 性A认为是所有节点的可达性之和,则A表 示为 A一?K一?kt4一 i=1 [萋(爹.EAC1]S一1,2,…,,Vi,J,VaEA(6) 3.1.4考虑节点重要度的路网可达性 为了使路网可达性计量模型能够考虑节点之 间的相对重要度,也就是分区之间对流量吸引不 同,将节点的可达性以其重要度为权重,将路网中 所有节点的可达性的加权求和值作为路网的可达 性,可表示为: 基于路网可达性的城市交通离散网络设计模型及算法——邓克涛65 ?K A一兰一 ? 礁[爹 ?J— I S一1,2,…,m,Vi,J,Va?A(7) 式中:A为考虑节点重要度的路网可达性;为 节点i的重要度. 3.2基于路网可达性的城市交通离散网络设计 进行城市交通网络设计的目的就是通过建设 新的路段或改善已有路段的能力,从而满足日益 增长的交通需求量.现实中有时只提高部分路段 的能力或许并不能满足网络的要求,需要新建路 段才能显着缓解交通拥挤,提高路网的可达性,本 文提出以路网可达性最大为上层目标函数,由于 路网中的节点重要度反映路网各节点功能强弱的 特征量或特征参数,是描述节点在交通网络中所 处地位,重要程度相对大小的一个量化指标,其计 算主要根据反映和度量节点社会经济活动的指标 来确定,实际中是很难确定的,所以本文不予考 虑,但并不影响路网可达性,基于此,本文设计了 如下数学模型. 定义符号和参数如下:i,J为节点,i,J一1, 2,…,;为从节点i到节点的路径条数;为 从节点i到节点的第s条路径距离,s一1,2,…, m;口为路段,路段n的下标用1,2,…,,+1, … ,+叫表示,a?A,A—A1UA2.其中:A为 已经存在的路段集合,A一{a,a,…,a);A.为 备选的 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 新建的路段集合,A一{n,a+, … ,a计};Al,为节点i到节点J之间的最短出行 时间的走行路段集合为计划修建路段n的修 建费用;B为用于修建路段的预算投资总额; 为OD对间路径P上的流量;q为OD对的 基本出行. 定义逻辑参数如下:.为路径一路段关系参 数,如果OD对之间的路径p通过普通路段a, 则取值为1,否则为0. 定义决策变量和从变量如下:为路段a是 否修建的O一1变量,当路段a修建时Ua一1,否则 Ua----0;ll一("l,乱+2,…,+)为该决策变量的向 量表示;为路段流量向量,一(,z.,…,, 卅??Xv+w);chor)为从节点i到节点最小距 离,它是U的函数;,.(z.,Ua)为路段阻抗函数. 3.2.1上层规划模型 minAt(,|1)一 镌[爹.]] s.t.??BVn?A2(8) =:=0或1,Va?A2(9) 约束条件(8)为拟修建道路不超过预算投资; 约束条件式(9)为决策变量取值限制. 3.2.2下层规划模型 minF=:=?.(叫,")aEA s.t.?f一%V,P(1o) P ?0,V,P(11) z一 ??,V/j,,n?A(12)P 约束条件式(10),(12)为路网流量守恒条 件. 4求解算法 城市交通离散网络设计问题实际上是一个非 线性整数规划问题,模型的上层网络规划者在满 足预算投资约束及其它约束条件下使路网在添加 若干路段后使路网的可达性达到最大.下层规划 中假定OD需求量固定,并且用户的路径选择行 为符合用户平衡分配(userequilibrium,UE)原 则.基于此,上层规划采用粒子群算法,下层规划 用Frank-Wolfe算法,算法基本思想和算法设计 如下. 4.1粒子群算法基本思想 粒子群算法表示如下,设x一(,,…, z)为粒子i的当前位置;V一(,…,)为 粒子i的当前飞行速度;P一(p—P…,P)为 迄今为止粒子i所经历的最好位置,也就是粒子i 所经历过的具有最好适应值的位置,称为个体最 好位置.对于最小化问题,目标函数值越小,对应 的适应值越好. 如何找到一个合适的表达式,使粒子与解对 应,是实现算法的关键问题之一.本文构造一个 W维的空间来表达叫条待修建的路段的网络设 计问题.设每个路段a对应是否修建的0—1变 量,a?A,现在就是要把这种形式的可行解与 66交通信息与安全2012年l期第3O卷总166期 粒子对应起来. 例如,设原有路段4条,待修建的路段有6 条,则lI一(1,0,1,0,0,1)为原问题的一个可行 解,它表示第1条路段,第3条路段,第6条路段 要修建,其他备选路段不修建.则ll对应的粒子 X一(1,0,1,0,0,1). 1)初始化粒子群. ?每个粒子位置向量x的每一维坐标X"随 机取[0,1]之间的整数. ?每个速度向量V的每一维坐标d随机取 一 if,(1--X,)之间的整数. ?将每个xl转换成H,对每个U用求解非线 性规划的Frank—wolfe算法求下层问题的最优 解. ?将上层目标函数作为评价函数评价所有粒 子. ?将初始评价值作为个体历史最优解Pl,并 寻找群体内最优解P. 2)重复以下步骤,直到满足终止条件. (15),(16)计算, ?对每个粒子,按迭代式 X.其中V,xl向下取整,当Vi,超过其范围 时按边界取值. ?每个x转换成U,对每个U用Frank— wolfe算法求下层问题的最优解. ?将上层目标函数作为评价函数评价所有粒子. ?若某个粒子的当前评价值优于其历史最优 评价值,则记当前为该历史最优评价值,同时记忆 当前位置为粒子历史最优位置Pi. ?寻找当前群体内最优解P. 5算例分析 如图2所示的简单路网图,虚线表示待选添 加的路段,均为双向行驶路段,共有4条. 图2简单路网图 Fig.2Simplenetworkfigwre 模型所需参数数据见表1,其中A一{a,a., … ,alo),A2一{口口12'aa14},B一1000万元. 表1基本参数数据表 Tab.1Thebasicparametersofthedatatable 路段 7891oIIi21314 35424342 5045404550505540 57646564 400300200500 根据以上数据和对实际中某些参数的估算和 预测,通过粒子群算法得到如下结果,见表2,应 该修建路段l1和路段14,可使得该城市路网可 达性达到最大. 裹2不同候选组合中路网可达性数值比较 Tab.2Numericalcomparisonfordifferentcombinations ofcandidatesforRoadNetworkAccessibility ', 路网可达性行驶时间达到最优解计算时间 A/min迭代次数/min 6结束语 改善路网可达性对城市交通发挥其功能有着 重要的作用,从上面简单的实例中可见,合理的修 建路段确实能够提高路网的可达性.以下几个问 题还需要进一步研究. 1)实际中,由于预算投资的限制,仅能对已 有路段改造以增加其通行能力,即路段通过能力 假想是连续增加的,基于路网可达性的城市交通 连续网络设计问题有待进一步研究.如果投资允 许的情况下,同时进行新建路和对已有的路段进 行改造,如何来设计新的模型. 2)确定添加哪些新的路段和对哪些已有路 段进行改造以提高其通行能力,如何定量的考虑 路段规模,即从车道的数量来改造和修建. 一一 I C 234861267 111552311 ?????????456376546 589568434 42O861572 333233334 555223629 264342232 i;i ^^^^^^^^^ 1O1111O1O ,,,,,,,,, 11O11O1OO ,,,,,,,,, l11O1OOO0 ,?,?,,,,,,, l111011O0 lll 基于路网可达性的城市交通离散网络设计模型及算法——克涛67 3)节点的重要度反映路网各节点功能强弱 的特征量或特征参数,是描述节点在交通网络中 所处地位,重要程度相对大小的一个量化指标,文 章忽略了. 4)依据城市交通分区理论,把考虑的城市区 域分成若干子区,如果子区地域面积很大的时候, 很容易忽略子区内的交通出行,从而度量节点的 可达性容易出现较大误差. 5)下层规划模型中假定OD需求量是固定 的,在一个城市网络中,如果城市规模不够大,可 以这样认为,但是实际中,规模大的城市进行城市 交通网络设计更加有必要,所以OD需求量固定 与实际差距大,使用弹性需求UE模型和SUE模 型能更切合实际. 参考文献 [1]高自友,张好智,孙会君.城市交通网络设计问题中 的双层规划模型,方法及应用[J].交通运输系统工 程与信息,2004,4(1):35—44. 宋一凡,高自友.基于弹性需求的连续平衡网络设 计问题的双层规划模型及求解算法口].公路交通科 技,1999,16(4):53—56. 赵彤,高自友.城市交通网络设计问题中的双层 规划模型[J].土木工程,2003,36(1):6-10. 许良,高自友.基于路段能力可靠性的城市交通 网络设计问题[J].中国公路,2006,19(2):86— 9O. 许良,高自友.基于连通可靠性的城市道路交通 离散网络设计问题[J].燕山大学,2007,31(2): 159-163. 许良,高自友.基于出行时间可靠性的城市交通 网络设计[J].系统仿真,2008,20(2):494—498. 盖春英,裴玉龙.公路网络可达性研究[J].公路交通 科技.2006,23(6):104—107. 陈洁,陆峰,程昌秀.可达性度量方法及应用研 究进展评述[J].地理科学进展,2007,26(5):100— 11O. ModelandAlgorithmforUrbanTransp0rtati0nDiscrete NetworkDesignBasedonRoadNetworkAccessibility DENGKetao (BasisTeachingandResearchDepartment,RailwayandPolice RailwayPoliceCollege,Zhengzhou450053,China) Abstract:Basedonthedivisiontheoryofurbantransportationnetwork,thispaperdividedurb annetworkintosub— districtasanode,andconsideredtheaccessibilityofallthenodestomeasuretheaccessibilityo ftheentireroadnetwork. Amodelforurbantransportationdiscretenetworkwasdesignedtomaximizetheroadnetwor kaccessibility.Moreover,a particleswarmoptimizationalgorithmwasproposed.Asimplenumericalexamplewasprese nted.Thenumericalresults showthatreasonableaddedsegmentofroadwillmaximizetheurbanroadnetworkaccessibility. Keywords:accessibility;urbantransportation;discretenetworkdesign;particleswarmoptimizationalgorithm ]1J1J1J1J1?一]