基于最少换乘的公交最优路径算法的设计与实现

第!"卷第"#期$##%年"#月

武汉大学学报!信息科学版

&’()*+,-.*/01/2(3)*+,(/4-,’/-’(2567*/8/,9’3.,+:

;(<=!">(="#

?-+=$##%

收稿日期"$##%@#A @$##

项目来源"中国科学院知识创新工程重大资助项目$R d C a "@45@#"@#$%&国家重点基础研究发展规划资助项目$&$####A A H #$

%#文章编号""%A "@F F %#$$##%%"#@#H #B @#B 文献标志码"G

基于最少换乘的公交最优路径算法的设计与实现

廖楚江"!蔡忠亮$!杜清运$!王长耀"

$"!中国科学院遥感应用研究所遥感科学国家重点实验室’北京市大屯路!号’"##"#"

%$$!武汉大学资源与环境科学学院’武汉市珞喻路"$H 号’B !##A H

%摘!要"提出了基于最少换乘的公交最优路径理论’在此基础上设计了公交最少换乘的算法#由于算法本身的独特性’笔者将(图算法)部署到空间网络数据库中加以实现’利用数据库的快速查询*索引支持和在集合运算方面的优秀性能解决了算法的效率问题#同时还利用此类数据库系统对空间查询的支持’确保算法在求取最少换乘后可以兼顾距离最短的要求#关键词"空间网络数据库&最少换乘&最优路径中图法分类号"I $#F

!!城市公交系统是与城市居民日常生活联系最

为紧密的环节之一’甚至在一定程度上决定着城市居民的生活方式’因而’时下众多城市的电子地图产品都把实现公交网络最优路径查询作为其重中之重’以期使电子地图能够更好地满足用户的需求’但其离最优还有很大的差距#笔者经过调查研究发现’存在这一差距的主要原因是电子地图软件的开发者与用户双方对公交最优路径的理解有着明显的分歧#一方面’

软件开发者认为’公交网络最优路径分析同其他网络分析一样’也应

该是以最短为基础的+"’$,&另一方面’多数用户认

为’最少换乘才是关键问题#这两者看似统一’但其实不然’

因为绝大多数城市公交网络中的站点是依据客流量的大小而设计的’还有一些是源于政治和历史的原因而形成的’因而即使把最短路径求得再快再好’

建立于其上的最优乘车方案往往会为达到最短而增加换车次数#

当然’不排除一些最短路径虽然换乘次数较多’但由于中途等待的时间很短反而能更快地到达的情况’因而笔者在最后的系统中仍然保留了这一传统模式的实现’以便用户可以在两种模式之间进行选择#本文主要就基于最少换乘的最优路径展开讨论#

$!基于最少换乘的最优路径算法思

想

!!算法的基本思想如图"所示’

在查询从站点"到站点$的最优路径的过程中’

首先看二者之间是否可以直达’如果是’则直接进入最后一步’按照路线距离进行排序’给出其中最短的几条线路供用户选择&如果不是’则查询站点"所能直达的所有站点和能直达站点$的所有站点’对这两个集合求取交集’如果存在交集’则结束迭代’进入最后一步按路线总距离进行排序’否则’仍然继续迭代’求取从站点"必须经过"次换乘才能够到达的站点集合$涉及集合差与并%’与能够直达$的所有站点集合求交’

从而得到必须换乘两次才能到达的乘车方案#交集非空’则结束迭代’进入最后一步&否则’继续迭代’直到找到乘车方案为止#

显然’这一基于(图论)的算法包含了众多的集合运算#对该算法的实现有两种途径可供选择’一是采用主存数据结构’实现集合的快速运算’其中包括快速查找*索引支持以及集合运算等一系列算法&二是直接利用现存商业数据库已有的在集合运算方面的优秀性能#对于前者’笔者

!第!"卷第"#期廖楚江等!基于最少换乘的公交最优路径算法的设计与实现

曾经采用基于4E P"标准模板库#的算法予以了实现$在为这个算法作进一步改进的过程中%笔者尝试了第二种选择%结果表明%其在武汉公交网络查询系统中的效率和稳定性明显更进了一步$

图"!算法思想

^,X="!10’*(2G

%!空间网络数据库逻辑结构

公交网络图的逻辑结构如图$所示%它主要由三个表组成%分别为Q(6+’表&4+(J表和Q(6+@’4+(J表$在Q(6+’表中%除了传统关系数据库中常见的头两个字段外%还增加了47*J’字段%其中%P,/’.+3,/X对象类型定义如下’!(!

C Q

D G

E DE f I DP,/’.+3,/X G4?Z\D C E"

>6)＿(2＿I(,/+.1>E%

!!&’()’+3:P,/’E:J’%

T D T Z D Q^8>C E1?>P’/X+7X’+＿G J J(,/+’0I*3@ +Q(6+’P’/X+7"<(/X>8T Z D Q%

I Q G&TG Q D4E Q1C E＿Q D^D Q D>C D4"P’/X+7%

5>L4##)

由此可以计算指定的两个站点之间的距离$所有线路站点的对应关系在Q(6+’4+(J中进行了实体化%Q*/S字段为站点在路线中所处的位置$如可以用如下查询得到从广埠屯能够直达的所有车站!

4D P D C EL14E1>C E"4$=>*)’#

^Q?T Q(6+’4+(J Q"%Q(6+’4+(J Q$%4+(J4"%4+(J 4$

5c D Q DQ"=Q(6+’1L U Q$=Q(6+’1L G>L

Q"=4+(J1L U4$=4+(J1L G>L

Q$=4+(J1L U4$=4+(J1L G>L

4"=>*)’U*广埠屯+G>L

Q"=4+(J1L("Q$=4+(J1L

+!算法设计

上文提到%整个最少换乘算法的思想是一个迭代的过程%从搜索经过起点站的线路开始%由线路查找该线路经过的所有站点%再从这些站点查找经过它们的所有线路%不断迭代%直至找到终点站为止$在具体实现中%可把它演变成一个双向的过程%即从起点站和终点站同时进行搜索%直到

图$!公交网络图逻辑结构

^,X=$!P(X,-4+36-+63’(2I6W<,-E3*22,->’+](3S

N # H

武汉大学学报!信息科学版$##%年"#月

找到两者相交的站点为止"再从这些线路中寻求最短和最优的线路#下面是算法的伪语言描述#

I6W<,-4’*-7I*+7$%

&

线路集P,/’4’+"U D M’-6+’e6’3:$起点站所经过的所有线路%’

从出发点能够直达的站点集4+(J I(,/+4’+"U8/,(/ $P,/’4’+"中的所有能达站点%’

线路集合P,/’4’+$U D M’-6+’e6’3:$经过终点站的所有线路%’

能够到达终点站的所有站点集4+(J I(,/+$U8/,(/ $P,/’4’+$中的所有能达站点%’

;’-+(3(4+(J I(,/+4’+"4+(J I(,/+4’+;’-+(3’

4+(J I(,/+4’+;’-+(3=J6.7＿W*-S$4+(J I(,/+4’+"%’

]7,<’$1/+’3.’-+,(/$4+(J I(,/+$"4+(J I(,/+4’+"%U U>8P P%

&

!P,/’4’+!U D M’-6+’e6’3:$经过4+(J I(,/+4’+"中每个站点的所有线路%’

!该线路集所能到达的站点集4+(J I(,/+4’+!U 8/,(/$P,/’4’+!中的所有能达站点%’

!2(3$,/+-U#’-(4+(J I(,/+4’+;’-+(3=.,b’$%’-[[%

!&

!!从出发点必须经-["次换乘方能到达的站点集合4+(J I(,/+4’+B U0,22’3’/-’$4+(J I(,/+4’+!"4+(J I(,/+@ 4’+;’-+(3=*+$-%%’

!(

!4+(J I(,/+4’+"U4+(J I(,/+4’+B’

!4+(J I(,/+4’+;’-+(3=J6.7＿W*-S$4+(J I(,/+4’+B%’

(

最后一次换乘站点集合P*.+4+(J I(,/+4’+U1/+’3@ .’-+,(/$4+(J I(,/+$"4+(J I(,/+4’+"%’

J*+7U&,9’Z,3+7?J+,(/*

4(3+$所有结果%U最短路径

(

在代码中"0,22’3’/-’)6/,(/和,/+’3.’-+,(/都是关系代数中的基本运算"可以用4e P查询来实现#从整个步骤看来"算法蕴涵着相当庞大的运算量"其中对于一次换乘"其时间复杂度就已经是?$=$%"如果采用常规的主存数据结构"实现起来将非常困难#笔者曾经通过基于4E P的数据结构对该算法进行了实现"但在实际运行过程中"仍然无法满足需求#本文利用数据库本身在空间查询)索引支持和集合运算上的优秀性能"使得这一算法最终得到有效实现的同时"更大程度地满足了需求#以武汉市为例"它共有%"$个交通站点"B%$条公交线路$据$##!年统计%"从中查询

需两次换乘才能到达的站点间的乘车方案"最多仅耗时%.#

*!公交网络查询系统应用实例

本算法是隶属于*武汉交通网络查询系统+的一个子任务"目前该系统为第二版#在原来的版本中"由于开发周期非常短"笔者直接在网络版系统中调用了原来为单机版开发的组件"在组件的实现中采用的是基于4E P的数据结构和算法"一定程度上保证了公交换乘查询在网络上的运行效率"在实际运行中也取得了比较好的效果#但在第二版中"由于后台支持的数据库由原来的G-@ -’..变成了?3*-<’"从而为空间数据的存储和查询创造了条件#因此"笔者在这个版本中改用基于数据库结构的算法设计"剔除了原来系统中的非\*9*部分#实践证明"新的系统无论在稳定性还是在效率上"都较前一版本有了很大的改观#图!为该网络查询系统窄带版的界面"查询从位于武昌高校中心的广埠屯到位于汉口的宗关长途汽车站的乘车方案#从图!可以看出"在两站点之间可以乘坐F#%路车直达"就公交网络的规划设计而言"理论上"这两个站点应该是直达的"但如果采用基于最短路径的查询"如图B所示"为了尽量走直线"提供的查询方案显示"必须换乘一次才能到达#对比两图的线路可以发现"后者只是在武胜路附近走了一个直线"距离显示仅少走了B F#)#

为测试算法效率"笔者选择相距较远的两个站点进行查询"查询从位于武昌东部的,关山口-到位于汉口北部的,堤角边-的最优路径$图N%"结果表明"该查询耗时仅为N.$算法效率与带宽无关%"只用一次换乘即可实现#同时"方案的选择也非常多样"与实际情况中绝大多数人的乘车思路完全吻合"相对于同类公交查询系统"其无论是从效率上还是稳定性上"都要优秀得多#

Q!结!语

本文提出的基于最少换乘的最优路径思想"是将,图算法-部署到空间网络数据库中加以实现"利用数据库在空间查询)索引和集合运算方面的优秀性能来达到目的"从而减小了系统维护的难度"缩短了系统的开发周期"并为今后,图算法-的实现开辟了一个新的途径#当然"就算法的设计而言"很多附加因素"如路面情况)车速)气候条

% # H

!第!

"卷第"#期廖楚江等!基于最少换乘的公交最优路径算法的设计与实现

件等由于数据的实时获取比较困难"本文没有纳入到考虑范围中来#另外"就算法的实现而言"可

以通过层次策略来减少1$?代价和主存缓冲的需求量"从而满足更大数据量的要求#

图!!最优换乘查询"

^,X =!!e 6’3:(2Z ’.+E 3*/.2’3"!图B !最短路径查询^,X =B !e 6’3:(2?J +,)6)I *+7!

图N !最优换乘查询$

^,X =N !e 6’3:(2D 22,-,’/-:E

’.+$参!考!文!献

%"&!T (7*))*0Q R "C :

36.4c=C (/+,/6(6.U >’*@3’.+>’,X 7W (63e 6’3,’.,/4J *+,*<>’+](3SL *+*W *.@’.%C &=4E L Z T "E (3(/+("C */*0*"$##B

%$&!乐阳=L ,‘

S .+3*最短路径算法的一种高效率实现%\&=武汉测绘科技大学学报""H H H "$B ’!(!$#H @$"$%!&!T ,-7*’

635(3<0%T &=Q ’0<*/0.!D 4Q 1I 3’.."$##$

%B &!4

7’S 7*344"C 7*]<*4=空间数据库%T &=谢昆青译=北京!机械工业出版社"$##B

第一作者简介!廖楚江"博士生#主要从事交通信息系统)组件&14以及电子地图的网络服务方面的研究#D @)*,

$:*7((=-()=-/D 7>:03G :146]1;67378!/=46.C 01886."F

;6?14!1;@H 15:>73V :15;C 01358:05

0J 7?W 29.-4=>"!W 7J&2:=>A -4=>$!,6L -=>*9=$!X78CW 24=>*

4:"

’"!4+*+’R ’:P *W (3*+(3:(2Q ’)(+’4’/.,/X 4-,’/-’"1/.+,+6+’(2Q ’)(+’4’/.,/X G J J

<,-*+,(/."C 7,/’.’G -*0’):(24-,’/-’."!L *+6/Q (*0"Z ’,‘,/X "

##"#""C 7,/*(’$!4-7((<(2Q ’.(63-’*/0D /9,3(/)’/+4-,’/-’"567*/8/,9’3.,+:""$HP 6(:

6Q (*0"567*/B !##A H "C 7,/*(-=5;01.;!E 7’+7’(3:(2+7’(J +,)6)_6’3:(2J 6W <,-+3*/.J

(3+*+,(/W *.’0(/+7’<’*.++3*/.@2’3.,.J 6+2(3]*30"*/0+7’*

(3,+7),.+3,’0+(3’*<,b ’W *.’0(/+7’.J *+,*

7’<’*.++3*/.2’3.=A :2B

70>5!.J *+,*)79M 2@3204;&623*12?2680*7&6:)/

-C ;:)&?!2027＿3,22/

$A ),**-6*:-67A

#

H

基于最少换乘的公交最优路径算法的设计与实现

作者：廖楚江， 蔡忠亮， 杜清运， 王长耀， LIAO Chujiang， CAI Zhongliang， DU

Qingyun， WANG Changyao

作者单位：廖楚江,王长耀,LIAO Chujiang,WANG Changyao(中国科学院遥感应用研究所遥感科学国家重点实验室)， 蔡忠亮,杜清运,CAI Zhongliang,DU Qingyun(武汉大学资源与环境科

学学院,430079)

刊名：

武汉大学学报（信息科学版）

英文刊名：GEOMATICS AND INFORMATION SCIENCE OF WUNAN UNIVERSITY

年，卷(期)：2006，31(10)

被引用次数：7次

参考文献(4条)

1.Mohammad R K.Cyrus S H Continuous K Nearest Neighbour Queries in Spatial Network Databases 2004

2.乐阳.龚健雅Dijkstra最短路径算法的一种高效率实现[期刊论文]-武汉测绘科技大学学报 1999(03)

3.Michael Z Modeling Our World 2002

4.SHEKHAR S.CHAWLA S.谢昆青.马修军.杨冬青空间数据库 2004

引证文献(7条)

1.何昭青.张来希.卢琦基于最短道路的城市公交智能咨询系统的研究与实现[期刊论文]-计算技术与自动化2009(1)

2.樊晓春.张雪英.刘学军.申琪君.樊晓明一种公交换乘优化算法设计[期刊论文]-地球信息科学学报 2009(2)

3.郭甲.乔冠东.李丹基于SPFA算法的公交线路优化模型[期刊论文]-中国科技博览 2008(19)

4.杨金梁.翟泳.王颖.樊铭渠基子MapInfo的城市公交出行最优路线算法研究[期刊论文]-交通标准化 2008(8)

5.陈小宾.葛新伟.林鸿飞基于语义计算的公交移动问答系统[期刊论文]-计算机工程与科学 2008(10)

6.付月朋.严余松.朱仲忠基于SMS城市公交线路查询系统的设计与实现[期刊论文]-科技咨询导报 2007(27)

7.张素智.崔晓康.史培中基于MVC技术的公交查询系统设计与实现[期刊论文]-郑州轻工业学院学报（自然科学版） 2007(4)

本文链接：https://www.wendangku.net/doc/0f9997870.html,/Periodical_whchkjdxxb200610015.aspx

授权使用：湖南大学(hunandx)，授权号：f892152a-afd7-45ba-9b0e-9dff014a484f

下载时间：2010年9月28日