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

(1. 西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 610031；2. 西南交通大學(xué) 綜合交通運(yùn)輸智能化國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室，四川 成都 610031)

鐵路客運(yùn)站到發(fā)線運(yùn)用方案是客運(yùn)站作業(yè)計(jì)劃的重要內(nèi)容之一，其目的在于最大限度地滿足不同類型的列車按照運(yùn)行計(jì)劃在客運(yùn)站進(jìn)行到發(fā)的作業(yè)需求.合理的到發(fā)線運(yùn)用計(jì)劃不僅是列車在站安全地完成行車作業(yè)的基本保障，而且可以實(shí)現(xiàn)方便旅客乘降、提高客運(yùn)站作業(yè)效率以及保證客運(yùn)站設(shè)備均衡使用等.但是，當(dāng)惡劣天氣、線路故障等原因?qū)е铝熊嚧罅客睃c(diǎn)到達(dá)，導(dǎo)致客運(yùn)站到發(fā)線能力緊張時(shí)，原有的到發(fā)線運(yùn)用方案已不能適應(yīng)變化了的列車作業(yè)要求，必須對(duì)客運(yùn)站到發(fā)線運(yùn)用方案進(jìn)行調(diào)整，以保證列車運(yùn)行安全和盡快恢復(fù)列車正點(diǎn)運(yùn)行.

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

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

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

本文首先分析了鐵路到發(fā)線資源的離散化時(shí)空描述方法，在此基礎(chǔ)上以列車加權(quán)總晚點(diǎn)時(shí)間與到發(fā)線使用費(fèi)用之和最小為優(yōu)化目標(biāo)，以保證列車運(yùn)行安全和滿足列車在站到發(fā)作業(yè)要求為約束條件，建立了求解客運(yùn)站到發(fā)線運(yùn)用方案調(diào)整問(wèn)題的線性0-1規(guī)劃模型，并設(shè)計(jì)了遺傳模擬退火算法對(duì)模型進(jìn)行求解，從而解決了客運(yùn)站到發(fā)線運(yùn)用方案調(diào)整問(wèn)題.

1 問(wèn)題分析

1.1 鐵路到發(fā)線資源的時(shí)空描述

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

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

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

a 示例車站A布置示意

b A站某時(shí)段下行列車運(yùn)行c A站某時(shí)段上行列車運(yùn)行

圖1 客運(yùn)站A布置及列車運(yùn)行

Fig.1Layout and train diagrams of passengerstation A

a 到發(fā)線資源使用情況

b 到發(fā)線資源矩陣

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

根據(jù)以上定義，列車在站作業(yè)過(guò)程對(duì)到發(fā)線資源占用有如下特征：

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

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

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

1.2 鐵路到發(fā)線運(yùn)用問(wèn)題分析

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

根據(jù)列車占用到發(fā)線時(shí)空資源的特征，在調(diào)整到發(fā)線運(yùn)用方案時(shí)，要考慮列車占用到發(fā)線的唯一性和連續(xù)性.此外，為滿足旅客的出行方便和乘降作業(yè)要求，一般情況下被調(diào)整列車的實(shí)際到達(dá)和出發(fā)時(shí)間應(yīng)分別不早于其計(jì)劃到達(dá)和出發(fā)時(shí)間，并保證被調(diào)整列車的運(yùn)行安全.在滿足以上條件的基礎(chǔ)上，考慮不同列車等級(jí)和列車對(duì)到發(fā)線的使用要求，實(shí)現(xiàn)在保證列車運(yùn)行安全的同時(shí)，充分利用客運(yùn)站通過(guò)能力，最小化晚點(diǎn)發(fā)生后列車加權(quán)總晚點(diǎn)時(shí)間與到發(fā)線使用費(fèi)用之和.

2 模型構(gòu)建

2.1 參數(shù)及變量說(shuō)明

2.1.1參數(shù)說(shuō)明

參數(shù)匯總見(jiàn)表1.如非特別提及，所有與時(shí)間相關(guān)的參數(shù)和變量的取值均為時(shí)間間隔Δτ的整倍數(shù).

表1 參數(shù)說(shuō)明

2.1.2變量說(shuō)明

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

(1) 到發(fā)線選擇變量

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

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

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

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

(1)

例如對(duì)于圖1示例客運(yùn)站A，當(dāng)列車l在時(shí)刻5占用下行到發(fā)線5并在時(shí)刻20離開(kāi)，上述3個(gè)變量ul,i,t、vl,i,t和xl,i,t對(duì)于該過(guò)程描述的取值分別如圖3所示.

a ul,i,t

b vl,i,t

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

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

(5) 列車實(shí)際到達(dá)時(shí)間yl,a和列車實(shí)際出發(fā)時(shí)間yl,d

(2)

(3)

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

