（交通运输规划与管理专业论文）基于蚁群算法的公交出行方案研究.pdf

中文摘要 随着交通拥挤问题的日益严重，大力发展公共交通已经成为解决城市交通问 题的主要措施之一。但是，面对迅速发展和不断更新的城市公共交通网络，如何 通过一种快捷、方便、直观的方式为乘客找到一种合理的出行方案，并为乘客提 供尽可能多的出行信息，是城市公共交通乘客信息服务系统建设的重要课题。 本文在总结分析国内外相关研究成果的基础上，围绕公交出行方案及相关算 法进行了如下研究： 首先，对城市公共交通系统构成进行了研究。分析了常规公交、轨道交通、 快速公交三种公共交通方式的特点并进行比较。在此基础上，分析了城市综合公 共交通网络的数学模型和拓扑结构。 其次，对公交出行广义费用进行了研究。分析了影响乘客出行方式选择的各 种因素，包括：时问因素、经济因素、换乘因素、舒适性因素。在此基础上提出 了公交出行广义费用模型和公交出行决策模型。 第三，对路径选择算法进行了研究。在研究已有算法的基础上，分析了蚁群 算法的基本原理，并通过实验的方式研究该算法初始化和相关参数的设置。之后 提出了利用蚁群算法搜索公交出行方案的方法，并结合具体的算例进行分析。 最后，结合以上研究设计城市公交出行查询系统，并实际生成给定站点间的 出行方案，验证了研究的可行性。 关键词：公共交通：广义费用；出行方案；蚁群算法 分类号： u 4 9 1 ；4 9 1 1 + 2 ；u 4 9 1 1 + 3 ；u 4 9 1 1 + 7 】 1 1 1 a b s t r a c t n o w a d a y s ，t h ed e v e l o p m e n to fp u b l i ct r a n s i th a sb e c o m eo n eo ft h em o s t i m p o r t a n tm e t h o d st os o l v et h et r a f f i cp r o b l e m s ，a st h es i t u a t i o no fc o n g e s t i o ni sg e t t i n g w o r s ed a yb yd a y h o w e v e r , i ti sv e r yi m p o r t a n tf o r t h ep a s s e n g e r st of i n dar e a s o n a b l e t r i pp l a ni nt h eg r o w i n gp u b l i ct r a n s i tn e t a n di ti sa l s oa ni m p o r t a n tp a r to fp a s s e n g e r i n f o r m a t i o ns y s t e m o nt h eb a s i so f r e s e a r c ha c h i e v e m e n t s ，t h er e s e a r c h e sa b o u tt h ep u b l i ct r i pp l a na n d r e l a t e da l g o r i t h m sa r ea sf o l l o w s f i r s t l y , t h es t r u c t u r eo fu r b a nt r a n s i ti ss t u d i e d t h ec h a r a c t e r i s t i c so fc o n v e n t i o n a l p u b l i ct r a n s i t ，r a i l w a yt r a n s i ta n db r tt r a n s i ta r ea n a l y z e da n dc o m p a r e d t h e n ，t h e m a t h e m a t i c a lm o d e la n dt o p o l o g i c a ls t r u c t u r eo fu r b a nt r a n s i tn e t w o r ka r es t u d i e d s e c o n d l y , t h eg e n e r a l i z e dc o s to fp u b l i ct r a n s i ti ss t u d i e d b a s e do nt h ei n f l u e n c i n g f a c t o r si n c l u d i n gt i m e ，c o s t ，t r a n s f e ra n dc o m f o r t ，t h eg e n e r a l i z e dc o s tm o d e la n dt h e p a t ho p t i m i z a t i o nm o d e la r ep r o p o s e d t h i r d l y , t h ep a t hc h o o s i n ga l g o r i t h mi ss t u d i e d b a s e do nt h ea l g o r i t h m st h a te x i s t ， t h ep r i n c i p l eo fa n tc o l o n ya l g o r i t h mi si n t r o d u c e d ，a n dt h e nt h es e t t i n go fi n i t i a l i z a t i o n a n dp a r a m e t e r sa r ea n a l y z e d a f t e rt h a t ，t h em e t h o dt os e a r c ht h et r a n s i tt r i pp l a nu s i n g a n tc o l o n ya l g o r i t h mi sp u tf o r w a r d a ne x a m p l ei sg i v e n f i n a l l y , b a s e d0 1 1t h er e s e a r c h e sa b o v e ，t h eu r b a np u b l i ct r a n s i ts y s t e mi sd e s i g n e d a n dt h et r i pp l a nb e t w e e nt w og i v e ns t a t i o n si ss e a r c h e dr e a l i s t i c a l l y k e y w o r d s ：p u b l i ct r a n s i t ；g e n e r a l i z e dc o s t ；t r i pp l a n ；a n tc o l o n ya l g o r i t h m c l a s s n o - u 4 9 1 ；4 9 1 1 + 2 ；u 4 9 1 1 + 3 ；u 4 9 1 1 + 7 】 图目录 图l 本文研究的技术路线图5 图2 城市客运交通系统构成6 图3 具有6 个节点的图示例1 1 图4 同一线路两个方向上同名站点抽象成一点1 2 图5 不同线路同名站点抽象成一点1 2 图6 公交网络基本构成元素1 4 图7 公交网络出行方案表示图1 5 图8 公交网络拓扑关系图1 6 图9 乘客出行心理因素分析18 图1 0 基于换乘次数最小的公交最短路径算法2 5 图1 1 双桥试验示意图2 7 图l2 蚁群算法流程图2 8 图1 3 不同蚂蚁数量情况下最优h a m i l t o n 回路长度趋势3 3 图1 4 不同蚂蚁数量情况下的c p u 运行时间( m s ) 趋势3 3 图1 5 不同启发信息系数的最优h a m i l t o n 回路长度趋势3 4 图1 6 不同伪随机比例因子的最优h a m i l t o n 回路长度趋势3 5 图1 7 不同局部更新系数的最优h a m i l t o n 回路长度3 6 图1 8 不同蒸发系数的最优h a m i l t o n 回路长度3 7 图1 9 算法主程序流程图一4 1 图2 0 蚂蚁构建路径模块流程图4 2 图2 l 算例网络4 3 图2 2 出行方案广义费用分布4 6 图2 3 广义费用随迭代次数的变化4 7 图2 4 系统功能模块5 0 图2 5 地图元素的基类一派生类的关系5 l 图2 6 城市公交实体网络5 3 图2 7 添加公交逻辑线路5 4 图2 8 公交出行广义费用影响因素权重设置5 4 图2 9 输入查询起、终点5 5 图3 0 公交出行方案查询结果显示5 5 表目录 表1 公共交通特性对比分析表1 0 表2 站点字段表1 5 表3 线路字段表16 表4 连接弧字段表16 表5 需要考虑的初始化及参数设置3 l 表6 不同蚂蚁数量下h a m i l t o n 回路长度和运行时间。3 2 表7 不同启发信息系数下h a m i l t o n 回路长度。3 4 表8 不同伪随机比例因子下h a m i l t o n 回路长度3 5 表9 不同局部更新系数下h a m i l t o n 回路长度3 6 表1 0 不同蒸发系数下h a m i l t o n 回路长度3 7 表1 l 算法参数设置3 9 表1 2 算例线路表4 4 表1 3 算例中算法参数设置表4 5 表1 4 蚁群算法出行方案4 5 表15d i j k s t r a 算法最优方案。4 7 表16 基于换乘次数最小算法最优方案4 8 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 南岛 导师签名： 亲吁 签字日期：2 g 年乡月，眇同签字日期：雳阳锣年舌月日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除 了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也 不包含为获得北京交通大学或其他教育机构的学位或证j f s 而使用过的材料。与我一同工作的 同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名： 签字日期：参劬9 年参月一日 6 7 致谢 在北京交通大学求学的生活即将结束，回顾这六年来的点点滴滴，让我感慨 万千。大学生活不但提高了我的专业水平，而且启发和拓展了我对于做人、做事 的一些新的认识和思考。这些收获与很多人的关心和帮助是分不开的。 本论文的工作是在我的导师宋瑞教授的悉心指导下完成的，读研期间，宋老 师不仅在专业学习上为我们传道解惑，更教会了我们学习和工作的方法与做人的 品格，在此衷心感谢两年来宋老师对我的关心和指导。 在撰写论文期间，许旺土、林建新、赵航、安健、王保华、白惠涛、孙杨等 同学对我论文中的很多研究工作给予了热情的帮助。在此向他们表达我的感谢之 情。 另外也感谢我的父母和亲人，由于他们的理解和支持使我能够在学校专心完 成我的学业，我所取得的所有成绩都与父母的辛勤培养分不开。 1 1 研究背景 1 绪论 随着我国城市化进程的不断加快，大城市机动车保有量逐年增多，由此带来 的交通拥堵、交通事故、环境污染等问题严重影响了我国城市的发展、人民群众 生活水平的提高。而在城市交通体系的构成中，公共交通相对于小汽车交通在占 用道路空间、运输成本、能源消耗以及环境污染等方面都有相当明显的优势。因 此，公交优先已经成为世界上解决大城市交通问题的主要措施之一。 城市公交系统的不断发展，将会有越来越多的常规公交线路、快速公交线路 和轨道交通线路，越来越多的人将选择公共交通作为主要的出行方式。预计在2 0 2 0 年，北京市出行总量将达到5 2 0 0 万 - - 5 5 0 0 万人次日，而中心城区公共交通出行 占客运出行总量的比例由2 0 0 0 年的2 7 ，提高到5 0 以上，其中轨道交通及地面 快速公交承担的比重占公共交通的5 0 以上【l l 。对于乘客来说，公交线路的增加固 然可以带来更多的出行选择，但另一方面也给乘客出行带来了极大的困扰。无论 对于当地人还是外来人员在进行公交出行路线选择时都是很困难的。因此，如何 从众多的出行备选方案中找到一条从出发地到达目的地的从距离、时间、经济、 换乘、旅行舒适度、安全性等多方面综合考虑的最优方案就显得尤为重要。这里 的最优方案建立在城市综合公交网络的基础上，并且不只局限于某一种交通方式， 而是在城市综合交通体系下包括各种交通方式内部及不同交通方式之间换乘的方 案。 因此，对于公交出行方案的研究可以在很大程度上解决乘客出行过程中遇到 的实际困难，提高乘客的出行效率。同时，对于推广公交优先政策、确定科学合 理的公交管理体系和提高公交系统的效率也具有重要作用。 1 2 研究现状 1 2 1 公交出行广义费用理论研究现状 广义费用是指：企业因生产经营活动和其它活动而发生的全部经济利益总流 出。广义费用应用到交通运输领域，多见于公路交通网络规划中，是基于网络规 划中对于道路服务水平的一切属性的综合评价的需要。 公交出行广义费用一般从费用和时间角度出发，对可定量化表示的指标进行 处理。在理论上把广义费用定义为与道路服务水平有关的旅行时间和道路长度这 两个属性的线性组合；或者单纯将换乘次数作为乘客出行路径选择的主要因素， 对一些重要的定性问题只作参考说明。而往往一些定性影响因素对出行决策也起 到很大作用，例如出行过程中的安全性、乘车舒适程度等，这些因素在以往评价 时研究不够深入。因此，对于公交出行方案的决策，需要一种能够综合反映出诸 因素对方案比选的不确定性、模糊性，深刻地反映出各方案的优劣的方法，使定 性问题定量化、定性与定量相结合来进行方案评价。 1 2 2 路径选择算法国内外研究现状 对于道路交通网络两点间最短路径的搜索，目前已有上百种成熟的算法( 最 著名的就是d 0 k s 仃a 算法) 。但现有的最短路径算法一般不能直接运用于公交网络 的路径选择中，因为公交乘客在出行的过程中不仅要考虑出行距离，还要考虑换 乘次数、出行时间、乘坐安全性和舒适性等其它因素。 国外对公交出行路径选择算法的研究伴随公交客流分配的研究而发展。 a n d e r s o nj 提出了名为v o l v o 方法的公交路径选择算法，该算法将换乘次数少作为 公交乘客出行路径选择的首要目标进行搜索【2 】；n i c h o l a sk o n c z 等提出了公交网络 静态多路径优选的算法，并以换乘次数为主要约束条件进行路径选择研究，但该 算法只能搜索一次及二次换乘的情况，而不能处理二次换乘以上的情况【3 】； n g u y e n 、d i m 等结合出行策略理论、有效路径算法和超级网络理论，发展了基于 超级路径和策略优化理论的公交网络有效超级路径搜索算法，该方法不需要枚举 所有的出行策略，同时能够生成多条优选路径，但当两点距离较远时，该方法产 生的“有效”路径过多，而其中很大部分是基本不被乘客考虑的路径【4 】；e h l b o v y 等研究了在多模式运输网络中乘客选择出行路径的行为特征【5 】。 随着一些城市公交乘客信息系统的建立，国内一些学者也开始对公交网络路 径选择算法进行研究。张国伍在扩展f l o y d 算法的基础上，提出了公交网络多条最 短路径算法，该算法一次可以搜索出所有的站点间的多条最短路径，但在只需选 择两点问路径的情况下应用效率较低嘲；王祖祥等研究了公交网络中乘客换乘次数 最小约束下的最短路算法，并给出了多条路径集的生成技术【7 】；杨新苗等进行了公 交乘客出行心理的调查，提出了以d 0 k s 仃a 算法为基础，以换乘次数最少为主要目 标，以出行距离最短为次要目标的出行路径选择模型，但是对于影响公交出行的 其它因素并未进行研刭副；近年来一些学者将现代启发式优化算法引入到该类问题 的研究中来，例如李文勇等使用蚂蚁算法求解公交出行路径选择问题【9 】，但该研究 2 只是涉及到常规公交一种交通方式，不能有效表达不同方式之间的换乘，而且只 是以最小换乘次数为约束，并没有综合考虑影响乘客出行的其它因素。杨励雅等 利用遗传算法进行了公交出行选择路径的研究【1 0 1 。 此外，对于公交网络中两点间多条最优路径的选择是该类问题研究的另一个 难点。由于公交乘客出行路径选择心理的复杂性，往往单一的乘车路径并不能满 足所有乘客的需要。例如，一些乘客希望选择换乘次数最少的乘车路径，而另外 一些乘客则倾向于选择出行距离更短的乘车路径。因此，不能只为用户提供单一 的出行方案，还应提供一定数量的合理各选路径供出行者根据实际情况进行选择。 q i 均i 1 1w u 等使用图论中k 最短路径算法( k s p ) 求解公交网络中多条备选路径的 选择问趔1 1 】，但k s p 算法产生的多条路径往往过于相似，很难称是真正意义上的 备选方案。 近些年来，随着网络技术的不断发展，国内出现了很多公交查询的电子地图 网站，如m a p b a r 、b j b u s 、5 1 d i t u 等。已经可以为出行者提供丰富的出行信息，包 括：显示城市的电子交通地图，同时具备放大、缩小、漫游等功能；查询某条公 交线路的具体停靠站点；查询给定起、讫站点间的最优公交线路( 包括公交线路、 换乘地点及换乘线路、经过站点) 。在这些功能当中，对于乘客来说最具意义的无 疑就是查询给定起、讫点之间的出行方案。而在实际应用中我们发现，由于系统 采用的搜索算法不同、费用的计算方法不同，同样的出行问题在不同系统中得到 的结果是不相同的，而且有些查询结果明显不合理。 综上所述，在目前的公交出行方案研究方面存在以下主要问题： ( 1 ) 主要以换乘次数为主要约束条件进行出行方案的研究，其它如出行距离、 出行时问、安全性以及舒适性等因素考虑较少，而这些因素也是乘客出行必须考 虑的，有时也是十分重要的。 ( 2 ) 通常只是在一种交通方式下研究，对于包括常规公交、快速公交和轨道 交通的城市综合交通系统下的公交出行方案研究较少。 ( 3 ) 在算法研究方面主要以d i j k s t r a 及其改进算法为主，由于该算法执行速 度较慢，而且在运行过程中不能考虑换乘次数，通常会出现两点问需要换乘很多 次才能到达的结果，而多次换乘在实际应用中是没有意义的。 1 3 本文研究主要目标和内容 1 3 1 研究目标 3 本文将在分析我国大城市公共交通构成及特点的基础上，对影响乘客出行选 择的因素及相关算法进行综合分析。 ( 1 ) 分析乘客出行心理，考虑时间、费用、换乘、舒适性等影响因素，给出 城市综合公共交通体系下的出行广义费用模型和公交出行决策模型： ( 2 ) 研究目前存在的蚁群优化算法，针对城市交通网络的特点，确定算法的 初始化设置方法和各种参数的取值，并提出利用蚁群算法搜索公交出行方案的具 体方法和步骤； ( 3 ) 结合理论研究进行城市公交出行查询系统设计，并实现用蚁群算法搜索 出符合人们需要的出行方案。 1 3 2 研究内容 全文分为六章，第一至四章围绕本研究的主要内容进行了理论分析，第五章 是系统设计部分，最后一章是本文研究的总结和展望。 第一章为绪论部分。主要阐述了有关公交出行方案的广义费用及路径搜索算 法的研究现状，提出了本论文的研究目标、研究内容和研究思路； 第二章为城市公交系统构成及网络描述。分析对比了目前我国大城市公共交 通方式的构成和特点，分析了公交网络的特点，重点对公交网络的数学模型和拓 扑结构进行研究； 第三章为公交出行广义费用及决策模型研究。通过对乘客出行选择影响因素 的分析，研究了公交出行的广义费用体系，并提出在常规公交、轨道交通和快速 公交三种公共交通方式下的公交出行广义费用模型及乘客公交出行决策模型； 第四章为蚁群算法在公交出行方案问题中的应用研究。这部分在研究已有算 法的基础上，分析了蚁群算法的原理、特性及参数设置问题，提出新的初始化信 息素和启发信息的设置方法，并通过实验的方式研究了参数大小对于算法结果及 效率的影响，之后提出了利用蚁群算法搜索公交出行方案的方法及步骤，并结合 算例进行具体分析。 第五章为城市公交出行查询系统设计及实现。利用v c + + 从底层开发城市公交 系统，介绍了系统的主要模块及相关类的构成。之后利用以上几章提出的理论和 算法进行给定站点之间的出行方案生成。 第六章为结论部分。总结本文所作的工作，并对存在的问题及今后的研究进 行展望。 本文的技术路线如图l 所示。 4 理 论 部 分 图l 本文研究的技术路线图 f i g 1t e c h n i c a lr o u t eo ft h i sd i s s e r t a t i o n 5 算法部分 应用部分 _ 一 - 2 城市公交系统构成及网络描述 2 1 城市公交系统构成及特点 改革开放以来，随着我国经济的快速发展，包括公共交通在内的城市基础设 施建设投资有了巨大的增长，促使我国公交事业得到了前所未有的大发展。一方 面，常规公交车的发展在数量上和方便程度上有了极大的提高，但由于我国城市 公共汽车长期以来过分强调“公益性 ，而忽视其“经营性”，在服务质量、时间 性、舒适性和安全性等方面亟待提高。另一方面，人们对于出行方式的选择越发 多样化，近些年来大量建设的轻轨、地铁等交通方式无论在服务质量和安全、舒 适性上都要好于常规公交。同时，由于城市轨道交通具有投资大、建设周期长等 特点，出现了一种介于常规公交与轨道交通之间的一种新的交通方式，即快速公 交，它同时具有常规公交灵活性和轨道交通的快捷性。 从交通服务的对象来分，居民出行方式可以分为私人交通和公共交通。公共 交通方式主要体现在其为公众服务的性质，表现为服务对象的公众化和不确定性， 一般是指常规公共汽( 电) 车、轨道交通和快速公交等；私人交通方式主要体现 在为特定个体服务的性质，表现为服务对象的个体化和确定性，一般指步行、自 行车、摩托车和小汽车等。因此，我国大城市客运交通系统组成中的出行方式结 构如图2 所示。 图2 城市客运交通系统构成 f i g 2s t r u c t u r eo f u r b a nt r a n s i t 6 2 1 1 常规公交系统 我们目前所说的常规公交一般包括普通公共汽车、电车和小公汽三种。由于 城市轨道交通系统投资昂贵、技术要求高、建设周期长，要成为城市客运交通的 骨干还有一个过程。因此，常规公交仍是目前我国城市公交的主要方式，为城市 的中、低收入居民提供低价格的出行机会，在一般中、小城市几乎占据9 0 以上 的份额，在大城市公共交通中比例也达到7 0 以上。因此，常规公交的发展状况 在很大程度上反映了一个城市的公共客运交通系统整体水平。 近年来，我国城市常规公共汽车得到了很大的发展，主要表现在公共汽车数 量和营运线路长度的增长上。在一些经济发达的大城市，公共汽车的线网密度已 达到了相当高的程度，居民出行可步行5 分钟到达公共汽车站，居民出行的二次 换乘率逐年下降。作为政府倡导的绿色交通方式，电车近年来在各大城市也得到 了长足的发展，其营运旱程增长迅速。在一些偏远的线路上，小公汽在很大程度 上解决了市民的出行难问题。但与此同时，私人小汽车交通迅速发展，大大增加 了小汽车对路面使用的需求，加剧了道路交通的紧张状况，对于没有公交专用道 路及优先通过权的常规公交影响严重，结果是常规公交车车速下降、正点率无法 保障、失去了与小汽车等私人交通方式的竞争优势，导致私人交通出行比例增加、 公交出行比例下降，呈现出某种恶性循环的状态。 常规公交系统具备下列主要特征： ( 1 ) 票价低廉 票价较低是常规公交同其它交通方式相比的优势，轨道交通票价一般为2 3 元，而大多数常规公交的票价为l 元左右。如北京目前实行的公交一卡通制度， 起步价成人票为0 4 元，学生票仅为0 2 元。 ( 2 ) 服务范围广 由于常规公交同轨道交通和快速公交相比，受行驶空间的约束较小，可以为 更大范围的乘客提供门到门的服务。因此，常规公交也是其它交通方式接驳、供 给和延伸的主要方式。 ( 3 ) 车速较慢 常规公交主要行驶在流量高的城市主要道路上，容易受交通阻塞的影响。随 着城市机动车保有量的逐年增加，常规公交的运营速度不断下降，高峰时段尤为 明显。上世纪5 0 年代，常规公交的平均运营速度为2 5 k m h 左右，6 0 年代开始下 降，平均时速在2 0 k m h 左右。目前，我国大城市常规公交运营速度仅为 12 。18 k m h 1 2 1 。 7 ( 4 ) 服务水平较低 长期以来，服务水平低已经成为影响常规公交发展和人们选择其出行的重要 因素。首先，在卫生、乘坐舒适性、服务态度等方面同其它交通方式确实存在较 大差距。其次，在线路上与其它车辆混杂行驶，易受交通阻塞和信号影响，正点 率低，尤其是在高峰小时，准时性很难保证。 2 1 2 轨道交通系统 城市轨道交通是大城市公共交通客运系统的骨干，是以大众化、大运量为特 征的安全、舒适、快速、准时的交通方式。它采用独立的专用轨道，高密度运行， 为城市内部中长距离运输提供服务。 轨道交通系统具备下列主要特征： ( 1 ) 较大的运输能力 城市轨道交通由于采用了高密度的运转方式，列车发车间隔时间短，行车速 度高，列车编组车辆数多，具有较大的运输能力。单向高峰小时运输能力轻轨为 l 4 万人，地铁为4 - 6 万人，市郊铁路可达6 8 万人【1 3 1 。 ( 2 ) 较高的准时性 城市轨道交通系统处于封闭状态，车辆在专用行车道上运行，不受其它交通 工具干扰，既不会产生拥堵现象，也不受气候条件影响，按照运行图行车，具有 可靠的准时性。 ( 3 ) 有较高的安全性和舒适性 城市轨道交通没有平交道口，全封闭、全立交、不受行人和其它交通工具干 扰。具有先进的通信信号设备和列车控制系统，包括自动列车防护系统( a t p ) 、 自动列车监督系统( a t s ) 和自动列车运行系统( a t o ) i 1 3 ，基本不会发生交通事 故，有较高的安全性。同时轨道交通还具有良好的乘坐设施、导向设施和自动售 检票系统，乘车条件优越、舒适性好。 ( 4 ) 有较高的速度 轨道交通与常规公交相比，有较高的起、停速度和运行速度。列车行驶在专 用轨道上，最高时速可达7 0 k m h 以上，运营速度一般为4 0 5 0 k m h 1 3 】。同时，轨 道交通多采用高站台，乘客乘车方便，换乘迅速，可以有效缩短在途时间。 ( 5 ) 造价昂贵 由于需要在轨道上运行，且车辆及相应的配套设施价格昂贵，轨道交通建设 投资巨大，这是制约其发展的主要原因。美国洛杉矶地铁造价高达2 1 亿美元英 8 里，日本东京的h a n z o m o n 线造价为3 0 0 亿日元k i n 。在我国，地铁造价一般为5 - 9 亿元k m 1 3 1 。 ( 6 ) 线路固定，直接服务范围小 轨道交通一旦建成，线路很难更改，不如常规公交机动灵活，需要其它交通 方式的配合才能发挥运能大的优势。 2 1 3 快速公交系统 快速公交系统( b u sr a p i dt r a n s i t ，简称b r t ) 是一种介于常规公交与轨道交 通之间的新型交通方式。它利用现代公交技术配合智能交通管理手段、使用改良 型的公交车辆、运营在公共交通专用道路空间上，使常规公交接近轻轨交通的服 务水平且具有常规公交的灵活性，其投资及运营成本又比轨道交通低，是一种便 利、快速的公共交通方式。 b r t 系统的核心包括【1 4 】：在城市的道路上开辟公共汽车专用路或公交汽车 专用道，形成快速公交线网；在道路交叉口实施公交优先通行；提高公共交 通运营效率，对线路、车辆、车站及枢纽进行优化，完善公交的管理体制，提高 运营速度和整体服务水平。 快速公交系统具备下列主要特征： ( 1 ) 类似轨道交通的车辆 快速公交系统的车辆不同于常规公交，通常采用大型铰接车以提高整个系统 的运输能力及减少运营成本。此外，对于环境影响较小的清洁公交车辆的使用也 较多。 ( 2 ) 道路的专有权 快速公交系统的公交车辆主要运行在专设的公共交通专用车道或道路上，以 信号优先作为辅助手段。 ( 3 ) 基础设施完善 快速公交车站具有许多轨道交通车站的特性，如岛式车站、在车站上设置收 费系统、高站台以便于乘客上下车等。b r t 车站的设计一般需要具有明显的建筑 特征，以便于乘客辨认。因此，基础设施与车辆是b r t 区别于常规公交专用道的 重要特征。 ( 4 ) 统一的收费系统 快速公交系统的收费一般采用与轨道交通类似的收费体系，收费往往是在车 站或枢纽点上完成，以便于乘客快速上下车。快速公交的收费系统一般需要与整 个快速公交系统的运营管理体制相一致。 9 ( 5 ) 短暂的停留时间 结合信号优先和公交导向技术，使用各项措施提高通过能力，使快速公交能 够与轻轨相媲美。为减少车辆在站台停靠时间，快速公交通常采用低地板公交车 或高站台的设计。 2 1 4 几种公共交通特性对比分析 下面从运能、速度、服务范围、乘坐安全性及造价几个方面对比以上几种公 共交通方式，如表l 所示。 表l 公共交通特性对比分析表 t a b l elp r o p e r t i e so fd i f f e r e n tt r a n s i tm o d e 单向输送能力运行速度 造价 交通方式服务范围安全性 ( 万人d , 时)( 公里小时)( 美元公里) 常规公交o 昏旬91 5 2 0短途、中距离一般2 0 肛7 0 0 万 快速公交 1 5 22 5 3 0中k 距离较高6 0 0 1 5 0 0 万 轻轨1 03 惝 长距离 高12 0 0 - - 3 4 0 0 万 地铁4 64 0 5 0长距离高0 9 1 3 亿 由图中可以看出，常规公交造价低，但输送能力小、速度慢；而轨道交通输 送能力大、速度快，但是造价相对较高；快速公交则介于二者之间，同时具有常 规公交造价较低和轨道交通运能大、速度快的特点。 2 2 城市公交系统网络描述 2 2 1 图论基础 图论是研究与图有关的理论和算法的一门科学，它的应用非常广泛，已渗入 到语言学、逻辑学、物理学、化学、计算科学、系统科学等领域。近年来随着计 算机技术的飞速发展，图论在数据结构、网络设计等方面的作用正变得越来越显 著，公交出行问题就涉及到图论中的很多原理。 一般在几何上将图定义为空间上一些点( 顶点) 和连接这些点的线( 边和弧) 的集合。点表示研究对象；线表示这些研究对象之间的关系( 其中边是不带箭头 的线段，表示的是一种对称关系；弧是带箭头的线段，表示的是一种非对称关系) 。 1 0 如图3 表示的是具有6 个节点的无向网络，记为g _ ( ，e ) 。其中代表点集合， 胙 l 凡儿儿儿儿) ；e 代表边集合，庐 ( l 儿) ，( l 儿) ，( l 凡) ，( l 批) ，m 儿) ， ( n 3 , n 4 ) ，( n 4 5 ) ，( 5 儿) ) 。 图3 具有6 个节点的图示例 f i g 3a ne x a m p l eo fg r a p hw i t h6p o i n t s 图的拓扑结构可以用矩阵c = ( ) 一x 。 o ，1 ) “来表示。c 是一个刀刀矩阵， 满足： 勺= 躐笏茎主 协t ) 如果两节点有一条路段，则邻接矩阵中对应的元素为1 ；否则为0 。在邻接矩 阵中，每行元素之和正好是对应节点的出度，每列元素之和是对应节点的入度。 图3 的邻接矩阵如下所示。 c = 0l lo o1 1o 10 l0 ol 1o o1 lo 01 o o ll 0 0 0o 1o 01 10 如果把城市道路网中的道路起点、终点和交叉口表示为节点，把道路表示为 连接节点的边，把道路的长度、通行时间和拥挤程度等属性表示为道路的权，那 么道路网就被抽象成为带权的图，与之相关问题就可以利用图论的方法进行分析。 对于道路网络的最短路问题已经有很多研究，目前被广泛采用并且研究最多 的是d i j k s t r a 、f l o y d 算法。但是这些研究只能针对特定的网络，而不可能直接应 用于公交网络中的路径寻优，因为公交网络不同于道路网络，具有自己的特征。 2 2 2 公交网络特征 同城市道路网络相比，公交网络有如下特征： ( 1 ) 网络连通性不同 城市道路网络中的道路交叉点连接着与该路口连通的多条路段，而两条公交 线路的站点在同一点时，同路公交路段之间的连通性和不同公交线路的连通性是 有差别的。这是因为两路不同公交线路在空间上的同一站点的连通需要换乘，增 加了时间消耗。另外多条公交线路虽然可以相交于空间上的同一个点，但是该点 不一定是公交停靠站点，或者不是同时有站点，因而不同公交线路在此是不连通 的。公交网络中节点的连通状态有三种【1 5 】：同一公交线路的连通；不同公交 线路在同一点通过换乘实现连通；不同公交线路在不同点的连通，此种情况需 要步行和换乘，增加了时间的消耗。 ( 2 ) 公交站点的抽象 虽然不同的公交线路在行程上有重叠，但是各自的站点不可能是完全的几何 重叠，因而要做有效的站点问叠加分析。这就要求把空间上适当距离内的相异线 路的同名站点按一定原则抽象成网络图上的相关节点，从而模拟不同公交线路之 间的换乘情况。对于实际公交网络的抽象可以包括：对于同一公交线路两个方 向上同名站点的抽象，如图4 所示；对于不同线路同名站点的抽象，如图5 所 示。在实际中乘客必然要求在不同的公交线路之间实现换乘以到达目的地，这就 要求相对应的网络图中不同的线路的同名站点抽象为一点，实现整个网络的联通。 、4 r - - - - 2 一 = 尘 图4 同一线路两个方向上同名站点抽象成一点 f i g 4t h ea b s t r a c t e dp o i n tf r o mt w os i t e sw i t ht h es a m en a m eo fo n el i n e 八广 厶j l j 图5 不同线路同名站点抽象成一点 f i g 5t h ea b s t r a c t e dp o i n tf r o ms i t e sw i t ht h es a m en a m eo fd i f f e r e n tl i n e s 1 2 ( 3 ) 弧段具有双向性 一般来说，一路公交线路有两个行驶方向。因此在一条公交线路连接的两个 相邻站点之间，存在两条方向相反的弧段来分别记录该公交线路在两个站点之间 的联通性。若两个相邻站点之间存在着若干条公交线路，则弧段的数目为m = 2 n ， 其中刀为两站点间的公交线路数。 ( 4 ) 最短路径的意义不同 道路网络上的最短路径和公交网络上的最短路径的意义也不相同。道路网络 的最短路径只要求两点之间路径距离最短即可，而公交出行方案可能包含多条线 路之间的换乘，而这种换乘活动是有时间消耗的，因而就不能为寻求简单的距离 上的最短而随意换乘，因为换乘成本也是反映整个路径优劣的关键因素之一。一 般来讲，换乘次数不应超过三次，超过三次换乘的出行方案对于乘客来说意义不 大。 2 2 3 城市公交网络数学模型 城市公共交通线网由地面城市道路、地铁线路、轻轨线路、快速公交专用道 等通道设施，车站、站牌等乘降设施，运行在上面的常规公交、快速公交车辆以 及地铁、轻轨列车以及采用公共交通方式出行的乘客等众多因素共同构成，是一 个集交通设施、设备、运营组织方案和乘客于一体的多维网络。下图6 表示一个 由常规公交、轨道交通、快速公交三种公交方式构成的局部公交网络。 图6 所示公共交通网络可以表示为g = ( n ，e ) 其中为节点集合，e 为弧集合。 节点集合包括物理实体站点和逻辑站点构成，逻辑站又由常规公交逻辑站点以、 轨道交通逻辑站点轨和快速公交逻辑站点快构成。 n = 物理u 逻辑 ( 2 - 2 ) 逻辑= u 轨u 快 ( 2 3 ) 整个网络按交通方式又可分为常规公交网络、轨道交通网络、快速公交网络 和换乘网络。因此，公交网络图又可以表示为： g = u u 嘞u 嘻( 2 - 4 ) 其中鲰为常规公交网络： 啄2 ( ，啄) ，= ( f 洲，) ( 2 5 ) 同理可得到轨道交通网络、快速公交网络和换乘网络： 1 3 b 塞蛮迫厶堂亟生羔位诠塞 邀丑! 垒童丕缝塑盛壁幽络描述 g 轨2 ( 4 n ，石九) ，e 巍2 ( f ，) i f n 轨 g 伙2 ( j v 伙，e 帙) ，e 稹。 ( i ，) 1 i j n 快 g 拽= e ( 巧) li j v 逻辑，且i ，不是同次车的站点 厂 厂 、j l f n el r 、一 r 、- 图6 公交网络基本构成元素 ( 2 6 ) ( 2 7 ) ( 2 8 ) f i g 6c o m p o n e n t so f t r a n s i tn e t w o r k 因此，图6 的公交网络中的一种出行方案可表示为图7 所示。图中，o r 睹n 一 1 2 a 一2 b 一3 b 一3 a 一4 一d e s t i n a t i o n 表示乘客从出发点步行到达站点1 ，进入常 规公交网络乘坐常规公交线l i n e a 到达站点2 ，经换乘网络进入轨道交通网络，并 乘坐轨道交通线l i n e b 到达站点3 。再经换乘网络进入快速公交网络，并乘坐快速 公交线l i n e c 到达站点4 ，由站点4 步行到达目的地。其中2 a 、2 b 分别代表l i n e a 和l i n e b 在实体站点2j ：的逻辑站点；同理，3 c 、3 b 分别代表l i n e c 和l i n e b 在 实体站点3 上的逻辑站点。需要强调的是，由于大多数常规公交、轨道交通和快 速公交线路在站点上并刁i 重合，乘客在由三者之间换乘时需要徒步走行一段距离， 这段步行包括在换乘弧中。图7 中的三种交通方式通过换乘网络来实现在彼此网 络中的换乘。但是，这种换乘不但消耗出行者出行时间，而且在很大程度上降低 了乘客出行的便捷性。 1 4 = e 塞銮适厶堂塑堂位途塞垃血公窑丕统捡盛丛圆终描述 i n eai 。il -常规公炎m 络 ! _ fi _轨道交迎川络 。：。；ii 快迷公文m 络 ；li l换乘例络 ；lj 2 2 4 城市公交网络拓扑结构 用几何描述的公交网络由线性特征和点状特征组成，是实际地理特征的图形 化表示。节点一弧段联合结构是g i s 表达道路网络的一种常用逻辑数据模型，该 模型用一组弧段组成，与线性特征相关的属性信息存储在与弧段相关联的属性表 中。本文采用节点一线路一弧段结构来表示复杂的公交网络拓扑关系。表2 至表4 分别为站点、线路和连接弧的字段表。图8 表示的是图6 公交网络的拓扑关系。 表2 站点字段表 t a b l e2f i e l d so fs t a t i o n s n o d ei d 站点名称r o u t el d 1 北京交通大学 、 2 b | 4 f s 2 两直i 、j2 3 7 1 5 表3 线路字段表 t a b l e3f i e l d so fl i n e s r o u t e i d 线路名称类型费制 1 运通1 0 5常规公交里程票制 2地铁2 号线轨道交通通票制 表4 连接弧字段表 t a b l e4f i e l d so f a r c s 起点终点 a r ci d r o u t e i d长度 ( n o d ei d )( n o d e d ) 112ll k m 22320 8 k m n o d e d站点名称r o u t e l d 1 北京交通大学 1 2 3 4 5 2 西直i 2 3 7 - r o u t e i d线路名称类型费制 1运通1 0 5常规公交里程票制 2地铁2 号线轨道交通通累制 起点终点 a r c dr o u t e i d 长度 ( n o d e i d ) ( n o d c