考慮替開(kāi)與均衡性的城軌列車運(yùn)行調(diào)整

楚彭子 虞 翊 董丹陽(yáng) 袁建軍 陳義軍

(同濟(jì)大學(xué)道路與交通工程教育部重點(diǎn)實(shí)驗(yàn)室1) 上海 201804) (同濟(jì)大學(xué)磁浮交通工程技術(shù)研究中心2) 上海 201804)

0 引 言

城市軌道交通(城軌)系統(tǒng)具有大運(yùn)量與高密度運(yùn)行的特征，由不確定因素造成的運(yùn)行延誤與中斷事件，根據(jù)運(yùn)行計(jì)劃偏離程度，可分為擾動(dòng)和中斷[1]．?dāng)_動(dòng)所造成的列車延誤較小，可通過(guò)改變停站時(shí)間、折返時(shí)間和區(qū)間運(yùn)行速度等方式恢復(fù)運(yùn)行計(jì)劃．中斷的影響程度則較大，通常需要采用跳停、加開(kāi)、減少線上列車、變更交路等措施．

制定可靠的列車運(yùn)行調(diào)整方案，提高乘客出行的順暢性一直是國(guó)內(nèi)外研究熱點(diǎn)．柏赟等[2]關(guān)注了列車運(yùn)行的總晚點(diǎn)時(shí)間和到發(fā)均衡性，構(gòu)建了列車運(yùn)行調(diào)整模型，并借助遺傳算法進(jìn)行求解．針對(duì)因初始延誤較大導(dǎo)致初始延誤列車與前方列車(前車)之間運(yùn)力不足的現(xiàn)象，劉峰博等[3]以乘客出行總時(shí)間最小為目標(biāo)建立了優(yōu)化模型，并設(shè)計(jì)了組合動(dòng)態(tài)規(guī)劃求解算法．盧佐安等[4]探討了延誤條件下列車“跳?！辈呗裕瑯?gòu)建了混合整數(shù)規(guī)劃模型，并設(shè)計(jì)嵌套式遺傳算法進(jìn)行求解．將初始延誤列車的前車納入考慮范圍，盧佐安等[5]進(jìn)一步提出含有趕點(diǎn)、扣車、跳停的列車運(yùn)行全過(guò)程調(diào)整方法，涉及以乘客旅行總時(shí)間最小的優(yōu)化模型和嵌套式遺傳算法．針對(duì)故障后的運(yùn)行調(diào)整，Gao等[6]通過(guò)引入“跳?！狈桨?，建立了以提高列車周轉(zhuǎn)速度和降低乘客等待時(shí)間為目標(biāo)的整數(shù)規(guī)劃模型．Yin等[7]探討了增開(kāi)備車與調(diào)整列車運(yùn)行次序的手段來(lái)盡快疏散站臺(tái)滯留乘客．何占元等[8]針對(duì)故障結(jié)束、線路恢復(fù)階段客流需求，綜合考慮正線列車、備車及車輛段列車，結(jié)合“跳?！辈呗詷?gòu)建了以列車到達(dá)終點(diǎn)站時(shí)間總和最小為目標(biāo)的優(yōu)化模型．

綜上，總晚點(diǎn)時(shí)間、到發(fā)均衡性、列車運(yùn)行效率,以及乘客出行總時(shí)間等為列車運(yùn)行調(diào)整常見(jiàn)優(yōu)化目標(biāo)，而跳停、加開(kāi)備車或車輛段列車、趕點(diǎn)、扣車等為常見(jiàn)優(yōu)化策略．值得關(guān)注的是，作為一種列車運(yùn)行調(diào)整策略，“替開(kāi)”的應(yīng)用尚未得到充分討論，尤其是針對(duì)初始延誤較大的場(chǎng)景．同時(shí)，提高列車到發(fā)均衡性有助于保證乘客服務(wù)水平．基于此，文中針對(duì)因車輛故障導(dǎo)致較大初始延誤的情形，以“替開(kāi)”為手段，兼顧列車到發(fā)均衡性以及總晚點(diǎn)時(shí)間，開(kāi)發(fā)多目標(biāo)優(yōu)化模型與算法，為相應(yīng)場(chǎng)景下列車運(yùn)行調(diào)整制定可行方案．

1 模型準(zhǔn)備

1.1 問(wèn)題描述

