基于图论的联锁程序的研究与设计

2013-08-30石擎宇成利刚

计算机工程与应用 2013年21期

关键词：站场搜索算法结点

石擎宇，谭丽，成利刚

SHIQingyu,TAN Li,CHENG Ligang

兰州交通大学自动化与电气工程学院，兰州 730070

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

1 引言

计算机联锁系统中联锁程序所涉及的数据点的选取方法、数据组织形式和核心算法的设计都是以6502电气集中电路的思想为基础而发展的[1]。但由于6502电气集中电路缺少对现实对象必要的理论分析，使得计算机联锁系统存在如下缺点。

首先，不能从理论上给出联锁运算核心算法的安全性证明。其次，数据被存于只读存储器。这种方法源于6502电气集中电路分为选择组和执行组两部分的想法[1]。使得联锁程序繁琐，且选排进路需大量人工干预。再次，数据组织形式繁琐且不统一。现有联锁系统多以文献[1]中的站场型数据结构为主，不同站场的数据组织形式不同。这使得联锁程序的可移植性较差，同时车载列控系统需存储沿线所有车站的进路表，数据量庞大[2-3]。

目前对计算机联锁系统中联锁程序的改进主要在数据的组织形式和进路搜索算法上。如文献[4]提出有向无环图结构，文献[5]提出的二叉树结构等。文献[6]在文献[5]的基础上作了一些改进，提出了一种二叉树与四叉链表结合的结构。文献[7-14]对文献[1]中的站场型数据结构进行了改进，并提出了一些新的搜索算法。如A*进路所搜算法[7]、k步扩散算法[8]和基于遗传算法的进路搜索算法[9]。由于上述算法仍以站场型数据结构为基础，都不能从理论证明算法的安全性。同时，算法仍有较大的局限性。

本文以线路本身及信号点的分析为基础，给出了一种较为恰当的数据点的选取方法。在此基础之上，进一步分析车站信号控制问题。

2 数学抽象

线路和基本信号点是设计联锁系统中联锁程序的现实根据，首先对这些对象进行分析，说明它们的本质和作用。

2.1 信号机

对列车进行指挥控制的根本是速度。不同的情况下有不同的速度限制，信号机是根据这一速度限制给出相对应的显示。信号机不能作为与道岔和无岔区段相同的数据点来看待，不能将其作为数据点。

2.2 无岔区段

无岔区段显然是线路的一部分，称这样的一部分线路为区段（无岔区段）：

定义1车辆无论从哪一端进入该段线路后，其前向运行方向唯一，这样的一段线路就称为区段。

2.3 道岔

根据上面区段的定义，对于一个单开道岔，应是这样的一部分线路：在线路分歧处，由两个区段共同构成的区段组。两个区段分别代表道岔的直股方向和弯股方向。道岔的属性全部被这两个区段的属性所代表。

2.4 点与点之间的三种关系

由上面分析知，对联锁运算要处理的线路而言，首先不存在信号机这一对象，其次道岔是由区段构成的。即线路的基本组成元素是区段。故取单一区段为一个点，下面讨论一个实际车站中点与点之间存在的三种关系。

2.4.1 关系R

定义2对点vi和vj，给定某一运行方向（向前、后）后，车辆从vi所代表的区段驶出，即刻压入的区段可以是vj所代表的区段，则称vi和vj间存在关系R，记：viRvj。同时，记vi和vj间不存在关系 R为viRˉvj。

另外，viRvj和vjRvi表示的是同一个意思，即点vi和点vj的线路直接相连。但viRvj表示车辆自vi离开后可进入vj，vjRvi表示车辆自vj离开后可进入vi，这是一种有方向的关系。

关系R描述了区段与区段之间的实际连接关系。

2.4.2 关系S

线路为车辆的运行提供了空间。对某一区段而言，其上方限界所包含的空间即是车辆占用这一区段时所需要的空间，将这一空间称为该区段的代表空间。

对于被分割为若干区段的线路，不同的区段所代表的空间可能存在重叠，为描述这种区段的代表空间之间相互重叠、侵入的关系，定义S关系。

