基于時空資源的鐵路客運站到發線運用調整

彭其淵， 張永祥， 魯工圓， 李文新， 石 鐵

(1. 西南交通大學 交通運輸與物流學院，四川 成都 610031；2. 西南交通大學 綜合交通運輸智能化國家地方聯合工程實驗室，四川 成都 610031)

鐵路客運站到發線運用方案是客運站作業計劃的重要內容之一，其目的在于最大限度地滿足不同類型的列車按照運行計劃在客運站進行到發的作業需求.合理的到發線運用計劃不僅是列車在站安全地完成行車作業的基本保障，而且可以實現方便旅客乘降、提高客運站作業效率以及保證客運站設備均衡使用等.但是，當惡劣天氣、線路故障等原因導致列車大量晚點到達，導致客運站到發線能力緊張時，原有的到發線運用方案已不能適應變化了的列車作業要求，必須對客運站到發線運用方案進行調整，以保證列車運行安全和盡快恢復列車正點運行.

車站到發線運用方案編制問題是近年來國內外學者研究的熱點問題.國內學者一般使用線性0-1規劃模型[1-2]、非線性0-1規劃模型[3-4]混合整數規劃模型[5]對車站到發線運用方案編制問題進行描述，模型的優化目標主要為最小化到發線使用成本[1-3]、均衡使用到發線[4]及最小化列車停站時間[7]等，求解模型所采用的算法也以模擬退火算法[1-2]、蟻群算法[3]、遺傳算法[4]、拉格朗日松弛算法[5]等啟發式算法為主，這是由于車站到發線運用方案編制問題本質上是NP難題(non-deterministic polynomial, NP-Hard)問題[5].國外與車站到發線運用方案編制問題相關的研究可參考文獻[6].國外學者主要將車站到發線運用方案編制問題抽象為節點緊模型(node packing model, NPP)[7]、集合緊模型(set packing model, SPP)[8]及圖著色問題[9]等經典問題求解，也有國外學者直接使用線性0-1規劃模型[10]或二次0-1規劃模型[11]對車站到發線運用方案編制問題進行描述，同時還有國外學者[12]設計了模擬現場調度員思路的啟發式方法來解決車站到發線運用方案編制問題.國外學者的研究主要包括最小化到發線使用成本[8,11]、最大化車站通過能力[7]及最小化列車到達和出發晚點時間[12]等，所采用的算法以特殊設計的分枝定價算法[7-8]及分枝定界定價算法[11]為主.

國內外學者除對如何合理、高效地編制車站計劃到發線運用方案進行了大量研究工作，也有一部分學者對到發線運用方案調整問題進行了研究.王棟[13]闡述了到發線運用計劃調整的可行措施，包括改變列車?？康桨l線、列車到達和出發時間及列車到發線占用時間等，并建立了對應于4種優化指標下的實時調整模型.喬瑞軍[14]以列車對到發線使用偏好為首要目標、以列車實際到發時間與理想到發時間的偏離程度為次要目標，建立了列車延誤情況下的鐵路客運站到發線運用方案調整優化模型，并設計了先考慮到發線運用、后考慮列車到發時間的分步求解算法.朱昌鋒[15]分析了到發線運用方案實時調整對于輔助列車調度員工作的必要性，并提出了基于滾動時域的到發線運用方案動態調整策略.

與前人的研究工作相比，本文主要有以下3個方面的貢獻.首先，考慮了在列車大量晚點到達的情況下，如何在短時間內對列車的到達和出發時間以及列車所分配到發線進行綜合優化調整，以保證列車運行安全和盡快恢復列車的正常運行秩序；其次，采用0-1變量描述列車占用離散的鐵路到發線時空資源的沖突關系，從而避免了大M法中復雜的列車占用到發線先后順序變量；最后，基于鐵路到發線時空資源占用沖突分步求解的思路，設計了高效的遺傳模擬退火算法以快速得到問題的滿意解，并通過實例驗證了模型和算法的有效性.

