面向O-D時(shí)變需求的城軌列車運(yùn)行計(jì)劃優(yōu)化方法

史 峰，涂 纖，趙 爍

(中南大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長沙 410075)

城市軌道交通(簡稱城軌)線路的運(yùn)行效率與服務(wù)水平在很大程度上取決于列車運(yùn)行計(jì)劃。高品質(zhì)的列車運(yùn)行計(jì)劃通常需要權(quán)衡乘客和企業(yè)兩方面的利益，一方面為乘客提供較優(yōu)質(zhì)的服務(wù)，另一方面為企業(yè)降低運(yùn)行成本[1]。

列車運(yùn)行計(jì)劃包括列車時(shí)刻表與列車周轉(zhuǎn)方案?，F(xiàn)有列車時(shí)刻表的研究更多地關(guān)注降低乘客出行費(fèi)用，如減少乘客的候車時(shí)間[2]、換乘時(shí)間[3]和總旅行時(shí)間[4],以及優(yōu)化周期性列車時(shí)刻表[5]，文獻(xiàn)[6]綜合考慮了乘客出行費(fèi)用和企業(yè)運(yùn)行成本，但這些研究均假定全天出行需求為固定常數(shù)或是均勻到達(dá)車站的理想客流。實(shí)際上，旅客出行需求具有隨時(shí)間的波動(dòng)性，這種具有時(shí)間波動(dòng)性的出行需求稱為時(shí)變需求[7]。文獻(xiàn)[8]基于客流O-D時(shí)變需求，考慮列車對(duì)數(shù)與上座率，設(shè)計(jì)了優(yōu)化列車發(fā)車時(shí)間間隔的遺傳算法，降低了乘客的等待時(shí)間。文獻(xiàn)[9]以德國市郊鐵路為背景，強(qiáng)調(diào)指出需確定靈活的列車間隔以適應(yīng)客流的時(shí)變性。文獻(xiàn)[10]和文獻(xiàn)[11]建立了基于彈性需求的乘客列車開行方案的雙層規(guī)劃模型，并設(shè)計(jì)了基于模擬退火算法求解的優(yōu)化算法。列車時(shí)刻表的實(shí)施必須由列車周轉(zhuǎn)方案來保障[12]。文獻(xiàn)[13]基于給定的車輛運(yùn)行時(shí)刻表，針對(duì)單車場(chǎng)研究了車輛調(diào)度問題。綜合優(yōu)化列車運(yùn)行計(jì)劃的問題非常復(fù)雜，研究成果較少。文獻(xiàn)[14]針對(duì)城軌線路時(shí)變斷面需求，提出了滿足服務(wù)水平的列車時(shí)刻表和列車周轉(zhuǎn)方案的兩階段優(yōu)化方法。同時(shí)，文獻(xiàn)[15]對(duì)城軌列車運(yùn)行計(jì)劃的優(yōu)化具有一定的參考價(jià)值。以上文獻(xiàn)雖然未能有效解決面向O-D時(shí)變需求的城軌線路列車運(yùn)行計(jì)劃優(yōu)化問題，但是在優(yōu)化思想、優(yōu)化方法上有一定的啟發(fā)作用。

本文在上述文獻(xiàn)研究成果的基礎(chǔ)上，針對(duì)城軌線路的O-D時(shí)變需求，以具有單一盡頭車場(chǎng)的城軌線路為研究背景，提出基于列車時(shí)刻表的客流分配方法，在給定乘客服務(wù)水平的限制下，實(shí)現(xiàn)O-D時(shí)變需求與列車時(shí)刻表的耦合，進(jìn)而以列車對(duì)數(shù)和列車車底數(shù)最小化為目標(biāo)，構(gòu)建了列車時(shí)刻表和列車周轉(zhuǎn)的2階段優(yōu)化模型，并提出了2階段求解算法。

1 列車運(yùn)行計(jì)劃優(yōu)化問題

