胡必松

（中鐵第一勘察設(shè)計院集團(tuán)有限公司 線路運輸處，陜西 西安 710043）

0 引言

路徑搜索是進(jìn)行交通規(guī)劃、運量分配及編制列車開行方案研究工作的基礎(chǔ)，路徑搜索通常需要找出 1 個 OD 對間的多條徑路。目前我國既有鐵路網(wǎng)車站和區(qū)間數(shù)量超過 6 000 個，線路近 300 條，任意 2 個車站之間可能存在 2 條及以上的有向區(qū)間，繼而形成含有大量環(huán)和圈的復(fù)雜路網(wǎng)，其實質(zhì)為大規(guī)模多重邊有向網(wǎng)絡(luò)。截止 2014 年底，我國鐵路營業(yè)里程已經(jīng)達(dá)到 11.2 萬 km，其中高速鐵路 1.6 萬 km，未來鐵路網(wǎng)規(guī)模將進(jìn)一步擴(kuò)大。對于規(guī)模如此宏大的復(fù)雜網(wǎng)絡(luò)，在進(jìn)行運量分配時如果枚舉 OD 對中所有的路徑將非常困難。因此，一方面需要對網(wǎng)絡(luò)構(gòu)建、結(jié)構(gòu)存儲、路徑表達(dá)等進(jìn)行系統(tǒng)研究，以方便計算機(jī)編程實現(xiàn)；另一方面需要設(shè)計復(fù)雜度較低、簡便易行的算法，從而帶來如何在大規(guī)模復(fù)雜鐵路網(wǎng)中實現(xiàn)多路徑快速搜索的問題。

目前國內(nèi)外學(xué)者在網(wǎng)絡(luò)構(gòu)建、路徑求解等方面進(jìn)行了大量研究?？浊У萚1]、張羽成等[2]研究鐵路網(wǎng)絡(luò)結(jié)構(gòu)存儲及路徑構(gòu)造與分析方法；迪克斯特拉算法[3]給出 1 個頂點與圖中各個其他點相連的最短路徑；二重掃除算法[4]、Yen 算法[5]進(jìn)一步給出 1 個頂點與圖中各其他點相連的 K 條最短路徑，但只適用于簡單網(wǎng)絡(luò)，求解路徑可能存在環(huán)路問題；Macgeor M 等[6]給出接近最短路的簡單路徑的短路算法；王喆等[7]從遺傳學(xué)角度探討兩點間 K 條最優(yōu)路徑；李旭華等[8]采用分層思想對城市道路網(wǎng)節(jié)點進(jìn)行分級，并且進(jìn)行網(wǎng)絡(luò)求解；王明中等[9]、付夢印等[10]、榮瑋[11]主要從限制路徑的搜索區(qū)域?qū)β窂剿阉鬟M(jìn)行研究；胡必松[12]、柳健等[13]主要研究列車開行方案服務(wù)網(wǎng)絡(luò)中的有效路徑求解。

上述學(xué)者主要針對鐵路網(wǎng)網(wǎng)絡(luò)抽象、結(jié)構(gòu)存儲和路徑搜索等方面進(jìn)行研究，而以大規(guī)模復(fù)雜網(wǎng)絡(luò)為研究對象，對網(wǎng)絡(luò)構(gòu)建、路徑表達(dá)、結(jié)構(gòu)存儲、路徑求解算法等的綜合性系統(tǒng)研究還有待完善。在路徑求解算法方面，這些算法無法直接應(yīng)用于多重有向邊圖，并且不保證無環(huán)路；同時，算法時間復(fù)雜度較高，無法應(yīng)用于大規(guī)模復(fù)雜網(wǎng)絡(luò)。通過構(gòu)建鐵路網(wǎng)抽象網(wǎng)絡(luò)，采用分層思想進(jìn)行網(wǎng)絡(luò)簡化，設(shè)計路徑統(tǒng)一表示方法，采用橢圓算法限制路徑搜索范圍，基于動態(tài)規(guī)劃思想設(shè)計一種適應(yīng)多重有向邊復(fù)雜網(wǎng)絡(luò)、算法復(fù)雜度較低、無環(huán)路、易于計算機(jī)編程實現(xiàn)的路徑搜索技術(shù)。

1 鐵路網(wǎng)抽象網(wǎng)絡(luò)的構(gòu)建及簡化

1.1 鐵路網(wǎng)抽象網(wǎng)絡(luò)

