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

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

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

0 引言

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

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

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

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

1 自動編制

1.1 應(yīng)用場景

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

1.2 到發(fā)線分配原則

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

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

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

（2）一列列車同一時間段內(nèi)只能占用一條到發(fā)線。

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

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

（5）指定到發(fā)線的計劃在作業(yè)時間段內(nèi)不可更改到發(fā)線。

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

1.3 計劃編制與調(diào)整

按照計劃應(yīng)用場景，可將到發(fā)線自動編制系統(tǒng)功能具體劃分為計劃編制和計劃調(diào)整兩大功能。

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

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

2 模型設(shè)計

為有效利用編組站資源，將到發(fā)線運用計劃自動編制時所涉及的關(guān)聯(lián)資源進行統(tǒng)一定義，模型符號定義如表1所示。

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

目標函數(shù)：若原計劃無法正常實施，對計劃進行調(diào)整時應(yīng)盡量降低原股道運用計劃的波動性，即減少股道調(diào)整次數(shù)，即

股道占用約束如下。

（1）任務(wù)分配股道滿足超限規(guī)則，即當=e，滿足≤。

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

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

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

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

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

根據(jù)結(jié)果評判，若WPWq，則=q。

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

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

3 算法分析

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

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

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

調(diào)整計劃分配方案如圖2所示。

圖2 調(diào)整計劃分配方案Fig.2 Adjustment of plan allocation scheme

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

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

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

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

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

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

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

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

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

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

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

算法步驟如下。

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

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

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

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

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

⑥當達到最大搜索次數(shù)，則轉(zhuǎn)下一步；否則，搜索次數(shù)增加1，轉(zhuǎn)第3步，進行下一次搜索。

⑦輸出全局極值點和最優(yōu)個體值[14]。

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

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

4 應(yīng)用效果

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

表2 不同方式下的調(diào)整次數(shù)次Tab.2 Statistics of adjustment times in different ways

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

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

5 結(jié)束語

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