定义3对点vi和vj，若vi与vj所代表的空间存在重叠，则称vi与vj之间存在关系S，记：viSvj。同时，记vi和vj间不存在关系 S为 viSˉvj。

定理1 对关系 S，若viSvj，则vjSvi。

另外，这里同样有两点需要强调。第一，viSvi没有意义。第二，若viSvj，vjSvk，不能推出viSvk。

2.4.3 关系B

考虑到多个区段共用一个轨道电路，下定义B关系。

定义4对点vi和vj，若vi所代表的区段和vj所代表的区段共用同一轨道电路，则称vi和vj间有关系 B，记：viBvj。同时，记 vi和 vj间不存在关系 B 为 viBˉvj。

定理2对关系B，有如下性质：

性质1 若 viBvj，则 vjBvi。

性质2 若 viBvj，vjBvk，则 viBvk。

另外，viBvi没有意义。

2.5 站场图的定义及其性质

上述三种关系给出了线路中点与点之间基本关系的描述。在此基础之上给出站场图的定义。

定义5 对一车站，称 G=(V，RV，SV，BV)为其站场图，其中V是构成站场线路的所有区段的点集：

命题1对一个只存在单开道岔的实际站场，由其得到的站场图G=(V，RV，SV，BV)，点集V在RV下的有向图有如下结论：

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

（2）对 vi∈V ，若 vi的出（入）度为3，则 vi为某一道岔区段点组合的前一区段点。

（3）对 vi∈V ，若 vi的出（入）度为4，则 vi为某两个对向道岔的道岔区段点组合的前一区段点。

另外，对一个道岔区段组中的两个点{vi，vj}有 viRˉvj，viSvj。

同时，上述关于道岔区段组中两个点关系的结论还可推广到更一般的情况。

定理3记一道岔组中含有的区段点的集合为{v1，v2，…，vn}，则 ∀vi，vj∈{v1，v2，…，vn}，viRˉvj，viSvj。

证明于道岔结点组集合{v1，v2，…，vn}任取 vi，vj，显然车辆不可由vi直接进入vj，必须经过岔尖前的一区段作折返才能完成，故 viRˉvj。

同时，vi和vj在道岔尖端一定存在重叠部分，即vi的空间一定侵入了vj的空间，故viSvj。证毕。

3 进路链与进路链的扩展集

上面的讨论已经给出数据点的选取及其组织形式的问题。下面给出进路的相关定义。

3.1 进路链和进路的定义

定义 6 对站场图 G=(V，RV，SV，BV)，称 M=(M*，RM)为一个进路链，其中：

（1）点集 M*⊂V 。

（2）关系集 RM⊂RV。

（3）点集M*中的点在关系集RM中关系的连接下得到的图是有且只有一个点的入度为0、出度为1，有且只有一个点的出度为0、入度为1，其余所有点的出入度均为1的链。

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

定义7进路链及其性质构成进路。这里的性质指列车的接车、发车、通过以及调车。

定义7给出了一条进路所包含的全部信息，即其始终端和性质。进路链的定义就是对进路一般性意义[3，14]进行的描述。定义6中（1）、（2）是指进路链的构成来自于站场图由RV确定的有向图。定义中的（3）描述了M*中的点在RM下所构成的图的特性。

定义6的前三条描述了站场图中V在RV下确定的有向图的一类子图，称这类子图为链。

定义6中的（4）是个现实结论：车辆走行所经过的区段不能有空间冲突。但对任意的V在RV下的链，并不能够构成车辆进行一次完整的自启动至停车所走行的路径。这点在定理4的证明中很重要。

3.2 进路链扩展集的定义

定义8对站场图G=(V，RV，SV，BV)中确定的一条进路链 M=(M*，RM)，称集合 M+={v|vSv`，其中 v`∈M*}为进路链M的扩展集。

进路链扩展集的定义描述了一个进路链为车辆运行提供空间时所涉及到的不在进路链中的所有点。这个集合包含了所有与进路链中的点具有S关系的点。车辆占用进路链中的点会自然侵入进路链外的点，所以需要被侵入的点为进路链提供空间支持。

3.3 单一进路安全性定理及证明

下面给出的定理用以证明满足进路链定义的点列可以作为车辆安全通过的通道。

