基于廣義成本的軌道交通最優路徑模型研究

, , ,

(浙江理工大學機械與自動控制學院, 杭州 310018)

引 言

我國已有的高速鐵路專線分布網絡總長度已達到1.8萬km,開通城市軌道交通運營線路的城市共有15座,運營長度總規模約1 746 km。預計到2020年,將會建成省會城市及大中城市間的快速客運通道,建設客運專線1.2萬km以上[1]。隨著軌道交通的發展,鐵路接駁地鐵的最優路徑模型成為一個新的研究熱點。傳統的最優路徑理論一般將路程最短、時間最短或費用最少作為最優路徑,這種單目標的最優化往往帶有片面性和局限性,難以符合現實狀況。因此,建立基于多目標下的路徑優化模型能為軌道交通最優路徑模型的研究提供新思路?；谶@一思路,Dial[2]提出了時間和費用雙準則多目標最優路徑模型,即時間約束下的最小費用路徑模型。楊新苗等[3]設計了以換乘次數最少作為第一目標、出行距離最短為第二目標的雙目標約束最優路徑搜索和選擇模型。柴登峰等[4]提出了廣義最短路徑問題,設計了一個遞歸調用Dijkstra算法,可以求取前N條最短路徑的新算法。姚春龍等[5]提出了考慮多重目標的查詢模型,通過權值設定來靈活調整目標的取舍問題。Jourquine等[6]給出了出行時間和路徑選擇的組合動態用戶最優模型,利用出行費用和延遲成本求解模型。這些文獻給出了多目標的最優路徑模型和算法設計,但只是將目標作為約束條件,沒有將多目標之間的關系進行轉換。而且,這些文獻也沒有給出不同交通工具間換乘的計算模型。

本文提出將時間和成本兩個目標統一成廣義成本,建立基于廣義成本下的軌道交通換乘最優路徑模型,使之更加具有實際價值,應用Dijkstra算法求出的解也更為合理。

一、軌道交通換乘最優路徑求解問題

(一)交通網絡模型

軌道交通換乘路徑求解問題可以描述為:已知乘客在鐵路和地鐵兩種交通出行方式的情況下,找出從起點到終點的滿足乘客需求的最優路徑。其中換乘路徑必須滿足以下條件[7]:

(1) 出發點與目標點不屬于同一條線路;

(2) 出發點與目標點必須是連通的;

(3) 出發點到目標點的路徑不允許有回路。

將各站點進行分類,換乘站點:路線從一條線轉入另一條線的必經站;關鍵站點:出度>3且不算是換乘站點的車站;一般站點:出度≤2的站。將換乘站點和關鍵站點作為交通網絡的節點。

本文經過對軌道交通網絡的分析,采用兩級網絡的層次模型。第一級網絡模型:包括鐵路以及地鐵的所有車站、營運線名及其里程,也稱物理模型。第二級網絡模型:除去第一級網絡中的中間站,僅取第一級網絡中的關鍵站點、換乘站點以及拓撲結構。兩級路網模型的對應關系如圖1所示?？梢钥吹?第二級網絡模型的節點數明顯減少,能夠顯著提高算法效率。

圖1 兩級路網模型的對應關系

二、廣義成本下的二階段換乘最優路徑模型

(一)最優路徑計算模型

1.時間成本模型

設G=為有向帶權圖,其中N={1,2,…,n}表示節點的集合,E={eij|i∈N,j∈N,i≠j}表示交通網絡里的路段集合,M代表所有開車列車的車次集合,D代表節點之間的里程，T代表節點之間經歷的時間,C代表節點之間的票價。兩列列車在換乘站能夠換乘的條件是:到車時間和發車時間間隔不小于最小的換乘時間,這里用T0表示。構建的時間成本模型:

Ttrain=Ttravel+Twait=

(1)

其中,

對城市軌道交通而言,只有發車頻率和首末班時間,行車時間由路程長度與行車速度決定。設地鐵速度為v,發車間隔頻率為fk。在城市軌道交通的研究中,通常認為等車時間是發車頻率的函數,計算公式如下[8]:

(2)

在兩種不同的交通工具之間進行換乘時,必須添加一個懲罰因子[9],記作Tturn。因此,軌道交通換乘的時間成本模型函數為:

T(O,D)=β1(Ttravel×X鐵路+T乘車×X地鐵)+

β2(Twait×X鐵路+Twait×X地鐵)+β3×Tturn×Xturn=

(3)

β1、β2、β3分別為各部分時間的重要性權值。

2.票價成本模型

