基于博弈思想的編組站階段計(jì)劃自動(dòng)調(diào)整系統(tǒng)研究

張 明

（中國(guó)鐵路南昌局集團(tuán)有限公司， 南昌 330002）

編組站作為鐵路貨物列車的“制造工廠”[1]，是鐵路樞紐及干線暢通的關(guān)鍵環(huán)節(jié)，它對(duì)加速全路車輛周轉(zhuǎn)、提高運(yùn)輸能力起著舉足輕重的作用，其作業(yè)效率和質(zhì)量直接影響著鐵路運(yùn)輸?shù)男屎托б鎇2-3]。隨著鐵路信息化建設(shè)的不斷推進(jìn)，我國(guó)鐵路編組站調(diào)度指揮完成了由手工作業(yè)到計(jì)算機(jī)輔助作業(yè)的過(guò)渡。目前在逐步向智能化調(diào)度作業(yè)發(fā)展。編組站階段計(jì)劃編制理論經(jīng)過(guò)幾十年的發(fā)展，已經(jīng)積累了豐富的理論基礎(chǔ)，但真正與實(shí)際現(xiàn)場(chǎng)結(jié)合卻有許多困難。早期國(guó)外相關(guān)研究對(duì)編組站調(diào)度計(jì)劃編制理論的研究較少，且注重從數(shù)學(xué)、運(yùn)籌學(xué)的視角出發(fā)，如 Gulbodsen[4]、Grainic[5]等、Assad[6]和 Keaton[7-8]等人的研究。我國(guó)學(xué)者對(duì)階段計(jì)劃編制的優(yōu)化模型以及計(jì)算機(jī)實(shí)現(xiàn)等方面的研究已較為深入，如劉軍[9]、牛惠民[10]、何世偉[11]、王瑩[12]等的研究。本文在上述研究的基礎(chǔ)上，根據(jù)南昌鐵路局向塘西編組站的編組站綜合自動(dòng)化（SAM）系統(tǒng)的應(yīng)用情況，利用博弈思想，設(shè)計(jì)了一種協(xié)調(diào)優(yōu)化編組站調(diào)機(jī)運(yùn)用和配流問(wèn)題的模型，并用于階段計(jì)劃自動(dòng)編制和調(diào)整系統(tǒng)。

1 編組站階段計(jì)劃編制與調(diào)整

每個(gè)工作日開始前，鐵路局調(diào)度所會(huì)下發(fā)本日計(jì)劃任務(wù)給編組站。編組站通過(guò)制定和實(shí)施班計(jì)劃、階段計(jì)劃和調(diào)車作業(yè)計(jì)劃來(lái)保證日計(jì)劃的順利完成。為了完成班計(jì)劃任務(wù)，編組站調(diào)度員要利用編組站技術(shù)作業(yè)表，記錄編組站運(yùn)輸工作的實(shí)際完成情況，并以每3 h為一個(gè)階段，在表上安排下一階段的接發(fā)列車和調(diào)車工作，指揮全站的運(yùn)輸生產(chǎn)。

1.1 編組站階段計(jì)劃編制

編組站階段計(jì)劃的編制方法如圖1所示。其中，基礎(chǔ)資料收集內(nèi)容包括班計(jì)劃規(guī)定的各項(xiàng)任務(wù)、時(shí)間要求和本階段重點(diǎn)工作；各到達(dá)列車的到達(dá)時(shí)刻及編組內(nèi)容（實(shí)績(jī)）；各車場(chǎng)現(xiàn)車情況；調(diào)機(jī)作業(yè)進(jìn)度（實(shí)績(jī)）；機(jī)車整備、扣修、站內(nèi)施工等資料。而后根據(jù)場(chǎng)內(nèi)存車和解編車流推算下一階段的車流。跟據(jù)推算車流和基礎(chǔ)資料內(nèi)容鋪畫到、發(fā)列車運(yùn)行線，填寫到達(dá)列車編組內(nèi)容，確定到達(dá)列車的解體順序，確定出發(fā)列車的編組時(shí)機(jī)，確定取送內(nèi)容和時(shí)機(jī)。并編制到發(fā)線運(yùn)用計(jì)劃和調(diào)機(jī)運(yùn)用計(jì)劃。

