多目標鐵路旅客乘車方案優(yōu)化模型及算法研究

楊信豐,劉蘭芬,李引珍,b,何瑞春

(蘭州交通大學a.交通運輸學院;b.西北交通經濟研究中心,蘭州730070)

多目標鐵路旅客乘車方案優(yōu)化模型及算法研究

楊信豐*a,劉蘭芬a,李引珍a,b,何瑞春a

(蘭州交通大學a.交通運輸學院;b.西北交通經濟研究中心,蘭州730070)

鐵路旅客乘車方案選擇問題需要考慮不同旅客出行路徑選擇的影響因素.為了提高計算效率,首先對鐵路客運網(wǎng)絡進行適當簡化,在分析影響旅客出行路徑選擇主要因素的基礎上,以總乘車時間最小、總票價費用最少、換乘次數(shù)最少、換乘距離最短、換乘間隔時間損失最小及疲勞恢復時間最短為目標函數(shù),考慮最大換乘次數(shù)的限制,建立鐵路旅客乘車方案優(yōu)化模型;并利用旅客列車時刻表設計旅客出行可行路徑的快速搜索算法,根據(jù)可行路徑集合,利用信息熵法確定各目標的權重,計算各可行路徑的綜合目標值,從而獲得較滿意的出行方案.最后,利用近期的鐵路旅客列車時刻表,計算蘭州至北京,蘭州至長春的鐵路旅客乘車方案.計算結果表明,可以得到旅客滿意的出行方案.

鐵路運輸;乘車方案;多目標;換乘;信息熵

1 引 言

隨著鐵路六次大提速和客運專線的大量開通,旅客列車開行的數(shù)量和種類越來越多,這些硬件設施的加強使得越來越多的旅客選擇鐵路出行.這就要求鐵路部門在加強硬件建設的同時提高服務能力,其中,針對旅客出行要求提供可選擇的乘車方案就是一個值得研究的課題.

國內外關于旅客換乘的研究多集中在公共交通上,其中的方法和理論在鐵路換乘研究中可以加以借鑒.文獻[1]引入效用函數(shù)的概念,采用消費者依據(jù)效用最大化原則得到的出行路線更貼近出行者意愿.文獻[2,3]分別運用直達矩陣、換乘矩陣和換乘有罰的方式建立了優(yōu)化模型,設計了搜索換乘次數(shù)最少、所需時間最短的公交出行路徑的算法.在鐵路旅客換乘方面,文獻[4]通過分析旅客乘車方案選擇問題,對狹義最短乘車時間、最短換乘時間及最小乘車費用等8個目標進行分析,通過8個平衡系數(shù)綜合以上目標,最終建立旅客乘車綜合優(yōu)化數(shù)學模型,根據(jù)旅客列車開行方案構造有向網(wǎng)絡并設計了相應算法.文獻[5]考慮旅客出行方案需求的差異性基于效用理論構建旅客換乘方案優(yōu)化模型,并選用K短路算法求解.文獻[6]通過增加虛擬點的方式構建基于列車運行時刻的換乘網(wǎng)絡,并在此基礎上,設計了有換乘次數(shù)限制的、總旅行時間最少的中轉換乘模型,并采用遺傳算法尋找最優(yōu)解.文獻[7]基于旅客列車運行時刻表,考慮換乘中轉的影響因素根據(jù)旅客個性化需求設置相應的優(yōu)先級,定義各類因素的加權和為“旅行廣義時間函數(shù)”,構造出了一個動態(tài)規(guī)劃數(shù)學模型及相應的A*算法.文獻[8]設計了旅客對列車選擇概率的多項Logit模型,并對影響因素選擇及參數(shù)標定進行了研究.文獻[9]以旅行目標值與換乘目標值之和最小作為目標函數(shù),研究多目標權值的確定方法,提出最短路法和列車匹配法2種求解方法.

在實際應用中,由于出行者考慮問題的角度不同,對最佳乘車路線的理解就不同,問題不能簡單地抽象為最短路問題.本文選擇乘車時間、票價費用、換乘次數(shù)、換乘距離、換乘等候時間及舒適度等6個影響因素,建立多目標鐵路旅客乘車方案優(yōu)化模型,并根據(jù)路網(wǎng)結構、列車開行特點結合信息熵法設計求解算法.

2 換乘網(wǎng)絡

我國鐵路大小客運營業(yè)站有上千個,若構造一個包含全國鐵路所有客運營業(yè)站的網(wǎng)絡,計算量將非常龐大,從實際應用角度也沒有必要.為提高效率,需要對路網(wǎng)進行適當?shù)暮喕?本文以路網(wǎng)上對客運徑路和換乘計算有影響的車站作為網(wǎng)絡結點,刪除無列車停站及只有一個列車停站的車站(始發(fā)站及終到站除外),將路網(wǎng)簡化后保留下來的車站作為換乘網(wǎng)絡的節(jié)點.

