考慮替開(kāi)與均衡性的城軌列車(chē)運(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)所造成的列車(chē)延誤較小，可通過(guò)改變停站時(shí)間、折返時(shí)間和區(qū)間運(yùn)行速度等方式恢復(fù)運(yùn)行計(jì)劃．中斷的影響程度則較大，通常需要采用跳停、加開(kāi)、減少線上列車(chē)、變更交路等措施．

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

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

1 模型準(zhǔn)備

1.1 問(wèn)題描述

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

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

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

1.2 假設(shè)條件

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

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

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

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

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

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

1.3 符號(hào)定義

1.4 模型構(gòu)建

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

(1)

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

(2)

進(jìn)一步地，模型的約束條件包括：列車(chē)運(yùn)行間隔約束、備車(chē)上線時(shí)間約束、延誤時(shí)間約束、站停時(shí)分約束、決策變量邊界約束，以及區(qū)間運(yùn)行時(shí)分約束等．其中，對(duì)列車(chē)運(yùn)行間隔時(shí)間進(jìn)行約束是為了保證列車(chē)運(yùn)行的安全性，涉及列車(chē)的追蹤間隔不能小于最小追蹤間隔，列車(chē)的發(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)行的列車(chē)通常還需要與前車(chē)保持“一站一區(qū)間”的間隔．以該情形為例，初始延誤列車(chē)前方可能是備車(chē)，也可能是可調(diào)整的正常列車(chē)．此時(shí)，對(duì)于i∈M，j∈Si，如果有di-,j>ts，則：

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

(8)

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

al,sl≥ta+ts

(9)

(10)

(11)

ai,j-Ai,j≥0

(12)

di,j-Di,j≥0

(13)

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

(14)

(15)

由于前車(chē)計(jì)劃時(shí)刻表、初始延誤列車(chē)處置方案和初始延誤列車(chē)后方相鄰列車(chē)調(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)

此外，考慮到乘客舒適性、列車(chē)以及線路條件，需設(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ì)正線列車(chē)信息的編碼為前車(chē)計(jì)劃到發(fā)時(shí)分的增加量，對(duì)備車(chē)信息的編碼為初始延誤列車(chē)計(jì)劃到發(fā)時(shí)分的增加量．解碼時(shí)，只需在計(jì)劃到發(fā)時(shí)分的基礎(chǔ)上加上相應(yīng)的增加量．其中，若時(shí)間點(diǎn)的總數(shù)為n，前車(chē)到站時(shí)分和出發(fā)時(shí)分個(gè)數(shù)為w，則備車(chē)的時(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ī)量作為正線列車(chē)與備車(chē)的延誤時(shí)間．隨機(jī)量面向列車(chē)到發(fā)的均衡性，因個(gè)體與列車(chē)的不同而不同，并隨著列車(chē)經(jīng)過(guò)車(chē)站的數(shù)目遞增．例如，對(duì)于個(gè)體cp，列車(chē)q在某車(chē)站的隨機(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座車(chē)站，車(chē)站11存放有備車(chē)．假設(shè)列車(chē)9在07:10:30于車(chē)站8～9運(yùn)行時(shí)突發(fā)故障．調(diào)度員于07:12:45下發(fā)列車(chē)運(yùn)行調(diào)整方案，要求列車(chē)9降級(jí)運(yùn)行至車(chē)站11存車(chē)線搶修，并啟動(dòng)備車(chē)“替開(kāi)”相應(yīng)車(chē)次．運(yùn)行調(diào)整中晚點(diǎn)車(chē)次統(tǒng)計(jì)的參考值為300 s，列車(chē)最大、最小站停時(shí)分分別為300 和25 s．同時(shí)，列車(chē)計(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)整列車(chē)數(shù)量，將每列列車(chē)到發(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)整量隨列車(chē)運(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)的解作為列車(chē)運(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)的列車(chē)運(yùn)行調(diào)整方案見(jiàn)圖6．

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

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

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

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