石擎宇，譚 麗，成利剛

SHIQingyu,TAN Li,CHENG Ligang

蘭州交通大學(xué) 自動化與電氣工程學(xué)院，蘭州 730070

School of Automation&Electrical Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China

1 引言

計(jì)算機(jī)聯(lián)鎖系統(tǒng)中聯(lián)鎖程序所涉及的數(shù)據(jù)點(diǎn)的選取方法、數(shù)據(jù)組織形式和核心算法的設(shè)計(jì)都是以6502電氣集中電路的思想為基礎(chǔ)而發(fā)展的[1]。但由于6502電氣集中電路缺少對現(xiàn)實(shí)對象必要的理論分析，使得計(jì)算機(jī)聯(lián)鎖系統(tǒng)存在如下缺點(diǎn)。

首先，不能從理論上給出聯(lián)鎖運(yùn)算核心算法的安全性證明。其次，數(shù)據(jù)被存于只讀存儲器。這種方法源于6502電氣集中電路分為選擇組和執(zhí)行組兩部分的想法[1]。使得聯(lián)鎖程序繁瑣，且選排進(jìn)路需大量人工干預(yù)。再次，數(shù)據(jù)組織形式繁瑣且不統(tǒng)一。現(xiàn)有聯(lián)鎖系統(tǒng)多以文獻(xiàn)[1]中的站場型數(shù)據(jù)結(jié)構(gòu)為主，不同站場的數(shù)據(jù)組織形式不同。這使得聯(lián)鎖程序的可移植性較差，同時車載列控系統(tǒng)需存儲沿線所有車站的進(jìn)路表，數(shù)據(jù)量龐大[2-3]。

目前對計(jì)算機(jī)聯(lián)鎖系統(tǒng)中聯(lián)鎖程序的改進(jìn)主要在數(shù)據(jù)的組織形式和進(jìn)路搜索算法上。如文獻(xiàn)[4]提出有向無環(huán)圖結(jié)構(gòu)，文獻(xiàn)[5]提出的二叉樹結(jié)構(gòu)等。文獻(xiàn)[6]在文獻(xiàn)[5]的基礎(chǔ)上作了一些改進(jìn)，提出了一種二叉樹與四叉鏈表結(jié)合的結(jié)構(gòu)。文獻(xiàn)[7-14]對文獻(xiàn)[1]中的站場型數(shù)據(jù)結(jié)構(gòu)進(jìn)行了改進(jìn)，并提出了一些新的搜索算法。如A*進(jìn)路所搜算法[7]、k步擴(kuò)散算法[8]和基于遺傳算法的進(jìn)路搜索算法[9]。由于上述算法仍以站場型數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)，都不能從理論證明算法的安全性。同時，算法仍有較大的局限性。

本文以線路本身及信號點(diǎn)的分析為基礎(chǔ)，給出了一種較為恰當(dāng)?shù)臄?shù)據(jù)點(diǎn)的選取方法。在此基礎(chǔ)之上，進(jìn)一步分析車站信號控制問題。

2 數(shù)學(xué)抽象

線路和基本信號點(diǎn)是設(shè)計(jì)聯(lián)鎖系統(tǒng)中聯(lián)鎖程序的現(xiàn)實(shí)根據(jù)，首先對這些對象進(jìn)行分析，說明它們的本質(zhì)和作用。

2.1 信號機(jī)

對列車進(jìn)行指揮控制的根本是速度。不同的情況下有不同的速度限制，信號機(jī)是根據(jù)這一速度限制給出相對應(yīng)的顯示。信號機(jī)不能作為與道岔和無岔區(qū)段相同的數(shù)據(jù)點(diǎn)來看待，不能將其作為數(shù)據(jù)點(diǎn)。

2.2 無岔區(qū)段

無岔區(qū)段顯然是線路的一部分，稱這樣的一部分線路為區(qū)段（無岔區(qū)段）：

定義1車輛無論從哪一端進(jìn)入該段線路后，其前向運(yùn)行方向唯一，這樣的一段線路就稱為區(qū)段。

2.3 道岔

根據(jù)上面區(qū)段的定義，對于一個單開道岔，應(yīng)是這樣的一部分線路：在線路分歧處，由兩個區(qū)段共同構(gòu)成的區(qū)段組。兩個區(qū)段分別代表道岔的直股方向和彎股方向。道岔的屬性全部被這兩個區(qū)段的屬性所代表。