當(dāng)因部分列車晚點(diǎn)到達(dá)客運(yùn)站而需對(duì)到發(fā)線運(yùn)用方案進(jìn)行調(diào)整時(shí)，首先應(yīng)盡量不改變列車的到達(dá)和出發(fā)時(shí)間；其次，要盡量滿足列車對(duì)到發(fā)線的使用要求，本文所設(shè)計(jì)目標(biāo)函數(shù)如式(4)所示.式(4)由兩項(xiàng)之和構(gòu)成，第1項(xiàng)為列車加權(quán)總晚點(diǎn)時(shí)間，其中，列車等級(jí)越高則Pl取值越大，且α為第1項(xiàng)的加權(quán)系數(shù)；第2項(xiàng)為到發(fā)線使用費(fèi)用.

(4)

2.3 約束條件

由到發(fā)線時(shí)空資源特征和列車在站作業(yè)過(guò)程特征，客運(yùn)站到發(fā)線運(yùn)用方案調(diào)整問(wèn)題需服從到發(fā)線占用唯一性、到發(fā)線持續(xù)作業(yè)、到發(fā)線沖突、車站追蹤間隔時(shí)間、列車在站作業(yè)時(shí)間和列車到發(fā)時(shí)間等6類主要約束條件以保證列車運(yùn)行安全和滿足列車對(duì)到發(fā)線的使用要求.

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

(5)

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

(6)

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

(2) 到發(fā)線沖突約束

(7)

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

(3) 到發(fā)線持續(xù)作業(yè)約束

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)通過(guò)保證ul,i,t和vl,i,t取值的連續(xù)性來(lái)實(shí)現(xiàn)列車在某一條到發(fā)線上的持續(xù)作業(yè).

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

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

?l,k∈L:l≠k,πl(wèi)=πk

(11)

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

?l,k∈L:l≠k,πl(wèi)=πk

(12)

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

?l,k∈L,?i∈Il∩Ik:k>l,πl(wèi)=πk

(13)

zl,k=zk,l, ?l,k∈L:k>l,πl(wèi)=πk

(14)

λl,k+λk,l=1, ?l,k∈L:k>l,πl(wèi)=πk

(15)

μl,k+μk,l=1, ?l,k∈L:k>l,πl(wèi)=πk

(16)

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

(5) 列車在站作業(yè)時(shí)間約束

(17)

如果列車l占用到發(fā)線i，則列車在到發(fā)線i上的停留時(shí)間必須不小于列車計(jì)劃停站時(shí)間與到發(fā)線作業(yè)安全間隔時(shí)間之和.

(6) 列車到達(dá)和出發(fā)時(shí)間約束

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)保證列車實(shí)際到達(dá)時(shí)間不小于列車計(jì)劃到達(dá)時(shí)間；式(19)保證列車實(shí)際出發(fā)時(shí)間不小于列車計(jì)劃出發(fā)時(shí)間與到發(fā)線安全作業(yè)間隔時(shí)間之和；式(20)保證列車實(shí)際停站時(shí)間不小于計(jì)劃停站時(shí)間與到發(fā)線作業(yè)安全間隔時(shí)間之和.

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

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(wèi)=πk

(30)

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

2.4 有效不等式

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

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

式(1)～式(34)即構(gòu)成了客運(yùn)站到發(fā)線運(yùn)用與列車運(yùn)行調(diào)整協(xié)同優(yōu)化問(wèn)題的線性0-1規(guī)劃模型，采用商業(yè)優(yōu)化軟件CPLEX對(duì)模型進(jìn)行求解，以驗(yàn)證模型的正確性.同時(shí)，為提高問(wèn)題求解效率，設(shè)計(jì)了遺傳模擬退火算法[16].

3 遺傳模擬退火算法

3.1 染色體編碼

染色體編碼采用一維實(shí)數(shù)編碼的形式，每個(gè)染色體的長(zhǎng)度為列車數(shù)量|L|，染色體的基因按照列車計(jì)劃或預(yù)計(jì)到達(dá)時(shí)間由小到大的順序進(jìn)行編號(hào)，每個(gè)基因值的取值范圍均為[1,|I|].每個(gè)染色體都對(duì)應(yīng)一個(gè)到發(fā)線分配方案，如圖4所示.

圖4 染色體編碼示意圖

3.2 生成初始種群

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

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

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

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

3.3 生成可行解

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

下面對(duì)消解由于不滿足到發(fā)線安全作業(yè)間隔時(shí)間要求而引起的時(shí)間資源沖突的啟發(fā)式規(guī)則進(jìn)行介紹，消解另外兩類時(shí)間資源沖突的規(guī)則與此類似.

(1) 將所有列車按照計(jì)劃或預(yù)計(jì)到達(dá)時(shí)間由小到大的順序進(jìn)行排序，并從1到|L|進(jìn)行編號(hào)；

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

表2 列車占用到發(fā)線時(shí)間資源沖突疏解算法

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

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

