鐵路編組站配流與調機運用的協調決策優化

薛 鋒，陳崇雙，戶佐安

1.西南交通大學 交通運輸與物流學院，成都610031

2.北京交通大學 軌道交通控制與安全國家重點實驗室，北京100044

1 引言

鐵路編組站的調度指揮工作是通過編制與執行階段計劃來完成的。階段計劃（3～4 小時）是班計劃（12 小時）分階段的具體安排，主要解決本階段內所有列車的出發計劃、調機運用計劃和到發線運用計劃三個決策問題，其中第一個子問題確定出發列車的編組內容和車流來源（即配流），第二個子問題確定每臺調機的調車工作內容和時段，第三個子問題安排到發列車占用到發線計劃。只有合理運用調機，正確地組織解編作業，才能加速調車場的車流集結過程，縮短車輛在站停留時間，實現列車的出發計劃，因而調機運用與列車配流密不可分，而第三個問題則相對獨立[1]。如何合理地運用調機全面完成配流計劃，是值得研究的問題。在技術站中，由于區段站調機設備少，往往使接續時間合理的車流因調機的繁忙而難于實現，一些專家學者在研究區段站的配流問題時都緊密結合調機來建模和求解[2-3]。編組站雖然調機配備較多，且解體和編組作業由不同的調機擔當，但仍需以配流計劃為核心，合理決策，使列車配流與調機運用相協調。本文根據編組站的實際作業特點，構造了配流與調機運用的協調優化模型，以期實現編組站車流資源的合理分配。

2 參數定義

設T0為階段計劃開始時刻，在階段計劃時間內的出發列車的車流來源包括[4]：

（1）T0時刻已解入調車場集結等待編組的現車，可視作1 列到達列車。

（2）T0時刻到達場內待解列車車流。

（3）階段時間內預計將要到達列車車流。

（4）交換場等待轉場分解的車組，每轉場一次視作1 列到達列車。

（5）貨場、專用線、車輛段取回待分解的本站作業車、修竣車，每取回一次視作到達一列。

