基于距离的线路数据反推算法

郁文斌

（北京全路通信信号研究设计院集团有限公司，北京 100070）

1 概述

线路数据配置的设计与实现是高铁信号产品基于线路数据进行计算的前提。目前高铁信号地面安全产品，如无线闭塞中心、临时限速服务器、列控中心等，对于线路数据配置的有关距离的计算比较多，但是在数据设计和数据测试时，对于庞大的工程数据，需要根据输入点和距其相对距离得到对应的输出点。这些如果由人工进行计算，工作量巨大，尤其是目前高铁营业里程超4万km，对于任何设备提供商，这些数据的计算如果仅由人工来完成，是无法想象的。因此需要提供辅助工具以自动化的形式来实现，提供一种有效的算法是必要且非常有意义的。

2 引用算法介绍

以基于距离的线路数据处理算法和基于散列的长链算法为基础进行设计，建立在此两种算法的基础上设计一种新的算法。本文介绍的反推算法是上述两种算法的实际应用。

2.1 基于距离的线路数据处理算法

根据文献[1]，基于距离的线路数据处理算法目的是提供给数据配置用户对于线路数据配置规则的制定，而不是由研发用户固化到软件中，使得数据配置灵活且统一。同时，对研发用户屏蔽了数据配置规则，使线路数据计算根据用户需求由给定的输入点输出距离线路逻辑数据起点的相对距离，获取到与线路数据相关的大小比较、范围判断、距离计算的参数。本文的算法仍旧是对工程数据配置的处理，因此，对于数据配置，本文直接引用文献[1]的结论。文献[1]中的下列定义仍旧是本文的基础：

定义1.工程规定的正向线路方向（DIR），也是其他方向定义的基准或者参考方向，与DIR同向，以SAME_DIRECTION标记，与DIR反向，以CONVERSE_DIRECTION标记；

定义2.数据配置方向（UCDIR），其涉及到分段配置方向，段内数据配置方向；

定义3.用户计算方向（USDIR），也就是运行的实际方向；

定义4.长链的配置起点（LCS），与方向无关，带有长链标志；

定义5.长链的配置终点（LCE），与方向无关，不带长链标志；

定义6.长链的配置长度（LCL）；

定义7.USDIR方向，线路的逻辑第一个分段（LLS）；

定义8.USDIR方向，线路的逻辑最后一个分段（LLE）；

定义9.USDIR方向，分段内的逻辑起点（LSS）；

定义10.USDIR方向，分段内的逻辑终点（LSE）；

定义11.USDIR方向，长链的逻辑起点（LFS）；

定义12.USDIR方向，长链的逻辑终点（LFE）。

2.2 基于散列的长链算法

根据文献[2]，输入点和距输入点相对距离的输出点均可能落入长链范围，需要进行长链点的处理和计算，同时进行长链标志的判断和校验，文献[2]提供的散列算法可以解决此问题。

3 基于距离的反推算法

如果是普通的线路计算，根据输入点PI和距输入点的相对距离D获取输出点PO，仅仅通过简单的数学逻辑运算即可实现。但是，铁路的线路数据存在工程的复杂性，具有不同里程标系而造成的分段及里程标系转换，而且还有断链，其中长链的处理也增加计算的复杂度，同时，列车运行可以以线路的正向和反向两个方向运行，从而使得线路数据的处理和计算复杂度增加。

例如，在列车运行方向上，如果输入点是一个逻辑分段起点，若要获取距离其反向1 m的输出点，即相对距离-1的输出点，此点已落入了其后方段中。如果输入点是一个长链的逻辑起点后方1 m的里程点，若要获取其前方1 m的输出点，即相对距离+1的输出点，此点已落入此长链范围内，即输出点具有长链标志。因此，通过常规的数学运算不可能实现距离的计算，需要设计一种新的算法来解决此问题。

3.1 场景分析

分析上述的例子，如果以正向思维根据PI和D两个参数推导出输出点PO，难度比较大。不妨进行逆向思维考虑，假设已经获取PO点，那么根据文献[1]，z(PO)－z(PI)=D。

1）如果z(PO)>z(PI),D>0，在线路逻辑方向上，PO位于PI前方。

2）如果z(PO)=z(PI),D=0，在线路逻辑方向上，PO与PI重叠。

3）如果z(PO)

根据位置的不同，定义分段i，段内长链为ni，区间分类数为ci(ni)，总共场景数为qi(ni)。

考虑一个分段，根据区间的不同分为以下几种情况。

1）如果1个线路只有1个分段，分段内无长链，则分为段逻辑起点外、段内、段逻辑终点外3个区间，加上段逻辑起点和段逻辑终点，分为5种情况。c0(0)=3，场景数为q0(0)=5。

2）如果一个线路只有一个分段，分段内有一个长链，那么可以分为段逻辑起点外、段内长链逻辑起点外、段内长链范围内、段内长链逻辑终点外、段逻辑终点外5个区间，加上段逻辑起点、段逻辑终点、长链逻辑起点、长链逻辑终点，分为9种情况。c0(1)=5，场景数为q0(1)=9。

