動車段(所)集中控制系統作業進路方案沖突檢測的方法

曹桂均，閆　石

(中國鐵道科學研究院 通信信號研究所，北京　100081)

動車段(所)站場規模龐大，存在多個存車場及檢查檢修庫，有近百條存車及作業股道，用于完成動車組的入段，車輪踏面診斷，車輛外皮洗刷、卸污、整備和檢查檢修，動車組轉場、轉線、入出庫和出段等作業。動車段(所)實行集中調度指揮和一體化作業的生產管理，要求調度指揮各作業崗位高度協同、緊密銜接，以達到高效運轉、充分發揮各種設施設備能力的目標。

另外，為滿足運輸生產和各項作業的需求，動車段(所)需要在不同場區和不同作業線間頻繁調車，因此存在調度指揮過程復雜，需要辦理的作業進路量很大等問題。為此開發并使用了動車段(所)集中控制系統，從而實現了動車段(所)內作業進路的自動控制、作業計劃動態管理、現存動車組追蹤管理、人機界面統一管理等，提高了作業效率和安全可靠度，減輕了作業人員的勞動強度[1-2]。

為了提高接發車和調車效率，充分利用咽喉區進行作業，動車段(所)集中控制系統執行接發車和調車作業計劃時需要在時間和空間上進行合理安排。當存在多個作業計劃同時進行時，需要提前考慮各作業計劃的進路之間是否在空間上有沖突，從而選擇合理的進路方案以避免沖突。為此，本文針對動車段(所)集中控制系統作業進路沖突檢測方法開展研究。

1　作業計劃執行與作業進路方案生成

1.1　作業計劃的自動執行過程

動車段(所)集中控制系統自動接收鐵路局調度所下達的階段計劃和調度命令，自動采集站場設備的狀態信息和動車組運行情況，作為制定段(所)作業計劃的依據；根據段(所)作業計劃并綜合考慮動車組走行距離最短、最大限度地平行作業、合理利用股道及牽出線、避免進路沖突等要求，自動生成相應的作業進路方案及進路指令集；按照作業計劃的執行順序，自動分析和判斷在時間和空間上發生沖突的作業進路，自動或人工對作業進路進行選優處理；采用事件與時間觸發相結合的方式，確定進路指令下達的時機，自動下達進路指令和辦理作業進路[3-4]。

1.2　作業進路方案的生成方法

系統根據作業計劃的內容確定作業計劃執行的優先級別，然后再根據作業計劃的時間順序和優先級別確定作業計劃的執行順序，預計觸發的時機。系統根據作業計劃的觸發時機、起始股道和目標股道，搜索作業進路數據表，得到1組進路方案，每個進路方案所經過的路徑不同。通常將其中包含基本進路或常用的變通進路方案作為默認進路方案，其他進路方案作為備選進路方案。

完成1個作業計劃可能有1條或多條作業進路可供選擇；而開放1條作業進路又可能包含1條或多條進路指令。作業計劃、進路方案和進路指令之間的關系如圖1所示。

圖1　作業計劃、進路方案和進路指令之間的關系

某作業計劃的第x個進路方案Rx可形式化描述為

Rx={U1,U2,U3,…}

(1)

式中：Uy為構成作業進路的第y個元素，每個元素包含站場設備的類型及編號2個要素。站場設備指信號機、道岔、股道等設備[5]。

圖2為某動車段的站場平面圖。假設在該動車段有3個同時作業的調車計劃，見表1。調車計劃A為某動車組從1場38道至2場13道，調車計劃B為某動車組從1場5道至2場1道， 調車計劃C為某動車組從1場13道至2場6道。

圖2　動車段站場平面圖

表1　調車計劃示例

分別由作業計劃A，B，C可生成對應的6，3，6個進路方案，對這些進路方案可按照式1進行描述，見表2。

表2　作業計劃的進路方案列表

續表

注：“:”前的符號表示站場設備類型，而“:”后的符號及數字組合表示站場設備的編號；S為信號機，R為道岔反位，N為道岔定位，W為無岔區段，T為股道。

