考慮計劃分配優先級與干擾條件的編組站階段計劃自動編制研究

何占元，許展瑛，姚宇峰，蔣繼磊

(1.國能朔黃鐵路發展有限責任公司 運輸部，河北 滄州 062350；2.中國鐵道科學研究院集團有限公司 通信信號研究所，北京 100081)

0 引言

編組站作為鐵路運輸網絡車流集散中心，是鐵路樞紐及干線暢通的關鍵節點，承擔了鐵路貨物運輸環節的多項關鍵工作，包括但不限于貨物列車接發車作業、解編作業、檢修作業及裝卸作業等。階段計劃自動編制與動態調整作為編組站綜合自動化系統的核心技術，計劃編制質量的好壞直接關系到貨物車輛中停時，從而直接影響鐵路運輸效率[1]。編組站階段計劃基本編制流程如圖1 所示?，F階段，編組站階段計劃編制仍然以人工編制為主，編制周期長、出錯率高，且調整不便。對此，如何高效編制編組站階段計劃為眾多學者所研究的課題。

圖1 編組站階段計劃基本編制流程Fig.1 Basic preparation process of stage plan of marshalling station

針對編組站階段計劃的動態調整，張巖[2]研究提出了包括時間預測、動態車流推算、計劃調整、計劃實施、實時信息采集反饋等步驟的階段計劃動態調整流程，并建立了基于作業過程用時精準預測的動態車流推算模型。宋宇[3]研究了我國編組站運輸調度工作存在的問題，從硬件結構、軟件結構、系統功能和系統流程4 個方面為切入點設計了編組站運輸調度自動化系統。馬亮等[4]提出了階段計劃的自動調整算法并進行驗證。黎浩東等[5]分別對確定條件下和不確定條件下的階段計劃編制及階段計劃計算機編制與實現的研究現狀進行了綜述。楊穎[6]以編組站的實際工作為研究重點和核心，從編組站綜合能力的角度出發，以編組站能夠充分利用各設施設備的能力為目標進行了一系列的深入研究。趙軍鋒[7]基于新豐鎮編組站運輸組織現狀，研究分析制約車站運輸能力提升的客貨列車混跑、點線能力不協調、駝峰設備缺陷等主要因素，進而從線上擴能、點上擴能、管理擴能等方面提出運輸組織優化對策。趙蕾[8]研究了編組站資源的可用度計算方法，根據可用度的計算原理給出編組站資源可用度的計算方法及步驟，并進一步構建了編組站解編計劃耦合優化模型。劉俊[9]在分析了鐵路運輸調度高質量發展實踐成效和經驗啟示的基礎上，研究提出鐵路運輸調度指揮高質量發展優化策略。張明[10]借鑒博弈思想，對站內調機和分配車流進行協同優化，研究建立編組站調機運用與配流協同優化模型，驗證了編組站階段計劃自動編制、自動調整的系統方案。王琦[11]研究提出確定環境下的階段計劃優化模型，引入了延誤系數進行模型的補充完善，以列車平均待解時間最大和在站停留時間最短為目標進行了模型求解。

考慮編組站現場實際作業的隨機性、復雜性及突發性等特點，如遇到實際列車晚點、臨時調度命令下達等事件，會造成已編制好的計劃不能正常實施，人工調整較為耗時耗力。且現階段完全基于計算機進行階段計劃的全自動編制很難實現，仍考慮人機相結合的方式來實現。對此，基于階段計劃中到發線運用計劃的自動編制和計劃變動時到發線運用計劃的自動調整2 方面，以適度降低現階段人工編制計劃的工作量為切入點，建立一種編組站到發線運用計劃編制模型，并設計考慮股道優先級與股道干擾權重最小原則實現到發線運用計劃的自動編制。同時，編組站到發線運用計劃編制系統可實時跟蹤計劃的實際執行情況，當到發線實際占用情況與原計劃不一致時，系統可根據算法中的調整原則實現到發線運用計劃的自動調整。