2.4 點(diǎn)與點(diǎn)之間的三種關(guān)系

由上面分析知，對聯(lián)鎖運(yùn)算要處理的線路而言，首先不存在信號機(jī)這一對象，其次道岔是由區(qū)段構(gòu)成的。即線路的基本組成元素是區(qū)段。故取單一區(qū)段為一個點(diǎn)，下面討論一個實(shí)際車站中點(diǎn)與點(diǎn)之間存在的三種關(guān)系。

2.4.1 關(guān)系R

定義2對點(diǎn)vi和vj，給定某一運(yùn)行方向（向前、后）后，車輛從vi所代表的區(qū)段駛出，即刻壓入的區(qū)段可以是vj所代表的區(qū)段，則稱vi和vj間存在關(guān)系R，記：viRvj。同時，記vi和vj間不存在關(guān)系 R為viRˉvj。

另外，viRvj和vjRvi表示的是同一個意思，即點(diǎn)vi和點(diǎn)vj的線路直接相連。但viRvj表示車輛自vi離開后可進(jìn)入vj，vjRvi表示車輛自vj離開后可進(jìn)入vi，這是一種有方向的關(guān)系。

關(guān)系R描述了區(qū)段與區(qū)段之間的實(shí)際連接關(guān)系。

2.4.2 關(guān)系S

線路為車輛的運(yùn)行提供了空間。對某一區(qū)段而言，其上方限界所包含的空間即是車輛占用這一區(qū)段時所需要的空間，將這一空間稱為該區(qū)段的代表空間。

對于被分割為若干區(qū)段的線路，不同的區(qū)段所代表的空間可能存在重疊，為描述這種區(qū)段的代表空間之間相互重疊、侵入的關(guān)系，定義S關(guān)系。

定義3對點(diǎn)vi和vj，若vi與vj所代表的空間存在重疊，則稱vi與vj之間存在關(guān)系S，記：viSvj。同時，記vi和vj間不存在關(guān)系 S為 viSˉvj。

定理1 對關(guān)系 S，若viSvj，則vjSvi。

另外，這里同樣有兩點(diǎn)需要強(qiáng)調(diào)。第一，viSvi沒有意義。第二，若viSvj，vjSvk，不能推出viSvk。

2.4.3 關(guān)系B

考慮到多個區(qū)段共用一個軌道電路，下定義B關(guān)系。

定義4對點(diǎn)vi和vj，若vi所代表的區(qū)段和vj所代表的區(qū)段共用同一軌道電路，則稱vi和vj間有關(guān)系 B，記：viBvj。同時，記 vi和 vj間不存在關(guān)系 B 為 viBˉvj。

定理2對關(guān)系B，有如下性質(zhì)：

性質(zhì)1 若 viBvj，則 vjBvi。

性質(zhì)2 若 viBvj，vjBvk，則 viBvk。

另外，viBvi沒有意義。

2.5 站場圖的定義及其性質(zhì)

上述三種關(guān)系給出了線路中點(diǎn)與點(diǎn)之間基本關(guān)系的描述。在此基礎(chǔ)之上給出站場圖的定義。

定義5 對一車站，稱 G=(V，RV，SV，BV)為其站場圖，其中V是構(gòu)成站場線路的所有區(qū)段的點(diǎn)集：

命題1對一個只存在單開道岔的實(shí)際站場，由其得到的站場圖G=(V，RV，SV，BV)，點(diǎn)集V在RV下的有向圖有如下結(jié)論：

（1）?vi∈V ，vi的出（入）度小于等于4。

（2）對 vi∈V ，若 vi的出（入）度為3，則 vi為某一道岔區(qū)段點(diǎn)組合的前一區(qū)段點(diǎn)。

（3）對 vi∈V ，若 vi的出（入）度為4，則 vi為某兩個對向道岔的道岔區(qū)段點(diǎn)組合的前一區(qū)段點(diǎn)。

另外，對一個道岔區(qū)段組中的兩個點(diǎn){vi，vj}有 viRˉvj，viSvj。

同時，上述關(guān)于道岔區(qū)段組中兩個點(diǎn)關(guān)系的結(jié)論還可推廣到更一般的情況。

定理3記一道岔組中含有的區(qū)段點(diǎn)的集合為{v1，v2，…，vn}，則 ?vi，vj∈{v1，v2，…，vn}，viRˉvj，viSvj。

