戶佐安 夏一鳴 鄭 磊

(西南交通大學(xué)交通運(yùn)輸與物流學(xué)院1) 成都 611756)(西南交通大學(xué)綜合交通大數(shù)據(jù)應(yīng)用技術(shù)國家工程實(shí)驗(yàn)室2) 成都 611756)

0 引 言

城市軌道交通列車的正常運(yùn)行容易因各類突發(fā)事件產(chǎn)生延誤，而較長時(shí)間的延誤則會(huì)導(dǎo)致列車大面積晚點(diǎn)和站臺(tái)乘客滯留.在這種情況下，常規(guī)的站站停運(yùn)行調(diào)整模式已經(jīng)不能很好地滿足盡快恢復(fù)列車正常運(yùn)行的要求[1].而跳停調(diào)整模式相較于站站停調(diào)整模式，能夠使列車通過跨站運(yùn)行從而更快地恢復(fù)至計(jì)劃運(yùn)行狀態(tài)，但同時(shí)也會(huì)導(dǎo)致部分乘客無法及時(shí)乘降，增加其乘車及候車時(shí)間.現(xiàn)階段城軌列車跳停方案的制定主要還是依據(jù)于調(diào)度員經(jīng)驗(yàn)及預(yù)案，在全局性上還存在不足.因此，為了制定更為合理的跳停方案，在恢復(fù)列車正常運(yùn)行的同時(shí)盡可能縮短乘客的旅行時(shí)間，建立行之有效的列車運(yùn)行調(diào)整模型和相應(yīng)求解算法就具有十分重要的意義.

國內(nèi)外學(xué)者針對(duì)城市軌道交通列車跳停問題已展開一定的研究.鄭鋰等[2]對(duì)列車停站方案進(jìn)行分類組合，建立了以乘客總出行時(shí)間節(jié)省最大為目標(biāo)的0-1規(guī)劃模型，并通過算例驗(yàn)證了模型的有效性.王嬋嬋等[3]從延誤情況下多線換乘站的工況、跳停需求、跳停方案影響因素，以及跳停效果等方面進(jìn)行分析，得出列車延誤時(shí)在多線換乘站的跳停方法，并通過實(shí)際案例分析了該方法的局限性.劉祥喜[4]對(duì)各類突發(fā)大客流的特征進(jìn)行分析，選取實(shí)際案例進(jìn)行客流預(yù)測，并建立了以運(yùn)營效率最高為目標(biāo)的停站方案優(yōu)化模型，最后提出突發(fā)大客流背景下的列車運(yùn)營組織策略.Cao等[5]以列車停站狀態(tài)為決策變量，建立乘客出行時(shí)間及列車總運(yùn)行時(shí)間的總節(jié)省量最大為目標(biāo)的0-1規(guī)劃模型，并通過實(shí)例驗(yàn)證了模型的有效性.Freyss等[6]采用近似連續(xù)法將列車跳停問題用線路的站點(diǎn)密度等連續(xù)參數(shù)進(jìn)行描述，并構(gòu)建以列車運(yùn)行成本最小為目標(biāo)的運(yùn)行調(diào)整模型，最后對(duì)跳停策略適用情況進(jìn)行總結(jié).Jamili等[7]對(duì)動(dòng)態(tài)客流條件下的列車跳停方案進(jìn)行研究，設(shè)計(jì)了一種將分解算法及模擬退火算法相結(jié)合的混合優(yōu)化算法，并用實(shí)例證明該算法的穩(wěn)定性.

綜上，現(xiàn)有研究大多都是針對(duì)于常規(guī)情況下的城軌列車跨站停車問題，跳停方案采用固定的列車分類組合停站模式，且沒有考慮因列車運(yùn)能不足而使乘客滯留的問題.而在延誤條件下，列車之間的運(yùn)行調(diào)整空間小，且站臺(tái)乘客容易出現(xiàn)積壓，跳停方案的制定還需要考慮列車運(yùn)行安全及列車運(yùn)能利用情況等等因素，因此現(xiàn)有研究成果并不適用于延誤條件下的列車跳停問題.本文基于某一列車延誤條件，以乘客總旅行時(shí)間最小為優(yōu)化目標(biāo)，考慮列車運(yùn)能約束、運(yùn)行約束，以及跳停約束，建立相應(yīng)模型與算法，以期制定更加靈活且合理的城市軌道交通列車跳停方案.

1 問題描述

1.1 跳停影響分析

列車跳停是指載客列車抵達(dá)某站后不進(jìn)行停車操作，直接運(yùn)行通過此站，圖1 為列車跳停示意圖.跳停對(duì)乘客出行的影響主要體現(xiàn)在以下三個(gè)方面.

圖1 列車跳停示意圖

