一种基于图和邻接表的站场图模型设计方法

贾积禹，崔佳诺

（1．北京全路通信信号研究设计院集团有限公司，北京 100070；2．北京市高速铁路运行控制系统工程技术研究中心，北京 100070）

1 概述

计算机联锁系统中参与联锁逻辑运算的数据包括静态数据和动态数据两大类，对应了静态数据结构和动态数据结构，数据结构的类型不仅影响联锁程序的结构，还直接关系到联锁逻辑运算的复杂度、运算时间等系统参数。目前，静态数据主要采用联锁表的数据结构进行存储，联锁表的数据结构中，主要描述了进路与对象（道岔、信号机、区段）之间的关系[1]。

随着社会不断发展，既有铁路车站的改造和升级必不可少，当新增需求与信号设备在站场中的位置相关时，通常有以下两种方式进行处理。其一，是对静态数据结构进行修改，更新既有联锁表数据结构，在联锁表中增加新需求所需的设备信息或信号设备之间的制约关系，联锁表数据结构的频繁更新，会导致数据配置容易出错[2]，增加程序的存储空间；其二，在计算机联锁软件的核心逻辑中，根据进路与信号设备之间的制约关系进行逻辑判断来获取指定信号设备的相关信息，通过复杂逻辑判断间接获取车站内指定信号设备的信息，存在一定的安全风险。

本文针对上述两种方法的不足，在既有联锁表的基础上，提出一种用于计算机联锁逻辑运算的站场图模型设计方法，该站场图模型存储了站场的信号设备信息及其之间的连接关系。通过站场图模型获取计算机联锁逻辑运算所需的信号设备信息，可以避免联锁表数据结构的频繁更新，提高联锁系统的可靠性；同时信号设备信息采用站场拓扑图直接获取的方式，无需进行逻辑判断获取信号设备信息，提高联锁系统的安全性。

2 站场图模型的选择

铁路车站站场图模型是以图的方式描述站场中信号设备之间的关系，图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。目前在国内外车站站场图模型的研究中，无向图模型有功能点模型、承载点模型，有向图模型有道岔组顶点模型、轨道顶点模型、进路冲突模型等，研究人员根据需求选择不同的站场图模型进行建模，以实现预期目标[3-4]。

功能点模型将道岔、渡线交点、绝缘节、站线等具有特定功能的点抽象为顶点建立铁路车站站场图，能对站场中信号设备信息及连接关系进行表示；承载点模型[5-6]将不同属性的设备抽象并定义为衔接点，衔接不同属性线路的衔接点与衔接点之间线路抽象为承载点而构建的模型，有利于记录不同属性设备之间的联系；道岔组顶点模型[7]将必然同时使用的道岔分为一组，简化计算，有利于计算车站咽喉通过能力；轨道顶点模型的权值赋值机制可以有效的避免迂回进路，同时保证尽量使用平行进路；进路冲突模型描述进路之间的冲突关系，可以方便计算进路之间的冲突程度，但缺乏对具体道岔、线路设备的描述。

为了描述铁路车站站场中具有特定功能的设备，并获取信号设备的相关信息，故选取无向图模型中的功能点模型作为铁路车站站场图建模方法，将绝缘节、道岔中心点作为图的顶点，将连接两个顶点之间的轨道作为顶点之间的边，功能点模型的站场图模型可表示为G(V,E)，其中V为站场中功能点的集合，定义为V={vi|i=0,1,…,Nv},顶点包含了站场图中的绝缘节和道岔中心点；E为功能点模型中顶点之间的边的集合，定义为E={eij|i,j=0,1,…,Nv}。

本文以图1所示为例，站场由区段、道岔、信号机、绝缘节组成，其中，信号机依附于绝缘节设置，道岔中心点使用数字表示，绝缘节使用“J”进行标识。

图1 信号平面布置Fig.1 Signal layout

根据上述方法，采用功能点模型，按照图1所示的信号设备及其之间的联系，建立站场图模型结构，如图2所示。

图2 站场型结构Fig.2 Structure of station/yard model

其中，绝缘节和道岔作为站场型数据结构中的顶点，顶点之间的轨道区段作为边。当顶点类型为绝缘节类型时，只能与两个顶点进行连接；当顶点类型为道岔类型时，必须有3个顶点与其连接。

3 站场图模型的数据结构

站场图模型与图的结构类似，属于图论模型[8]，图的各顶点之间通常存在多对多的关系。图形结构在计算机中可以使用邻接矩阵、邻接表、十字链表、邻接多重表、边集数组等进行表示，不同的存储结构有各自的优缺点和适用范围[9]。根据站场图模型的顶点和边之间的对应关系，是一个边稀疏的图形结构，为了减少存储空间的浪费，本设计采用了邻接表的存储结构对站场型数据进行存储。

邻接表存储结构由顶点数组和线性表组成。图形结构中的所有顶点采用一个一维数组存储，同时，在顶点数组中，每个数据元素还需存储指向第一个邻接点的指针，以便查找到该顶点的边信息。图中的每个顶点的所有邻接点构成一个线性表，采用单链表进行存储。

