基于最少换乘路径选择算法的改进

摘要:最短路径是图论研究中一个最基本的算法问题,也是公交出行路线选择系统中的关键技术之一。通过分析研究目前比较流行的最短路径算法,根据人们选择出行路线的心理,提出以最少换乘为第一目标,最短路径为第二目标的思想,并以其作为基准点,对传统的广度优先搜索算法中存在的问题做出适当的改进。

关键词:最短路径;广度优先搜索算法;最少换乘

中图分类号:TP301文献标识码:A文章编号:1009-3044(2010)01-168-03

Improvements for Optimal Path Selection Algorithm with Minimum Transfer Times

JING Li-rong, MA Shang-cai, SHEN Liang

(Information Management,Shanxi University of Finance & Economics,Taiyuan 030006,China)

Abstract: The shortest path problem is a classic algorithm issue in Graph Theory study,and it is also one of the key technologies in Bus Travel Route Choice System.In this paper,by analyzing the shortest path algorithms which is an idea prevails currently and considering people's psychology when choosing travel routes,the minimum transfer times is regarded as the main principle and the shortest path followed is proposed.Based on the discussion above,appropriate improvements are made to the traditional Breadth First Search algorithm.

Key words: Shortest Path;Breadth First Search Algorithm;Minimum Transfer Times

城市道路交通网是城市的重要基础设施,它的运行直接影响着城市的规划、建设和管理。面对未来的城市,道路有效地运行,无疑是城市发展的一个重要方面。目前,解决交通拥挤的直接办法是提高路网的通行能力,增加公共交通运输能力提倡人们选择公共交通出行。但正因为路线的众多,给人们出行选择路线带来了一定的困扰。在综合考虑了时间,费用,距离的基础上,人们倾向于选择能花最少的时间,付最小的代价的路线作为出行路线。

目前,已经有许多的研究者在公交最优路径选择问题中做出了相关研究。王建林提出一种基于换乘次数最少的城市公交网络最优路径算法,文中充分考虑了乘客乘车时的心理因素,并指出换乘次数最少是乘客出行时考虑的首要因素[1];胡霍真等人将最短路径算法应用到公交车网络中,并通过实验验证该算法取了较好的查询结果[2];李洪波等人提出了一种动态优化的Floyd最短路径算法,提高了算法的运行效率[3]。

本文第二节简要介绍了几种比较著名的最短路径算法,并分析了其算法中所存在的问题。第三节中具体的描述了传统的广度优先搜索算法以及对公交车路线网的抽象。第四节给出了一种新的公交车路线网抽象模型和改进的广度优先搜索算法,经实例验证了该新模型以及改进算法的有效性。第五节总结全文。

1 最短路径算法综述

最短路径算法的研究,得到了国内外各个领域的高度重视。研究学者分别从不同的角度出发,提出了各种相关的知名算法,如Dijkstra算法、Floyd算法以及A*算法等,并且成功的应用于各个领域。

Dijkstra算法是由E.W.Dijkstra在1995年提出的[4]。它是一种基于贪婪搜索技术[5]的搜索算法。首先,它求出从起点到最接近起点的顶点之间的最短路径,然后求出到第二接近顶点间的最短路径,以此类推。推而广之,在第i次迭代开始以前,该算法已经确定了i-1条离起点最近顶点之间的最短路径。

Floyd算法是一种动态规划算法[3]。它从图的带权邻接矩阵A=[a(i,j)]n×n开始,按照公式(1)迭代,构造出矩阵D(1),D(2)……D(n-1),D(n)。其中D(0)=A=[a(i,j)]n×n,D(k)[i][j]是从vi到vj的中间顶点的序号不大于k的最短路径长度。矩阵D(n)的第i行第j列元素为从i号顶点到j号顶点的最短路径长度,D(n)为图的距离矩阵。

A*算法是目前最流行的启发式搜索算法(Heuristic Search)[6],也是一种静态路网中求解最短路最有效的方法。该算法的创新之处在于采用启发信息,其目的是估计待选的节点到目标节点间的距离,以使搜索算法优先考虑最有希望的节点,即使估价函数最小的节点[7]。定义节点n 的启发式估价函数f'(n)见公式(2)。其中,g(n)是从原点到当前节点n的实际代价,h'(n)是从当前节点n到目标节点的最小代价的估计函数,A*算法是搜索具有最小f'(n)的节点。