城軌線路具有m個(gè)車站s1,s2,…,sm，記全體車站集為S。車站s1至sm為線路的下行方向D，車站sm至s1為上行方向U。列車從車站su至sv的旅行時(shí)間與車站sv的停站時(shí)間之和為τ(su,sv)。端點(diǎn)站s1和sm的列車停放能力分別為N1和Nm(含立即折返列車)，折返作業(yè)時(shí)間分別為r1和rm。全天運(yùn)營時(shí)段為[T1,T2]。

1.1 列車運(yùn)行計(jì)劃

列車周轉(zhuǎn)方案主要受車場(chǎng)布局的影響，城軌線路上有很多種車場(chǎng)布局形式，每種布局形式對(duì)應(yīng)不同類型的列車周轉(zhuǎn)方案。本文以單一盡頭車場(chǎng)為背景，討論列車時(shí)刻表與列車接續(xù)的優(yōu)化問題。具有單一盡頭車場(chǎng)的城市軌道線路及列車運(yùn)行組織形式特征如下：

線路僅有1個(gè)車場(chǎng)p且與端點(diǎn)站s1鄰接，且車場(chǎng)p無能力限制；若車站s1達(dá)到飽和，則新到達(dá)列車必須停放至車場(chǎng)p；若車站sm達(dá)到飽和，則只能等待車站sm有列車駛離后才能到達(dá)列車。

由此可見，所有早班列車均由車場(chǎng)p提供給車站s1，列車從車站s1出發(fā)，到達(dá)車站sm，或折返回車站s1，或停留于車站sm；列車到達(dá)車站s1后，可折返回車站sm，也可停放在車站，還可返回車場(chǎng)；所有晚班列車均返回車場(chǎng)p。

1.2 乘客服務(wù)水平

從以下3個(gè)方面來考慮乘客服務(wù)水平。

(2)發(fā)車時(shí)間間隔限制：最小發(fā)車時(shí)間間隔為τmin，最大發(fā)車時(shí)間間隔為τmax。

(3)列車載客量限制：列車載客能力為C，常規(guī)載客系數(shù)為α(0<α<1)。列車斷面載客量一般不超過αC，除非列車按最小發(fā)車時(shí)間間隔發(fā)車。當(dāng)列車按最小發(fā)車時(shí)間間隔發(fā)車時(shí)，列車最大斷面載客量達(dá)到αC，但不超過列車載客能力C，超過載客能力C的需求作為車站滯留客流。

1.3 列車運(yùn)行計(jì)劃優(yōu)化

2 基于列車時(shí)刻表的客流分配

基于列車時(shí)刻表的客流分配就是模擬乘客的上車行為，根據(jù)每趟列車到達(dá)每個(gè)車站時(shí)列車上的客流量、下車人數(shù)和列車容量，計(jì)算列車在每一站的剩余能力，確定可以上車的乘客數(shù)。超過上車數(shù)量的乘客作為滯留客流，各站的滯留客流量按終點(diǎn)分別記錄。當(dāng)需求量超過上車數(shù)量時(shí)，各終點(diǎn)的需求量按照等比例原則上車，以便適度體現(xiàn)“先到先走”的原則。

基于給定的列車時(shí)刻表，分別計(jì)算雙向各站滯留客流量和客流量。

1)下行方向

按照k=1,2,…,n;u=1,2,…,m-1;v=u+1,u+2,…,m的順序，依次遞推求解滯留客流量和客流量如下。

首先，求解滯留客流總量，即

(1)

(2)

(3)

(4)

2)上行方向

按照k=1,2,…,n;u=m,m-1,…,2;v=u-1,u-2,…,1的順序，依次遞推求解滯留客流量和客流量如下。

首先，求解滯留客流總量，即

(5)

(6)

(7)

(8)

3 列車時(shí)刻表優(yōu)化模型

列車發(fā)車時(shí)刻相關(guān)的約束條件如下。

(9)

(10)

綜合考慮以上2部分內(nèi)容，獲得首班車發(fā)車時(shí)間約束為

(11)

(12)

(2)末班車的最早發(fā)車時(shí)間約束。表示為

(13)

(14)

(3)最小發(fā)車時(shí)間間隔約束。同一方向發(fā)車時(shí)間間隔不得小于最小發(fā)車時(shí)間間隔，即