1) 跳?？梢怨?jié)省列車i在跳停站j的停站時(shí)間及起停附加時(shí)間，從而減少部分乘客的乘車時(shí)間.

2) 跳停會(huì)導(dǎo)致出行起始站為跳停站j的乘客無法及時(shí)上車，使其必須等待下一趟同向列車i+1才能上車，增加其候車時(shí)間.

3) 跳停會(huì)導(dǎo)致出行終到站為跳停站j的乘客無法及時(shí)下車，而乘客在提前得知跳停信息后會(huì)出現(xiàn)兩種選擇：①在跳停站的前一站j-1下車，此時(shí)乘客需要額外花費(fèi)一次等候下一趟同向列車i+1的時(shí)間，才能到達(dá)出行終到站；②在跳停站的后一站j+1下車，此時(shí)乘客需要額外花費(fèi)從跳停站j乘至后一站j+1、在站j+1等候反向列車，以及乘坐反向列車到達(dá)站j的時(shí)間.

綜上可知，跳停調(diào)整模式在提高部分乘客出行效率的同時(shí)也會(huì)對(duì)一些乘客的出行產(chǎn)生負(fù)面影響.因此，當(dāng)某一列車發(fā)生延誤時(shí)，如何制定使整個(gè)乘客群體出行效率最高的列車運(yùn)行調(diào)整方案，是本文需要解決的主要問題.

1.2 問題假設(shè)

結(jié)合我國城市軌道交通實(shí)際調(diào)度情況，本文給出以下假設(shè).

1) 列車在線路的首站及末站均不組織跳停，列車不能連續(xù)跳停兩站，同一站點(diǎn)不能被連續(xù)跳停兩次.

2) 列車在恢復(fù)正點(diǎn)運(yùn)行后不再進(jìn)行調(diào)整.

3) 某線路1 h時(shí)段內(nèi)的站間OD數(shù)據(jù)已知，且各站客流的到達(dá)服從均勻分布.

2 城市軌道交通列車運(yùn)行調(diào)整模型

2.1 參數(shù)定義

模型相關(guān)參數(shù)定義見表1.

表1 參數(shù)定義

2.2 模型相關(guān)參數(shù)計(jì)算

本文將用列車出發(fā)時(shí)車內(nèi)人數(shù)、上車需求人數(shù)、實(shí)際上車人數(shù)、實(shí)際下車人數(shù)，以及車站滯留人數(shù)來描述客流與列車運(yùn)能之間的交互關(guān)系.

列車i在j站出發(fā)時(shí)的車內(nèi)人數(shù)與其在j-1站出發(fā)時(shí)的車內(nèi)人數(shù)及在j站的上下車人數(shù)有關(guān)，即

Pi,j=Pi,j-1+Bi,j-Ei,j

(1)

列車i在j站的實(shí)際上車人數(shù)決定于列車在該站的剩余載客能力能否滿足上車需求，以及列車在該站的跳停與否，即

(2)

式(2)中上車需求人數(shù)即為列車i-1在j站出發(fā)時(shí)的滯留人數(shù)與在時(shí)段[di-1,j,di,j]內(nèi)到達(dá)j站的人數(shù)之和，為

qi,j=li-1,j+δj(di,j-di-1,j)

(3)

式(3)中j站乘客到達(dá)速率δj可由OD表中的數(shù)據(jù)直接求出，即

(4)

由跳停影響分析可知，列車i在j站的下車人數(shù)與列車i在j站、j+1站以及j-1站的跳停與否有關(guān)，即

Ei.j=(Pi,j-1·θj·ξi,j+λ1·Pi,j·θj+1·ξi,j+1·

xi,j+1+λ2·Pi,j-2·θj-1·ξi,j-1·xi,j-1)(1-xi,j)

(5)

(6)

(7)

列車i離開j站時(shí)，j站滯留人數(shù)與列車i在j站面臨的上車需求人數(shù)、實(shí)際上車人數(shù)以及可能因跳停在j站提前下車的人數(shù)有關(guān)，即

li,j=qi,j-Bi,j+λ1·Pi,j·θj+1·ξi,j+1·xi,j+1

(8)

2.3 目標(biāo)函數(shù)

研究目標(biāo)是使乘客總旅行時(shí)間最小，乘客總旅行時(shí)間表示為T.乘客總旅行時(shí)間可分為站臺(tái)候車時(shí)間及乘車時(shí)間，分別表示為T1和T2，兩者計(jì)算為

(9)

(10)

式(9)中，第一項(xiàng)表示正常乘客候車時(shí)間，第二項(xiàng)表示滯留乘客候車時(shí)間，第三項(xiàng)表示乘客換乘反向列車時(shí)的候車時(shí)間，此時(shí)平均候車時(shí)間取I0/2；式(10)中，第一項(xiàng)表示車內(nèi)乘客站間乘車時(shí)間，第二項(xiàng)表示列車停站過程中不下車乘客的等待時(shí)間，第三項(xiàng)表示乘客乘坐反向列車時(shí)的乘車時(shí)間.