城市軌道交通收費體系中票形式為里程票制[10]。里程票是指根據路程的長短確定票價,其票價函數形式為f(s)。因此,參照鐵路的時間成本模型函數,地鐵的成本函數為:

(4)

結合鐵路及地鐵的成本函數模型,得到軌道交通換乘的票價成本模型函數:

中醫專業學生通過5年的本科學習，具備了較為扎實的中醫學基本理論和基本技能，但普遍對中藥化學成分、鑒別、炮制和制劑等知識缺乏了解，而中藥是醫生治療疾病的重要武器，中藥質量的好壞關系到藥物療效的發揮，最終會影響到患者的身體健康。所以隨著中藥現代化推進，中醫專業研究生有必要加強中藥化學成分、分析測試技術和現代制劑技術等知識的學習。

F(O,D)=

(5)

3.可靠性成本模型

可靠性成本是指交通工具到站時間的準點性、相鄰交通工具間隔的均勻性及安全性。本文用出行時間中等待時間的偏差因子來衡量。理想狀態下的等待時間為fk/2,因此,可靠性成本模型的函數為:

(6)

式(6)表明,在軌道交通等封閉環境較好的交通工具下,由于其準時性較高,可靠性成本可以不作考慮。

(二)票價成本對時間成本的轉換模型

票價的單位為元,時間的單位是h(小時)。這兩者之間可以通過時間行為價值的原理相互轉化[11]。按照相關文獻計算公式如下:

Bvot=Pwork×[Ywage/(50×40)-Bxiuxiam]+

(1-Pwork)×Bxiuxian

(7)

當Pwork為全國城市平均水平時,即Pwork=0.5時,得到票價成本對時間成本的轉換函數為:

Bvot=Ywage/4000

(8)

(三)廣義成本下的最優路徑模型

廣義成本是指由時間、票價、可靠性成本三部分構成的成本[8-9]。其形式為:

C(O,D)=CT(O,D)+CF(O,D)+CR(O,D)=

θ1ω1(T)T(O,D)+θ2ω2(F)F(O,D)+θ3ω3(R)R(O,D)

s.t.θ1+θ2+θ3=1,θ1,θ2,θ3>0

(9)

式(9)中,C(O,D)表示起點O和終點D間的廣義成本;CT(O,D)表示起點O和終點D間的時間成本;CF(O,D)表示起點O和終點D間的票價成本。ω1(T)、ω2(F)、ω3(R)分別表示時間、票價和可靠性的量綱轉化函數。T(O,D)、F(O,D)、R(O,D)分別表示時間函數、票價函數和可靠性函數。θ1、θ2、θ3分別表示時間、票價和可靠性的權重。

通過上述最優路徑計算模型以及票價成本對時間成本的轉換模型,最終得到基于廣義成本下的軌道交通換乘最優路徑的計算模型函數為:

minC(O,D)=

θ1ω1(T)×T(O,D)+θ2ω1(T)×(Ywage/4000)×

F(O,D)+θ3ω1(T)R(O,D)

(10)

三、Dijkstra算法

Dijkstra算法的基本思路是:假定V1→V2→V3→V4是V1→V4的最短路,如圖2所示,則V1→V2→V3必定是V1→V3的最短路,V2→V3→V4必定是V2→V4的最短路。否則,設V1→V3的最短路為V1→V5→V3,就有V1→V5→V3→V4的路必小于V1→V2→V3→V4,這與假設矛盾。

圖2 Dijkstra算法思路

若用dij表示兩相鄰點i與j的距離,若i與j不相鄰,則令dij=∞,顯然dii=0。若用Lsi表示從s點到i點的最短距離,現求從s點到o點的最短路,用Dijkstra算法的步驟如下[12]:

(1) 從s點出發,因Lss=0,將此值標注在s旁的方框內,表示s點已標號;

(2) 從s點出發,找出與s相鄰的點中距離最小的一個點,設為t。將Lst=Lss+ds的值標注在t旁的方框內,表明點t也已標號;

(3) 從已標號的點出發,找出與這些點相鄰的所有未標號的點p。若有Lsp=min{Lss+dsp;Lst+dtp},則對p點標號,并將Lsp的值標注在p點旁的方框內;

(4) 重復第3步,一直到o點被標號為止。

Dijkstra算法主要用于靜態路徑的最優化模型,該算法也是目前公認的理論上較完善的算法,且簡單易用。由于軌道交通本身具有封閉性好的特點,即受外界環境變化的影響很小。因此可以通過Dijkstra算法對基于廣義成本下的軌道交通換乘最優路徑模型進行求解。

