基于鐵路有效路徑的換乘方案快速搜索方法

蘇煥銀，史峰 ，張佩，魏堂建,3

(1.中南大學 交通運輸工程學院，湖南 長沙 410075; 2.鄭州鐵路局，河南 鄭州 450052;3.華東交通大學 軌道交通學院，江西 南昌 330013)

基于鐵路有效路徑的換乘方案快速搜索方法

蘇煥銀1，史峰1，張佩2，魏堂建1,3

(1.中南大學 交通運輸工程學院，湖南 長沙 410075; 2.鄭州鐵路局，河南 鄭州 450052;3.華東交通大學 軌道交通學院，江西 南昌 330013)

研究鐵路旅客換乘方案的快速搜索方法可為鐵路售票系統提供支持。通過分析鐵路旅客出行路徑特征，引入非最短系數概念，給出有效路徑的判定條件，設計有效路徑的搜索算法。基于有效路徑集，設計前序弧數法搜索任意計劃出發時間的旅客最優換乘方案。整體算法由2個部分組成，一是整個鐵路網絡有效路徑的預先生成和存儲；二是給定計劃出發時間和起訖站點的最優換乘方案的快速搜索。算法既考慮了鐵路旅客的出行路徑特征又突出了“快速搜索”的特點。基于2014年中國高速鐵路網絡及運行圖進行算例分析，結果顯示算法具有較高的運算效率和很強的實用性。

鐵路運輸；換乘方案；有效路徑；非最短系數；運行圖

鐵路運輸是旅客中長距離出行的重要交通方式，具有節能環保、安全舒適、可持續發展的明顯優勢。隨著鐵路客運網絡的擴大以及居民生活水平的提高，旅客對鐵路客運服務提出了更高的要求。旅客換乘方案的搜索既是協助旅客購票的鐵路客運服務，又是基于列車時空網絡進行客流分配的核心技術，在鐵路旅客運輸組織中具有重要意義。目前對換乘方案的研究一般以時間、費用、里程等為多目標構建數學規劃模型[1]，通過構造換乘網絡，求解最短路獲得最優解。崔炳謀等[2]通過匹配列車發到站間的銜接關系得到所有可行的出行方案，根據目標權重對方案排序得到K優解。楊信豐等[3]考慮最大換乘次數的限制，建立鐵路旅客乘車方案優化模型，設計旅客出行可行路徑的快速搜索算法。林冬梅等[4]提出換乘節點匹配法，在換乘次數的限制下通過匹配列車發到站間的銜接關系，等到始發終到站間所有可行出行方案。史峰等[5]設計了多種類型的換乘網絡，并對各換乘網絡的規模、功能和計算能力進行了綜合比較分析。在出行路徑搜索方面，傳統的路徑搜索方法是從起點開始，從各個方向不斷向周圍擴展，直到終點，背離終點方向的搜索為無效搜索，搜索規模較大。Hart等[6]提出的A*啟發式算法,通過估價函數可引導搜索向著成本最小的方向進行，提高了最小費用路徑搜索效率，但是對于鐵路旅客特有的出行行為特征不能很好地描述，是具有一般應用性的路徑搜索方法，針對性不強。對鐵路路徑選擇的研究主要側重于客運經由的計算，大多遵從“里程短、換乘次數少”的原則[7]。王華等[8]以接算站為點集構造網絡縮小路網規模，考慮換線數來模擬換乘數，設計以距離與換線結合為單目標的啟發性算法求解客運徑路。呂曉艷等[9]提出一種車次約束機制下的徑路生成計算方法：采取車站特殊徑路的分布式存取與徑路公共信息的全路共享的方式, 有效壓縮徑路信息存儲空間，并通過車站特殊徑路計算和公共徑路計算生成有效徑路。DOU等[10]基于列車時刻表構建了旅客換乘網絡，考慮廣義費用和列車剩余能力搜索路徑。

