改进的基于关系数据库技术的公交查询算法
伍雁鹏1, 2，彭小奇2, 3，杨恒伏3
(1. 邵阳学院 信息工程系，湖南 邵阳，422000；
2. 中南大学 能源科学与工程学院，湖南 长沙，410083；
3. 湖南第一师范学院 信息技术系，湖南 长沙，410205)
摘 要：为满足公众对出行路径的多样性需求，针对目前公交查询算法的不足，提出改进的基于关系数据库技术的公交查询算法。该算法依据“最优路径的子路径都是最优路径”理论，通过换乘次数小的最优路径逐步求取换乘次数大的最优路径，并利用关系数据库技术进行最优路径集合的生成和优化，从而实现大规模公交网络的多目标路径搜索。以北京公汽网络作为算例，分别以最短出行时间、最小换乘次数、最少出行费用为评价标准编制程序搜索最优路径，结果表明最短出行时间算法的多目标搜索结果最优，查询速度快，具有推广价值。
关键词：公交网络；关系数据库；换乘；最优路径；路径查询
中图分类号：U491；U121 文献标识码：A 文章编号：1672-7207(2009)03-0763-04
Improved algorithm based on relational database technology for querying transit network
WU Yan-peng1, 2, PENG Xiao-qi2, 3, YANG Heng-fu3
(1. Department of Information Engineering, Shaoyang University, Shaoyang 422000, China;
2. School of Energy Science and Engineering, Central South University, Changsha 410083, China;
3. Department of Information Technology, Hunan First Normal University, Changsha 410205, China)
Abstract: Aiming at some shortcomings of existing algorithms, improved querying transit network algorithm based on relational database technology was proposed to meet people’s various demands of travel path. Based on the theory “all sub-paths of optimal path are optimal paths”, optimal paths were acquired step by step in accordance with transfer time from minimum to maximum, and optimal path sets were generated and optimized by use of relational database technology. This algorithm can be used to realize multi-objective path searching of large-scale transit network. Taking Beijing bus network as an example, programs were made with different assessing standard of minimum travel time, fewest transfer time, and least travel cost to search optimal paths. The results show that the algorithm of minimum travel time is optimal for multi-objective path searching, efficient in querying and valuable to apply.
Key words: public transit network; relational database; transfer; optimal path; path query
随着城市化进程的实施，城市公交网络变得越来越庞大和复杂，城市交通拥塞问题也变得越来越严重，公众想要选择1条满意的公交出行路径变得很困难。设计1种多目标公交查询算法，有利于公众出行[1]。同时，对公交查询结果的分析，有利于公交网络的优化和改进[2-4]。
城市公交查询算法主要分为3类：第1类是基于最短路径搜索技术(如Dijkstra算法、A*算法、Floyd算法等)的查询算法[5-9]，算法主要在内存中进行，查询速度快，缺点是不能解决换乘问题，应用推广价值较小；第2类是基于人工智能技术(如遗传算法、蚂蚁算法、禁忌算法等)的查询算法[10-12]，查询结果的精确度受算法的收敛速度影响，不能适用于大规模公交网络；第3类是基于数据库技术或集合运算的查询算 法[13-16]，可用于解决路径换乘问题。但由于受算法效率限制，对于大规模网络通常采用最小换乘路径搜索策略。为此，本文作者提出一种改进的基于关系数据库技术的公交查询算法，以实现大规模公交网络的多目标路径搜索。
1 公交网络模型
公交网络可表示成有向图的形式：G=(V, E, R)。其中：V为所有站点的集合；E为所有公交路段(边)的集合；R为有向线路的集合。
路径定义为：
，表示从站点v0乘线路r1至站点v1，再从站点v1换乘线路r2至站点v2，…，最后，从站点vk-1换乘线路rk至站点vk。
通常认为，影响人们选择公交出行路线的最重要因素依次为换乘次数、出行时间（包括候车时间和乘车时间）、出行费用。
2 改进的基于关系数据库技术的公交查询算法
2.1 基于关系数据库技术的公交查询算法思路
公交网络数据库的基础数据表有3张：ZD (站点表)，XL (线路表)和XLZD (线路站点表)。表1~2所示分别为XL和XLZD的表结构。
大多数基于关系数据库技术的公交网络查询算 法[15]由Dijkstra算法改进而来，寻径目标为最少换乘次数。算法的基本思路如下：
a. 计算终点站直达站点集合W0，若起点站在W0中，则程序结束；
表1 XL表结构
Table 1 Table structure of XL
表2 XLZD表结构
Table 2 Table structure of XLZD
b. 计算起始站直达站点集合S0，若
，则程序结束；
c. 计算起始站1次换乘可达站点集合S1，若
，则程序结束；
d. 重复步骤c，直到找到起始站k次换乘可达站点集合Wk，满足时，程序结束。
2.2 改进的基于关系数据库技术的公交查询算法思路
改进的基于关系数据库技术的公交查询算法依据“最优路径的子路径都是最优路径”理论[16]，使用换乘次数小的最优路径逐步求取换乘次数多的最优路径，并利用关系数据库技术进行最优路径集合的生成和优化，从而进行多目标路径搜索。算法基本思路如下：令最大换乘次数为k，定义最优路径表，即HC0(直达路径表)，HC1(1次换乘路径表)，…，HCk(k次换乘路径表)。最优路径表结构见表3。
表3 HCi表结构
Table 3 Table structure of HCi
利用关系数据库技术，用XLZD和XL连接可得到HC0，用HC0自连接可得到HC1，用HC0和HC1连接可得到HC2，…，用HC0和HC(k-1) 连接可得到HCk。
删除所有非最优路径的换乘路径表称为优化路径表，分别命名为HCT0，HCT1，…，HCTk。显然，具有相同换乘次数的换乘路径表和优化路径表的表结构相同。
使用优化路径表替代换乘路径表进行表连接运算，同样能得到优化路径表，但算法所需的时间需求和空间需求都会极大地降低，对大规模公交网络算法需求降低尤为明显。
最后，为加快查询速度，可汇总所有优化路径表生成HCR(最优路径表) 。HCR用于最优路径查询，表结构见表4。
表4 HCR表结构
Table 4 Table structure of HCR
最优路径的评价标准可以是最短出行时间，也可以是最小换乘次数，或者最少出行费用。若使用第1个评价标准，则本算法可用于搜索最短出行时间路径和最小换乘次数路径，若使用第3个评价标准，则可用于搜索最少出行费用路径和最小换乘次数路径。
2.3 以最短出行时间为评价标准的算法实现
以最短出行时间作为路径评价标准，设计改进的基于关系数据库技术的公交网络寻径算法，具体步骤如下：
a. 初始化ZD，XL和XLZD。估计需要计算的最大换乘次数，设为k。
b. 用XL表和XLZD生成HC0，计算出行时间cxsj和出行费用cxfy（见表4）。
c. 生成HCT0，置空值。将HC0按照zd0，zd1，cxsj从小到大排序，然后进行汇总，计算每一对站点的最短出行时间，将具有最短出行时间的记录复制到HCT0中。
d. 使用HCT0自连接生成HC1，对应的Sql操作为：
Select T1.zd0, T1.xl1, T1.zd1, T2.xl1 as xl2, T2.zd1 as zd2, T1.cxsj+T2.cxsj as SJ, T1.cxfy+T2.cxfy as cxfy From HCT0 T1，HCT0 T2 Where T1.zd1=T2.zd0 Order By zd0, zd2, sj Into Table HC1。
更改HC1的sj字段名称为cxsj。然后，使用HC1汇总生成HCT1，具体方法参考步骤c。
类似于计算HCT1的过程，计算出所有优化路径表。
e. 为所有优化路径表添加zdz字段和hccs字段。zdz字段赋值为优化路径的终点站号，hccs字段赋值为优化路径的换乘次数。
f. 将所有优化路径表的内容添加到最优路径表HCR(初始为空)中，按照zd0，zdz，cxsj，hccs，cxfy的升序进行排序，并建立索引。
3 实验结果
编制程序对算法进行测试，基本数据来源于2007年高教社杯全国大学生数学建模竞赛甲组B题“乘公交，看奥运”。应用本算法分别使用最短出行时间、最小换乘次数、最少出行费用为评价标准编制程序，然后依次对题中要求的6组出行线路进行最优路径搜索，结果见表5。
表5 3种不同算法对北京公汽网络最优路径查询结果
Table 5 Results of searching optimal path of Beijing bus network obtained by three different algorithms
从表5看出，最小换乘次数算法的搜索结果与最短出行时间算法相比差异较大，而与最少出行费用算法基本一致；使用最短出行时间算法可以搜索到包括最短出行时间路径、最小换乘次数路径和最少出行费用路径的HCR。
将HCR以中间件形式存放在内存中[16]。查询以上最优路径的时间均小于1 s，达到了实时查询的 标准。
4 结 论
a. 提出改进的基于关系数据库技术的公交查询算法用于多目标路径搜索。
b. 以出行时间最短为路径评价标准编制程序可以快速搜索到包括最短出行时间路径、最小换乘次数路径和最少出行费用路径的HCR。
c. 将HCR以中间件形式存放在内存中，实现了最优路径的快速查询。
参考文献：
[1] Diaz R B, Schneck D C. Bus rapid transit technologies in the American: An overview[J]. Transportation Research Record, 2000, 1731: 3-9.
[2] 戴 帅, 陈艳艳, 荣 建, 等. 公共交通系统的可靠度研究[J]. 北京工业大学学报, 2006, 32(9): 813-816.
DAI Shuai, CHEN Yan-yan, RONG Jian, et al. Study on system reliability of public transportation[J]. Journal of Beijing University of Technology, 2006, 32(9): 813-816.
[3] 李 彬, 杨 超, 杨佩昆. 公交最短路径算法与网络通达性指标的计算[J]. 同济大学学报, 1997, 25(6): 651-655.
LI Bin, YANG Chao, YANG Pei-kun. Algorithm to obtain the shortest bus route and the calculation of bus networks accessibility[J]. Journal of Tongji University, 1997, 25(6): 651-655.
[4] Hall R W. Route choice and advanced traveler information systems on a capacitated and dynamic network[J]. Transportation Research Part C: Emerging Technologies, 1996, 4(5): 289-306.
[5] 严寒冰, 刘迎春. 基于GIS的城市道路网最短路径算法探讨[J]. 计算机学报, 2000, 23(2): 210-215.
YAN Han-bing, LIU Ying-chun. A new algorithm for finding shortcut in a city’s road net based on GIS technology[J]. Chinese Journal of Computers, 2000, 23(2): 210-215.
[6] WU Qiu-jin, Hartley J. Using K-shortest paths algorithms to accommodate user preferences in the optimization of public transport travel[C]//The 8th International Conference on Applications of Advanced Technologies in Transportation Engineering. U.S: ASCE, 2004: 181-186.
[7] LIANG Dai. Fast shortest path algorithm for road network and implementation[J]. Carleton University School of Computer Science COMP 4905 Honours Project Fall Term, 2005.
[8] Anez J, Barra T, Perez B. Dual graph representation of transport networks[J]. Transportation Research Part B, 1996, 30(3): 209-216.
[9] 刘 韵, 何建农. 基于交通网络最短路径搜索的改进算法[J]. 计算机工程与应用, 2007(14): 220-222.
LIU Yun, HE Jian-nong. Improved algorithm about searching for shortest path over traffic network[J]. Computer Engineering and Applications, 2007(14): 220-222.
[10] Bielli M, Caramia M, Carotenuto P. Genetic algorithms in bus network optimization[J]. Transportation Research: Part C, 2002, 10(1): 19-34.
[11] 毕 军, 付梦印, 张宇河. 一种改进的蚁群算法求解最短路径问题[J]. 计算机工程与应用, 2003(3): 106-108.
BI Jun, FU Meng-yin, ZHANG Yu-he. An improved ant colony algorithm for the shortest path problem[J]. Computer Engineering and Applications, 2003(3): 106-108.
[12] 白子建, 赵淑芝, 田振中. 公共交通网络优化的禁忌算法设计与实现[J]. 吉林大学学报: 工学版, 2006, 36(3): 40-44.
BAI Zi-jian, ZHAO Shu-zhi, TIAN Zhen-zhong. Design and implementation of tabu search algorithm for optimizing transit network[J]. Journal of Jilin University: Engineering and Technology Edition, 2006, 36(3): 40-44.
[13] Choi K, Jan G W. Development of a transit network from a street map database with spatial analysis and dynamic segmentation[J]. Transportation Research Part C, 2000(8): 129-146.
[14] 王世祥, 饶维亚. 数据库系统中公交网络换乘线路的优化选择模型[J]. 计算机系统应用, 2008(4): 112-116.
WANG Shi-xiang, RAO Wei-ya. An optimized choosing model of bus-line changing in PTN in database system[J]. Computer Systems Applications, 2008(4): 112-116.
[15] 张晋伟, 邹 云. 公交网络最优线路查询模型及软件开发[J]. 交通运输工程与信息学报, 2008(4): 118-125.
ZHANG Jin-wei, ZOU Yun. Enquiry model of the optimization path search in transit network and its software development[J]. Journal of Transportation Engineering and Information, 2008(4): 118-125.
[16] 陈 昊, 宁红云. 基于集合运算的最短路径搜索算法[J]. 计算机工程, 2007, 33(20): 199-203.
CHEN Hao, NING Hong-yun. Shortest path searching algorithm based on set calculation[J]. Computer Engineering, 2007, 33(20): 199-203.
收稿日期：2008-12-20；修回日期：2009-03-15
基金项目：湖南省教育厅科研基金资助项目(08C790)；湖南省科技厅科技计划项目(2008FJ3089)
通信作者：伍雁鹏(1975-)，男，湖南邵阳人，博士研究生，从事计算机应用技术、能源动力工程的研究；电话：0739-6146197；E-mail: wuyanpeng@yahoo.com.cn