圖1為考慮替開(kāi)的列車運(yùn)行調(diào)整示意圖．列車i在車站3突發(fā)車載信號(hào)設(shè)備故障只能降低駕駛模式低速運(yùn)行，若列車按該模式運(yùn)行至終點(diǎn)站，勢(shì)必會(huì)影響其后方列車，導(dǎo)致較大的晚點(diǎn)．此時(shí)，如果車站4具備存車線，且存車線存有一列備車，則可使用備車“替開(kāi)”列車i車次，還可將列車i盡快停放在車站4存車線上，以降低對(duì)后車的影響，見(jiàn)圖1中虛線．值得注意的是，由列車i導(dǎo)致的初始延誤可能對(duì)列車服務(wù)的均衡性產(chǎn)生影響，很容易造成類似于列車i和列車i-1之間運(yùn)力不足的現(xiàn)象．

圖1 考慮替開(kāi)的列車運(yùn)行調(diào)整示意

針對(duì)圖1所示的服務(wù)不均問(wèn)題，文中通過(guò)控制前車晚點(diǎn)時(shí)間，并協(xié)調(diào)備車與前車，以使得運(yùn)行計(jì)劃恢復(fù)期間列車的到發(fā)時(shí)分更加均衡．也就是說(shuō)，該問(wèn)題可理解為如何調(diào)節(jié)不同列車在不同車站的到發(fā)時(shí)分來(lái)保證運(yùn)行計(jì)劃恢復(fù)期間列車服務(wù)的均衡性以及準(zhǔn)時(shí)性．

1.2 假設(shè)條件

根據(jù)圖1場(chǎng)景特征及問(wèn)題范圍，結(jié)合城市軌道交通運(yùn)營(yíng)需求，給出了以下基本假設(shè).

假設(shè)1列車運(yùn)行順序是已知的，不存在次序變化的情況．

假設(shè)2客流相對(duì)較小，較小延誤不至于導(dǎo)致客流大范圍擁堵的情況．

假設(shè)3列車采用站站停的運(yùn)行方式，無(wú)“跳?！边\(yùn)行的情況．

假設(shè)4涉及的場(chǎng)景中只需一列備車就可以較好地服務(wù)乘客，且備車存放或上線位置距離初始延誤發(fā)生位置較近．

假設(shè)5類似于文獻(xiàn)[3]，初始延誤列車及其后方相鄰列車的調(diào)整方案與前車運(yùn)行計(jì)劃是已知的．

1.3 符號(hào)定義

1.4 模型構(gòu)建

文中考慮的基本問(wèn)題是如何在總延誤盡可能小的前提下盡可能提高列車服務(wù)的均衡性．由于初始延誤列車的處置方案及初始延誤列車后方相鄰列車的調(diào)整方案已知，且部分前車的調(diào)整路徑有限，因此總延誤最小應(yīng)為備車(相對(duì)于初始延誤列車而言)與前車的總延誤最小，且備車與前車需要經(jīng)過(guò)的車站是已知的．此時(shí)，對(duì)于k∈M∪{l}，j∈Sk，總延誤時(shí)間最小可表示為

(1)

同時(shí)，根據(jù)相同車站不同列車的到達(dá)時(shí)分與發(fā)車時(shí)分，可借助到達(dá)間隔與出發(fā)間隔的方差來(lái)表示均衡性．此時(shí)，對(duì)于k,k+1∈M∪{l,ib}，j∈Sk，均衡性盡可能好為

(2)

進(jìn)一步地，模型的約束條件包括：列車運(yùn)行間隔約束、備車上線時(shí)間約束、延誤時(shí)間約束、站停時(shí)分約束、決策變量邊界約束，以及區(qū)間運(yùn)行時(shí)分約束等．其中，對(duì)列車運(yùn)行間隔時(shí)間進(jìn)行約束是為了保證列車運(yùn)行的安全性，涉及列車的追蹤間隔不能小于最小追蹤間隔，列車的發(fā)到間隔不能小于最小發(fā)到間隔．此時(shí)，對(duì)于k,k+1∈M∪{l,i-,ib}，j∈Sk，有：

(3)

(4)

ak+1,j-ak,j≥Ih

(5)

dk+1,j-dk,j≥Ih

(6)

ak+1,j-dk,j≥Ip

(7)

除了正常的追蹤間隔要求外，為了保證安全，采用較低駕駛模式時(shí)還需要考慮其他安全邊界．例如，以RM(人工駕駛)模式運(yùn)行的列車通常還需要與前車保持“一站一區(qū)間”的間隔．以該情形為例，初始延誤列車前方可能是備車，也可能是可調(diào)整的正常列車．此時(shí)，對(duì)于i∈M，j∈Si，如果有di-,j>ts，則：