鐵路網(wǎng)主要構(gòu)成元素為車站、區(qū)間、線路等信息，鐵路網(wǎng)運量分配時流量具有流向性，因而可以將鐵路網(wǎng)抽象成 1 張有向圖，有向圖節(jié)點為車站，邊為區(qū)間、樞紐內(nèi)聯(lián)絡(luò)線或換乘虛擬線。

設(shè) V = { vi| i 為車站序列號 } 為車站集；Eq={| i 為區(qū)間序列號 } 為區(qū)間集，El= {| i 為聯(lián)絡(luò)線序列號 } 為樞紐內(nèi)聯(lián)絡(luò)線集； Ex= {| i 為虛擬換乘線序列號 } 為樞紐內(nèi)車站的虛擬換乘線集合； E = { ei| i 為邊序列號 } 為邊集合，其中 Eq? E，El? E，Ex? E。

設(shè) c ( ei) 為邊的權(quán)值； l ( ei) 為邊所屬的線路 ( 當(dāng) ei∈ Ex時， l ( ei) 為空 )；L = { li| i 為線路序列號 } 為線路集合，三元組 G = ( V，E，R ) 為有向圖，其中 R = { ri| ri= ( vj，vk；el)，vj，vk∈ V，el∈ E}為 V 和 E 的連接關(guān)系集合，R 的存在條件為 V ∩ E=Φ，V ∪ E≠Φ并且 dom ( R ) ∪ cod ( R ) =V ∪ E ( 即圖中不能存在孤立元素 )，dom ( R ) = { vi，vj| ?ek使 ( vi，vj；ek) ∈ R } 和 cod ( R ) = { ei| ?vj，vk使 ( vj，vk；ei) ∈ R } 分別為 R 的定義域和值域。記連接關(guān)系 ri的起點、終點、所經(jīng)過的邊和權(quán)值分別為 q ( ri)， z ( ri)， e ( ri) 和 c ( ri)，其中 q ( ri) ∈ V，z ( ri) ∈ V，e ( ri) ∈ E。

1.2 鐵路網(wǎng)簡化

鐵路網(wǎng)簡化的目的在于方便計算機(jī)存儲，提高路徑搜索效率。為簡化網(wǎng)絡(luò)，對節(jié)點車站[14]進(jìn)行定義。節(jié)點車站為滿足以下 2 個條件之一的車站：①與該車站相連邊的數(shù)目大于 2；②該車站為線路起點站或終點站。通過采用分層思想簡化龐大的鐵路網(wǎng)，簡化形成的高層圖由節(jié)點車站及其連接關(guān)系構(gòu)成，低層圖由未簡化前的網(wǎng)絡(luò) ( 簡稱全路網(wǎng) ) 組成，路徑搜索算法僅在高層圖中計算，低層圖中車站路徑搜索通過相鄰高層圖節(jié)點車站導(dǎo)出。全路網(wǎng)簡化后，設(shè) V*= {| i 為節(jié)點車站序列號 } 為節(jié)點車站集，E*= {| i 為邊序列號 } 為節(jié)點車站形成的邊，R*為 V*和 E*的連接關(guān)系集合，簡化網(wǎng)記為 Gj= ( V*，E*，R*)。

1.3 路徑表達(dá)

由于路徑搜索首先需要在簡化網(wǎng)中搜索，然后從節(jié)點車站查詢起點 O 到終點 D 的路徑，從而涉及全路網(wǎng)和簡化網(wǎng)中的路徑轉(zhuǎn)換問題，需要進(jìn)行歸一化處理。

設(shè) aq= { ri，i 為序列號，1≤i≤n，n≥1|ri∈R}和 aj= {，i 為序列號，1≤i≤n，n≥1|∈R*} 分別為全路網(wǎng)和簡化網(wǎng)路徑，當(dāng) n＞1 時，q ( ri+1) = z ( ri)，q () = z ()，q ( ri) ≠ z ( rj)，q () ≠ z () (不允許出現(xiàn)環(huán)路)，記徑權(quán)值分別為c ( aq)，c ( aj)；路徑集合分別為 Aq和 Aj。

