客貨混行條件下列車運(yùn)行調(diào)整模型及算法

查偉雄，張子悅，嚴(yán)利鑫

(華東交通大學(xué) 交通運(yùn)輸與物流學(xué)院，南昌 330013)

鐵路行車調(diào)度指揮工作是列車正點(diǎn)運(yùn)行的重要保障，編制列車運(yùn)行計(jì)劃、保證列車正點(diǎn)運(yùn)行是調(diào)度指揮工作的核心.列車在運(yùn)行過程中受各種隨機(jī)擾動的影響，容易偏離圖定運(yùn)行時間，影響行車效率.如何在短時間內(nèi)進(jìn)行高效、有序的列車運(yùn)行調(diào)整，保證行車安全，是衡量區(qū)段內(nèi)行車組織工作質(zhì)量的標(biāo)準(zhǔn)，也是近期的熱點(diǎn)和難點(diǎn)問題.“最優(yōu)列車調(diào)度”問題由Szpigel[1]首次提出，以列車開行時間最小為目標(biāo)建立線性規(guī)劃模型.既有文獻(xiàn)對旅客列車運(yùn)行調(diào)整問題展開研究，通過建立混合整數(shù)規(guī)劃模型，分別采用兩階段法[2]、拉格朗日松弛算法和最短路徑算法[3]、策略優(yōu)化方法[4]及仿真[5-6]等優(yōu)化方法，以列車偏離圖定運(yùn)行時間最短為目標(biāo)進(jìn)行求解.近年來，許多學(xué)者采用智能算法，如遺傳算法[7]、粒子群算法[8]等來解決列車運(yùn)行調(diào)整問題.文獻(xiàn)[9]建立基于最小列車秩序熵的模型求解，實(shí)例證明了僅對受輕微擾動的單線客貨混行條件下列車運(yùn)行調(diào)整的問題有效.文獻(xiàn)[10-11]針對客運(yùn)鐵路網(wǎng)絡(luò)下的貨物列車運(yùn)行調(diào)整問題，以客、貨列車延誤時間最短、貨物列車旅行時間最短為目標(biāo)建立優(yōu)化模型，采用啟發(fā)式算法求解.文獻(xiàn)[12]研究了基于超圖的兩級建模，考慮旅客時刻表延誤和貨運(yùn)時間，利用問題特殊結(jié)構(gòu)的修正線性化求解.上述文獻(xiàn)基于雙線鐵路網(wǎng)絡(luò)，對客貨混行列車運(yùn)行調(diào)整問題進(jìn)行研究.

本文作者以客貨混行條件下的單線鐵路全線為背景，以列車間隔時間和到發(fā)線等為約束條件，建立列車運(yùn)行調(diào)整計(jì)劃混合整數(shù)規(guī)劃模型.以列車在調(diào)度區(qū)間內(nèi)總的偏離圖定運(yùn)行時間最少為目標(biāo)函數(shù)，采用自適應(yīng)柯西變異人工蜂群算法(ACMABC)求解，并通過實(shí)例驗(yàn)證了模型及算法的可行性.

1 問題描述

列車運(yùn)行調(diào)整的目標(biāo)是恢復(fù)正點(diǎn)運(yùn)行，當(dāng)列車在運(yùn)行過程中偏離圖定時間發(fā)生晚點(diǎn)時，調(diào)度指揮人員需遵守以下原則實(shí)施調(diào)整：①若為同等級列車發(fā)生晚點(diǎn)，則正點(diǎn)列車優(yōu)先，晚點(diǎn)列車后行；②若為不同等級列車發(fā)生晚點(diǎn)，則部分高等級列車可接受低等級列車一定時間的連帶晚點(diǎn),其他列車絕對優(yōu)先；③若在晚點(diǎn)傳播情況下進(jìn)行調(diào)整，則低等級列車不得越行高等級列車.