max(di,j+1,dl,j+1)≤di-,j

(8)

同時(shí)，備車達(dá)到正線車站所需滿足的時(shí)間約束為

al,sl≥ta+ts

(9)

(10)

(11)

ai,j-Ai,j≥0

(12)

di,j-Di,j≥0

(13)

要求列車站停時(shí)分不能過(guò)短，也不能太長(zhǎng)．即對(duì)于k∈M∪{l}，j∈Sk，有：

(14)

(15)

由于前車計(jì)劃時(shí)刻表、初始延誤列車處置方案和初始延誤列車后方相鄰列車調(diào)整方案均為已知，可設(shè)置前方邊界約束與后方邊界約束分別為

ai,j=Ai,j,?(i,j)∈{(i,j)|Ai,j≤ts+tp}

(16)

di,j=Di,j,?(i,j)∈{(i,j)|Di,j≤ts+tp}

(17)

(18)

(19)

此外，考慮到乘客舒適性、列車以及線路條件，需設(shè)置運(yùn)行時(shí)分約束．即對(duì)于k∈M∪{l}，j,j+1∈Sk，有：

ak,j+1-dk,j≥rj,j+1

(20)

2 算法設(shè)計(jì)

采用帶精英策略的快速非支配排序遺傳算法(NSGA-II)[9]，并設(shè)計(jì)相應(yīng)的遺傳算子．NSGA-II是一種基于群體演化的多目標(biāo)遺傳算法，算法流程見(jiàn)圖2．與常規(guī)遺傳算法不同，其個(gè)體的優(yōu)劣程度根據(jù)目標(biāo)函數(shù)值、約束違反(constraint violation,CV)值(存在約束條件時(shí))、非支配排序(rank)和擁擠距離(crowding distance,CD)共同確定，所得的最優(yōu)解為Pareto(帕累托)最優(yōu)解集[10]．

圖2 算法流程

圖3位染色體編碼．其中，對(duì)正線列車信息的編碼為前車計(jì)劃到發(fā)時(shí)分的增加量，對(duì)備車信息的編碼為初始延誤列車計(jì)劃到發(fā)時(shí)分的增加量．解碼時(shí)，只需在計(jì)劃到發(fā)時(shí)分的基礎(chǔ)上加上相應(yīng)的增加量．其中，若時(shí)間點(diǎn)的總數(shù)為n，前車到站時(shí)分和出發(fā)時(shí)分個(gè)數(shù)為w，則備車的時(shí)間點(diǎn)個(gè)數(shù)為n-w．同時(shí)，為便于個(gè)體操作，將目標(biāo)函數(shù)值、約束違反(CV)值、非支配排序(Rank)與擁擠距離(CD)等信息存放于染色體尾部．

圖3 染色體編碼

由于決策變量多，約束條件復(fù)雜，根據(jù)優(yōu)化目標(biāo)與問(wèn)題特征設(shè)計(jì)了相應(yīng)的種群初始化方法．該方式是在較小的范圍內(nèi)生成隨機(jī)量作為正線列車與備車的延誤時(shí)間．隨機(jī)量面向列車到發(fā)的均衡性，因個(gè)體與列車的不同而不同，并隨著列車經(jīng)過(guò)車站的數(shù)目遞增．例如，對(duì)于個(gè)體cp，列車q在某車站的隨機(jī)量為δq，則相應(yīng)的編碼值為δp,q，解碼值為aq+δp,q或dq+δp,q．

個(gè)體選擇采用了二元錦標(biāo)賽選擇法．該方法隨機(jī)挑選兩個(gè)個(gè)體，優(yōu)先選擇非支配排序小的個(gè)體(即精英個(gè)體)作為父代個(gè)體．若個(gè)體排序一致，則選擇擁擠距離大的個(gè)體．若等級(jí)與距離相等，則隨機(jī)選擇其中的一個(gè)．同時(shí)，替換操作也遵循該原則．對(duì)于交叉與變異，文中隨機(jī)選取操作位置，見(jiàn)圖4．該方式是一種全局的交叉與變異方式．

圖4 交叉和變異算子

3 仿真算例

3.1 算例描述

