楚彭子 虞 翊 董丹陽 袁建軍 陳義軍

(同濟大學道路與交通工程教育部重點實驗室1) 上海 201804) (同濟大學磁浮交通工程技術(shù)研究中心2) 上海 201804)

0 引 言

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

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

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

1 模型準備

1.1 問題描述

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

圖1 考慮替開的列車運行調(diào)整示意

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

1.2 假設(shè)條件

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

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

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

假設(shè)3列車采用站站停的運行方式，無“跳停”運行的情況．

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

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

1.3 符號定義

1.4 模型構(gòu)建

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

(1)

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

(2)

進一步地，模型的約束條件包括：列車運行間隔約束、備車上線時間約束、延誤時間約束、站停時分約束、決策變量邊界約束，以及區(qū)間運行時分約束等．其中，對列車運行間隔時間進行約束是為了保證列車運行的安全性，涉及列車的追蹤間隔不能小于最小追蹤間隔，列車的發(fā)到間隔不能小于最小發(fā)到間隔．此時，對于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)

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

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

(8)

同時，備車達到正線車站所需滿足的時間約束為

al,sl≥ta+ts

(9)

(10)

(11)

ai,j-Ai,j≥0

(12)

di,j-Di,j≥0

(13)

要求列車站停時分不能過短，也不能太長．即對于k∈M∪{l}，j∈Sk，有：

(14)

(15)

由于前車計劃時刻表、初始延誤列車處置方案和初始延誤列車后方相鄰列車調(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è)置運行時分約束．即對于k∈M∪{l}，j,j+1∈Sk，有：

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

(20)

2 算法設(shè)計

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

圖2 算法流程

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

圖3 染色體編碼

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

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

圖4 交叉和變異算子

3 仿真算例

3.1 算例描述

以文獻[4-5]中基礎(chǔ)數(shù)據(jù)為例，涉及線路有20座車站，車站11存放有備車．假設(shè)列車9在07:10:30于車站8～9運行時突發(fā)故障．調(diào)度員于07:12:45下發(fā)列車運行調(diào)整方案，要求列車9降級運行至車站11存車線搶修，并啟動備車“替開”相應(yīng)車次．運行調(diào)整中晚點車次統(tǒng)計的參考值為300 s，列車最大、最小站停時分分別為300 和25 s．同時，列車計劃追蹤間隔為180 s，最小追蹤間隔為120 s，最小發(fā)到間隔為80 s，計劃站停時分Tw(s)、計劃區(qū)間運行時分RP(s)與最小區(qū)間運行時分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ā)時分隨機調(diào)整量范圍分別設(shè)置為[0,32]、[0,64]、[0,97]、[0,129]、[0,162]、[0,194]、[0,227]與[0, 258](單位為s)，且調(diào)整量隨列車運行時間遞增．同時，個體編碼的變異范圍為[0,450]．算例的仿真過程借助了matlab軟件．

3.2 結(jié)果分析

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

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

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

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

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

4 結(jié) 束 語

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