路徑歸一化處理如下。設(shè)關(guān)鍵線路點 linenode ( li) = ( on ( li)，li，off ( li) )，其中 ( on ( li)，off ( li) 分別為在某條線路 li上線、下線時的車站， 則路徑可以用關(guān)鍵線路點序列統(tǒng)一表示為 a ={linenode ( li)，i 為序列號，1≤i≤n，n≥1}，當(dāng)n＞1 時，on ( li+1) = off ( li)，on ( li) ≠ off ( li)，1≤i＜j≤n。當(dāng) li存在為空值時表示該路徑存在異站換乘的情況。

2 多路徑求解

2.1 限制路徑的搜索范圍

在橢圓算法[15]中，OD 間的路徑基本處于 OD 連線兩側(cè)或附近，其搜索區(qū)域大致為焦點分別是 O 和D 的橢圓范圍。橢圓算法可以大幅提高搜索效率，其搜索時間和規(guī)模僅為未作任何處理的 16.6 %和50 %，而準(zhǔn)確率則高達(dá) 99.8 %。在應(yīng)用橢圓算法限制路徑搜索范圍時，焦點分別為給定的起點車站和終點車站，長軸為兩車站最短路權(quán)重的 2～3 倍，在路徑搜索時舍棄橢圓范圍外的無效路徑，橢圓算法路徑搜索范圍圖如圖1 所示。

圖1 橢圓算法路徑搜索范圍圖

2.2 多路徑求解思路

多路徑求解共分為以下 3 步。①判斷起訖點是否為節(jié)點車站，如果否，找到其在簡化網(wǎng)中的最鄰接節(jié)點車站，并且記錄該段路徑 aq( 如果起訖點為節(jié)點車站，則 aq為空值 )；②在簡化網(wǎng)中，利用前K 條最短路徑求解算法按照距離、時間或費用最短求解 aj表示的 K 短路；③把 aq和 aj表示的路徑歸一化成 a。

利用動態(tài)規(guī)劃思想進(jìn)行簡化網(wǎng)中前 K 條最短路徑求解，先按照順序解法求解源點節(jié)點車站與所有節(jié)點車站的最短路徑；然后逆序解法從目的節(jié)點車站回溯至源點節(jié)點車站，根據(jù)回溯路徑相對最短路徑權(quán)值的增量保持升序排序，一旦回溯出前 K 條增量最小的路徑，即代表已經(jīng)求出 K 短路，回溯終止。

以有向多重邊圖求解 v0— v3的前 3 條最短路徑為例，采用動態(tài)規(guī)劃思想順序解法求出 v0至所有節(jié)點的最短路徑，粗線為 v0— v3的最短路徑，有向多重邊圖如圖2 所示。在圖2 中，括號中 3 個元素含義為 ( 該點至起點的最短路徑權(quán)值，該點所在最短路徑的上 1 個節(jié)點，從最短路徑上 1 個節(jié)點至該節(jié)點所經(jīng)過的有向邊 )。逆序解法從 v3反向回溯過程圖如圖3 所示，圈中括號內(nèi)的數(shù)字為從 v3回溯至當(dāng)前節(jié)點再經(jīng)最短路徑回溯至起點的最短路權(quán)值增量，每一步回溯后均保持升值排序，圖3 中從左至右按照其最短路權(quán)值增量排列，第 1 步沿 e6， e7， e5分別經(jīng) v1， v2， v1再經(jīng)最短路徑回溯至起點，3 條回溯路徑最短路權(quán)值增量分別為 0，1，2，其余回溯過程如圖3 第 2 步至第 7 步所示，圖中粗圈說明已經(jīng)回溯到起點。到第 4 步回溯時已經(jīng)得到所需要的前 3 條最短路徑，回溯即可終止，從而有效控制回溯范圍，提高路徑求解效率。

圖2 有向多重邊圖

圖3 前 K 條最短路輸出樹回溯過程圖

2.3 多路徑求解算法步驟

為便于簡化網(wǎng)路徑求解，降低算法復(fù)雜度，實現(xiàn)計算機(jī)系統(tǒng)開發(fā)。通過采用六元組數(shù)據(jù)結(jié)構(gòu)) 來存儲路徑信息，并且記 phypath 對象集合為 DicA，DicA 始終按照 w 值保持升值排序；記最短路徑集合為 DicM；前 K 條路徑集合為 DicK。

在順序解法求解起點至所有節(jié)點車站的最短路徑時，phypath 存儲數(shù)據(jù)分別為起點節(jié)點車站，當(dāng)前節(jié)點車站，最短路權(quán)值 w，最短路徑經(jīng)過的車站集合為，邊集合為、連接關(guān)系集合為。在回溯過程中，其存儲數(shù)據(jù)分別為起點節(jié)點車站，當(dāng)前回溯節(jié)點車站，當(dāng)前回溯路徑相對最短路權(quán)值增量 w，從目的車站回溯至經(jīng)過的車站集合、邊集合、連接關(guān)系集合。多路徑求解算法詳細(xì)步驟如下。