根據(jù)以上原則，基于客、貨列車混行的特點(diǎn)，本文采取以下調(diào)整策略：①減少列車在車站作業(yè)時間.當(dāng)部分列車在車站作業(yè)時間較長時，可以適當(dāng)壓縮列車在車站作業(yè)時間，但需滿足車站的最小作業(yè)時間約束；②列車越行.當(dāng)前行列車出現(xiàn)到達(dá)晚點(diǎn)并對后續(xù)列車產(chǎn)生晚點(diǎn)傳播時，若滿足兩列車的最小間隔時間約束，且后續(xù)列車優(yōu)先級高于前行列車時，可實(shí)現(xiàn)越行；③組織列車趕點(diǎn).當(dāng)列車發(fā)生晚點(diǎn)時，可在滿足不同等級列車在區(qū)間的最小運(yùn)行時間約束條件下，通過區(qū)間加速方式實(shí)現(xiàn)正點(diǎn)運(yùn)行，提高行車效率；④運(yùn)行調(diào)整時間的確定.當(dāng)前行列車出現(xiàn)晚點(diǎn)并影響到后續(xù)列車時，運(yùn)行調(diào)整時間為列車最小列車間隔時間、實(shí)際到達(dá)時間與圖定到達(dá)時間差值的最小值.

由于列車運(yùn)行調(diào)整問題涉及條件較多，故作以下問題假設(shè)：列車的圖定到、發(fā)時間已知，列車在偏離圖定運(yùn)行前保持正點(diǎn)運(yùn)行，列車在任一站點(diǎn)可越行.

2 模型的建立

2.1 符號定義

假設(shè)某一單線半自動閉塞區(qū)段有m次列車，n個站點(diǎn)，n-1個區(qū)間.令Qt為列車車次集合，其中包含各等級旅客列車Qk和貨物列車Qh，Qt=Qk∪Qh={Qt1,…,Qtg,…,Qtm}，Qk={1,…,g}，Qh={g,…,m}；令Qs為車站站點(diǎn)集合，Qs={Qs1,Qs2,…,Qsn}；令K為區(qū)間集合，K={1,2,…,n-1}；令Dj為車站j的到發(fā)線集合(j∈Qs)，則列車運(yùn)行調(diào)整中可用的資源集合為Φ={Qs,Qt,K,Dj}；令A(yù)0、D0分別為圖定列車到、發(fā)時刻，A、D分別為列車在運(yùn)行過程中的實(shí)際到、發(fā)時刻，則列車運(yùn)行調(diào)整中的時間集為ψ={A0,D0,A,D}.

定義列車的優(yōu)先級為λ，依據(jù)列車類型、等級來取不同的權(quán)重，M為足夠大的正數(shù).

定義3個0-1決策變量：列車在車站辦理停站作業(yè)θij、列車過站次序Xi1,i2,j，列車優(yōu)先級ηi1,i2.若列車i在車站j辦理停站作業(yè)，則θij=1，反之θij=0；若列車i1比i2先通過車站j，則Xi1,i2,j=1，反之Xi1,i2,j=0;若列車i1優(yōu)先級高于列車i2,則ηi1,i2=1,反之,ηi1,i2=0.

2.2 約束條件和目標(biāo)函數(shù)

2.2.1 約束條件

為保證列車行車安全，需考慮8組約束條件，具體描述如下：

1)不同時列車到達(dá)間隔時間約束.

在單線區(qū)段，來自相對方向的兩列列車在車站交會時，從某一方向列車到達(dá)車站時起至相對方向列車到達(dá)或通過該站時止的最小間隔時間為

TB≤M(1-Xi1,i2,j)+Ai2,j-Ai1,j

?i1,i2∈Qt, ?j,j+1∈Qs

(1)

式中：TB為不同時列車到達(dá)間隔時間.

2)列車發(fā)車時間約束.

若列車在車站辦理停站作業(yè)，則發(fā)車時間不得早于圖定時間.

?i∈Qt, ?j∈Qs

(2)

3)到發(fā)線約束.

車站到發(fā)線占用數(shù)不得超過車站的到發(fā)線總數(shù).

?i∈Qt, ?j∈Qs

(3)

4)客貨列車間隔時間.

M(1-Xi1,i2,j)+Di2,j≥Ai1+1

M·Xi1,i2,j+Di1,j≥Ai2,j+1