優(yōu)化目標(biāo)即為

minT=T1+T2

(11)

2.4 運(yùn)行約束

運(yùn)行約束條件有：

di.j=ai,j+wj(1-xi,j)

(12)

ai.j≥di,j-1+Rj-1-τ1·xi,j-1-τ2·xi,j

(13)

ai+1,j-di.j≥I1

(14)

ai+1,j-ai.j≥I2

(15)

di+1,j-di.j≥I2

(16)

di,j≥Di,j

(17)

式(12)為停站時(shí)間約束，由于縮短停站時(shí)間可能會(huì)導(dǎo)致積壓的乘客無法及時(shí)乘降，因此本文不對(duì)停站時(shí)間進(jìn)行調(diào)整；式(13)為列車區(qū)間運(yùn)行時(shí)間約束，即列車i在j-1站跳停則可節(jié)省起動(dòng)附加時(shí)間τ1，在j站跳停則可節(jié)省停車附加時(shí)間τ2；式(14)為列車最小發(fā)到間隔約束；式(15)為列車最小到達(dá)間隔約束；式(16)為列車最小發(fā)車間隔約束；式(17)為列車發(fā)車時(shí)刻約束.

2.5 跳停約束

跳停約束有：

xi.1=xi.m=0

(18)

xi.j+xi.j+1≤1

(19)

xi.j+xi+1.j≤1

(20)

式(18)為列車不能跳停首尾站；式(19)為列車不能連續(xù)跳停兩次；式(20)為同一站點(diǎn)不能被連續(xù)跳停兩次.

3 求解算法

目標(biāo)函數(shù)及部分約束條件為非線性，而遺傳算法具有優(yōu)秀的全局搜索能力及處理非線性系統(tǒng)優(yōu)化問題的能力，因此采用遺傳算法求解[8].但由于本文決策變量中，跳停變量的取值直接決定著列車的到發(fā)時(shí)刻關(guān)系，導(dǎo)致兩種變量無法同時(shí)參與迭代.為解決上述問題，設(shè)計(jì)了一個(gè)內(nèi)外層嵌套式遺傳算法，即外層遺傳算法對(duì)停站方案進(jìn)行優(yōu)化，內(nèi)層遺傳算法基于外層的停站方案對(duì)到發(fā)時(shí)刻方案進(jìn)行優(yōu)化.具體流程見圖2.

圖2 嵌套式遺傳算法求解流程

3.1 染色體編碼及種群初始化

設(shè)外內(nèi)層染色體分別為Xi和Yj，種群規(guī)模分別為S1和S2.其中:i=1,2,…,S1；j=1,2,…,S2.由于外層染色體由0-1變量構(gòu)成，因此外層遺傳算法采用二進(jìn)制編碼.為方便內(nèi)層編碼，本文將運(yùn)行時(shí)刻表中的到發(fā)時(shí)刻轉(zhuǎn)化為上午06:00:00至該時(shí)刻的間隔秒數(shù)，例如3 600即代表07:00:00這一時(shí)刻.由于內(nèi)層染色體由正整數(shù)構(gòu)成，因此內(nèi)層遺傳算法采用實(shí)數(shù)編碼.外內(nèi)層染色體結(jié)構(gòu)見圖3.

圖3 外內(nèi)層染色體結(jié)構(gòu)

假設(shè)列車I在第Q站發(fā)生初始延誤.對(duì)于外層種群的初始化，本文首先將染色體中第Q個(gè)及之前的基因全部設(shè)為0，隨后從第Q+1個(gè)基因開始將其隨機(jī)賦值為0或1，若違反跳停約束則令其為0.以此類推，直到形成符合跳停約束的個(gè)體Xi.循環(huán)上述操作S1次即形成初始種群X.

對(duì)于內(nèi)層種群的初始化，首先分析跳停次數(shù)最大情況下以及站站停調(diào)整模式下各列車在各站的到達(dá)時(shí)刻，并將這兩組時(shí)刻作為育種邊界，以此生成染色體中代表到達(dá)時(shí)刻的基因，隨后根據(jù)外層個(gè)體Xi和約束條件(12)生成代表出發(fā)時(shí)刻的基因，從而形成完整個(gè)體Yj.循環(huán)上述操作S2次即形成初始種群Y.

3.2 適應(yīng)度函數(shù)

染色體適應(yīng)度越大，表示其性能越好.因此內(nèi)層個(gè)體Yj的適應(yīng)度函數(shù)設(shè)計(jì)為

(21)

式中：C為一個(gè)足夠大的正整數(shù)；nk(Xi,Yj)為基于外層個(gè)體Xi生成的個(gè)體Yj違反第k個(gè)運(yùn)行約束的次數(shù)；p為懲罰因子且為正數(shù).