表2中每個作業計劃的第1個進路方案為默認進路方案，其他進路方案為備選進路方案。當某作業計劃的默認進路方案與其他作業計劃的進路方案無沖突時，將自動執行該作業計劃的默認進路方案，而其他備選進路方案可供人工選擇時之用；但是，當該作業計劃的默認進路方案與其他作業計劃的進路方案有沖突時，則需要從該作業計劃的備選進路方案中選擇與其他作業計劃的進路方案無沖突的進路方案作為執行方案。因為每個進路方案涉及的站場設備較復雜，所以為實現作業進路沖突檢測的自動化，研究采用數學方法進行作業進路方案的沖突檢測。

2　矩陣乘法

矩陣是線性代數的主要內容之一，是解決眾多問題的有力工具[6]。由矩陣乘法的定義可知，當矩陣M1和M2的大小分別為m×n和n×p時， 則T=M1M2是一個大小為m×p的矩陣；其中m，n，p皆為正整數。

再定義M3是一個大小為p×q的矩陣，則由矩陣乘法的結合律性質可知，有(M1M2)M3=M1(M2M3)，且由(M1M2)M3或M1(M2M3)得到的新矩陣的大小為m×q。

矩陣乘法在數學中應用很廣，而在信息學中同樣有很廣的應用，如優化動態規劃、圖鄰接矩陣上的乘法以及折半遞歸等[7-10]。

3　作業進路方案的沖突檢測

為使計算不太過復雜，特作如下約定：只要一些作業計劃在執行在時間上有重疊，就認為這些作業計劃存在時間上的沖突； 對于這些存在時間上沖突的作業計劃，只要它們的進路方案均占用相同的站場設備，則認為這些作業計劃的進路方案還存在空間上的沖突。

本文采用遍歷方法和矩陣乘法對存在時間沖突的多個作業計劃的進路方案間是否存在空間上的沖突進行檢測。

為了便于對問題求解過程的描述，首先定義存在時間上沖突的3個作業計劃A，B和C，它們各自對應的進路方案集合分別為{A1,A2…Am}，{B1,B2…Bn}和{C1,C2,…,Cp}；m，n和p分別為作業計劃A，B和C的進路方案數。

3.1　2個作業計劃的進路方案之間空間沖突檢測

在2個作業計劃的進路方案之間進行空間沖突檢測，可以采用逐一遍歷的方法進行。比如逐一遍歷A作業計劃的m個進路方案與B作業計劃的n個進路方案之間是否存在占用相同的站場設備，其結果可用1個m×n階的沖突矩陣表示，即

MAB=(aik)m×n

(2)

式中：元素aik表示作業計劃A的第i個進路方案與作業計劃B的第k個進路方案之間是否有空間沖突的比較結果，若存在空間沖突則置其值為0，若無空間沖突則置其值為1。

按照此方法，結合表2，在作業計劃A的進路方案與作業計劃B的進路方案之間進行空間沖突檢測，可得到1個6×3的沖突矩陣MAB，即

同理，可以在作業計劃B的進路方案與作業計劃C的進路方案之間以及在作業計劃A的進路方案與作業計劃C的進路方案之間進行空間沖突檢測，分別得到1個3×6的沖突矩陣MBC和1個6×6的沖突矩陣MCA，即

矩陣中值為1的元素，其所對應作業計劃的2個進路方案之間無空間沖突，否則就是存在空間沖突。例如，矩陣MAB中的元素a11=1，表示作業計劃A的進路方案A1與作業計劃B的進路方案B1之間不存在空間沖突，也即這2個計劃的默認進路方案之間不存在空間的沖突，無須調整，可作為執行方案。矩陣MCA中的元素c11=0，則表示作業計劃C的默認進路方案C1與作業計劃A的默認進路方案A1之間存在空間沖突，即這2個計劃的默認進路方案之間存在空間沖突，加之這2個計劃也存在時間上的沖突，故默認進路方案C1與默認進路方案A1的組合不能作為執行方案；為了使得C與A這2個作業計劃能夠同時執行，應選擇MCA中元素值為1的元素所對應的進路方案，如c15=1，即作業計劃C的默認進路方案C1與作業計劃A的備選進路方案A5之間無空間上的沖突，故可以調整成將作業計劃A的備用進路方案A5與作業計劃C的默認進路方案C1組合，構成執行方案，從而達到排解進路沖突目的。

