基于博弈思想的編組站階段計劃自動調整系統研究

張 明

（中國鐵路南昌局集團有限公司， 南昌 330002）

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

1 編組站階段計劃編制與調整

每個工作日開始前，鐵路局調度所會下發本日計劃任務給編組站。編組站通過制定和實施班計劃、階段計劃和調車作業計劃來保證日計劃的順利完成。為了完成班計劃任務，編組站調度員要利用編組站技術作業表，記錄編組站運輸工作的實際完成情況，并以每3 h為一個階段，在表上安排下一階段的接發列車和調車工作，指揮全站的運輸生產。

1.1 編組站階段計劃編制

編組站階段計劃的編制方法如圖1所示。其中，基礎資料收集內容包括班計劃規定的各項任務、時間要求和本階段重點工作；各到達列車的到達時刻及編組內容（實績）；各車場現車情況；調機作業進度（實績）；機車整備、扣修、站內施工等資料。而后根據場內存車和解編車流推算下一階段的車流。跟據推算車流和基礎資料內容鋪畫到、發列車運行線，填寫到達列車編組內容，確定到達列車的解體順序，確定出發列車的編組時機，確定取送內容和時機。并編制到發線運用計劃和調機運用計劃。

圖1 階段計劃編制方法

1.2 編組站階段計劃調整規則

編組站的作業和車流隨著時間不斷變化，階段計劃的調整必須具有實時性和有效性。所以本文采用循環調整和分層規劃調整兩個調整規則，對階段計劃進行調整。

1.2.1 循環調整規則

編組站階段計劃根據現有作業進度等基礎數據在設定的計算時域進行滾動迭代。可以隨機制定開始調整的時間點和迭代時域。階段計劃循環調整依據上一階段的階段計劃，根據實際作業情況和作業進度進行滾動調整。不斷地根據現有基礎數據更新約束條件，并將新的約束條件帶入到后續調整計算中去。如此調整的階段計劃更能符合現場實際作業情況，提高階段計劃的兌現率和編組站的工作效率，滿足實時性的調整原則。

1.2.2 分層規劃調整規則

編組站有大量的調車作業，作業復雜。各項作業之間需要相互配合協調，很難建立統一的、整體的優化模型。因此需要建立分層規劃調整模型。本文利用分層規劃，將階段計劃調整問題分為車流分配和調機運用協同調整、到發線應用優化兩個問題。既保證了調整決策的整體優化，又大大降低了問題的復雜程度。其中到發線應用優化問題的相關研究已經比較成熟，本文重點研究車流分配和調機運用協同調整問題。該規則滿足有效性的調整原則。

2 基于博弈思想的調機運用與配流協同優化

2.1 演化博弈理論

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

2.2 模型假設

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

此問題的目標為：在滿足每個客戶的最小滿意度閾值的條件下，使得所有客戶滿意度的加權和最大。

2.3 模型建立

本文建立的博弈模型包括多個有博弈關系的局中人（車流的集結過程和出發計劃）、每個局中人的策略集合（解體和編組方案中各列車的解編順序）、每個局中人采取各自策略后得到的收益函數（編組列車的編組完成時刻）。

圖2 無等待流水車間調度問題甘特圖

依照演化博弈理論的思想，每個車流的集結過程和出發計劃都想通過競爭最佳解編順序來獲得該車流最早的編組完成時刻，若某車流的集結過程和出發計劃的編組完成時刻不能達到期望值，該車流的集結過程和出發計劃就會尋求更好的解編順序位置。

2.3.1 參變量定義

R：足夠大正數；

AR={ar1, ar2, …, arm}：數量為m的本階段內到達解體列車的集合（包含已經集結在編組場內的現車）；

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

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

Tj

編組：編組開始時刻；

t解體：待解列車在站進行解體作業的標準時間；

arib：到達列車ari中擁有到達編組站的編組去向號b(1≤b≤B)的車輛數；

sejb：待發列車sej中擁有出發編組站的編組去向號b(1≤b≤B)的車輛數；

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

nj： sej滿軸車輛數 ；

Pj：配流方案；

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

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

