劉　偉，朱曉寧

(北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京 100044)

數(shù)字出版日期： 2017-04-24

0　引言

安全是鐵路運(yùn)輸?shù)幕疽?，是鐵路一切工作的基礎(chǔ)。鐵路大型客站的咽喉區(qū)和到發(fā)線的應(yīng)用十分復(fù)雜，車站在接發(fā)車作業(yè)時(shí)應(yīng)滿足安全約束、行車約束等。針對(duì)鐵路運(yùn)輸安全，張殿業(yè)等[1]提出了鐵路運(yùn)輸安全研究的框架體系；范振平等[2]分析了鐵路運(yùn)輸生產(chǎn)中的不利因素，探討了鐵路安全預(yù)警系統(tǒng)的實(shí)現(xiàn)。在車站安全作業(yè)的要求下，車站到發(fā)線作為鐵路客運(yùn)站基礎(chǔ)設(shè)施的關(guān)鍵資源和重要組成部分，在接、發(fā)車作業(yè)中發(fā)揮著不可替代的作用[3-6]。針對(duì)鐵路車站到發(fā)線作業(yè)優(yōu)化問(wèn)題，國(guó)內(nèi)外學(xué)者建立了相關(guān)數(shù)學(xué)優(yōu)化模型，如Carey等[7]構(gòu)建了到發(fā)線分配優(yōu)化的混合整合規(guī)劃模型；Zwaneveld等[8]采用點(diǎn)包裝問(wèn)題描述到發(fā)線運(yùn)用問(wèn)題，建立了0-1整數(shù)規(guī)劃模型；Cardillo等[9]基于客運(yùn)站的到發(fā)線分配優(yōu)化，建立圖染色模型。此外，Billionnet等[10]定義相容進(jìn)路集，將車站到發(fā)線優(yōu)化視為帶有權(quán)重的點(diǎn)包裝問(wèn)題，構(gòu)造了無(wú)向圖，采用分支定界法求解。Li等[11]建立了鐵路客站到發(fā)線選擇的優(yōu)化模型，將車站的作業(yè)能力作為約束條件，并使用K短路算法進(jìn)行求解。D’Ariano等[12-13]通過(guò)模擬人工調(diào)度，針對(duì)復(fù)雜車站列車到發(fā)線運(yùn)用調(diào)整問(wèn)題設(shè)計(jì)相應(yīng)啟發(fā)式算法。

在保障列車進(jìn)站作業(yè)安全的條件下，通過(guò)提高旅客列車的準(zhǔn)點(diǎn)率，采取動(dòng)態(tài)時(shí)刻表的方式，可優(yōu)化車站作業(yè)，消除列車在站內(nèi)的作業(yè)沖突，確保行車安全[14-15]。Huisman等[16]研究不確定列車運(yùn)行圖問(wèn)題，考慮線路通過(guò)能力，根據(jù)防沖突的疏解原則建立了列車進(jìn)出站模型；Burdet等[17]對(duì)車站能力進(jìn)行評(píng)估，并設(shè)計(jì)隨機(jī)貪婪搜索算法計(jì)算車站最大通過(guò)能力；Castillo等[18]和Corman等[19]基于列車運(yùn)行圖，優(yōu)化列車進(jìn)出站路徑。

隨著列控技術(shù)的發(fā)展，鐵路技術(shù)裝備水平的提升，鐵路安全行車和準(zhǔn)點(diǎn)率水平顯著提高。然而，由于鐵路運(yùn)輸網(wǎng)絡(luò)的開(kāi)放性和運(yùn)輸組織工作的復(fù)雜性，存在各種不確定因素的干擾，如車站設(shè)備故障、出現(xiàn)極端天氣、區(qū)間線路損壞、節(jié)假日旅客集中進(jìn)站上車和臨客的大規(guī)模開(kāi)行等，造成不同規(guī)模、不同程度的晚點(diǎn)，車站到發(fā)線分配又受制于各種安全條件約束，因而需要根據(jù)實(shí)際情況及時(shí)調(diào)整到發(fā)線使用，避免列車晚點(diǎn)傳播。因此，基于安全約束對(duì)列車晚點(diǎn)情況下的到發(fā)線調(diào)整優(yōu)化具有重要的實(shí)用價(jià)值。鑒于此，本文研究基于安全約束的客站晚點(diǎn)列車到發(fā)線分配優(yōu)化。采用混合整數(shù)建模方法建立優(yōu)化模型，設(shè)計(jì)模擬退火算法進(jìn)行求解，并以寶雞站為例進(jìn)行案例分析。

