彭宏勤,朱郁俊

(北京交通大學(xué)城市軌道交通系,北京100044)

基于客流動態(tài)分配的城際列車開行方案

彭宏勤*,朱郁俊

(北京交通大學(xué)城市軌道交通系,北京100044)

綜述了城際列車開行方案的研究現(xiàn)狀.為準(zhǔn)確描述客流與開行方案的互動關(guān)系,本文提出了模型建立的系統(tǒng)封閉性假設(shè)、列車種類劃分假設(shè)、客流動態(tài)轉(zhuǎn)化假設(shè)和選乘優(yōu)先順序假設(shè)等假設(shè)條件.在此基礎(chǔ)上,對相關(guān)集合變量進(jìn)行了描述,建立了反映不同類型客流轉(zhuǎn)化過程的客流動態(tài)分配模型,構(gòu)建了綜合考慮鐵路部門收益最大化、旅客總支出最小化和最大限度滿足客流需求的多目標(biāo)規(guī)劃模型.針對建立的多目標(biāo)0-1整數(shù)規(guī)劃模型,采用遺傳算法求解,并對規(guī)劃模型求解的過程進(jìn)行了說明,最后通過算例驗(yàn)證模型算法的有效性.

鐵路運(yùn)輸;開行方案;客流動態(tài)分配;多目標(biāo)規(guī)劃;遺傳算法

1 引 言

城際鐵路是在人口稠密的都市圈或城市帶規(guī)劃和修建的高速鐵路客運(yùn)系統(tǒng),是區(qū)域性的重要交通運(yùn)輸基礎(chǔ)設(shè)施.根據(jù)《中國鐵路中長期鐵路網(wǎng)規(guī)劃》,環(huán)渤海、長三角、珠三角地區(qū)建立區(qū)域性城際客運(yùn)系統(tǒng),覆蓋區(qū)域內(nèi)主要城鎮(zhèn)[1].為更好地集中配置和運(yùn)用城際鐵路運(yùn)力資源,提高市場競爭力,科學(xué)合理地制定城際列車開行方案具有重要現(xiàn)實(shí)意義.

國外客運(yùn)專線建設(shè)運(yùn)營起步早,列車開行方案的研究相對成熟,主要針對旅客列車開行方案成本、收益、直達(dá)旅客人數(shù)、換乘次數(shù)等目標(biāo),建立數(shù)學(xué)規(guī)劃模型.Bussieck等[2]提出了滿足旅客運(yùn)輸需求和運(yùn)輸能力約束,以直達(dá)旅客數(shù)最大化為目標(biāo)的混合整數(shù)規(guī)劃模型.Claessens等[3]提出了一個在給定路網(wǎng)結(jié)構(gòu),以成本最小化為目標(biāo),優(yōu)化發(fā)車頻率和所需列車數(shù)量的整數(shù)非線性規(guī)劃模型. Goossens等[4,5]提出復(fù)式線路規(guī)劃問題即單條鐵路上多種停站模式并行,建立以成本最小化為目標(biāo)的混合整數(shù)規(guī)劃模型.Chang等[6]采用模糊數(shù)學(xué)規(guī)劃方法,建立了以鐵路運(yùn)營費(fèi)用和旅客等待時間最小化為目標(biāo),單條鐵路上城際高速列車開行方案的多目標(biāo)優(yōu)化模型.

國內(nèi)客運(yùn)專線建設(shè)運(yùn)營起步相對較晚,相關(guān)研究多基于既有線路列車開行方案.馮楓[7]設(shè)計(jì)了以最大化直達(dá)運(yùn)輸和最小化列車虛糜為目標(biāo),在不考慮旅客換乘的影響情況下,求解旅客列車開行方案的多目標(biāo)數(shù)學(xué)規(guī)劃模型.鄧連波[8]構(gòu)造了客運(yùn)專線列車開行方案的雙層規(guī)劃模型,上層模型考慮企業(yè)收益和旅客需求,下層模型處理客流換乘選擇問題,并設(shè)計(jì)了基于模擬退火方法的優(yōu)化算法.張擁軍等[9]對高速列車停站影響進(jìn)行分析,研究建立了高速列車開行方案多目標(biāo)0-1規(guī)劃模型.徐瑞華等[10]研究了在已知OD車流的條件下合并車流方法,建立以滿足運(yùn)輸需求為約束,以列車開行數(shù)量最小化為目標(biāo)的高速列車開行方案優(yōu)化模型.