(15)

(16)

(4)最大發(fā)車時(shí)間間隔約束。同一方向發(fā)車時(shí)間間隔不得大于最大發(fā)車時(shí)間間隔，即

(17)

(18)

(5)列車在各站發(fā)車時(shí)間與始發(fā)時(shí)間的關(guān)系

由于τ(s1,su),τ(sm,su)分別表示列車在區(qū)段(s1,su),(sm,su)的旅行時(shí)間與車站su的停站時(shí)間之和，所以滿足如下關(guān)系。

(19)

(20)

(6)無車場(chǎng)端車站sm列車接續(xù)約束。第i趟上行列車出發(fā)前，第i趟下行列車必須到達(dá)車站sm。由于τ(s1,sm)表示列車在區(qū)段(s1,sm)的旅行時(shí)間與車站sm的停站時(shí)間之和，rm為車站sm的折返作業(yè)時(shí)間，所以

(21)

(7)無車場(chǎng)端車站sm停車能力約束。第i趟下行列車到達(dá)車站sm之前，第i-Nm趟上行列車必須離開車站sm。由于τ(s1,sm)表示列車在區(qū)段(s1,sm)的旅行時(shí)間與車站sm的停站時(shí)間之和，rm為車站sm的折返作業(yè)時(shí)間，所以

(22)

(8)出行需求與列車始發(fā)時(shí)間的耦合。若按最小發(fā)車時(shí)間間隔發(fā)車，則列車最大斷面載客量達(dá)到常規(guī)載客能力αC，但不超過最大載客能力C；否則，列車斷面載客量不超過常規(guī)載客能力αC。即

(23)

(24)

(25)

(26)

以列車對(duì)數(shù)n最小化為優(yōu)化目標(biāo)函數(shù)，以上述關(guān)系式為約束條件，構(gòu)建列車時(shí)刻表的優(yōu)化模型為

minZ=n

(27)

s.t.

約束條件式(1)—式(26)。

4 列車時(shí)刻表優(yōu)化算法

4.1 算法思想

將求解步驟分為3步：最大化首班車發(fā)車時(shí)間、最大化中間列車發(fā)車時(shí)間、終止條件。

(28)

(29)

對(duì)于下行方向，分別考慮以下3種情形。

3)終止條件

根據(jù)上述算法思想和相應(yīng)步驟，設(shè)計(jì)模型式(1)—式(27)的求解算法。

4.2 列車最晚發(fā)車時(shí)間的雙向關(guān)聯(lián)序列化優(yōu)化算法

開始

i←2,j←2；

開始1

i←i+1,j←j+1}；

j←j+1}；

返回1

i←i-1,j←j-1；

n←i；

結(jié)束。

5 列車周轉(zhuǎn)方案優(yōu)化方法

5.1 列車周轉(zhuǎn)方案優(yōu)化模型

車站s1始發(fā)的下行列車車次序集為{i|i=1,2,…,n}，終到的上行列車車次序集為{j|j=1,2,…,n}，列車周轉(zhuǎn)問題就是要確定這2個(gè)方向列車車次的銜接關(guān)系。每1趟始發(fā)的下行列車，或者由此前到達(dá)的上行列車來擔(dān)當(dāng)，或者由來自車場(chǎng)p的列車來擔(dān)當(dāng)。我們采用指派問題描述列車周轉(zhuǎn)問題。

借助于指派問題優(yōu)化求解列車周轉(zhuǎn)問題，就是優(yōu)化{j|j=1,2,…,n}與{i|i=1,2,…,n}之間的指派M。指派滿足以下限制：M?{(j,i)|j,i=1,2,…,n}， 對(duì)于任何(j,i), (j′,i′)∈M，滿足若j=j′，則i≠i′；若i=i′，則j≠j′。對(duì)于任何j=1,2,…,n,i=1,2,…,n,定義指派費(fèi)用cji如下。

(30)

式中：K為充分大的數(shù)，通常取K=24nh。

定義指派變量

(31)

可建立列車周轉(zhuǎn)問題的指派模型為