圖1 階段計(jì)劃編制方法

1.2 編組站階段計(jì)劃調(diào)整規(guī)則

編組站的作業(yè)和車流隨著時(shí)間不斷變化，階段計(jì)劃的調(diào)整必須具有實(shí)時(shí)性和有效性。所以本文采用循環(huán)調(diào)整和分層規(guī)劃調(diào)整兩個(gè)調(diào)整規(guī)則，對(duì)階段計(jì)劃進(jìn)行調(diào)整。

1.2.1 循環(huán)調(diào)整規(guī)則

編組站階段計(jì)劃根據(jù)現(xiàn)有作業(yè)進(jìn)度等基礎(chǔ)數(shù)據(jù)在設(shè)定的計(jì)算時(shí)域進(jìn)行滾動(dòng)迭代。可以隨機(jī)制定開始調(diào)整的時(shí)間點(diǎn)和迭代時(shí)域。階段計(jì)劃循環(huán)調(diào)整依據(jù)上一階段的階段計(jì)劃，根據(jù)實(shí)際作業(yè)情況和作業(yè)進(jìn)度進(jìn)行滾動(dòng)調(diào)整。不斷地根據(jù)現(xiàn)有基礎(chǔ)數(shù)據(jù)更新約束條件，并將新的約束條件帶入到后續(xù)調(diào)整計(jì)算中去。如此調(diào)整的階段計(jì)劃更能符合現(xiàn)場(chǎng)實(shí)際作業(yè)情況，提高階段計(jì)劃的兌現(xiàn)率和編組站的工作效率，滿足實(shí)時(shí)性的調(diào)整原則。

1.2.2 分層規(guī)劃調(diào)整規(guī)則

編組站有大量的調(diào)車作業(yè)，作業(yè)復(fù)雜。各項(xiàng)作業(yè)之間需要相互配合協(xié)調(diào)，很難建立統(tǒng)一的、整體的優(yōu)化模型。因此需要建立分層規(guī)劃調(diào)整模型。本文利用分層規(guī)劃，將階段計(jì)劃調(diào)整問(wèn)題分為車流分配和調(diào)機(jī)運(yùn)用協(xié)同調(diào)整、到發(fā)線應(yīng)用優(yōu)化兩個(gè)問(wèn)題。既保證了調(diào)整決策的整體優(yōu)化，又大大降低了問(wèn)題的復(fù)雜程度。其中到發(fā)線應(yīng)用優(yōu)化問(wèn)題的相關(guān)研究已經(jīng)比較成熟，本文重點(diǎn)研究車流分配和調(diào)機(jī)運(yùn)用協(xié)同調(diào)整問(wèn)題。該規(guī)則滿足有效性的調(diào)整原則。

2 基于博弈思想的調(diào)機(jī)運(yùn)用與配流協(xié)同優(yōu)化

2.1 演化博弈理論

與古典博弈理論不同，演化博弈理論的基本假設(shè)是參與人的理性度是有限的。在這一問(wèn)題中，參與人的各項(xiàng)決策均處于連續(xù)的動(dòng)態(tài)變化過(guò)程中，為了實(shí)現(xiàn)最終的均衡目標(biāo)，必須歷經(jīng)一個(gè)復(fù)雜的演化發(fā)展過(guò)程。這里存在一種可能性，即這一問(wèn)題永遠(yuǎn)無(wú)法實(shí)現(xiàn)最終的均衡目標(biāo)，而是始終處于無(wú)限接近均衡的狀態(tài)。如果問(wèn)題存在多種均衡模式，那么最終處于哪一種均衡模式就取決于演化博弈的初始條件以及演化的具體過(guò)程和動(dòng)態(tài)更新路徑。演化博弈理論在問(wèn)題分析中更加適用于實(shí)際情況，更加具有靈活性和實(shí)用性。