目前相關(guān)領(lǐng)域的研究成果多圍繞旅客列車的組織、開行方案的制定、開行方案的優(yōu)化等方面展開,且通常以固定的客流OD作為系統(tǒng)的輸入,針對開行方案的制定對實(shí)際客流反饋影響方面的研究尚顯不足.本文針對這一問題進(jìn)行研究,提出了客流的動態(tài)轉(zhuǎn)化假設(shè),并將客流動態(tài)分配融入到客運(yùn)專線列車開行方案的編制過程中.

2 建模的系統(tǒng)條件及假設(shè)

在本研究中,模型的建立是基于如下的條件假設(shè):

(1)系統(tǒng)封閉性假設(shè).系統(tǒng)狀態(tài)的變化只取決于內(nèi)部影響因素的變化.

(2)列車種類劃分假設(shè).根據(jù)城際列車平均速度和停站方案的不同,提出以擇站停高速、擇站停中速和站站停普速列車為基本組合的停站方案.各類型的列車優(yōu)先運(yùn)送相應(yīng)類型的客流.

(3)客流動態(tài)轉(zhuǎn)化假設(shè).不同的開行方案會對客流產(chǎn)生反饋?zhàn)饔肹11],使得各類別客流存在相互轉(zhuǎn)化現(xiàn)象.本文的動態(tài)不是指客流相對時間的動態(tài)性,而是實(shí)際客流分配相對于系統(tǒng)開行方案的動態(tài)性.

(4)選乘優(yōu)先順序假設(shè).本文不考慮旅客中途換乘情況,旅客在出發(fā)站可根據(jù)列車開行方案選乘列車,選乘時旅客按照自身客流類型優(yōu)先選擇相應(yīng)類型列車.

在滿足以上條件的情況下,建立了客流動態(tài)分配模型及各類型列車開行方案的多目標(biāo)規(guī)劃模型.

3 模型中相關(guān)量的數(shù)學(xué)描述

城際客運(yùn)專線網(wǎng)G={S,E},車站集S={si|i =1,2,…,n},s1,s2…,sn依次表示從始發(fā)站到終到站按經(jīng)過順序排列的車站.路段集E={ei|i=1,2,…,n-1},ei為si和si+l站間路段.相鄰車站間路段距離D={di,i+1|i=1,2,…,n-1},為車站si和sj間路段總距離.

列車等級集合T={G,Z,L},類型G為擇站停高速列車,Z為擇站停中速列車,L為站站停普速列車.設(shè)類型為K∈T的列車定員為AK.

初始客流OD已知,客流OD矩陣H=(hij)n×n, hij表示si和sj站間客流OD量.記si和sj站間乘坐K∈T型列車的初始客流為hKij.為簡便,稱該類型客流為K型客流.同理,高速、中速、普速列車客流OD矩陣可記為HK=(hKij)n×n( K∈T ).h～Kij為因開行方案變化造成客流類別發(fā)生轉(zhuǎn)化后,si和sj站間乘坐K∈T型列車的實(shí)際客流.

已知三種類型列車的開行方案均以s1為始發(fā)站sn為終到站[12],區(qū)別在于停站方案和服務(wù)頻率.用xKi表示K(K∈T)型列車是否在si停站.若列車停,則xKi=1,否則xKi=0.每日各類型列車服務(wù)頻率為fK.列車服務(wù)頻率是指單位周期時間(一天)內(nèi),該類型列車的開行對數(shù)(服務(wù)次數(shù))[13].三種類型列車開行停站方案如圖1所示.

K型列車停站時間為tKs,停站費(fèi)用cKs,車公里費(fèi)用cKr,K型列車運(yùn)行速度vK.

