计算机联锁系统进路表自动生成算法

陈 光，杨 扬

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

计算机联锁系统进路表自动生成算法

陈 光，杨 扬

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

简述了通过读取基础站场数据，对站场数据中的信号设备的属性和位置坐标进行分析，用一种方法将铁路信号设备进行位置关联，从而建立计算机联锁系统中的站场型数据结构。提出一种基于站场型数据结构的进路表自动生成算法，该算法是结合有向图的拓扑结构、二叉树、深度优先搜索的一种进路表自动生成算法。本文给出算法的完整描述。

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

随着铁路全面建设及逐步提速，计算机联锁系统角色越来越重要，正逐步取代继电器联锁系统，其主要功能是通过计算机控制并处理进路上的道岔、信号机、轨道电路之间的联锁关系。进路表是计算机联锁系统重要数据之一，排列着该站场的所有进路信息。目前，进路表多数是由人工编写审核，其工作量繁重而且容易造成人为错误，需多次审核才能达到实际工程要求。本文通过总结前人经验及成果，对进路表自动生成算法开展进一步探索。

1 信号设备位置关联并构造站场数据型结构

在设计之初所获得的站场基础数据来自于铁路CAD软件，该软件所生成的数据包括信号设备的类型、设备位置坐标、设备所独具的属性等。这些数据排列是无序的，并不是按照设备所在站场里从上咽喉到下咽喉的顺序排列，这种数据结构不利于进路搜索，由此，在进路搜索之前需确定信号设备左右位置关系并构造站场型数据结构。

1.1 确定信号设备位置关系

在站场中设备的位置关系主要有3种，分别是左侧相邻、右侧相邻、不相邻。 设备位置关系的确定需设备的关键位置坐标及结合一种关联方法，关键位置坐标如图1所示，具体方法主要分为以下几步：

（1）找出所有的道岔区段，一个道岔区段可能包含一个道岔，也可能包含多个道岔。

（2）在找出所有的道岔区段后，通过比对该道岔区段中道岔basepoint点的横坐标和纵坐标，以及道岔的开口属性，确定该道岔区段内道岔之间的位置关系，同时也能确定该道岔区段最左端、最右端的设备类型及ID。

（3）通过将调车信号机的basepoint坐标与道岔区段最左侧或最右侧的道岔设备的normalpoint、fromalpoint、reversepoint坐标进行比较，确定出信号机左侧相邻和右侧相邻的设备类型及ID。

图1 信号机、道岔、股道关键点坐标

（4）将列车兼调车信号机basepoint与股道的leftpoint、rightpoint坐标进行比对，从而完成所有设备位置关联。

通过上述步骤后，每个设备都找到了与其相邻的左右设备，并把相邻设备的类型及ID记录在该设备的属性中，因此，站场中所有设备通过这种形式间接地关联在一起。

1.2 站场型数据结构[1]

通过上节阐述的设备位置关联后，便可构造站场型数据结构。站场型数据结构是指数据块像站场一样格局进行联接，把信号设备比作一个信号结点的数据结构，如图2所示。

每个信号结点又由信号结点主要属性、左侧信号结点数据块、右侧信号结点数据块组成。信号结点属性主要存储着该设备的主要特征，例如：道岔属性存储着该道岔的名字、所属区段、开口方向等，而左右侧信号结点数据块主要存储着与该设备相邻的设备类型及ID。

对于道岔设备比较特殊，其信号结点除图3所示外，还需记录道岔反位所链接的设备类型及ID。

2 进路搜索算法

进路就是由起始信号机、终端信号机、若干个道岔及道岔位置、轨道区段组成的列车在车站内行车时所经过的通路[1]。

图2 信号平面图及站场型数据结构示例

图3 信号结点

以站场型数据结构为基础的进路搜索按照走迷宫的方式进行探索，以确定的入口去搜寻可能的对应的出口，以道岔的开口方向决定着该进路的搜索走向，根据入口信号点的类型决定着进路的终端类型，要求准确地搜索出各种类型的基本进路。进路搜索不重复、进路不遗漏是进路表自动生成算法的核心内容[2]。

下面进路搜索算法结合了图搜索、二叉树、栈结构，来处理进路搜索中的一些问题以及给出自动生成的进路表的格式规范。

2.1 二叉树结构与图搜索相结合

二叉树是树的一种，从图论的角度来说是一张连通的无环图，并且每一个顶点的度数不大于2，是一种非线性结构，二叉树的结点分为根节点和叶结点，二叉树的子树有左子树和右子树之分，并且二者顺序不可以颠倒[3]。

二叉树在计算机中的存储可以采用链式存储结构和队列存储结构，链式存储应用较为广泛，其节点由一个数据元素和分别指向其左、右子树的两个分支构成。

