一種基于關(guān)系數(shù)據(jù)庫的出行路徑快速檢索算法

劉 晟，汪長勤

(1.安徽大學(xué) 計(jì)算機(jī)教學(xué)部，安徽 合肥 230039；2.安徽大學(xué) 計(jì)算機(jī)學(xué)院，安徽 合肥 230039)

隨著交通運(yùn)輸和經(jīng)濟(jì)的發(fā)展，越來越多的出行者需要考慮合理地選擇出行方案。通常可供出行者選擇的出行方案比較多，如何為出行者快速提供到達(dá)目的地的可行性出行方案，是現(xiàn)今旅游、交通運(yùn)輸?shù)刃袠I(yè)迫切需要解決的實(shí)際問題，同時也是學(xué)者研究的熱點(diǎn)和難點(diǎn)之一[1-3]。為了解決交通出行問題，研究人員提出了出行路徑選擇模型與算法。出行選擇模型主要以換乘次數(shù)最少與出行距離最短為優(yōu)化目標(biāo)，其目的是尋找一條最優(yōu)路徑[4]。現(xiàn)有的出行路徑選擇模型多為基于“出行距離最短”或“出行耗時最少”的最短路模型，而楊新苗等人的研究結(jié)果表明“換乘次數(shù)”是大部分乘客在選擇出行方案時首先考慮的因素，“出行距離最短”為第二目標(biāo)[5]。而且出行選擇模型的求解思想是將多目標(biāo)規(guī)劃問題轉(zhuǎn)化為單目標(biāo)規(guī)劃問題，或者將多目標(biāo)問題轉(zhuǎn)化為有主次之分的多層單目標(biāo)規(guī)劃問題[6]。從理論上講，出行者的起點(diǎn)到終點(diǎn)的出行方案可多達(dá)數(shù)千甚至上萬條，而且可選擇的交通工具類型也是多源的。因此出行路徑選擇模型中所涉及的多源交通數(shù)據(jù)量較大且關(guān)系復(fù)雜，目前多選擇利用關(guān)系數(shù)據(jù)庫存儲出行路徑選擇模型中所涉及的交通基礎(chǔ)數(shù)據(jù)[6-8]。故對這些交通數(shù)據(jù)檢索并最終確定最優(yōu)的出行方案需要大量時間，而目前大多數(shù)的交通出行方案的查詢只是針對如飛機(jī)、火車或者汽車的這種單一的交通工具的點(diǎn)到點(diǎn)查詢。本文以關(guān)系數(shù)據(jù)庫SQL Server為存儲工具，采用基于分層結(jié)構(gòu)首尾協(xié)同的出行路徑模型進(jìn)行快速、準(zhǔn)確查詢出多種交通工具組合的出行方案。

1 路徑選擇模型

由于交通出行路徑查詢中涉及多源的交通數(shù)據(jù)較多，導(dǎo)致從出行者的起點(diǎn)到終點(diǎn)的出行方案很多。為了能夠快速準(zhǔn)確查詢出可行的出行方案，本文采用了基于分層結(jié)構(gòu)首尾協(xié)同的出行路徑模型來快速準(zhǔn)確查詢可行的出行路線。該模型的基本思想就是同時從起點(diǎn)(S)和終點(diǎn)(T)查詢中轉(zhuǎn)站信息，直到找到匹配的可行方案。這樣可以相對快速、準(zhǔn)確地查詢出多種交通工具組合的出行方案。該模型的出行方案查詢策略如圖1所示。

圖1 基于分層結(jié)構(gòu)首尾協(xié)同出行方案查詢策略圖

該模型主要包括以下幾個部分：(1)選用SQL Server存儲的交通數(shù)據(jù)及該模型中所產(chǎn)生的中間數(shù)據(jù)；(2)同時從起點(diǎn)(S)和終點(diǎn)(T)查詢中轉(zhuǎn)站信息，然后再對中轉(zhuǎn)站信息進(jìn)行匹配和查詢，直到找到可行出行方案；(3)比較給出可行出行方案。

該模型的具體描述如下：

(1)利用SQL Server建立包括交通信息表、臨時堆棧表、方案主表、方案子表和一些輔助臨時表等一系列的關(guān)系數(shù)據(jù)表。

(2)從起點(diǎn)(S)開始向前查詢出所有經(jīng)過起點(diǎn)的交通信息集合。設(shè)這些信息集合為S1且層次為1；再以S1為起點(diǎn)向前查詢經(jīng)過S1的所有交通信息集合(不含同種交通工具的重復(fù)信息)，設(shè)這些信息集合為S2且層次為2；則第i次搜索形成信息集合為Si且層次為i；經(jīng)過若干次搜索后可將以起點(diǎn)為出發(fā)點(diǎn)以終點(diǎn)為目的的整個交通數(shù)據(jù)搜索完畢。

(3)從終點(diǎn)(T)開始向后查詢出所有經(jīng)過終點(diǎn)的交通信息集合。設(shè)這些信息集合為T1且層次為1；再以T1為起點(diǎn)向前查詢出經(jīng)過T1的所有交通信息集合，設(shè)這些信息為 T2且層次為2，則第j次搜索形成信息集合為 Tj且層次為j，經(jīng)過若干次搜索后可將以終點(diǎn)為出發(fā)點(diǎn)以起點(diǎn)為目的的整個交通數(shù)據(jù)搜索完畢。

