姚宇峰

(中國鐵道科學研究院集團有限公司通信信號研究所，北京 100081)

0 引言

編組站作為保障鐵路安全有效運輸的關鍵基層單位，承擔了鐵路貨物運輸環(huán)節(jié)的多項核心工作，包括但不限于列車接車作業(yè)、貨物列車的解體和編組作業(yè)以及列車發(fā)車作業(yè)等。階段計劃作為整個車站工作計劃的重要組成部分，既是對日班計劃分階段的工作細分，也可以有效指導車站工作人員完成日常的排班工作，提高工作效率。由于編制計劃時考慮的相關因素較多，如何編制高效、高質量的編組站階段計劃一直都是眾多學者的研究課題。

國內專家學者針對階段計劃自動編制的理論進行了一系列的研究。楊穎[1]研究了編組站固定設施和不同方向車流對編組站能力的影響以及編組站內部設備的均衡性對編組站接發(fā)車能力的影響；黃俊生等[2]提出以使用均衡性、列車到達不確定性、技術作業(yè)時間彈性、帶重疊時間窗等為約束，帶柔性重疊時間窗編組站終到列車到發(fā)線應用的優(yōu)化模型；徐永梅等[3]分析了編組站綜合自動化系統(tǒng)大數據平臺的構建和典型應用；徐晶等[4]通過對影響鐵路客運站到發(fā)線因素的分析建立整數規(guī)劃模型，研究并提出求解該模型的啟發(fā)式排序規(guī)則和禁忌搜索算法相結合的優(yōu)化算法；康山松[5]對編組站到發(fā)線運用中的股道占用、咽喉占用資源沖突問題進行了研究，提出以行車設備的均衡利用和最小緩沖時間的長短為目標的數學模型；趙蕾[6]通過對編組站集群資源進行分析，提出對實體資源劃分多個節(jié)點，結合資源邊際效用情況引入了資源可用度的評價指標；易嬌等[7]探討了編組站階段計劃自動編制時存在的典型問題并分別針對到發(fā)線運用、調車機車運用和取送車運用進行了建模；高雪等[8]提出了基于啟發(fā)式算法對編組站到發(fā)線運用問題進行研究的思路；李濤等[9]研究建立客運站到發(fā)線運用優(yōu)化模型，采用模擬退火遺傳算法求解實現到發(fā)線設備固定使用、均衡使用及保證行車作業(yè)安全的優(yōu)化目標；李濤等[10]研究建立客運站到發(fā)線運用優(yōu)化模型，采用改進的遺傳算法求解實現列車占用到發(fā)線時間最小和到發(fā)線運用最均衡的優(yōu)化目標；何林等[11]建立高速鐵路車站到發(fā)線運用的0-1 規(guī)劃模型，采用遺傳算法求解實現上下行列車股道的均勻分配；孫波等[12]提出一種應用于機器人路徑規(guī)劃的遺傳算法優(yōu)化思路。

考慮到編組站現場實際作業(yè)的多樣性、復雜性、隨機性、突發(fā)性等特點，現階段很難單獨依靠計算機來進行階段計劃的全自動編制，仍舊需要人機結合來實現。為了盡可能彌補人工編制計劃的不足，更合理地使用站內的相關資源，研究提出一種編組站到發(fā)線運用計劃的優(yōu)化模型與算法，在綜合考慮編組站的實際作業(yè)情況、資源使用情況、資源沖突情況等多項約束條件下，利用啟發(fā)式算法尋求一個可行的優(yōu)化解，重點解決現階段到發(fā)線運用計劃中到達場股道資源分配特定場景下的資源優(yōu)化問題，從而使得特定資源如股道的使用分配更為合理。

1 到發(fā)線運用計劃

編組站到發(fā)線運用計劃作為編組站階段計劃的核心工作之一，其主要任務是在綜合考慮編組站的布局情況(參考車站布置圖)、計劃接發(fā)列車的數量、接發(fā)列車的性質、接發(fā)列車的密集度、站內車輛解編技術的作業(yè)過程、作業(yè)方式、作業(yè)時間等多種因素的基礎上，制定出階段計劃內所有到發(fā)列車占用到發(fā)場線路的具體計劃，規(guī)定所有到發(fā)列車占用到發(fā)線的具體時間段，并支持計劃的快速調整，最終保障車站能夠完成按計劃接車、列車準點發(fā)車和避免或盡量減少列車線路交叉等多個計劃任務，實現階段計劃內合理運用到發(fā)線的目標，提高編組站的運行效率。

到發(fā)線運用的基本分配原則如下。

