基于二维坐标信息进路搜索算法研究

谢 林，杨 扬

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

基于二维坐标信息进路搜索算法研究

谢 林，杨 扬

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

二维坐标信息进路搜索算法，运用CAD提取各个节点坐标的思路，从有向图的角度对进路进行研究，通过面向对象的思想将各个节点连接起来形成站场型数据结构，以此为基础设计出一套通用进路搜索程序，能够快速高效地搜到目标节点，提高进路搜索效率。

坐标；CAD；有向图；面向对象

随着铁路运输的快速发展，计算机联锁技术已广泛运用于车站信号控制领域。其主要功能是处理进路内的道岔、信号机和轨道电路之间的安全联锁关系，在保证安全的前提下提高运输效率。

进路搜索是计算机联锁的核心部分，搜索时间的长短直接影响了进路控制的正确性、安全性和高效性。目前运用广泛的进路搜索算法主要有采用带导向标志和优先策略的传统搜路法，改进的深度优先、广度优先搜索和Dijkstra 算法，以及相关理论研究采用二叉树遍历进行搜索[1]，实验证明，上述搜索算法在功能上基本能满足要求，但是搜索的时间冗余度太大，多数情况下会遍历所有分支，程序执行时间较长。本文在分析铁路车站信号特性的基础上，利用CAD2013对车站进行建模，并设计程序提取各个节点的坐标信息，利用面向对象思想连接信号设备，形成静态数据库。在前期准备的基础上，提出基于坐标信息的进路搜索算法，把其应用到实际搜索过程中，能够全面高效地完成进路的搜索。

1 站场型数据结构建模

利用站场型数据结构，在办理一条进路时，根据下发的进路操作命令，如果符合操作要求，便为进路搜索程序指明进路的始端模块首址和终端模块的首址，立即启动进路搜索程序，从站场型数据结构中搜出与进路有关的全部模块，再从模块中找出进路联锁程序所需的数据，就可以构成进路表[2]。图1为某铁路车站局部信号平面布置图，可以看出，铁路车站站场是由多个信号设备按照一定的顺序链接起来。在实际建模过程中，对应每一个信号、道岔、区段设计一个静态数据库，按照6502电气集中组合排列中顺序构建相邻各个模块之间的连接关系，将图1中相邻的模块进行连接，形成相应的站场型数据结构。结果如图2所示。

为了能将各个模块链接起来，方便进路搜索程序进行搜索，将每个模块空间进行扩展，分成数据场和指针场两部分，用数据场存放相应的数据，指针场存放该模块的首地址，利用双向链表将各个模块链接起来[3]。对于区段和信号机，只涉及到两个搜索方向(假设从左往右搜索为正方向)，一般设置两个指针场，前向节点prev和后项节点next，对于道岔区段，它有3个链接节点，为了方便形成双向链表，并在搜索时不会出现死循环，需设4个指针场，岔前节点prev，岔后节点next和正向搜索弯股节点pfz和反向搜索弯股节点pfw。连接结果如图3和图4所示。其中，实线箭头表示正方向连接，虚线箭头表示反方向连接，当指针没有连接对象时指向NULL。

图1 某铁路车站局部信号平面布置图

图2 站场型数据结构图

如果在站场图中有超限绝缘区段，必须检查超限绝缘。对于交叉渡线，按照6502的设计理念，当一组道岔动作在反位时必须将另一组道岔防护在正位，因此在连接过程中将两个道岔组合的位置换过来，可以防止在搜索过程中漏掉需要防护道岔对应的轨道区段。

站场模型建好以后需要用CAD对各个节点的坐标信息进行提取，以便完成静态数据库。为了方便节点坐标的存储，设计一段简单的LISP程序语言，自动地将提取的坐标信息保存在Excel表格中。

图3 各模块之间的连接关系（下接图4）

图4 各模块之间的连接关系（上接图3）

2 进路搜索算法设计

2.1 进路搜索目标及任务

一条进路是由若干个信号机、道岔、轨道区段组成的列车在车站内运行时所经过的路径。进路的始终端是由始端按钮和终端按钮决定，一条完整的进路必须搜索出进路上所有有关的信息，包括进路类型、进路方向、经过的道岔、占用的轨道区段、敌对信号机和防护信号机。根据按下的始终端按钮，判断按钮是否能配对，形成有效的输入，然后根据输入进行搜索。

2.2 搜索策略分析

输入正确的始终端信息后，理论上可以形成多条搜索路径，如何少走分支，快速有效地找到最佳的搜索路径是问题研究的关键。其中最主要的影响因素取决于道岔节点，在搜索过程中遇到对向道岔，将会出现两个搜索方向，如果能快速地确定搜索方向就会在很大程度上节省程序执行时间，提高运行效率。

2.3 搜索策略设计

车站信号平面布置图主要反映了站场线路的布置，接发车的方向和主要信号设备的名称与位置。可以将道岔和信号机节点抽象为图的顶点，那么轨道区段就成为连接这些顶点的边，因此整个站场图就可以抽象成一幅有方向的平面图。在定义静态数据结构时，在数据场里定义一个点类的成员变量，用来记录当前节点在站场的二维坐标信息，那么对于特定的一条进路，根据按下的始终端按钮对应的坐标信息就可以形成一个有向线段，唯一确定一个搜索方向。避免了不必要的分支搜索，节省程序执行时间。

