铁路车站计算机联锁软件进路搜索算法研究

王文波，马学霞

（1.浙江众合科技股份有限公司，杭州 310052；2.卡斯柯信号有限公司，上海 200071）

铁路车站计算机联锁软件进路搜索算法研究

王文波1，马学霞2

（1.浙江众合科技股份有限公司，杭州 310052；2.卡斯柯信号有限公司，上海 200071）

计算机联锁软件的关键技术是联锁软件数据结构的选取和进路搜索算法的优化。针对常用数据结构对联锁软件的制约和进路搜索算法对搜索效率的影响，本文基于站场型数据结构，优化了进路搜索算法，以站场举例为对象，详细论述了采用高度搜索算法搜索基本进路和变更进路的过程，该过程表明高度搜索算法克服了广度和深度优先算法的不足，搜索目标明确、搜索过程高效准确。

进路搜索算法；数据结构；计算机联锁

铁路车站联锁系统用于判断站内轨道电路的空闲与占用、转换并锁闭道岔、控制信号开放与关闭及控制进路的建立与解锁。目前我国车站主要采用电气集中联锁和计算机联锁。因计算机联锁具有高可靠性、高安全性、维护工作量小、占地面积小、便于和其他信号系统相连等优点[1]，计算机联锁正处于大力发展并逐步代替电气集中联锁的阶段。

计算机联锁软件采用模块化方法设计，可分为人机会话层、联锁逻辑运算层和执行表示层，层次结构如图1所示。人机会话层完成操作信息、表示信息以及维护与管理信息的处理；联锁运算层完成基本联锁运算、特殊联锁操作、自动检测和故障诊断，实现与其它系统的联锁功能。执行层完成控制命令的输出和表示信息的输入。联锁逻辑运算模块是联锁运算层的核心，完成进路搜索、建立、锁闭和解锁。进路搜索的效率和准确性依赖于搜索算法，而搜索算法的选取取决于联锁软件采用的数据结构[2]。

图1 软件的层次结构

1 联锁软件数据结构

联锁数据量是很大的，它们在计算机中的存储和组织方式称为数据结构[3]。数据有静态数据和动态数据之分，相应有静态数据结构和动态数据结构。静态数据结构是程序编写的基础，精心选择的数据结构决定着进路搜索算法的选取，合理高效的进路搜索算法可以带来更高的运行效率，影响到软件复杂度等[4]。目前计算机联锁常用的数据结构主要有：进路表型数据结构、二叉树型数据结构和站场型数据结构。

1.1 进路表型数据结构

按照进路中包含的信号点数据属性将数据放入一个数据表便构成进路表数据结构。将所有进路汇总在一个表中便形成总进路表数据结构。总进路表简单明了，易于学习，当站场股道、道岔不多、结构简单时，总进路表并不复杂，但当站场庞大，总进路就会剧增，尤其当站场改建或扩建时，总进路完全就需要重新编制，因此进路表数据结构不适应于较大的车站和车站的改建[5]。

1.2 二叉树型数据结构

二叉树采用多重链表结构，是非线性数据结构的一种。其节点由一个数据元素和左右两个分支子树构成，形成链表结构。站场中信号点间的连接关系又不完全具有二叉树的特点，故二叉树型数据结构不能很好地应用于站场。

1.3 站场型数据结构

站场型数据结构就是根据站场信号布置平面图，把各信号点数据模块按照其在信号平面布置图中的位置链接构成，其本质是节点的链接表。具有以下优点：

（1）在数据结构中的任何地方增加或删除节点，只需修改节点指针域中的地址，不影响节点的物理地址，方便站场改建或扩建时联锁数据的修改；

（2）节点的链接只是在逻辑上有序的，与节点在存储器中的实际物理地址无关，这种数据结构可以用计算机辅助设计自动生成；

（3）基于根据进路办理命令的数据结构生成的进路表存在于RAM中，进路表随着进路办理而建立，随着进路解除而删除，占用RAM空间小；同时该静态数据库占用ROM空间小，有利于检测。

2 进路搜索算法研究

进路搜索算法是调度集中和计算机联锁系统软件的重要部分，该软件研究的重点内容是如何准确高效搜索出符合操作意图的进路，即通过始终端按钮选出一条基本进路（当列车进路的同一个始端和同一个终端存在两条或两条以上进路时，一般把对平行作业影响小、走行距离短、经过道岔少的进路定为基本进路，其余进路定为变更进路[6]）而非变更进路或迂回进路，若要选出变更进路，则需另加按钮条件，指明变更点。