證明 于道岔結(jié)點(diǎn)組集合{v1，v2，…，vn}任取 vi，vj，顯然車輛不可由vi直接進(jìn)入vj，必須經(jīng)過岔尖前的一區(qū)段作折返才能完成，故 viRˉvj。

同時，vi和vj在道岔尖端一定存在重疊部分，即vi的空間一定侵入了vj的空間，故viSvj。證畢。

3 進(jìn)路鏈與進(jìn)路鏈的擴(kuò)展集

上面的討論已經(jīng)給出數(shù)據(jù)點(diǎn)的選取及其組織形式的問題。下面給出進(jìn)路的相關(guān)定義。

3.1 進(jìn)路鏈和進(jìn)路的定義

定義 6 對站場圖 G=(V，RV，SV，BV)，稱 M=(M*，RM)為一個進(jìn)路鏈，其中：

（1）點(diǎn)集 M*?V 。

（2）關(guān)系集 RM?RV。

（3）點(diǎn)集M*中的點(diǎn)在關(guān)系集RM中關(guān)系的連接下得到的圖是有且只有一個點(diǎn)的入度為0、出度為1，有且只有一個點(diǎn)的出度為0、入度為1，其余所有點(diǎn)的出入度均為1的鏈。

（4）?v1，v2∈ M*，v1Sˉv2。

定義7進(jìn)路鏈及其性質(zhì)構(gòu)成進(jìn)路。這里的性質(zhì)指列車的接車、發(fā)車、通過以及調(diào)車。

定義7給出了一條進(jìn)路所包含的全部信息，即其始終端和性質(zhì)。進(jìn)路鏈的定義就是對進(jìn)路一般性意義[3，14]進(jìn)行的描述。定義6中（1）、（2）是指進(jìn)路鏈的構(gòu)成來自于站場圖由RV確定的有向圖。定義中的（3）描述了M*中的點(diǎn)在RM下所構(gòu)成的圖的特性。

定義6的前三條描述了站場圖中V在RV下確定的有向圖的一類子圖，稱這類子圖為鏈。

定義6中的（4）是個現(xiàn)實(shí)結(jié)論：車輛走行所經(jīng)過的區(qū)段不能有空間沖突。但對任意的V在RV下的鏈，并不能夠構(gòu)成車輛進(jìn)行一次完整的自啟動至停車所走行的路徑。這點(diǎn)在定理4的證明中很重要。

3.2 進(jìn)路鏈擴(kuò)展集的定義

定義8對站場圖G=(V，RV，SV，BV)中確定的一條進(jìn)路鏈 M=(M*，RM)，稱集合 M+={v|vSv`，其中 v`∈M*}為進(jìn)路鏈M的擴(kuò)展集。

進(jìn)路鏈擴(kuò)展集的定義描述了一個進(jìn)路鏈為車輛運(yùn)行提供空間時所涉及到的不在進(jìn)路鏈中的所有點(diǎn)。這個集合包含了所有與進(jìn)路鏈中的點(diǎn)具有S關(guān)系的點(diǎn)。車輛占用進(jìn)路鏈中的點(diǎn)會自然侵入進(jìn)路鏈外的點(diǎn)，所以需要被侵入的點(diǎn)為進(jìn)路鏈提供空間支持。

3.3 單一進(jìn)路安全性定理及證明

下面給出的定理用以證明滿足進(jìn)路鏈定義的點(diǎn)列可以作為車輛安全通過的通道。

定理4對進(jìn)路鏈M=(M*，RM)，車輛可由入度為0的始端點(diǎn)不停車依次經(jīng)過所有點(diǎn)到達(dá)出度為0的終端點(diǎn)。

證明 對只有一個點(diǎn)的進(jìn)路鏈，顯然；對含有兩個點(diǎn)的進(jìn)路鏈，設(shè) M=(M*，RM)，M*={v1，v2}，RM={v1Rv2}，則該進(jìn)路鏈以v1為始端，指向終端v2。

