基于最短路径查询的城市公交网络拓扑建模研究

《基于最短路径查询的城市公交网络拓扑建模研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、遥感信息理论研究$##$;"基于最短路径查询的城市公交网络拓扑建模研究陆忠，钱翔东，张登荣（浙江大学地理科学系，杭州!"##$%）摘要：最短路径分析是地理信息系统（&’(）中网络分析的一项重要功能，等价于图论中的节点间求解最短路径问题。对地理网络进行地理分析和建模，以实现最短路径搜索已经有大量论文讨论，但是专门针对城市公交网络的建模和路径寻优，则少鲜有研究，而且已有的一些网络模型也不能直接应用到公交网络寻优中。本文应用图论理论，讨论公共交通网络的拓扑建模，实现公交网络最优路径的查询。关键词：&’(网络建模；公共交通网络（公交网络

2、）；网络寻优（最短路径）中图分类号：)$*"文献标识码：+文章编号："###,!"%%（$##$）-.,##"",#/算法进行优化，以提高运行效率。其中被广泛采用"引言并且研究最多的是4256789:算法。第二类是对图的对网络进行地理分析和模型化是地理信息系统数据结构的研究［"#］，这些数据结构都以边和节点结（&’(）中网络分析的一项重要内容［"#］。网络主要指构为基础。第三类是关于道路网络、管道或管线网各种实际的道路（如铁路、城际乡间公路、城市道路络图的建模［.!%］。这些模型和算法研究针对特定的等）网络和城市管线网（如点里网

3、、给排水管网、电话实际网络，没有可能直接应用于公交网络寻优，因为网等）等［"］。网络建模指把实际网络抽象成图论中公交网络不同于道路网络。具有拓扑性质的网络图。&’(网络分析中的实际应$公交网络的特点用，如道路交通网络最短路径查询、电子导游图、城市管线管理系统、""#电子报警系统等，其实都等价公交网络有如下特点：于图论中的节点间求解最短路径问题［$!/］。（"）连通性一个图!"（#，$）是由有穷而非空的顶点集城市道路网络中的道路交叉点无差异地连接着#和边集$所组成，如果边是顶点的有序对（%&，与该路口连通的多条路段，而两路公交线路

4、的站点%’），（%&，%’）!$；%&，%’!#，则说这个图是有向在同一点时，同路公交路段之间的连通性和不同公的［$，!］。交线路的连通性是有差别的，这是因为两路不同公(，)是两个非空集合，*，+分别是#到(，$到交线路在空间上的同一站点的连通，要换车而增加)的两个映射，则称有序四元组!"（#，$，(，)）了时间消耗。另外多条公交线路虽然可以相交于空为加权图，(，)称为顶点的权和边的权。间上的同一个点，但是该点不一定是公交停靠站点，图!的一个边序列0，0，0，⋯，0，或者说一个或者不是同时有站点，因而不同公交线路在此是不#"$,

5、顶点序列%，%，%，⋯，%称为图从%到%的一条连通的。#"$,#,路经；从%到%的所有路径中，权-（%，%）最小（$）节点的特性#,#,的路径称为从%到%的最短路径，记为（%，%）。虽然不同的公交线路在行程上有重叠，但是各#,#,其长度为：自的站点不可能是完全的几何重叠，因而要做有效-（%#，%,）"123｛-&（%#，%,）.%#，%,!#；&""，$，⋯｝的站点间叠加分析。在实际通勤中必然要求在不同最短路径问题已经有大量的研究论文，这些论的公交线路之间实现换车以到达目的地，这就要求文大致可分为三类。第一类是最短路径的算法研相

6、对应的网络图上不同属性的边在节点上的连通，究［.!*］，讨论最短路径算法及根据实际问题对经典这是公共交通网络分析的意义。在公交网络叠加分析时，要求把空间上相近的异线站点合理抽象成图收稿日期：$##$,#","$作者简介：陆忠（"*%"!），男，浙江大学地球科学系硕士研究生，主要从事&’(应用开发、算法、图形图像处理等方面的研究。万方数据"#)--)$%理论研究遥感信息上的相关节点，来模拟不同公交线之间的可换车情和道路通畅程度有差异，因而实际公交网络抽象的况。节点抽象是公交网络抽象的关键。拓扑模型是有向带权图。（!）最短路径的意义

7、!实际的公交网络抽象成拓扑模型分析道路网络上的最短路径和公交线路的最短路径的意义也不相同。道路网络的最短路径值要求两点!$%实际公交线站点空间关系分析之间路径距离最短即可，或者改进为同时参考道路实际公交网络抽象成拓扑性质的网络图，路径的速度权值，获得最优路径。即使如文献［"，#］所述，搜索时不同属性的边之间在节点处的连通对应实际用层次空间模型来解决快速道路选择问题，但它在通勤的换车。换车要在公交站点处进行，这就要求不同层次的道路间穿越，在不同等级的道路的交叉把适当距离内可能换车的多个站点抽象成一个节口上并不增加时间消耗，对应于图

8、上在边界节点上点。把空间位置相邻近的公交站点归并，并抽象成不增加权值。公交网络中每一条公交线路也可理图的节点，是生成交通网络图的关键。解为一个层次，从一条公交线路到另一条公交线路在实际情况下，同一公交线路两个方向上的同的换车活动是有时间消耗的，因而就不能为寻找简