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

曹桂均，閆　石

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

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

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

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

1　作業(yè)計劃執(zhí)行與作業(yè)進路方案生成

1.1　作業(yè)計劃的自動執(zhí)行過程

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

1.2　作業(yè)進路方案的生成方法

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

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

圖1　作業(yè)計劃、進路方案和進路指令之間的關(guān)系

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

Rx={U1,U2,U3,…}

(1)

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

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

圖2　動車段站場平面圖

表1　調(diào)車計劃示例

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

表2　作業(yè)計劃的進路方案列表

續(xù)表

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

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

2　矩陣乘法

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

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

矩陣乘法在數(shù)學中應(yīng)用很廣，而在信息學中同樣有很廣的應(yīng)用，如優(yōu)化動態(tài)規(guī)劃、圖鄰接矩陣上的乘法以及折半遞歸等[7-10]。

3　作業(yè)進路方案的沖突檢測

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

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

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

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

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

MAB=(aik)m×n

(2)

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

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

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

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

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

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

3.2.1沖突檢測方法

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

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

TAC=MABMBC=(tij)m×p

(3)

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

(4)

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

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

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

(5)

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

(6)

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

同理，可以計算得到作業(yè)計劃B和C的結(jié)果矩陣。

3.2.2沖突檢測算例

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

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

TAC=MABMBC

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

MA=TACMCA

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

同理，可計算得到作業(yè)計劃B的結(jié)果矩陣，即

MB=MBCMCAMAB=TBAMAB

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

同樣能夠計算得到作業(yè)計劃C的結(jié)果矩陣，即

MC=MCAMABMBC=TCBMBC

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

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

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

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

4　沖突檢測方法的實現(xiàn)

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

圖3　矩陣類圖

5　結(jié)　語

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

表3　矩陣類中成員函數(shù)的說明

[1]曹桂均,張華.動車基地調(diào)度集中系統(tǒng)研究[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]中國鐵道科學研究院通信信號研究所. 動車基地調(diào)度集中系統(tǒng)技術(shù)方案[R]. 北京：中國鐵道科學研究院通信信號研究所，2009.

[3]曹桂均.編組站綜合自動化系統(tǒng)控制技術(shù)及其擴展應(yīng)用的研究[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]林瑜筠. 鐵路信號基礎(chǔ)[M].北京：中國鐵道出版社，2006.

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

[7]程美玉,于祿,李興華. 矩陣乘法在計算中引起的思考[J]. 林區(qū)教學，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]胡潔萍，楊樹林，田益民. 矩陣乘法巧算及其拓廣應(yīng)用[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]鄧明香. 淺議矩陣乘法的應(yīng)用[J]. 大學教育，2015(2)：84-86.

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