1 自動編制

1.1 應用場景

針對實際現場應用場景利用計算機輔助技術研究編組站到發線運用計劃自動編制系統，根據車流狀況、調機剩余能力及到發線空閑能力，包括但不限于實現以下功能：①出發計劃后的到發線自動分配功能；②階段計劃中確認接車順序后自動分配到達計劃的到發線功能；③系統接收到實際作業情況同計劃不一致時自動調整相關到發線運用計劃的功能；④作業人員對到發線運用計劃進行人工干預時自動調整相關到發線運用計劃的功能；⑤系統接收施工計劃時對到發線進行自動占用標記等功能。上述功能的實現可有效提高到發線運用計劃的編制效率。

1.2 到發線分配原則

作為編組站階段計劃的核心工作之一，編組站到發線運用計劃的主要任務是在綜合考慮編組站場型布局、接發列車的數量、種類、解編技術作業的過程、時間等多種因素的基礎上，制定出階段計劃內所有到發列車占用到發場線路的具體計劃和具體時間段，實現合理運用到發線的目標，提升運輸生產效率。

在實際工作中，到發線運用的分配原則如下[12]。

（1）一條到發線同一時間段只能接發一列列車，直至列車離去。

（2）一列列車同一時間段內只能占用一條到發線。

（3）同一到發線接發相鄰到發列車的時間間隔要滿足最小安全時間間隔要求。

（4）到發線屬性必須滿足接發列車條件，如超長、超限列車等。

（5）指定到發線的計劃在作業時間段內不可更改到發線。

（6）到發線運用計劃編制應分類處理。除考慮到發線列車占用情況，還需要因考慮施工計劃、調機走行、減軸車輛等產生的占用情況，大體歸為2類：①可調整的到發線占用。包括到發列車、調機走行的到發線占用等；②不可調整的到發線占用。包括施工計劃、停放機車影響的到發線占用等。

1.3 計劃編制與調整

按照計劃應用場景，可將到發線自動編制系統功能具體劃分為計劃編制和計劃調整兩大功能。

（1）計劃編制功能。到發線運用計劃編制功能主要用于新增到達、出發列車計劃、施工計劃等，新增時存在多個計劃同時提交，計劃編制時分類按序編制。編制順序遵循先編制不可調整計劃，后編制可調整計劃，避免可調整計劃搶占不可調整計劃到發線資源，具體流程如下。①循環編制不可調整的到發線占用計劃。②循環編制可調整的到發線占用計劃。

（2）計劃調整功能。針對已編制完的計劃進行調整，分為自動調整和人工調整。自動調整主要考慮隨著計劃的執行，實際站場運用情況可能與計劃有所偏離，為保證后續計劃的可用性，需根據到發線實際占用情況進行動態調整。人工調整需考慮的是到發線占用計劃的規則檢查與受到影響后的后續計劃調整。具體流程如下。①接受到發線實際占用信息時，對比原到發線占用計劃，當到發線占用信息不一致時，將原到發線占用計劃更新為實際占用的到發線，到發線占用結束時間延用原計劃的占用結束時間，并篩選出移動后有沖突的到發線占用計劃重新進行編制。②到達/出發計劃實際占用股道出清時，應刪除當前到發線占用計劃。③人工對計劃調整時，若與不可調整到發線占用計劃沖突且禁止調整或存在其他異常情況，應篩選出有沖突的占用計劃重新進行編制。

2 模型設計

為有效利用編組站資源，將到發線運用計劃自動編制時所涉及的關聯資源進行統一定義，模型符號定義如表1所示。

表1 模型符號定義Tab.1 Model symbol definition

目標函數：若原計劃無法正常實施，對計劃進行調整時應盡量降低原股道運用計劃的波動性，即減少股道調整次數，即

股道占用約束如下。