2.2 模型假設(shè)

為適應(yīng)南昌鐵路局向塘西編組站調(diào)車作業(yè)和站場(chǎng)結(jié)構(gòu)復(fù)雜的情況。根據(jù)演化博弈理論思想，將車流的集結(jié)過(guò)程和出發(fā)計(jì)劃類比為生產(chǎn)車間的一個(gè)加工任務(wù)。為了保證先交貨的加工任務(wù)無(wú)間斷加工（車流集結(jié)為無(wú)間斷連續(xù)集結(jié)），加工完成后進(jìn)行第2個(gè)加工任務(wù)的加工（集結(jié)完畢后進(jìn)行后續(xù)出發(fā)列車的車流集結(jié)）。因此，一般先確定車流的編組順序，然后根據(jù)編組順序確定最優(yōu)解體順序?？梢詫砍鼍€和擔(dān)當(dāng)編組任務(wù)的調(diào)車機(jī)看作生產(chǎn)線上第1個(gè)加工機(jī)器，將駝峰和擔(dān)當(dāng)推峰解體任務(wù)的調(diào)車機(jī)看作生產(chǎn)線上第2個(gè)加工機(jī)器，將編組列車的編組完成時(shí)刻看作加工任務(wù)的模糊交貨期。因此，編組站解編順序調(diào)整問(wèn)題可進(jìn)行簡(jiǎn)化，并類比為一個(gè)帶模糊交貨期的無(wú)等待流水車間調(diào)度問(wèn)題 ，其甘特圖如圖2所示。

此問(wèn)題的目標(biāo)為：在滿足每個(gè)客戶的最小滿意度閾值的條件下，使得所有客戶滿意度的加權(quán)和最大。

2.3 模型建立

本文建立的博弈模型包括多個(gè)有博弈關(guān)系的局中人（車流的集結(jié)過(guò)程和出發(fā)計(jì)劃）、每個(gè)局中人的策略集合（解體和編組方案中各列車的解編順序）、每個(gè)局中人采取各自策略后得到的收益函數(shù)（編組列車的編組完成時(shí)刻）。

圖2 無(wú)等待流水車間調(diào)度問(wèn)題甘特圖

依照演化博弈理論的思想，每個(gè)車流的集結(jié)過(guò)程和出發(fā)計(jì)劃都想通過(guò)競(jìng)爭(zhēng)最佳解編順序來(lái)獲得該車流最早的編組完成時(shí)刻，若某車流的集結(jié)過(guò)程和出發(fā)計(jì)劃的編組完成時(shí)刻不能達(dá)到期望值，該車流的集結(jié)過(guò)程和出發(fā)計(jì)劃就會(huì)尋求更好的解編順序位置。

2.3.1 參變量定義

R：足夠大正數(shù)；

AR={ar1, ar2, …, arm}：數(shù)量為m的本階段內(nèi)到達(dá)解體列車的集合（包含已經(jīng)集結(jié)在編組場(chǎng)內(nèi)的現(xiàn)車）；

SE={se1, se2,…, sej,…, sen}：數(shù)量為n的本階段內(nèi)編組出發(fā)列車的集合（不包含已整編的待發(fā)列車）；

GO={1, 2,…, B} ：編組去向集合；

Tj

編組：編組開始時(shí)刻；

t解體：待解列車在站進(jìn)行解體作業(yè)的標(biāo)準(zhǔn)時(shí)間；

arib：到達(dá)列車ari中擁有到達(dá)編組站的編組去向號(hào)b(1≤b≤B)的車輛數(shù)；

sejb：待發(fā)列車sej中擁有出發(fā)編組站的編組去向號(hào)b(1≤b≤B)的車輛數(shù)；

seijb：從 ari(i=1, 2,…, m)中配入 sej(j=1, 2,…, n)中的去向號(hào)為b(1≤b≤B)的車輛數(shù)；