本文首先分析了鐵路到發線資源的離散化時空描述方法，在此基礎上以列車加權總晚點時間與到發線使用費用之和最小為優化目標，以保證列車運行安全和滿足列車在站到發作業要求為約束條件，建立了求解客運站到發線運用方案調整問題的線性0-1規劃模型，并設計了遺傳模擬退火算法對模型進行求解，從而解決了客運站到發線運用方案調整問題.

1 問題分析

1.1 鐵路到發線資源的時空描述

鐵路客運站到發線資源是具有時間和空間雙重屬性的二維資源.對于到發線運用問題，客運站擁有的空間資源集合為其到發線集合，時間資源為問題所研究的時間段.令以時間間隔Δτ為單位對所研究時段T離散化后，共有|T|個時間間隔，|T|=[T/Δτ]，到發線數量為|I|，則客運站的到發線資源可描述為二維資源矩陣X.

式中:xi,t表示到發線資源(i,t)的狀態.

將到發線資源離散化后，可以對列車占用和騰空到發線的過程進行更加準確、直觀的描述.對于如圖1a所示包含4條到發線、2條正線的鐵路客運站A，有5列列車在1h內在客運站進行作業，列車對到發線資源的占用包括列車在被分配到發線上從接車開始到作業完畢再到出清到發線的時間段，其運行如圖1b和圖1c所示.以5 min為時間間隔為例對到發線時空資源進行離散化，則該客運站在該運行圖下資源使用情況可描述如圖2a，其到發線資源矩陣XA可描述如圖2b.

a 示例車站A布置示意

b A站某時段下行列車運行c A站某時段上行列車運行

圖1 客運站A布置及列車運行

Fig.1Layout and train diagrams of passengerstation A

a 到發線資源使用情況

b 到發線資源矩陣

Fig.2 Arrival and departure track resource usage and its time-space resource matrix

根據以上定義，列車在站作業過程對到發線資源占用有如下特征：

(1) 列車使用的唯一性特征.列車一次作業只能使用唯一的一條到發線；

(2) 到發線資源一次性使用特征.同一到發線資源元素最多只能被一次作業使用，即xi,t≤1；

(3) 連續使用特征.列車在使用到發線時將至少使用1個到發線資源，當使用多個時，到發線資源總是在時間上被連續使用，如某列車從時間t開始使用到發線i，且總使用時間間隔數為Δt時，xi,t=xi,t+1=xi,t+2=…=xi,t+Δt.

1.2 鐵路到發線運用問題分析

鐵路客運站一般通過編制到發線運用方案來合理使用到發線資源，方便旅客乘降.但當發生列車大量晚點時，原有的到發線運用方案已不能適應列車的到發作業要求，導致客運站到發線能力緊張，從而必須將列車運行計劃與客運站到發線運用方案綜合起來進行優化調整.因此，本文研究在固定數量到發線的客運站中，多列不同等級的列車由于不可抗拒原因晚點到達客運站時，如何合理調整客運站到發線運用方案和列車運行計劃，以保證列車運行安全和盡快恢復列車正點運行.

根據列車占用到發線時空資源的特征，在調整到發線運用方案時，要考慮列車占用到發線的唯一性和連續性.此外，為滿足旅客的出行方便和乘降作業要求，一般情況下被調整列車的實際到達和出發時間應分別不早于其計劃到達和出發時間，并保證被調整列車的運行安全.在滿足以上條件的基礎上，考慮不同列車等級和列車對到發線的使用要求，實現在保證列車運行安全的同時，充分利用客運站通過能力，最小化晚點發生后列車加權總晚點時間與到發線使用費用之和.

2 模型構建

2.1 參數及變量說明

2.1.1參數說明

參數匯總見表1.如非特別提及，所有與時間相關的參數和變量的取值均為時間間隔Δτ的整倍數.

表1 參數說明

2.1.2變量說明

對任意列車l、k(l,k∈L)、任意一條到發線i(i∈I)和任意時刻t(1≤t≤MT)，模型定義如下：

(1) 到發線選擇變量