外層個(gè)體Xi的適應(yīng)度取內(nèi)層最優(yōu)個(gè)體Ybest對(duì)應(yīng)函數(shù)值的倒數(shù)，即

Fit(Xi)=1/T(Xi,Ybest)

(22)

3.3 種群演變策略

4 算例分析

4.1 基礎(chǔ)數(shù)據(jù)

以某城市地鐵線路為例.設(shè)線路共有20站，列車最大載客人數(shù)Cmax=1 400，計(jì)劃追蹤間隔I0=180 s，最小發(fā)到間隔I1=80 s，最小追蹤間隔I2=120 s.假設(shè)某列車在第二站因突發(fā)事故產(chǎn)生初始延誤，導(dǎo)致其在該站的出發(fā)時(shí)刻由08:01:40延誤至08:11:40.根據(jù)延誤時(shí)間可確定受延誤影響列車數(shù)n=10.

當(dāng)乘客的出行終到站被跳停時(shí)，由于在跳停站前一站下車的決策比在后一站下車所需額外花費(fèi)的時(shí)間明顯更少，因此本文設(shè)λ1=0.8，λ2=0.2.由文獻(xiàn)[9]可知城軌列車起停附加時(shí)間均在15 s左右，因此本文設(shè)τ1=τ2=15 s.

只研究線路單向跳停方案，該線路08:00:00-09:00:00時(shí)段內(nèi)的OD量,見表2.

表2 OD客流

設(shè)定的列車停站時(shí)間、計(jì)劃區(qū)間運(yùn)行時(shí)間及最小區(qū)間運(yùn)行時(shí)間分別如下(單位為s).

圖4 函數(shù)收斂曲線

4.2 結(jié)果分析

優(yōu)化后的列車運(yùn)行調(diào)整方案見圖5.

圖5 兩種調(diào)整方案下的列車運(yùn)行圖

為驗(yàn)證本模型的優(yōu)化效果，將影響集合范圍內(nèi)，計(jì)劃運(yùn)行方案、站站停調(diào)整方案,以及跳停調(diào)整方案下的乘客總旅行時(shí)間、站臺(tái)乘客候車時(shí)間與乘客乘車時(shí)間一一進(jìn)行對(duì)比(各時(shí)間的單位由s換為h，以方便目標(biāo)值的比對(duì))，跳停調(diào)整方案相對(duì)于站站停調(diào)整方案的優(yōu)化效果見表3.

由于算例中列車存在延誤情況，且設(shè)定列車在恢復(fù)正點(diǎn)運(yùn)行后均不再進(jìn)行調(diào)整，因此跳停調(diào)整方案與站站停調(diào)整方案下得到的乘客總旅行時(shí)間必然大于計(jì)劃值.但由表3可知，在站臺(tái)乘客候車時(shí)間方面，模型求解得到的跳停調(diào)整方案相較于站站停調(diào)整方案，可以縮短6.6%因延誤而產(chǎn)生的額外站臺(tái)乘客候車時(shí)間；而在乘客乘車時(shí)間方面，模型求解得到的跳停調(diào)整方案和站站停調(diào)整方案相比于計(jì)劃運(yùn)行方案均能夠有效縮減乘客的乘車時(shí)間，但跳停調(diào)整方案的縮減效果更加明顯.最后在整體層面上，結(jié)果表明本模型求解得到的跳停調(diào)整方案能夠顯著減少64.8%由列車延誤帶來的額外乘客總旅行時(shí)間.由此證明，在列車延誤條件下，建立的運(yùn)行調(diào)整模型與算法在應(yīng)對(duì)城軌列車運(yùn)行調(diào)整問題上具有有效性及優(yōu)越性.

表3 結(jié)果對(duì)比

5 結(jié) 束 語

文中從乘客的角度出發(fā)，分析列車跳停對(duì)乘客出行的影響，并結(jié)合城市軌道交通實(shí)際調(diào)度情況，考慮客流與列車運(yùn)能之間的交互關(guān)系及列車延誤情況下列車跳停需考慮的約束，建立了以乘客總旅行時(shí)間為目標(biāo)函數(shù)的運(yùn)行調(diào)整優(yōu)化模型，并根據(jù)模型特點(diǎn)設(shè)計(jì)了嵌套式遺傳算法來對(duì)模型進(jìn)行求解.最后通過設(shè)計(jì)算例證明了本文模型及算法的有效性及優(yōu)越性，可為城市軌道交通列車延誤條件下的實(shí)際調(diào)度提供理論支持.文中研究的前提之一是客流的到達(dá)為均勻分布，這與實(shí)際情況略有差別，因此動(dòng)態(tài)客流下跳停方案的制定有待進(jìn)一步深入研究.