通过对比，站场型数据结构与二叉树数据结构的形状相似，因此，可以考虑通过二叉树的形式进行站场型数据结构模型的建立[4]，以图2为基础，所建立的模型如图4所示。

图4 二叉树建模图

二叉树的搜索可以采用图的搜索策略，图的搜索可分为广度优先搜索、深度优先搜索、启发式优先搜索，考虑到二叉树的结构特性以及进路选排的技术要求，采用深度优先搜索较为合理。

深度优先搜索是在一张无向图中的某一点发起搜索，下一次的访问路径不确定，一旦选中一条路径后便要穷尽该路径，找到结束的信号结点，如未找到则废弃此路径，返回路径的分叉点去搜索另一条可行路径。

在进路自动搜索的过程中，深度优先搜索的方向是由起始信号机防护的方向决定，一条进路的终端是根据起始信号机的属性，及终端是并置、差置、列车兼调车信号机等不同情况来确定，这在计算机联锁系统的进路选排要求中有着明确的规定，在搜索的过程中会遇到多个道岔，这里视每个道岔为深度优先搜索的路径分叉点，路径分叉点需一种方法特殊处理来辅助进路的搜索，同时在进路自动搜索的过程中也要遵循直股优先以及同类渡线优先的原则。例如：以D1为始端的基本进路搜索，当确定以D1为始端的时候，信号机防护的是1-DG道岔区段，所以进路搜索的方向为上咽喉到下咽喉方向，通过D1信号结点属性中存储的信息，可找到D1右侧相邻的信号结点类型及ID，依次类推，当遇到D3时，此路径终端已找到，完成此路径搜索并返回路径分叉点搜索另一路径，搜索到D5完成此次以D3为始端的进路搜索。

2.2 道岔结点的栈存储

道岔的处理是进路自动搜索的关键，道岔具有定位和反位两种状态，从而导致了搜索时始端信号确定后有多条搜索路径，也就是说道岔是搜索路径的分叉点，由于采取了深度优先搜索策略，需要一种方法来存储当一条进路搜索失败或者搜索结束时回退到哪一个分叉点，考虑到回退时应该从进路的后辈结点逐渐向起始结点回退，又由于栈有着后进先出的特点，所以采取栈结构存储道岔结点，如图5所示，辅助完成进路的搜索。

图5 道岔的栈结构存储

道岔又分为顺向道岔和对向道岔，在搜索的过程中，与搜索方向对向的道岔进入栈结构，顺向的道岔对路径不造成影响，则不入栈。

2.3 进路格式要求

进路搜索结束后，需要按照一定格式输出进路信息，便于计算机联锁主机读取和使用，在一条进路信息中，进路的始端终端要明确表达出，用符号‘＞’表示进路的方向，同时进路所经过的道岔要给出道岔的位置状态，如果道岔处于定位则用‘#1’来表示，如在反位则用‘#1^’这样的符号与道岔名字的组合来表示。如图2，D1到D3的进路表示如下：

D1＞D3 =[D1,D3] #1

3 算法实现

进路表自动生成算法已成功在计算机上实现，具体流程如图6所示。

图6 算法实现流程图

进路表自动生成软件是在Visual C++环境下实现的，通过读取基础站场数据文件SWJDATA.dat文件，最终生成进路表ROUT.txt，具体站场如图7所示。

4 结束语

在计算机上成功地验证了进路表自动生成算法，实现了进路表的自动生成，能够遍历出所有的基本进路，达到了不重复、不遗漏的设计要求。不足之处是对变更进路和长进路的处理不够完善，进路表自动生成算法还需要进一步研究和探讨。

图7 仿真站场

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

[2]覃崇乾，吴芳美.一种搜索与交互相结合的联锁表自动生成 算法[J].上海铁道大学学报，1999（12）.

[3]严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，2007.

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

[5]朱 怡.基于计算机联锁的进路表搜索生成系统的设计与实现[D].上海：上海交通大学，2012.

责任编辑 方 圆

Automatic Generating Algorithm for accessing table of Computer Interlocking System

CHEN Guang, YANG Yang
( School of Information Sciences and Technology, Southwest Jiaotong University, Chendu 610031, China )

The paper analyzed the attribute and position of signal equipment by reading the based date of the station, made the railway signal equipment be position correlation, thereby established a station-type data structure of Computer Interlocking System, put forward an Automatic Generating Algorithm for accessing table of Computer Interlocking System based on station-type data structure. The Algorithm was combined with topology map and binary tree. The description for the Algorithm was given in detail.

Computer Interlocking System; accessing table; data structure; algorithm

U284.37；TP311

A

1005-8451（2015）05-0005-04

2014-10-17

中国铁路总公司科技研究计划项目（2013X012-A-1，2103X012-A -2，2014X008-A）。

陈 光，在读硕士研究生；杨 扬，副教授。