在簡化的路網(wǎng)基礎上以客運站作為網(wǎng)絡節(jié)點,以兩站間通過的列車作為有向弧,兩站間列車運行時間作為弧的權,以列車的到發(fā)時刻作為節(jié)點的權值,構建乘車網(wǎng)絡.設G=(V,L)為有向圖.L={li|i=1,2,…,N}為列車集合,N為列車數(shù)量(上下行列車分別表示);i=1,2,…,N}為列車經過站點集合,其中Vli=為列車li經過的站點集合;Tli=為列車經過站點的時間集合,示li次列車到達s站的時刻,表示li次列車從s站的發(fā)車時刻;C={cli|表示li次列車的類型;設∈Vli,li∈L}表示列車的票價集合,為乘li次列車從i站到j站所用的票價;為換乘站點對集合,表示列車lk,lm可以在站點進行換乘,一般為同一車站或同一城市內的車站;為換乘站間的距離集合,表示lk,在站點的換乘距離.

3 換乘路徑選擇影響因素

旅客出行路徑選擇的主要影響因素包括乘車時間、票價費用、換乘次數(shù)、換乘距離、換乘等候時間及舒適度等.

3.1 乘車時間

鐵路旅客乘車時間除了與所選線路、始發(fā)終到站里程有關外,還與所選列車種類(快、慢車)有關.用tij(li)表示乘li次列車從i站到j站所用的乘車時間

3.2 票價費用

鐵路票價因列車等級、席座的不同而各異,列車的等級可分為:動車組、直特列車、特快列車、快速列車及普快列車等.我國鐵路網(wǎng)中,任何鐵路線路上的兩站點間的鐵路運價均可以在鐵路列車時刻表上查詢得到,在研究過程中,票價選用各種類的最低票價(如普通列車選用硬座票價)進行計算.那么乘li次列車從i站到j站所用的票價為pij(li).

3.3 換乘次數(shù)

換乘次數(shù)是指乘客在完成一次出行過程中所換列車的次數(shù).由于換乘次數(shù)是乘客能直接感知的,因此換乘次數(shù)是直接影響乘客路徑選擇的一個重要因素.一般情況下,乘車時間差不多時換乘次數(shù)越少的路徑被選擇的概率越大[10].鐵路中轉換乘的旅客在途時間長、疲勞程度高,中轉換乘耗時耗力,因此換乘方案中換乘次數(shù)一般是一個不大的值,設最大換乘次數(shù)為Nmax,為了方便計算旅客乘車方案,最大換乘次數(shù)值可取2.

3.4 換乘距離

由于換乘可能會在同一城市的不同車站進行,給換乘帶來不便.換乘距離也是旅客出行路徑選擇的主要因素.如果換乘地點在同一個車站,則換乘距離較短,如果是不同車站,則換乘距離較長.為了便于計算,將在同一個車站換乘的距離設為0,即

3.5 換乘間隔時間

換乘間隔時間為從l1次列車換乘l2次列車的時間,即l2次列車出發(fā)時刻與l1次列車到達時刻之間的時間差,若差值小于1個緊接續(xù)標準T0(一般取T0=20 min)[9],則時差應加一天,即1 440 min.那么乘坐l1次列車從i站到j站換乘l2次列車所需的換乘間隔時間tij(l1,l2)為

如果換乘間隔時間較長,則旅客需要等待較長時間進行換乘,特別是跨天的還需要吃飯、住宿,換乘成本較大;如果換乘間隔時間較短,則由于列車運行時間的隨機性,可能會錯過換乘列車,造成車票的浪費,一般乘客會選擇換乘間隔在3～5 h之間的列車.本文設換乘間隔時間tij(l1,l2)的損失評價函數(shù)為

3.6 舒適性

舒適性是現(xiàn)代旅客交通運輸追求的服務特性之一,本文采用文獻[11]的研究成果,用旅行疲勞恢復時間來描述旅客選擇不同車次出行的舒適程度.鐵路旅客選擇某車次出行的疲勞程度越大,需要的疲勞恢復時間越長,該車次的疲勞恢復時間的廣義費用就越大[11].因此,本文選擇乘坐某車次的疲勞恢復時間的價值來表示乘坐該車次的舒適度價值.鐵路旅客乘li次列車從i站到j站的疲勞恢復時間[11]