（1）任務分配股道滿足超限規則，即當=e，滿足≤。

（2）股道占用唯一性：作業時間內有沖突的列車不應占用同一條股道，即?Te，Tf∈T，當則

（3）占用同一條股道的前后2 項任務，需滿足后項任務的股道占用開始時間與前項任務的股道占用結束時間之差不小于最小安全間隔時間，即當則

（4）依據股道干擾值、優先級加權最小值原則分配股道，對于任務Tj任意2條編號為p和q的待選股道，首先計算股道p的加權值，獲取任務優先級=k，則股道p的加權值Wp的計算公式為

式中：FI(p)為股道p的干擾值函數，計算公式為

式中：FC(i)為當前任務與已分配任務占用股道i的重疊時間；干擾因子Iip、優先級Pkp通過查表可得。同理，計算股道q的加權值。

根據結果評判，若WPWq，則=q。

（5）股道占用均衡性：以每條股道占用時間總和與各股道平均占用時間之差的標準差來表示，即

式中：Ej為股道占用均衡性系數，既有研究表明股道占用均衡系數越小，股道占用均衡性越好；反之越差。

3 算法分析

按照計劃的優先順序依次對計劃進行到發線占用分配。分配應遵循以下規則。①不可調整的到發線占用計劃優先級高于可調整的到發線占用計劃。②占用開始時間早的計劃優先級高于占用開始時間晚的計劃。③有限制條件的計劃優先級高于無限制條件的計劃。④沖突時優先度高的計劃可以搶占優先度低的計劃資源。⑤到發線占用沖突的計劃重新進入到發線分配流程進行再次編制。

（1）初始化。①初始化股道配置參數(是否超限、股道有效長等)。②初始化股道之間干擾值矩陣。③初始化股道優先級矩陣。

（2）循環處理待分配計劃。①按照優先規則對待分配計劃列表進行排序。②依序處理不可調整計劃，判斷是否有沖突，若無沖突可直接分配到發線；若存在沖突，沖突對象是不可調整到發線占用計劃時，標識本計劃為沖突計劃，如果沖突對象是可調整到發線占用計劃，將沖突對象占用解除并推入待處理占用計劃列表，為本計劃分配到發線，直至所有不可調整計劃分配完畢。③依序處理可調整計劃，查詢可分配且無沖突的到發線，依據優先級和干擾值加權平均最小原則分配到發線，如所有可分配到發線都有沖突，在所有沖突對象中查找占用開始時間大于本次分配計劃開始時間并且沖突干擾最小的到發線，然后解除找到的沖突對象的到發線占用并推入待處理占用計劃列表，為本計劃分配到發線，直至所有可調整計劃分配完畢。④輸出已分配計劃，同時標識沖突計劃，等待人工審核。

調整計劃分配方案如圖2所示。

圖2 調整計劃分配方案Fig.2 Adjustment of plan allocation scheme

（3）求解算法。鐵路編組站到發線運用優化問題屬于多約束條件組合優化問題，使用常規的算法很難在多項式時間內求出最優解，可考慮利用螢火蟲優化算法(Firefly Algorithm，FA)來解決。螢火蟲算法通過模擬螢火蟲個體之間的相互吸引從而達到尋優的目的。

螢火蟲算法主要包含亮度和吸引度2 個要素。亮度體現了螢火蟲所處位置的優劣并決定其移動方向，吸引度決定了螢火蟲移動的距離，通過亮度和吸引度的不斷更新，從而實現目標優化[13]。從數學角度對螢火蟲算法的主要參數進行以下描述。

①發光強度。如果求解的是最小值問題，則處于空間xi(xi，1，xi，2，…，xi，d)的螢火蟲的發光強度Ii的計算公式為

式中：f(xi)為當變量為xi時的目標函數值。

如果求解的是最大值問題，則處于空間xi(xi，1，xi，2，…，xi，d)的螢火蟲的發光強度Ii的計算公式為