本文采用的站场平面布置图如图2所示，本站场下行接车口有两个方向：东郊方向和北京方向，防护接车进路的信号机分别为XD和X，股道端有出站信号机SⅡ、SⅢ、S4和S5，咽喉区有调车D1至D17共9架信号机。数字代表道岔，如1/3号道岔。道岔区段轨道电路名称在图中不标注，如1/3号道岔区段默认名称为1-3DG；无岔区段在图中标注，如IAG，1/19WG。现以该站场平面布置图介绍进路搜索算法。

2.1 广度优先搜索策略

广度优先搜索策略基于树的层次遍历方法，搜索过程从始端节点出发，按照站场的层次结构逐层搜索目标节点，当在该层搜索不到目标节点时转向下层继续搜索，直到搜索到目标节点为止，例如搜索D11至4G的调车进路，将会搜索到S5、SⅢ、D17、SⅡ后才能搜索到S4。这种搜索方法方向不确定，当目标节点在站场较深层时搜索量将会相当巨大，搜索过程中会有大量节点数据的入栈和出栈，造成搜索效率低下。

2.2 深度优先搜索策略

深度优先搜索和广度优先搜索策略相反，其类似于树的先序遍历的过程。深度优先搜索算法会选择一条路径搜索到这条路径的尽头节点，当搜索不到目标节点时再逐层退回搜索，直到搜索到目标节点为止。这种搜索算法相对于广度搜索方法搜索路径较为明确，但这种算法会选择一条路径走到底，即不管通过这条路径能否找到目标节点都要进行试探，因此，当目标节点在较浅层时也会造成找不到目标节点而需一步步回溯搜索的缺陷，不利于搜索效率的提高，不是一种理想的搜索算法。

2.3 高度搜索策略

本文采用基于站场形数据结构的高度搜索算法。高度搜索策略的基本思想是：基于站场形数据结构，对站场中每个设备节点按实际纵向位置定义高度，按其实际横向位置定义编号，这样在站场中处于同一线上的设备就有相同的高度[7]，然后根据始终端节点横向编号和纵向高度确定搜索方向和路径。图2站场的各设备节点纵向高度分布如表1所示。

表1 设备节点高度分布表

3 进路搜索过程实现

3.1 进路搜索规则

图3 站场形数据结构

图2所示站场的站场形数据结构如图3所示，其中，K表示设备节点的数据模块，例如XD数据模块表示为K(XD)。进路搜索时，首先根据进路操作命令找出进路的始端模块和终端模块，确定搜索方向，依据站场形数据结构沿着进路搜索方向找出与进路相关的所有模块。当遇到分支模块(对向道岔)时，比较分支模块与终端模块的高度，若高度一致，沿直股搜索；若高度不一致，则沿弯股搜索。例如办理SⅢ至D7的调车进路，确定从进路始端向终端搜索，始端模块是K(SⅢ)，终端模块是K(D7)。由始端模块出发找到K(25DG)、K(25)模块，因K(25)模块为分支模块，通过比较K(25)和K(D7)的高度，确定沿弯股搜索，依次找到K(23)、K(17)、K(17-23DG)、K(D13)、K(9)、K(9-15DG)和K(15)，K(15)也是分支模块，因其与终端模块K(D7)具有相同高度，故沿直股搜索找到K(D9)，最终找到终端模块K(D7)。进路搜索程序从这些模块中提取进路联锁程序所需的数据，并生成一个进路表，就完成了进路搜索任务。

3.2 基本进路搜索过程

当进路的始端模块和终端模块高度不一致时，此种进路搜索方法总是沿着遇到的第1个对向道岔形成的渡线向前搜索或者朝能缩小与终端模块高度差的后继模块向前搜索。北京方向X进站信号机至IIIG接车有3条进路：经5/7道岔反位、9/11、13/15、21、23/25道岔定位；经9/11反位、5/7、1/3、13/15、21、23/25定位；经23/25反位、5/7、1/3、9/11、13/15、17/19定位，其中，第1条、第2条为变更进路，第3条为基本进路。按照上述搜索规则，在选基本进路时按压进路始终端按钮后就会搜出模块K(X)、K(IAG)、K(D3)、K(5DG)、K(5)，因K(5)是第1个遇到的对向道岔，且与终端模块K(SⅢ)高度不一致，则沿弯股搜索到K(7)、K(7DG)……K(13)，K(13)也是对向道岔，但其与终端模块高度一致，故沿直股搜索到K(21DG)……，最终找到终端模块K(SⅢ)。这时选出的是一条变更进路，不满足选基本进路时不能选出变更进路的运营要求。为了解决此问题，我们可以在对向道岔K(5)和K(9)模块中加上“直股优先搜索”的导向标志，此时X至IIIG的接车进路搜索路径就变成了K(X)、K(IAG)、K(D3)、K(5DG)、K(5)、K(3)……K(9)……K(23)，K(23)无导向标志且与终端模块K(SⅢ)高度不一致，则沿弯股搜索到K(25)、K(25DG)、K(SⅢ),从而选出基本进路。若采用深度优先搜索算法，X至IIIG的进路则在搜索到K(25)时会沿直股搜索到K(D17)，该终端节点不是目标节点，则需回溯到K(25)沿弯股搜索才能找到目标节点K(SⅢ)。若采用广度优先搜索算法，在搜索到K(17)时会首先沿弯股搜索K(19)，一直搜索下去直到搜索不到目标节点时才逐步退回，搜索工作量更加巨大。

