公交最短路径算法与网络通达性指标的计算

第 26卷第 6期 1997年 l2月 同 济 太 学 学 摄 JOURNAL OF TONGJI UNIVERSITY V01．25 N0．6 Dec．1997 公交最短路径算法与网络通达性指标的计算 1， f一6 李 彬 杨 起 杨佩昆 (同济大学道路与交通工程系 上海．2~oo92) 摘要 砰克了也、变单一票价 制度 关于办公室下班关闭电源制度矿山事故隐患举报和奖励制度制度下载人事管理制度doc盘点制度下载 对柬喜路践选择的影响 格出了术两变通小匠问公变毒短抒程时『l1和 套变曩艋砖拄的算法．并在公变客流姑蝽点OD分布矩阵的基础上，叶套变网，鼬 遮性进行了深八的研 克．可用于全空罔肄优化评价与才辜秩择． 关键词 坌奎塑竺；坌奎垦堕堕堡i逗垄生 中图法分类号 U 491 峨{ -} 文献CIJ中提出了城市交通网络总体通达性指标的概念，其公式如下： T==t ‘埘 ／∑肘 (1) 式中：T表示城市交通网络通达性指标；M 表示从交通小区i到J的由家出行人数； 表 示从交通小区 到j的最短路径所需时间． T的实际意义就是城市居民出行最短平均时间．它反映了整个城市居民出行的方便程 度，也反映了城市道路网的充分性、路网布局的合理性、管理水平等多方面的特性．但是，它 没有反映城市规模对通达性的影响．为了在公交网络规划中进行公交网络的优化与评价，我 们对式(1)作了修改，因为在规划时，城市面积在扩大，相应的居民平均公交行程时间会变大， 无法与原来的进行比较，因此，本文定义的城市公交网络的通达性指标如下： T=辛 ∑ u ／z ， (2) √A ‘ 式中：A为建成区面积 为城市形态修正系数；‘“为从交通小区 i到 的公交最短行程时 间；朋 表示从交通小区 i到J的公交乘客始终点 OD的量． 亍越小，说明公交网络越好，居民乘公交出行越方便．我们考虑城市形态的影响 主要是 为了对不同城市的公交网络通达性进行比较． 对于现有公交网络的通达性指标，可以通过居民出行调查得到，设调查得到的公交乘客 平均行程时间为 T，平均换乘次数为 则有 一 T= ；(T+ ) (3) √A 式中： 表示票价转换为花费的时间． 但是，对于规划中的公交网络，不能通过调查而得到．未来的公交乘客 OD矩阵可以通 过预测得到．为了计算公交网络通达性指标 ，首先要计算规划公交网络中交通小区间的最 本文收捌日期：3．996年6月19日 第一作者：男，l989年生，博士生 维普资讯 http://www.cqvip.com 652 同 济 大 学 学 报 第26卷 短公交路径和最短公交行程时间． 公交路径生成技术是公交网络客流分配、公交网络优化与评价的关键技术之一．文献[23 和文献[3]提出了求两交通小区间公交最短路径的算法，但是，目前在我国城市中普通推广 公交单一票价制度，无疑会对乘客路线选择产生重大的影响，从而文献[2]和文献[3]所得到 的公交最短路径和实际有很大的差距．本文企图考虑这一政策因素的重大影响 并用图论和 矩阵论的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ，改进了文献[23和文献[3]中的公交最短路径的算法，提高了运算速度．在此基 础上，计算了公交网络通达性指标，可用于公交网络优化评价与抉择． 笔者曾把本文的方法用于广西桂林市公交规划的方案抉择中 得到了比较满意的结果． 1 公交网络的基本概念 城市中有公共电汽车行驶的道路全体为道路网络，道路网络中任何相邻公交站点间的 道路称为路段，构造简单图G，结点集 ⅥG)是所有公交站点全体构成的集合(若一个站点为 多路公交线路所共有，则只算一个结点)．边集E(G)是所有路段的集合， G)的基数记为 ． 即 l G)I= ． 本文将考虑结点 G)到任何其它结点阃的公交最短路径问题，将所生成的最短路径 与合适的小区形心连接，可获得小区间的公交最短路径． 定义1 设 ⅥG)，称为基结点，称由j出发经 次转乘可以到达的结点为 的第 k层 点， 的第 k层点的全体记为 {．特殊地，若 J到J有直达公交线路，则称 为 的第 0层 点(或直达点)． 一 般情况下．要求公交网络中任意两结点之间在换乘次数不超过 2次的情况下有公交 路径．即，最大公交换乘次数 矗～=2． 由定义 1知 W{f1聊 (0≤h，m≤ ． )不一定为空集． 定义 2 称结点 J到结点 研 经 次换乘的时间最短的公交路径为 j到 的 第 阶 公交最短路径 ，其时间称为j封J的 第 阶公交最短时间 ，记为 』)． 记 J到 的最短公交行程时间为 (f，j)，则有 f )=min{ ( )，f’( )，f )1 (4) 两结点 x，Y问的公交路径是 G中的一条路，记为 P =fX= ，Z ． -，f| h，⋯． ，f．． +，一 } (5) 式中：i。，⋯，f^是换乘点；f】，⋯，f^是车线； 称为 “，的前点， ，称为 0的后点． 定义 3 公交网络 G的邻接矩阵P定义为 阶方阵，其中： = { 结 被一条车线连接 (6) 引理 1 结点 f经 k次换乘可以到达结点 的充分必要条件是 P ，>0． 定义4 公交网络初始时间矩阵 r定义为n阶方阵如下： r 0 = {min( )d．』当浮_J且i到j有m条车线经过 (7) L 其它 式中：m表示车线条数，m>1； 为线路 h的车辆全线行程时间： 为线路 h的全线距离； ， 为 f到』的实际距离． 维普资讯 http://www.cqvip.com 第6期 李 椎荨：公交最短路径算法与网络通达性指标的计算 653 如果考虑的公交线路均是双向的，则 T是对称矩阵． 定义 5 公交网络换乘步行时间矩阵 H为 n阶方阵，定义如下： f 0 i=j h 一 d ／u 当 i≠J且 d <月 (8) 【{30 其它 式中：d 为 ￡到J的步行距离 为允许的换乘最大步行距离； 为平均步行速度．可取站点 覆盖半径作为换乘步行距离的上界 月． 2 公交站点闻最短公交行程时间的计算 公交路径是从一个区域出发经过公交网络在一定转车次数内到达另一区域的轨迹 首 先必须由出发点经步行(或其它交通工具，本文仅考虑步行的情况)到达公交车站，而下车以 后，还得步行一段时间才能到达目的地，把这两者之和记为 首先计算公交站点间最短公交行程时间．两公交站点间的公交行程时间由下列几部分组 成：① 等车时间(在车站等车的时间)；② 转车时间(包括转车步行时间和转车等车时 间)：③ 车内时间．此外，还应该考虑公交单一票价制度(不包括专线公交车及中巴)对乘客路 线选择的影响，以前实行的计程票价制度是根据乘客乘行的站数而定票价；而单一票价制度 是无论乘多少站均是统一的票价．在计算公交最短路径时必须考虑换乘票价的影响，把它转 化为花费的时间，记为 ．采用如下公式计算： 票价X480×法定年工作天数 —— 瓢 _ 例如，居民人均年收人为 6 000元，则 近似为 10mln． 设总的车线条数为 1，各车线的发车间隔时间分别为￡ t ⋯， (rain)，定义集合 A。(E一1，2，⋯，D，A 是由车线 经过的公交站点所构成的集合，则有 ￡ ( ， =田in{ff^+ d ／ ) (10) tJE^‘ 任取两结点 i,i，记集合 风 为满足条件： <∞， ，<∞，艇 W?的站点 I"n所构成的 集合，则有 ( ，J)一 ra inB ( ( ，凫)十月 +￡。Cm-J)}+ (11) (E，』)= ra in B { (E，凫)+月 + (m- }+ ( 2) 由式(4)即可求得任两公交站点问的最短公交行程时间． 3 交通小区间公交最短路径和最短公交行程时间的算法 3．1 公交站点间公交最短路径的算法 由前节的结论，可以很方便地求出公交站点间的公交最短路径，算法如下： (1)若 Po≠0，则 i到J有公交线路相连，若 k使式(10)成立，将 f到J的第 0阶公交最短 路径记为PJ 则PJn=fiIh,j1． (2)若m，k使式(11)成立，将i到J的第 1阶公交最短路径记为P 则An=f PJ 1．U {R ．}． 维普资讯 http://www.cqvip.com 同 济 大 学 学 报 第26卷 (3)若 m， 使式(12)成立，将 i到j的第 2阶公交最短路径记为P月I_，则 PH：．= fP UP }． (4)比较三条。最短路径 的长度就可以求出任两公交站点间的公交最短路径． 3．2 交通小区间公交最短路径和最短公交行程时间的算法 设到任一交通小区 的形心的距离小于站点覆盖半径 的公交站点构成的集合为 B．． 则交通小区 ， 间的公交最短行程时间为 J，= rain f + + ) (13> 日-- B 式中：t 为交通小区 的形心到站点 r的步行时间：f，．为站点 r到 8的公交最短行程 时间； 为站点 s到交通小区J形心的步行时间．使上式成立的站点 r，8间的公交最短路径 加上两端的步行路径就是交通小区 i到j的公交最短路径． 本文的算法具有概念简单、考虑的因素较为全面的特点．用 C语言缩写了计算机程序， 使计算速度比文献r2]的算法大为提高． 4 应 用 在作广西桂林市公共交通规划的时候 ，为了进行方案的抉择，在线网密度．重复系 数、3oom覆盖率等指标达到规划要求的前提条件下，用公交阿络通达性指标进行方案抉择． 1995年，桂林市建成区面积为 46．5km ，居民人均年收人为 3 900元，桂林市远景规 ~rJ(2020年)建成区面积为 96．0kmz． 于 1996年 1月底对桂林市的公共交通作了抽样调查．得到居民公交平均出行时间 为 29rain．平均换乘次数为0．2次．公交车平均行程车速为 14．5min·km～． 由式(9)得 =15min．暂不考虑城市形态的影响，故令 =1．由式(2)得现有的公交网络 的通达性指标为 4．6rain·kin-。． 对于规戈0的三十方案，假设未来公交票价会随居民人均收人同步提高，故令 不变，假 设在公交平均行程车速不变的情况下，用公交网络通达性指标进行方案抉择．计算机输出的 结果见附表． 附表 用公空阿络通达性指标进行方案抉择的计算机输出结果 由上表可见，方案 3是最好的 5 结 语 本文改进了公交最短路径的算法，在此基础上，考虑了城市形态和城市面积对公交冈络 通达性的影响，具有很强的实用性．但是，怎样确定城市形态修正系数 ，有待进一步研究． 维普资讯 http://www.cqvip.com 第6期 李 彬等：公交最短培径算法与网络通达性指标的计算 655 参考文献 l 梧涛．黄创云．城市交通同结可达性：反思和更新．见-孙云军主编 城市建设与发展研究论文集．上海：同井大学 出版社 1992 2 王祖祥，商成修，周安宁公交最短路算法与公交路径集生成技术系统工程．1993(4)：37~43 3 吴棘豪．赵永昌．王春样．公共交通阿络路径算法．系统工程，1987(1)：53~59 Algorithm to Obtain the Shortest Bus Route and the Calculation of Bus Netw ork S AccessjbjIjty LiBin Chao Peikun (Department of Road and Traffic Engineering．Tongii University．Shanghai，2O0O92) Abstract In this paper，we study how the public transportation single—price rule affects passengers to choose bus routes，and suggest an algorithm to find the shortest bus route and the shorte~ travel time between two zones．Based on passenger 0D distribution matrix，we also study the bus network’8 accessibility， which can be used to evaluate bus network and to pro vide alternatiyes． Keyw ords BUS network；Shortest bus roure；Accessibility ；通 讯 第七届土木与营造工程计算国际会议简介 ． p ⋯ 本届会议于 1997年 8月 19~21日在韩国首都汉城举行 来自36个国家的 200多名学 者参加了本届会议 ．土木与营造工程计算国际会议是由营造工程计算国际学会主办，每三年 举办一次 ．本届会议由韩国高等科技学院主办．会议的主题是计算机方法及其实际应用 内 容包括：建筑和 CAD、城市规划、专家系统、模糊和神经网络、CAD／CAE、GIS、土力学、流 体力学、地质力学、结构动力学、数值模型化、空气动力学，随机分析 结构工程、优化、计算力 学、风工程，安全度与可靠度、地震工程、环境工程、海洋工程、材料和构成规律、水工程、交通 与城市规划、项目管理、生产过程模型化、渗漏、遥感、自动化设计、软件发展、桥梁工程、基础 工程、复合材料、铜结构、混凝土和钢筋混凝土结构、信息技术、波的传播／SSI、监视和再 现．会议共收到论文390篇，其中包括4篇特邀报告，17篇特邀论文． (gf卫星) 维普资讯 http://www.cqvip.com