摘  要： 人們?cè)谕獬鲞x擇交通路徑過(guò)程中，通常根據(jù)起點(diǎn)和終點(diǎn)找出可行的出行方案，但如果考慮中轉(zhuǎn)(無(wú)直達(dá)時(shí))條件，則需要從數(shù)據(jù)量巨大的關(guān)系數(shù)據(jù)庫(kù)中檢索出可行的方案。給出了一種基于關(guān)系數(shù)據(jù)的首尾協(xié)同分層結(jié)構(gòu)快速檢索算法，可以對(duì)多次中轉(zhuǎn)信息進(jìn)行查詢和匹配，從而快速得到可行的出行方案，滿足出行方案選擇的實(shí)際需要。
關(guān)鍵詞： 數(shù)據(jù)挖掘；關(guān)系數(shù)據(jù)庫(kù)；出行方案

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

    該模型主要包括以下幾個(gè)部分：(1)選用SQL Server存儲(chǔ)的交通數(shù)據(jù)及該模型中所產(chǎn)生的中間數(shù)據(jù)；(2)同時(shí)從起點(diǎn)(S)和終點(diǎn)(T)查詢中轉(zhuǎn)站信息，然后再對(duì)中轉(zhuǎn)站信息進(jìn)行匹配和查詢，直到找到可行出行方案；(3)比較給出可行出行方案。
    該模型的具體描述如下：
    (1)利用SQL Server建立包括交通信息表、臨時(shí)堆棧表、方案主表、方案子表和一些輔助臨時(shí)表等一系列的關(guān)系數(shù)據(jù)表。
    (2)從起點(diǎn)(S)開(kāi)始向前查詢出所有經(jīng)過(guò)起點(diǎn)的交通信息集合。設(shè)這些信息集合為S1且層次為1；再以S1為起點(diǎn)向前查詢經(jīng)過(guò)S1的所有交通信息集合(不含同種交通工具的重復(fù)信息)，設(shè)這些信息集合為S2且層次為2；則第i次搜索形成信息集合為Si且層次為i；經(jīng)過(guò)若干次搜索后可將以起點(diǎn)為出發(fā)點(diǎn)以終點(diǎn)為目的的整個(gè)交通數(shù)據(jù)搜索完畢。
    (3)從終點(diǎn)(T)開(kāi)始向后查詢出所有經(jīng)過(guò)終點(diǎn)的交通信息集合。設(shè)這些信息集合為T(mén)1且層次為1；再以T1為起點(diǎn)向前查詢出經(jīng)過(guò)T1的所有交通信息集合，設(shè)這些信息為T(mén)2且層次為2，則第j次搜索形成信息集合為T(mén)j且層次為j，經(jīng)過(guò)若干次搜索后可將以終點(diǎn)為出發(fā)點(diǎn)以起點(diǎn)為目的的整個(gè)交通數(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)車(chē)出行條件。
2 算法實(shí)現(xiàn)
    基于SQL Server的存儲(chǔ)平臺(tái)，設(shè)計(jì)了包含交通信息表(表2)、臨時(shí)堆棧表(表3)、方案主表、方案子表和一些輔助臨時(shí)表等用來(lái)存儲(chǔ)路徑選擇過(guò)程中所涉及的數(shù)據(jù)。其中交通信息表格用來(lái)存儲(chǔ)交通基礎(chǔ)信息，該表中包括車(chē)次/航班號(hào)、站點(diǎn)序號(hào)以及站點(diǎn)編號(hào)等字段。臨時(shí)堆棧表用來(lái)將每次查詢出的車(chē)次信息按層次保存。方案子表是出行方案的明細(xì)，同一方案而言，如果是直達(dá)的，則只有一條數(shù)據(jù)；如果是中轉(zhuǎn)的，則數(shù)據(jù)個(gè)數(shù)為中轉(zhuǎn)次數(shù)加1且數(shù)據(jù)為方案車(chē)次/航班的匯總信息。方案主表是方案子表明細(xì)的匯總，具體字段見(jiàn)表4。

3 應(yīng)用與結(jié)果分析
    首先，根據(jù)圖2和表1確定中轉(zhuǎn)車(chē)次數(shù)最少的方案，根據(jù)方案查詢出相應(yīng)的信息，并將信息保存到臨時(shí)堆棧表中(為解決同城多個(gè)站點(diǎn)中轉(zhuǎn)問(wèn)題，中轉(zhuǎn)時(shí)使用地點(diǎn)編號(hào)作為中轉(zhuǎn)條件)；然后，生成可行的出行方案并保存到臨時(shí)結(jié)果子表中；最后，對(duì)臨時(shí)結(jié)果子表進(jìn)行匯總并將結(jié)果保存到臨時(shí)結(jié)果主表中。