鐵路旅客換乘方案搜索主要在售票過程或售票模擬過程中實施運用，采用傳統方法不能滿足快速搜索的需求。隨著售票過程的進展，一些列車區段相繼滿員，列車時空網絡變得越來越支離破碎。在這種不斷變化的網絡中搜索當前最優換乘方案時，如何既考慮鐵路旅客的出行路徑特征又突出“快速搜索”的特點，是本文研究的核心內容。鐵路網絡中，任意2點之間旅客經常出行的路徑一般是確定的，這樣的路徑具有2個特征，一是繞道里程不會太長，二是一般不會出現迂回節點。旅客根據實時信息，選擇最優的換乘方案，而且，旅客的選擇空間是有限的，更確切地說是局限于常用的幾條路徑上。因此，大可不必從全路網的范圍內搜索旅客出行的最優換乘方案，可以將搜索范圍限制于常用的幾條路徑上，既符合旅客的出行行為特征，又可以避免大量的無效搜索工作，提高換乘方案的搜索效率，實現快速搜索的目的。本文通過引入非最短系數概念，給出有效路徑(旅客經常出行的路徑)的判定條件。設計具有能力約束的時空換乘網絡，將換乘方案的搜索范圍限制在有效徑路上，并設計了前序弧數法，基于有效路徑集快速搜索任意計劃出發時間的旅客最優換乘方案。整體算法由2個部分組成，一是整個鐵路網絡有效路徑的預先生成和存儲；二是給定計劃出發時間和起訖站點的最優換乘方案的快速搜索。基于2014年中國高速鐵路網絡及運行圖進行算例分析，驗證了算法的正確性和高效性。

1 鐵路旅客換乘方案及費用分析

鐵路旅客換乘方案是指從始發站u出發，換乘幾趟列車后，到達終點站v的乘車序列，可表示為

(1)

其中，“+”表示列車區段之間的換乘銜接，當m=1時，該換乘方案表示直達方案；當m>1時，表示需要換乘不同的列車。

(2)

2 鐵路旅客有效路徑

2.1 有效路徑定義

鐵路網絡中任意兩點之間旅客經常出行的幾條路徑稱為有效路徑。有效路徑通常有2個重要特征：1)繞道里程不會太長；2)僅當需要換乘或列車折返時才可能使得路徑上出現重復節點。

(3)

綜上所述，有效路徑R的判定條件如下：

(4)

圖1 有效路徑搜索范圍示意圖Fig.1 Hunting zone diagram of effective paths

2.2 有效路徑搜索

在式(4)判定條件的約束下，可以在式(3)的范圍內搜索出多條有效路徑。注意到“最短路上任意兩點之間的路徑也是最短路”，有效路徑也具有類似特征“有效路徑上任意2點之間的路徑也是有效路徑”。基于此特征，設計有效徑路的搜索算法。

圖2 有效路徑搜索方法示意圖Fig.2 Search method diagram of effective paths

算法1 有效路徑的搜索算法

開始

對于k=2,3,…,n，循環執行

開始1

當m

開始2

返回2

返回1

結束

3 基于有效路徑的換乘方案搜索算法

3.1 有效路徑上列車區段的判定法則

圖3 列車路徑與有效路徑不一致的示意圖Fig.3 Train section doesn’t lie on an effective path

(5)

3.2 基于單條有效路徑搜索換乘方案

方便描述起見，構造沿有效路徑R進入或離開車站s的列車區段集：

(6)

(7)

算法2 基于單條有效路徑的換乘方案搜索算法

開始

開始1

開始2

返回2

返回1

結束

運算量較大的運算為語句：

(8)

綜上所述，算法2只要適當加強預處理，就是一個關于有效路徑內乘車區段數的線性復雜度的最優算法。

3.3 基于多條有效路徑搜索換乘方案

算法2所描述的是基于單條有效路徑搜索換乘方案的方法，注意到不同有效路徑之間可能存在重疊部分，基于多條有效路徑搜索換乘方案時，將公共部分共享搜索，則可進一步提高搜索效率。

4 算例分析

4.1 基礎數據及參數標定

采用2014年7月1日運營的高鐵線路及列車時刻表(獨立于路網的線路除外)。路網節點由444個列車停靠站組成，路網弧段為相鄰兩站間鐵路線路，站間里程為弧段里程。車站劃分為4個等級，如表1所示。設置列車票價為0.45元/km，疲勞因子為0.5元/min，調整出發時間懲罰因子為0.4 元/min。考慮到高鐵網絡比較簡單，設置每對O-D間的最多有效路徑數M=2，非最短系數λ=1.7。

