基于二叉树结构的城轨沙盘联锁系统设计

2018-05-03蒋文燕

铁路计算机应用 2018年4期

蒋文燕

（西南交通大学信息科学与技术学院，成都 610097）

城市轨道交通联锁的主要功能是进路处理，该功能由联锁程序完成[1]。而联锁程序的复杂度和占用空间大小又很大程度上取决于联锁数据结构。一个好的联锁数据结构还能使各功能模块化，简化搜索流程，提高程序执行效率。为了解决计算机联锁中进路搜索存在的时间复杂度和内存利用问题,结合站场结构，建立一个好的联锁数据结，简化联锁程序，优化联锁系统很有必要。目前，提出的有基于有向图的数据结构，二叉树与四叉链表的结合结构[2],有向无环图与二叉树结合的结构[3]，基于邻接表的图形数据结构[4]。目前，使用的联锁表型数据结构，在车站规模较大时，占用内存空间较大，增加程序执行时间，不利于车站规模扩大。另一种站场型数据结构，占用内存空间较小，但为了避免搜出迂回进路和平行进路，在设计搜索算法时要设计相应的搜索条件，这又增加了搜索程序的复杂度。本文结合二叉树的结构特点，对站场型数据结构做了改进，把站场中的信号机，道岔，轨道区段都作为二叉树节点。这样在进路搜索时可以通过对进路上信号机的检查实现同向及反向敌对信号的检查。同时还在二叉树的节点中加入了指向前面节点的父辈指针，既可以从根节点采用先序遍历方式搜索到目标节点，也可以沿着二叉树中任一节点沿着父辈节点搜索到目标节点，实现进路的逆向搜索。

1 基于二叉树的进路搜索算法及研究

1.1 城轨沙盘2号线金顶站站场建模

1.1.1 站场信号设备的网络拓扑结构

图1所示为城轨实验室轨道交通二号线金顶集中站的站场平面布置图。设计线路时设定了运行方向（上行和下行方向），一般情况下，列车从上行线路进站，下行线路出站，但也可根据线路运行情况的需要，办理反方向的列车作业。

图1 金顶站信号平面布置图

地铁集中站控制的主要信号设备有信号机、转辙机和轨道电路，在信号平面布置图中有3种设备类型，信号机、道岔、轨道。结合前面对站场数据结构的分析对金顶集中站信号设备进行有向无环图建模，如图2所示。

图2 站场有向无环图建模

通过上面建立的有向无环图搜索进路较为复杂，观察发现在不存在三开道岔或更为复杂的道岔时，有向无环图中节点的度数最多二，这与二叉树结构存在相似性，所以选择在有向无环图中建立二叉树。选择进路的起点T0406（T0401）为根建立二叉树，并作为当前节点，若当前节点的度数为2，那么第1 条弧所指向的顶点为其左孩子, 第2条弧所指向的顶点为其右孩子, 若当前结点的度数为1, 则弧所指向的顶点为其左孩子, 若当前结点的度数为0, 则其为叶子结点, 以此类推。以节点T0406和节点T0401为根节点分别建立了两棵二叉树，如图3所示。

图3 站场二叉树模型

由于两棵二叉树在双动道岔处相交，为了便于区分，所以将双动道岔节点在两棵树中被定义成了Dbdc1和Dbdc2，节点数据完全相同，只是名称不同。

从两棵树根节点到各叶子节点的所有路径，也就是从洗象池站到金顶站折返线或停车线的所有路径，这样就将联锁程序中的进路搜索转化成了二叉树的遍历了。

1.1.2 信号设备节点的数据结构

二叉树在存储过程中，采用了链存储结构[5]。在站场的二叉树模型中，每个信号设备都对应了一个二叉树节点,每个节点都包含了数据域和指针域，因为涉及到逆向搜索，且在双动道岔处会出现1个节点有2个父辈节点，所以其节点具体组成是由一个数据元素和4个指针元素构成，4个指针元素分别指向其左右分支节点及左右父辈节点，所以表示二叉树的链表至少有5个域：表示该设备属性的数据域Nodedata、指向父辈节点的指针域Pleftparent、Prightparent和分别指向左右子节点的指针域Pleftchild、Prightchild，节点数据结构，如图4所示。父辈节点指针为前一节点的指针地址，根节点的父辈节点指针为空，除双动道岔节点的Prightparent不为空外，其它节点的Prightparent为空，Pleftchild、Prightchild分别存储该节点左右分支节点的指针地址，当节点不存在右孩子节点时，则Rightnode为空，叶子节点的左右子节点指针都为空。

图4 站场二叉树节点数据结构

1.2 基于二叉树的进路搜索算法设计

1.2.1 搜索策略分析

二叉树的遍历有递归和采用堆栈两种，这里我们采用了堆栈的方式[6]。从起始节点开始按前序遍历方式搜索，并将搜索到的节点压入堆栈，当搜索到邻站站台对应的节点后则中止，将该条进路的所有元素写入到数组中，直到搜索出以该节点开始的所有可用进路。

本文针对城轨实验室二号线金顶集中站的线路情况，考虑到有接发车作业和进出折返线作业，所以设计了两种搜索方式，正向搜索和逆向搜索。办理金顶站的接车进路和进折返线进路以及进停止线进路时，采用正向搜索（上行方向）。其中，接车进路是以车站股道为终端节点，进折返线或停止线是以叶子节点为搜索的终端节点。办理出折返线和发出进路时，则采用逆向搜索策略（下行方向）。这样就需要在办理进路时告诉搜索程序所办理的进路类型，以便采用对应的搜索策略。

1.2.2 搜索约束条件

办理进路后，从起始节点开始搜索，直到目标节点。通常都是将进路终端节点作为叶子节点，但在金顶站由于是站后折返，所以需要接车进站办理乘客下车作业后才可进折返线。鉴于此种情况需要在股道节点处设置一个进路结束标志f。