式中 Tmax表示恢復疲勞所需的最長時間參數(shù),通常取14～15 h;αcli表示當乘車時間為0時,選擇cli列車類型的疲勞恢復時間(即出行疲勞恢復時間的最小值);βcli表示單位出行時間的疲勞恢復時間強度系數(shù),其值越大則疲勞恢復時間越長,參數(shù)βcli＞0.如果Tmax取15 h,則參數(shù)αc,βc的取值如表1所示[11].

表1 αc,βc取值Table 1 Values of αc,βc

4 換乘模型的構建

模型目標函數(shù)式(5)-式(10)分別為總乘車時間最小、總票價費用最少、換乘次數(shù)最少、換乘距離最短、換乘間隔時間損失最小及疲勞恢復時間最短.式(11)～式(13)保證從始發(fā)站o到終到站d為一條路徑,式(14)表示換乘次數(shù)滿足最大換乘次數(shù)Nmax的限制,式(15)是0-1變量約束.

顯然,該換乘方案數(shù)學模型是一個多目標路徑問題,屬于多目標優(yōu)化問題的一個子問題.

5 模型求解算法

多目標優(yōu)化問題的目標函數(shù)通常彼此之間都是互相矛盾的,因此,采用傳統(tǒng)最短路算法無法直接求得一條多目標最優(yōu)路徑.為了求解方便,可將模型求解過程分解為兩個階段:第一階段進行可行路徑集合的求解;第二階段利用信息熵法確定各目標的權重,并對各條可行路徑進行綜合目標值計算,找出較優(yōu)路徑方案.

5.1 可行路徑的搜索

由于旅客列車時刻表本身包含路徑信息,因此,在進行可行路徑集合的求解時,可以利用每個旅客列車時刻表的站點序列快速的得到多條可行的旅客出行路徑.為了方便計算旅客乘車方案,取最大換乘次數(shù)Nmax=2.

對于一次出行需求od而言,首先在列車集合L={li|i=1,2,…,N}中,分別找出經過o站及d站的列車集合,并分別記為Lo,Ld.

直達方案求解思路:設Li=Lo∩Ld,則li∈Li列車均經過o站及d站,如果li次列車從o站的發(fā)車時刻早于到達d站的時刻,即,則表示從o站乘坐li次列車可以直接到達d站.

根據(jù)上述思路,鐵路旅客出行乘車方案的具體算法步驟如下:

Step 2 如果Lo=?或者Ld=?,則停止計算,否則令Li∈Lo∩Ld;

Step 3 直達列車路徑計算,如果Li=?,轉至Step 4,否則,對于所有的若,則輸出li列車從o到d站的路徑,計算總乘車時間,票價費用換乘次數(shù)z3=0,換乘距離z4=0,換乘間隔時間效用z5=0及疲勞恢復時間,轉至Step 4;

Step 4 一次換乘路徑計算,令Lm=Lo-Ld,Lk=Ld-Lo,若Lm=?或者Lk=?,則停止計算,否則令且,如果,轉至Step 5,否則,轉至Step 6;

Step 5 輸出lm列車從o到vlm的站點及Lk列車從vl到d的站點,構成一次換乘路徑,計算總乘車時間,票價費用,換乘次數(shù)z3=1,換乘距離,換乘間隔時間效用z5=及疲勞恢復時間,轉至Step 6;

Step 6 兩次換乘路徑計算,令Lq=L-Lo∪Ld,若Lq=?,則停止計算,否則,對于所有的lq∈ Lq,如果且轉至Step7,否則,停止計算.

Step 7 輸出lm列車從o到vlm的站點,lq列車從到的站點及Lk列車從vlk到d的站點,構成兩次換乘路徑,計算總乘車時間,票價費用,換乘次數(shù)z3=2,換乘距離,換乘間隔時間效用及疲勞恢復時間z6,停止計算.

5.2 可行路徑的綜合目標值計算

從o站到d站的可行路徑集合的優(yōu)選實質為多目標決策問題.信息熵法是一種常用的確定多目標權重的方法,該方法基于“差異驅動”原理,突出局部差異,由各個樣本的實際數(shù)據(jù)求得最優(yōu)權重,反映了指標信息熵值的效用價值,避免了人為的影響因素,因而給出的指標權重更具有客觀性,從而具有較高的再現(xiàn)性和可信度;另外,信息熵法采用歸一化方法對數(shù)據(jù)進行無量綱化處理,具有單調性、縮放無關性和總量恒定性等優(yōu)異品質,且魯棒性較好[12].

設可行路徑條數(shù)為M,那么,M條可行路徑及6個目標值就構成了一個決策矩陣,設這個決策矩陣為MAodM×6.那么利用熵值賦權法獲得可行路徑的綜合目標值的計算過程如下:

Step 3 計算第j個目標的熵

Step 4 計算第j個目標的權重系數(shù)

Step 5 計算路徑i的綜合目標值

根據(jù)計算得到的綜合目標值,按照從大到小對可行路徑進行排序,排在前面的路徑為較優(yōu)路徑.

6 算例分析

利用2012年7月份的鐵路旅客列車時刻表,首先計算蘭州至北京的鐵路旅客乘車方案,選取最大換乘次數(shù)Nmax=1,經過計算得到可行路徑2 438條,其中直達路徑為6條,一次換乘方案中換乘城市為124個.利用熵值信息計算得到6個目標的權重為:0.001 8,0.004 9,0.509 8,0.005 3,0.471 8, 0.006 4.計算各可行路徑的綜合目標值,排在前15的路徑的綜合目標值及乘車方案如表2所示.從表2中可以看出直達方案的綜合目標值遠遠高于換乘方案,說明該方法能體現(xiàn)換乘次數(shù)是直接影響乘客路徑選擇的一個重要因素的現(xiàn)象.對比方案的各目標值,發(fā)現(xiàn)目標z3及z5的數(shù)值差異較大,對乘車方案選擇的影響較大,兩個目標對應的權重分別為0.509 8及0.471 8,相對較大,這反映了信息熵法基于“差異驅動”原理的特點.

仍然選取最大換乘次數(shù)Nmax=1,計算蘭州至長春的鐵路旅客乘車方案,得到可行路徑591條,全部為一次換乘方案,可換乘城市為66個.利用熵值信息計算得到6個目標的權重為:0.073 6, 0.0682,0,0.232 6,0.362 3,0.263 4.由于所得可行方案均為一次換乘方案,因此各方案的目標三的值均為1,該目標對方案的選擇沒有作用,從熵值信息計算得到的目標權重來看,目標三的權重為0,這也反映出信息熵法的客觀性.計算各可行路徑的綜合目標值,排在前5位及后5位路徑的綜合目標值及乘車方案如表3所示.

表2 蘭州至北京的較優(yōu)乘車方案及目標值Table 2 The optimal traveling schemes and objective values of Lanzhou-Beijing

表3 蘭州至長春的部分乘車方案及目標值Table 3 Some traveling schemes and objective values of Lan-zhuo-Changchun

表3中前5個方案為較優(yōu)方案,后5個方案為較劣方案,對比前5個方案與后5個方案的各目標值,z4,z5及z6三個目標的數(shù)值差異較大,對乘車方案選擇的影響較大,三個目標對應的權重也較大;另外,前5個方案均為同站換乘,而后4個方案為非同站換乘,對乘車方案的選擇也有較大影響.

7 研究結論

由于出行者考慮問題的角度不同,對最佳乘車路線的理解就不同,鐵路旅客乘車方案不能簡單地抽象為最短路問題,需要考慮不同的旅客出行選擇影響因素.本文分析了影響旅客出行路徑選擇的主要因素,并在簡化的路網(wǎng)基礎上構建旅客乘車網(wǎng)絡,以總乘車時間最小、總票價費用最少、換乘次數(shù)最少、換乘距離最短、換乘間隔時間損失最小及疲勞恢復時間最短為目標函數(shù),考慮最大換乘次數(shù)的限制,建立了鐵路旅客乘車方案優(yōu)化模型.本文以旅客列車時刻表為基礎,設計了利用每個旅客列車時刻表的站點序列搜索出行路徑的算法,該算法不需要對每個站點都進行標號,就能夠得到多條可行路徑,提高了路徑的搜索速度.根據(jù)獲得的可行路徑集合,利用信息熵法確定各目標值的權重,計算各可行路徑的綜合目標值,利用綜合目標值對可行路徑進行排序,從而獲得較滿意的出行方案.最后,利用近期的鐵路旅客列車時刻表,計算了蘭州至北京及蘭州至長春的鐵路旅客乘車方案,計算結果表明,可以快速的得到旅客滿意的出行方案.

[1] 劉雪巖.出行路線選擇行為研究[D].北京:對外經濟貿易大學,2006.[LIU X Y.The analysis of travelers route choice[D].Beijing:The University of International Business&Economics,2006.]

[2] BI Y,HU H P.Mathematical model of best-path planning algorithms for public transportation systems[C]//2010 International Conference on Computer Application and System Modeling,2010,V13:345-348.

[3] LIU C L.Best-path planning for public transportation systems[C]//Proc of the 5th International IEEE ConferenceonIntelligentTransportationSystems, 2002:834-839.