表1 不通車站等級的參數設置Table 1 Parameter settings for different station classes

4.2 程序運行結果及分析

算法代碼采用C#語言編寫，運行環境是CPU雙核、主頻為3.20 GHz，內存為4G的計算機。算法運行分為2部分：1)加載基礎數據并計算任意2站間有效路徑，將有效路徑存儲；2)在給定計劃出發時間及始發終到站的條件下，實時搜索最小費用換乘方案。第1部分平均耗時50 s，第2部分運行時間不超過0.1 s，算法具有很高的求解速度。

4.2.1 有效路徑分析

選取兩個具有代表性的出行O-D，計算有效路徑，結果如表2所示，具體的路徑節點分布如圖4所示。南京南至上海虹橋的2條有效路徑確實是旅客經常出行的路徑，符合旅客的出行行為特征。其實，蚌埠南至武漢還有第2條路徑：蚌埠南→滁州→南京南→全椒→合肥→麻城→武漢，圖4中虛線部分的子路徑(蚌埠南→滁州→南京南→全椒→合肥)的里程為329 km，而對應的最短路(蚌埠南→淮南東→合肥)的里程為132 km，那么該子路經的非最短系數為2.49，遠大于非最短系數的上限λ=1.7，所以，第2條路徑不滿足有效路徑的判定條件。若調整非最短系數上限λ=2.5，那么第2條路徑即可滿足有效路徑的判定條件。但是，由于繞道里程太長，在一般情況下旅客不會選擇第2條路徑出行，其實，設置λ=1.7是符合絕大多數旅客的出行路徑習慣的。

表2 有效路徑Table 2 Effective paths

圖4 有效路徑示意圖Fig.4 Effective paths diagram

4.2.2 換乘方案分析

不同計劃出發時間的旅客最優換乘方案選擇情況如圖5所示，將計劃出發時間劃分了7個時段，每個時段內的乘客具有相同的最優乘車方案。在時段①內計劃出行的旅客需要換乘1次，這是因為該時段的旅客若要選擇直達方案，將會等待很長時間，出行時間調整費用過高，因此寧愿選擇換乘1次的方案出行；其他時段內列車發車頻率較高，出行時間調整費用較小，因此旅客都愿意選擇直達方案，和實際情況相符合。

圖5 不同計劃出發時間的最優換乘方案Fig.5 Optimal transfer scheme at different expected departure time

5 結論

本文在分析鐵路旅客出行路徑特征的基礎上，通過引入非最短系數概念，給出了有效路徑的判定條件，設計了有效路徑快速搜索算法。設計了前序弧數法，基于有效路徑集快速搜索任意計劃出發時間的旅客最優換乘方案。整體算法由2部分組成，一是整個鐵路網絡有效路徑的預先生成和存儲；二是給定計劃出發時間和起訖站點的最優換乘方案的快速搜索。在不斷變化的換乘網絡中搜索當前最優換乘方案時，本文設計的算法實現了既考慮鐵路旅客的出行路徑特征又突出“快速搜索”的特點的目的。基于2014年中國高速鐵路網絡及運行圖進行算例分析，算例結果顯示全路網有效徑路的生成和存儲平均耗時50 s，任意一個最優換乘方案的搜索時間不足0.1 s，算法具有較高的運算效率和很強的實用性。

[1] 張銥瑩,彭其淵. 綜合運輸旅客換乘網絡優化模型[J]. 西南交通大學學報,2009,44(4):517-522. ZHANG Yiying, PENG Qiyuan. Optimization model of passenger transfer network for integrated transportation [J]. Journal of Southwest Jiaotong University,2009,44(4):517-522.

[2] 崔炳謀,馬鈞培,陳光偉,等. 鐵路旅客旅行換乘方案優選算法[J]. 中國鐵道科學, 2007,28(6):122-127. CUI Bingmou, MA Junpei, CHEN Guangwei, et al. Optimal algorithm of travel transfer scheme for railway passengers [J]. China Railway Science,2007, 28(6):122-127.