圖1 三種類型列車開行方案示意圖Fig.1 Operating schemes of this three type trains

4 模型的構(gòu)建

城際鐵路相對于干線鐵路距離短,多采用公交化運(yùn)營方式,一般無復(fù)雜的路網(wǎng)結(jié)構(gòu).研究城際列車開行方案,重點(diǎn)在于確定各類型列車停站方案與服務(wù)頻率.在城際列車的始發(fā)、終到站都已確定,且城際列車路線是一條單一路徑的條件下,可以建立以三種類型列車的停站方案和服務(wù)頻率為優(yōu)化指標(biāo),鐵路部門收益最大和旅客總體支出最小和盡量滿足客流需求為優(yōu)化目標(biāo),區(qū)段運(yùn)輸能力與通過能力等客觀因素為約束的多目標(biāo)優(yōu)化模型.

根據(jù)客流動態(tài)轉(zhuǎn)化假設(shè),建立各類型客流動態(tài)分配模型,使得模型能更為準(zhǔn)確地反映客流變化和乘客選乘行為.

4.1 客流動態(tài)分配模型

根據(jù)先前所述,城際列車分為三種類型,根據(jù)乘客選擇列車類型的不同將客流分為高速、中速和普速三個類別.為簡化模型,假設(shè)初始高速、中速客流已知,普速為零(此假設(shè)對結(jié)果無影響).

為準(zhǔn)確反映乘客選乘列車心理,下面對各類別客流動態(tài)分配過程進(jìn)行闡述.依據(jù)文中系統(tǒng)假設(shè),旅客按照自身客流類型優(yōu)先選擇相應(yīng)類型列車.已知si到sj的G型客流為hGij,若G型列車開行方案在si和sj不停站,此部分客流將進(jìn)行轉(zhuǎn)化,轉(zhuǎn)化過程中優(yōu)先選擇Z型列車,若Z型列車開行方案也不在si和sj停站,則選擇L型列車.Z型列車客流的轉(zhuǎn)化過程類似,轉(zhuǎn)化過程優(yōu)先選擇G型,其次是L型.這種轉(zhuǎn)化過程符合城際列車對速度和時間的高要求性,也符合乘客心理.

可列出任意兩站之間三種類型客流轉(zhuǎn)化的計(jì)算方程為

εKij表示K型列車是否同時si和sj停站,

當(dāng)且僅當(dāng)xKi=1,xKj=1時,εKij=1.

模型的動態(tài)性表現(xiàn)為:在運(yùn)算過程中,不斷生成停站方案εKij集合,然后以實(shí)際客流 h～Kij為因變量,εKij為自變量依據(jù)上述方程進(jìn)行運(yùn)算,生成與εKij集合相對應(yīng)的 h～Kij集合.在整個過程中,體現(xiàn)出客流分配相對于開行方案的動態(tài)性.

4.2 基于多類型列車開行方案的多目標(biāo)規(guī)劃模型

基于上述客流動態(tài)分配模型計(jì)算方程得到的動態(tài)客流矩陣,可建立后續(xù)的多目標(biāo)規(guī)劃模型. 4.2.1 模型目標(biāo)函數(shù)

(1)鐵路部門收益最大化.

鐵路部門運(yùn)營收入為客票收入與運(yùn)營成本之差,運(yùn)營成本包括固定成本和變動成本.固定成本對開行方案無影響,在此視為零.變動成本則主要體現(xiàn)在列車運(yùn)行時車公里費(fèi)用和停站費(fèi)用.由于無中途換乘情況,不需考慮換乘成本.

K型列車的總票價(jià)收入為

式中 pK表示K型列車的人公里票價(jià)率.

鐵路部門總收入為

根據(jù)城際列車的停站情況,列車運(yùn)行路段信息及車公里費(fèi)用,可得K型列車運(yùn)行總費(fèi)用

鐵路部門運(yùn)營總支出為

綜上可得,鐵路部門總收益

(2)旅客總支出最小化.