1　基于安全約束的到發(fā)線分配優(yōu)化模型

1.1　問(wèn)題提出

如圖1所示，正點(diǎn)情況下列車T3到達(dá)車站時(shí)刻t1，離開(kāi)車站時(shí)刻t5，停留Ⅰ道；T1到達(dá)車站時(shí)刻t2，離開(kāi)車站時(shí)刻t3，停留Ⅱ道；T2到達(dá)車站時(shí)刻t4，離開(kāi)車站時(shí)刻t6，停留Ⅱ道。當(dāng)列車T1晚點(diǎn)至t4到達(dá)，此時(shí)出現(xiàn)列車進(jìn)站安全沖突，列車T1與T2在滿足安全約束條件下的進(jìn)站的先后次序，在實(shí)際接發(fā)車作業(yè)過(guò)程中是一個(gè)優(yōu)化決策問(wèn)題。此外，后進(jìn)站列車T1(或T2)停留在Ⅰ道還是Ⅱ道(待T3離站)，也是一個(gè)決策優(yōu)化。以上示例僅考慮兩條到發(fā)線，一列車發(fā)生晚點(diǎn)的到發(fā)線優(yōu)化調(diào)整問(wèn)題。在實(shí)際作業(yè)中列車晚點(diǎn)時(shí)有發(fā)生，且當(dāng)問(wèn)題的規(guī)模逐漸擴(kuò)大(到發(fā)線數(shù)、列車數(shù)、晚點(diǎn)車數(shù))，同樣需要滿足安全條件約束，該組合優(yōu)化問(wèn)題的復(fù)雜度呈幾何增長(zhǎng)。為此，本文研究基于安全約束的客站晚點(diǎn)列車到發(fā)線分配優(yōu)化，可為該問(wèn)題提供科學(xué)的理論依據(jù)。

圖1　鐵路車站列車晚點(diǎn)示意Fig.1　Train delay in a railway station

1.2　數(shù)學(xué)模型

1.2.1模型假設(shè)

模型建立基于以下假設(shè)：不存在行車事故，站內(nèi)設(shè)施設(shè)備均能正常使用；任意列車遍歷咽喉區(qū)單個(gè)道岔占用時(shí)間已知；前后兩列列車進(jìn)入同一到發(fā)線的安全時(shí)間間隔為常量。

1.2.2集合符號(hào)定義

集合定義：車站道岔組集合D，任意道岔組d∈D，D={d|d=1,2,...,n}，其中n為道岔組總數(shù)；階段計(jì)劃內(nèi)到發(fā)列車集合L，任意列車l∈L，L={l|l=1,2,...,m}，其中m為該階段計(jì)劃內(nèi)的列車到發(fā)總數(shù)；車站到發(fā)線集合，任意到發(fā)線g∈G，G={g|g=1,2,...,r}，其中r為到發(fā)線總數(shù)。

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

(1)

(2)

判斷列車l晚點(diǎn)到達(dá)車站時(shí)，預(yù)設(shè)到發(fā)線g是否空閑。?g,g′∈G,?l∈L：

(3)

式(3)表示列車是否進(jìn)入預(yù)設(shè)到發(fā)線。正點(diǎn)情況下列車l進(jìn)入預(yù)設(shè)到發(fā)線g，當(dāng)發(fā)生晚點(diǎn)后需判斷到發(fā)線g是否空閑。若到發(fā)線g空閑則晚點(diǎn)列車l可進(jìn)入該到發(fā)線；若到發(fā)線g繁忙則晚點(diǎn)列車需等待或另行分配。引入0～1變量αl，?g,g′∈G,?l∈L：

(4)

式(4)表示列車是否進(jìn)入原到發(fā)線。當(dāng)αl=1，則列車l進(jìn)入預(yù)設(shè)到發(fā)線；反之，需另行分配到發(fā)線。