(32)

s.t.

(33)

(34)

xji=0, 1j，i=1,2,…,n

(35)

指派模型的式(30)—式(35)以接續(xù)時(shí)間最小化為優(yōu)化目標(biāo)，等價(jià)于不可接續(xù)車次數(shù)量最小，全部列車運(yùn)用小時(shí)數(shù)最小，進(jìn)而列車車底數(shù)最小。

(36)

5.2 列車周轉(zhuǎn)方案優(yōu)化算法

匈牙利算法可以用來求解指派問題的最優(yōu)解。采用匈牙利算法對(duì)建立的指派模型進(jìn)行求解，算法分為以下2步。

第1步：用匈牙利算法求解指派問題最優(yōu)解的方法求解最優(yōu)指派方案M*。

6 算例分析

以北京市地鐵5號(hào)線為例，對(duì)本文的方法進(jìn)行驗(yàn)證。該線路上共23個(gè)車站，如圖1所示，天通苑北—宋家莊為下行方向，天通苑北站有太平莊車輛段。列車在立水橋、大屯路東、惠新西街南口、雍和宮、東四、東單、磁器口、蒲黃榆站的停站時(shí)間為45 s，其它車站停站時(shí)間為30 s。區(qū)間運(yùn)行時(shí)間參考首班列車各站發(fā)車時(shí)間與停站時(shí)間推算出，

圖1 車站及區(qū)間運(yùn)行時(shí)間(單位：s)

采用該線2014年某天的實(shí)際乘車O-D客流數(shù)據(jù)作為時(shí)變需求，篇幅所限，不詳細(xì)列舉。為了增加客流需求強(qiáng)度，將該O-D客流需求放大2倍作為算例的O-D客流需求。

利用優(yōu)化方法求出列車運(yùn)行計(jì)劃如圖2所示，圖中車站s1與車站sm之間的線段為列車運(yùn)行線，簡略起見，沒有標(biāo)記沿途停站的時(shí)間信息。車站s1與車站sm外側(cè)的折線表示列車的接續(xù)關(guān)系。車站s1外側(cè)的實(shí)心箭頭表示列車來自或返回車場(chǎng)，空心箭頭表示列車在車場(chǎng)接續(xù)，以解決車站s1不滿足停放能力N1的困難。D與數(shù)字的組合表示下行方向列車車次，U與數(shù)字的組合表示上行方向列車車次，為避免車次標(biāo)記過于密集，車次標(biāo)記間隔大約為10趟列車。

優(yōu)化產(chǎn)生的列車運(yùn)行計(jì)劃，開行列車194對(duì)，需要列車62列，列車接續(xù)時(shí)間為850.36 min，往返車場(chǎng)124次。

從圖2可以看出，在早晚高峰具有較密集的列車開行頻率，發(fā)車時(shí)間間隔隨著客流需求變化而變化，具有較平滑的變化規(guī)律。下面分別對(duì)折返站列車接續(xù)狀態(tài)、發(fā)車時(shí)間間隔、主導(dǎo)方向成因分析如下。

1)折返站列車接續(xù)狀態(tài)

為了分析折返站sm的列車接續(xù)狀態(tài)，從圖2可以看出：列車接續(xù)狀態(tài)大體可分為3個(gè)階段，第1階段為立即折返，第2階段為停車能力持續(xù)飽和，第3階段為立即折返。

比較雙向列車在折返站sm的始發(fā)終到時(shí)刻發(fā)現(xiàn)：

下行列車1至36與上行列車1至36均由立即折返的方式接續(xù)，即接續(xù)時(shí)間均為折返作業(yè)時(shí)間rm=2 min。下行列車37與上行列車37的接續(xù)時(shí)間超過折返作業(yè)時(shí)間rm，此后，接續(xù)時(shí)間不斷增加，折返站sm開始停放暫時(shí)不需要的列車，停車能力飽和率越來越大。

圖2 城軌線路列車運(yùn)行計(jì)劃示意圖

