基于动态分段的最优公交乘车方案查询的实现

摘要：多数公交查询系统的换乘方案都是采用最短路径的算法，本文对公交线路数据采用动态分段技术进行组织与处理，结合邻接矩阵的路径查询算法，可实现获得基于最短路径、最小换乘数或是最少费用等各种最优换乘方案，提高了公交换乘方案的适用性。

关键词：GIS动态分段公交换乘

中图分类号：U495;P208 文献标识码：A 文章编号：1007-9416（2012）03-0000-00

1、引言

目前多数公交查询系统的换乘方案都是采用最短路径的算法，本文对公交线路数据采用动态分段技术进行组织与处理，结合邻接矩阵的路径查询算法，实现了可获得基于最短路径、最小换乘数或是最少费用等各种最优换乘方案，提高了公交换乘方案的适用性。

动态分段技术

在GIS的网络分析模型中，线性特征构成了地理网络的基础框架。早期的GIS系统多数采用弧段―结点模型来描述线性特征，该模型由一组弧段组成，而弧段由构成网络线的一组有序坐标对组成，其中弧段的两个端点称为结点。与线性特征相关的属性信息储存在与弧段相关联的属性表中[1]。

动态分段是在弧段-结点数据模型的基础上根据不同的属性按照某种度量标准对线性要素进行动态相对定位的一种技术[2]。其基本思想是在拓扑图形的基础上建立线路系统，在对线性地物的空间信息进行查询和显示的过程中，系统根据所选择的属性数据以及所要满足的某种特定条件，动态地建立空间实体与其属性数据之间的关联与逻辑分段，从而达到在不增加系统数据库实际容量的前提下实现系统数据信息的按需分配[3]。

2、数据的动态分段组织

在本文中，利用动态分段技术对公交数据进行处理，各要素类和事件表的设计如下：(1)街道要素类。城市街道空间数据是本系统公交网络的基础数据，公交线路网络在此基础上创建。(2)公交线路要素类。在街道数据基础上通过动态分段方式建立。(3)公交站点要素类。存储公交站点数据，由站点编号和站点名称组成。(4)站点事件表。它是动态分段点事件表，由公交站点数据与公交线路数据生成，站点与线路通过RID进行关联。站点的度量值可确定站点在公交线路中的顺序、两站点方向、站点之间的距离等。(5)街道事件表。它是动态分段线事件表，由街道数据与公交线路数据生成，街道路段与公交线路通过RID进行关联。街道路段的起止度量值可确定某路公交经过该街道长度，RID与StreetName关联，可获得街道经过的公交。

3、系统实现

3.1算法分析

在获得用户出行的起始站点及目的站点后，能否从一个站到另一个站，须不断判断站点之间是否有联系，本算法中用邻接矩阵的存储了站点间的通达关系，两个站点可直达则值为1，不可直达则值为0，相同站点对值也为0。

在给定了起始站点、目的站点及搜索树层数N后, 对邻接矩阵进行按行优先(广度优先搜索的思路)搜索，建立一个以起始点作为根结点的双亲表示法搜索树。双亲表示法搜索树结点数据结构包含两个数据域，第一项为结点值，第二项为父结点索引值。根结点的无父结点，规定父结点索引值为-1。

当搜索树层数达到指定层数N时，对邻接矩阵停止搜索，搜索树建立完毕。然后从搜索树中包含目的站的叶子结点出发，找到父亲结点，一直回溯到根结点为止，除叶子结点和根结点外所经过的结点, 即为换车的中间站点，记录经过结点并加入方案组。当搜索层数过大或公交数据组织不合理时，所得到的方案并非完全正确。对于这些错误方案应给予排除，得到最终正确的方案组。

3.2最优方案获得

基于动态分段的公交线路数组织，在公交线路数据中有着票价和公交线路长度属性值，只需计算起始站点间公交线路长度之或票价之和，即可得到最短路径或是最少费用的公交换乘方案。在本文的公交换乘算法中，由于使用了邻接矩阵来存储站点的连通性关系，在查询时对搜索树的搜索层数就为换乘的次数，最后对此方法进行了实现。

在公交换乘方案的查询中，最短路径分析只需选择路径长度为搜索的限制条件，点击查询按钮后可得到两点之间的乘车方案列表，方案按路径长度排序；最少换乘分析选择换乘次数为搜索的限制条件，点击查询按钮后可得到两点之间的乘车方案列表，方案按换乘次数排序；最少费用分析选择乘车费用为搜索的限制条件，点击查询按钮后可得到两点之间的乘车方案列表，方案按乘车费用排序。

实验表明，基于动态分段的公交换乘方案查询，可以方便的设置不同的限制条件，如换乘次数、路径长度、乘车费用等，满足各种要求的乘车方案。

4、结语

动态分段技术较好的解决了城市公交查询系统在处理线性特征的数据时存在着重复数字化、数据冗余量大、多属性数据综合查询不易和数据难以维护等问题。本文在动态分段技术下实现了最优公交乘车方案的查询实现，但也存在一些问题，如对公交网络的抽象只限于完全的双向线路，情况较为特殊,在后续研究工作中可考虑更多情况。在方案查询时考虑更多因素，如行驶时间、乘车频率等因素，使之更加接近真实情况。

参考文献

[1] 高勇,刘瑜,邬伦.GIS 网络分析的动态分段方法与实现.地理与地理信息科学,2003,19(4):41-44.

[2] 吴木旺,任丽梅,查良松.基于动态分段技术的城市公交系统数据库的建立.地理信息世界,2006,4(003):61-65.

[3] 刘勖,宣国富,陈方才.动态分段技术在公交查询系统中的应用.北京测绘,2009(003):50-52.