西北大学学报(自然科学版) 2010年8月,第加卷第4期,Aug.,2010,Vo1.40,No.4 Journal of Northwest University(Natural Science Edition) 基于ArcGIS的城市公交网络规划方法 姜岩飞 ,郗恩崇 ,虎(1.长安大学经济与管理学院,陕西西安啸 710064;2.招商局亚太有限公司,广东深圳518067) 摘要:目的构筑基于ArcGIS的公交网络规划方法。方法 以ArcGIS为基础研究平台,结合神经 网络算法、燃烧原理算法等用于开发“基于ArcGIS的城市公交网络规划系统”,用以优化现有的公 交网络。结果优化后的公交网络系统能够较好地满足人民出行的运输需求,让城市公交成为一 个城市的名片。结论基于ArcGIS的城市公交网络规划系统是目前较好的规划理论与方法。 关键词:ArcGIS;公交网络;网络规划;燃烧算法;居民出行 文献标识码:A 文章编号:1000-274X(2010)04-0617-05 中图分类号:U116.2 A study on the urban bus netwok planning method based on the ArcGIS JIANG Yan—fei I, .XI En.chong ,HU Xiao (1.School of Economics and Management,Chang n Uniaversiy,tXi n a710064,China; 2.China Merchants Holings(Pacidifc)Limited,Shenzhen 518067,China) Abstract:Aim To construct the planning method of public transportation network based on ArcGIS.Methods From the basic research platform of ArcGIS,to develop the planning system of urban public transportation network based on ArcGIS with the combination of neural network algorithm and combustion principle algorithm SO that the present public transportation network Can be modiifed.Results The modiifed public transportation network Can sat- isfy he demand oft residents travel better to make the public transport the nanle card of a city.Conclusion The plnniang system of urban public transportation network based on ArcGIS is tne better heory and tmethod presently. Key words:ArcGIS;public transportation network;network planning;combustion principle algorihm;resitdents travel 城市公共交通网络,主要是指城市陆上、水上和 空中各种运输方式的运输线路和场站设施所组成的 系统,本文的研究对象是城市陆上的运输线路和场 站设施所组成的系统。随着社会城市化进程加速, 城市交通问题日益严重…。为了响应交通运输部 高低最重要的“天平”,一个完整的公交网络体系包 括网络密度、场站服务情况、线路数量等多个因素, 为了给人民群众提供最好的公交运输服务,需要着 重关注城市公共交通网密度、城市公共交通场站用 地情况以及站点服务深度、城市公共交通线路条数 “三个服务”要求中服务人民群众安全便捷出行的 号召,更快更好的发展城市公共交通,为人民群众的 出行提供优质的运输服务,城市公共交通受到了多 方面的关注。近年来,许多学者提倡公交优先发展 与平均线路长度、城市居民非乘车时间及乘客转换 车等方面的因素,才能做好城市公交的规划 J。 的理念,而如何评价公交网络的性能,如何进一步改 善公交服务体系等问题都需要公交网络路径寻优技 术的支持。 合理的公交网络是评价一个城市公交服务水平 收稿日期:2009-03-11 1.1构造矢量化地图 扫描地图矢量化是获取数字化矢量地图数据的 有效手段。传统的矢量化过程采用交互式方式完 基金项目:高等学校博士学科点专项科研基金资助项目(200807100001) 作者简介:姜岩飞,男,山东济南人,长安大学博士生,从事交通运输经济与管理研究。 ・・——618-——— 西北大学学报(自然科学版) 第40卷 成,这种方法相对于早期的手扶跟踪数字化方法而 且,对线状地图要素矢量化,必须首先提取线状地图 言,不管是在效率,还是在精度方面,都有明显的提 要素的中心线像素,然后利用相关算法将像素序列 高。本文重点在以下几点上作了改进: 转换成矢量表达形式。细化处理是获取线状地图要 1)图要素的细化处理要实现地图要素的分 素中心线的主要手段,因此,细化处理在扫描地图自 离与识别,关键就是要找出地图要素的轮廓并提取 动矢量化过程中占有非常重要的地位 J。 出对应要素的特征信息。对于线状(或条形面状) 2)用MAPGIS制作地图主要过程如图1。 地图要素,其中心线能有效表征地图要素轮廓。而 图1制作矢量化地图流程图 Fig.1 The flow chart ofmaking vector map 1.2算法设计 其中,过滤函数是将运输需求量(预测值),人 该模型根据输人信号,以选取函数计算输出,判 口总数和GDP指标3者总和考虑的表达式: 别输出层输出是否满足要求,成立则输出,否则,修 设n为预测年限;|i}为统计年度客运量; 为道 正权值,继续处理。 路客运弹性系数;r 为统计年度客运增长率;r2为统 计算函数选用|s型函数 计年度国民经济增长率;r 为预测期间内客运增长 f(x)= 。 率; 为预测期间内国民经济增长率;Pt为预测期人 收敛函数选用平方型误差函数 口数;Po为基期人口数; 为0一t时期内人口出生 数;D为该时期死亡人数;,为该时期迁入人数;E为 ∑(该时期迁出人数;C为居民消费(即个人消费);G为 =生L_ ‰一一 ) 。。 政府消费(相当于财政的经常性支出);(c+G))就 厶 收敛阈值 待定 是总消费; 为总投资; 为出口; 为进口;(X— 1.3选取规划指标 M)就是出口净额。 1.3.1点分类本文将需要乘坐城市公交出行的人 则点的综合指标为 聚集的点称为运输需求点,那么,可以将一个城市需 Y=qlk譬+g2[P0+日一D+,一E]+q3[(C+ 要出行的人划分为若干个点,这若干个点的重要度 G+,g+ — )]。 不同,最重要的点就是出行人数最多的点。运输需 说明:①0<q <1(i=1,2,3)为适当参数,按 求是点到点位移的需求,满足运输需求就意味着要 该项的重要程度取值;②对于人口预测和GDP预 将分布在不同空间的运输需求所在点连接起来,这 测的方法和手段有很多,有多种表达式可选择,这里 是建立城市公交网络的基本要求。最短连通路径对 仅选用了其中一种。 于节约投资、减少土地占用、降低运输消耗有密切的 1.3.2 选取规划指标本文规划的总体思路是满 联系。因此本文选择最短连通路径作为切入点来研 足人民群众的出行要求,以对国民经济及社会发展 究城市公交网络优化布局。由于待考虑的运输需求 贡献最大化为构建城市公交网络体系的根本目标, 点的数目众多,因此要尽可能地采用高效的方法将 以把握国民经济及社会发展形成的人群出行的运输 其分类。本文考虑采用过滤函数与神经网络双重筛 需求为切入点,在经济均衡的原则上以最大限度满 选的方法对所有点进行分类。具体做法为:设定过 足运输需求为直接目标,综合考虑网络投资、占用土 滤函数,将所有点粗分为两类,挑出其中的第一类大 地机会成本、运输费用、网络运营效率4个基本因 点,利用神经网络方法把剩余的点分为两类,即第2 素,基于平面来构建满足城市交通合理分工要求的 和3类点。[ 。] 城市公交网络规划的理论与方法体系。 第4期 姜岩飞等:基于ArcGIS的城市公交网络规划方法 ・——619—-—— 1.4构建模型 对于前3个因素:网络投资、占用土地机会成 点的最少换乘次数,前一个站点D(记录路径的经过 本、运输费用,均可转化为货币量进行进算,第4个 因素:网络运营效率无法用货币比较。设:网络投资 的总里程为 (L>0),共需投资或改造n种等级的 城市道路,站点和线路占用m种土地,每种道路的长 站点)以及最短路径长度(实际上是“最大人口密 度”); ②读入线路起始点 的所有邻接点,分别人队 列Q,将这些顶点对应的linechange值设为l,pres— top设为£,dist设为两点之间的“权值”; 度为aiL(0< <1),且∑口 =1,每种道路的单 ③若dist[j]不等于零,算法结束; 位长度使用费用为 ,平均单位运价为p ,运量为Y , 路基宽度为d ,每种土地的单价为t (.『=l,2,…, m),每种道路占用各类土地的面积总和为 ∑6 (0<b <l,且∑∑)6 =1,若日为道路 平均年周转量, , 为适当系数, 为网络运营效率, >0位某一定值,Ⅳ为年限,则总费用可以表为 c= ∑ +ot ̄y.,p +∑ d ], 或 C:主 l 1 ‘’ +[ ln(日)卢] +主妻ti=I』。1 jbq‘’Ⅳd  ̄L。 其中 可根据经验值或期望值设定,Y 可为实 际测量值或预估值,根据不同的分类标准P 的取值 很灵活,则本研究构造的优化模型为 Min C,s.t.B≥ 。 按照经验,路网使用效率一般在70%~80%, 可据此设定占的取值。 以上公式可以求得每种城市道路需要改(建) 造成公交线路的长度l-9]。 1.5算法流程 在将所有点和线(即城市和道路)分类之后,对 第三类点的处理方法如下: 保持整体是联通的,但不要求第三类点之间点 点连通,我们就近处理第三类点的连通问题。具体 步骤如下:设有P个大点, 1)以点 为起点做阿基米德螺线(即等速螺 线)搜索运动,EPp= p,OL为极径, 为极角。当遇到 第一个大时停止,此时以口为半径画圆,检查圆内有 多少大点,若存在大于1个的大点,则根据具体的地 理情况、出行方向等选出最合理的连接大点,将 放 入相应的集合中 ( =1,…,P+Q)中。重复此过 程,直到所有的第三类点均放人相应的集合中。 2)设计燃烧算法,进行每一个圆内的最短路径 连通。 ①创建3个数组linechange[vnum],prestop [vnum],和dist[vnum]分别记录从 到其他各顶 ④当队列Q非空时,对头结点出队,用指针q 记录该结点的第一个邻接点,若linechange[q一> adjvcx]为0,说明此邻接点未被访问,修改数组li. nechange[q一>adjvex],prestop[q一>adjvex],和 dist[qm>adjvex]的值,若linechange[qm>adjvex] 值非空,说明此邻接点已经访问过,则比较ga.adjlist [q一>adjvex].weight+dist[pre一>vextex])和dist [q一>adjvex])值,取较小值。同时修改相应的li— nechange和prestop值; ⑤继续其他邻接点的操作,如图2所示。 图2邻近点操作图 Fig.2 Operation charts of neighborhood points 利用“燃烧”算法,求出顶点1到顶点6的最短 路径过程。 3)重复以上过程,直到所有小点都处理完。如 图3所示 加_1 。 1.6检验 1.6.1 图的连通性证明 设城市公交网络中共有 共有n个点,将其编号为I,l, ,…, ,令S={ , ,…, }。 1)任取一个点 ∈S,令S。={ }; 2)对于任意的 ∈So,若 与 相邻,且 隹 s,令Is0 s0 u{ }; 3)重复2),直到&中不能添加点为止; ・-——620--—— 西北大学学报(自然科学版) 第40卷 若So=S则表明公交网络是连通的。 若s0 c.s则表明公交网络是不连通的。 若不连通,则取 E s\So,令St={ },重复 上面的1)~3),可得到集合S。,若S =Js\S。,则 IS。,Is。是公交网络的两个连通分支。 若S c Is\S。,则取 ∈s、(s。U S。),令S:= { },重复1)~3),得|s ,即为另一连通分支。 图3最短网络路径图 Fig.3 The shortest network path 重复上述过程,直到所有的连通分支.s ,s:, 5 都找出来,然后在任意两个分支间做直线,将 两个连通分支连通,重复该过程,直到所有的连通分 …在一起,其起始位置包在结点结构中D(C)表:设立 ,0表和C表。0表用来存放将要处理的结点。C表用 来存放处理过的结点,这两个表均是双向链表。 遗传/蚁群表:存放遗传算法的最小迭代次数 n 和最大迭代次数n ,设置的最小进化率m和求蚁 支都连通。此时,整个公交网络即为连通的。 1.6.2新方法的可行性和高效性检验为了对新 方法的可行性和高效性进行检验,本文选用另2种 方案作比选,第一种是和现有公交网络与规划方案 直接对比,另一种是和理论上的最短路径——最小 生成树作对比,我们在图上任意选取2个点,采用基 于GIS的改进A+算法方法寻求该2点之间的最短 路径。 群初始信息素的权值k。 利用遗传算法和蚁群算法寻找估价函数,先将 公交网络中每个结点关联一个指引搜索方向的估价 函数,估计从起点途径此结点到达终点所需的最小 通行代价,搜索过程就是不断去拓展估价函数值最 小的那个结点,直到达到终点。 估价函数由2部分组成 )=g(n)+h(n)。 其中 n)为结点n估价函数;g(,1)为从初始 该方法结合了蚁群、遗传算法,有效提高了传统 A+算法的计算效率。 1)建立网络分析和算法的数据结构 结点:每一个结点都有一个结点号作为标识。其 中经度与纬度标志其位置信息,父结点表示其在最 优路径中的上一结点号,子结点数与该点相连的结 点数目,在P中位置表示在P表记录所有经过该结 结点到结点n的实际代价; (n)是从结点n到目标 节点最佳路径的估计代价即为启发函数。启发函数 的值若过小,则起不到相应的作用,导致搜索范围扩 大,如果其值过大,则不保证找到最优解。 2)算法流程 开始时将起点放人O表,然后处理该表中的结 点,直到0表为空。D表中的结点是按估价值 的升 序排列的。考察0表中的第一个结点 值最小),对 其所有子结点做出判断,若不在D表中,则加入D 表,如已在0表中,则利用遗传和蚁群算法经过重新 点的弧权起始记录位置,g, 标志搜索结点的优先 级。 结点表:路网结点的集合构成结点表,结点在表 中的位置与结点好对应。 路权表:路权表记录路网中所有弧的权。路权 表大体上按节点号排列,经过一结点的所有弧记录 第4期 姜岩飞等:基于ArcGIS的城市公交网络规划方法 计算g值,重排0表,找出最优估价值。当所有子结 点处理完毕后,将该结点插入C表中,并从D表中删 除。当0表中第一个结点为终点时,找出最优路径, 如D表为空,则表示没找到最优路径。 通过以上5部分得到的公交网络规划,从理论 源市公交五年规划”课题中得到应用,取得了较好 的效果。在一般情况下公交路网的规划要求在任意 两个站点之间的转车的次数不能超过2次。在笔者 所设计的公交最短路算法中设定了最多2次转车, 此方法也可用于验证公交路网的通达性。对乘客的 乘车心理统一按照一种思路考虑,这种方法可能并 不能使所有的用户满意,因此进一步研究即要设计 出合乎不同用户乘车心理的路线选择标准;随着先 进的交通信息技术的进入,在乘客的路径选择标准 上说是比较完善的,对实际城市公交网络建设具有 指导意义。 2基于ArcGIS的公交网络规划平台 的实现 在上述步骤的运行下,本文作者将制作好的电 子矢量化地图、进行公交网络规划所需要的数据 (如人口、人均出行次数、出行频率等)、算法等所需 要的元素均放入到已构建好的GIS平台中,通过神 经网络组件对数据进行筛选、分类,最终计算出合理 的公交网络以及每条线路的缓冲分析,如图4所示。 图4规划线路的缓冲区分析 Fig.4 Analysis of buffer in routing planning 3结语 利用GIS的特性设计了符合公交查询的数据结 构,考虑到乘客出行的心理特征,设计了能够在一 定程度上满足公交乘客出行选择路线需要的路线选 择标准,然后给出了一个双向搜索最短路算法,该 算法具有比较好的实时陛与快速性。本系统在“济 以及算法中要融人时间因素,设计考虑最短出行时 间的公交最优路线,以及起点与终点间多条优化路 线的算法是将来的一个研究方向。 参考文献: [1] 孙启鹏,吴群琪.运输需求生成机理及其规律[J].长 安大学学报:社会科学版,2008,10(2):7—12. [2]吴群琪,袁长伟.公路网规划研究进展与发展趋势 [J].中国公路学报,2005,19(2):91-96. [3]孙启鹏,吴群琪.基于路段通过能力的运输系统成本 模型[J].长安大学学报:自然科学版,2007,27(5): 94-97. [4] 孙金香,许道云.基于蚁群算法的邮政运输规划研究 [J].计算机应用与软件,2009,26(1):115—117. [5]胡建国,付健.基于四阶段法的交通运输规划中运输 量预测方法[J].湖南工程学院学报,2005,15(3): 1401. [6]王庆云.交通运输规划模型的基本原理及应用[J].交 通运输系统工程与信息,2002,2(1):20-24. [7] 杨树荣,冯芳霞,郑加柱.基于GIS的道路运输规划的 研究[J].森林工程,2002,18(6):46_47. [8]王发艳.地理信息系统与地图制图[J].资源环境与工 程,2008,22(2):239-422. [9]傅白白,高自友.平衡规划问题的嫡函数方法及其在 混合交通流中的应用[J].运筹学学报,2007,11(1): 49-54. [10]阮宁,孙小玲.带组约束可靠性网络最优化问题的精 确算法[J].运筹学学报,2007,11(4):33—40. [11]马昌喜,马永红,广晓平.甘肃省高速公路网合理规模 预测[J].兰州交通大学学报,2008,27(3):78-80. [12]匡烨,何晓鸣.地方公路网规划的最佳经济规模探讨 [J].武汉工业学院学报,2007,26(2):59-63. (编辑曹大刚)