然而,上述讨论的最短路径算法并不适用于公交路线选择问题中。首先,根据统计数据表明[1],在选择出行路线时首先考虑换乘最少的乘客占有41.16%,而只有18.60%的乘客在选择出行路线时会考虑路径最短。其次,将最短路径算法应用在公交路线查询系统中会给系统带来不必要负担。如在Dijkstra算法中,Dijkstra要求的是一组路径,每条路径都从起点出发通向图中的一个不同顶点。由于公交路线中的站站分布较广,抽象为图式本身的数据结构比较庞大,无疑在查询的过程中会增加运算时间。而在A*算法中,h(n)的信息越多,它的计算量就越大,耗费的时间就越多。如果适当的减小h(n)的信息,即减小约束条件,算法的准确性就差。

综上所述,基于乘客的乘车的心理,最少换乘算法应运而生,本文称之为传统的广度优先搜索算法。

2 传统的广度优先搜索算法

在公交车路线网中,由于所有的站点都是通过公交路线相连的,故可以将公交车路线网抽象为一个无向的连通图[8]G(V,E),图中顶点V表示公交路线所经过的站点,E表示来两个站点之间有公交路线相连。如图1所示。

该算法的基本思路是:假设欲查找从起始站S出发到达终点站E的公交路线。

1) 查找站点S处所有的公交车号集合BUS(S)是否与站点E处所有的公交车号集合BUS(E)有交集,若有,则说明从S站到E站有直达的公交车。否则转步骤2)。

2) 查找经过S站所有的公交车沿路能转成的公交车号的集ALONG(BUS(S))是否与站点E处所有的公交车集合BUS(E)有交集。若有,则说明从S站能通过转车到达E站,否则重复2)直到找到有交集或转车次数达到2次为止。

3 基于广度优先搜索算法的改进

3.1 算法的主要思路

由于公交车路线的数据量比较庞大,传统的广度优先搜索算法将公交路线网抽象为无向连通图较为复杂。本文用无向带标签的图[7]G1=(V,E,L)来抽象整个公交车路线网。将公交车号集合抽象成顶点集V={v1,v2,…vn},vi表示某一条公交车路线。边集E={e1,e2,…en}表示来两个公交车之间的公共站点。标签集包括两个子集L=Lv∪Le,分别为:Lv={lv1,lv2,…lvn},Le={le1,le2,…Len}。改进后的公交路线网抽象模型如图2所示。

此外,传统的广度优先搜索算法在运行过程中产生大量的无效数据,使得算法对这些数据的重复操作,极大的影响了算法的效率。因此本文主要是针对以上问题做出相应的改进。

算法的步骤如下:

1)将乘客欲查找的起始站S作为树TS的根节点,终点站E作为树TE的根节点。

2)将经过起始站S与终点站E的所有公交车号分别作为这两棵树的子节点。

3)对TS和TE的子节点进行遍历查找,查找这两棵树的子节点中是否存在相同的公交车号,若不存在,则转步骤4),否则转步骤5)。

4)对TS和TE树的子节点交替构造新的子节点,即将当前节点中表示的公交车号沿路能转乘的车号作为其欲构造的子节点。在添加节点的过程中,若添加的节点与其上一层节点相同,则取消添加。转步骤(3)。

5)输出相应的公交车号即转乘路线。(考虑到实用性,规定转车上限为2次,因为超过一定的转车次数,人们会选择其他的方式出行。)

3.2算法的实现

由上所述,其算法伪代码实现如下:

算法1:改进的广度优先算法

If(S&E)

{

CreateTree(TS)

CreateTree(TE)

ExtendTree (TS);

ExtendTree (TE);

If(BFSearch(TS,1)∩BFSearch(TE,1)≠Φ)

Path=GetThePath(BFSearch(TS,1)∩BFSearch(TE,1),0)

Else

ExtendTree(TS);

If(BFSearch(TS,2)∩BFSearch(TE,1)≠Φ))