[4] 江南,史峰,盧紅巖,等.鐵路旅客乘車方案優(yōu)化決策模型研究[J].鐵道學報,2007,29(3):13-18. [JIANG N,SHI F,LU H Y,et al.The study on optimizationdecisionmakingmodelofpassenger traveling plan by train[J].Journal of The China Railway Society,2007,29(3):13-18.]

[5] 于冉冉.基于鐵路旅客需求異質性的換乘服務方案優(yōu)化研究與系統(tǒng)[D].北京:北京交通大學,2011. [YU R R.Optimization research of transfer services plan and aystem based on heterogeneous demand of railway passenger[D].Beijing:Beijing Jiaotong University,2011.]

[6] 劉蘭芬,倪曉宇.鐵路客運中轉換乘模型的遺傳算法研究[J].鐵道運輸與經濟,2006,28(2):86-89. [LIU L F,NI X Y.Study on the genetic algorithm for railway passenger transferring model[J].Railway Transport and Economy,2006,28(2):86-89.][7] 王琳穎,楊浩.基于個性化需求的鐵路最優(yōu)換乘模型與應用研究[J].鐵路計算機應用,2009,18 (12):1-5.[WANG L Y,YANG H.Study on optimal model of railway passenger transference based on individual demand and its applications[J].Railway Computer Application,2009,18(12):1-5.]

[8] 史峰,鄧連波,霍亮.鐵路旅客乘車選擇行為及其效用[J].中國鐵道科學,2007,28(6):117-121.[SHI F,DENG L B,HUO L.Boarding choice behavior and its utility of railway passengers[J].China Railway Science,2007,28(6):117-121.]

[9] 崔炳謀,馬鈞培,陳光偉,等.鐵路旅客旅行換乘方案優(yōu)選算法[J].中國鐵道科學,2007,28 (6):122-127.[CUI B M,MA J P,CHEN G W,et al.Optimization algorithm of travel transfer scheme for railway passengers[J].China Railway Science,2007, 28(6):122-127.]

[10] 郭彥云.城市軌道交通有效路徑問題研究[D].北京:北京交通大學,2011.[GUO Y Y. Research on problem of efficient paths for urban rail transit[D].Beijing:BeijingJiaotong University,2011.]

[11] 史峰,鄧連波,黎新華,等.客運專線相關旅客列車開行方案研究[J].鐵道學報,2004,26(2): 16-20.[SHI F,DENG L B,LI X H,et al.Research on passenger train plans for dedicated passenger traffic lines[J].Journal of The China Railway Society,2004, 26(2):16-20.]

[12] 孫利娟,邢小軍,周德群.熵值賦權法的改進[J].統(tǒng)計與決策,2010,(21):153-154.[SUN L J,XING X J,ZHOU D Q.The improving of rntropy method[J].Statistics and Decision,2010,(21): 153-154.]

Route Selection for Railway Passengers: A Multi-objective Model and Optimization Algorithm

YANG Xin-fenga,LIU Lan-fena,LI Yin-zhena,b,HE Rui-chuna
(a.School of Traffic and Transportation;b.Northwest Traffic Economic Research Centre of China, Lanzhou Jiaotong University,Lanzhou 730070,China)

With an increased operating speed in Chinese railways in recent years,the number of passengers traveling by trains has been significantly increasing.The research issue is regarding how passengers select their routes when there are no direct trains.Previous studies have dealt with the route selection problem as a multi-objective optimization.The study began by setting up a transportation network which encompasses the departure and terminal stations along with important intermediate stations.Then,six key factors are analyzed and formulated using a multi-objective model,consisting of the train-running time, railway fare,transfer frequencies,distances between transfer stations,transfer interval time,and travel comfort.Furthermore,a two-phase algorithm is employed to solve the model.A rapid searching algorithm for feasible routes based on the train timetable is established,then the weight vector is assigned by introducing the information entropy to obtain satisfied routes.In the end,the two-phase algorithm is tested respectively for railway passengers from Lanzhou to Beijing(with direct trains)and from Lanzhou to Changchun(withoutdirect trains),and the results show that the proposed model and solution algorithm are efficient for obtaining satisfactory routes.

railway transportation;traveling scheme;multi objective;transfer;information entropy

U293

: A

U293

A

1009-6744(2013)05-0072-08

2012-09-27

2012-12-11錄用日期:2013-01-09

國家自然科學基金項目(61164003、61064012);蘭州交通大學青年基金項目(2012030).

楊信豐(1978-),男,河南省開封人,副教授,博士.

*通訊作者:xinfengyang@mail.lzjtu.cn.