步驟 1： 新建 phypath 對象，phypath.=，phypath.=， phypath. w = 0，將加入到phypath 的集合元素中， phypath 的其余元素置空，將 phypath 加入到集合 DicA 中后轉(zhuǎn)步驟 2。

步驟 2： 取出集合 DicA 的首個對象 DicA [0]，遍歷D icA [0].q ( 的)所有 D連icA接 [關(guān)0]系.，如果D (icA [0].，并且 ? 的 防止回路和環(huán)路 )，新建 1 個 phypath 對象，記為 tempath，使tempath.=，tempath.= q ()，tempath. w =DicA [0]. w + d (，tempath.) + c () - d (，DicA [0].)，tempath.= DicA [0].+ q ()，tempath.= DicA [0].+ e ( )，tempath.=DicA [0].+然后轉(zhuǎn)步驟 3。

步驟 3： 對所有的 phypath 對象 tempath，如果tempath.，將 tempath 直接加到 DicA 集合的末尾，然后轉(zhuǎn)步驟 4。否則，更新 tempath 信息，使)，反轉(zhuǎn) tempath.，tempath.和tempath.后，將 tempath 加入到 DicK 集合中，轉(zhuǎn)步驟 4。

步驟 4： 當(dāng) DicK 集合對象數(shù)目為 K 時，輸出DicK，算法終止。否則轉(zhuǎn)步驟 5。

步驟 5： 刪除集合 DicA 中對象 DicA [0]，當(dāng)集合 DicA 中對象數(shù)目為 0 時，輸出 DicK，算法終止。否則對 DicA 中剩余路徑按照最短路權(quán)值增量升值排序后轉(zhuǎn)步驟 6。

2.3.3 路徑的歸一化

將 aq，aj的組合路徑統(tǒng)一轉(zhuǎn)換為 a。

步驟 1：將組合路徑加入到集合 SQ 中，并且記SQ 中第 i 個對象為 SQ [i]，轉(zhuǎn)步驟 2。

步驟 2：如果 m + n + k = 1，新建 1 個線路關(guān)鍵點對象 linenode ( ltemp) 加入到 a 中， 使 on ( ltemp) =q ( SQ [1] )，ltemp= l ( e ( SQ [1] ) )，off ( ltemp) =z ( SQ [1] )，之后輸出 a，算法終止。否則轉(zhuǎn)步驟 3。

步驟 3：遍歷集合 SQ，進(jìn)行以下處理。當(dāng) i = 1

時，新建 linenode ( ltemp)，使 on ( ltemp) = q ( SQ [ i ] )，ltemp= l ( e ( SQ [ i ] ) )，off ( ltemp) 置空，i = i + 1 繼續(xù)循環(huán)。當(dāng) 1＜i＜m + n + k －1，如果 ltemp= l ( e ( SQ [ i ] ) )，i = i + 1 繼續(xù)循環(huán)；否則如果 ltemp≠ l ( e ( SQ [ i ] ) )，即說明得到 1 個完整的線路關(guān)鍵點對象，補(bǔ)充 off ( ltemp) = q ( SQ [ i ] )，將 linenode ( ltemp) 加入到 a 中， 然后再新建 1 個 linenode ( ltemp)，使 on ( ltemp) = q ( SQ [ i ] )，ltemp= l ( e ( SQ [ i ] ) )，off ( ltemp) 置空，之后 i = i + 1 繼續(xù)循環(huán)。當(dāng) i = m + n + k 時，補(bǔ)充 off ( ltemp) = z ( SQ [ i ] )，將 linenode ( ltemp) 加入到 a 中，輸出 a，算法終止。