四、模型仿真分析

以北京南站到上海同濟大學為例,通過鐵路運行時刻表和城市軌道交通運行表得到所有北京南站到上海的列車信息以及軌道交通的票價和發車頻率。以高鐵G157次列車為例,導入表1的數據,利用Matlab進行數據仿真。仿真參數:列車的等待時間為2 min;地鐵的發車頻率為每4 min一列;地鐵的平均速度為75 km/h;按照相關文獻調查及研究的成果將乘車時間相對重要性權值為1,等待時間相對重要性權值為2.1,換乘時間相對重要性權值為2.5[13];時間成本權值系數為0.26,票價成本權值系數為0.43,可靠性成本權值系數為0.31[14]。

表1 G157次列車信息

通過仿真運行得到圖3。從圖3中可以看到,黑色箭頭方向即為最優路徑方向。依次經歷的車站分別是北京南、滄州、濟南、昆山南、上海南站、人民廣場、上海體育館、徐家匯、豫園、南京東路、四川北路、海倫路、同濟大學。另外,通過仿真得到從北京南站到上海同濟大學的最低廣義成本為1 075元。綜合仿真結果得出,仿真求得的最優路徑較為合理,沒有出現重疊交叉路徑,且符合實際出行的規律?？梢?本文提出的基于廣義成本的軌道交通最優路徑模型具有收斂性以及可行性。

圖3 可視化的最優路徑

五、結 語

本文將行為時間價值理論應用于軌道交通換乘的多目標路徑優化模型,提出了基于廣義成本的軌道交通換乘最優路徑模型,并采用兩級分層的層次模型描述軌道交通網絡,有效減少搜索節點的數量,提高了Dijkstra算法效率。最后通過Matlab進行實例仿真,驗證了模型和算法的可行性和收斂性。本文的研究實現了多目標之間的關系轉換以及兩種交通工具之間換乘的模型計算,為多目標下的軌道交通換乘最優路徑模型的研究提供了一些思路和方法。

文中僅考慮了鐵路接駁地鐵這兩種運輸環境較為封閉的交通工具之間的換乘,在將來的工作中,還需對更多交通工具組合方式下的換乘進行討論,將經典的Dijkstra算法進行改進,以及針對外部環境不斷變化的情況下,考慮采用更加適合和高效的算法進行優化求解。

參考文獻：

[1] 陳文強, 吳群琪. 時間相關的運輸網絡最小費用路徑模型及算法[J]. 鐵道運輸與經濟, 2009, 31(5): 11-14.

[2] Dial R B. Transit pathfinder algorithm[J]. Highway Research Record, 1967, 205: 67-85.

[3] 楊新苗, 王 煒. 基于 GIS 的公交乘客出行路徑選擇模型[J]. 東南大學學報: 自然科學版, 2000, 30(6): 87-91.

[4] 柴登峰, 張登榮. 前 N 條最短路徑問題的算法及應用[J]. 浙江大學學報: 工學版, 2002, 36(5): 531-534.

[5] 姚春龍, 王 昱. 基于權值設定策略的公交出行路徑查詢模型[J]. 計算機工程與應用, 2009, 45(11): 241-244.

[6] Jourquine B, Beuthe M. Transportation policy analysis with a geographic information system: the virtual network of freight transportation in Europe[J]. Transportation Research, 1996, 4 (6): 359-371.

[7] 余震江. 基于最短路徑Dijkstra算法的鐵路客運中轉徑路優化研究[D]. 重慶: 重慶大學, 2008.

[8] 柳晶晶. 基于多種換乘方式的公共交通路徑選擇模型研究[D]. 武漢: 華中科技大學, 2009.

[9] 白惠濤. 基于多種交通方式的城市快捷客運系統出行路徑選擇模型及優化方法研究[D]. 北京: 北京交通大學, 2007.

[10] 李春清. 城市公共交通換乘系統關鍵問題及評價研究[D]. 北京: 北京交通大學, 2008.

[11] 黃樹森. 基于非集計的城市公共交通方式選擇模型及靈敏度分析研究[D]. 北京: 北京交通大學, 2008.

[12] 張伯生. 運籌學[M]. 北京: 科學出版社, 2008: 175-176.

[13] 王 林. 車輛導航系統中最優路徑算法的研究[D]. 葫蘆島: 遼寧工程技術大學, 2009.

[14] 張 帥. 基于ITS的智能乘客信息系統研究[D]. 鄭州: 河北工業大學, 2004.