(2) 列車占用到發線狀態變量xl,i,t

(3) 為描述列車的到達、出發過程，定義了到發線使用狀態變量ul,i,t和到發線騰空狀態變量vl,i,t，分別表示列車l接車到達和發車離開所導致的到發線狀態.

由xl,i,t、ul,i,t和vl,i,t的定義可知，這三者存在關系如下：

xl,i,t=1-(ul,i,t+vl,i,t)

(1)

例如對于圖1示例客運站A，當列車l在時刻5占用下行到發線5并在時刻20離開，上述3個變量ul,i,t、vl,i,t和xl,i,t對于該過程描述的取值分別如圖3所示.

a ul,i,t

b vl,i,t

c xl,i,t=1-(ul,i,t+vl,i,t)

(4) 列車到達和出發先后順序變量

(5) 列車實際到達時間yl,a和列車實際出發時間yl,d

(2)

(3)

2.2 目標函數

當因部分列車晚點到達客運站而需對到發線運用方案進行調整時，首先應盡量不改變列車的到達和出發時間；其次，要盡量滿足列車對到發線的使用要求，本文所設計目標函數如式(4)所示.式(4)由兩項之和構成，第1項為列車加權總晚點時間，其中，列車等級越高則Pl取值越大，且α為第1項的加權系數；第2項為到發線使用費用.

(4)

2.3 約束條件

由到發線時空資源特征和列車在站作業過程特征，客運站到發線運用方案調整問題需服從到發線占用唯一性、到發線持續作業、到發線沖突、車站追蹤間隔時間、列車在站作業時間和列車到發時間等6類主要約束條件以保證列車運行安全和滿足列車對到發線的使用要求.

(1) 到發線占用唯一性約束

(5)

wl,i=0, ?l∈L,i∈(I-Il)

(6)

式(5)和式(6)保證列車l只在可選的到發線集合中選擇唯一一條的到發線進行作業.

(2) 到發線沖突約束

(7)

式(7)保證任意一條到發線在任一時刻均最多只有一列車占用.

(3) 到發線持續作業約束

ul,i,t≥ul,i,t+1+wl,i-1, ?l∈L,

?i∈I,?1≤t

(8)

vl,i,t≤vl,i,t+1-wl,i+1, ?l∈L,

?i∈I,?1≤t

(9)

ul,i,t≤ul,i,t+1+wl,i, ?l∈L,

?i∈I,?1≤t

(10)

式(8)～式(10)通過保證ul,i,t和vl,i,t取值的連續性來實現列車在某一條到發線上的持續作業.

(4) 車站追蹤間隔時間約束

yl,a-yk,a≥(1-zl,k)ha+zl,kD-λl,kM,

?l,k∈L:l≠k,πl=πk

(11)

yl,d-yk,d≥(1-zl,k)hd+zl,kD-μl,kM,

?l,k∈L:l≠k,πl=πk

(12)

zl,k≥wl,i+wk,i-1,

?l,k∈L,?i∈Il∩Ik:k>l,πl=πk

(13)

zl,k=zk,l, ?l,k∈L:k>l,πl=πk

(14)

λl,k+λk,l=1, ?l,k∈L:k>l,πl=πk

(15)

μl,k+μk,l=1, ?l,k∈L:k>l,πl=πk

(16)

式(11)和式(12)保證同方向到達與出發的任意兩列車間滿足車站到達和出發追蹤間隔時間要求公式(13)通過wl,i和wk,i的取值來確定列車l和列車k是否使用同一條到發線.式(14)～式(16)根據列車l和列車k之間的先后關系，分別對zl,k、λl,k和μl,k的取值進行了限制.

(5) 列車在站作業時間約束

(17)

如果列車l占用到發線i，則列車在到發線i上的停留時間必須不小于列車計劃停站時間與到發線作業安全間隔時間之和.

(6) 列車到達和出發時間約束

yl,a≥tl,a, ?l∈L

(18)

yl,d≥tl,d+D, ?l∈L

(19)

yl,d≥yl,a+Δl+D, ?l∈L