由關(guān)系R的定義知，車輛離開v1點(diǎn)可以直接壓入v2點(diǎn)。即，對含有兩個點(diǎn)的進(jìn)路鏈滿足定理；對含有三個點(diǎn)的進(jìn)路鏈，設(shè) M=(M*，RM)，M*={v1，v2，v3}，RM={v1Rv2，v2Rv3} ，則該進(jìn)路鏈以v1為始端，v3為終端，期間經(jīng)過v2，即，v1-＞v2-＞v3。不妨設(shè)，v2在站場圖G在RV下的有向圖中的度為4（這里假設(shè)G中只含有雙開道岔）。

記與 v2相連的點(diǎn)為 vi，vj，vk，vl，由命題1（3）知，vi，vj，vk，vl屬于兩個道岔點(diǎn)組。

設(shè)vi，vj屬于一個，vk，vl屬于另一個，則由定理3知，viSvj，vkSvl，同時，由 v1，v3∈M*知 v1Sˉv3，進(jìn)而，v1，v3分別取自兩個道岔點(diǎn)組，即，實(shí)際線路中，v1和v3分別位于v2的兩側(cè)，故，車輛可以從v1駛出，由v2一端壓入v2，再從v2另一端駛出壓入v3，即，車輛可由入度為0的始端點(diǎn)不停車一次經(jīng)過所有點(diǎn)到達(dá)出度為0的終端點(diǎn)。

同理可證當(dāng)v2的度為2，3時的情況。即，對含有三個點(diǎn)的進(jìn)路鏈滿足定理；假設(shè)對含有K個點(diǎn)任意進(jìn)路鏈，均滿足定理。設(shè)含有K+2個點(diǎn)的任意進(jìn)路M=(M*，RM)，M*={v1，v2，…，vk，vk+1， vk+2}，RM={v1Rv2，v2Rv3，…， viRvi+1，…，vk+1Rvk+2}。取進(jìn)路鏈 N=(N*，RN)，N*={v2，v3，…，vk，vk+1}，RN={v2Rv3， v3Rv4，…，viRvi+1，…，vkRvk+1} 。由含有 K 個點(diǎn)的進(jìn)路鏈均滿足定理知，進(jìn)路鏈N滿足定理。從而，可將N看做一個區(qū)段點(diǎn)，則M 為一由v1，N，v2三點(diǎn)構(gòu)成的進(jìn)路鏈。同含有三個點(diǎn)的進(jìn)路鏈的證明可證，M滿足定理。

綜上所述，對任意進(jìn)路鏈M，可滿足定理。證畢。

定理4說明了在站場圖G中由進(jìn)路鏈定義確定的點(diǎn)列可以供車輛進(jìn)行的一次直向不停車的運(yùn)行。

定理5站場圖G=(V，RV，SV，BV)中一條已經(jīng)確定的進(jìn)路鏈 M=(M*，RM)，其擴(kuò)展集為 M+，則 ?vi∈CV(M*∪M+)，不存在 vj∈M*，使得 viSvj。

證明 設(shè) ?vi∈CV(M*∪M+)，vj∈M*，使得 viSvj。由M+={v|vSv`，其中 v`∈ M*}知，vi∈ M+。這與?vi∈ CV(M*∪M+)矛盾。證畢。

定理5說明了車輛于進(jìn)路鏈M上運(yùn)行只會占用M*和M+中元素的代表空間，而不會侵入(M*∪M+)在V中的補(bǔ)集的元素所代表的空間。這說明，在按照進(jìn)路鏈定義選出一個點(diǎn)列后，可以再在這個點(diǎn)列和它的擴(kuò)展集的補(bǔ)集中選出另外一條新的進(jìn)路鏈，這樣先后選出的兩個進(jìn)路鏈之間沒有空間沖突。

4 數(shù)據(jù)結(jié)構(gòu)

由前面的討論知，聯(lián)鎖運(yùn)算所要處理的全部數(shù)據(jù)及相互組織關(guān)系可由站場圖G=(V，RV，SV，BV)描述。G是一個四元組，考慮到三種關(guān)系在實(shí)際情況下的鄰接矩陣是稀疏陣，故用鄰接表作為基本模型[13]描述G。

表結(jié)點(diǎn)的結(jié)構(gòu)：

由于三種關(guān)系都是在對同一組數(shù)據(jù)進(jìn)行描述，故三個關(guān)系使用相同的頭結(jié)點(diǎn)：

其中，used用于區(qū)分點(diǎn)是否在某一進(jìn)路鏈的點(diǎn)集或擴(kuò)展集中，locked屬性用于反應(yīng)軌道的占用情況。