其次，判斷該時(shí)刻是否有多列車同時(shí)到達(dá)，?g,g′∈G,?l∈L：

(5)

引入指標(biāo)函數(shù)f(αl,βg)：

f(αl,βg)=αl+βg

(6)

式(6)表示對(duì)列車到發(fā)線分配的方案設(shè)置。根據(jù)f(αl,βg)大小，對(duì)車站列車出現(xiàn)晚點(diǎn)情況下的到發(fā)線再分配計(jì)劃設(shè)閾值，根據(jù)閾值的大小，嵌入表1的操作。

表1　不同情況下的列車進(jìn)站操作

針對(duì)有多列車同時(shí)進(jìn)站，且其預(yù)設(shè)到發(fā)線相同的情況下，考慮列車權(quán)重系數(shù)wl。列車權(quán)重系數(shù)wl越大，安排其進(jìn)入預(yù)設(shè)到發(fā)線的可能性越大。當(dāng)出現(xiàn)表1中的情況2時(shí)，權(quán)重系數(shù)wl最大的列車進(jìn)入到發(fā)線g，其余列車另行分配。當(dāng)出現(xiàn)情況4時(shí)，根據(jù)不同列車的權(quán)重大小，逐一分配到發(fā)線。情況1和3由于只存在一列列車，因此，權(quán)重系數(shù)不必考慮。

對(duì)晚點(diǎn)情況下的列車進(jìn)站咽喉利用和到發(fā)線分配，本文以列車二次延誤時(shí)間最小化為目標(biāo)，考慮各趟列車的權(quán)重大小，目標(biāo)函數(shù)如公式(7)：

(7)

1.2.4模型約束條件

1)進(jìn)站道岔組安全約束

(8)

2)停站到發(fā)線安全約束

(9)

式(9)表示到發(fā)線占用安全約束。為確保進(jìn)站作業(yè)安全，1個(gè)時(shí)間段內(nèi)，1條到發(fā)線只能接發(fā)1列列車。

3)進(jìn)站列車必須安排到發(fā)線約束

(10)

式(10)表示必須給進(jìn)站列車l安排一條到發(fā)線進(jìn)行停站作業(yè)。

4)出站道岔組安全約束

(11)

5)防沖突安全約束

(12)

式(12)表示列車進(jìn)站防沖突安全約束，一般而言列車進(jìn)入到發(fā)線前要求到發(fā)線已清空。具體要求到發(fā)線的占用時(shí)段間需要有一段安全間隔時(shí)間，防止列車之間發(fā)生進(jìn)、出站沖突。Tmin表示最小安全時(shí)間間隔。

2　模擬退火算法

客站咽喉利用與到發(fā)線分配優(yōu)化問(wèn)題是一類NP-hard問(wèn)題，問(wèn)題復(fù)雜度高且較難求解，本文采用基于模擬退火算法的啟發(fā)式算法求解以上模型。模擬退火算法的解的表示與迭代如圖2所示，解的橫軸表示到發(fā)線號(hào)，縱軸表示列車。單一父代解產(chǎn)生子代解的方法：通過(guò)變異任一列車的停站到發(fā)線，并檢查是否滿足約束條件，決定是否保留該子代解。兩個(gè)父代解產(chǎn)生子代解的方法：兩個(gè)父代解通過(guò)交換某列車的停站到發(fā)線生成兩個(gè)子代解，檢查子代解是否滿足約束，若滿足則保留該子代解。通過(guò)比較上述解的優(yōu)劣，選擇性保留最優(yōu)解作為下一次迭代的開(kāi)始。

具體求解步驟如下：

第1步，初始化。

1)初始輸入。初始溫度值T0，算法停止溫度τ，降溫系數(shù)ω以及馬爾科夫鏈長(zhǎng)度L為算法的初始輸入值。

2)基礎(chǔ)數(shù)據(jù)讀取。讀取車站咽喉結(jié)構(gòu)，輸入咽喉道岔組占用時(shí)間以及安全間隔時(shí)間ΔT、Tmin，列車的時(shí)刻及晚點(diǎn)時(shí)間。