該路徑搜索技術(shù)采用動態(tài)規(guī)劃思想，一旦求出K 條最短路，即終止回溯過程，算法存儲結(jié)構(gòu)采用字典和數(shù)字進(jìn)行存儲，保持遞增有序。算法復(fù)雜度主要考慮以下 2 點。①字典插入排序。在算法第 2步第 1 階段中，字典最大長度為 n，完成 1 次插入排序的復(fù)雜度為 o ( lg n )，完成所有插入排序的復(fù)雜度為 o ( n lg n )。第 2 步第 2 階段中字典最大長度為 K，由于只考慮 K 條最短路徑，單次插入排序的復(fù)雜度為 o ( lg K )，最多插入 2 m 次，因而總復(fù)雜度為 o ( m lg K )。②權(quán)值兩兩比較。算法第 2 步第 1 階段中每個節(jié)點進(jìn)入字典 1 次，沿著每條邊進(jìn)行兩兩比較，總次數(shù)最多為 2 m，算法復(fù)雜度為 o ( m )；第 2 步第 2 階段由于不考慮環(huán)路，因而單個節(jié)點沿著每條邊回溯兩兩比較次數(shù)明顯小于 2 m，其算法復(fù)雜度最多也是 o ( m )；因而算法總時間復(fù)雜度為o ( m + nlg n + mlg K )，其中 m 為邊的個數(shù)，相比算法時間復(fù)雜度為 o ( Kn3)的迪克斯特拉、福勞德、Yen 及 A* 等常規(guī)算法，明顯降低算法時間復(fù)雜度。

2.4 算例分析

以全國 6 023 個車站、近 300 條線路、6 000 多個區(qū)間、520 × 520 個 OD 對的全路網(wǎng)進(jìn)行路徑搜索案例研究。該全路網(wǎng)為多重有向邊的大規(guī)模復(fù)雜網(wǎng)絡(luò)，流量分配時路徑搜索要求無環(huán)路，常規(guī)算法在適用性、求解規(guī)模和速度上均無法滿足要求。采用C#.NET 編程開發(fā)實現(xiàn)算法，測試結(jié)果如下。

（1）最短路求解。全路網(wǎng)簡化后，只有 500 個節(jié)點車站；當(dāng)求解 500 × 500 個 OD 對全部最短路徑時，算法執(zhí)行時間僅為 1 min56 s；當(dāng)求解 60 × 60 個OD 對，K = 30 的前 30 條最短路時，算法執(zhí)行時間僅為 18 s；單個 OD 對求解時間不到 20 ms。西安—北京的前 4 條時間最短路如表1 所示。

（2）實現(xiàn)條件。路網(wǎng)構(gòu)建、路徑搜索算法運行占用內(nèi)存約為 70 M，可以在一般配置的 PC 機(jī)上即能將該路徑搜索技術(shù)實現(xiàn)。

3 結(jié)束語

通過深入分析多重有向邊大規(guī)模復(fù)雜網(wǎng)絡(luò)中的路徑搜索技術(shù)，構(gòu)建鐵路網(wǎng)抽象網(wǎng)絡(luò)，采用分層思想進(jìn)行網(wǎng)絡(luò)簡化，給出路徑統(tǒng)一表示方法，采用橢圓算法限制路徑搜索范圍，最后給出無環(huán)路的前 K條最短路的有效算法，解決大規(guī)模復(fù)雜網(wǎng)絡(luò)中快速求解路徑的難題。該路徑搜索技術(shù)可以直接應(yīng)用于多重有向邊復(fù)雜網(wǎng)絡(luò)，并且保證無環(huán)路，通過路網(wǎng)簡化及在路徑搜索時采用橢圓算法限制搜索區(qū)域，能大幅度提高計算效率，同時路徑搜索更加合理，只在高層圖及橢圓區(qū)域中進(jìn)行搜索，排除一些繞行遠(yuǎn)、反復(fù)換乘等與實際不符的不合理路徑。在大規(guī)模復(fù)雜鐵路網(wǎng)多路徑搜索技術(shù)中，通過構(gòu)建鐵路抽象拓?fù)渚W(wǎng)絡(luò)，節(jié)點和邊拓?fù)潢P(guān)系合理，數(shù)據(jù)結(jié)構(gòu)清晰，易于數(shù)據(jù)存儲，減少路徑搜索時大量不必要的判斷，便于計算機(jī)編程開發(fā)實現(xiàn)。

表1 西安—北京前 4 條時間最短路

[1] 孔 千，劉 中，周飛飛，等. 鐵路網(wǎng)絡(luò)結(jié)構(gòu)存儲及貨運徑路問題研究[J]. 軍事交通學(xué)院學(xué)報，2009，11(5)：10-15.KONG Qian，LIU Zhong，ZHOU Fei-fei，et al. Research on Store Method of Railway Network Structure and Calculation of Freight Tariff Routes[J]. Military Traffic and Transportation，2009，11(5)：10-15.