上行列車44的發(fā)車，釋放了折返站sm處于飽和的停車能力，保證下行列車46能夠終到車站sm(依據(jù)如下：下行列車46的終到時(shí)間等于上行列車44的始發(fā)時(shí)間，但下行列車45的終到時(shí)間大于上行列車43的始發(fā)時(shí)間)。此后，折返站sm進(jìn)入了停車能力持續(xù)飽和狀態(tài)。

下行列車104的終到，終止了停車能力持續(xù)飽和狀態(tài)(依據(jù)如下：下行列車104的終到時(shí)間略小于上行列車102的始發(fā)時(shí)間，但下行列車103的終到時(shí)間等于上行列車101的始發(fā)時(shí)間)。此后，車站sm的停車能力飽和率越來越小，進(jìn)而變得完全不飽和，折返時(shí)間越來越短，直至下行列車112與上行列車112仍然不是按照立即折返的方式接續(xù)。下行列車113至194與上行列車113至194均由立即折返的方式接續(xù)。

立即折返與停車能力持續(xù)飽和分別表示不同方向的需求主導(dǎo)。立即折返意味著上行方向?yàn)橹鲗?dǎo)方向，即上行方向按上行需求開行列車，下行方向?yàn)樯闲蟹较蚣皶r(shí)提供列車。折返站停車能力持續(xù)飽和意味著下行方向?yàn)橹鲗?dǎo)方向，即下行方向按下行需求開行列車，上行方向?yàn)橄滦薪K到折返站而及時(shí)釋放停車能力。

2)發(fā)車間隔時(shí)間

為了分析發(fā)車間隔時(shí)間，將上下行2個(gè)方向相鄰列車發(fā)車間隔時(shí)間變化規(guī)律如圖3所示。圖中第i個(gè)藍(lán)色菱形標(biāo)記下行列車i與下行列車i+1的發(fā)車間隔時(shí)間，第j個(gè)紅色加號(hào)標(biāo)記上行列車j與上行列車j+1的發(fā)車間隔時(shí)間。

圖3 列車運(yùn)行間隔時(shí)間示意圖

從圖3可以看出：對(duì)于列車i=1,2,…,36，與列車i+1的發(fā)車間隔時(shí)間曲線，上下行方向的變化規(guī)律完全一致，只是下行方向提前了τ(s1,sm)+rm=53 min 5 s，這是由上行方向主導(dǎo)的原因所致。

上行方向在這一階段的主導(dǎo)地位結(jié)束于下行列車37的終到，下行方向需求加大，發(fā)車間隔時(shí)間變小，下行列車發(fā)車間隔時(shí)間曲線出現(xiàn)了1個(gè)折點(diǎn)，但上行列車的發(fā)車間隔時(shí)間仍然在增加。直至上行列車43的終到，上下行分別按照各自需求確定發(fā)車間隔時(shí)間，密集到達(dá)、暫不需要的下行列車可以停放在折返站sm備用。

上行列車43與44的發(fā)車間隔時(shí)間有1個(gè)突變，就是圖3中被圓圈所包圍加號(hào)對(duì)應(yīng)的孤立點(diǎn)，此時(shí)上行列車44必須發(fā)車，以釋放折返站sm處于飽和的停車能力，保證下行列車46能夠終到車站sm。此后上行列車i的發(fā)車時(shí)刻與下行列車i+2在折返站sm的終到時(shí)刻保持相等，體現(xiàn)了下行方向的主導(dǎo)地位，致使上行列車的發(fā)車間隔時(shí)間與下行列車的發(fā)車時(shí)間間隔保持一致。

下行方向在這一階段的主導(dǎo)地位結(jié)束于下行列車104的終到，上行方向需求加大，發(fā)車間隔時(shí)間大幅下降，但下行列車的發(fā)車間隔時(shí)間仍然緩慢下降。直至下行列車112的終到，上下行分別按照各自需求確定發(fā)車間隔時(shí)間，上行列車出發(fā)較下行列車到達(dá)的列車缺額，由折返站sm停放的列車填補(bǔ)。

