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

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

    該模型主要包括以下幾個部分：(1)選用SQL Server存儲的交通數(shù)據(jù)及該模型中所產(chǎn)生的中間數(shù)據(jù)；(2)同時從起點(S)和終點(T)查詢中轉(zhuǎn)站信息，然后再對中轉(zhuǎn)站信息進行匹配和查詢，直到找到可行出行方案；(3)比較給出可行出行方案。
    該模型的具體描述如下：
    (1)利用SQL Server建立包括交通信息表、臨時堆棧表、方案主表、方案子表和一些輔助臨時表等一系列的關(guān)系數(shù)據(jù)表。
    (2)從起點(S)開始向前查詢出所有經(jīng)過起點的交通信息集合。設(shè)這些信息集合為S1且層次為1；再以S1為起點向前查詢經(jīng)過S1的所有交通信息集合(不含同種交通工具的重復(fù)信息)，設(shè)這些信息集合為S2且層次為2；則第i次搜索形成信息集合為Si且層次為i；經(jīng)過若干次搜索后可將以起點為出發(fā)點以終點為目的的整個交通數(shù)據(jù)搜索完畢。
    (3)從終點(T)開始向后查詢出所有經(jīng)過終點的交通信息集合。設(shè)這些信息集合為T1且層次為1；再以T1為起點向前查詢出經(jīng)過T1的所有交通信息集合，設(shè)這些信息為T2且層次為2，則第j次搜索形成信息集合為Tj且層次為j，經(jīng)過若干次搜索后可將以終點為出發(fā)點以起點為目的的整個交通數(shù)據(jù)搜索完畢。
    (4)比較Si中任意中轉(zhuǎn)站集中任意和Tj中相同的中轉(zhuǎn)站，找到從起點到終點的出行可行方案?；诜謱咏Y(jié)構(gòu)首尾協(xié)同的兩次以內(nèi)中轉(zhuǎn)出行路徑查詢算法的流程圖如圖2所示。

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

3 應(yīng)用與結(jié)果分析
    首先，根據(jù)圖2和表1確定中轉(zhuǎn)車次數(shù)最少的方案，根據(jù)方案查詢出相應(yīng)的信息，并將信息保存到臨時堆棧表中(為解決同城多個站點中轉(zhuǎn)問題，中轉(zhuǎn)時使用地點編號作為中轉(zhuǎn)條件)；然后，生成可行的出行方案并保存到臨時結(jié)果子表中；最后，對臨時結(jié)果子表進行匯總并將結(jié)果保存到臨時結(jié)果主表中。
3.1 臨時堆棧表數(shù)據(jù)查詢
    臨時堆棧表的數(shù)據(jù)是分層的，其S1和S2層是從起點查詢的，T1和T2層是從終點查詢的。其對應(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 臨時結(jié)果子表查詢
    在臨時堆棧表數(shù)據(jù)的基礎(chǔ)上，根據(jù)表1所對應(yīng)中轉(zhuǎn)類型的條件可直接獲得此中轉(zhuǎn)類型的所有方案數(shù)；再將具體的方案信息保存到臨時結(jié)果表中(先保存到子表中，主表信息可根據(jù)子表的方案號進行匯總得到)。
3.3 結(jié)果分析
    將起點、終點及其他參數(shù)作為存儲過程的入口參數(shù)，通過參數(shù)便可獲得相應(yīng)出行方案信息，同時可根據(jù)最優(yōu)策略對這些方案進行排序，從而獲得出行者所需要的方案。
    本文討論了一種基于分層結(jié)構(gòu)首尾協(xié)同的出行路徑選擇模型，通過對中轉(zhuǎn)信息進行快速檢索，并對相應(yīng)信息判斷是否匹配，以便找出相對優(yōu)化的出行路徑。但該算法僅適合起點(S)與終點(T)中都是有若干條線路途徑的地點。如果兩者中有一點是沒有任何線路經(jīng)過(即為孤點)，文中算法對于出現(xiàn)孤點而無法實現(xiàn)中轉(zhuǎn)的情況尚未予以考慮。
參考文獻
[1] 李文勇，王煒，陳學(xué)武.公交出行路徑螞蟻算法[J].交通運輸工程學(xué)報，2004，4(4):102-105.
[2] 張衛(wèi)華，陸化普，石琴.公交優(yōu)先的信號交叉口配時優(yōu)化方法[J].交通運輸工程學(xué)報，2004，4(3):49-53.
[3] DZEROSKI S， LAVRAC N. Relational datamining[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].計算機應(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].中國科學(xué)與技術(shù)大學(xué)學(xué)報，2005，35(5)：674-682.