(3) 計(jì)算所有列車實(shí)際到達(dá)和實(shí)際出發(fā)時(shí)間分別相對(duì)于計(jì)劃或預(yù)計(jì)到達(dá)和出發(fā)時(shí)間的總調(diào)整量，該值即為染色體的目標(biāo)函數(shù)值.

3.4 確定適應(yīng)度函數(shù)

適應(yīng)度函數(shù)參考文獻(xiàn)[16]中的遺傳模擬退火算法部分的適應(yīng)度函數(shù)如下：

(35)

式中：tk表示種群進(jìn)化到第k代時(shí)的溫度；f(i)表示第i個(gè)染色體的目標(biāo)函數(shù)值；fmin為第k代種群中最小的目標(biāo)函數(shù)值；fi(tk)則表示第i個(gè)染色體在溫度為tk時(shí)的適應(yīng)度值.

3.5 確定溫度下降函數(shù)

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

tk=Tαk

(36)

式中：tk為種群進(jìn)化到第k代時(shí)的溫度；α為溫度下降速率.在本文所設(shè)計(jì)的遺傳模擬退火算法中，若全局最優(yōu)個(gè)體目標(biāo)函數(shù)值連續(xù)n代不發(fā)生改變，則將溫度提升至T/2.

3.6 遺傳操作

3.6.1鄰域搜索

對(duì)種群中的每一個(gè)染色體進(jìn)行鄰域搜索操作，即隨機(jī)改變?nèi)旧wi的任意一個(gè)位置的基因值，以產(chǎn)生新的染色體j，計(jì)算染色體j的目標(biāo)函數(shù)值f(j)，根據(jù)模擬退火算法的Metropolis準(zhǔn)則接受或拒絕染色體j[16].

(37)

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

3.6.2選擇

采用輪盤賭的方法選擇父代個(gè)體，根據(jù)個(gè)體適應(yīng)度值計(jì)算累積概率如下：

(38)

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

3.6.3交叉

每次隨機(jī)選擇兩個(gè)父代個(gè)體，并產(chǎn)生[0,1)區(qū)間的隨機(jī)數(shù)r3，若r3大于或等于交叉率，則不進(jìn)行交叉操作，將兩個(gè)父代個(gè)體直接保留至子代；否則，采用兩點(diǎn)交叉算子進(jìn)行交叉.

3.6.4變異

對(duì)于染色體的每一個(gè)基因，若該基因所對(duì)應(yīng)的列車不是在列車晚點(diǎn)發(fā)生之前到達(dá)客運(yùn)站，則產(chǎn)生[0,1) 區(qū)間的隨機(jī)數(shù)r4.若r4大于或等于變異率，則不進(jìn)行變異操作；否則，隨機(jī)為該基因分配一條不同的到發(fā)線.

4 算例分析

圖5 客運(yùn)站拓?fù)浣Y(jié)構(gòu)

Fig.5 Layout of the passenger stations

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

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

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

表3 16:0022:00時(shí)段到發(fā)列車

表4 16:0022:00時(shí)段計(jì)劃到發(fā)線使用情況

表5 不同方向、不同等級(jí)列車使用客運(yùn)站到發(fā)線費(fèi)用

表6 晚點(diǎn)列車的預(yù)計(jì)到達(dá)和出發(fā)時(shí)間

表7 被推遲列車的到達(dá)時(shí)間和出發(fā)時(shí)間推遲量

表8 調(diào)整后16:0022:00時(shí)段到發(fā)線使用情況

表9 不同目標(biāo)函數(shù)加權(quán)系數(shù)α取值下CPLEX與遺傳模擬退火算法求解結(jié)果

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

目標(biāo)函數(shù)加權(quán)系數(shù)αCPLEX遺傳模擬退火算法目標(biāo)函數(shù)值求解時(shí)間/s目標(biāo)函數(shù)值求解時(shí)間/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 結(jié)論

鐵路客運(yùn)站到發(fā)線運(yùn)用方案調(diào)整對(duì)于保證列車運(yùn)行安全、提高到發(fā)線運(yùn)用效率和盡快恢復(fù)列車正點(diǎn)運(yùn)行具有重要意義.客運(yùn)站到發(fā)線運(yùn)用方案調(diào)整問(wèn)題從根本上來(lái)說(shuō)是到發(fā)線時(shí)空資源的分配與調(diào)整問(wèn)題，本文使用離散化的到發(fā)線時(shí)空資源變量針對(duì)問(wèn)題建立了線性0-1規(guī)劃模型并設(shè)計(jì)了遺傳模擬退火算法進(jìn)行求解，所提出方法具有如下特征：

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

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

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

(4) 通過(guò)實(shí)例驗(yàn)證表明，結(jié)合問(wèn)題特點(diǎn)而設(shè)計(jì)的遺傳模擬退火算法可以快速對(duì)問(wèn)題進(jìn)行求解，實(shí)現(xiàn)了客運(yùn)站到發(fā)線運(yùn)用方案的實(shí)時(shí)調(diào)整.

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