?i1∈Qh, ?i2∈Qk, ?j,j+1∈Qs

(4)

5)區(qū)間運(yùn)行時間約束.

當(dāng)列車發(fā)生晚點(diǎn)時，可以通過區(qū)間加速方式實(shí)現(xiàn)正點(diǎn)運(yùn)行，提高行車效率，但需要滿足不同等級列車在區(qū)間的最小運(yùn)行時間ttλ,K約束.

?i∈Qt, ?j,j+1∈Qs

(5)

式中：ttλ,k為不同等級列車在區(qū)間的最小運(yùn)行時間.

6)列車作業(yè)時間約束.

部分列車在車站作業(yè)時間需滿足車站的最小作業(yè)時間約束.

Di,j-Ai,j≥θij·tsλ,j

?i∈Qt, ?j∈Qj

(6)

式中：tsλ,j為不同等級列車在車站的最小作業(yè)時間.

7)站內(nèi)越行約束.

當(dāng)前行列車i1在到達(dá)車站j后對后續(xù)列車i2產(chǎn)生晚點(diǎn)傳播時，若列車i1,i2到達(dá)j站的時間間隔滿足兩列車的最小間隔時間μ，且列車i2優(yōu)先級高于列車i1時，可實(shí)現(xiàn)站內(nèi)越行.

ηi1,i2·(Ai2,j-Ai1,j)2≥μ2

?i1,i2∈Qt, ?j∈Qs

(7)

式中：μ為兩列車的最小間隔時間；λi1、λi2為列車i1、i2的優(yōu)先級.

8)運(yùn)行調(diào)整時間約束.

當(dāng)前行列車出現(xiàn)早點(diǎn)或晚點(diǎn)情況并影響到后續(xù)列車時，運(yùn)行調(diào)整時間為兩列車最小列車間隔時間、實(shí)際到達(dá)時間與圖定到達(dá)時間差值的最小值.

?i∈Qt, ?j∈Qs

(8)

式中：tad為列車運(yùn)行調(diào)整時間.

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

由于客、貨列車混跑下存在列車不同等級的情況，高等級列車和低等級列車相比，調(diào)整的效益更大.以客、貨不同等級列車在調(diào)度區(qū)間內(nèi)總的偏離圖定列車運(yùn)行時間最少為目標(biāo)函數(shù)

?i∈Qt, ?j∈Qs

(9)

式中：Z為目標(biāo)函數(shù)；λ為等級權(quán)重.

旅客列車有三個等級：第一等級為直達(dá)特快旅客列車，最高速度為160 km/h；第二等級為快速旅客列車，最高速度為120 km/h；第三等級為普通旅客列車，速度為90～110 km/h.高等級的列車在運(yùn)行調(diào)整時具有優(yōu)先權(quán).

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

考慮到列車運(yùn)行調(diào)整問題多、約束、求解復(fù)雜的特點(diǎn)，在線路長度和列車數(shù)量增多的情況下，求解難度呈指數(shù)級增長，需要現(xiàn)代啟發(fā)式算法求最優(yōu)解或近似最優(yōu)解.因此，可以選擇人工蜂群算法(Artificial Bee Colony,ABC)進(jìn)行求解.具體算法步驟如下：

Step1 隨機(jī)產(chǎn)生初始群體P即SN個初始解，SN為種群規(guī)模也等于蜜源數(shù)目，迭代次數(shù)iter=0，最大迭代次數(shù)MCN，初始化標(biāo)志向量trial(i)，記錄同一蜜源的連續(xù)開采次數(shù).每個解Xi(i=1,2,…,SN)是1個D維向量，D為優(yōu)化參數(shù)的個數(shù)，初始化后，由雇傭蜂、跟隨蜂、偵查蜂對位置(解)進(jìn)行改進(jìn)的循環(huán)搜索過程.

Step2 在搜索過程中，雇傭蜂對蜜源鄰域進(jìn)行搜索，產(chǎn)生1個新蜜源位置(新解)為

υij=xij+ξij(xij-xlj)

(10)

