资源描述：
《公交线路中最优路线的查询算法设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、公交线路中最优路线的查询算法设计149公交线路中最优路线的查询算法设计王朝晖,杨洁(江苏省测绘工程院,江苏南京210013)摘要在一个公共交通网络中寻找两个结点间的一条最佳路径,使之换车次数最少。利用GIS地理分析的特性,设计了合乎乘客心理的最优路线查询算法。本算法是基于广度优先搜索提出公交路线最短路径选择的算法。该算法对图的搜索方法提出了一个新的思路,经模拟试验,算法简单合理,运算速度快,容易在计算机上实现。关键词广度优先遍历最优路线数据库地理信息系统连通的多条路段,而两路公交线路的站点在同一点0引
2、言时,同路公交路段之间的连通性和不同公交线路的在智能交通系统中利用GIS、GPS等技术在全连通性是有差别的,这是因为两路不同公交线路在球范围内已是一种趋势。网络分析中最基本最关键空间上的同一站点的连通,要换车而增加了时间消的问题是最短路径问题。耗。另外多条公交线路虽然可以相交于空间上的同本文着重讨论交通系统中的最优路线查询。在一个点,但是该点不一定是公交停靠站点,或者不是这里,最优并不意味着最短。最优路线是指在通达同时有站点,因而不同公交线路在此是不连通的。出行者出行目的的多条线路中,能最好的满足出行
3、虽然不同的公交线路在行程上有重叠,但是各者愿望的线路,即是出行效用最大的线路。自的站点不可能是完全的几何重叠,因而要做有效1数据分析与组织的站点间叠加分析。这就要求相对应的网络图上不同属性的边在节点上的连通。在公交网络叠加分析对城市公交路线进行最优路径分析,需要将现时,要求把空间上相近的异线站点合理抽象成图上实中的城市公交网络实体抽象化为网络图论中的网的相关节点,来模拟不同公交线之间的可换车情况。络图,然后通过图论中的网络分析理论来实现道路节点抽象是公交网络抽象的关键。网络的最优路径分析。113城市道
4、路网的地图表示和网络拓扑结构的111基础数据提取在交通网络分析中,所需要的实用数据如下:GIS中的矢量地图是按图层组织的,针对图层11111道路网的空间信息道路网的空间数据由组织的特点,将城市道路网单独作为一个图层处理,一系列的结点以及连接这些结点的曲线构成。这里称之为道路层。由于在最优路线分析时,用户往往的结点既包括道路中的站点,也包括道路的交叉点。关心的只是街道的相关信息,因此在将实际的城市这种简单的数据源在对道路网的分析应用非常重道路网转化到地图的图层中时,只将各条街道作为要,如寻求道路网的最佳
5、路径等。线对象保存在图层中。至于街道的属性数据和交叉11112道路网的空间信息拓扑结构在组织数据路口的坐标信息,各GIS软件均提供了相应的数据时,应存储道路网络的拓扑结构,比如在一个道路交交换文件,以用于空间数据和属性数据的数据交换。叉点处,究竟有哪些道路在此交汇;一条道路究竟与哪些道路相连等。有了道路网的这些空间拓扑结构如MapInfo的.MIF和.MID文件,ArcInfo的信息,在进行道路网的最优路径计算时,会大大缩小shapefile文件等。在以下的讨论中,仅针对MapIn2道路网的搜索范围,
6、从而提高运算速度。fo的文件结构进行讨论。11113道路的属性是指对道路特征的描述,如道114数据组织路的名称、道路的等级、道路是否为单行道等。在MapInfo中,每个图层均有其对应的属性数112公交网络的特点据表结构文件(.TAB)。该文件定义了图层中空间城市道路网络中的道路交叉点连接着与该路口对象的属性数据的表结构,包括字段数、字段名称、150π2005数字江苏论坛———电子政务与地理信息技术论文专辑字段类型和字段宽度等,另外还指出索引字段及一与终点B之间的直线距离是260m,但是之间却没有些用于
7、显示的参数设置等。因此在道路层的属性数直达的公交车,如果按照文献[1,2]中的算法计算则据表结构文件中定义街道的属性信息字段如下:要转车。利用GIS对起点A所接近的道路和终点B所接近的道路进行分析,计算出起点A与终点B之街道ID街道名称正向权值反向权值间是否存在合适的道路可以步行,并根据道路的地表1街道的属性信息字段理特性计算出步行距离,如果步行距离在300m以内,则建议乘客步行。其中,街道ID是道路唯一的标识号;街道名称212Dijkstra算法不适合公交最优路径查询是道路的物理名称;街道的正向、反
8、向权值是不同方Dijkstra算法是目前解决最短路径问题采用的向上道路的权值,其方向是由地图绘制的方向确定。理论基础。该算法基于图论中的网络图模型,用标MapInfo对地图中的每一图层可以生成一种交换格号的方法不仅求出从v1到vn的最短路径,最后所式文件,它将地图空间数据与属性数据用文字的方得到的实际上是从v1到其它各个节点的最短路径,式表示了出来。交换格式文件包含有两类文件,其所以在求解时,都有可能并准备搜索所有的网络节中.MIF文件主要包含了空间数据
