薛 鋒，陳崇雙，戶佐安

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

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

1 引言

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

2 參數(shù)定義

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

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

（2）T0時刻到達(dá)場內(nèi)待解列車車流。

（3）階段時間內(nèi)預(yù)計將要到達(dá)列車車流。

（4）交換場等待轉(zhuǎn)場分解的車組，每轉(zhuǎn)場一次視作1 列到達(dá)列車。

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

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

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

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

3 模型構(gòu)造

3.1 配流約束

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

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

3.2 解體約束

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

3.3 編組約束

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

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

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

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

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

4 模型的遺傳算法求解

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

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

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

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

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

4.2 算法思路

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

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

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

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

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

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

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

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

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

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

5 算例

5.1 時間標(biāo)準(zhǔn)及到發(fā)車流數(shù)據(jù)

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

表1 到達(dá)列車車流

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

5.2 算法結(jié)果分析

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

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

表3 最終配流方案

表4 解體調(diào)機(jī)安排

表5 編組調(diào)機(jī)安排

6 結(jié)論

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

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

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

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

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

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

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

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

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

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

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

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