設本階段到達解體列車數為n，到達解體列車（含調車場現車）集合按到達時間先后記作DD={dd0,dd1,…,ddi,…,ddn}；將要編組出發的列車（不包括已編完的待發列車）數為m，編組出發列車集合按出發時間先后記作CF={cf1,cf2,…,cfj,…,cfm}；車站共有K個編組去向，構成編組去向集合QX={1,2,…,K}；車站共有D臺調機，構成集合DJ={1,2,…,D}。對于到達解體列車ddi(i=1,2,…,n，其到達時刻為Tidd；開始解體時刻為Tijt；列車ddi中具有本站編組去向號k(1 ≤k≤K)的車數為ddik；對于出發列車cfj(j=1,2,…,m)，其出發時刻為；開始編組時刻為；已編組列車cfj中具有本站編組去向號k(1 ≤k≤K)的車數為cfjk。列車解體作業時間標準為tjt，編組作業時間標準為tbz，到達列車技術作業時間標準為tdd，出發列車技術作業時間標準為tcf；表示調機d的第s(1 ≤s≤Sd)項固定作業的開始時刻，其中Sd為調機d總的固定作業項數；表示調機d的第s項固定作業的作業時間；出發列車cfj的滿軸車數為mj，配流時的方案值為Fj。

定義布爾變量：φid、φjd、λij、βj。若到達列車ddi(i=1,2,…,n)由調機d(1 ≤d≤D)解體，則φid取1，否則為0；若出發列車cfj(j=1,2,…,m) 由調機(1 ≤d≤D) 編組，則φjd取1，否則為0；若出發列車cfj能接續到達列車ddi，則λij取1，否則為0；若Fj≥0，則βj取1，否則為0。

定義決策變量：cfijk表示到達列車ddi(i=0,1,…,n)配入出發列車cfj(j=1,2,…,m)編組去向號k(1 ≤k≤K)的車數。

3 模型構造

3.1 配流約束

設M表示充分大的正數，則配流的約束條件為：

式（1）界定了出發列車中同一去向車流的配流上限；式（2）表示出發列車的基本去向組輛數約束；式（3）表示車流接續時間約束；式（4）表示列車編組輛數約束。

3.2 解體約束

式（5）表示任一列到達解體列車只能由一臺調機解體；式（6）表示到達列車解體時須完成到達技術作業；式（7）表示若兩列到達列車由同一臺調機解體，在時間上不能沖突；式（8）表示雙推單溜時，只有當前一列車解體完畢，另一列車才能開始解體；式（9）表示到達列車的解體作業與解體調機的固定作業不沖突。

3.3 編組約束

式（10）表示任一列出發列車只能由一臺調機編組；式（11）表示出發列車的最晚編組時刻須滿足技術作業時間要求，以保證正點發車；式（12）表示若兩列出發列車由同一臺調機編組，在時間上不能沖突；式（13）表示2 臺調機編組時占用同一牽出線不沖突；式（14）表示出發列車的編組作業與編組調機的固定作業不沖突。

3.4 目標函數

編組站調機運用計劃的安排是為列車合理配流服務的，而配流的最終目的是為了確保出發列車的滿軸和正點。約束式（1）～式（14）的可行域保證了出發列車的正點，因此目標函數可設定為滿軸列車數最多。

s.t. 式（1）～式（14）

式（15）表示盡可能使滿軸的出發列車數最多，即欠軸列車數最少。至此，構造了基于列車配流和調機運用約束的協調決策優化模型。一般情況下，編組站解體和編組作業由不同的調機擔當，二者在作業互不干擾，具有相對獨立性，關鍵是列車的解體和編組方案決定了出發列車的配流方案，即只有在解體、編組方案確定的情況下，才能實現對配流問題的優化。由于調機的運用和配流方案密切相關，所以確定到達列車的解體順序方案和出發列車的編組順序方案需要考慮調機的數量和調機作業方式，解體和編組時刻的具體計算公式可參考文獻[5]。

4 模型的遺傳算法求解

列車配流和調機運用約束的協調決策優化模型，其復雜性為NP 難題，不可能得到求其最優解的多項式算法。編組站列車配流與調機運用的協調決策問題對算法收斂速度有著較強的實時性要求，需要根據問題的性質提出新的啟發式算法。遺傳算法是一種以自然選擇和遺傳理論為基礎，將生物進化過程中適者生存規則與種群內部染色體的隨機信息交換機制相結合的優化搜索算法，它已經被成功地引入編組站作業優化領域用于解決大規模組合優化問題[6-8]。本文采用遺傳算法，根據運輸問題的資源分配特點進行求解[9]。編組站配流和調機運用協調決策問題有其特殊性，需設計有效的編碼及適應函數。

4.1 編碼及適應值函數

遺傳算法編碼方法靈活，且無規范的方法，在應用遺傳算法求解車列解編排序問題時，由于問題所固有的特殊性，采用傳統的二進制方式表示解空間，不僅復雜而且不便于處理不可行解的操作，最方便的編碼方式是直接利用列車解編順序作為基因。設J 為到達列車解體順序方案，B 為出發列車編組順序方案。設J 、B 對應的調機特征向量P={p1,p2,…,pu,…,pv}，pu表示解體（或編組）列車ddu（或cfu）的調機編號，v 為解體或編組列車數。

將調機特征向量P 對應的某個解體或編組順序作為個體，即任一到達列車解體方案J={ddi,dd2,…,ddu,…,ddvJ}，任一出發列車編組順序B={cfi,cf2,…,cfu,…,cfvB}。顯然，J 、B 分別為到達列車或出發列車編號的一個排列。由于列車解編順序的遺傳編碼并不能將約束條件表示出來，因此為了獲得可行的解體順序初始群體，可依據解體序號矩陣進行有效編碼，限制不可行解的產生，具體的編碼過程可參考文獻[10]。

對任一解體方案J 和編組方案B 配流時，可根據式（15）計算配流方案中欠軸列車的列數，因此可將目標函數作為適應值函數。由此，適應函數可取：

4.2 算法思路

初始時，出發列車以先發先編的原則進行排序，到達解體列車根據解體序號矩陣隨機產生若干個v 階解體順序排列作為初始群體，采用聯賽選擇規則對初始種群進行篩選，找出若干優化解。交叉規則采用非常規碼常規交配法，變異規則采用交換變異算子，從解體序號矩陣限制的列車序號中隨機選擇兩個變異點，按一定的概率進行變異，互相交換兩個基因位置。對新個體重新按適應值進行排序，排在最后的染色體性能最差，將其用上一代最優染色體代替。在利用傳統遺傳算法時，交叉概率pc和變異概率pm在迭代過程中始終不變。在求解本模型時，可取pc和pm隨著適應度動態變化，如此當種群各個體適應度趨于一致或趨于最優解時，pc和pm增大；當群體適應度比較分散時，pc和pm減小。由歷史最優解體方案，對出發列車依次進行配流，并根據當前配流方案安排解編調機；若出發列車均滿軸，則輸出配流方案及調機安排，否則根據文獻[11]的方法調整編組順序，重新構造解體序號矩陣。最后以確定迭代代數作為停止準則。算法步驟如下：

步驟1初始化遺傳算法相關參數。

步驟2以先發先編的原則進行的出發列車排序為初始條件，構造解體序號矩陣。

步驟3根據解體序號矩陣隨機產生若干個v 階解體順序排列作為初始群體。

步驟4采用聯賽選擇規則對群體進行篩選，找出若干優化解。

步驟5根據優化群體對出發列車進行配流，分別計算適應度函數值，記錄最優解體順序，并安排解體調機。

步驟6若出發列車均滿軸，則轉步驟7，否則進行交叉和變異操作，重新計算適應度函數值，記錄本次迭代最優解，將其與歷史最優解做比較，若優于歷史最優解，則用其替換歷史最優解，否則轉步驟4。

步驟7按照設定的條件，判斷迭代是否終止，若終止，則輸出歷史最優解，否則轉步驟5。

步驟8重新檢查出發列車是否均滿軸，若滿軸，則安排編組調機，同時輸出配流方案及解編調機安排，否則調整編組順序，重新構造解體序號矩陣，轉步驟3。

編組站的車流組織工作具有時變性的特征，雖然有很多算法可以得出模型的解，但是花費時間資源太多，這不符合動態調度的要求。動態調度要求優化解必須在一定時間內得到，即使所得解不一定最優，次優也可以接受。解體序號矩陣的構造方法從車流接續時間上保證了遺傳算法以此產生的初始群體都為可行解，且變異操作也在解體序號矩陣限制的列車序號中選擇，避免了不可行個體的產生。交叉和變異概率的動態變化，使個體產生的配流方案逐步接近全部滿軸。因此，由解體序號矩陣產生的群體保證了算法的收斂性。

5 算例

5.1 時間標準及到發車流數據

某編組站列車解體、編組由不同的調機擔當，解體、編組調機均為2 臺。列車到達作業時間標準為35 min，出發作業時間標準為25 min，列車解體時間標準為25 min，編組作業時間標準為25 min。選取其中一個階段的到發原始車流數據，見表1 和表2（其中10000 為調車場現車）。

表1 到達列車車流

表2 出發列車車流

5.2 算法結果分析

根據編組站配流問題的特點所改進的遺傳算法，采用了增強型的初始種群生產策略，利用解體序號矩陣限制不可行解的產生，減少了遺傳算法本身隨機性帶來的影響，并通過有限制的個體變異操作，避免了變異操作的盲目性，使變異后的種群能向高適應度方向進化，在每次變異后對母子染色體的適應度進行比較，只保留適應度高的個體，從而增強了種群適應度，使算法能夠沿著出發列車全部滿軸的方向前進，最終達到種群適應度高、運行代數和運行時間少的效果。

在求解配流方案時，在遺傳算法中設定種群規模popsize=50，初始交叉率pc=0.8，變異率pm=0.08，最大進化代數根據實例不同設定為50～100 代不等。算法采用VC++6.0 語言編程，在LENOVO 酷睿TM2 計算機上，經過多次測算，結果表明采用遺傳算法一般能在30 s 內收斂到最優解（或滿意解），其中一次以配流方案中欠軸列車數最少為目標運行得到的配流方案和調機運用方案如表3、表4和表5 所示。將表2 和表3 對比可以看出，出發列車均已滿軸。從表4 和表5 的解編調機安排分析可知，到達列車的平均待解時間為36.4 min，出發列車的平均待發時間為41.5 min，若在保證列車均滿軸的前提下以待解和待發時間最小為目標，列車的配流方案還有進一步優化的空間。

表3 最終配流方案

表4 解體調機安排

表5 編組調機安排

6 結論

本文構建的基于列車配流和調機運用約束的協調決策優化模型，能夠較好地描述編組站站配流和調機運用的協調問題。針對該問題，采用增強型的初始種群生產策略，利用解體序號矩陣限制不可行解的產生，并通過有限制的個體變異操作，使變異后的種群向高適應度方向進化。通過實例驗算，表明采用遺傳算法能夠快速求解出滿意的配流方案。在編組站實際工作中，列車預計的到達和出發時間與實際的到達、出發時間會有出入，需要通過人機對話動態調整，以保證系統運算結果的實用性。

[1] 王明慧，趙強.編組站智能調度系統階段計劃優化模型及算法研究[J].鐵道學報，2005，27（6）：1-9.

[2] 李文權.鐵路區段站日工作計劃優化模型及其算法的研究[D].成都：西南交通大學，1997.

[3] 王正彬.區段站階段計劃調整模型與算法研究[D].成都：西南交通大學，2007.

[4] 王慈光.運輸模型及優化[M].北京：中國鐵道出版社，2004.

[5] 薛鋒，羅建，陳崇雙.編組站配流中解編時刻參數的計算[J].交通運輸工程與信息學報，2010，8（4）：21-27.

[6] 牛惠民，胡安洲.雙向編組站車流接續的綜合優化[J].鐵道學報，1998，20（6）：16-21.

[7] 崔炳謀，馬鈞培，張樸.編組站進路調度優化算法[J].中國鐵道科學，2007，28（2）：100-103.

[8] 劉霆，何世偉，王保華，等.編組站調度計劃隨機機會約束規劃模型及算法研究[J].鐵道學報，2007，29（4）：12-17.

[9] 薛鋒，羅建.基于遺傳算法的動態MC2 運輸問題求解[J].計算機工程與應用，2008，44（28）：236-238.

[10] 薛鋒，王慈光，張展杰.編組站配流的協調優化算法[J].西南交通大學學報，2010，45（6）：932-937.

[11] 薛鋒，王慈光.編組站列車編組順序的調整方法[J].鐵道學報，2007，29（4）：1-5.