3.1 臨時(shí)堆棧表數(shù)據(jù)查詢
    臨時(shí)堆棧表的數(shù)據(jù)是分層的，其S1和S2層是從起點(diǎn)查詢的，T1和T2層是從終點(diǎn)查詢的。其對(duì)應(yīng)的表關(guān)聯(lián)如下：
    第一層：
    T_TRAFFIC_INFO T1，T_TRAFFIC_INFO T2 Where
    T2.F_NB_STATION_ID=(S) AND T1.F_VC_TRAIN_NO=
    T2.F_VC_TRAIN_NO AND T1.F_NB_SEQ_NO>T2.F_NB_SEQ_NO
    第二層：
    T_TRAFFIC_INFO T1，#T_STACK T2，T_TRAFFIC_INFO T3 WHERE
    T2.F_NB_LAY=1 And T2.F_NB_LOCATION_ID=
    T3.F_NB_LOCATION_ID And T1.F_VC_TRAIN_NO
    !=T2.F_VC_TRAIN_NO And T1.F_VC_TRAIN_NO=
    T3.F_VC_TRAIN_NO And T1.F_NB_SEQ_NO>T3.F_NB_SEQ_NO
    第三層:
    T_TRAFFIC_INFO T1，#T_STACK T2，T_TRAFFIC_INFO T3 WHERE T2.F_NB_LAY=4 And T2.F_NB_LOCATION_ID=
    T3.F_NB_LOCATION_ID And T1.F_VC_TRAIN_NO=T3.F_VC_TRAIN_NO And T1.F_NB_SEQ_NO<T3.F_NB_
SEQ_NO And T1.F_VC_TRAIN_NO!=T2.F_VC_TRAIN_NO
    第四層：
    T_TRAFFIC_INFO T1，T_TRAFFIC_INFO T2 Where
    T2.F_NB_STATION_ID=(T) AND T1.F_VC_TRAIN_NO=
    T2.F_VC_TRAIN_NO AND T1.F_NB_SEQ_NO<T2.F_NB_SEQ_NO
3.2 臨時(shí)結(jié)果子表查詢
    在臨時(shí)堆棧表數(shù)據(jù)的基礎(chǔ)上，根據(jù)表1所對(duì)應(yīng)中轉(zhuǎn)類(lèi)型的條件可直接獲得此中轉(zhuǎn)類(lèi)型的所有方案數(shù)；再將具體的方案信息保存到臨時(shí)結(jié)果表中(先保存到子表中，主表信息可根據(jù)子表的方案號(hào)進(jìn)行匯總得到)。
3.3 結(jié)果分析
    將起點(diǎn)、終點(diǎn)及其他參數(shù)作為存儲(chǔ)過(guò)程的入口參數(shù)，通過(guò)參數(shù)便可獲得相應(yīng)出行方案信息，同時(shí)可根據(jù)最優(yōu)策略對(duì)這些方案進(jìn)行排序，從而獲得出行者所需要的方案。
    本文討論了一種基于分層結(jié)構(gòu)首尾協(xié)同的出行路徑選擇模型，通過(guò)對(duì)中轉(zhuǎn)信息進(jìn)行快速檢索，并對(duì)相應(yīng)信息判斷是否匹配，以便找出相對(duì)優(yōu)化的出行路徑。但該算法僅適合起點(diǎn)(S)與終點(diǎn)(T)中都是有若干條線路途徑的地點(diǎn)。如果兩者中有一點(diǎn)是沒(méi)有任何線路經(jīng)過(guò)(即為孤點(diǎn))，文中算法對(duì)于出現(xiàn)孤點(diǎn)而無(wú)法實(shí)現(xiàn)中轉(zhuǎn)的情況尚未予以考慮。
參考文獻(xiàn)
[1] 李文勇，王煒，陳學(xué)武.公交出行路徑螞蟻算法[J].交通運(yùn)輸工程學(xué)報(bào)，2004，4(4):102-105.
[2] 張衛(wèi)華，陸化普，石琴.公交優(yōu)先的信號(hào)交叉口配時(shí)優(yōu)化方法[J].交通運(yùn)輸工程學(xué)報(bào)，2004，4(3):49-53.
[3] DZEROSKI S， LAVRAC N. Relational datamining[M]. Berlin: Sp ringer， 2001.
[4] 譚滿春，李丹丹.基于Vague集的公交出行路徑選擇[J].中國(guó)公路學(xué)報(bào)，2008(5):86-89.
[5] 楊新苗，馬文騰.基于GIS的公交乘客出行路徑選擇模型[J].東南大學(xué)學(xué)報(bào)自然科學(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ù)庫(kù)系統(tǒng)對(duì)半結(jié)構(gòu)化數(shù)據(jù)進(jìn)行近似查詢[J].中國(guó)科學(xué)與技術(shù)大學(xué)學(xué)報(bào)，2005，35(5)：674-682.