②兩只螢火蟲之間的距離。第i只螢火蟲與第j只螢火蟲之間距離rij的計算公式為

式中：xi，k為第i只螢火蟲空間坐標xi的第k個分量；d為問題的維數。

③吸引力。螢火蟲的吸引力計算公式為

式中：r表示這只螢火蟲與另一只螢火蟲的距離；β0是常數，表示最大吸引力；γ為光吸收系數。

④螢火蟲位置的更新。如果第j只螢火蟲的光強度大于第i只螢火蟲的光強度，那么第i只螢火蟲就會被吸引，第i只螢火蟲的空間位置xi也會發生變化，xi的計算公式為

式中：α∈[0，1]為步長因子；rand是均勻分布在[0，1]之間的隨機數；xi，xj為螢火蟲i，j所處的空間位置。

算法步驟如下。

①初始化算法基本參數。設置螢火蟲數目n，最大吸引度β0，光強吸收系數γ，步長因子α，最大迭代次數M。

②隨機初始化螢火蟲的位置，計算螢火蟲的目標函數值作為各自最大熒光亮度I0。

③計算群體中螢火蟲的相對亮度I和吸引度β，根據相對亮度決定螢火蟲的移動方向。

④更新螢火蟲的空間位置，對處在最佳位置的螢火蟲進行隨機移動。

⑤根據更新后螢火蟲的位置，重新計算螢火蟲的亮度。

⑥當達到最大搜索次數，則轉下一步；否則，搜索次數增加1，轉第3步，進行下一次搜索。

⑦輸出全局極值點和最優個體值[14]。

螢火蟲算法流程圖如圖3所示。

圖3 螢火蟲算法流程Fig.3 Flow of firefly algorithm

4 應用效果

選取某編組站一個班次413列(到達218列，出發195 列)列車進行3 種方式(人工分配，不考慮股道間干擾的自動分配，考慮股道干擾及加權優選的自動分配)的到發線分配操作，基于螢火蟲優化算法，輔以計算機技術將其嵌入到現有的編組站系統中進行求解，對操作次數及操作時長進行比較，不同方式下的調整次數如表2 所示，不同方式下的調整用時如表3所示。

表2 不同方式下的調整次數次Tab.2 Statistics of adjustment times in different ways

表3 不同方式下的調整用時 minTab.3 Statistics of adjustment duration in different ways

由表3 可知，通過計算機輔助可大幅減少作業人員人工分配、調整計劃方案次數及編制到發線運用計劃的工作時長，且在考慮股道干擾和加權優選方案的情況下，需人工做計劃調整的數量有明顯下降，實驗結果表明，該模型其作業效率比常規未考慮股道優先級和股道干擾條件的自動編制方案作業效率提高近2倍，比人工編制方法效率提高近4倍。上述模型及算法已成功應用在某編組站的運輸調度自動化系統，實現到發線分配作業計劃系統自動編制。通過現場試驗驗證表明系統滿足了現場應用需求，可大幅降低場站作業人員勞動強度，提高作業效率，取得了良好的運用效果。

5 結束語

編組站到發線運用問題作為一種多約束條件組合優化問題[15]，目前缺乏固定的優化算法。對此，結合編組站實際布置情況及工作中面臨的具體問題，將影響到發線運用計劃分配優先級條件與干擾條件融入到發線占用資源分配優化模型中，基于螢火蟲優化算法，并輔以計算機技術將其嵌入到現有編組站系統中進行模型有效性驗證及測試，模型效果顯著?？紤]到編組站作業流程復雜，作業過程涉及的資源種類多，建設一個高效、智能的編組站除了需要軟件層面優秀模型及算法支撐外，還需要完善的硬件基礎設施，更需要多個系統間相互協調配合才能實現。因此，結合編組站運用實際需求，對階段計劃自動編制軟件不斷完善改進，才能夠不斷提升編組站作業效率和質量。