3)產(chǎn)生初始解。初始化當(dāng)前溫度T=T0，隨機(jī)產(chǎn)生初始解s0，計(jì)算目標(biāo)函數(shù)值f(0)，檢查約束條件公式(8)～(12)，若滿足條件保留該初始解，如果不滿足通過(guò)交叉產(chǎn)生新解，直至滿足約束條件。

圖2　模擬退火算法解的表示Fig.2　Solution expressions of the simulated annealing algorithm

圖3　寶雞車站站場(chǎng)示意Fig.3　Map of the station bottleneck structure (Baoji, China)

第2步，迭代優(yōu)化。

1)產(chǎn)生新解。初始解通過(guò)交換某列車的停站到發(fā)線生成一個(gè)新的子代解，兩個(gè)父代解通過(guò)交換某列列車的停站到發(fā)線產(chǎn)生兩個(gè)新子代解sn

2)新解判斷。判斷以上子代解是否滿足約束條件(8)～(12)，并計(jì)算滿足約束條件解的目標(biāo)函數(shù)值f(η)，計(jì)算當(dāng)前解與前解的目標(biāo)函數(shù)之差Δf，Δf=f(η)-f(η-1)。若Δf≤0，則sn替換sn-1，否則采用隨機(jī)概率事件讓sn替換sn-1，概率為ρ=exp(-Δf/T)。

3)迭代終止判斷。對(duì)于當(dāng)前溫度T，如果T≤τ，停止；否則更新T=T×ω，繼續(xù)進(jìn)行下一次迭代。

3　實(shí)例研究

為了測(cè)試模型與算法的有效性，選取寶雞車站作為案例進(jìn)行研究與分析。圖3為寶雞站站場(chǎng)示意圖，其中到發(fā)線11條(股道VII，VIII號(hào)為正線)，道岔組28組。寶雞車站分為左右兩側(cè)咽喉，左側(cè)咽喉由奇數(shù)號(hào)道岔組構(gòu)成(1-3-5-…-25)，右側(cè)咽喉由偶數(shù)號(hào)道岔組構(gòu)成(2-4-6-…-28)，表2為列車時(shí)刻表相關(guān)信息。

表2　寶雞車站部分列車初始時(shí)刻

注：由于缺乏實(shí)際的列車延誤數(shù)據(jù)，本表采用正態(tài)分布模擬了列車延誤概率及時(shí)長(zhǎng)。

3.1　延誤處理

為表示列車是否延誤，采用延誤概率計(jì)算。本文假設(shè)列車的延誤概率成正態(tài)分布，如表2所示，設(shè)為該列車的延誤概率。

(γl-1)·M≤(δl-Xl)≤γl·M

(13)

式(13)表示延誤列車。其中，M為極大整數(shù)；γl為0-1變量，表示列車l是否按延誤處理。若γl=1，則按延誤處理；若γl=0則按正點(diǎn)處理。當(dāng)延誤概率δl大于等于閾值Xl時(shí)，γl=1；否則，γl=0。

εl′=εl·γl

(14)

式(14)表示列車延誤時(shí)長(zhǎng)。εl為列車的預(yù)設(shè)延誤時(shí)長(zhǎng)，根據(jù)延誤概率計(jì)算列車的延誤時(shí)長(zhǎng)εl′。

3.2　優(yōu)化結(jié)果

取Xl為0.5，對(duì)表3中列車延誤概率及延誤時(shí)長(zhǎng)進(jìn)行統(tǒng)計(jì)，延誤列車數(shù)12列，延誤總時(shí)長(zhǎng)333 min。到發(fā)線的占用頻次分別為[2 1 3 3 2 2 2 5 3 3 2]，其中，到發(fā)線8占用頻次最高，為5次；到發(fā)線2占用頻次最低，為1次；其余各條到發(fā)線均占用2到3次不等。

表3　列車延誤后到發(fā)線分配及道岔組組成優(yōu)化結(jié)果

3.3　延誤時(shí)長(zhǎng)分析