（1）同一時間段內一列列車只允許占用一條到發(fā)線。

（2）同一時間段內一條到發(fā)線上只允許一列列車占用。

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

（4）到發(fā)線的使用應盡量符合車站的相關規(guī)定。

（5）到發(fā)線的運用計劃應提高抗干擾能力，在滿足到發(fā)線能力的前提下，應考慮最大化列車作業(yè)占用行車設備的緩沖時間。

（6）到發(fā)線的既有行車技術設備應盡量均衡地使用，對于確定的列車運行圖和車站既有行車設備的利用率應趨于均衡。

2 數學模型

為了利用編組站的有限資源來實現計劃的自動編制，評測效果的優(yōu)劣，需要把到發(fā)線運用計劃涉及的關聯(lián)資源統(tǒng)一定義成模型表示，并進一步基于模型規(guī)則來求解輸出編制好的計劃。模型符號定義如表1所示。

表1 符號定義Tab.1 Symbol definition

股道占用約束條件如下。

（1）一趟車次作業(yè)周期內只能占用一條股道，作業(yè)中途不能更換股道，即

（2）作業(yè)時間有沖突的2 趟車次不能占用同一條股道，即

（3）超限車次只能占用可容納超限車次的股道，不能占用常規(guī)股道，即

優(yōu)化目標為使得股道資源使用更均衡，各股道占用時間方差最小，即

該目標評價車次使用股道資源的均衡性，好的到發(fā)線運用計劃應該使得各股道的資源占用盡量保持均衡，而不是只集中占用某些股道。

3 算法設計

鐵路編組站到發(fā)線運用優(yōu)化問題屬于多約束條件組合優(yōu)化問題，隨著問題規(guī)模(如接發(fā)車輛、股道數量、限制約束條件)的增大，搜索空間可急劇增大，使用常規(guī)的算法很難求出最優(yōu)解，退一步求次優(yōu)解來部分解決現有的問題較為可行，在當前流行的啟發(fā)式優(yōu)化算法[8]中，遺傳算法(Genetic Algorithm，GA)[5]是其中的佼佼者。遺傳算法借鑒了自然界生物進化的選擇和遺傳機制，模仿生物的優(yōu)勝劣汰思路來進行多群體、多參數的優(yōu)化，較適用于用常規(guī)搜索算法難以解決的復雜非線性問題。鑒于問題領域的特定場景，研究采用改進的遺傳算法來進行問題求解。遺傳算法流程如圖1所示。

圖1 遺傳算法流程Fig.1 Flow chart of genetic algorithm

（1）編碼。研究采用自然數方式編碼基因，按照車次占用到發(fā)線股道的先后順序依次排列，則基因xj表示列車j占用的股道編號，編碼簡單，可讀性好便于對應解空間。個體P可表示為基因x的序列，如[x1，x2，x3，…，xn-1，xn]，典型的個體P編碼實例如[108，101，110，…，106，109]，其中j的取值范圍為1～n，表示車次的先后自然排序編號，xj的取值范圍為車場股道的編號。

（2）生成初始種群。隨機產生若干個體P，其中符合股道占用約束條件的予以保留，不符合的則進行淘汰，確保符合要求的個體數量滿足種群數量的參數要求即可。

（3）定義適應度函數。適應度函數f作為遺傳算法中個體優(yōu)劣的評判準則，通常同目標函數Z一致，用來保障適應度較高的個體有較大機率遺傳到下一代。若求解目標函數最大值時，則目標函數可直接作為適應度函數f=Z，若求解目標函數最小值時，則變換公式為f=M-Z，其中M為大的正整數。

（4）選擇操作。研究采用適應度最大值選取法，每一輪選擇操作中，計算種群內個體的適應度數值并按照大小排序，依次選擇前K個(選擇參數閾值)適應度較高的個體，而非采用傳統(tǒng)的輪盤賭選擇法。將選擇出來的父代個體直接作為子代個體予以保留，然后利用選擇的這些父代個體進行交叉及變異操作生成新的子代個體，最終保持種群規(guī)模數量不變。這樣可以較為快速地篩選出符合股道占用約束條件的解，淘汰掉不符合的無效解。

（5）交叉操作。研究采用均勻交叉基因點的方法，依次選取2條父染色體，然后隨機產生一個[0，1]區(qū)間的均勻分布序列，其長度與父染色體長度一致，根據隨機數的大小(交叉概率閾值)且交換后的相鄰基因符合股道占用約束條件來交換2 條父染色體對應位置的基因，從而生成2 條子染色體，而非簡單基于概率交叉。這樣可以盡力保障生成符合股道占用約束條件的有效解。