(20)

式(18)保證列車實際到達時間不小于列車計劃到達時間；式(19)保證列車實際出發時間不小于列車計劃出發時間與到發線安全作業間隔時間之和；式(20)保證列車實際停站時間不小于計劃停站時間與到發線作業安全間隔時間之和.

(1) 初始條件.在模型開始的初始時刻，式(21)初始化ul,i,t值均為1，式(22)初始化vl,i,t值均為0，即在初始時刻既沒有列車到達客運站也沒有列車從客運站出發.式(23)～式(25)分別固定在列車晚點發生之前到達客運站的部分列車的占用到發線、到達客運站時間以及客運站出發時間.式(26)和式(27)分別更新列車在開始晚點后預計到達客運站及從客運站出發的時間.

ul,i,1=1, ?l∈L,?i∈I

(21)

vl,i,1=0, ?l∈L,?i∈I

(22)

wl,i=ql,i, ?l∈L,?i∈I:tl,a

(23)

yl,a=tl,a, ?l∈L:tl,a

(24)

yl,d=tl,d, ?l∈L:tl,a

(25)

(26)

(27)

(2) 變量取值

wl,i={0,1}, ?l∈L,?i∈I

(28)

ul,i,t,vl,i,t={0,1}, ?l∈L,?i∈I,

?1≤t≤MT

(29)

zl,k,λl,k,μl,k={0,1}, ?l,k∈L:l≠k,

πl=πk

(30)

式中：xl,i,t、yl,a和yl,d是為便于表示模型而引入的中間變量，其值均可由ul,i,t和vl,i,t的取值推導得到.

2.4 有效不等式

有效不等式是暗含在前文模型約束條件中的約束關系，為提高模型求解速度，在模型中引入如下有效不等式.

ul,i,t≥1-wl,i, ?l∈L,?i∈I,?1≤t≤MT

(31)

vl,i,t≤wl,i, ?l∈L,?i∈I,?1≤t≤MT

(32)

xl,i,t≤wl,i, ?l∈L,?i∈I,?1≤t≤MT

(33)

xl,i,t=0, ?l∈L,?i∈I,?t

t>tl,d+Δmax+D

(34)

式(31)～式(33)的原理類似，結合圖3能對這三個公式有更加直觀的理解.以式(31)為例說明，當列車l占用到發線i時，則式(31)為ul,i,t≥0，為無效約束；當列車l不占用到發線i時，則式(31)為ul,i,t≥1，即ul,i,t=1.式(34)考慮到當客運站能力緊張，需要將計劃或預計占用到發線時間互相重疊的兩列車安排到同一條到發線時，其中一列等級相對較低列車的到發時間將被推遲一段時間，這段時間的最大值即為Δmax+D，而且列車的到發時間只能被推遲，因此可用式(34)限制變量xl,i,t在ttl,d+Δmax+D范圍內的取值為0.

式(1)～式(34)即構成了客運站到發線運用與列車運行調整協同優化問題的線性0-1規劃模型，采用商業優化軟件CPLEX對模型進行求解，以驗證模型的正確性.同時，為提高問題求解效率，設計了遺傳模擬退火算法[16].

3 遺傳模擬退火算法

3.1 染色體編碼

染色體編碼采用一維實數編碼的形式，每個染色體的長度為列車數量|L|，染色體的基因按照列車計劃或預計到達時間由小到大的順序進行編號，每個基因值的取值范圍均為[1,|I|].每個染色體都對應一個到發線分配方案，如圖4所示.

圖4 染色體編碼示意圖

3.2 生成初始種群

采用如下的初始種群個體生成策略：

(1) 固定在列車晚點發生之前到達客運站的列車所使用的到發線，所分配到發線為初始到發線運用方案中這部分列車所使用的到發線；

(2) 對于下行到發線，將剩余未固定到發線的下行列車隨機地平均分配到下行到發線上；對于上行到發線，執行類似操作；

(3) 重復(1)和(2)，直至所有初始種群個體生成完畢.