顶点数组中元素的数据结构包含：数据域(data)和链域(firstarc)，其中数据域用于存储当前顶点的名称或其他相关信息，链域用于指向链表中的第一个邻接点；线性表中数据元素的数据结构包含：邻接点域（adjvex）、数据域（info）、链域（nextarc），其中，邻接点域用于存储与顶点连接的点在图中的位置，数据域用于存储与边相关的信息，链域用于存储依附于当前顶点的下一条边。

根据邻接表的存储方式，将站场型结构图中的设备信息依次配置到顶点数组和邻接点数组中，如图3所示，顶点数组中的数据域（data）中存储了站场中绝缘节和道岔的相关信息，链域（firstarc）中存储了与绝缘节或道岔相连的第一条边的指针。由于站场型结构图中，每个顶点最多只能与3个顶点进行连接，线性表的结点最大数为3个。当绝缘节作为顶点时，线性表的结点数为1个或2个，当道岔作为顶点时，线性表的结点数为3个。

图3 站场图的邻接表结构Fig.3 Adjacency list structure of station/yard diagram

站场型的数据结构的数据连接方式与站场的平面布置图上特定功能点的连接方式是一一对应的，当站场的信号设备改变时，只需改变既有数据之间的连接方式，增加或减少顶点，很容易修改。

4 站场图模型的需求实现

需求举例：“列车进路满足信号开放条件时，联锁应先将进路内的调车信号机带动开放。”该需求实现过程中，应能查找列车进路内同向的调车信号机并对其进行控制。

既有联锁系统中，列车信号的开放无需将进路内的调车信号机带亮，在既有的联锁表数据结构中缺少进路内调车信号机的信息。以下对基于站场图模型实现新需求的方案进行详细说明。

通过对新需求的理解和分析，新需求的关键点是找到进路内同向的调车信号机。站场型数据结构已经存储了站场中的信号设备信息及其之间的连接关系，通过信号设备之间的连接关系和道岔相关信息即可查找到进路内的同向调车信号机。

为了能正确查找到站场中指定的信号设备信息，设计了邻接表中的顶点和邻接点，其数据结构如图4所示，顶点的数据域包含：设备名称、设备类型、设备索引、设备坐标；邻接点的数据域包含：区段名称、区段索引、区段方向、道岔开向。

图4 顶点和邻接点的数据域Fig.4 Data field for vertex and adjacent

联锁软件所处理的对象主要有3类：信号机、道岔、区段。站场中的信号机信息包含于绝缘节信号设备数据结构中，道岔信息包含于道岔设备数据结构中，区段信息包含于邻接点的数据结构中。绝缘节和道岔设备的数据结构如图5所示，其中绝缘节信号设备数据结构包含：绝缘节名称、绝缘节对应的信号机数量、信号机名称、信号机类型、信号机方向、区间口类型；道岔设备的数据结构包含：道岔名称、道岔类型。

图5 基础设备信息数据结构Fig.5 Infrastructure information data structure

通过顶点数据域中的设备索引，在基础设备信号表中即能查找到指定信号设备的信息。

顶点和邻接点的数据域中存储了信号设备的相关信息，根据这些信息以及信号设备的连接关系，可以简单、准确获取站场中特定的信号设备并对其进行控制。

查找进路内调车信号机的流程如图6所示，实现的功能为：通过进路代码在站场型数据结构中查询该进路内同向的调车信号机信息。

图6 查找进路内调车信号机流程Fig.6 Flow chart of locating the shunting signal within the route

进路内调车信号机的查询步骤如下。

第一步，通过进路联锁表获取该进路始终端信号机对应的绝缘节名称，即站场型结构图中顶点的名称。

第二步，在站场型结构图中遍历找到始端信号机对应绝缘节顶点，并记录该顶点的数据域和链域。

第三步，在站场图模型中，以始端信号机对应绝缘节顶点为起始点，结合进路内区段方向、区段内的道岔开向唯一确定进路内下一个邻接顶点。

第四步，根据邻接顶点设备信息，记录进路内同向的调车信号机信息。

第五步，若邻接顶点不是终端信号机对应绝缘节顶点，则重复第二步、第三步、第四步，继续查找；否则，结束查找。

通过执行上述步骤，可将进路内的同向调车信号机记录下来，并对记录的信号设备进行控制。采用站场图模型的方法，避免了更新联锁表数据结构，省去了数据配置的工作，同时也简化了联锁应用逻辑的复杂度。站场图模型存储了更全面的信号设备信息，能适应更多新的需求，提升联锁系统的鲁棒性。

5 结束语

站场图模型的设计及站场型数据结构的建立，能可靠、安全的查找到站场中特定的信号设备。可以避免联锁表数据结构的频繁更新，降低数据配置过程中出错的可能性，减少联锁表占用的存储空间，提高联锁系统的可靠性；同时也能避免复杂逻辑运算获取特定信号设备信息的异常情况发生，提升联锁系统的安全性。