5 過程和算法

聯(lián)鎖系統(tǒng)最基本的兩個問題是：將那些將要或已經(jīng)被某些通路使用的點(diǎn)及相關(guān)的點(diǎn)標(biāo)記，使其不能再被使用；將那些已經(jīng)用過了的點(diǎn)釋放掉，供下次使用。這里討論其中最基本的三種操作，點(diǎn)的封閉、釋放和如何選擇一條進(jìn)路。

5.1 封閉某一結(jié)點(diǎn)

封閉某一結(jié)點(diǎn)指：當(dāng)一結(jié)點(diǎn)處于某個進(jìn)路鏈的點(diǎn)集或擴(kuò)展集中時，將其從站場圖點(diǎn)集V中暫時去除。

由于擴(kuò)展集是由進(jìn)路鏈點(diǎn)集生成的，所以只需逐個封閉進(jìn)路鏈點(diǎn)集中的點(diǎn)及該點(diǎn)的擴(kuò)展集，即與該點(diǎn)具有S關(guān)系的點(diǎn)，即可。

軌道電路的使用使得關(guān)系B十分重要。若在擴(kuò)展集中只含有關(guān)系S，隨著車輛的走行，由于關(guān)系B，將使某些點(diǎn)突然處于封閉狀態(tài)，故應(yīng)在進(jìn)路鏈擴(kuò)展集的定義中加入關(guān)系B。

一個道岔組由兩個或以上的區(qū)段點(diǎn)構(gòu)成。這些點(diǎn)在同一時刻只有一個可以存在。不同使用情況下，道岔組中沒有被使用的點(diǎn)是否可以被安全使用，以下給出定理6解釋這一問題。

定理6 對道岔組 D={v1，v2，…，vn}，若同時存在被封閉的點(diǎn)和未被封閉的，則該道岔組D中的被封閉的點(diǎn)沒有處于某一進(jìn)路鏈點(diǎn)集，只是處于進(jìn)路鏈的擴(kuò)展集中。同時，若道岔組中一點(diǎn)處于一進(jìn)路鏈點(diǎn)集，那么該道岔組其他點(diǎn)均會被封閉。

證明 設(shè)道岔組 D={v1，v2，…，vn}，其中 v1，v2，…，vs未被封閉，vs+1，…，vn被封閉。

假設(shè)vs+1,…,vn存在有一點(diǎn)vs+k，對進(jìn)路鏈M=(M*,RM)，vs+k∈M*，則由定理3知，?vi∈CD{vs+k}，viSvs+k，即，vi∈M+，vi應(yīng)被封閉，這與 v1，v2，…，vs未被封閉矛盾。故，vs+1，…，vn只會在某進(jìn)路鏈的擴(kuò)展集中。證畢。

由定理6及關(guān)系S不具有傳遞性，可得：若一道岔組中同時存在被封閉的點(diǎn)和未被封閉的點(diǎn)，則未被封閉的點(diǎn)可以作為新一個進(jìn)路鏈點(diǎn)集中點(diǎn)的候選點(diǎn)。

過程1封閉結(jié)點(diǎn)

輸入：所要封閉的點(diǎn)P。

（1）將P點(diǎn)的used屬性標(biāo)識為已被使用。

（2）對所有與P具有S關(guān)系的點(diǎn)，將其used屬性標(biāo)識為已被使用。

5.2 釋放某一結(jié)點(diǎn)

釋放某一結(jié)點(diǎn)指：使被封閉的點(diǎn)返回未被封閉的狀態(tài)。

釋放已經(jīng)封閉的點(diǎn)后，它可以再次成為一個進(jìn)路鏈的點(diǎn)集或擴(kuò)展集中的點(diǎn)。由于擴(kuò)展集中的點(diǎn)要為點(diǎn)集中的點(diǎn)提供空間支持，故擴(kuò)展集中的點(diǎn)要隨點(diǎn)集中的點(diǎn)的釋放而釋放。同時，擴(kuò)展集中的點(diǎn)又可能與多個點(diǎn)具有S關(guān)系，所以要釋放擴(kuò)展集中的點(diǎn)，只有當(dāng)與這個點(diǎn)具有S關(guān)系的點(diǎn)都不屬于某一進(jìn)路鏈的點(diǎn)集中時，才能釋放。