以文獻(xiàn)[4-5]中基礎(chǔ)數(shù)據(jù)為例，涉及線路有20座車站，車站11存放有備車．假設(shè)列車9在07:10:30于車站8～9運(yùn)行時(shí)突發(fā)故障．調(diào)度員于07:12:45下發(fā)列車運(yùn)行調(diào)整方案，要求列車9降級(jí)運(yùn)行至車站11存車線搶修，并啟動(dòng)備車“替開(kāi)”相應(yīng)車次．運(yùn)行調(diào)整中晚點(diǎn)車次統(tǒng)計(jì)的參考值為300 s，列車最大、最小站停時(shí)分分別為300 和25 s．同時(shí)，列車計(jì)劃追蹤間隔為180 s，最小追蹤間隔為120 s，最小發(fā)到間隔為80 s，計(jì)劃站停時(shí)分Tw(s)、計(jì)劃區(qū)間運(yùn)行時(shí)分RP(s)與最小區(qū)間運(yùn)行時(shí)分R(s)分別為：Tw=[40,40,40,35,40,30,35,30,35,35,35,30,40,35,30,30,30,30,30,30]，RP=[130,96,105,85,89,79,76,90,85,89,93,107,101,78,82,78,83,93,110]，R=[104,77,84,68,71,63,61,72,68,71,74,86,80,62,66,62,66,74,88]．

在NSGA-II算法參數(shù)方面，設(shè)置交叉與變異概率分別為0.9和0.09，種群規(guī)模為200，迭代次數(shù)為50．在種群初始化方面，根據(jù)可調(diào)整的前后邊界以及被調(diào)整列車數(shù)量，將每列列車到發(fā)時(shí)分隨機(jī)調(diào)整量范圍分別設(shè)置為[0,32]、[0,64]、[0,97]、[0,129]、[0,162]、[0,194]、[0,227]與[0, 258](單位為s)，且調(diào)整量隨列車運(yùn)行時(shí)間遞增．同時(shí)，個(gè)體編碼的變異范圍為[0,450]．算例的仿真過(guò)程借助了matlab軟件．

3.2 結(jié)果分析

當(dāng)采用調(diào)整量遞增的方式來(lái)獲取初始種群時(shí)，初始種群中的可行解有177個(gè)，而僅采用隨機(jī)調(diào)整量時(shí)通常不存在可行解，即調(diào)整量遞增的方式適用于本文模型與算法．同時(shí)，算法運(yùn)行時(shí)間為51.5 s，速度較快．圖5為NSGA-II算法得到的Pareto最優(yōu)前沿，該P(yáng)areto最優(yōu)解集中存在11個(gè)最優(yōu)解，解的分布較為均勻．

圖5 Pareto最優(yōu)前沿

實(shí)際中，具體調(diào)整方案可根據(jù)決策偏好進(jìn)行選?。?，選取目標(biāo)函數(shù)1最優(yōu)的解或目標(biāo)函數(shù)2最優(yōu)的解作為列車運(yùn)行調(diào)整方案，也可以選擇兩目標(biāo)均相對(duì)較優(yōu)的情況．該標(biāo)記顯示其目標(biāo)函數(shù)1的值為5 106，目標(biāo)函數(shù)2的值為75 206.1，對(duì)應(yīng)的列車運(yùn)行調(diào)整方案見(jiàn)圖6．

圖6 考慮備車與均衡性的運(yùn)行調(diào)整

由圖6可知：前車調(diào)整計(jì)劃向右側(cè)逐漸傾斜，保證了較好的均衡性，而種群初始化方式也采用了該思路．同時(shí)，前車調(diào)整計(jì)劃存在一定的延誤，但延誤時(shí)間在可接受的范圍內(nèi)．其中，前車的最大延誤時(shí)間為191 s，為列車8到達(dá)終點(diǎn)站的時(shí)間．備車的最大延誤時(shí)間為253 s，也滿足約束條件．在列車的站停時(shí)分方面，最大站停時(shí)分為71 s，最小站停時(shí)分為30 s，均滿足要求．此外，圖中最小追蹤間隔為166 s，最小發(fā)到間隔為130 s，同樣滿足約束．因此，文中模型與算法是有效的．

4 結(jié) 束 語(yǔ)

總延誤時(shí)間與到發(fā)均衡性是列車運(yùn)行調(diào)整中常見(jiàn)指標(biāo)．在初始延誤較大時(shí)，如何協(xié)調(diào)這兩方面的需要，保證服務(wù)質(zhì)量值得關(guān)注．文中針對(duì)備車“替開(kāi)”初始延誤列車背景下的列車運(yùn)行調(diào)整，設(shè)計(jì)了雙目標(biāo)優(yōu)化模型及其求解算法．有關(guān)增開(kāi)多個(gè)備車及“跳?！鼻樾蜗驴紤]均衡性的列車運(yùn)行調(diào)整有待進(jìn)一步研究．