基于A*搜索算法的城轨联锁系统仿真研究

张铭瑶 ，向美柱

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

计算机联锁系统是城市轨道交通控制系统的重要子系统，它控制着站场进路中信号机、道岔和轨道电路之间的安全关系，以确保行车安全。随着城市轨道交通控制系统的智能化发展，对联锁系统的要求越来越高，联锁软件中进路搜索方法和效率也成为重要的研究课题。现有的计算机联锁系统采用的进路搜索方法主要有进路表式搜索方法[1]、带导向标志的搜索方法[2]、深度优先搜索算法[3]、广度优先搜索算法[4]以及二叉树遍历[5]等，这些方法相对成熟，但搜索效率却不高。基于进路表的搜索方法由人工编制联锁表，工作繁复，容易出错；基于算法的进路搜索可以用于进路表自动生成工具，帮助自动生成进路表，再人工校对，从而提高进路表生成效率[6]。基于传统算法的搜索多数情况会遍历进路上所有分支，在站场复杂时会搜索到很多扩展节点，增加了程序执行时间。本文将A*搜索算法应用到联锁进路搜索过程中，利用启发信息指导搜索，使搜索沿着目标方向进行，避免盲目性搜索，从而提高搜索效率。

1 联锁数据结构

1.1 城轨站场的图结构

图1是西南交通大学城市轨道交通控制实验室地铁1号线的局部信号平面布置图，轨道电路、信号机和道岔这3类信号设备是联锁进路上的主要设备。

如果把信号机、轨道电路和道岔看成一个个设备节点，那么根据它们之间的位置关系就可以将各设备节点连接起来，构成设备节点图[7]，拓扑结构图，如图2所示。

图1 157站-西山梁站信号平面布置图

图2 拓扑结构图

拓扑结构图是由顶点（图2中用蓝色圆表示）和边（两个顶点间的连接线）构成的图结构，其中，顶点为3种类型的信号设备，边用来表示顶点之间的连接关系。基于这种图结构，可以构建站场型数据结构来存储各信号点的信息。

1.2 基于链表的站场型数据结构

所谓站场型数据结构，就是把每个设备对象看成一个个节点，然后依据其在信号平面布置图的位置来构建设备节点图，节点在图中的位置与实际站场图中设备的位置相对应[8]。每个设备节点都由两部分组成：数据域（Data标记区域）和指针域（Prev表示前向指针，Next表示后向指针），具体结构设计，如图3所示。

图3 信号设备节点结构

其中，数据域用来存放该节点设备的数据属性，指针域用来存储该节点与相邻节点的连接关系，根据节点类型来确定指针数目。对于信号机和轨道电路，其前方或者后方最多与一个设备存在连接关系，因此其前向指针和后向指针各设置一个即可；对于道岔，其前方或者后方可能与一个或两个信号设备有连接，因此需要为其设计两个前向指针和两个后向指针。

为了方便站场中进路的双向搜索，采用基于双向链表的存储结构来构建站场型数据结构。根据各设备节点在信号平面布置图中的位置关系将各设备节点通过指针连接起来[9]，构建如图4所示的基于双向链表的站场型数据结构图，通过指针可以实现进路的双向搜索。

图4 基于双向链表的站场型数据结构图

2 进路搜索算法的设计

2.1 进路搜索算法比较

目前，应用较为广泛的基于图的进路搜索算法主要有深度优先搜索算法、广度优先搜索算法和启发式搜索算法。

（1）深度优先搜索算法是一种盲目搜索算法，搜索沿着状态空间的某一条单一路径从起点开始向下搜索，只有当搜索到一个没有后继节点的节点时，才考虑替代路径。其缺点是，搜索深度可能无限深，或者深度超出可能的深度范围。为了避免这种情况，使用深度优先搜索时往往给定一个深度界限，任何节点只要达到这个界限，就视为没有后继节点处理。但即使规定了深度界限，深度优先搜索也不能保证一定找到最优路径。

（2）广度优先搜索也是盲目搜索算法，搜索以接近起始节点的程度为依据来扩展节点，搜索是逐层进行的。相比深度优先，广度优先搜索可以保证只要存在最优路径就一定可以搜索到。但对于结构复杂、扩展节点相对较多的铁路站场来说，广度优先并不是一种好的选择。