（6）變異操作。研究采用隨機變異基因點的方式選取染色體的變異位置(設定變異點個數、變異概率閾值)。為了提高解空間的搜索速度，達到快速局部收斂的目的，變異的值從可行解的待分配股道(符合股道占用規(guī)則，不會發(fā)生資源沖突)中隨機選取。

（7）停止準則。通過設置最大迭代次數，同時觀察適應度函數的變換曲線，綜合評判選取最優(yōu)解。

4 實例研究

研究選取某編組站某一天的典型運行數據來進行實例分析。該編組站的布局為雙向三級六場縱列式編組站，其中下行到達場車場的編號為一場，其中配備有14 條股道，編號分別為101—114，均可用來接發(fā)列車，其中101，106，107，108，111 號股道為超限股道，支持容納超限車次。

下行到達場某一天接車作業(yè)計劃如表2 所示(股道占用開始、結束時間已由車流推算系統(tǒng)計算得到)。其中，序號分別為69，71，75 的3 趟車次為超限車次，車次號分別為45908，41071，22165，目前分配的股道分別為106，101和107。

表2 下行到達場某一天接車作業(yè)計劃Tab.2 Schedule of pick-up operation on a certain day at the downward arrival site

續(xù)表

基于該站一天的接車作業(yè)計劃數據，計算當天車次股道占用時間沖突矩陣F如表3所示。

表3 車次股道占用時間沖突矩陣FTab.3 Track occupation time conflict matrix F

通過遺傳算法進行求解，種群規(guī)模設置為30，選擇參數K設為16，即每輪保留約一半染色體，交叉概率Pc設置為0.95，變異點個數為2，變異概率Pm取0.05，迭代次數100，目標優(yōu)化函數為Z(股道占用時間方差最小)，適應度函數為f=100-Z，且規(guī)定如果解空間不符合股道占用約束條件則適應度為0。適應度函數變化曲線如圖2 所示，目標優(yōu)化函數變化曲線如圖3所示。

圖2 適應度函數變化曲線Fig.2 Fitness function curve

圖3 目標優(yōu)化函數變化曲線Fig.3 Objective optimization function curve

由圖2、圖3 可知，種群個體在迭代了大約85 代時，適應度函數達到了平衡狀態(tài)。得到目前較優(yōu)的股道分配新方案[106，113，108，110，105，104，101，103，109，111，113，102，101，108，114，105，112，113，109，107，103，111，112，104，105，113，108，106，102，110，114，111，112，109，106，102，110，105，107，101，108，103，111，104，102，109，114，113，110，112，105，108，107，106，104，103，109，114，113，111，106，110，103，107，104，109，102，111，108，107，106，114，102，113，107，105，110，111，107，102，114，112，104，101，106，103]。其中超限車次45908，41071，22165 分配的新股道為108，106，107。

由圖2、圖3 可以看出，股道分配新方案較之原有的股道分配方案，股道占用時間方差較小，股道占用時間更均衡，新舊股道分配方案股道使用時間對比如圖4所示。

圖4 新舊股道分配方案股道使用時間對比Fig.4 Comparison of track utilization time between old and new track distribution schemes

此時得到的股道分配方案仍然可能是一個局部最優(yōu)解，這是由于遺傳算法本身的局限性導致的。但是，針對目前的編組站來說，此解具備可行性，可以在一定程度上解決現階段股道資源均衡使用的問題。通過在真實場景的驗證表明優(yōu)化設計經受住了實踐的考驗，取得了良好的應用效果。

5 結束語

編組站到發(fā)線運用屬于典型的NP-C 問題，目前缺乏單一的優(yōu)化算法。通過借鑒國內的最新研究成果，結合編組站的實際布置情況和工作中面臨的實際問題，采用計算機輔助手段對編組站到發(fā)線運用中的到發(fā)場股道分配問題進行研究和分析，提出一種自動優(yōu)化模型與算法，并在真實場景下進行了模型驗證和測試，效果明顯。由于編組作業(yè)的復雜性和應用場景的特殊性，建設一個高效的智能編組站難度很大，除了在算法和模型上不斷探索和改進，還需要硬件設施、人員、多方系統(tǒng)的相互配合。提高編組站作業(yè)的智能化水平絕不是依靠一個單一的系統(tǒng)就能解決的問題。以現實為依托，深入了解編組站日常作業(yè)的難點與痛點，合理地規(guī)劃計算機與人員的分工，不斷改進和完善到發(fā)線運用自動化系統(tǒng)，可以更為有效地提高和改善編組站作業(yè)效率和作業(yè)質量。