如果沖突矩陣為全1矩陣，即矩陣中所有元素的取值均為1時，表示分別從2個作業計劃對應的進路方案中各任意選出1個進路方案，這2個進路方案之間均不存在空間沖突，即這2個作業計劃的進路方案之間不會發生空間上的沖突。如果沖突矩陣為全0矩陣，即矩陣中所有元素的取值均為0，則表示分別從2個作業計劃對應的進路方案中各任意選出1個進路方案，這2個進路方案均存在空間沖突；在沖突矩陣為全0矩陣的情況下無法進行進路方案的優選。因此，只有在沖突矩陣中元素的取值有0也有1的情況下，才可以通過進路方案的優選排解2個作業計劃的進路方案在空間上的沖突。

3.2　3個及以上作業計劃的進路方案之間空間沖突檢測

3.2.1沖突檢測方法

對于3個存在時間上沖突的作業計劃A，B和C，同樣采用逐一遍歷的方法先分別得到作業計劃A與B的進路方案之間的空間沖突矩陣MAB=(aik)m×n， 作業計劃B與C的進路方案之間的空間沖突矩陣MBC=(bkj)n×p， 以及作業計劃C與A的進路方案之間的空間沖突矩陣MCA=(cji)p×m。然后采用矩陣乘法對這3個空間沖突矩陣進行乘法操作。以計算作業計劃A的結果矩陣為例，具體步驟如下。

步驟1：先將沖突矩陣MAB與MBC相乘，得到作業計劃A與C的進路方案之間的參考矩陣。

TAC=MABMBC=(tij)m×p

(3)

根據矩陣乘法的定義可知，元素tij為

(4)

如果aikbkj=1，則表示作業計劃B的進路方案Bk分別與作業計劃A的進路方案Ai和作業計劃C的進路方案Cj之間均不存在空間上的沖突；而作業計劃A的進路方案Ai和作業計劃C的進路方案Cj之間是否有空間沖突，取決于沖突矩陣MCA中元素cji的值。如果aikbkj=0，則表示進路方案Bk與Ai或Cj存在空間沖突，即進路方案Ai，Bk，Cj不能作為同時執行作業計劃A，B和C的無沖突進路方案組合。元素tij的值表示了進路方案Ai和Cj能夠與作業計劃B的進路方案組成無沖突進路方案組合的次數。

步驟2：根據矩陣乘法的結合律，用參考矩陣TAC與沖突矩陣MCA相乘，得到作業計劃A的結果矩陣。

MA=TACMCA=MABMBCMCA=(rii′)m×m

(5)

結果矩陣MA是一個階數等于作業計劃A的進路方案數m的方陣；該結果矩陣MA對角線上元素的值為

(6)

元素rii的值為進路方案Ai能夠與作業計劃B和C的進路方案組成無沖突進路方案組合的次數，也就是說結果矩陣對角線上的元素值表示了作業計劃A的進路方案Ai可與其他2個作業計劃的進路方案組成無沖突進路方案組合的次數。

同理，可以計算得到作業計劃B和C的結果矩陣。

3.2.2沖突檢測算例

結合表2，仍以A，B，C這3個需要同時間執行的作業計劃為例，進行作業進路的沖突檢測。

首先由式(2)和式(3)計算作業計劃A與C的作業進路之間的參考矩陣，即

TAC=MABMBC

然后由式(4)和式(5)計算作業計劃A的結果矩陣，即

MA=TACMCA

對作業計劃A的結果矩陣對角線上值不為0的元素進行分析可知，作業計劃A的進路方案A5和A6可分別與其他2個作業計劃的進路方案組成無沖突進路方案組合，能夠組成無沖突進路方案組合的次數均為2次。

同理，可計算得到作業計劃B的結果矩陣，即

MB=MBCMCAMAB=TBAMAB

對作業計劃B的結果矩陣對角線上值不為0的元素分析可知，進路方案B1可以有4次機會與作業計劃A和C的進路方案組成無沖突進路方案組合。

同樣能夠計算得到作業計劃C的結果矩陣，即

MC=MCAMABMBC=TCBMBC

分析作業計劃C的結果矩陣對角線上值不為0的元素可知，進路方案C1和C3可分別有2次機會與其他2個作業計劃的進路方案組成無沖突進路方案組合。

另外，如果在按式(6)進行計算的過程中有aikbkjcji=1，則表示作業計劃A，B，C各自對應的進路方案Ai，Bk，Cj之間均無沖突，這3個進路方案可以作為同時執行作業計劃A，B，C時的1個無沖突進路方案組合。

