基于拓扑图论策略的城市轨道交通信号设备布置方法研究

万 霞，王长林

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

近年来，伴随着我国城市化进程的加快以及经济的高速发展，城市人口快速增长，城市规模日益扩大，许多大城市的地面交通己经无法适应日益增长的客运需求。由于城市轨道交通系统具有快速、便捷、大运量的特点，因此许多城市己经确定了以轨道交通作为公共交通骨干的战略。

城市轨道交通信号项目实施过程中，由于信号设备量大，程序繁琐，大大降低了进度。因此，设计具有针对性的信号设备应用模型在城市轨道交通中起着非常重要的作用，直接影响着工程的效率。

本文通过分析和研究各个信号设备之间的关系，并结合拓扑图论的相关策略，建立城市轨道交通信号设备基础线路数据的拓扑结构，方便后续拓展应用功能的开发和研究。

1 图论拓扑结构

图论通过将具体事物抽象成图形的形式来描述具有某种关系的系统，并根据图的性质进行分析，提供研究各种系统的巧妙方法。本文采用矢量图形拓扑结构组织信号设备和线路数据信息，如图1所示，使图元数据的层次性更强，对图元的操作也变得容易很多。

在解图论问题的算法中，经常需要从图的某一点出发，系统访问图的其余顶点，且使每一个顶点最多被访问一次，这一过程称为图的搜索。图的搜索是人工智能中一种重要而且有力的解决问题的方法。最典型的图搜索方法有3种[3]。包括：宽度优先搜索，深度优先搜索，启发式搜索。

2 城市轨道交通信号设备应用模型

2.1 图元化处理

图元化处理是将现实存在的需要处理的事物，抽象成具有某些特殊属性的图元来表示和处理。

此处以信号机为例说明。信号机是指引列车在线路上运行的主要信号设备，机车上的司机根据信号机的不同显示来决定列车是否可以前行、前行的速度级别。将信号机实体用函数对象来进行定义和实现，在城市轨道交通中信号机分为单显示信号机、三显示信号机和虚拟信号机共3种类型。其图元化处理后的图形表示图如图2所示。

图2 信号机图元化处理

图元化处理不仅仅是完成了各种信号设备的图元表示，还包括对各种图形设备的快速创建、复制、粘贴、删除等基本的操作功能。

2.2 基于矢量图形拓扑结构的信息数据模型

结合图论和拓扑结构理论，本文采用的信息数据模型是根据地铁站场平面特性，将地理信息系统（GIS—Geographic Information System）数据模型进行平面化处理，构建地铁信号设备系统的信息数据模型。

本文根据车站站场图将各个常量模块联结起来就形成了站场形数据结构图。本文测试站段线路数据结构图如图3所示。

图3 线路信息数据结构图

图3中的数据模块为节点，节点与节点之间的联结为链接。以K(n)作为节点的代号，其中 是相应监控对象的名称。之后添加的信号设备对象都会依附在这些节点上，再增加一个位置偏移量来区别相对位置和关系，这样形成一个完整的信息系统。

因此，构建的线路数据拓扑结构主要包括：轨道区段信息、道岔区段信息和它们的连接关系。其中，轨道区段信息和道岔区段信息是用节点来表示的，它们的连接关系是用线来表示的，线路信息数据结构本质上是节点的链接表，如图4所示。

图4 数据模块的链接图

根据节点链接图就可以生成站场形数据结构。每个节点所占区域划分成数据场df和指针场 pf两部分。数据场存放该节点的常量，指针场存放相邻节点首地址。指针场定义了两个指针sp和xp，sp表示上行方向上该节点的后辈节点首地址，xp表示下行方向上该节点的后辈节点首地址，当没有邻节点时即没有后辈节点的节点，则在相应的指针场中记入“0”。对于道岔节点来说，有3个指针场：

（1）岔前指针场，用来存放岔前邻节点的首地址；

（2）岔后直股指针场，用来存放岔后直股邻节点的首地址；

（3）岔后弯股指针场，用来存放岔后弯股邻节点的首地址。

2.3 基于拓扑图论搜索的设备布置模型

根据拓扑图论的思想，将信号设备数据结构与线路拓扑数据关联。将信号设备数据放到线路拓扑数据结构中，在节点数据中包含道岔，在边数据结构中包含信号机、计轴、应答器等。基于拓扑图论搜索的设备布置模型是城市轨道交通信号设备应用模型的核心，模型结构图如图5所示。

图5 基于拓扑图论搜索的设备布置模型

2.3.1 基于矢量拓扑结构的遍历搜索

根据信号设备布置模型的要求，需查找到布置设备约束条件中的特定信号设备。为了解决这个问题，在图论的算法中选择了图的搜索算法。

在一个图G中搜索算法的基本思路：从一个顶点v1开始，给它一个“标记”，N(v1)。然后给v1的邻点标记，再给它的邻点的邻点标记，如此等等。最典型的搜索方法有3种，即深度优先搜索（DFS）、广度优先搜索（BFS）和启发式搜索（HS）。

根据之前建立的信息数据拓扑结构，本文结合了广度优先搜索BFS和启发式搜索HS来设计搜索算法，基本思想是：从v0开始，依次访问v0的所有邻点v1，v2，…，vl，然后依次访问与v1邻接的所有顶点，已经访问过的顶点不再访问，依次继续搜索，直到所有的顶点都被访问为止[1]；当搜索到某个节点时，进行条件布置判断，若成立，则搜索周围的设备，再进一步进行条件判断。

