系统功能实现.docVIP

4.基于GIS公交查询系统功能的实现 4.1算法的设计与实现 4.1.1公交网络的特点 城市中公交汽车沿着道路运行，形成的公交线路网是建立在道路网之上，依据道路建立的网络模型并不能直接应用于公交网络，这是因为公交网络与道路网络相比有它的一些特点: 1、连通性 城市道路网络中的道路交叉点无差异地连接着与该路口连通的多条路段，而两路公交线路的站点在同一点时，同路公交路段之间的连通性和不同公交线路的连通性是有差别的，这是因为两路不同公交线路在空间上的同一站点的连通，要换车而增加了时间消耗。另外多条公交线路虽然可以相交在空间上的同一个点，但是该点不一定是公交停靠站点，或者不是同时有站点，因而不同公交线路在此是不连通的。 2、节点的特性 虽然不同的公交线路在行程上有重叠，但是各自的站点不可能是完全的几何重叠，因而要做有效的站点间叠加分析。在实际通勤中必然要求在不同的公交线路之间实现换车以到达目的地，这就要求相对应的网络图上不同属性的边在节点上的连通，这是公共交通网络分析的意义。在公交网络叠加分析时，要求把空间上相近的异线站点合理抽象成图上的相关节点，来模拟不同公交线之间的可换车情况。节点抽象是公交网络抽象的关键。 3、有向线性质 实际的公交线路是有方向的，起点和终点决定了公交线路的行驶路径和方向。不同的公交线路有不同的行驶路线和方向，即使同一路公交车，其上行车和下行车行驶的路径和停靠站点也可能不完全重叠，所以公交网络图应是有方向的，这种方向性无法用边的有向性来体现.所以在公交网络中，应引入有向线路集，而空间位置相同的结点和弧段的性质和权值在不同线路上是不同的，另外，在同一道路上平行行驶的多条线路的停靠站点和数目是不同的，这些差异只有在有向线中才能体现。 4、最短路径的意义 道路网络上的最短路径和公交线路的最短路径的意义也不相同。道路网络的最短路径值要求两点之间路径距离最短即可，或者改进为同时参考道路的速度权值，获得最优路径。即使用层次空间模型来解决快速道路选择问题，但它在不同层次的道路间穿越，在不同等级的道路的交叉口上并不增加时间消耗，对应于图上在边界节点上不增加权值。公交网络中每一条公交线路也可理解为一个层次，从一条公交线路到另一条公交线路的换车活动是有时间消耗的，因而就不能为寻找简单的路径距离的最短而随意换车，因为换车时间成本成了整个路径最优性的关键因素之一。 4.1.2公交网络的拓扑模型 公交车只能按既定的顺序停靠站点，每条公交线路都有规定的方向，因此，由实际公交网络抽象的拓扑网络图是一个有向图。在拓扑网络图上不同属性的边结点处连通，表示乘客可以在该结点处换乘。换乘必须在公交站点进行，不同公交线的站点在空间上并不一定完全相同，乘客在换乘时，一般需要步行一段距离，才能完成换乘。因此，需要将空间位置邻近的站点抽象成网络图中的一个结点。 将公交站点抽象成网络结点后，接下来要做的工作是将公交线路的各站点间的路段抽象成网络图中的边。公交网络图是一个赋权有向图，边的权值可以是路段的长度、路段通行时间，或其它的含义。通常一条公交线路有两个行驶方向，当两个方向的行驶线路重合时，网络图上的点在两个方向上各有一条出边和入边;当两个方向的行驶线路不重合时，网络图上的点在每个方向上只有一条出边或入边。如果一个点是多条公交线路的交汇点，则该点处的边数等于各条公交线路在该点处的出边和入边之和。 部分公交线路的网络拓扑图 在拓扑模型的边上增加距离权值就可实现距离最优搜索;在模型上增加边的速度权 值(道路的通畅性权值)可实现不考虑换车时间的时间最优搜索。但是实际上，在换车时 需要等下一路车，甚至在两路公交线路的站点间步行，是耗时的事情。换车耗时是通勤 中影响时间最优的主要因素，因而要在拓扑网络和搜索算法中进行模拟。在拓扑网络中 换车代价可以用节点带权来模拟。在最短路径搜索时，如果一条路径在某节点上的出边 和入边的属性发生了改变(即实际交通中的换车)，就增加合理的权值来衡量换车耗时。 另外，换车是影响路径便捷性的因素，因而在节点权值上还需增加一个惩罚性的量来抑 制换车。在同一节点处由于公交线路的不同，实际换车站点可能是重合站点、紧邻站点 或近邻站点，因而用节点权函数设置不同的权值来模拟实际情况。我们设节点的权函数 f的表达式如下: f(ei，ej)=A(dij)+B(dij) dij=0，l，2 式中ei，ej分别表不一条路径在该节点上的出边和入边的属性;uij是这两条边代表的 公交线路在该节点上站点间的相邻距离判别值，根据站点重合、近邻、紧邻分别取O，1，2; A(aij)为换车时间消耗权值;B(d，j)为惩罚性量。 如果在一个节点处所历经的出边和入边属性相同(同一公交线路)，表示没有换车， 权值取0。 4.1.3算法设计 1、一次换乘算法设计 假设a为经过起点