旅客的出行總支出包括票價(jià)支出和出行時間消耗.其中旅客的票價(jià)總支出CP即鐵路部門總票價(jià)收入,旅客時間消耗包括列車運(yùn)行過程的時間消耗和因中途停站造成的時間消耗兩部分.

K型列車在行駛過程中的總時間消耗為

搭乘K型列車停站時間總消耗為

搭乘K型列車上旅客總時間消耗為

旅客總時間消耗為

(3)最大限度滿足初始客流需求.

模型采用客流動態(tài)分配,即開行方案的不同會對實(shí)際客流選擇產(chǎn)生影響.應(yīng)盡量減小客流的轉(zhuǎn)化,以滿足初始客流需求.為定量地衡量開行方案不同所引起的客流矩陣的變化,采用總歐式距離EOD衡量實(shí)際客流矩陣與初始客流 OD矩陣的偏差.

最理想情況,EOD=0,此時

歐氏距離越小表示客流動態(tài)分配結(jié)果越接近初始客流,即越接近乘客初始需求.

4.2.2 模型的約束條件

(1)K型列車客座利用率為λK,路段ei(ei∈E)上K型列車的單向客流運(yùn)輸量為

當(dāng)K型列車以客座利用率λK,定員AK,服務(wù)頻率fK載客時,區(qū)段客流運(yùn)輸量不能超過該區(qū)段運(yùn)輸能力,即

上述約束等價(jià)于

(2)城際客運(yùn)專線上運(yùn)行列車數(shù)不大于各車站和區(qū)段通過能力上限.設(shè)區(qū)段ei通過能力上限為le(si),車站Si通過能力上限為ls(si),有

嚴(yán)躍進(jìn)：收購普洛斯這件事對萬科的意義很大，因?yàn)檫@標(biāo)志著萬科的物流布局正式走向了國際市場。但是物流項(xiàng)目屬于周期長、投資回報(bào)慢的重資產(chǎn)運(yùn)營，這也是萬科當(dāng)前不容忽視的問題。而且隨著企業(yè)物流板塊的規(guī)模不斷擴(kuò)張，盈利問題也將愈發(fā)凸顯。這就要萬科慎重考慮，如何在企業(yè)大戰(zhàn)略下，打好協(xié)同牌，以彌補(bǔ)物流地產(chǎn)存在的盈利問題。

(3)xKi∈{0,1},fK∈自然數(shù)集N.

4.2.3 綜合的多目標(biāo)非線性整數(shù)規(guī)劃模型

鐵路部門收益最大化:

旅客總支出最小化:

最大化滿足初始客流需求:

約束條件:

5 模型求解

本文建立的列車開行方案模型屬于較復(fù)雜的多目標(biāo)0-1整數(shù)規(guī)劃模型,為了增加算法適用性,本文采用遺傳算法進(jìn)行求解.求解過程如下:

本文模型包含眾多目標(biāo)函數(shù)和約束條件,根據(jù)各目標(biāo)的重要程度引入不同的權(quán)重因子ωi構(gòu)造適應(yīng)度函數(shù),將多目標(biāo)函數(shù)轉(zhuǎn)為單目標(biāo)函數(shù).通過罰函數(shù),將有約束問題轉(zhuǎn)為無約束問題[14].這樣可得到較為理想的適應(yīng)度函數(shù):式中 gj(X)為各約束條件,gj(X)≥0;m為約束條件數(shù)目;ψ(gj(X))為罰函數(shù).

Step 2 隨機(jī)生成開行方案集的初始種群.文中停站決策0-1變量xKi可直接用二進(jìn)制編碼,服務(wù)頻率fK用相應(yīng)位長的二進(jìn)制變量進(jìn)行編碼.

Step 3 客流動態(tài)分配與多目標(biāo)規(guī)劃模型的求解.

Step 3.1 根據(jù)開行方案生成相應(yīng)的預(yù)測實(shí)際客流,并計(jì)算得出目標(biāo)值.

Step 3.2 根據(jù)適應(yīng)度函數(shù)計(jì)算種群個體的適應(yīng)度,記錄當(dāng)前最優(yōu)個體.