3.3 生成可行解

設計的染色體只確定每列列車所要占用的到發線空間資源，而未考慮由于不滿足到發線作業安全間隔時間、車站到達追蹤間隔時間和車站出發追蹤間隔時間等安全作業要求，而引起的3類時間資源沖突.在調整列車的到達和出發時間來消解時間資源沖突時，若沖突是由于不滿足到發線作業安全間隔時間和車站到達追蹤間隔時間要求而引起的，則需要將列車的到達時間和出發時間調整相同的值；否則，若沖突是由于不滿足車站出發追蹤間隔時間而引起，則只需要調整列車的出發時間來消解沖突.

下面對消解由于不滿足到發線安全作業間隔時間要求而引起的時間資源沖突的啟發式規則進行介紹，消解另外兩類時間資源沖突的規則與此類似.

(1) 將所有列車按照計劃或預計到達時間由小到大的順序進行排序，并從1到|L|進行編號；

(2) 根據給定的列車順序和表2中的算法疏解列車占用到發線時間資源沖突；

表2 列車占用到發線時間資源沖突疏解算法

Tab.2 Conflicts resolving algorithm for the occupancy of arrival and departure track time resources

每列車i(1≤i≤|L|) 每列車j(1≤j

(3) 計算所有列車實際到達和實際出發時間分別相對于計劃或預計到達和出發時間的總調整量，該值即為染色體的目標函數值.

3.4 確定適應度函數

適應度函數參考文獻[16]中的遺傳模擬退火算法部分的適應度函數如下：

(35)

式中：tk表示種群進化到第k代時的溫度；f(i)表示第i個染色體的目標函數值；fmin為第k代種群中最小的目標函數值；fi(tk)則表示第i個染色體在溫度為tk時的適應度值.

3.5 確定溫度下降函數

在確定初始溫度T后，采用如式(36)所示溫度下降函數進行降溫，即

tk=Tαk

(36)

式中：tk為種群進化到第k代時的溫度；α為溫度下降速率.在本文所設計的遺傳模擬退火算法中，若全局最優個體目標函數值連續n代不發生改變，則將溫度提升至T/2.

3.6 遺傳操作

3.6.1鄰域搜索

對種群中的每一個染色體進行鄰域搜索操作，即隨機改變染色體i的任意一個位置的基因值，以產生新的染色體j，計算染色體j的目標函數值f(j)，根據模擬退火算法的Metropolis準則接受或拒絕染色體j[16].

(37)

若Pij(tk)大于[0,1)區間的隨機數r1，則將染色體j替換染色體i.

3.6.2選擇

采用輪盤賭的方法選擇父代個體，根據個體適應度值計算累積概率如下：

(38)

式中，N為種群規模.產生[0,1)區間的隨機數r2，若r2∈(Ci,Cj)，則個體j被選擇作為父代.本文采用精英保留策略，即種群中適應度值最高的個體不經過交叉、變異操作而直接保留至子代，因此，在選擇操作中也不能選擇該個體.同時，為避免算法過早收斂于局部最優解，在選擇操作中限制個體連續被選中作為父代.

3.6.3交叉

每次隨機選擇兩個父代個體，并產生[0,1)區間的隨機數r3，若r3大于或等于交叉率，則不進行交叉操作，將兩個父代個體直接保留至子代；否則，采用兩點交叉算子進行交叉.

3.6.4變異

對于染色體的每一個基因，若該基因所對應的列車不是在列車晚點發生之前到達客運站，則產生[0,1) 區間的隨機數r4.若r4大于或等于變異率，則不進行變異操作；否則，隨機為該基因分配一條不同的到發線.

4 算例分析

圖5 客運站拓撲結構

Fig.5 Layout of the passenger stations

Fig.6 Arrival and departure track utilization scheme between 16:00 and 22:00

假設該客運站從18：38時刻得知有6列下行列車和4列上行列車將晚點到達，已知這些列車晚點后預計到達客運站的時間，由此可以推算出這些列車的到達晚點量、預計到達和出發時間如表6所示.由表2可知，到發線計劃作業時間的最大值Δmax為43 min，研究時段長度T為360 min，取到發線作業安全間隔時間D為6 min，因此MT為366 min，取車站到達追蹤間隔時間和車站出發追蹤間隔時間均為5 min.同時，設置目標函數第一項的加權系數α為200.

以表3～表6中的數據及其他已知參數作為模型輸入，在CPU為Intel(R) Core(TM) i7-5600U 2.6 GHZ、內存為12G的電腦上，采用C#編程語言調用商業優化軟件IBM ILOG CPLEX 12.7.0求解算例模型，CPLEX的相關參數均為默認值.CPLEX在運行679 s后求得問題最優解，問題最優目標函數值為17 059.經調整后，11列車的到達時間或出發時間被推遲，以滿足到發線沖突約束和車站追蹤間隔時間約束，如表7所示，且有13列車所使用的到發線發生改變.模型所求得的調整后的到發線使用情況如表8所示，將調整后的到發線使用情況繪制成圖后如圖7所示.由圖7可以看出，同一條到發線上相鄰兩列車的間隔時間均不小于到發線作業安全間隔時間，且不同到發線上的同向列車間均滿足車站追蹤間隔時間約束.

表3 16:0022:00時段到發列車

表4 16:0022:00時段計劃到發線使用情況

表5 不同方向、不同等級列車使用客運站到發線費用

表6 晚點列車的預計到達和出發時間

表7 被推遲列車的到達時間和出發時間推遲量

表8 調整后16:0022:00時段到發線使用情況

表9 不同目標函數加權系數α取值下CPLEX與遺傳模擬退火算法求解結果

Tab.9 Solving results of CPLEX and the Genetic Algorithm-Simulated Annealing Hybrid Algorithm with different objective function weighting coefficients

目標函數加權系數αCPLEX遺傳模擬退火算法目標函數值求解時間/s目標函數值求解時間/s與CPLEX相差百分比/%403 9397404 140285.10807 2195897 507283.9912010 49976410 914283.9516013 78344714 233283.2620017 05967917 612273.2424020 33938820 951273.0128023 61936024 342273.0632026 89959627 681282.9136030 17932931 069282.9540033 45934034 402292.8244036 73941237 808282.91

5 結論

鐵路客運站到發線運用方案調整對于保證列車運行安全、提高到發線運用效率和盡快恢復列車正點運行具有重要意義.客運站到發線運用方案調整問題從根本上來說是到發線時空資源的分配與調整問題，本文使用離散化的到發線時空資源變量針對問題建立了線性0-1規劃模型并設計了遺傳模擬退火算法進行求解，所提出方法具有如下特征：

(1) 離散化的到發線時空資源變量從微觀上描述了到發線使用過程原理，基于此定義，問題模型約束精煉到了到發線時空資源使用約束和列車在站作業過程兩大類；

(2) 模型綜合考慮了列車運行計劃和列車對到發線的使用要求，在此基礎上對客運站到發線運用方案進行調整，以得到盡量不改變列車運行計劃條件下的新的到發線運用方案，而若由于客運站到發線能力不足，導致列車運計劃被改變，其改變量可以作為列車調度員隨后進行列車運行調整的依據；

(3) 離散化變量的引入使得模型變量規模較大，引入的有效不等式通過對無效約束的消除等提高了模型效率，使其能使用主流優化軟件進行求解；

(4) 通過實例驗證表明，結合問題特點而設計的遺傳模擬退火算法可以快速對問題進行求解，實現了客運站到發線運用方案的實時調整.

本文所設計的遺傳模擬退火算法采用了到發線時間和空間資源占用分步求解的思路，未來將考慮到發線時間和空間資源同時分配的更加有效的啟發式算法.此外，本文僅考慮了適用于客運站的到發線運用方案調整模型與算法，并未考慮包含復雜調車作業的技術站，在下一步研究中將進一步研究考慮調車作業的建模方法以及技術站到發線運用方案調整問題的模型與求解方法.