（3）启发式搜索利用启发信息来指导搜索过程，不断地将当前节点的估价值与其他节点的估价值进行比较，并对待扩展节点进行排序，然后选择最有希望的节点进行扩展。相比于盲目搜索，启发式搜索沿着目标方向扩展节点，能够减少大量的搜索路径，使搜索更加高效。本文采用启发式搜索算法中的A*搜索算法进行进路搜索。

2.2 A*搜索算法

A*搜索算法利用启发函数来决定待扩展节点，基本思想如下：

（1）假定存在启发函数f(n)，并且可以通过f(n)确定下一步要扩展的最佳节点，由于f(n)表示起始节点到目标节点的接近程度，因此f(n)越小表示找到的节点状态越好。

（2）选取f(n)最小的节点作为下一步要扩展的节点，假设可以产生这个扩展节点的全部后继节点。

（3）直到下一个待扩展节点是目标节点时搜索结束。

A*搜索算法是一种最佳优先搜索算法，其特点在估价函数的定义上，为此需要重新定义A*搜索算法的估价函数f*(n)，如式（1）：

其中，f(n)—启发函数，表示从起始节点经由节点n到达目标节点的最优路径代价；g(n)—表示从起始节点到当前节点n的实际代价；h(n)—表示从当前节点n到达目标节点的最优路径的估计代价值；

f*(n)—f(n)的某个估值，起始节点经由中间节点n到目标节点的估计代价；

g*(n)—g(n)的某个估值，起始节点到当前节点n的最优路径的估计代价；

h*(n)—h(n)的某个估值，从当前节点n到达目标节点的最优路径的估计代价。

式中，当g(n)≥g*(n)时，随着算法执行到深层将会获得更多的搜索信息，两者的数值也会越来越接近，直到两者数值相等找到最优路径。如果对A*搜索算法估计函数中的启发函数h(n)进行限制，使其满足h*(n)≤h(n)，称h*(n)是可采纳的，此时只要存在最优解就一定可以找到该解。

2.3 A*搜索算法在进路搜索中的具体设计

2.3.1 A*搜索算法搜索策略

A*搜索算法使用open和closed列表来维护状态。open表用来记录已计算出估价值的待考察的节点，closed表用来记录已经访问过得节点。相比盲目搜索，A*搜索算法新增加的一步就是对open表中的节点状态进行排序，排序依据起始节点到目标节点的接近程度的估价值。这样，每一轮循环中open列表中都保存的是最有希望的节点。需要注意的是，每一个状态节点都保留其祖先节点的信息，这样做的目的：（1）可以随时比较当前路径是否是最佳路径；（2）可以利用这些信息返回最终搜索到的路径[10-11]。

C#中的List类是一种很好的用来存储数组数据的列表，该类可以根据需求来动态地分配存储空间，而且List类自带添加、删除、查找等方法，使用起来很方便，因此，open表和closed表均使用List类存储。

2.3.2 启发函数的设计

A*搜索算法利用启发函数来决定下一步要扩展的节点，启发函数直接影响搜索效率的，因此，启发函数的设计在A*搜索算法中至关重要。

对于城轨铁路站场，其结构相对简单，节点设备几十到几百不等，搜索宽度不大，每个节点的后继扩展节点至多只有两个，每个节点设备在站场中位置相对固定，可以考虑采用欧几里得距离来计算h(n)的值，但在遇到对向道岔时，还要考虑直股优先/弯股优先问题，因此给h(n)增加纵向分量，在遇到对向道岔时，会比较分岔处的两节点的估价值，来指导搜索方向[12-13]。假设计算从起始节点S(xs, ys)到目标节点E(xe, ye)的估价值，设搜索过程中当前节点为n，坐标为（xn, yn），则对搜索过程中任意节点n的估价函数h(n)如式（2）：

式中， M—权值系数。

最终，确定启发函数f(n)，如式（3）：

2.3.3 A*搜索算法流程图设计

A*搜索算法的一般步骤为：