[3] 楊信豐,劉蘭芬,李引珍,等. 多目標鐵路旅客乘車方案優化模型及算法研究[J]. 交通運輸系統工程與信息,2013,13(5):72-78. YANG Xinfeng, LIU Lanfen, LI YInzhen, et al. Route selection for railway passengers: A multi-objective model and optimization algorithm [J]. Journal of Transportation Systems Engineering and Information Technology,2013,13(5):72-78.

[4] 林冬梅,劉軍. 限制網絡上的鐵路旅程規劃快速求解算法[J]. 鐵道學報,2013,35(2):8-13. LIN Dongmei, LIU Jun. A fast algorithm for railway route planning on restricted network [J]. Journal of the China Railway Society,2013,35(2):8-13.

[5] 史峰,鄧連波. 旅客換乘網絡優化設計[J]. 鐵道科學與工程學報,2004,1(1):78-82. SHI Feng, DENG Lianbo. Optimal design of passenger transfer network [J]. Journal of Railway Science and Engineering,2004,1(1):78-82.

[6] Hart P E, Nilsson N J, Raphael B. A formal basis for the heuristic determination of minimum cost paths in graphs [J]. IEEE Transactions of Systems Science and Cybernetics, 1968, 4(2):100-107.

[7] 史峰,馬鈞培,向聯慧,等. 客運中轉徑路的換乘模型及算法[J]. 鐵道學報,1999,21(5):1-4. SHI Feng, MA Junpei, XIANG Lianhui, et al. A Transfer model and its algorithm of the transfer route in railway passenger transportation [J]. Journal of the China Railway Society, 1999,21(5):1-4.

[8] 王華,季令. 我國鐵路客運合理徑路選擇的研究[J].上海鐵道大學學報,1999,20 (4):51-54. WANG Hua, JI Ling. Research an rational pathway assemble in our national railway[J]. Journal of Shanghai Tiedao University, 1999,20 (4):51-54.

[9] 呂曉艷,劉春煌,單杏花,等. 基于車次徑路約束下的客運徑路生成算法優化[J]. 中國鐵道科學,2007, 28(3):122-125. Lü Xiaoyan, LIU Chunhuang, SHAN Xinghua, et al. Optimal on route computation algorithm based on train-route restriction [J]. China Railway Science,2007,28(3):122-125.

[10] DOU Fei, YAN Kai, HUANG Yakun, et al. Optimal path choice in railway passenger travel network based on residual train capacity [J]. The Scientific World Journal, 2014:1-8.

Fastsearch algorithm of transfer scheme based on effective paths in railway networks

SU Huanyin1, SHI Feng1, ZHANG Pei2, WEI Tangjian1,3

(1. School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China;2. Zhengzhou Railway Department, Zhengzhou 450052, China;3.School of Rail Transit, East China Jiaotong University, Nanchang 330013, China)

Research on fast search algorithm of transfer scheme for railway passengers can provide supports to ticket booking system. Through analyzing characters of rail passenger travel paths, this paper designs decision conditions of an effective path by non-shortest coefficient and develops a search algorithm for effective paths. Based on the set of effective paths, a fast search algorithm of transfer scheme with minimum cost at any expected departure time is proposed by a front-arc-number method. The whole algorithm in this paper includes two parts: firstly, producing and storing effective paths of the whole railway network in advance; secondly, searching a transfer scheme with minimum cost on effective paths with the given departure time and O-D pair. This algorithm captures passenger’s travel characters and lights the fast-search feature. Numerical experiment is conducted based on China high-speed railway network and train schedule in 2014, and results verify the effectiveness and utility of the algorithm.

rail transit; transfer scheme; effective path; non-shortest coefficient; train schedule

2016-01-26

國家自然科學基金資助項目(U1334207)；中南大學博士生自主探索創新項目(2015zzts046)

史峰(1956-)，男，湖南芷江人，教授，博士，從事交通流理論，運輸網絡優化研究；E-mail：shifeng@csu.edu.cn

U293.32

A

1672-7029(2016)12-2496-07