圖1中交叉渡線處有ABCDEFGH，8個點(diǎn)。若有進(jìn)路鏈M->B->G->P，其擴(kuò)展集{A，E，D，H}，車輛離開B后，B的擴(kuò)展集{A，E，D}中只能釋放A，因?yàn)镋、D同時還為G提供空間支持。只有當(dāng)D區(qū)段也出清時才可以將E、D釋放。

圖1 交叉渡線處的結(jié)點(diǎn)設(shè)置

過程2釋放結(jié)點(diǎn)

輸入：要釋放的點(diǎn)P。

（1）將P點(diǎn)的used屬性標(biāo)識為未被使用。

（2）將與P具有S關(guān)系的所有點(diǎn)放入集合T。

（3）取T中一點(diǎn)，若與這一點(diǎn)具有S關(guān)系的點(diǎn)的used屬性均為未被使用，則將該點(diǎn)的used屬性標(biāo)識為未被使用。并將其移除集合T。

（4）若T為空，結(jié)束。否則，返回（3）。

5.3 由一對始終端點(diǎn)，選擇一條進(jìn)路

由定理4和定理5知，在V由RV確定的有向圖中，按照進(jìn)路鏈定義選擇一個點(diǎn)列，再在這個點(diǎn)集和它的擴(kuò)展集的補(bǔ)集中選擇另外一個進(jìn)路鏈，這樣的一種連續(xù)選取進(jìn)路的方法是符合安全條件的。

站場圖G中，能夠溝通任意兩點(diǎn)的鏈不一定存在。即使存在，這些鏈中是否含有可以滿足進(jìn)路鏈定義的也不一定。而對所有的鏈進(jìn)行驗(yàn)證是不現(xiàn)實(shí)的。另外，一般情況下，具有相同始終端的鏈，隨著其長度的增加，滿足進(jìn)路鏈定義的可能性也會越來越小。故只對這些鏈中最短的一條進(jìn)行驗(yàn)證，下面給出這一算法。該算法以Dijkstra算法[15]為原型。

算法1選擇進(jìn)路

輸入：站場圖G；V在R下的圖中任兩點(diǎn)x，y間的邊長w(x，y)；進(jìn)路的始端begin，終端end。

輸出：表示進(jìn)路由始端指向終端的前驅(qū)向量 previous[]。

對G，w（x，y）為V在R下的有向圖中相連結(jié)點(diǎn)x和y之間的邊長。記始端為begin，終端為end。

（1）對V中所有點(diǎn)：距離向量d[v]初始化，全部為無窮；前驅(qū)向量 previous[v]初始化，全部為空。

（2）置 d[begin]=0。

（3）初始化，集合T為V中沒有確定最短路徑的點(diǎn)，集合U為V中已經(jīng)確定最短路徑的點(diǎn)。

（4）將begin從T移入U(xiǎn)。

（5）將used值為1的點(diǎn)從T移入U(xiǎn)。

（6）若T為空，終止程序。

（7）若T非空，則取T中d[v]值最小的點(diǎn)，記min。

（8）將min從T移入U(xiǎn)，若min==end，終止程序。

（9）對 T中所有點(diǎn)：若 d[v]＞d[min]+w(min，v)，則置d[v]=d[min]+w(min，v)，previous[v]=min。

（10）返回（6）。

特別的，對于終端是無岔區(qū)段的調(diào)車進(jìn)路，只需將（8）改為：“將min從T移入U(xiǎn)，若與min相連的點(diǎn)中存在end，則置 previous[end]=min，并將end從T移入U(xiǎn)?！?/p>

6 實(shí)驗(yàn)

6.1 安全性實(shí)驗(yàn)

首先在真實(shí)數(shù)據(jù)下，測試文中所提出的封閉結(jié)點(diǎn)、釋放結(jié)點(diǎn)及選路方法可以達(dá)到預(yù)期的安全性。根據(jù)文中提出的方法編寫程序，以京津線舉例站場作為實(shí)際數(shù)據(jù)，對其運(yùn)行情況進(jìn)行實(shí)測。選取數(shù)據(jù)結(jié)點(diǎn)64個，R關(guān)系147個，S關(guān)系56個，B關(guān)系134個。

圖2給出了舉例站場下行咽喉的一種結(jié)點(diǎn)設(shè)置方案，由圖中絕緣節(jié)的設(shè)置易得，該咽喉有B關(guān)系89個，S關(guān)系36個。