AM={1, 2,…, m}：調機集合；

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

Ti到達：到達時刻；

t到達：到達列車在站內進行技檢作業的時間標準；

t解體：待解列車進行解體作業的時間標準；

Xa：調機a固定作業的總數量；

αia：0-1變量，若調機a(1≤a≤A)負責進行到達列車ari(i=1, 2,…, m)的解體作業，αia取1，否則取0；

βja：0-1變量，若調機a(1≤a≤A)負責進行出發列車 sej(j=1, 2,…, n)的編組作業，βja取1，否則取 0；

Tj出發：出發列車sej(j=1, 2,…, n)的出發時刻；t編組：編組列車的技術作業時間標準；t出發：出發列車的技術作業時間標準。

2.3.2 配流約束

同去向配流約束：

基本去向組車輛數約束：

車流的接續時間約束：

列車編成車輛數約束：

2.3.3 解體約束

列車解體占用調機的時域約束：

到達列車解體作業可行性約束：

解體調機作業的時域約束：

雙推單溜約束：

作業交叉約束：

2.3.4 編組約束

編組調機約束（同一出發列車只可使用一臺編組調機）：

出發列車正點發車約束（開始編組時刻須早于滿足出發列車技術作業時間要求的最晚開始編組時刻）：

調機作業時域約束（不同出發列車不可同時使用同一臺調機進行編組作業）：

牽出線時域約束（不同調機進行編組作業時不可同時占用同一牽出線）：

作業交叉約束（編組作業不可與調機的固定作業相互沖突）：

2.3.5 目標函數

以出發列車的正點滿軸出發列車數最多，定義目標函數為：

相關參數區間如下：

3 編組站階段計劃自動調整系統設計

本文利用UML對編組站階段計劃自動調整系統進行設計。

3.1 系統功能設計

編組站階段計劃自動調整系統的功能模塊有：數據自動分類匯總模塊、階段計劃自動調整及人工干預功能模塊、圖表及調整結果顯示模塊、日志及文檔管理模塊、用戶管理模塊。其中階段計劃自動調整及人工干預模塊利用數據自動分類匯總模塊提供的基礎信息，根據本文第2節中建立的優化模型對調機運用和配流進行優化，并通過圖表及調整結果顯示模塊進行輸出。

圖3 系統功能結構圖

系統功能結構如圖3所示。

3.2 系統動態模型設計

系統動態模型設計主要包括調機運用與配流協同調整模塊設計、數據管理模塊設計、網絡消息處理模塊設計和規則檢查模塊設計4個部分，詳細模型如圖4所示。當需要對階段計劃進行調整時，調機運用與配流協同調整模塊首先從數據管理模塊獲取當前可用資源，包括調機狀態、到發線狀態、現車信息、駝峰狀態、牽出線狀態等。而后通過套用調機運用與配流協同調整模型，根據規則檢查模塊提供的規則約束，計算出調整后的階段計劃。網絡消息處理模塊主要負責模塊間的消息通信。

4 軟件仿真實現

根據南昌鐵路局向塘西編組站SAM系統應用情況，選擇將向塘西站現場數據導入SAM系統仿真環境，并布置系統，對向塘西站進行1：1仿真模擬。階段計劃自動調整效果如圖5所示。在點擊調整計劃后，系統自動生成了兩臺推峰調機的推峰計劃，并且根據作業先后順序排序。如按照調整后的作業計劃，能夠最高效率的滿足始發車流的集結和出發。點擊應用調整方案后，該計劃會下達至值班員的操作終端。由值班員具體安排作業。

5 結束語

階段計劃自動編制的研究成果很多，但在結合現場實際使用時卻困難重重。本文利用博弈思想對編組站階段計劃自動編制和調整進行數學建模和系統建模，在南昌鐵路局向塘西編組站SAM系統仿真環境的支撐下驗證了系統的正確性和有效性，具有一定的理論和技術意義。下一步的研究目標是充分結合現場作業，研究局、站一體化情況下的階段計劃自動編制和調整問題。

圖4 系統動態模型圖

圖5 階段計劃調整自動調整界面