Step 3.3 采用“比例選擇”策略進(jìn)行選擇.假設(shè)種群規(guī)模為popsize,那么個體i被選中的概率為

利用交叉、變異等操作生成下一代開行方案新個體.以交叉概率Pc交換兩條染色體部分基因,構(gòu)造下一代兩條新的染色體.若染色體可行則替換父代,否則重復(fù)交叉直至可行為止;以概率Pm變異染色體基因串.

Step 4 重復(fù)Step 3的操作,直至滿足最大迭代次數(shù)或最大停滯迭代次數(shù).

Step 5 輸出最優(yōu)個體.即列車服務(wù)頻率和停站模式所組成的最優(yōu)開行方案.

遺傳算法大致過程如圖2所示.

圖2 遺傳算法流程圖Fig.2 Genetic algorithm flow chart

6 數(shù)值算例

為了對算法進(jìn)行驗(yàn)證,構(gòu)造如圖3所示城際網(wǎng)絡(luò).路段上標(biāo)有該路段標(biāo)號和長度(km).

圖3 城際路網(wǎng)圖Fig.3 Intercity road network scheme

區(qū)段通過能力取每晝夜263對,始發(fā)終到站通過能力取350對,沿途站取200對.表1為模型所需的基本參數(shù)(數(shù)據(jù)來源于文獻(xiàn)[12]及網(wǎng)絡(luò)文獻(xiàn)).

表1 基本參數(shù)Table 1 Basic parameter

初始客流矩陣[15](人/日)為

算法的實(shí)現(xiàn)采用MATLAB R2010a自帶遺傳算法工具箱求解,ωi取1,種群規(guī)模popsize=50,根據(jù)經(jīng)驗(yàn)取交叉概率Pc=0.6,變異概率Pm=0.4,最大停滯迭代次數(shù)為15,最大迭代次數(shù)為100代.運(yùn)行結(jié)果為:需開行擇站停高速列車18(對),在s1,s3,s6停站,預(yù)測客流(人/日)分別為s1,s3之間4 560,s3,s6之間4 780,s1,s6之間3 631;擇站停中速列車9 (對),在s1,s5,s6停站,預(yù)測客流分別為s1,s5之間2 262,s5,s6之間2 241,s1,s6之間2 123;站站停普速列車20(對),預(yù)測客流

模型最終結(jié)果為:CI=816 300(元),CT= 2 089 100(元),EOD=20 064.

7 研究結(jié)論

本文提出了反映開行方案對客流的反饋影響動態(tài)客配模型,對乘客的選乘行為進(jìn)行了較為深入的分析.文中相關(guān)假設(shè)為模型建立與求解提供了必要的條件.考慮到乘客選乘行為的復(fù)雜性以及乘客出行時間需要、中轉(zhuǎn)換乘需求、運(yùn)輸環(huán)境變化等因素,模型應(yīng)進(jìn)一步完善,以適應(yīng)實(shí)際應(yīng)用的需要.

[1]王兆成.中長期鐵路網(wǎng)規(guī)劃研究[M].北京:中國鐵道出版社,2004.[WANG Z C.Medium and longterm railway network planning research[M].Beijing: China railway press,2004.]

[2]Bussieck M R,Kreuzer C,Zimmermann U T.Optimal lines for railway systems[J].European Journal of Operational Research,1997,96(1):54-63.

[3]Claessens M T,Vandijk N M,Zwaneveld P J.Cost optimal allocation of rail passenger lines[J].European Journal of Operational Research,1998,110(3): 474-489.

[4]Goossens J,Hoesel S T,Kroon L.A branch and cut approach for solving railway line-planning problems [J].Transportation Science,2004,38(3):379-393.

[5]Goossens J,Hoesel S T,Kroon L.On solving multitype line planning problem[J].European Journal of Operational Research,2006,168(2):403-424.

[6]Chang Y H,Yeh C H,Shen C C.A multi-objective model for passenger train services planning:application to Taiwan's high-speed rail line[J].Transportation Research Part B:Methodological,2000,34:91-106.