nj： sej滿軸車輛數(shù) ；

Pj：配流方案；

ωij：0-1變量，若sej能夠接續(xù)ari，則ωij取1，否則取0；

σj：0-1變量，若 Pj≥ 0，σj取 1，否則取 0；

AM={1, 2,…, m}：調(diào)機(jī)集合；

ari(i=1, 2,…, m)：到達(dá)解體列車；

Ti到達(dá)：到達(dá)時(shí)刻；

t到達(dá)：到達(dá)列車在站內(nèi)進(jìn)行技檢作業(yè)的時(shí)間標(biāo)準(zhǔn)；

t解體：待解列車進(jìn)行解體作業(yè)的時(shí)間標(biāo)準(zhǔn)；

Xa：調(diào)機(jī)a固定作業(yè)的總數(shù)量；

αia：0-1變量，若調(diào)機(jī)a(1≤a≤A)負(fù)責(zé)進(jìn)行到達(dá)列車ari(i=1, 2,…, m)的解體作業(yè)，αia取1，否則取0；

βja：0-1變量，若調(diào)機(jī)a(1≤a≤A)負(fù)責(zé)進(jìn)行出發(fā)列車 sej(j=1, 2,…, n)的編組作業(yè)，βja取1，否則取 0；

Tj出發(fā)：出發(fā)列車sej(j=1, 2,…, n)的出發(fā)時(shí)刻；t編組：編組列車的技術(shù)作業(yè)時(shí)間標(biāo)準(zhǔn)；t出發(fā)：出發(fā)列車的技術(shù)作業(yè)時(shí)間標(biāo)準(zhǔn)。

2.3.2 配流約束

同去向配流約束：

基本去向組車輛數(shù)約束：

車流的接續(xù)時(shí)間約束：

列車編成車輛數(shù)約束：

2.3.3 解體約束

列車解體占用調(diào)機(jī)的時(shí)域約束：

到達(dá)列車解體作業(yè)可行性約束：

解體調(diào)機(jī)作業(yè)的時(shí)域約束：

雙推單溜約束：

作業(yè)交叉約束：

2.3.4 編組約束

編組調(diào)機(jī)約束（同一出發(fā)列車只可使用一臺(tái)編組調(diào)機(jī)）：

出發(fā)列車正點(diǎn)發(fā)車約束（開始編組時(shí)刻須早于滿足出發(fā)列車技術(shù)作業(yè)時(shí)間要求的最晚開始編組時(shí)刻）：

調(diào)機(jī)作業(yè)時(shí)域約束（不同出發(fā)列車不可同時(shí)使用同一臺(tái)調(diào)機(jī)進(jìn)行編組作業(yè)）：

牽出線時(shí)域約束（不同調(diào)機(jī)進(jìn)行編組作業(yè)時(shí)不可同時(shí)占用同一牽出線）：

作業(yè)交叉約束（編組作業(yè)不可與調(diào)機(jī)的固定作業(yè)相互沖突）：

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

以出發(fā)列車的正點(diǎn)滿軸出發(fā)列車數(shù)最多，定義目標(biāo)函數(shù)為：

相關(guān)參數(shù)區(qū)間如下：

3 編組站階段計(jì)劃自動(dòng)調(diào)整系統(tǒng)設(shè)計(jì)

本文利用UML對(duì)編組站階段計(jì)劃自動(dòng)調(diào)整系統(tǒng)進(jìn)行設(shè)計(jì)。

3.1 系統(tǒng)功能設(shè)計(jì)

編組站階段計(jì)劃自動(dòng)調(diào)整系統(tǒng)的功能模塊有：數(shù)據(jù)自動(dòng)分類匯總模塊、階段計(jì)劃自動(dòng)調(diào)整及人工干預(yù)功能模塊、圖表及調(diào)整結(jié)果顯示模塊、日志及文檔管理模塊、用戶管理模塊。其中階段計(jì)劃自動(dòng)調(diào)整及人工干預(yù)模塊利用數(shù)據(jù)自動(dòng)分類匯總模塊提供的基礎(chǔ)信息，根據(jù)本文第2節(jié)中建立的優(yōu)化模型對(duì)調(diào)機(jī)運(yùn)用和配流進(jìn)行優(yōu)化，并通過(guò)圖表及調(diào)整結(jié)果顯示模塊進(jìn)行輸出。