出折返线、出停止线和发车作业都涉及到逆向搜索，这就需要在值班员按下始端按钮后给出一个表示进路类型的信息，以便告诉程序该采取何种搜索方式。其逻辑流程图，如图5所示。

图5 搜索方式判定流程图

1.2.3 进路搜索算法

联锁表自动生成进路表的搜索算法是在启动搜索程序后就将整个站场的所有进路搜索出来，并保存每条进路所征用元素，然后在排列进路时检查改进路元素是否空闲，敌对进路是否建立。本文中提出的搜索算法的不同之处在于，它是在每次排列进路，车站值班员按下始端按钮，启动进路搜索程序，搜索出以该按钮为始端的所有可用进路。在搜索时一旦检查到某进路元素被征用或建立了敌对进路，则停止该条进路的搜索。若某进路可用，终端按钮处闪烁，在值班员按下终端按钮后，征用从始端到终端的进路元素，并开放始端信号机。

（1）搜索开始，根据始端按钮确定进路搜索方向；

（2）建立两个堆栈，S1和S2，S1用于保存进路搜索过程中的元素，S2用于保存对向道岔节点；

（3）按照先序遍历方式搜索；

（4）搜索出该始端按钮可排的所有可能进路，如果没有进路可用，则取消，否则按压终端按钮，排列进路。

正向进路搜索流程图如图6所示，逆向进路搜索流程图如图7所示。

图6 正向进路搜索流程图

2 城轨沙盘联锁软件设计与实现

2.1 联锁系统总体框架

联锁系统设计分为人机界面设计和联锁软件设计。如图8所示，为联锁系统的总体结构图。

联锁软件的主要功能模块有初始化数据、进路搜索、进路执行、进路锁闭、进路解锁、模拟/现场切换、串口通信模块[7-8]。

2.2 联锁系统人机界面的设计

按照人机界面的设计原则，用shape、line、image分别表示信号机、轨道、道岔，每个信号机旁设计一个按钮。因为采用了二叉树的搜素算法，所以将信号机、道岔和轨道都在公共模块中定义成了节点。

在工程加载函数中加入对定义的节点并初始化，然后设置相关控件的属性。

2.3 联锁软件工作流程

图7 逆向进路搜索流程图

图8 联锁系统总体框架图

该联锁系统的主要功能是通过二叉树的搜索算法完成进路的选排、进路锁闭、列车通过后进路自动解锁等功能。具体工作流程，如图9所示。

2.4 联锁软件各功能模块实现

2.4.1 模拟/现场切换模块实现

在登陆窗体的加载模块中添加了一个用于区分是模拟模式还是现场模式的布尔型变量，当它为真时进入现场模式，为假则进入模拟模式。

图9 软件工作流程

2.4.2 数据块实现

基于二叉树的搜索算法将进路中的信号设备相关数据都按节点数据块的形式定义在程序中。整个数据块中各节点按链表的形式存储在内存中，其存储在逻辑上是有序的，物理上是无序的。数据的访问是按程序指令找到始端节点，访问其数据域，然后根据节点中的指针地址去搜索该节点的下一节点并访问。这里采用Varptr()函数获取变量所在处的内存地址，即获得了指向变量内存位置的指针。

2.4.3 进路搜索模块

程序根据操作指令找到进路始端节点，从始端节点开始搜索，搜索到每个节点时，先检查节点对应的设备控件是否处于空闲状态，若满足则通过节点的Leftnode找到其左子节点地址，然后使用Copymemery()函数找到其左节点，再检查左节点是否满足条件，在这个过程中，若出现不满足条件的节点在，则跳出该条进路的搜索，返回到最近的分叉节点从右子节点搜索。搜索出的可用进路需要返回其进路终端节点地址，并保存该进路上的所有节点。整体程序思路设计，如图10所示。

图10 搜索模块整体程序设计思路流程图

搜索模块需要完成进路建立条件检查，其中包括进路是否空闲，道岔是否锁闭在敌对位置，敌对信号是否开放，轨道区段是否被征用。检查进路元素是否满足进路建立原则程序设计流程，如图11所示。

图11 进路元素条件检查程序流程图

2.4.4 进路执行模块

进路执行模块的功能就是根据操作指令，按照值班员的意图将进路上的道岔转换到正确位置，并锁闭进路，然后开放始端信号机。

由搜索模块返回一个地址指针，按下终端按钮启动进路执行模块，在始终端都确定的情况下，修改轨道、道岔的表示及信号机的显示，使进路设备都从空闲状态变成锁闭状态。进路锁闭后，延时10 s,在这10 s内可以人工无延时解锁进路。图12是进路执行模块工作流程。

2.4.5 进路解锁模块

图12 进路执行模块程序流程图

进路解锁分为列车通过后自动解锁和人工解锁两种，这里自动解锁分为分段解锁和一次性解锁，而人工解锁又分为无延时解锁和延时解锁。分段解锁只要列车每占用出清一个区段并占用下一区段后解锁该区段；有延时解锁是指在按下解锁按钮后检查到列车已压入接近轨，为保证安全，需要延时30 s确定列车未进入进路方可解锁，若在这端时间内列车已进入进路则进路无法解锁。本设计中自动解锁采用的是分段解锁方式。

列车根据信号机显示进入进路，列车压入进路就关闭始端信号机，列车的运行由Timer()函数完成。根据列车位置程序将列车占用并出清的区段解锁。由于界面设计上用的是Line、Shape、Image等控件表示的轨道、信号机、道岔，所以直接用这些控件的Bordercolor(fillcolor)的不同颜色来表示信号设备的不同状态。进路解锁模块程序流程图，如图13所示。