3.3 变更进路搜索过程

对于变更进路采用从始端模块至变更模块、变更模块至终端模块进行分段搜索，搜索方法同基本进路。例如对于上述接车进路要选出经由5/7反位的变更进路，现以K(D11)充当变更模块，因K(5)和K(9)已有直股优先的导向标志，故进路搜索路径为K(X)……K(5)、K(3)……K(9)、K(D13)……K(23)、K(25)……K(SⅢ)，从始端模块K(X)开始未找到变更模块K(D11)。对于这种由于导向标志而导致找不到目标模块的情况，采用从终端向始端反向搜索的办法。此时搜索路径为K(SⅢ)……K(25)，K(25)与目标模块即变更模块K(D11)同高度，沿直股搜索找到K(21DG)……K(11)，K(11)同样与K(D11)同高度，沿直股找到K(D11)，即变更模块找到。再从此变更模块开始寻找下一目标模块即始端模块K(X)，搜索路径为K(D11)……K(7)、K(5)……K(X)，最后一个目标模块找到，从而选出了变更进路，进路搜索成功。同理，D3至D11的调车进路也需反向搜索，搜索路径为K(D11)……K(7)、K(5)……K(D3)。对于变更进路，广度搜索算法和深度搜索算法搜索过程如同对基本进路的搜索，因搜索方向不确定也会造成回溯搜索，降低搜索效率。

3.4 进路搜索流程

进路搜索的流程如图4所示。

图4 进路搜索流程图

4 结束语

采用站场型数据结构的联锁软件摆脱了总进路表数据结构联锁软件在站场改建和扩建时需大量修改总进路表的困扰。基于该数据结构的高度搜索算法，搜索目标明确，搜索方向确定，有效克服了广度搜索算法逐层搜索和深度搜索算法回溯搜索导致的搜索量大、搜索效率低的缺点。通过C语言编程实现并验证，该算法搜索路径准确，能有效提高联锁软件的进路搜索效率，优越性显著，具有重要的现实意义和应用价值。

[1]赵志熙.计算机联锁系统技术[M].北京：中国铁道出版社，2008.

[2]占自才，徐雪松.进路搜索的数据结构与算法及其仿真[J].铁路运输与经济，2005，27（9）：73-74.

[3]文武臣,王晓明.计算机联锁的数据结构及进路搜索算法[J].重庆工学院学报：自然科学版，2008（6）：51-52.

[4]Michael T.Goodrich,Roberto Tamassia and Nikos Triandopoulos.Efficient authenticated data structures for graph connectivity and geometric search problems[J].Springer science business media.2011,60(3):505-552.

[5]陈志颖，董 昱，杨 柳，等.计算机联锁进路搜索算法的分析与研究[J].铁道通信信号，2007，43（4）：4-5.

[6]王瑞峰.铁路信号运营基础[M].北京：中国铁道出版社，2008.

[7]王文波，米根锁，岳丽丽.全电子联锁软件设计与进路搜索算法优化[J].微计算机信息，2012，28（11）：234-236.

责任编辑 王 浩

Route Search Algorithm for Computer Interlocking System of railway station

WANG Wenbo1,MA Xuexia2
( 1.United Science &Technology Co.Ltd.,Hangzhou 310052,China;2.CASCO Signal Ltd.,Shanghai 200071,China)

Data structures selection and Route Search Algorithm are two key technologies of computer interlocking software.Because the common data structure constraints to interlocking software,and route search algorithm affects search effciency,this paper optimized the Route Search Algorithm based on station type data structures,used the example of yard as the object to discuss the researching course for basic route and alternate route by using Height Search Algorithm in detailed,which showed that the Height Search Algorithm overcame shortcomings of Breadth and Depth Priority Algorithm,the search goal was specifc and the search course was high-effciency and accurate.

Route Search Algorithm;data structures;computer interlocking

U284.362：TP39

A

1005-8451（2016）04-0063-04

2015-09-24

南京铁道职业技术学院青年基金科研项目（YQ1403）。

王文波，助教；马学霞，助理工程师。