改變列車延誤總時(shí)長(zhǎng)，分析列車延誤時(shí)長(zhǎng)對(duì)車站到發(fā)線分配的影響。將列車延誤數(shù)量逐一疊加，產(chǎn)生變化的延誤總時(shí)長(zhǎng)。根據(jù)寶雞車站的列車運(yùn)行時(shí)刻表，假設(shè)列車延誤數(shù)量是離散變量，變量值范圍為1～7，統(tǒng)計(jì)相應(yīng)的延誤時(shí)間，分別從30～202 min，優(yōu)化后的結(jié)果見(jiàn)表4。發(fā)現(xiàn)隨著列車延誤總時(shí)長(zhǎng)的增加，列車的二次延誤時(shí)長(zhǎng)呈(準(zhǔn))對(duì)數(shù)函數(shù)遞增。

表4　列車延誤總時(shí)長(zhǎng)分析

3.4　延誤時(shí)長(zhǎng)與延誤車數(shù)熱力分析

列車調(diào)度優(yōu)化中準(zhǔn)點(diǎn)率是一個(gè)非常重要的指標(biāo)。隨著延誤列車數(shù)量的遞增(如受到延誤傳播的影響)，二次延誤時(shí)長(zhǎng)勢(shì)必增加。造成列車二次延誤的原因除了受車站資源有限影響，也跟列車晚點(diǎn)時(shí)長(zhǎng)相關(guān)。因此，分析延誤列車數(shù)量與列車延誤時(shí)長(zhǎng)之間的熱力關(guān)系，能夠給調(diào)度工作者一定的科學(xué)指導(dǎo)。在此，假定列車延誤數(shù)量按線性增加，即1到N；各次列車的延誤時(shí)長(zhǎng)亦呈線性遞增關(guān)系，即5到t′ min。

圖4　列車延誤數(shù)量與延誤時(shí)長(zhǎng)對(duì)二次延誤的影響Fig.4　Influence of the number of delayed trains and delay times on the second-delay times

測(cè)試以上實(shí)驗(yàn)數(shù)據(jù)，得到圖4和表5所示結(jié)果。發(fā)現(xiàn)當(dāng)列車延誤時(shí)長(zhǎng)較短時(shí)(如2 min)，隨著延誤車數(shù)的增加，列車二次延誤時(shí)間遞增較緩慢。該結(jié)果說(shuō)明寶雞車站的列車到達(dá)間隔時(shí)間預(yù)留較合理，滿足車站接發(fā)車安排作業(yè)的魯棒性特征。當(dāng)列車延誤時(shí)長(zhǎng)增加至10 min時(shí)，延誤車數(shù)的影響逐漸凸顯。而當(dāng)列車延誤時(shí)長(zhǎng)突增至24 min時(shí)，只需幾列列車延誤，便會(huì)造成長(zhǎng)時(shí)間的二次延誤。以上結(jié)論說(shuō)明，調(diào)度在安排列車晚點(diǎn)情況下的到發(fā)線分配作業(yè)時(shí)，首先建議考慮列車的延誤時(shí)長(zhǎng)，當(dāng)延誤時(shí)長(zhǎng)較長(zhǎng)時(shí)，需要優(yōu)先解決延誤車數(shù)問(wèn)題，即優(yōu)先安排非延誤列車的進(jìn)站作業(yè)；當(dāng)延誤時(shí)長(zhǎng)在可控范圍內(nèi)，可以遵循“先到先服務(wù)”(First-in-first-service)原則，逐一安排到站列車完成到、發(fā)作業(yè)。

表5　二次延誤時(shí)長(zhǎng)

4　結(jié)論

1)建立了列車到發(fā)線分配優(yōu)化混合整數(shù)規(guī)劃模型，設(shè)計(jì)了模擬退火算法求解該大規(guī)模NP-hard問(wèn)題。

2)以寶雞車站案例分析表明，當(dāng)列車晚點(diǎn)時(shí)間較短情況下，列車依次進(jìn)站作業(yè)一般能滿足安全約束，可采取“先到先服務(wù)”原則，當(dāng)有多列列車晚點(diǎn)且時(shí)間較長(zhǎng)時(shí)，在滿足安全約束條件下，優(yōu)先安排非晚點(diǎn)列車進(jìn)站作業(yè)才能有效避免晚點(diǎn)傳播。

[1]張殿業(yè), 金鍵, 楊京帥. 鐵路運(yùn)輸安全理論與技術(shù)體系[J]. 中國(guó)鐵道科學(xué),2005(5):114-118.