（1）把起始节点S存入open表中，将closed表置空。（2）重复以下过程，直到找到目标节点。如果open表为空，则宣告失败。（3）选取open表中估价值最小的节点min作为最优节点，并将其存入closed表中。（4）如果min就是目标节点，那么成功搜索到目标节点，结束搜索。（5）如果min不是目标节点，则扩展其后继节点ptemp，并存储到open表中。（6）计算估价值f(n)，转（2）。

将A*搜索算法应用到进路搜索中，实际上是在A*搜索算法的基础上加入城轨联锁的检查条件，这里，主要是检查搜索到的进路是否被占用。扩展节点时，通过始终端信号机节点的坐标先后位置来确定搜索方向，并结合节点类型和后继节点的估价值来确定待扩展节点。考虑到搜索到的节点可能存在被占用的情况，该模块中设计了一个存储关键道岔节点的容器，若搜索到的节点被占用，则回退到最新存储的道岔节点，沿其另一个子节点方向继续搜索可替代进路。搜索流程，如图5所示。

3 联锁仿真平台的功能需求及模块设计

搭建城轨联锁仿真平台，主要功能包括：进路控制、道岔控制、信号机控制和轨道区段控制等。其中，进路控制是计算机联锁的核心功能，基于A*搜索算法的进路搜索模块就是实现该功能的关键。考虑到操作人员可能希望看到A*搜索算法的搜索过程，仿真平台要求显示搜索过程中访问到的节点。

根据仿真平台的功能需要，将联锁功能划分为3个主要模块：

（1）站场初始化模块：存储各信号设备节点初始的相关信息，并将设备节点以链表的形式连接起来。（2）进路处理模块：主要实现进路的选排（进路搜索）、进路锁闭、进路解锁以及道岔单独操纵等功能。（3）命令显示模块：主要用于输出当前执行的命令、错误提示信息以及进路搜索过程中搜索到的节点信息等。

联锁仿真平台模块结构图，如图6所示。

4 进路搜索测试

图5 A*搜索算法流程

图6 联锁仿真平台模块图

在仿真平台上进行进路选排测试，顺序按下始终端信号机按钮，检查联锁条件后可对进路预选排，对选排成功的进路命令显示区给出搜索过程中访问的所有节点。经多次反复测试，选排进路过程中搜索到的节点基本上为进路上的节点，有效地避免了访问到过多的扩展节点，从而提高了进路搜索效率。图7为测试的两条进路，选排成功后进路锁闭，始端信号机开放。

图7 进路选排测试

5 结束语

进路搜索是联锁系统的核心模块，直接影响着进路控制的效率和正确性，因此进路搜索方法的效率至关重要，本文将A*搜索算法应用到进路搜索中，在算法中加入联锁条件的检查，另外，考虑到搜索到的节点可能存在被占用情况，在算法中对关键道岔节点进行存储，一旦搜索到的节点被占用，就会回退到关键道岔节点沿另一方向搜索。经过联锁仿真系统上进行验证，该方法可以快速、准确地搜索到联锁进路，有效减少了搜索过程中扩展节点数目，能够提高进路搜索效率。

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

[2]王文波 ，马学霞. 铁路车站计算机联锁软件进路搜索算法研究[J]. 铁路计算机应用，2016，25（4）：63-66.

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

[4]高利民，李文慧，孙 慧. 双向广度搜索算法在联锁进路自动生成中的应用[J]. 铁路计算机应用，2007，16（5）：43-45.

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

[6]陈 光，杨 扬. 计算机联锁系统进路表自动生成算法[J].铁路计算机应用，2015，24（5）：5-8.

[7]徐 鑫，陈光武. 计算机联锁软件设计及进路搜索算法的研究与应用[J]. 铁路计算机应用，2011，20（1）：49-52.

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

[9]吴益芳. 进路搜索数据结构与算法研究[J]. 铁路通信信号，2010，46（8）： 34-36.

[10]蔡自兴，徐光祐. 人工智能及其应用[M]. 北京： 清华大学出版社，2010：63-75.

[11]罗 兵，梨花嵩，李敬民. 人工智能原理及应用[M]. 北京：机械工业出版社，2011：170-188.

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

[13]宋 岩. 基于A-Star算法的进路搜索研究[D]. 成都：西南交通大学， 2014.