[7]馮楓.客運(yùn)專線高速客車開行方案的計(jì)算與評價(jià)[D].北京交通大學(xué),2006.[FENG F.High-speed train of passenger dedicated line operating scheme computing and evaluating[D]. Beijing JiaotongUniversity,2006]

[8]鄧連波.客運(yùn)專線相關(guān)旅客列車開行方案優(yōu)化研究[D].中南大學(xué),2007.[DENG L B.Study on the optimal problems of passenger train plan for dedicated passenger traffic line [D]. Central South University,2007.]

[9]張擁軍.高速列車開行方案研究[J].西南交通大學(xué)學(xué)報(bào),1998,33(5):400-404.[ZHANG Y J.High speed train operating scheme research[J].Journal of Southwest Jiao Tong University,1998,33(5): 400-404.]

[10]徐瑞華.客運(yùn)專線列車開行方案的優(yōu)化方法研究[J].同濟(jì)大學(xué)學(xué)報(bào),2005,33(12):1608-1703.[XU R H.Optimization method research of passenger dedicated line operating scheme[J].Journal of Tongji University,2005,33(12):1608-1703.]

[11]聶磊,胡小風(fēng),等.基于旅客列車開行方案的客流分配方法研究[J].交通運(yùn)輸系統(tǒng)工程與信息,2011, 11(3):87-92.[NIE L,HU X F,et al.Research of passenger flow assignment based on passenger train plann[J]. Journal of Transportation Systems Engineering and Information Technology,2011,11 (3):87-92.]

[12]徐鵬.城際客運(yùn)專線列車開行方案研究[D].成都:西南交通大學(xué),2010.[XU P.Research on the train operation scheme of the intercity dedicated passenger railway[D]. ChengDu: Southwest Jiao Tong University,2010.]

[13]彭其淵.客運(yùn)專線運(yùn)輸組織[M].北京:科學(xué)出版社,2007.[PENG Q Y.Passenger dedicated line transportation organization[M].Beijing: Science Press,2007.]

[14]賈曉秋.客運(yùn)專線網(wǎng)絡(luò)列車開行方案模型與算法研究[J].系統(tǒng)工程學(xué)報(bào),2011,26(2):216-221.[JIA X Q.Research on a model and its alogorithm about the line planning on the network for passenger transportation[J].Journal of Systems Engineering, 2011,26(2):216-221.]

[15]吳昌進(jìn).昌九城際軌道交通運(yùn)量預(yù)測及運(yùn)輸方案研究[D].北京:清華大學(xué),2008.[WU C J.Inter-city railway of Nanchang to Jiujiang traffic volume forecast and transport scheme Study[D].Beijing:Tsinghua University,2008.]

Intercity Train Operation Schemes Based on Passenger Flow Dynamic Assignment

PENG Hong-qin,ZHU Yu-jun
(Department of Urban Mass Transit,Beijing Jiaotong University,Beijing 100044,China)

This paper summarizes the research status of intercity train operating scheme.To precisely describe the interaction between passenger flow and operating scheme,it proposes assumptions of system closure,train type division,passenger flow dynamic assignment and selecting priority during the process of establishing model.Based on these,it describes relative variables and formulates the passenger flow dynamic assignment model to reflect the conversion process of different passenger types.Then it develops a multiple objective programming model considering maximum railway department revenue,the smallest passenger total expenditure and the maximum passenger demand.It also uses the genetic algorithm to solve the established multi-objective 0-1 integer programming model.Finally,a numerical example is provided to illustrate the effectiveness of this algorithm of model.

railway transportation;operation scheme;passenger flow dynamic assignment;multi-objective optimization;genetic algorithm

U292.3

A

U292.3

A

1009-6744(2013)01-0111-07

2012-10-10

2012-12-03錄用日期:2012-12-13

國家自然科學(xué)基金項(xiàng)目(71131001);國家基礎(chǔ)研究計(jì)劃項(xiàng)目(2012CB725406).

彭宏勤(1963-),男,湖北武漢人,副教授.

*通訊作者:hqpeng@bjtu.edu.cn