結合表2 并采用上述作業進路沖突檢測方法計算可知，a51b11c15=1，a51b13c35=1，a61b11c16=1，a61b13c36=1，由此得出A，B，C這3個作業計劃同時執行時的無沖突進路方案組合分別為A5B1C1，A5B1C3，A6B1C1和A6B1C3。

受咽喉區設備能力及作業計劃執行順序的限制，很少有超過3個作業計劃同時進行的情況。但當有多于3個作業計劃同時進行的時候，一般可通過調整這些作業計劃的執行時間及其作業進路方案，排解它們進路方案之間在空間上的沖突。

4　沖突檢測方法的實現

用C++語言設計矩陣類，進行矩陣的賦值、乘法、轉置、全0或全1矩陣的判斷等操作，并按照本文方法編寫了作業進路沖突檢測程序。矩陣類如圖3所示，矩陣類中的成員函數及其主要功能見表3。

圖3　矩陣類圖

5　結　語

動車段(所)是動車組的檢修基地，接發車作業和出入庫、轉線等調車作業一般都集中在某時間段進行，經常出現多個作業計劃的進路方案發生沖突的情況，本文提出采用遍歷法和矩陣乘法解決該問題。用遍歷方法生成沖突矩陣，可以反映2個作業計劃進路方案之間的沖突情況；通過沖突矩陣的乘法運算，可以排解3個及以上多個作業計劃進路方案間的沖突；用C++語言對本文方法進行編程，實現了對作業計劃進路方案之間沖突的自動檢測。本文方法在動車段(所)集中控制系統中得到了成功應用，提高了動車段(所)咽喉區的利用率以及作業效率，降低了作業人員的勞動強度。

表3　矩陣類中成員函數的說明

[1]曹桂均,張華.動車基地調度集中系統研究[J].中國鐵路，2012(4)：55-59.

(CAO Guijun, ZHANG Hua. Research on the CTC in EMU Base[J]. Chinese Railways, 2012(4)：55-59. in Chinese)

[2]中國鐵道科學研究院通信信號研究所. 動車基地調度集中系統技術方案[R]. 北京：中國鐵道科學研究院通信信號研究所，2009.

[3]曹桂均.編組站綜合自動化系統控制技術及其擴展應用的研究[D].北京：中國鐵道科學研究院，2013: 59-88.

(CAO Guijun. The Research of Control Technology of Synthetic Automation of Marshalling Yard and Extended Application [D]. Beijing:China Academy of Railway Sciences，2013：59-88. in Chinese)

[4]丁昆，李瑋，婁正良. CIPS按計劃自動辦理進路的原理[J]. 鐵道通信信號，2010，46(11): 15-18.

(DING Kun， LI Wei，LOU Zhengliang. Principle of CIPS Automatic Route Setting on Schedule [J]. Railway Signalling & Communication，2010，46 (11):15-18. in Chinese)

[5]林瑜筠. 鐵路信號基礎[M].北京：中國鐵道出版社，2006.

[6]同濟大學. 線性代數 [M]. 5版. 北京：高等教育出版社，2007.

[7]程美玉,于祿,李興華. 矩陣乘法在計算中引起的思考[J]. 林區教學，2014(2)：81-85.

(CHENG Meiyu, YU Lu, LI Xinghua. Thinking Caused in the Calculation of the Matrix Multiplication [J]. Teaching of Forestry Region，2014(2)：81-85. in Chinese)

[8]胡潔萍，楊樹林，田益民. 矩陣乘法巧算及其拓廣應用[J]. 北京印刷學院學報，2012，20(4)：60-62.

(HU Jieping，YANG Shulin，TIAN Yimin. Simple Calculation of Matrix Multiplication and Its Extended Application[J]. Journal of Beijing Institute of Graphic Communication，2012，20(4)：60-62. in Chinese)

[9]李長明. 矩陣乘法的來源和意義[J]. 貴州教育學院學報，2002，13(4)：13-15，42.

(LI Changming. Source and Meaning of Matrix Multiplication[J]. Journal of Guizhou Educational College，2002，13(4)：13-15，42. in Chinese)

[10]鄧明香. 淺議矩陣乘法的應用[J]. 大學教育，2015(2)：84-86.

(DENG Mingxiang. The Application of Matrix Multiplication[J]. University Education，2015(2)：84-86. in Chinese)