3）如果一个线路只有一个分段，分段内两个长链，那么可以分为段逻辑起点外、段内第一个长链逻辑起点外、段内第一个长链范围内、段内第一个长链逻辑终点外且第二个长链逻辑起点外、段内第二个长链范围内、段内第二个长链逻辑终点外、段逻辑终点外7个区间，加上段逻辑起点、段逻辑终点、第一个长链逻辑起点、第一个长链逻辑终点，第二个长链逻辑起点、第二个长链逻辑终点，分为13种情况。c0(2)=7，场景数为q0(2)=13。

4）根据上述规律，以此类推，使用归纳总结法，可以推导出c0(n0)=c0(n0－1)＋2,n0>1,c0(0)=3，场景数q0(n0)=c0(n0)×2－1。因此c0(n0)= 2n0＋3,n0≥0,q0(n0)=4n0＋5,n0≥0。

考虑两个分段，根据区间的不同分为以下几种情况。

1）如果一个线路有两个分段，分段均无长链，那么可以分为第一段逻辑起点外、第一段内、第一段逻辑终点外、第二段逻辑起点外、第二段内、第二段逻辑终点外6个区间，加上第一段和第二段的逻辑起点和终点，分为10种情况。场 景 数 为

2）如果一个线路有两个分段，第一分段内存在长链，那么可以分为第一段逻辑起点外、第一段内长链逻辑起点外、第一段内长链范围内、第一段内长链逻辑终点外、第一段逻辑终点外、第二段逻辑起点外、第二段内、第二段逻辑终点外8个区间，加上第一段和第二段的逻辑起点和终点，第一段长链逻辑起点和终点，分为14种情况。场景数

4）根据上述规律，依次类推，对于任意分段数m，对于第i段内任意长链数 ，使用归纳总结法，可以建立推导公式：

3.2 算法设计

可以根据公式（2）的e(m,n)对应的场景进行处理，那么只要知道区分公式（1）的d(m,n)对应的分界点值即可，总共需要e(m,n)－d(m,n)个值的分界点，进行计算4种分界距离的计算：段逻辑起点距线路逻辑起点的距离DSS，段逻辑终点距线路逻辑起点的距离DSE，长链逻辑起点距线路逻辑起点的距离DLS，长链逻辑终点距线路逻辑起点的距离DLE，在此基础上实现反推计算。

若要获取DSS、DSE、DLS、DLE，则需使用文献[1]中如公式（3）～（10）所示。

其中，公式（3）为给定带有长链点返回对应配置的长链终点；公式（4）为给定带有长链点返回对应配置的长链所在的下标，即线路上的第几个长链点；公式（5）为给定输入点，返回USDIR方向所在的分段索引；集合（6）为与输入点同属一个分段内的所有长链配置点，且USDIR方向，在输入点前方的所有长链点；集合（7）为USDIR方向，分段x内的所有长链点；公式（8）为输入点所在段的前方所有段并包含其中所有长链点的距离；公式（9）为USDIR方向，输入点所在段中，距离段逻辑起点并包含长链点的距离；公式（10）为USDIR方向，输入点具有长链标志时，对于其距长链逻辑起点的距离，根据长链散列算法进行实现。

因此，对于任意段i,DSS=s(LSSi)＋f(LSSi),DSE=s(LSEi)＋f(LSEi),DLS=s(LFSi)＋f(LFSi)，结合公式（1）、（2），可以判断出输出点落到了公式（2）对应的哪种场景，并且可以获得对应此种场景中距段逻辑起点的距离，因此可以得到输出点的里程标具体参数，提供给用户。

本算法是基于文献[1-2]设计的线性算法，因此算法复杂度与文献[1-2]保持一致，为O(m＋n)，m为线路分段数，n为线路长链数。

4 算法实现

根据公式（1）～（10）进行算法实现，程序设计逻辑如图 1所示。

图1 程序逻辑Fig.1 Program logic diagram

为完成上述程序逻辑，即根据公式（1）～（8）实现算法，需进行功能实现，主要功能如表 1所示。

表 1 算法实现功能列Tab.1 Algorithm implementation function list

5 测试验证

根据程序实现的线路数据反推算法设计案例进行验证。设计案例的原则为考虑各种数据配置规则下每种线路分段、段内递增减、段内长链情况，划分等价类，每种等价类需要对边界值设定案例，以此检验反推算法的逻辑是否正确。设定线路场景案例如表 2所示。

表 2 测试案例场景Tab.2 Test case scenario

根据上述场景，考虑设置输入点与输出点所在公式（2）同一场景和不同场景，总共设计案例100个。

测试结果正确，确认算法功能符合预期。

6 总结

本文在基于距离的线路数据处理算法和基于散列的长链算法基础上，提出一种基于距离的线路数据反推算法。给定线路数据上任意的输入点和距其的相对距离，获得对应的线路输出点。扩展了算法的功能，从而扩大线路数据计算的使用范围。使站内侧线映射正线、正线跨线根据已知线路信息推导出计算所需的信息，应用于线路数据设计和自动化测试所需的预期结果计算。

本算法目前主要考虑在数据设计、校验、测试的使用，可以考虑提供给脚本语言的接口，在软件开发中直接调用，尤其应用于产品自动化测试的预期结果计算应用，均可以作为对于后续工作的展望。