圖2 舉例站場下行咽喉結(jié)點(diǎn)設(shè)置

（1）實(shí)驗(yàn)1：選擇該站上下咽喉聯(lián)鎖表中的全部進(jìn)路。

實(shí)驗(yàn)結(jié)果：程序可以實(shí)現(xiàn)聯(lián)鎖表中的全部進(jìn)路，且對單一進(jìn)路，程序同樣防護(hù)了聯(lián)鎖表中的防護(hù)區(qū)段。

表1為進(jìn)路a：“北京方面下行經(jīng)5/7反位，13/15反位向I股道接車”與進(jìn)路b：“北京方面下行經(jīng)5/7定位，9/11反位向5股道接車”的實(shí)驗(yàn)數(shù)據(jù)。

由上述兩例可以看出，B關(guān)系和S關(guān)系有效地確定了所需要防護(hù)的區(qū)段，侵限絕緣處防護(hù)區(qū)段的確定是僅由S關(guān)系完成的。道岔的位置是由進(jìn)路鏈中的結(jié)點(diǎn)確定的。

實(shí)驗(yàn)證明文中所設(shè)計(jì)的進(jìn)路的選擇方法及封閉結(jié)點(diǎn)的方法是符合安全條件的。

（2）實(shí)驗(yàn)2：在含有已封閉點(diǎn)的站場內(nèi)，先后選擇兩條由任意非道岔組結(jié)點(diǎn)作始終端的進(jìn)路，隨機(jī)選擇了1 000對不同進(jìn)路。

實(shí)驗(yàn)結(jié)果：沒有存在空間沖突的一對進(jìn)路被連續(xù)選出。

特別地，先后選擇進(jìn)路“3股道經(jīng)5/7反位向北京方面上行發(fā)車”和進(jìn)路“北京方面下行經(jīng)1/3反位向I股道接車”。這一對進(jìn)路是通過侵限絕緣的一對平行進(jìn)路。它們的正常選出說明，S關(guān)系在侵限絕緣處準(zhǔn)確確定了需要防護(hù)的區(qū)段。正如前面理論部分證明的，S關(guān)系確定的擴(kuò)展集是為車輛運(yùn)行額外空間支持的最小點(diǎn)集。

另外，實(shí)驗(yàn)中隨機(jī)選擇的進(jìn)路多數(shù)已超出聯(lián)鎖表的范圍，證明連續(xù)選擇站場上任意多條進(jìn)路是符合安全條件的。

6.2 與現(xiàn)有聯(lián)鎖程序的對比

由于文中提出的程序設(shè)計(jì)理論與現(xiàn)有基于6502電氣集中電路的設(shè)計(jì)思想從根本上是不同的，兩者不存在用以實(shí)現(xiàn)相同功能的程序，這里希望驗(yàn)證新的程序有更好的可移植性。

圖3給出了幾種主要結(jié)構(gòu)與文中結(jié)構(gòu)分別應(yīng)用于三股道標(biāo)準(zhǔn)站、四股道標(biāo)準(zhǔn)站和舉例站場三個典型車站時，需要人為錄入數(shù)據(jù)量大小的對比。

圖3 不同結(jié)構(gòu)人為錄入數(shù)據(jù)量對比

從圖中可以看出，第一，對三個典型車站，文中結(jié)構(gòu)的數(shù)據(jù)量都是最小的。第二，隨著站場復(fù)雜度的增加，四種結(jié)構(gòu)中文中結(jié)構(gòu)的增量是最小的。第三，四種結(jié)構(gòu)間的差距隨著站場變得復(fù)雜而增加，表明越是復(fù)雜的車站，文中結(jié)構(gòu)的優(yōu)勢越明顯。

后兩點(diǎn)也可由前面的理論推知。文中結(jié)構(gòu)對任意數(shù)據(jù)點(diǎn)的屬性是一樣的，而其余幾種結(jié)構(gòu)為配合特定的搜索算法，不同數(shù)據(jù)點(diǎn)的屬性個數(shù)有較大差距，站場越復(fù)雜屬性越多。如站場型數(shù)據(jù)結(jié)構(gòu)在舉例站場中9號道岔結(jié)點(diǎn)屬性有13個。