圖3 系統(tǒng)功能結(jié)構(gòu)圖

系統(tǒng)功能結(jié)構(gòu)如圖3所示。

3.2 系統(tǒng)動(dòng)態(tài)模型設(shè)計(jì)

系統(tǒng)動(dòng)態(tài)模型設(shè)計(jì)主要包括調(diào)機(jī)運(yùn)用與配流協(xié)同調(diào)整模塊設(shè)計(jì)、數(shù)據(jù)管理模塊設(shè)計(jì)、網(wǎng)絡(luò)消息處理模塊設(shè)計(jì)和規(guī)則檢查模塊設(shè)計(jì)4個(gè)部分，詳細(xì)模型如圖4所示。當(dāng)需要對(duì)階段計(jì)劃進(jìn)行調(diào)整時(shí)，調(diào)機(jī)運(yùn)用與配流協(xié)同調(diào)整模塊首先從數(shù)據(jù)管理模塊獲取當(dāng)前可用資源，包括調(diào)機(jī)狀態(tài)、到發(fā)線狀態(tài)、現(xiàn)車信息、駝峰狀態(tài)、牽出線狀態(tài)等。而后通過(guò)套用調(diào)機(jī)運(yùn)用與配流協(xié)同調(diào)整模型，根據(jù)規(guī)則檢查模塊提供的規(guī)則約束，計(jì)算出調(diào)整后的階段計(jì)劃。網(wǎng)絡(luò)消息處理模塊主要負(fù)責(zé)模塊間的消息通信。

4 軟件仿真實(shí)現(xiàn)

根據(jù)南昌鐵路局向塘西編組站SAM系統(tǒng)應(yīng)用情況，選擇將向塘西站現(xiàn)場(chǎng)數(shù)據(jù)導(dǎo)入SAM系統(tǒng)仿真環(huán)境，并布置系統(tǒng)，對(duì)向塘西站進(jìn)行1：1仿真模擬。階段計(jì)劃自動(dòng)調(diào)整效果如圖5所示。在點(diǎn)擊調(diào)整計(jì)劃后，系統(tǒng)自動(dòng)生成了兩臺(tái)推峰調(diào)機(jī)的推峰計(jì)劃，并且根據(jù)作業(yè)先后順序排序。如按照調(diào)整后的作業(yè)計(jì)劃，能夠最高效率的滿足始發(fā)車流的集結(jié)和出發(fā)。點(diǎn)擊應(yīng)用調(diào)整方案后，該計(jì)劃會(huì)下達(dá)至值班員的操作終端。由值班員具體安排作業(yè)。

5 結(jié)束語(yǔ)

階段計(jì)劃自動(dòng)編制的研究成果很多，但在結(jié)合現(xiàn)場(chǎng)實(shí)際使用時(shí)卻困難重重。本文利用博弈思想對(duì)編組站階段計(jì)劃自動(dòng)編制和調(diào)整進(jìn)行數(shù)學(xué)建模和系統(tǒng)建模，在南昌鐵路局向塘西編組站SAM系統(tǒng)仿真環(huán)境的支撐下驗(yàn)證了系統(tǒng)的正確性和有效性，具有一定的理論和技術(shù)意義。下一步的研究目標(biāo)是充分結(jié)合現(xiàn)場(chǎng)作業(yè)，研究局、站一體化情況下的階段計(jì)劃自動(dòng)編制和調(diào)整問(wèn)題。

圖4 系統(tǒng)動(dòng)態(tài)模型圖

圖5 階段計(jì)劃調(diào)整自動(dòng)調(diào)整界面