定理4对进路链M=(M*，RM)，车辆可由入度为0的始端点不停车依次经过所有点到达出度为0的终端点。

证明对只有一个点的进路链，显然；对含有两个点的进路链，设 M=(M*，RM)，M*={v1，v2}，RM={v1Rv2}，则该进路链以v1为始端，指向终端v2。

由关系R的定义知，车辆离开v1点可以直接压入v2点。即，对含有两个点的进路链满足定理；对含有三个点的进路链，设 M=(M*，RM)，M*={v1，v2，v3}，RM={v1Rv2，v2Rv3} ，则该进路链以v1为始端，v3为终端，期间经过v2，即，v1-＞v2-＞v3。不妨设，v2在站场图G在RV下的有向图中的度为4（这里假设G中只含有双开道岔）。

记与 v2相连的点为 vi，vj，vk，vl，由命题1（3）知，vi，vj，vk，vl属于两个道岔点组。

设vi，vj属于一个，vk，vl属于另一个，则由定理3知，viSvj，vkSvl，同时，由 v1，v3∈M*知 v1Sˉv3，进而，v1，v3分别取自两个道岔点组，即，实际线路中，v1和v3分别位于v2的两侧，故，车辆可以从v1驶出，由v2一端压入v2，再从v2另一端驶出压入v3，即，车辆可由入度为0的始端点不停车一次经过所有点到达出度为0的终端点。

同理可证当v2的度为2，3时的情况。即，对含有三个点的进路链满足定理；假设对含有K个点任意进路链，均满足定理。设含有K+2个点的任意进路M=(M*，RM)，M*={v1，v2，…，vk，vk+1， vk+2}，RM={v1Rv2，v2Rv3，…， viRvi+1，…，vk+1Rvk+2}。取进路链 N=(N*，RN)，N*={v2，v3，…，vk，vk+1}，RN={v2Rv3， v3Rv4，…，viRvi+1，…，vkRvk+1} 。由含有 K 个点的进路链均满足定理知，进路链N满足定理。从而，可将N看做一个区段点，则M 为一由v1，N，v2三点构成的进路链。同含有三个点的进路链的证明可证，M满足定理。

综上所述，对任意进路链M，可满足定理。证毕。

定理4说明了在站场图G中由进路链定义确定的点列可以供车辆进行的一次直向不停车的运行。

定理5站场图G=(V，RV，SV，BV)中一条已经确定的进路链 M=(M*，RM)，其扩展集为 M+，则 ∀vi∈CV(M*∪M+)，不存在 vj∈M*，使得 viSvj。

证明设 ∃vi∈CV(M*∪M+)，vj∈M*，使得 viSvj。由M+={v|vSv`，其中 v`∈ M*}知，vi∈ M+。这与∀vi∈ CV(M*∪M+)矛盾。证毕。

定理5说明了车辆于进路链M上运行只会占用M*和M+中元素的代表空间，而不会侵入(M*∪M+)在V中的补集的元素所代表的空间。这说明，在按照进路链定义选出一个点列后，可以再在这个点列和它的扩展集的补集中选出另外一条新的进路链，这样先后选出的两个进路链之间没有空间冲突。

4 数据结构

由前面的讨论知，联锁运算所要处理的全部数据及相互组织关系可由站场图G=(V，RV，SV，BV)描述。G是一个四元组，考虑到三种关系在实际情况下的邻接矩阵是稀疏阵，故用邻接表作为基本模型[13]描述G。

表结点的结构：

由于三种关系都是在对同一组数据进行描述，故三个关系使用相同的头结点：

其中，used用于区分点是否在某一进路链的点集或扩展集中，locked属性用于反应轨道的占用情况。

5 过程和算法

联锁系统最基本的两个问题是：将那些将要或已经被某些通路使用的点及相关的点标记，使其不能再被使用；将那些已经用过了的点释放掉，供下次使用。这里讨论其中最基本的三种操作，点的封闭、释放和如何选择一条进路。

5.1 封闭某一结点

封闭某一结点指：当一结点处于某个进路链的点集或扩展集中时，将其从站场图点集V中暂时去除。