式中：l∈{1,2,…,SN}；j∈{1,2,…,D}；且l≠i,υij為新蜜源位置；ξij為[-1,1]之間的隨機(jī)數(shù)，當(dāng)新蜜源位置比原蜜源位置更優(yōu)時，則替換，反之則保留.

Step3 跟隨蜂按照輪盤賭的選擇策略來判斷選擇哪個蜜源，判斷式為

Ci=fiti/(fit1+fit2+…+fitSN)

(11)

式中：Ci為選擇概率；fiti為解Xi的適應(yīng)度函數(shù)值.

Step4 若解Xi在“l(fā)imit”次迭代后仍不能改良，則表示陷入局部最優(yōu)解，該蜜源舍棄，對應(yīng)的1個雇傭蜂變成偵查蜂，并由下式隨機(jī)搜索1個新蜜源替換原蜜源：

(12)

ABC算法在蜂群位置更新上采用隨機(jī)函數(shù)，存在收斂速度快、易陷入局部最優(yōu)及搜索精度方面的問題，結(jié)合上述問題和列車運(yùn)行調(diào)整的特點(diǎn)，從以下幾個方面進(jìn)行改進(jìn)：

①算法初始化輸入圖定到、發(fā)時刻，實(shí)際到、發(fā)時刻，列車間隔時間，列車最小間隔時間，車站計(jì)劃作業(yè)時間(涉及到時間均轉(zhuǎn)化為分鐘計(jì)算)，列車區(qū)間運(yùn)行時間，車站到發(fā)線數(shù)目，各等級列車對應(yīng)的權(quán)重，種群規(guī)模SN，最大迭代次數(shù)MCN，控制參數(shù)limit，根據(jù)列車實(shí)際運(yùn)行時間和圖定時間來確定晚點(diǎn)列車和站點(diǎn)，并初始化產(chǎn)生SN個滿足約束條件(1)～(6)的隨機(jī)解以提高求解效率.

②在蜂群的搜索尋優(yōu)過程中，通過實(shí)際運(yùn)行時間和圖定時間對比,確定晚點(diǎn)時刻、待調(diào)整列車和站點(diǎn)，按約束條件(5)～(8)計(jì)算調(diào)整后列車到、發(fā)站時間，并對發(fā)車順序進(jìn)行調(diào)整，同時記錄當(dāng)前的最優(yōu)解.

③在初始階段，蜂群搜索進(jìn)程快，步長較大，搜索范圍廣，在接近最優(yōu)解范圍時，需要精細(xì)搜索縮小搜索范圍.根據(jù)需要，在搜索階段引入自適應(yīng)因子ω[13].在初始階段ω值較大，擴(kuò)大蜂群搜索范圍，在蜂群接近最優(yōu)解時ω較小，縮小搜索范圍，調(diào)整式為

ω=ω-+(f-fmin)·(ω+-ω-)/(fa-fmin)

(13)

式中：ω+、ω-分別為最大、最小慣性權(quán)重；f、fa、fmin分別為當(dāng)前適應(yīng)度函數(shù)值、平均適應(yīng)度函數(shù)值、群體最小適應(yīng)度函數(shù)值.

則式(10)調(diào)整為

υij=xij+ω·ξij(xij-xlj)

(14)

④在蜜源位置更新階段引入柯西分布算子，避免算法陷入局部最優(yōu)解[14].若在蜜源更新階段引入柯西變異算子，則采蜜蜂有可能跳出局部最優(yōu).一維柯西分布的概率密度函數(shù)為

f(x;0,1)=γ/[π·(γ+x2)]

(15)

當(dāng)γ=1，x=0時稱為標(biāo)準(zhǔn)柯西分布.

改進(jìn)后偵查蜂的搜索公式，即式(12)變?yōu)?/p>

(16)

式中：C(0,1)為標(biāo)準(zhǔn)柯西分布.

自適應(yīng)柯西變異人工蜂群(ACMABC)算法流程見圖1.

4 計(jì)算實(shí)例與分析