[2] 張羽成，呂紅霞，王寶杰. 基于圖論的列車運行徑路分析與構(gòu)造[J]. 西南交通大學(xué)學(xué)報，2000，35(3)：273-276.ZHANG Yu-cheng，LV Hong-xia，WANG Bao-jie. The Analysis and Construction of Train Routine based on Graphics Theory[J]. Journal of Southwest Jiaotong University，2000，35(3)：273-276.

[3] Dijkstra E. A Note on Two Problems in Connection with Graphs[J]. Numberische Mathmatic，1959，1(1)：269-271.

[4] Shier R. On Algorithm for Finding the K Shortest Pathes in a Network[J]. Networks，1979，9(9)：195-214.

[5] Yen J. Finding the k Shortest Loopless Pathes in A Network[J]. Management Science，1971，17(11)：712-716.

[6] Macgeor M，Grover WD. Optimized k-Shortest Path Algorithm for Facility Restoration[J]. Software Practice and Experience，1994，24(9)：823-828.

[7] 王 喆，彭其淵，謝小淞. 基于遺傳算法的鐵路旅客列車開行路徑優(yōu)化的研究[J]. 鐵路計算機(jī)應(yīng)用，2006，15(12)：4-6.WANG Zhe，PENG Qi-yuan，XIE Xiao-song. Research on Optimization of Railway Passenger Train Path based on Genetic Algorithms[J]. Railway Computer Application，2006，15(12)：4-6.

[8] 李旭華，王建中. 基于數(shù)據(jù)庫的城市道路中的最短路徑搜索[J]. 電腦開發(fā)與應(yīng)用，2005，18(1)：14-15.LI Xu-hua，WANG Jian-zhong. The Shortest Path Search based on City Road of Database[J]. Computer Development &Applications，2005，18(1)：14-15.

[9] 王明中，謝劍英，陳應(yīng)麟. 一種新的K-PATH最短路搜索算法[J]. 計算機(jī)工程與應(yīng)用，2004，40(30)：49-50.WANG Ming-zhong，XIE Jian-ying，CHEN Ying-lin. A New Algorithm for Finding Kth Shortest Path[J]. Computer Engineering and Applications，2004，40(30)：49-50.

[10] 付夢印，李 杰，鄧志紅. 限制搜索區(qū)域的距離最短路徑規(guī)劃算法[J]. 北京理工大學(xué)學(xué)報，2004，24(10)：881-884.FU Meng-yin，LI Jie，DENG Zhi-hong. A Route Planning Algorithm With in a Restricted[J]. Transportation of Beijing Institute of Technology，2004，24(10)：881-884.

[11] 榮 瑋. 基于道路網(wǎng)的最短路徑算法的研究和表現(xiàn)[D]. 武漢：武漢理工大學(xué)，2005.RONG Wei. The Shortest Path Algorithm based on Road Network Research and Performance [D]. Wuhan：Wuhan University of Technology，2005.

[12] 胡必松. 基于列車開行方案的服務(wù)網(wǎng)絡(luò)構(gòu)建及路徑搜索技術(shù)研究與系統(tǒng)開發(fā)[D]. 北京：北京交通大學(xué)，2011.HU Bi-song. Research on the Technology of Network Construction based on Train Service Plan and Path Search and the Development of Computer System[D]. Bejing：Beijing Jiaotong University，2011.

[13] 柳 健，聶 磊. 鐵路客運服務(wù)網(wǎng)絡(luò)路徑搜索算法的研究與實現(xiàn)[J]. 鐵道運輸與經(jīng)濟(jì)，2012，34(12)：58-63.LIU Jian，NIE Lei. Path Search Algorithm in the Passenger Train Service Network[J]. Railway Transport and Economy，2012，34(12)：58-63.

[14] 向聯(lián)慧. 客運中轉(zhuǎn)換乘的優(yōu)化模型與算法[D]. 長沙：長沙鐵道學(xué)院，2000.XIANG Lian-hui. Passenger Transit Transfer Optimization Model and Algorithm [D]. Changsha：Central South University，2000.

[15] 孫健鶴. 城市道路網(wǎng)絡(luò)最短路徑的統(tǒng)計學(xué)特征及試用算法研究[D]. 上海：華東師范大學(xué)，2006.SUN Jian-he. Statistical Characteristics of Urban Road Network Shortest Path and the Trial Algorithm Research[D]. Shanghai：East China Normal University，2006.