ZHANG Dianye, JIN jian, YANG Jingshuai. Railway transportation safety theory and technology system[J], China Railway Science, 2005(5):114-118.

[2]范振平, 林柏梁, 李俊衛(wèi).鐵路局安全預(yù)警系統(tǒng)的研究[J].交通運(yùn)輸系統(tǒng)工程與信息,2006(12):149-152.

FAN Zhenping, LIN Boliang, LI Junwei. Study on security early warning system of railroad bureau[J]. Journal of Transportation Systems Engineering and Information Technology, 2006(12):149-152.

[3]Kang L J, Wu J J, Sun H J. Using simulated annealing in a bottleneck optimization model at railway stations. Journal of Transportation Engineering [J]. 2012, 138: 1396-1402.

[4]張嘉敏, 韓寶明. 鐵路列車占用車站股道時(shí)序優(yōu)化研究[J]. 交通運(yùn)輸系統(tǒng)工程與信息, 2011,11(3): 100-107.

ZHANG Jianmin, HAN Baoming. Optimization on the occupation order for trains on tracks of the railway station[J]. Journal of Transportation Systems Engineering and Information Technology, 2011, 11(3): 100-107.

[5]青學(xué)江,馬國(guó)忠.遺傳算法在區(qū)段站到發(fā)線的應(yīng)用研究[J]. 西南交通大學(xué)學(xué)報(bào), 1998(4): 387-393.

QING Xuejiang. MA Guozhong. Application of GA to arrival and departure lines in district stations[J]. Journal of Southwest Jiaotong University, 1998(4): 387-393.

[6]雷定猷, 王棟, 劉明翔. 客運(yùn)站股道運(yùn)用優(yōu)化模型及算法[J]. 交通運(yùn)輸工程學(xué)報(bào), 2007(5):84-87.

LEI Dingyou, WANG Dong, LIU Mingxiang. Optimization model and algorithm of utilization of arrival and departure tracks in railroad passenger station [J]. Journal of Traffic and Transportation Engineering, 2007(5): 84-87.

[7]Carey M. A model and strategy for train pathing with choice of lines, platforms, and routes [J]. Transportation Research Part B Methodological, 1994, 28(5):333-353.

[8]Zwaneveld P J, Ambergen H W. Routing trains through railway stations: Model Formulation and Algorithms [J]. Transportation Science, 1996, 30(3):181-194.

[9]Cardillo D D L, Mione N. k L-list colouring of graphs [J]. European Journal of Operational Research, 1998, 106(1):160-164.

[10]Billionnet A. Using integer programming to solve the train-platforming problem [J]. Transportation Science, 2003, 37(2):213-222.

[11]Li Y, Zhao J, Cheng J. Model and algorithm for passenger station task allocation problem in railway terminal [J]. Journal of Transportation Engineering, 2010, 2590-2596.

[12]D’Ariano A, Dario, P. Assessment of flexible timetables in real-time traffic management of a railway bottleneck [J]. Transportation Research Part C. 2008, 16:232-245.

[13]Andrea DA, Dario P. Assessment of flexible timetables in real time traffic management of a railway bottleneck [J]. Transportation Research Part C, 2008, 16: 232-245.

[14]Delorme X, Gandibleux X, Rodriguez J. GRASP for set packing problems [J]. European Journal of Operational Research, 2004, 153(3): 564-580.

[15]Zwaneveld P J, Kroon LG, Hoesel S P M V. Routing trains through a railway station based on a node packing model [J]. European Journal of Operational Research, 2001, 128(1):14-33.

[16]Huisman T, Boucherie R J. Running times on railway sections with heterogeneous train traffic [J]. Transportation Research Part B, 2001, 35 (3): 271-292.

[17]Burdet T R L, Kozan E. A disjunctive graph model and framework for constructing new train schedules [J]. European Journal of Operation Research, 2010, 200(1):85-98.

[18]Castillo E, Gallego I, Uuena G J, Time tabling optimization of a mixed double and single tracked railway network [J]. Applied Mathematical Modeling, 2011, 35(2):859-878.

[19]Corman F, Dariano A, Pacciarelli D. A tabu search algorithm for rerouting trains during rail operations [J]. Transportation Research Part B: Methodological, 2010, 44(1):175-192.