（地图学与地理信息系统专业论文）基于公交网络模型的最优路径算法研究与实现.pdf

摘要 城市公共交通是整个城市交通系统中的一个重要组成部分，它的 发展水平是衡量城市现代化程度的重要标志，同时也是解决大中城市 交通拥挤问题的最佳途径。而基于公交网络模型的最优路径选择是城 市公共交通中的一个重要子系统，是公共交通优先的保证，它对城市 结构的完善、土地使用的合理化有着重要的意义。 本文首先对国内外城市基于公交网络模型的最优路径算法的研 究和实践进行了总结，在此基础上分析了城市公交系统高效运行的实 现条件和影响因素。接着介绍公交网络的图的存储表示，并在分析公 交网络模型的基础上将其抽象成具有拓扑性质的网络图。然后提出了 用“平均换乘次数 来对公交网络的可达性进行评价，并给出了基于 n 次换乘矩阵和基于a 木算法的平均换乘次数计算方法。如果在乘客 的步行距离范围内，他们可能步行以减少公交换乘的次数，本文据此 给出了一种考虑步行换乘的平均换乘次数计算方法，并且通过一个实 例分析验证了该算法的有效性。 对于公交网络最优路径选择问题，本文给出了两种算法：一种是 基于网络变换的最短路径算法，公交网络经过网络变换，有换乘的网 络问题变换为没有换乘的网络问题，避免了计算直达矩阵与最小换乘 矩阵；一种是基于前n 条最短路径的以换乘次数最小为第一目标、出 行距离最短为第二目标的路径选择模型，并考虑乘客在步行距离范围 内步行以减少公交换乘次数的实际情况，给出了一个考虑步行换乘的 双目标公交路径选择算法。 本文以长沙派诺电子科技有限公司提供的长春市城市空间数据 为基础，完成了长春市公交信息查询系统的设计与开发。系统的主要 功能公交网络最优路径查询，用户通过键盘输入起终点或图上点击选 择起终点，然后系统就可以列出所有的以换乘次数最少为第一目标、 出行路径最短为第二目标的出行方案。另外，系统还有信息查询功能 即公交站点查询、公交线路查询、地名查询及公共场所查询等，并可 进行精确查询和模糊查询。 最后，对本文进行了总结，并对进一步的研究提出了一些建议和 展望。 关键词：公交网络，平均换乘次数，公交换乘，最优路径，m a p x a bs t r a c t u r b a np u b l i ct r a n s p o r t a t i o ni sa ni m p o r t a n tp a r to ft h ew h o l eu r b a n t r a n s p o r t a t i o ns y s t e m ，i t sd e v e l o p m e n tl e v e l i sn o to n l yas i g n i f i c a n t s y m b o lo ft h eu r b a nm o d e r n i z a t i o n ，b u ta l s oa no p t i m a la p p r o a c ho f s o l v i n gu r b a nc r o w d e dt r a f f i cp r o b l e m t h ep u b l i ct r a f f i cn e t w o r km o d e l a n dt h ea l g o r i t h mo fi t so p t i m u mr o u t ec h o i c ei sa ni m p o r t a n ts u b s y s t e m o fu r b a nt r a n s p o r t a t i o ns y s t e ma n dt h eg u a r a n t e eo ft h ec i t yt r a n s p o r t p r i o r i t y , w h i c hi ss i g n i f i c a n tf o rt h ep e r f e c t i o no ft h ec i t ys t r u c t u r ea n d r a t i o n a l i z a t i o no fl a n du s e t h i sp a p e rf i r s t l ys u m m a r i z e st h er e s e a r c h e sa n dp r a c t i c e so nt h e p u b l i ct r a f f i cn e t w o r km o d e la n dt h ea l g o r i t h mo fi t so p t i m u mr o u t e c h o i c eo ff o r e i g na n du r b a nc i t i e s ，a n a l y s e st h em e a n i n g so fi ta n dt h e r e a l i z a t i o nc o n d i t i o n sa n di n f l u e n c ef a c t o r sf o re f f e c t i v en m n i n g a n d t h e ni ti n t r o d u c e st h ec h a r ts t o r a g ee x p r e s s i o no ft h ep u b l i ct r a f f i c n e t w o r k ，w h i c hi sa b s t r a c t e dt oan e t w o r kw i t ht h et o p o l o g yp r o p e r t yo n t h eb a s i so fa n a l y z i n gt h em o d e l a f t e r w a r d s ，i tb r i n g sf o r w a r dt h a tt h e a c c e s s i b i l i t yo ft h eu r b a np u b l i ct r a f f i cn e t w o r kc a nb ee v a l u a t e db y a v e r a g et r a n s f e rt i m e s ( a t r ) ，a n dp r e s e n t st w oa l g o r i t h m s ：o n ei sb a s e do n t h en t ht r a n s f e rm a t r i x ，t h eo t h e ri sb a s e do na 木a l g o r i t h m a c c o r d i n gt o t h ef a c tt h a tp a s s e n g e r s 。w o u l dl i k et ow a l kt or e d u c et r a n s f e rt i m e s u s u a l l yw i t h i nt h e i rw a l k i n gd i s t a n c e ，an e wa l g o r i t h mi sp r e s e n t e dt o c a l c u l a t ea t i a ne x a m p l ei sg i v e nt ov a l i d a t et h ef e a s i b i l i t yo fi t o nt h ep r o b l e mo ft h eo p t i m u mp a t hc h o i c eo ft h ep u b l i ct r a f f i c n e t w o r k ，t h i sp a p e rp r e s e n t st w oa l g o r i t h m s ：o n ei st h es h o r t e s tp a t hc h o i c e a l g o r i t h m o nt h eb a s i so fn e t w o r k t r a n s f o r m a t i o n s ，a f t e r n e t w o r k t r a n s f o r m a t i o n s ，t h ep u b l i ct r a f f i cn e t w o r ki st r a n s f o r m e di n t oa n e t w o r k w i t h o u tt r a n s f e r , t h i sa l g o r i t h mc a na v o i dc a l c u l a t i n gt h r o u g hm a t r i xa n d l e a s tt r a n s f e rm a t r i x ；t h eo t h e ri st h ep u b l i ct r a f f i cr o u t ec h o i c em o d e l b a s e do nns h o r t e s tp a t h sa l g o r i t h mw h i c hu s e st h el e a s tt r a n s f e rt i m e sa s f i r s to b j e c ta n ds h o r t e s tp a t hd i s t a n c ea ss e c o n do b j e c t c o n s i d e r i n g p a s s e n g e r sw o u l dl i k et ow a l kt or e d u c et r a n s f e rt i m e su s u a l l yw i t h i n t h e i rw a l k i n gd i s t a n c e ，an e ws h o r t e s tp a t ha l g o r i t h mi sp r e s e n t e d t h i sp a p e rd e s i g n sa n dr e a l i z e st h eu r b a np u b l i ct r a f f i cq u e r ys y s t e m o fc h a n g c h u n ，w h i c hi sb a s e do nt h es p a t i a ld a t ao fc h a n g c h u np r o v i d e d b yc h a n g s h ap i l o te l e c t r o n i ct e c h n o l o g yc o m p a n y t h ec e n t r a lf u n c t i o n i st h eo p t i m u mp a t hc h o i c eo ft h ep u b l i ct r a 伍cn e t w o r k ，u s e r sc a ni n p u t j u m p i n g - o f rp o i n ta n d t e r m i n a lo nt h ek e y b o a r do rd o to nt h em a p ，t h e n m e yc a nh u n to u tc h o i c e so fu s i n gt h el e a s tt r a n s f e rt i m e sa sf i r s to b j e c t a n ds h o r t e s tp a t hd i s t a n c ea ss e c o n do b j e c t i na d d i t i o n ，t h e r e i s i n f o r m a t i o nq u e r yw h i c hi n c l u d e sb u ss t a t i o n s ，b u sr o u t e s ，p l a c e n a m e sa n d p u b l i cp l a c e s ，i ta l s oi n c l u d e sp r e c i s ea n db l u r r yq u e r y a tl a s t ，t h i sp a p e rs u m m a r i z e st h em a i np o i n t s ，a n db r i n g sf o r w a r d s o m ea d v i c ea n dp r o s p e c tf o r t h ef u r t h e rs t u d i e s k e yw o r d s ：t h ep u b l i ct r a 伍cn e t w o r k , t h ea v e r a g et r a n s f e rt i m e ，t h e p u b l i ct r a n s f e r , t h eo p t i m u mp a t h ，m a p x u l 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：丝如瑶日期：塑哩年月迎日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 储躲驷难导师签名雒鲻吼半上月芈日 1 1 研究背景 第一章绪论 随着经济社会发展和城镇化进程的加快，我国的机动车拥有量和道路的交通 量急剧增加，尤其在大城市，交通拥堵以及由其引起的交通事故的增加，环境污 染的加剧，已经成为我国城市面临的极其严重的“城市病之一，严重影响了城 市发展和人民群众生活水平的提高。解决这些问题的传统途径是拓展道路，但是 我国土地资源稀缺，城市内可供拓展的道路空间非常有限，城市人口也非常密集， 不可能仅靠拓展道路来解决这些问题，必须想办法提高道路的利用率。有关专家 指出，在多种城市交通构成中，城市公共交通在占用道路空间、道路环境污染和 能源消耗等三个方面，具有其它交通方式无法比拟的优越性。若按在市区同样运 送1 0 0 名乘客计算，使用公共汽车与使用小汽车相比，道路占用长度减少9 倍， 节省油耗约5 倍，排放的有害气体最多的可降低1 5 倍左右。另外，城市公共交 通也是解决低收入人群出行难的基本保障。因此，要解决大、中城市目前存在的 交通拥挤、交通事故频繁和环境污染严重等问题，应特别重视优先发展城市公共 交通【1 j o 目前，我国城市的公交系统普遍存在以下几个问题【2 j ： ( 1 ) 换乘次数多。体现出公交网络在自达性方面尚不能满足乘客的需求，这 是一部分乘客感到不方便的主要原因。 ( 2 ) 站点覆盖率低。造成人们乘公交车不方便，步行距离太长。 ( 3 ) 车外耗时多。产生这些问题的原因是多方面的，公交网络与站点布设不 合理，公交网络密度分布与出行需求量密度分布不匹配，都是决定性的因素。在 公交系统中，基于公交网络模型的最优路径选择是运行的基础，因此，对公交网 络模型进行评价，从而优化公交网络，并找出其最优出行路径是提高公交系统服 务水平和公交客流吸引率的根本所在，也是最经济、最有效的手段。合理的公交 网络结构，对于提高系统的整体效率、缩短居民的出行时间、减少换乘次数、均 衡公交客流等都会产生积极影响。 城市公交系统的发展离不开相关理论与技术的支持。目前，国内一些研究单 位以国内城市为依托，在基于公交网络模型的最优路径算法方面做了许多有益的。 探索，提出了多种基于公交网络的最优出行路径选择方法，但是，大多数方法没 有考虑影响乘客出行选择的实际因素，缺乏实用性。在上述背景下，本文将对基 于公交网络模型的最优路径算法进行研究，旨在探求能够适合乘客出行需要，实 用性强的最优出行路径选择算法，为乘客的公交出行提供帮助，从而促进我国公 共交通事业的健康发展。 1 2 研究的意义及目的 1 2 1 研究的意义 在城市公共交通所面临的众多新课题中，本文选择基于公交网络模型的最优 路径算法这一课题来研究，这是由我国城市目前的交通现状和发展需求决定的， 现阶段对这一课题进行研究具有十分重要的理论和实践意义。 近年来，我国各个城市较之以前都有所扩大，人们在城市各个地方的活动频 度也都有所增加，公共交通也随之有了很大的发展，逐步形成了四通八达的城市 交通系统。 目前，公共交通仍然以公交车为主要的交通工具。公交车在我国城市客运系 统中起着主要作用，是人们日常生活中出行的主要交通工具。在改造旧城市和建 设现代化新城市的过程中，对公共交通系统做出合理的规划尤为重要【3 】。由于城 市公共交通的基本职能是为人们的出行提供服务，因此它的基本任务是通过为乘 客提供安全、方便、迅速、准点、舒适的乘车条件，最大限度地发挥现有公共交 通设施的营运能力，节约全社会的总乘车出行时间【4 羽。 当前，随着经济的发展，城市规模在不断地扩大和超常规的变化，城市公交 网络的规模和布局总是滞后于城市的发展，还不能很好地满足人们的出行需求。 所以，改进以公交车为主体的公共交通依然是改善城市交通现状的主要手段。因 此，在城市公交网络的规划工作中对公交网络模型进行评价，从而优化公交网络， 并找出其最优出行路径，对于满足客流需求，提高公共交通的便利性和经济性， 减少运能的浪费，缓解以至解决城市公交紧张的状况具有重要而现实的意义【6 】。 城市公共交通涉及面广，影响因素繁杂，必须抓住其主要矛盾才能解决问题。 通过分析比较，本文认为城市公共交通的核心问题是公交网络的合理布局与车 辆、资源的合理配置与调度。对公交网络模型进行科学合理的评价是公共交通系 统的一个重要组成部分。城市公共交通系统运行良好的标志在于这个系统内部各 子系统之间的相互协调，以及系统的总体有效性。如果一个公共交通系统的网络 布局不合理，那么即使在其他方面做出很大的努力，也是事倍功半，很难使这个 系统达到最佳运行状态r 7 - 9 1 。 在现有的公共交通条件下，提供满足乘客实际需求的最优出行路径选择有助 于人们确定出发时间、出行线路和换乘方案等，即在乘客给出起始点和目标点后， 自动生成最优出行路径方案供乘客选择。对于传统意义上的最短路径来讲，只要 两个顶点之间有边存在，它就可以进行搜索，而不去考虑该路径的换乘代价，这 就可能造成搜索得到的最短路径需要换乘多次，但是换乘的次数越多，意味着花 2 费的时间和金钱越多。因此需要给出种综合考虑多种因素的公交换乘算法。 1 2 2 研究的目的 本文在总结国内外公共交通问题前沿研究及应用成果的基础上，对城市公交 网络及其最优路径选择的一些重要问题进行分析研究，旨在补充和完善针对我国 城市公共交通问题研究的理论与方法，为公交网络的优化和公共交通最优出行路 径的选择提供有效的科学依据和决策支持。 具体目标为： ( 1 ) 对国内外城市的公交网络模型及其最优出行路径选择的研究和实践进行 总结，在此基础上分析城市公共交通的内涵、公交网络模型的评价及最优出行路 径选择的实现条件和影响因素。 ( 2 ) 根据公交网络的特点，讨论公交网络模型的基本数据组织。 ( 3 ) 对公交网络模型进行性能评价，选择反映公交网络可达性的指标平 均换乘次数的算法，并给出了基于n 次换乘矩阵和基于a 算法的平均换乘次数 计算方法。 ( 4 ) 根据公交出行的实际需求，给出两种基于公交网络的最优路径选择算法： 一种是基于网络变换的最短路径算法；一种是基于前n 条最短路径的以换乘次 数最小为第一目标、出行距离最短为第二目标的路径选择模型，并考虑乘客在步 行距离范围内步行以减少公交换乘次数的实际情况，给出了一个考虑步行情况下 的双目标公交路径选择算法。 1 3 国内外研究现状 1 3 1 国内研究现状 我国在基于公交网络模型的最优路径算法方面的研究虽然较国外起步晚一 些，但是经过国内学者的不懈努力，取得了一定的研究成果。韩传峰、胡志伟通 过建立数学模型，研究城市公交网络的拓扑结构，计算反映其综合性能的指标一 平均换乘次数，对该城市的公交网络的性能做出评价，据此评价给出该公交网 络的发展战略【l o l ；师桂兰等以平均换乘次数反映网络可达性这一指标，来讨论 公交网络的性能，最后得出结论：换乘次数越大说明城市公交网络的可达性越差， 公交网络的性能也越差，反之换乘次数越小说明该城市的公交网络的可达性越 好，公交网络的性能也越好【l l 】；翁敏在讨论公交网络特性的基础上，提出适于公 交网络的数据组织，将公交网络的数据组织以节点弧段有向线进行描述，研究 综合换乘次数及距离因素的出行路径选择模型，并提供算法的实现【l2 】：傅冬绵 设计了最小换乘的广度优先搜索算法摘要，他把图论中针对单个节点的广度优先 3 搜索思想，推广到拥有若干个节点集合的广度优先搜索上。对旅游路线中最佳路 径的问题，提出一种新的算法，可解决旅游路线中的最少换乘问题【1 3 】；赵巧霞 分析了一般公共交通的特点，建立了以换乘次数最小为第一目标，途经站数最小 为第二目标的最优公交出行路径模型。对这一组合优化问题，设计了广度优先搜 索算法，包括换乘次数上界确定和换乘点选择算法【1 4 】；徐兵从节约存储空间、 提高运算速度出发，结合最短路径换乘算法的优缺点，给出了一种高效的换乘算 法数据模型，并设计了基于站点优先级的公交换乘算法，最后给出该算法的应用 实例1 1 5 l ；苏爱华针对公交网络换乘问题构造了公共交通网络模型，基于该模型， 提出了基于改进d i j k s t r a 算法的公交网络最短路径问题的求解。将求解最短路径 获得的站点作为搜索站点，并将这些站点及经过这些站点的线路构成换乘矩阵， 结合换乘次数的要求，给出了换乘的实现算法，确定可行的换乘方案【1 6 j 。 1 3 2 国外研究现状 国外在基于公交网络模型的最优路径算法方面有广泛深入的研究。j a n e z 研究了用二重图表示公交网络模型【1 7 1 ；h o n gk i o 等建立了模型来解决多种公交 方式换乘过程中计算换乘方式数目及换乘中的非线性费用两个问题，并以此为依 据对公交网络进行评价【埔j ；w e l d i n g ，h e a p ，t h o m a s ，o s u n a 和n e w e l l 研究了 考虑换乘等待时间的最优路径选择【l 蛇l 】；j o l l i f f e 和h u t c h i n s o n 认为换乘等待时 间的随机性随公交发车时间间隔的增加而降低圈；a b k o w i t z 根据不同的公交网 络情况定义了四种处理公交出行的选择策略瞄j ；s a l z b o m 调查了若干支流与一条 主干道路的综合换乘情况，并且提出了一种公交出行最优路径选择的方法【2 4 j ； n g u y e ns 与s p i e s sh 将乘客选择公交出行路径作为通常的线性问题研究，他认 为乘客并不是选择在公交站点第一辆到达的公交汽车，而是使整个出行时间最短 的公交汽车1 2 弛6 】。w h ，j h 考虑了公交等待时间和车载时间，对s p i e s s 的研究内 容加以改进【27 】：d ec e aj 与f e r n a n d e ze 考虑了堵塞情况下公交出行时间最短的 问题【2 8 l ；l o z a n o a 与s t o r c h ig 研究了公交出行最优选择方式中的行为问题i 2 9 1 。 1 。4 论文的结构和研究方法 1 4 1 论文的结构 论文共分为六章，主要内容介绍如下： 第一章为绪论，在总结国内外基于公交网络模型的最优路径算法的研究成果 的基础上，讨论了发展公共交通的必要性和实际意义。 第二章分析公交网络的基本数据组织，介绍了图论的基本概念和公交网络模 型的数据组织，并给出公交网络的抽象和拓扑表示的方法。 4 第三章阐述公交网络性能评价指标平均换乘次数的概念和计算方法，给 出两种算法：基于n 次换乘矩阵的平均换乘次数算法和基于a 宰算法的平均换乘 次数算法，并考虑了步行换乘的实际情况。 第四章研究公交网络的最优路径选择问题，给出两种基于公交网络的最优路 径选择算法：一种是基于网络变换的公交网络最短路径算法；一种基于前n 条 最短路径的以换乘次数最少为第一目标、出行距离最短为第二目标的公交网络最 优路径选择算法，并考虑乘客在步行距离范围内步行以减少公交换乘次数的实际 情况。 第五章以长沙派诺电子科技有限公司提供的长春市城市空间数据为基础，完 成了长春市公交信息查询系统的设计与开发，并对系统的开发框架和功能结构给 出详细介绍。 第六章对本文进行总结，并对进一步的研究提出一些建议和展望。 1 4 2 论文的研究方法 城市公共交通是一个复杂的系统，在解决上述主要研究内容的过程中，本文 充分从系统的角度出发，利用系统分析的方法与理论来解决问题。本文选择平均 换乘次数这一指标对公交网络模型进行评价，在解决考虑步行换乘的平均换乘次 数计算方法问题上，以已有的平均换乘次数计算理论为基础，利用图论中最短路 径理论，结合公交换乘的特点提出相应模型。在考虑基于公交网络的最优路径选 择算法问题上，充分分析公交网络拓扑结构，提出了一种基于网络变换的公交网 络最短路算法。在研究了以换乘次数最小为第一目标、出行距离最短为第二目标 的公交最优路径算法方面，利用“前n 条最短路径问题结论，首先提出了基 于“前n 条最短路径算法的换乘次数最小为第一目标、出行距离最短为第二 目标的公交最优路径算法，并在此基础上考虑了步行换乘的情况。 5 第二章公交网络模型的基本数据组织 在地理信息系统中，常将空间事物抽象成点、线、面等几何要素。点、线建 立拓扑关系，可以组成网络。网络在几何上由边组成，边的端点、交点是网络的 节点。例如，道路网可以定义为几何上的“网”，行车路线可以定义为网络的“边 ， 车站站点可以定义为网络的“节点 。这样就把现实世界中的客观对象抽象成地 理信息系统中的网络、节点、边之间的关系。对应几何特征又有相应的属性特征， 例如道路网中的行车路线的距离等特征，转向点的通行规则等特征。一般情况下， 网络在数学和计算机领域中是被抽象为图这个概念的，所以其基础是图的存储表 示。 2 1 图 图是一种重要且复杂的数据结构。在线形表中，数据元素之间仅有着线性关 系，每个数据元素只有一个直接前驱和一个直接后继；在树性结构中，数据元素 之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素 ( 即其孩子节点) 相关，但只能和上一层中一个元素( 即其双亲节点) 相关；而 在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可 能相关【3 0 】。 一个图由两部分组成，一部分是节点，图的术语中也称之为顶点( v e r t e x ) ； 另一部分是顶点的偶对，称之为边( e d g e ) 。通常，图的任意一对顶点间都允许 有一条边。 2 1 1 图论中的基本概念 图论最早起源于一些数学游戏的难题研究，如欧拉所解决的柯尼希斯堡七桥 问题，以及在民间广泛流传的一些游戏难题，如迷宫问题、棋盘上马的行走路线 问题。这些古老的难题，当时吸引了很多学者的注意，在这些问题研究的基础上 又继续提出了著名的四色猜想、汉米尔顿( 环游世界) 数学难题。 6 图2 - 1 无向图图2 - 2 有向图 一般在几何上将图定义为空间一些点( 顶点) 和连接这些点的线( 边和弧段) 的集合，其中点表示研究对象，连线表示两个对象之间的某种特定关系。边是不 带箭头的连线，表示的是对称关系，弧段是带箭头的连线，表示不对称关系。可 以表示为一个偶对g = e ) ，其中v 表示顶点的集合，e 表示边的集合，因此图 2 1 可以表示为： v = v l ，v 2 ，v 3 ，v 4 ，e = e l ，e 2 ，e 3 ，e 4 ，e 5 除此以外，还可以用边的两个顶点来表示边。如果边e 的两个顶点是u 和v ， 那么e 可写成e = “v ) ，这里的沁v ) 表示u 和v 的无序对，即沁v ) 和( v u ) 都表达了 u 和v 为端点的无向边。这样图2 1 又可以表示为： 州e ) ，v = v lv 2 ，v 3 ，v 4 e = ( v l ，v 2 ) ，( v 2 ，v 4 ) ，( v l ，v 3 ) ，( v 3 , v 4 ) ，( v 2 ，v 3 ) ) 图2 1 中的边的两个顶点是无序的，一般称为无向图；在实际应用中图和每 条边分配一个方向是很自然的，这样的图成为有向图( 如图2 2 ) 。对有向图，有 向边e 用与其关联的顶点u 和v 的有序对来表示，即f 钆v ，u 表示边e 的起 点，v 表示e 的终点。因此图2 2 就可以表示为： 州e ) ，v = v l ，v 2 ，v 3 ，v 4 e = ， ， ， ， ) 如果顶点v 是边e 的一个端点，则称边e 和顶点v 相关联( i n c i d e n t ) ；对于 顶点u 和v ，若( u ，v ) e ，则称u 和v 是邻接的( a d j a c e n t ) ；若两条边有共同的顶 点，也称这两条边是邻接的。顶点v 的度( d e g r e e ) 是和v 相关联的边的数目， 记为t d ( v ) 。例如，图2 1 中v 2 的度是3 。对于有向图，以顶点v 为头的弧的数 目称为v 的入度( i n d e g r e e ) ，记为i d ( v ) ；以v 为尾的弧的数目称为v 的出度 ( o u t d e g r e e ) ，记为o d ( v ) 。那么， t d ( v 户i d ( v 卜o d ( v ) 应用中往往还需要对图中的边赋值，这个值称为权。它可以表示边的各种不 同的意义；如经过边的是一条道路，则权就可能是它的长度，也可能是它的通行 税赋或修建费用等。设边e i 的权为眦，则e 可以表示为： 7 e = ( e l ，w 1 ) ，( e 2 ，w 2 ) ，( e 3 ，w 3 ) ( e n ，w n ) ) 或者设 w = w l ，w 2 ，w 3 w h 则g 可以表示为一个三元组删e ，w 。 2 1 2 图的表示方法 图的模型复杂，应用广泛，所以图的表示方法也是多种多样的，如图的邻接 矩阵表示法、图的邻接表表示法、图的邻接多重表表示法。对应于不同的应用问 题有不同的表示方法，因为在后面的章节中要涉及到图的邻接矩阵表示法，所以 对该方法进行简要的介绍。 邻接矩阵是表示节点间的邻接关系的矩阵，若g 是一个具有n 个节点的图， 则g 的邻接矩阵是如下定义的n * n 的矩阵a ： a 一，1 ，若( v ；，v i ) 或 是图g 的边； 公式( 2 1 ) j 1 t i ”l 0 ，若( v i ，v 1 ) 或 不是图g 的边； 例如，图2 3 无向图的邻接矩阵为a ，如图2 4 所示： 图2 - 3 无向图 对于有向图2 5 的邻接矩阵为b ， a = 匡毫 ；寻 b 艇目 图2 5 有向图图2 - 6 邻接矩阵b 显然，无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定是对称 的。对于带权的图，其相邻矩阵中值为1 的元素可以用边的权来代替。 网络是一种带权的连通图，只要将邻接矩阵稍加扩充便可用来表示网络。设 网络g = ( v 卫，w ) 具有n 个顶点，编号为l 2 ，n 。描述网络g 的带权邻接矩阵 为n 阶方阵a ，其元素定义为： 8 m ，若顶点i 到顶点j 有邻接边，w i j 为该边上的权 a i j = 1 0 ，若i = j 公式( 2 2 ) l * ，若顶点i 到顶点i 无邻接边 例如图2 7 中无向网络的邻接矩阵为c ，如图2 8 所示： 5 71 0 图2 - 7 无向网络 1 05 7o o l 1 5o 8 7 0 00 0 c ：1 7 8 061 39 1 0 07 6 01 0 i 1 31 0o4 i 1 0 0o o9 0 040 图2 - 8 邻接矩阵c 用邻接矩阵法来表示图，需要存储一个n * n 的邻接矩阵来表示节点间的相邻 关系，对于有向图，需n 2 个位来存储邻接矩阵。用邻接矩阵来表示图容易判定 任意两个节点v i 和v j 之间是否有长度为m 的路径相连，这只要考察邻接矩阵的 第i 行和第i 列元素是否为0 或o o 就行了。 以上介绍的是图论中有关网络的几个基本概念和表示方法。在公交网络分析 中，为了更充分、更高效的发挥图论的优势，必须对公交网络模型进行研究。 2 2 公交网络模型 2 2 1 公交网络的构成要素 公交网络是城市交通网络的重要组成部分，它是一个连通图。它由公交站点 与站点之间的线路组成。 公交站点分为公交首末站与中间站点，中间站点又分为一般中间站与换乘 站。公交首末站是公交系统的重要组成部分，它合理的设置和布局，可以提高公 交分担率和公交出行的便捷程度，降低道路上机动车的交通量，有利于城市交通 问题的解决【3 1 1 。而公交中间站点形成了城市公共交通的重要依托地点，对周围 地区具有强大的吸引和辐射作用，换乘站一般安排三条以上的公共交通线路的到 发站，形式可以多种多样，通常安排有一定的运营管理调度设施及必要的后勤服 务设施，要求布局集中紧凑，可以多层衔接和立体换乘，做到人车分流，标志醒 目，尽可能减少换乘距离，方便舒适。合理布置城市公共交通中间站点，才能建 立一个更高水平的公交网络1 3 2 j 。 公交站点之间的连接路段可以是单向的，也可以是双向的，按照使用性质分， 可以分为一般的城市交通线路及公交专用线路。 典型公交网络如图2 9 所示： 9 o _ - 台一。 图2 - 9 典型公交线网示意图 线路l 线路2 一一一一线路3 一一线路4 o 燃点站 换乘站 一般中间站 公交网络是一个有向图，对于上述公交网络，各站点( 对应有向图中的节点) 间的连接路段( 对应有向图中有向边) 都是双向的，在示意图中没有画出双向箭 头。设站点集合用n 表示，连接路段用l 表示，则该公交网络可表示成g ( n ，l ) 。 其中，n = s d i = l ，2 ，1 0 ，而n d = s i 。s 6 ，s 7 , s l o 是起终点站集合；n r = s 2 ，s 4 ，s 9 ) 是 换乘站集合；n 。- - - - 8 3 ，s 5 ，s s ) 是一般中间站集合。l = 【s i ，s 2 】，【s 2 ，s l 】，【s 2 ，s 3 】，【s 3 ，s 2 】， 【s 2 ，s 4 ， s 4 ，s 2 ， s 3 ，s 6 ， s 6 ，s 3 ， s 4 ，s 5 ， s 5 ，s 4 ， s 4 。s 9 ，【s 9 ，s 4 ，【s 5 ，s 6 ， s 6 ，s 5 ，【s 7 s 8 】，【s 8 ，s 7 】，【s 8 ，s 9 】，【s 9 ，s 8 】， 8 9 ，s l o ， s 1 0 ，s 9 】) 是连接路段集合。 2 2 2 公交网络的特点 公交网络不同于一般的道路网络，它有如下特点【3 3 】： ( 1 ) 连通性 城市道路网络中的道路交叉点无差异地连接着与该路口连通的多条路段，在 道路网络上连通的两节点，在公交网络上不一定连通，如有道路连接而无公交车 到达的某两点。在公交网络中，多条公交线路虽然可以相交于空间上的同一个点， 但是该点不一定是公交停靠站点，或者不是同时有站点，因而不同公交线路在此 是不连通的。公交网络中节点的连通状态有三种：同路公交路段的连通；不 同公交线路路段在同一点通过换乘实现连通；不同公交线路路段在不同点的连 通，此种情况需要换乘多次车，增加了时间的消耗。 ( 2 ) 节点性质 虽然不同的公交线路在行程上有重叠，但是各自的站点不可能是完全的几何 重叠，因而要做有效的站点间叠加分析。在实际通勤中必然要求在不同的公交线 路之间实现换车以到达目的地，这就要求相对应的网络图上不同属性的边在节点 上的连通，这是公共交通网络分析的意义。空间位置特性。在同一道路上行驶 1 0 的不同公交线路在行程上是有部分重叠的，但各自的站点不可能完全重叠，因而 在公交网络分析中，就要求把空间上适当距离内的异线近邻同名站点按一定原则 抽象成网络图上的相关节点，从而模拟不同公交线路之间的换车情况。一对多 属性。在公交网络中，节点与属性之间为一对多的关系。道路网中空间位置和属 性相同的同名站点，在公交网络中因位于不同的公交线路而性质和权值可能不一 样。在公交网络描述中，可用节点权函数设置不同的值来模拟实际情况。 ( 3 ) 弧段性质 在公交网络中，弧段与属性之间为一对多的关系。如在城市中，一般情况下， 一条公交线路有两个行驶方向，因而在图的节点上，每个方向上各有一条出边和 入边，共四条边。而同一条道路上有若干条公交线路，因而对于相邻两站点之间 就有多条弧段的情形，弧段数由通过的公交线路数n 决定。一般情况下为 n u m = 2 n 。有着相同空间位置的弧段，可用弧段结构唯一确定，当为每条道路网 中的弧段匹配上公交属性时，弧段与属性之间为一对多的关系。为了表达这种一 对多的关系，当每条公交线路通过这段弧段时，都需要重复记录弧段的空间信息， 这就会产生大量的冗余数据。 ( 4 ) 有向线性质 实际的公交线路是有方向的，起点和终点决定了公交线路的行驶路径和方 向。不同的公交线路有不同的行驶路线和方向，即使同一路公交车，其上行车和 下行车行驶的路径和停靠站点也可能不完全重叠，所以公交网络图应是有方向 的，这种方向性无法用边的有向性来体现。所以在公交网络中，应引入有向线路 集，而空间位置相同的节点和弧段的性质和权值在不同线路上是不同的，另外， 在同一道路上平行行驶的多条线路的停靠站点和数目是不同的，这些差异只有在 有向线中才能体现。 2 2 3 公交网络表示方法 根据以上对公交网络特性的分析，为了对公交网络进一步分析，城市交通工 作者往往将公交网络以某种方式表示，以便对它的运营状况加以改善，对它的线 路加以优化，一般来说，可以通过以下两种方式对公交网络进行表示【3 6 】：一是 公交网络的相邻矩阵与邻接表；二是公交线路属性表。 ( 1 ) 公交网络的相邻矩阵与邻接表 根据以上论述，公交网络具有图的性质，而对于图的表示方法中主要有两种 方法：相邻矩阵( a d j a c e n c ym a t r i x ) 和邻接表( a d j a c e n c y l i s t ) 。 图的相邻矩阵是一个i v i i v l 数组。假设i v l - - n ，各顶点依次记为v o ，v l ， l ，则相邻矩阵的第i 行包括所有以v i 为起点的边。如果从v i 存在一条边，则 对第i 行的第j 列进行标记，否则不作标记。因此，相邻矩阵的每一个元素需要 占用一位。公交网络中一个公交停靠站仅仅与有限的几个站点直接相邻，而整个 研究范围的公交站点的数量有几百个乃至上千个。则显然在相邻矩阵中有大量的 元素为0 ，由此将浪费大量的资源。 图的第二种常见表示方法为邻接表。该邻接表主要描述公交站点在网络图中 的位置关系。即通过记录一个公交站点与其相邻的公交站点的连接状况来描述公 交网络中的站点位置关系。在邻接表中，对图中每个顶点建立一个单链表，第一 个单链表中的节点表示依附于顶点v i 的边( 对于有向图是以顶点v i 为尾的弧) 。 此表示法仅仅涉及到了与顶点v i 相关联的顶点信息，大大减少了其空间代价。 ( 2 ) 公交线路属性表 公交网络与一般的城市道路网络具有显著的差别之一就是公共交通看作一 个网络时是由许多的公交线路子网组合而成的，而公交线路子网是在公共交通线 路的布局时就已经确定，即公交线路子网的公交站点集已经确定。因此，乘客的 所有的公交出行路线是在设计的公交线路集中选择合适的路线完成出行。公交线 路属性表包括线路名称、沿途所经公交站点和弧段索引等。 2 3 公交网络抽象 2 3 1 节点抽象 实际公交网络抽象成拓扑性质的网络图，路径搜索时不同属性的边之间在节 点处的连通对应实际通勤的换车。换车要在公交站点处进行，这就要求把适当距 离内可能换车的多个站点抽象成一个节点。把空间位置相邻近的公交站点归并， 并抽象成图的节点，是生成公交网络图的关键彻。 ( 1 ) 实际网络中，同一公交线路两个方向上的同名站点的空间位置是不重合 的，我们把它们归并为同一点，并抽象成网络图上的一个节点( 如图2 1 0 所示) 。 抽象成网络图其它点 归并后的点 = = = 二，= 二二壹 图2 1 0 两个方向上同名公交站点的抽象 ( 2 ) 不同交通线路的站点空间分布情况较复杂，现以两条不同交通线路为例 来说明。根据站点调查和乘车经验，将公交站点分为如图2 一l l 所示的几种情况。 其中，站点重合的情况最简单，多个重合站点可抽象为图上的一个节点。 1 2 l 厂 j 乱站点 d 站 合 近邻 b 站点紧一 e 站点近一 c 站 紧邻 图2 - 1 1 实际公交网络中公交站点的分布 节点抽象的难点在于：紧邻和近邻站点的归并。紧邻和近邻站点的设置，目 的是模拟人们在不同线路间的换车，以便于路径寻优。紧邻、近邻是两个半定量 的描述公交站点间空间位置上的距离概念。在不同规模的城市或同一城市的不同 区域，不同公交线路相邻站点的距离及同一线路的不同相邻站点之间的距离有较 大差异。一般，城市中心区同线站点相邻距离较小，异线相邻站点相对多而分散。 而城市边缘区同线站点距离较大，异线站点在某一点集中。因此，根据实际公交 站点分布情况，我们定义近邻距离为：r l d i r 2 ，紧邻距离为：r 3 d i r l ，重合 距离为：d i r 3 。n ，r e ，r 3