以中國鐵路昆明局集團(tuán)有限公司2019年調(diào)整后的盤西鐵路列車運(yùn)行圖相關(guān)資料為例進(jìn)行分析.盤西鐵路西起貴昆鐵路沾益站，東經(jīng)富源至紅果與南昆線相接，向北沿長江至柏果，與水柏鐵路相連，跨越云貴兩省，區(qū)內(nèi)煤炭資源豐富，全長136 km沿線途徑10個站點(diǎn)，劃分為9個區(qū)間.調(diào)整時段選某日5:00—19:00，按列車進(jìn)入?yún)^(qū)段時間編號為i1,i2,…,i11，車站按沿途編號為j1,j2,…,j11，具體車次見表1.

表1 盤西鐵路5:00—19:00原列車時刻表

其中，速度160 km/h的列車為1列，速度120 km/h的列車為3列，速度90～110 km/h的列車位1列，貨運(yùn)列車為6列，列車等級為[2 4 4 1 4 4 3 4 2 4 2]，對應(yīng)權(quán)重λ=[0.3 0.1 0.1 0.4 0.1 0.1 0.2 0.1 0.3 0.1 0.3]，M取值為1 440，車站的到發(fā)線數(shù)目、計(jì)劃運(yùn)行時刻表、停站情況、間隔時間、區(qū)間運(yùn)行時間均由列車運(yùn)行圖技術(shù)資料給出.

為更好驗(yàn)證算法的有效性，采用電腦主頻CPU為Intel(R)Core(TM)i5-7267U，內(nèi)存為8.0 GB，Matlab2019a進(jìn)行求解，設(shè)置受輕微擾動、較大擾動兩個場景進(jìn)行模擬，并計(jì)算對應(yīng)的目標(biāo)函數(shù)Z、運(yùn)行時間.參數(shù)設(shè)置：最大迭代次數(shù)MCN=1 500，limit=200，SN=50，xmax=0.75，xmin=0.25.

在輕微擾動場景中，假設(shè)列車到站時發(fā)生4列列車初始晚點(diǎn)的情況：列車i1、i4、i7、i8分別到達(dá)站j3、j4、j2、j8各晚點(diǎn)37、10、20、50 min，初始晚點(diǎn)時間為117 min.在其他控制參數(shù)保持不變的情況下，MCN取不同的數(shù)值運(yùn)行，所有計(jì)算均進(jìn)行10次并取均值，得到ACMABC算法優(yōu)化目標(biāo)函數(shù)值見表2.

表2 ACMABC算法優(yōu)化目標(biāo)函數(shù)值

由表2可見：當(dāng)?shù)螖?shù)MCN較小時，ACMABC算法在對應(yīng)目標(biāo)函數(shù)的提升并不明顯；隨著迭代次數(shù)變大(MCN=1 500),ACMABC算法的有效性逐漸體現(xiàn)；隨著迭代次數(shù)倍數(shù)增加(MCN=3 000),優(yōu)化結(jié)果又趨于一致，過多的迭代次數(shù)耗費(fèi)時間巨大，本文設(shè)計(jì)在有限的時間下進(jìn)行列車運(yùn)行調(diào)整.

根據(jù)文獻(xiàn)[15]設(shè)計(jì)解的性能指標(biāo)，本文算法求得的目標(biāo)函數(shù)最優(yōu)值Z,實(shí)際最優(yōu)值為Ztrue，則解的性能指標(biāo)值為

(17)

式中：Per為解的性能指標(biāo)值，%.

性能指標(biāo)值Per越小，則解越精確，不同參參數(shù)取值對算法性能的影響見圖2.由圖2(a)可見，隨著limit值的增大，ACMABC算法性能呈上升后下降的趨勢；當(dāng)limit取值較大時，ACMABC算法產(chǎn)生的隨機(jī)解個數(shù)較少，易陷入局部最優(yōu)；當(dāng)取值較小時，搜索能力不足，算法的性能下降.因此，必定有值(limit=200)能達(dá)到算法性能最優(yōu).

由圖2(b)可見：隨著種群規(guī)模SN增大，ACMABC算法求出的解呈現(xiàn)先下降后上升的趨勢；當(dāng)SN數(shù)值增大時，全局搜索能力變差；當(dāng)SN降低時，影響蜂群的搜索能力；當(dāng)SN=100時效果最好.