设vi为一条进路的始端节点，对应的坐标为（xi, yi），目标节点为vj，对应的坐标为（xi, yi），vk为若干中间节点，对应的坐标为（xk, yk）。首先判断xi和yi的大小，确定搜索方向，若xi＜yi，则为正向搜索，若 xi＞yi为反向搜索。当遇到道岔时（此时xk为道岔），判断该道岔是顺向道岔还是对向道岔，若为顺向道岔，搜索方向不变，直股搜索。若为对向道岔，比较yk与yj的大小，同时为了避免搜出八字迂回进路，若yk＞yj并且道岔为捺型道岔，或者yk＜yj并且道岔为撇型道岔，弯股搜索，其余情况搜索方向不变都为直股搜索。搜索流程如图5所示。

图5 二维坐标信息算法搜索流程图

特殊情况下：

（1）如果要选择变通进路，根据要求必须指明变更点，因此可以将变通进路分解成两步来搜索。

（2）对于有通过进路的车站，如果要用一次办理的方法（按下通过按钮，再按下始端按钮）办理通过进路，根据两个按钮的坐标信息，在程序内部自动转换成分段办理的操作方法由远及近的排出发车进路和接车进路。以图2的站场型模型为例：

（1）当排列一条S3到4G的接车进路时，根据始端按钮LAS3和终端按钮LAX4的坐标信息，可以唯一地确定一条搜索路径。

（2）排列一条SLII到X10的通过进路，自动转换成由SLII-XII的接车进路和从SII-X10的发车进路。

（3）2G占用时，排列SI到D2的变通进路，指明变更点为D6或者X10，搜索过程可以分解成两步来处理。如图6所示。

图6 不同情形下的搜索策略

2.4 算法性能分析

传统的搜索策略中主要运用深度或者广度优先搜索方法对节点进行遍历，为了减少搜索次数需要对某些道岔设置导向标志，一次搜索到达死节点时需要返回上一次搜索到的道岔位置，重新进行搜索。因此需要不停地记录前一道岔的位置。这种思想在一定程度上可以避免多余分支的搜索，但是仍然不可避免地浪费许多不必要的搜索时间，节点存储情况复杂，而且需要设置很多中间变量记录道岔位置，程序设计相对复杂。与之相比较，基于二维坐标信息的搜索算法在时间冗余度和程序设计的简便性上有很大的提高。

2.4.1 时效性高

传统的搜索算法不可避免地要经过很多分支，以图1站场为例，排列由SLII到4G的一条接车进路，此时vi为SLII的节点，vj为S4的节点，传统的搜索方法至少要搜索3次，由SLII到SI，SII或者SII， S3,最后才到S4，显然搜索时间很长，而基于二维坐标信息的进路搜索算法根据始端节点和目标节点的位置以及道岔的类型，可以直接确定遇到道岔时搜索直股还是弯股，一次性搜到目标节点，时效性非常高。

2.4.2 程序设计简单

基于二维坐标信息的进路搜索程序可以一次性搜到目标节点，不需要设置大量的中间变量来记录道岔位置，同时它几乎不会出现搜到死节点的情况，因此可以对搜索到的节点类型直接进行压栈操作，形成进路表，而传统的搜索程序会出现搜到死节点的情况，何时才能进行节点的压栈操作需要额外的写附加程序进行判断，程序设计相对复杂。

3 结束语

二维坐标信息的进路搜索算法时效性较高，极大地节省了程序搜索时间，能够有效地避免搜到死节点，使程序一次性搜到目标节点，得到需要的进路信息，对其进行压栈操作。由于程序设计的通用性，通过接口，以vs2010为开发平台，为后期研究车站联锁表自动生成有很好的指导意义。

[1]梁艺凡，谭 丽，冯 挺.A*进路搜索算法的研究与实现[J].铁道标准设计，2013（2）.

[2]胡 媛，魏宗寿.采用DFS策略的进路搜索算法研究[J].铁路计算机应用，2007，16（9）：4-6.

[3]杨 扬.车站信号控制系统[M].成都：西南交通大学出版社，2012.

[4]Oytun Eris,Ilhan Mutlu.Design of Signal Control Structures Using Formal Methods for Railway Interlocking Systems[C].11th International Conference on Control, Automation, Robotics and Vision，2010.

责任编辑 方 圆

Two-dimensional coordinate information based Route Searching Algorithm

XIE Lin, YANG Yang
( School of Information Science Technology, Southwest Jiaotong University, Chengdu 611756, China )

The two-dimensional coordinate information of the Route Searching Algorithm could be used to extract the coordinates of each node with CAD, study the route from the angle of directed graph, connect various nodes to form a data structure of station type through the object-oriented thought, on this basis, design a set of general route search procedure, which was able to search to the target node highly effective, and greatly improve the eff i ciency of route searching.

coordinate; CAD; directed graph; object-oriented

U29∶TP39

A

1005-8451（2015）08-0016-04

2014-12-16

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

谢 林，在读硕士研究生；杨 扬，副教授。