城市公交网络出行路径选择的计算机算法研究.doc

城市公交网络出行路径选择的计算机算法研究公共交通信息系统是任何一个城市不可缺少的重要交通工具，它为各种交通信息的查询、统计提供方便直观的手段,为市民的出行提供了方便。公共交通信息系统最重要的一个功能是在乘客给出起迄点后,自动生成最优的出行路径方案供乘客选择. 城市公交网络出行路径选择的算法实质是寻找乘客的出行在公交网或道路网上分布的规律.研究和建立更接近现实的计算机算法,有利于得到更合理的公交客流分配结果.1公交乘客出行心理研究在研究公交网络最优路径算法时,首先要过对公交乘客的出行心理、行为进行调查研究,确定计算计算法的优化目标和约束条件。通常乘客选择出行路线时受到以下几个因素的作用:“换乘次数”、“出行距离”、“出行耗时”、“出行费用”。这几个出行因素是相互影响的,如换乘次数和出行费用就是相关联的。本文参照了在南京市做的一个公交乘客出行心理调查统计结果，如下表1所示。表1市公交乘客出行路径选择因素调查表出行选择因素所占比例（%）换乘最少41.16耗时最少30.93距离最短18.60其他9.30它主要对三个因素做了调查:换乘次数、出行距离、出行耗时。调查结果表明“换乘次数”是大部分公交乘客在选择出行路径时首要考虑的因素，其次考虑时间最短。本算法选用“换乘次数最少”作为优化目标。2城市公交网络的特点城市中公交汽车沿着道路运行, 公交网络不同于一般的道路交通网络，它有自身的一些特点。2.1连通性在道路网络计算算法中,一般将道路交叉点理解成单个结点,该结点连接着多条路段,路段与路段之间在该结点处具有连通性。但是在公交网络中,如果将公交站点视为结点的话, 多条公交线路可以交于空间上的同一结点，但是该结点不一定是公交停靠站点，也就是说在道路网上连通的两结点，在公交网上不一定连通。城市公交网络中结点的连通状态有：同路公交路段的连通；不同公交线路路段在同一点的连通；不同公交线路路段在不同点的连通。2.2结点性质在公交线路网中,不同的公交线路各自的站点不可能是完全的几何重叠。如果将一个公交站点视为一个结点, 在进行公共交通网络网络叠加分析时,要把实际上存在的异线同名站点合理抽象成同一个结点。要把实际上存在的相近的异线站点合理抽象成图上的相关节点，只有对公交网络进行了合理的图上抽象，才能进行模拟不同公交线之间的可换车情况。2.3有向线性质实际存在的公交线路是有方向性的，不同的公交线路具有不同的行驶路径和方向，甚至有的同一路线，其上、下行车路线也不尽相同。这些差异只有在有向线中才能体现，所以在公交网络中，应引入有向线路集。3公交网络最短路径常用算法比较当人们出行时,考虑到各方面的因素,人们对路径选择的标准也各不相同，但是主要以换乘次数最少为主要目标，算法主要有以下几种：3.1传统的Dijkstra最优路径算法Dijkstra最短路径算法由于其稳定性、能适应网络拓扑的变化,因而在计算机网络拓扑路径选择以及GIS中得到广泛的应用。但是传统的Dijkstra算法并不适合公交线路查询。数据结构复杂，采用现有的最短路径算法分析,所建立的公交线路网络图的数据结构计算计算法将是非常复杂的；算法时间长，Dijkstra算法工作时每次都要遍历与当前结点连通的所有结点，如果遇到大计算量的问题，系统的运算效率会有明显下降；查询结果不一定合理，采用Dijkstra算法,它会搜索两个结点之间存在的边,所计算出来的最短结果可能需要转乘好几次车才能到达。从前面的公交乘客出行心理研究报告中可以看到,换乘次数少才是乘客出行时考虑的首要因素。3.2改进的Dijkstra算法可以借助于最小换乘次数矩阵,求出基于换乘次数最少的最短路径,但Dijkstra最短路径算法要求网络拓扑图简洁,对于复杂的公交网络拓扑,必须对其进行复杂的抽象合并成简捷的网络拓扑图,这无疑增加了程序的复杂性。3.3广度优先搜索算法该算法求出出行选择方案的过程中搜索了大量不合理的出行路径, 容易产生维数爆炸或不方便管理维护数据，增加了算法不必要的执行次数，难以应用于大规模的实际公交网。4基于GIS的公交乘客出行路径选择算法该算法以Dijkstra算法为基础建立模型,并吸收Moore-pape算法链表管理技术的优点,建立起适合GIS网络的公交出行最优路径选择的计算计算法.具体算法思路如下表2算法步骤一览表所示。表2 算法步骤一览表算法步骤算法内容1初始化.根据给定的起点r和终点s的坐标,利用GIS的地理函数找出r和s周围一定范围内的公交节点集合S和D.将S放入链表T中,并置其lj值(jT)为r点到j点的距离;将D中节点的ei值赋为True;并令所有节点的ni和pi值为0,fi的值为False;将N和L也置为0.2找出链表T中公交权值最小的节点i(首先考虑ni,在ni值相同的情况下,再比较li值的大小),将其ni值和li值分别赋给N和L,并将i从链表T中删除.3如果节点i的ei值为True,则结束运算,输出结果,否则执行步骤44以节点i为搜寻基点,通过地理函数搜寻其相邻节点j,相邻节点分为2种情况:一种是直接与i相连的节点,即i的上一站或下一站;另一种是不与i直接相连的节点,即是从该点步行一定距离即可到达的节点,将后一种节点的fj值设为True,并设2点之间的步行换乘距离为Wij,然后对找到的相邻节点权值进行修正.具体修正方法见图1.nj值则视该点的公交线路与到达基点时的线路是否一致,若一致,则令nj= N,否则令nj= N+1.估价中间节点方向有效性是为了避免在无效方向上大量搜索.文献2提出了用GIS方向估价函数改进搜索策略,此方法同样适用于公交网络.网络搜索过程中,定义沿着起点r到终点s的方向为空间有效方向,相反的方向为空间无效方向.实际应用中,可能会出现有效方向上的路径不能被采用,而必须在无效方向上的一定距离内采用某些路径.设向量p(j)表示中间节点j的位置,p(r)和p(s)分别表示起终点的位置,h(j) =p(j)-p(r)表示节点j相对起点的位置.以h(j)为估价函数,如果j点在无效方向上,而且h(j) p(r)-p(s)时,即停止该路径上的扩展搜索,从而可以大量减少无效搜索次数.u为可调节的系数,一般取0.5左右.5如果链表T非空,返回步骤,否则结束.算法的具体计算框图见图2.其中K：线路总数；Sk：公交节点总数；i,j：第i,j个节点; Bij：节点i,j之间距离；r：起点；ni：从起点r到节点i最少的换乘次数;li：从起点r到节点i的最短公交出行距离;pi：在最短路径上节点i的前一个节点;布尔值fi：从前一点沿最短路前进到该点的方式是否为步行方式,如果是步行方式,则fi的值为True,否则为False;ei值：节点i是否在终点周围,ei=True表示其在终点周围; N：当前换乘次数,L：当前出行距离.图 1权值修正方法在上述分析的基础上，结合乘客心理，提出了以“步行”、“换乘次数最少”、“所经过公交站点最少”相结合的算法标准。该算法利用GIS地理函数搜索节点的相邻节点，突破了邻接关系的束缚,使得步行换乘的搜索和计算成为可能。当乘客的换乘距离在300米之内时，考虑加入“步行分析”。该分析提供乘客在起点和终点之内可以选择的合适的路线，如果有合适的路线则建议乘客步行前往，为了满足乘客“换乘次数最少”的心理需求，通过“步行分析”确定换乘点离终点存在合适的步行路线时，也可以建议乘客步行。图 2算法流程图5结语现实中，城市公交道路网络是十分复杂的,仅仅依靠距离最短、出行时间最短或者换乘次数最少等单一因素来选择最佳出行路径，具有很大的局限性。GIS具有对空间信息的管理能力和生动形象的图形表现形式，结合人们积累的实际路径寻找知识和城市公共交通网络的独特性，开发适合现代交通发展需要的GIS具有鲜明的实际意义。参考文献：1王世祥，烧维亚.大中城市公交线路查询的数据结构及其算法的实现J，计算机系统应用，2007，16(9). 2黄正东.公交实体的详细表达及其在出行系统中的应用J.武汉大学学报(工学版)，2003，36(3):69-75.3伍雁鹏,彭小奇,杨恒伏.改进的基于关系数据库技术的公交查询算法J.中南大学学报:自然科学版, 2009,40 (3): 763-766.4何胜