由于扩展集是由进路链点集生成的，所以只需逐个封闭进路链点集中的点及该点的扩展集，即与该点具有S关系的点，即可。

轨道电路的使用使得关系B十分重要。若在扩展集中只含有关系S，随着车辆的走行，由于关系B，将使某些点突然处于封闭状态，故应在进路链扩展集的定义中加入关系B。

一个道岔组由两个或以上的区段点构成。这些点在同一时刻只有一个可以存在。不同使用情况下，道岔组中没有被使用的点是否可以被安全使用，以下给出定理6解释这一问题。

定理6 对道岔组 D={v1，v2，…，vn}，若同时存在被封闭的点和未被封闭的，则该道岔组D中的被封闭的点没有处于某一进路链点集，只是处于进路链的扩展集中。同时，若道岔组中一点处于一进路链点集，那么该道岔组其他点均会被封闭。

证明设道岔组 D={v1，v2，…，vn}，其中 v1，v2，…，vs未被封闭，vs+1，…，vn被封闭。

假设vs+1,…,vn存在有一点vs+k，对进路链M=(M*,RM)，vs+k∈M*，则由定理3知，∀vi∈CD{vs+k}，viSvs+k，即，vi∈M+，vi应被封闭，这与 v1，v2，…，vs未被封闭矛盾。故，vs+1，…，vn只会在某进路链的扩展集中。证毕。

由定理6及关系S不具有传递性，可得：若一道岔组中同时存在被封闭的点和未被封闭的点，则未被封闭的点可以作为新一个进路链点集中点的候选点。

过程1封闭结点

输入：所要封闭的点P。

（1）将P点的used属性标识为已被使用。

（2）对所有与P具有S关系的点，将其used属性标识为已被使用。

5.2 释放某一结点

释放某一结点指：使被封闭的点返回未被封闭的状态。

释放已经封闭的点后，它可以再次成为一个进路链的点集或扩展集中的点。由于扩展集中的点要为点集中的点提供空间支持，故扩展集中的点要随点集中的点的释放而释放。同时，扩展集中的点又可能与多个点具有S关系，所以要释放扩展集中的点，只有当与这个点具有S关系的点都不属于某一进路链的点集中时，才能释放。

图1中交叉渡线处有ABCDEFGH，8个点。若有进路链M->B->G->P，其扩展集{A，E，D，H}，车辆离开B后，B的扩展集{A，E，D}中只能释放A，因为E、D同时还为G提供空间支持。只有当D区段也出清时才可以将E、D释放。

图1 交叉渡线处的结点设置

过程2释放结点

输入：要释放的点P。

（1）将P点的used属性标识为未被使用。

（2）将与P具有S关系的所有点放入集合T。

（3）取T中一点，若与这一点具有S关系的点的used属性均为未被使用，则将该点的used属性标识为未被使用。并将其移除集合T。

（4）若T为空，结束。否则，返回（3）。

5.3 由一对始终端点，选择一条进路

由定理4和定理5知，在V由RV确定的有向图中，按照进路链定义选择一个点列，再在这个点集和它的扩展集的补集中选择另外一个进路链，这样的一种连续选取进路的方法是符合安全条件的。

站场图G中，能够沟通任意两点的链不一定存在。即使存在，这些链中是否含有可以满足进路链定义的也不一定。而对所有的链进行验证是不现实的。另外，一般情况下，具有相同始终端的链，随着其长度的增加，满足进路链定义的可能性也会越来越小。故只对这些链中最短的一条进行验证，下面给出这一算法。该算法以Dijkstra算法[15]为原型。

算法1选择进路

输入：站场图G；V在R下的图中任两点x，y间的边长w(x，y)；进路的始端begin，终端end。

输出：表示进路由始端指向终端的前驱向量 previous[]。

对G，w（x，y）为V在R下的有向图中相连结点x和y之间的边长。记始端为begin，终端为end。

（1）对V中所有点：距离向量d[v]初始化，全部为无穷；前驱向量 previous[v]初始化，全部为空。

（2）置 d[begin]=0。

（3）初始化，集合T为V中没有确定最短路径的点，集合U为V中已经确定最短路径的点。