(4)比較Si中任意中轉(zhuǎn)站集中任意和Tj中相同的中轉(zhuǎn)站，找到從起點(diǎn)到終點(diǎn)的出行可行方案。基于分層結(jié)構(gòu)首尾協(xié)同的兩次以內(nèi)中轉(zhuǎn)出行路徑查詢算法的流程圖如圖2所示。

由圖1可以得出如表1所示的直達(dá)、一次和二次轉(zhuǎn)車出行條件。

2 算法實(shí)現(xiàn)

基于SQL Server的存儲平臺，設(shè)計(jì)了包含交通信息表(表2)、臨時堆棧表(表 3)、方案主表、方案子表和一些輔助臨時表等用來存儲路徑選擇過程中所涉及的數(shù)據(jù)。其中交通信息表格用來存儲交通基礎(chǔ)信息，該表中包括車次/航班號、站點(diǎn)序號以及站點(diǎn)編號等字段。臨時堆棧表用來將每次查詢出的車次信息按層次保存。方案子表是出行方案的明細(xì)，同一方案而言，如果是直達(dá)的，則只有一條數(shù)據(jù)；如果是中轉(zhuǎn)的，則數(shù)據(jù)個數(shù)為中轉(zhuǎn)次數(shù)加1且數(shù)據(jù)為方案車次/航班的匯總信息。方案主表是方案子表明細(xì)的匯總，具體字段見表4。

圖2 方案查詢算法流程圖

表1 中轉(zhuǎn)類型及其條件

表2 交通信息表(T_TRAFFIC_INFO)

表3 臨時堆棧表(#T_STACK)

表4 臨時方案子表(#T_RESULTZB)

3 應(yīng)用與結(jié)果分析

首先，根據(jù)圖2和表1確定中轉(zhuǎn)車次數(shù)最少的方案，根據(jù)方案查詢出相應(yīng)的信息，并將信息保存到臨時堆棧表中(為解決同城多個站點(diǎn)中轉(zhuǎn)問題，中轉(zhuǎn)時使用地點(diǎn)編號作為中轉(zhuǎn)條件)；然后，生成可行的出行方案并保存到臨時結(jié)果子表中；最后，對臨時結(jié)果子表進(jìn)行匯總并將結(jié)果保存到臨時結(jié)果主表中。

3.1 臨時堆棧表數(shù)據(jù)查詢

臨時堆棧表的數(shù)據(jù)是分層的，其S1和S2層是從起點(diǎn)查詢的，T1和T2層是從終點(diǎn)查詢的。其對應(yīng)的表關(guān)聯(lián)如下：

第一層：

第二層：

第三層：

第四層：

3.2 臨時結(jié)果子表查詢

在臨時堆棧表數(shù)據(jù)的基礎(chǔ)上，根據(jù)表1所對應(yīng)中轉(zhuǎn)類型的條件可直接獲得此中轉(zhuǎn)類型的所有方案數(shù)；再將具體的方案信息保存到臨時結(jié)果表中(先保存到子表中，主表信息可根據(jù)子表的方案號進(jìn)行匯總得到)。

3.3 結(jié)果分析

將起點(diǎn)、終點(diǎn)及其他參數(shù)作為存儲過程的入口參數(shù)，通過參數(shù)便可獲得相應(yīng)出行方案信息，同時可根據(jù)最優(yōu)策略對這些方案進(jìn)行排序，從而獲得出行者所需要的方案。

本文討論了一種基于分層結(jié)構(gòu)首尾協(xié)同的出行路徑選擇模型，通過對中轉(zhuǎn)信息進(jìn)行快速檢索，并對相應(yīng)信息判斷是否匹配，以便找出相對優(yōu)化的出行路徑。但該算法僅適合起點(diǎn)(S)與終點(diǎn)(T)中都是有若干條線路途徑的地點(diǎn)。如果兩者中有一點(diǎn)是沒有任何線路經(jīng)過(即為孤點(diǎn))，文中算法對于出現(xiàn)孤點(diǎn)而無法實(shí)現(xiàn)中轉(zhuǎn)的情況尚未予以考慮。

[1]李文勇，王煒，陳學(xué)武.公交出行路徑螞蟻算法[J].交通運(yùn)輸工程學(xué)報，2004，4(4)：102-105.

[2]張衛(wèi)華，陸化普，石琴.公交優(yōu)先的信號交叉口配時優(yōu)化方法[J].交通運(yùn)輸工程學(xué)報，2004，4(3)：49-53.

[3]DZEROSKIS，LAVRAC N.Relationaldatamining[M].Berlin：Sp ringer， 2001.

[4]譚滿春，李丹丹.基于Vague集的公交出行路徑選擇[J].中 國 公 路 學(xué) 報 ，2008(5)：86-89.

[5]楊新苗，馬文騰.基于GIS的公交乘客出行路徑選擇模型[J].東南大學(xué)學(xué)報自然科學(xué)版，2000(6)：87-91.

[6]徐光美，楊炳需，張偉，等.多關(guān)系數(shù)據(jù)挖掘方法研究[J].計(jì)算機(jī)應(yīng)用研究，2006(9)：8-12.

[7]AGRAWAL R，SRIKANT R.Mining sequential patterns[C].Proceedings of the 11 th International Conference on Data Engineering， Los Alamitos：IEEE Computer Society Press，1995：3214.

[8]韓愷，岳麗華，龔育昌.利用關(guān)系數(shù)據(jù)庫系統(tǒng)對半結(jié)構(gòu)化數(shù)據(jù)進(jìn)行近似查詢[J].中國科學(xué)與技術(shù)大學(xué)學(xué)報，2005，35(5)：674-682.