下行列車112與113的發(fā)車間隔時(shí)間有1個(gè)突變，就是圖3中被圓圈所包圍菱形符號(hào)對(duì)應(yīng)的孤立點(diǎn)，此時(shí)下行列車113必須到達(dá)折返站sm，以立即折返的接續(xù)方式擔(dān)當(dāng)上行列車113，保證上行列車113能夠準(zhǔn)時(shí)始發(fā)。此后下行列車的發(fā)車間隔時(shí)間與上行列車的發(fā)車間隔時(shí)間保持一致，體現(xiàn)了上行方向的主導(dǎo)地位。

3)主導(dǎo)方向成因

各個(gè)階段主導(dǎo)方向的成因與需求大小相關(guān)，與折返站沒有車場(chǎng)也相關(guān)。折返站沒有車場(chǎng)導(dǎo)致上行列車k比下行列車k的需求滯后約1 h，使得上下行需求大小必須進(jìn)行錯(cuò)位比較。由此分析3個(gè)階段的主導(dǎo)方向成因如下。

在第1階段，下行列車更接近于早班低谷，上行列車更接近于早高峰，可見上行列車的需求更大一些，所以上行方向?yàn)橹鲗?dǎo)方向。

在第2階段，下行列車更接近于早高峰，上行列車更接近于中午低谷，可見下行列車的需求更大一些，所以下行方向?yàn)橹鲗?dǎo)方向。

在第3階段，階段前期，下行列車更接近于中午低谷，上行列車更接近于晚高峰，可見上行列車的需求更大一些，所以上行方向?yàn)橹鲗?dǎo)方向。階段后期，由于上行方向晚高峰持續(xù)時(shí)間更長一些，所以一直保持上行方向?yàn)橹鲗?dǎo)方向。在晚班期間，上下行列車都按照最大間隔時(shí)間τmax=15 min發(fā)車，自然也都是立即折返了。

綜上所述，折返站列車接續(xù)狀態(tài)、發(fā)車間隔時(shí)間和各階段的主導(dǎo)方向成因都反映了列車運(yùn)行計(jì)劃具有顯著的合理性，這得歸功于結(jié)合客流分配和服務(wù)水平優(yōu)化列車運(yùn)行計(jì)劃，使得列車運(yùn)行計(jì)劃與乘客出行需求的吻合度高，列車開行趟數(shù)和車底數(shù)量最小化。

7 結(jié) 論

(1)城軌線路列車運(yùn)行計(jì)劃優(yōu)化問題可以描述為基于服務(wù)水平的列車時(shí)刻表和列車周轉(zhuǎn)2階段優(yōu)化問題，最小化開行列車對(duì)數(shù)和列車車底數(shù)，優(yōu)化有車場(chǎng)端列車接續(xù)關(guān)系。對(duì)于給定的列車時(shí)刻表，關(guān)于O-D時(shí)變需求的客流分配可以通過遞推公式獲得，由此可實(shí)現(xiàn)客流需求與列車時(shí)刻表的耦合。

(2)針對(duì)具有單一盡頭車場(chǎng)的城軌線路，在無車場(chǎng)端的列車接續(xù)和停車能力約束下，結(jié)合O-D時(shí)變需求的客流分配，可采用序列化優(yōu)化方法，分步實(shí)施最大化列車發(fā)車時(shí)間，實(shí)現(xiàn)雙向列車時(shí)刻表關(guān)聯(lián)優(yōu)化。

(3)基于最優(yōu)列車時(shí)刻表，將有車場(chǎng)端的列車周轉(zhuǎn)問題描述為指派問題，一個(gè)指派模型可同時(shí)確定端點(diǎn)站的列車最優(yōu)接續(xù)關(guān)系、往返于車場(chǎng)的列車。

(4)具有單一盡頭車場(chǎng)的城軌線路的列車運(yùn)行計(jì)劃，上行方向發(fā)車間隔時(shí)間比下行方向發(fā)車間隔時(shí)間的變化規(guī)律滯后。在上行方向?yàn)橹鲗?dǎo)的時(shí)間段，滯后稍大；在下行方向?yàn)橹鲗?dǎo)的時(shí)間段，滯后稍小。