根據(jù)上述參數(shù)設(shè)置，對輕微擾動場景下的4列晚點(diǎn)列車進(jìn)行自動調(diào)整，通過算法求出最后晚點(diǎn)總時間為147 min，并進(jìn)行如下調(diào)整：列車i1在站j3到達(dá)晚點(diǎn)后，進(jìn)行停站作業(yè)壓縮、趕點(diǎn)運(yùn)行，最終到站晚點(diǎn)28 min；列車i1晚點(diǎn)對站j3后續(xù)列車i2產(chǎn)生影響，滿足列車在區(qū)間最短運(yùn)行時間和車站最短作業(yè)時間下，列車i2到達(dá)站j9恢復(fù)正點(diǎn)運(yùn)行.此外，列車i4、i7、i8最終晚點(diǎn)20、49、50 min；列車i9在站j8實(shí)現(xiàn)越行，即當(dāng)?shù)偷燃壛熊囃睃c(diǎn)引起高等級列車后效晚點(diǎn)時，高等級列車可以在車站越行通過以減少晚點(diǎn)傳播時間.

算法的收斂曲線對比見圖3.

由圖3可見：ABC算法在0～260代之間，群體最小適應(yīng)度速率增長快.當(dāng)超過260代后，曲線趨于平滑，而ACMABC算法在接近220代時已趨于穩(wěn)定；在運(yùn)算時間上，ACMABC算法均耗時319 s, ABC算法需耗時360 s,這顯示出ACMABC算法在全局搜索能力和收斂性上的有效性.在運(yùn)行15次后，取15次的優(yōu)化目標(biāo)函數(shù)均值，ACMABC算法在平均優(yōu)化目標(biāo)函數(shù)值上較ABC算法減少58.5%，平均搜索次數(shù)減少33.2%，平均運(yùn)行時間降低11.4%.

在較大擾動場景中，隨機(jī)增加不同等級的晚點(diǎn)列車數(shù)目和晚點(diǎn)時間，計(jì)算受擾動下的目標(biāo)函數(shù)值、運(yùn)行時間T、迭代次數(shù)，運(yùn)行10次并取均值進(jìn)行比較，結(jié)果見表3.

表3 不同晚點(diǎn)情況下ACMABC算法與ABC算法求解結(jié)果比較

由表3可見：在受輕微擾動時，ACMABC算法在運(yùn)行時間上縮短15.4%，在目標(biāo)函數(shù)值上與ABC算法差值小；在面對較大擾動時，ACMABC算法求解效率增加了49.7%，運(yùn)行時間減少了20.6%，而ABC算法未求得可行解.在2個場景下ACMABC算法的求解表明：本文設(shè)計(jì)的客、貨混行條件下，列車運(yùn)行調(diào)整模型和自適應(yīng)柯西變異人工蜂群算法(ACMABC)具有有效性.

5 結(jié)論

1)考慮列車的優(yōu)先級、到發(fā)時間、客貨列車間隔時間、到發(fā)線等約束條件，以加權(quán)的總的偏離列車圖定運(yùn)行時刻最少為目標(biāo)函數(shù)，構(gòu)建客貨混行條件下的列車運(yùn)行調(diào)整模型.

2)針對人工蜂群算法易陷入局部最優(yōu)、收斂效果差的問題，采用自適應(yīng)柯西變異人工蜂群算法(ACMABC)，以盤西鐵路全線某時段的列車為依據(jù)，模擬2個晚點(diǎn)場景并進(jìn)行列車調(diào)整，通過計(jì)算證明設(shè)計(jì)的模型與算法在解決列車運(yùn)行調(diào)整問題上具有有效性.

3)以單線鐵路上客、貨混行條件下列車運(yùn)行調(diào)整為例進(jìn)行研究，且晚點(diǎn)時間確定，復(fù)雜度較低.下一步的研究重點(diǎn)是考慮雙線鐵路不確定晚點(diǎn)時刻下的列車運(yùn)行調(diào)整.