薛 鋒，陳崇雙，戶佐安

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

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

1 引言

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

2 參數(shù)定義

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

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

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

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

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

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

設本階段到達解體列車數(shù)為n，到達解體列車（含調車場現(xiàn)車）集合按到達時間先后記作DD={dd0,dd1,…,ddi,…,ddn}；將要編組出發(fā)的列車（不包括已編完的待發(fā)列車）數(shù)為m，編組出發(fā)列車集合按出發(fā)時間先后記作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)的車數(shù)為ddik；對于出發(fā)列車cfj(j=1,2,…,m)，其出發(fā)時刻為；開始編組時刻為；已編組列車cfj中具有本站編組去向號k(1 ≤k≤K)的車數(shù)為cfjk。列車解體作業(yè)時間標準為tjt，編組作業(yè)時間標準為tbz，到達列車技術作業(yè)時間標準為tdd，出發(fā)列車技術作業(yè)時間標準為tcf；表示調機d的第s(1 ≤s≤Sd)項固定作業(yè)的開始時刻，其中Sd為調機d總的固定作業(yè)項數(shù)；表示調機d的第s項固定作業(yè)的作業(yè)時間；出發(fā)列車cfj的滿軸車數(shù)為mj，配流時的方案值為Fj。

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

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

3 模型構造

3.1 配流約束

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

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

3.2 解體約束

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

3.3 編組約束

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

3.4 目標函數(shù)

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

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

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

4 模型的遺傳算法求解

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

4.1 編碼及適應值函數(shù)

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

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

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

4.2 算法思路

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

步驟1初始化遺傳算法相關參數(shù)。

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

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

步驟4采用聯(lián)賽選擇規(guī)則對群體進行篩選，找出若干優(yōu)化解。

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

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

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

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

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

5 算例

5.1 時間標準及到發(fā)車流數(shù)據(jù)

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

表1 到達列車車流

表2 出發(fā)列車車流

5.2 算法結果分析

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

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

表3 最終配流方案

表4 解體調機安排

表5 編組調機安排

6 結論

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

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

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

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

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

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

[6] ?；菝?，胡安洲.雙向編組站車流接續(xù)的綜合優(yōu)化[J].鐵道學報，1998，20（6）：16-21.

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

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

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

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

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