Path=GetThePath(BFSearch(TS,2)∩BFSearch(TE,1),1)

Else

ExtendTree(TE);

If(BFSearch(TS,2)∩BFSearch(TE,2)≠Φ)

Path=GetThePath(BFSearch(TS,2)∩BFSearch(TE,2),2)

Else

Return 0

}

算法2 构造子节点函数

ExtendTree(Tree T)

{

If(T)

{

While(Tchlid)

T=TChild;

While(Bi?Buses(Tdata))

{

If(Bi?Histroy)//History集合即父辈已插入的站点

Insert(Bi,T);

}

}

}

其中,CreateTree( )函树用来创建一个树,建立树的根节点。BFSearch(T,int i)表示对T树的第i层节点进行广度优先遍历搜索。GetThePath(T,int i)为输出路径函数。其中,T表示两棵中的公共子节点,i表示需要转乘的次数。Buses( )为当前站点表示的公交车沿路能转乘的公交车号集合。

3.3 实例分析

下面以实例具体说明该算法的求解过程。求从起始站“山西财经大学”(以S表示)到终点站“青年路口”(以E表示)的最优路径。

第一步,创建树TS和TE。

第二步,扩展TS树,此时,TS的叶子节点集BUS(S)={861,103,39,849,824,877,870,868}。同理,扩展TE树,TE的叶子节点集BUS(E)={1,3,6,10,25,611,618,808,838,848,859},

第三步,由于BUS(S)∩BUS(E)=Φ,不存在从S站点到E站点的直达路径,因此在以后的查询过程中可将BUS(S)集合中的数据视为无效的数据。

第四步,再次扩展TS树,将其叶子节点放入ALONG(BUS(S))集合,查看ALONG(BUS(S))与BUS(E)是否存在交集。比如在集合ALONG(BUS(S))中,“861”沿路能转乘的公交车号的集合为ALONG(BUS(861))={861,6,101,1,102,39,103,611,618, 808,824, 830, 831,836,838,840,848,849,868,870,877},从这个集合中可以看出此集合存在大量的无效数据,即{861,103, 39, 824, 849, 870, 877,868},使得算法在运行过程中重复这些数据进行扫描,影响算法执行的速度。故在创建树时有必要删除多余的节点。此时ALONG(BUS(861))={6,101,1,102,611,618,808,830,831,836,838,840,848}。由于ALONG(BUS(S))∩BUS(E)={1,6,611, 618,838, 808,848},因此乘客可以转乘此集合中的公交车到达终点站E。类似地,算法采用相同的方法对ALONG(BUS(S))集合中的数据进行迭代查找,直到找出所有通过转乘一次的公交路线。

第五步,输出公交车乘车路线,用户可以根据其所需求选择相应的路线。

4 小结

本文中所提出的公交车路线网络抽象模型能够有效地将复杂的公交车路线网络模型化,较之传统的抽象模型有较大的改进,减少了数据的存储量,提高了算法的查询速度。另外,通过将本文所提出的改进算法应用在公交路线查询系统中,验证了该算法可以有效的找出最少换乘路线,与传统的广度优先搜索算法相比,提高了算法运行的效率。

参考文献:

[1] 王建林.基于换乘次数最少的城市公交网络最优路径算法[J].经济地理,2005,25(5):673-676.

[2] 胡霍真,戴光明,李颖.公交车网络的最短路径算法及实现[J].微机发展,2005,15(9):21-22.

[3] 李洪波,王茂波.Floyd最短路径算法的动态优化[J].计算机工程与应用,2006,34:60-63.

[4] E.W.Dijkstra.A Note on Two Problems in Connexion with Graphs.Numerische Mathematik 1959,(1):269-271.

[5] Annny Levitin.Introduction to the Design and Analysis of Algorithms[M].2007.

[6] 张仁平,周庆忠,熊伟,等.A*算法改进算法及其应用[J].计算机系统应用,2009,(9):98-100.

[7] 王林,石金峰.智能交通系统中几种最短路径算法分析[J].交通科技与经济,2009,11(4):110-112.

[8] 常新功.基于混合进化的子结构发现[M].北京:国防工业出版社,2009.