（4）将begin从T移入U。

（5）将used值为1的点从T移入U。

（6）若T为空，终止程序。

（7）若T非空，则取T中d[v]值最小的点，记min。

（8）将min从T移入U，若min==end，终止程序。

（9）对 T中所有点：若 d[v]＞d[min]+w(min，v)，则置d[v]=d[min]+w(min，v)，previous[v]=min。

（10）返回（6）。

特别的，对于终端是无岔区段的调车进路，只需将（8）改为：“将min从T移入U，若与min相连的点中存在end，则置 previous[end]=min，并将end从T移入U。”

6 实验

6.1 安全性实验

首先在真实数据下，测试文中所提出的封闭结点、释放结点及选路方法可以达到预期的安全性。根据文中提出的方法编写程序，以京津线举例站场作为实际数据，对其运行情况进行实测。选取数据结点64个，R关系147个，S关系56个，B关系134个。

图2给出了举例站场下行咽喉的一种结点设置方案，由图中绝缘节的设置易得，该咽喉有B关系89个，S关系36个。

图2 举例站场下行咽喉结点设置

（1）实验1：选择该站上下咽喉联锁表中的全部进路。

实验结果：程序可以实现联锁表中的全部进路，且对单一进路，程序同样防护了联锁表中的防护区段。

表1为进路a：“北京方面下行经5/7反位，13/15反位向I股道接车”与进路b：“北京方面下行经5/7定位，9/11反位向5股道接车”的实验数据。

由上述两例可以看出，B关系和S关系有效地确定了所需要防护的区段，侵限绝缘处防护区段的确定是仅由S关系完成的。道岔的位置是由进路链中的结点确定的。

实验证明文中所设计的进路的选择方法及封闭结点的方法是符合安全条件的。

（2）实验2：在含有已封闭点的站场内，先后选择两条由任意非道岔组结点作始终端的进路，随机选择了1 000对不同进路。

实验结果：没有存在空间冲突的一对进路被连续选出。

特别地，先后选择进路“3股道经5/7反位向北京方面上行发车”和进路“北京方面下行经1/3反位向I股道接车”。这一对进路是通过侵限绝缘的一对平行进路。它们的正常选出说明，S关系在侵限绝缘处准确确定了需要防护的区段。正如前面理论部分证明的，S关系确定的扩展集是为车辆运行额外空间支持的最小点集。

另外，实验中随机选择的进路多数已超出联锁表的范围，证明连续选择站场上任意多条进路是符合安全条件的。

6.2 与现有联锁程序的对比

由于文中提出的程序设计理论与现有基于6502电气集中电路的设计思想从根本上是不同的，两者不存在用以实现相同功能的程序，这里希望验证新的程序有更好的可移植性。

图3给出了几种主要结构与文中结构分别应用于三股道标准站、四股道标准站和举例站场三个典型车站时，需要人为录入数据量大小的对比。

图3 不同结构人为录入数据量对比

从图中可以看出，第一，对三个典型车站，文中结构的数据量都是最小的。第二，随着站场复杂度的增加，四种结构中文中结构的增量是最小的。第三，四种结构间的差距随着站场变得复杂而增加，表明越是复杂的车站，文中结构的优势越明显。

后两点也可由前面的理论推知。文中结构对任意数据点的属性是一样的，而其余几种结构为配合特定的搜索算法，不同数据点的属性个数有较大差距，站场越复杂属性越多。如站场型数据结构在举例站场中9号道岔结点属性有13个。

另外，从前面的理论部分可知，提出的算法和过程对所有车站是通用的，只需编写一个联锁程序就可应用于全部车站。而现有的程序对每个车站都需根据其电气集中电路编写特定的程序[1]。这证明新的程序具有更好的可移植性。

7 结束语

本文研究了计算机联锁系统中联锁程序数据点的选取、组织形式和最基本的一些算法。使用图论中的基本思想分析联锁程序所要处理的基本问题。给出了点、点与点之间关系和进路等几个最基本概念的严格数学定义，将图论中分析问题的手段引入到联锁问题的解释中。实验部分，验证了文中提出的理论本身符合安全条件，以及与现有系统相比所具有的较好的优越性。