另外，從前面的理論部分可知，提出的算法和過程對所有車站是通用的，只需編寫一個聯(lián)鎖程序就可應(yīng)用于全部車站。而現(xiàn)有的程序?qū)γ總€車站都需根據(jù)其電氣集中電路編寫特定的程序[1]。這證明新的程序具有更好的可移植性。

7 結(jié)束語

本文研究了計(jì)算機(jī)聯(lián)鎖系統(tǒng)中聯(lián)鎖程序數(shù)據(jù)點(diǎn)的選取、組織形式和最基本的一些算法。使用圖論中的基本思想分析聯(lián)鎖程序所要處理的基本問題。給出了點(diǎn)、點(diǎn)與點(diǎn)之間關(guān)系和進(jìn)路等幾個最基本概念的嚴(yán)格數(shù)學(xué)定義，將圖論中分析問題的手段引入到聯(lián)鎖問題的解釋中。實(shí)驗(yàn)部分，驗(yàn)證了文中提出的理論本身符合安全條件，以及與現(xiàn)有系統(tǒng)相比所具有的較好的優(yōu)越性。

表1 進(jìn)路a、b的安全性實(shí)驗(yàn)數(shù)據(jù)

[1]趙志熙.計(jì)算機(jī)聯(lián)鎖系統(tǒng)技術(shù)[M].北京：中國鐵道出版社，1999：122-176.

[2]董昱.區(qū)間信號與列車運(yùn)行控制系統(tǒng)[M].北京：中國鐵道出版社，2008：269-295.

[3]王瑞峰.鐵路信號運(yùn)營基礎(chǔ)[M].北京：中國鐵道出版社，2008：29-36，63-100.

[4]吳益芳.進(jìn)路搜索數(shù)據(jù)結(jié)構(gòu)與算法研究[J].鐵道通信信號，2010（8）：34-36.

[5]文武臣，王曉明.計(jì)算機(jī)聯(lián)鎖的數(shù)據(jù)結(jié)構(gòu)及進(jìn)路搜索算法[J].重慶工學(xué)院學(xué)報(bào)，2008，22（6）：51-53.

[6]陳志穎，董昱，楊柳，等.計(jì)算機(jī)聯(lián)鎖進(jìn)路搜索算法的分析與研究[J].鐵道通信信號，2007（4）：4-6.

[7]梁藝凡，譚麗，馮挺.A～*進(jìn)路搜索算法的研究與實(shí)現(xiàn)[J].鐵道標(biāo)準(zhǔn)設(shè)計(jì)，2013（2）：117-127.

[8]祝庚.聯(lián)鎖進(jìn)路生成的k步擴(kuò)散搜索算法實(shí)現(xiàn)[J].微計(jì)算機(jī)信息，2008（21）：245-247.

[9]徐洪澤，燕永田，徐立新.計(jì)算機(jī)聯(lián)鎖控制系統(tǒng)的進(jìn)路生成算法研究[J].北方交通大學(xué)學(xué)報(bào)，1998（5）：94-98.

[10]董昱，林俊亭，劉振強(qiáng).計(jì)算機(jī)聯(lián)鎖軟件數(shù)據(jù)結(jié)構(gòu)的分析及應(yīng)用[J].蘭州鐵道學(xué)院學(xué)報(bào)，2003，22（3）：94-96.

[11]徐鑫，陳光武.計(jì)算機(jī)聯(lián)鎖軟件設(shè)計(jì)及進(jìn)路搜索算法的研究與應(yīng)用[J].鐵路計(jì)算機(jī)應(yīng)用，2011，20（1）：49-52.

[12]朱明，王曉明.一種鐵路微機(jī)聯(lián)鎖進(jìn)路搜索的實(shí)現(xiàn)方法[J].鐵路計(jì)算機(jī)應(yīng)用，2007，16（11）：45-48.

[13]彭建偉，殷人昆.基于鄰接表結(jié)構(gòu)的進(jìn)路搜索算法研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2006，28（18）：3400-3401.

[14]張敏，陳敏.一種針對站場型結(jié)構(gòu)數(shù)據(jù)的計(jì)算機(jī)搜索算法[J].電子制作，2012（10）：145-146.

[15]高繼祥.鐵路信號運(yùn)營基礎(chǔ)[M].北京：中國鐵道出版社，1998：109-138.

[16]Kingston J H.Algorithms and data structures design，correctness，analysis[M].2nd ed.New York：Addison-Wesley Pub，1997.