本文采用的搜索算法步骤如下：

由线路数据拓扑结构信息得到数据结构图G每个顶点对象的邻接表L(v)，建立一个先进先出的表（队列）Q：

（1）T←φ，对所有的点 v∈V，N(v)←0 ，Q ← 0 ，i← 0 ，N(v)← 1 。

（2）对L(v)的每个顶点u，如都有N(u) ≠0。则转(4)，否则转下一步。

（3）L(v)中存在顶点u，使N(u)←0，则T←T∪{v, u}，Q←Q∪{ u}，i←i+1，N(u)←i=n–1，转 (2)。

（4）若i+1或Q为空，停止，否则从Q中取排头元素u，在Q中删除u，v←u，转(2)。

算法中，N(v)表示v的标号，即v被访问的顺序号。T表示输出的图。

当T中得到访问点时，再进行启发式搜索（HS）判断是否满足信号设备布置原则，若满足则插入新设备对象到信息数据库中。

2.3.2 信号设备布置原理分析

信号设备布置原理分析是模型的重要部分，也是工作量最大的部分。在此部分将对需要布置的全部信号设备逐个进行条件分析，然后确定是否满足布置的要求。以信号机为例简要说明布置原理分析。

信号机的布置与停车点、计轴、道岔、车挡和防护门等因素相关联。实际应用时信号机的布置需遵循设备数量最少化原则。信号机布置规则简表如表1所示。

表1 信号机布置实现

2.4 基于图搜索的进路生成模型

在矢量拓扑理论的基础上可以拓展更多的应用，如完成更多设备的自动布置功能、联锁进路表的生成功能、仿真实现功能等。以进路表的生成为例说明拓展应用的开发和研究的方便性。

此模型的核心是进路搜索模块，进路搜索算法流程图如图6所示。

进路搜索模块的其任务是根据进路表名称从站场形数据结构中选出与该进路有关的节点及确定进路中各道岔应处的位置，然后将各节点的数据及道岔位置信息构成该进路的“暂态进路（数据）表”，作为后续联锁程序使用。

图6 进路搜索算法流程图

3 模型仿真与验证

案例采用某实际地铁站的信息，在Visual 2010仿真平台上，对以上所建的城市轨道交通信号设备应用模型进行仿真和验证。软件实现过程中，编程完成的主要工作如表2所示。

案例中，根据拓扑图论的理论思想，为了反映对象之间的关系，首先对地铁站所涉及的研究对象进行图元化处理，实现了轨道区段、道岔、信号机、计轴等研究对象的定义，并完善了这些对象的操作功能。

在基于拓扑结构的信息数据模型的基础上，就可以按照规定的形式建立和完善地铁站线路基本信息。信息输入的方法可以分为2种：

表2 编程实现功能表

（1）根据界面的图元快捷工具，绘制线路基础数据信息；

（2）按照规定的形式将线路基础数据信息写成txt文件，系统将根据文件信息自动绘制线路基础站场信息。

3.1 基于拓扑图论搜索的信号设备布置

案例中要完成主要信号设备布置，首先需按照设定的格式输入一些必要信息，如根据属性框提示输入道岔属性信息如图7所示。

图7 编辑道岔属性框图

根据信息数据模型相关处理后，完成基于拓扑图论搜索的设备布置，其仿真结果图如图8所示。

图8 信号设备布置结果图

分析仿真结果可知，通过此模型有效的实现了主要信号设备如信号机、计轴、应答器等的自动布置。布置结果和工程中手动设计的布置图误差很小，且通过系统可以手动来调整这些特殊情况下的设备布置。由此可见，采用图论和拓扑结构处理数据后，可以在较短的时间内，较容易的实现复杂的信号设备布置关系。

3.2 进路信息Excel表生成

将城市轨道交通信息数据通过图元化处理，以模块的形式进行操作，再将各个模块之间的关系采用拓扑结构组织，建立信息模型后，便于进行多种功能的扩展，如进路表。生成进路信息Excel表时，需要完善信号机的属性，如图9所示。

完善各个信号机的属性后，经过基于图搜索的进路生成模型，自动生成进路信息Excel表的仿真结果如图10所示。

图9 完善信号机属性图

图10 进路信息Excel表图

进路信息Excel表列举了所有进路，并明确的反映了每一条进路所对应的设备的具体状态。查看进路信息Excel表可知，由于城市轨道交通和大铁站点的区别，使得进路信息Excel表与以往大铁联锁表的表示方法具有很大区别。模型生成的进路信息Excel表更能明确的反映地铁中重要的联锁逻辑关系。

4 结束语

本文通过对各个信号设备的研究，将拓扑图论的相关策略运用到信号设备布置模型中，在较短的时间内实现了信号设备布置和进路信息Excel表生成，有效的减轻了信号项目实施者的工作强度。通过对实际地铁站的仿真和验证，说明了模型的可行性。因此基于图论拓扑结构的城市轨道交通信号设备应用模型可以大大降低人力成本，提高工程的实施效率，模型具有一定的应用价值。

[1]龚 劬.图论与网络最优化算法[M].重庆：重庆大学出版社，2009：18-30.

[2]陆小红．铁路信号微机联锁仿真系统设计[D].成都：西南交通大学，2010.

[3]左淑利，吴芳美.基于图搜索策略的车站运行仿真命令集的自动生成算法[J].上海铁道大学学报．1999，20（2）.