基于多层网络分割算法的高速铁路检测区域均衡化划分方法研究

Balanced Division Method of High Speed Railway Inspection Regions Based on Multi-Level Network Partition Algorithm

摘要

高速综合检测列车是保证高速铁路安全高效运营的重要手段，其检测效率与资源分配的合理性尤为关键。为提升检测效率，降低检测人员工作强度，提出一种基于权重映射的多层网络分割算法，以实现高速铁路网络的均衡划分。为解决多层网络分割算法破坏网络连通拓扑的问题，在既有的多层网络分割算法中引入权重映射策略，通过概化、分割、细化3个阶段将高速铁路网络图划分为均等分区。实验表明，该算法能有效将全国高速铁路网络完整均衡分割为若干检测分区，各区域里程差异控制在10%以内，显著降低检测人员工作强度与车底维护成本。相比于传统算法，本方法在保障网络拓扑连通性的同时，解决大规模路网分割效率低、边界割裂线路等问题，为动态检测计划的智能编制提供参考。

Abstract

High speed comprehensive inspection train serves as an important tool to ensure the safe and efficient operation of high speed railways, and its inspection efficiency and the rationality of resource allocation are particularly critical. In order to improve the inspection efficiency and reduce the work intensity of inspection personnel, a multi-level network partition algorithm based on weight mapping was proposed, so as to realize the balanced division of high speed railway network. In order to solve the problem that the multi-level network partition algorithm destroys the network connectivity topology, the weight mapping strategy was introduced into the existing multi-level network partition algorithm, and the high speed railway network graph was divided into equal regions through three phases, such as generalization, partitioning, and refinement. The experiment shows that the algorithm can effectively divide the national high speed railway network into several inspection regions in a comprehensive and balanced manner. The mileage discrepancy between regions is controlled within 10%, significantly reducing the work intensity of inspection personnel and carriage maintenance costs. Compared to traditional algorithms, this method ensures network topology connectivity while addressing inefficiencies in large-scale railway network partition and issues of fragmented boundary lines, providing a reference for the intelligent formulation of dynamic inspection plans.

Graphical abstract

关键词

网络图分割 / 多层分割算法 / 高速综合检测 / 区域化检测 / 高速铁路

Key words

Network Graph Partition / Multi-Level Partition Algorithm / High Speed Comprehensive Inspection / Region Inspection / High Speed Railway

1　高速铁路综合检测现状

截至2023年底，我国高速铁路营业里程达到4.5万 km，占世界高速铁路营业总里程的70%以上。为实现对铁路基础设施状态的有效监控，高速综合检测列车(以下简称“检测车”)对全国高速铁路运营线路实施每月2次全覆盖的周期性动态检测，获取与运营列车等速的检测数据，可及时发现故障、准确掌握状态，指导设备维修单位合理安排各项养护维修工作。庞大的路网规模带来巨量的检测需求，随着新线的开通，年度检测里程持续增加，路网结构日趋复杂，形成越来越多的“十”字型和“米”字型交叉点^[1]。然而长期以来检测车的检测交路一直依赖于人工手动编制，开通一条高速铁路，规划一条交路，缺乏整体规划，存在重复检测、检测盲区、检测任务量不均衡等问题。加之现有14列检测车在实际运用中面临诸多挑战，包括联调联试、综合试验、高级维修等预留需求，以及车底与线路速度不匹配等问题，导致实际可用于日常动态检测任务的列车数量减少至约11列^[2]。面对不断增长的检测任务，车底运用资源紧张、检测任务量不均、检测车运用效率低下等问题日益凸显。

国内外高速铁路综合检测模式的组织结构具有一定差异，我国高速铁路检测计划由中国国家铁路集团有限公司统一制定，各检测车围绕“八纵八横”高速铁路主通道，以城际、区域铁路为连接，形成干线串联支线的检测模式，长大干线往往涉及多个铁路局集团公司，跨区域协调沟通较为复杂；且干线规模长短不一，导致检测车检测里程分布不均。日本高速铁路基于JR东日本、JR东海、JR西日本3家公司的经营范围划分，固定检测车和检测人员对各区域线路进行定期检测^[3]，实现区域化检测模式。这种模式相比于传统的检测模式具有明显优势，首先区域化检测使得检测人员对固定区域的线路有更深入的了解，能够更准确地识别和处理特定线路问题，能够提高检测工作的效率和准确性，为属地铁路局集团公司提供更加个性化和针对性的服务；其次区域化检测通过相对固定的检测计划，能够确保关键区域和时段的检测需求得到满足，避免由于运行图变化带来的对检测计划的频繁调整；此外，由于检测人员对特定区域的熟悉度较高，能够灵活调整检测计划和维护策略，快速响应线路变化和突发事件；最后，区域化检测模式下检测人员在相对固定的区域内工作，减少全国范围内频繁移动的需要，检测人员可以将更多的时间和精力投入到实际的检测工作中。综上所述，区域化检测模式不仅提升了检测工作的效率和质量，还能够显著改善检测人员工作与生活的平衡，亟需研究适合我国高速铁路路网的区域化检测模式。

1.1　检测车运用现状

根据《高速综合检测列车运用维修管理办法》(TG/GW 253—2020)规定，我国检测车每10~15 d对每条高速铁路线路动态巡检1遍。在此基础上，针对特定区域和季节，检测频次有所调整。具体而言，高温季节(6—9月)，部分炎热地区的特定线路每月增加1次检测；高寒季节(11月—次年4月)，部分高海拔寒冷地区的特定线路每月增加2次检测。对于具有特殊需求或被视为检测重点的线路，检测频次将根据实际情况进行动态调整^[4]。

目前的检测计划主要依赖人工编制，缺乏模型和算法等技术手段的支持，导致整体统筹效率较低，人工干预和调整工作强度较大，编制效率不高。此外，在面对突发情况时，检测计划的调整缺乏实时性，导致检测车的检测里程分布不均，车底运用效率低下。

以2024年7月为例，2024年7月份各检测车检测任务信息如表1所示。分析不同车底的检测里程，CRH380AJ-2818车型的检测里程达到16 629 km，而CR400BF-J-0003车型的检测里程则为6 233 km，里程差异超1万 km。分析不同车底的检测天数，CRH380AJ-2818车型的巡检天数为27 d，而CRH380BJ-A-0504车型的巡检天数为14 d。检测里程差距过大将导致车底的老化程度明显不一致，检测任务较重的车底需要频繁高级修，对日常检测任务的分配将产生不利影响。通常情况下，检测作业班组人员与车底是固定搭配的，但由于各检测车巡检任务时长的差异性，导致作业人员工作强度的不一致，强度较大的班组人员存在疲劳作业的安全隐患，因此区域化检测模式首先应均衡各检测区域里程。

1.2　多层网络分割算法研究现状

区域化检测模式涉及将全国高速铁路路网均衡分割为一系列检测区域，基本可视为网络图分割问题。现有的网络图分割算法研究分为几类，谱二分算法是一种较早出现的算法^[5]，基于图的谱特性来找到图的均衡划分，但随着分区数量的增加，计算复杂度和迭代次数上升，可能导致谱二分算法的效率和准确度降低^[6]。图形生长算法初始选择1个节点作为种子，随后逐步将该节点的相邻节点纳入其所属的区域。当该区域的规模达到预设标准时，划分过程即终止^[7-8]。这种算法因其生长特性而被称为图形生长算法，其最终的划分效果在很大程度上取决于最初节点的选取。通过选取1个初始节点并逐步扩展区块来实现分割，其结果受初始节点选择的影响较大^[9-11]。很多时候原始图划分的结果并不理想，于是有些研究按照某种规则合并原始图形的节点来缩小图的规模，然后在缩小后的图上进行分割，最后再将结果还原到原始图上，是一种多层网络分割算法^[12]。通过合并节点来降低问题的规模，提高了分割的效率和效果。这种算法通过在不同层次上进行分割，能够更好地处理复杂和大规模的网络，对于处理我国庞大的高速铁路路网规模具有明显的优势，但在实际应用中存在分割路网连通拓扑的缺陷^[13]。

撖志恒等^[14]通过多层网络分割算法将节点均等分区，并取同一分区节点的凸包多边形作为分区边界，得到的多边形会割断连通道路，对此建议对多层网络分割算法进行改进，提出基于层次策略的改进方向，以避免分割道路并保留网络的连通性；张梦园等^[15]引入节点重要性概念，通过将边权映射到点，并结合模块度增益最大原则进行社团划分，通过Lancichinetti-Fortunato-Radicchi (LFR)人工基准网络数据集实验验证所提出算法的有效性和优越性。

综上，传统网络图分割算法存在大型网络分割效率低、分割不均衡、分区边界切割线路等问题，本研究通过优化车站节点、映射形成边点分区、移动边界节点等方法，对多层网络分割算法进行优化，提升分割效率和分割质量，确保分区连通性，最终得到均衡检测分区。

2　基于多层网络分割算法的优化方法研究

2.1　网络图概念和定义

高速铁路网络上下行线路里程间的差值忽略不计，可将高速铁路网络抽象地表示为无向网络图G=\left(V，E，W\right)的形式，节点V表示车站，节点间的边E表示站间线路，边的权值W表示线路里程，km，w_{ij}表示直接相连的节点v_i与v_j间边的权值，对于无向网络w_{ij}=w_{ji}，与节点v_i直接相连的边数为节点v_i的度d_i；当有q个点与节点v_i直接相连时，节点v_i的权值w_i={\displaystyle \sum _{j=\mathrm{1}}^q}{w}_{ij}，节点v_i的度d_i=q。在本研究中，定义区域的边界度为区域内所有节点与区域外节点相连的边的总数，反映区域与外部网络的相互连接程度；定义区域的内部度为该区域内所有边的总数，反映区域内节点的相互连接程度。

2.2　优化车站节点

我国高速铁路网络结构复杂，车站各节点连接关系众多，为提升计算效率，去除非枢纽车站节点，同时为不破坏路网拓扑的连通性，排除未与路网连接的独立线路。优化后，全路网车站数量由2 242个降至175个，遍历数量降低至全路搜索量的8%，从而降低计算复杂度和提高算法的执行速度。

2.3　算法设计

为尽可能均衡各检测分区的线路里程，同时减少检测车在区域边缘折返的次数，网络均衡分割算法的目标是将边的权值尽可能均匀地分配到若干个区域中，同时尽量减少区域之间的边界度。算法分为概化、分割和细化3个阶段，概化阶段将边权映射到节点，形成的分区同时包含节点和边，保证分区的连通性；分割阶段将概化后的网络图进一步细化为预定数量的区域，确保分区里程近似均衡；细化阶段通过移动边界节点使得分区里程更均衡。

2.3.1　概化阶段

在此过程中，网络中的每个节点初始化为1个社团，社团包含节点及节点的所有邻接边，社团编号为节点编号，保留权值最小的社团内所有的边，将这些边在其他社团内移出，并在下一个概化图中标记该社团已被访问过。当社团间权值一致时，度最小的优先被保留；当权值和度均一致时，优先保留邻居社团权值最小的社团。遍历网络中的所有社团，直到社团之间没有重复的边，此时每条边都属于且仅属于1个社团。

2.3.2　分割阶段

将网络图重构为概化图，将第一阶段划分出的社团标记为新的节点，社团编号标记为新的节点编号，新节点之间的连接关系与原社团之间的连接关系保持一致。此时概化图的边仅表示新节点之间的连接关系，新节点的权值为第一阶段结束后社团内所有边的权值和。假定要求划分为k个区域，每个 区域的权值为l，则按照以下规则进行分割。

（1）优先合并2个相连且合并后权值最小的2个节点，计算合并后区域的边界度。

(2）若2个节点合并组成的区域权值最小且与另2个节点相同，选出度最小的待选的2个节点，保证生成的区域与周边区域的边界边数尽可能低。

（3）若仍有多个待选区域满足条件，则选出区域内部度最小的待选区域。

（4）确定好合并的区域后，将该区域标记为新的节点，继续下一步分割。

（5）若所有的区域权值均大于l，或已形成k个分区，区域初步分割完成。

2.3.3　细化阶段

分割阶段形成的k个分区之间只能保证近似平均，因此需要选择合适的方式调整分区的均衡性。外部度大于0的节点为边界节点，Fiduccia-Mattheyses (FM)算法通过在分区间选择移动边界节点达到细化平衡的效果，同时相比Kernighan-Lin (KL)算法效率更高且没有划分质量的损失^[16]。细化阶段中边界节点按照以下规则从区域a移入区域b。

（1）在不同分区间移动边界节点需要进行平衡判断，W_a表示区域a的权值，定义最终各区域权值的下限W_{\mathrm{m}\mathrm{i}\mathrm{n}}=X{\displaystyle \sum _{\mathrm{0}}^k}\frac{\left|W\right|}{k}，上限W_{\mathrm{m}\mathrm{a}\mathrm{x}}=S{\displaystyle \sum _{\mathrm{0}}^k}\frac{\left|W\right|}{k}，d_{ia}表示节点v_i与区域a内节点的连接边数，d_{ib}表示节点v_i与区域b内节点的连接边数，节点v_i可以从区域a移入区域b的条件为

\mathrm{s}.\mathrm{t}.\left\{\begin{array}{l}{W}_a-w_i\ge W_{\mathrm{m}\mathrm{i}\mathrm{n}}\\ W_b+w_i\le W_{\mathrm{m}\mathrm{a}\mathrm{x}}\\ d_{ia}\ge d_{ib}\end{array}\right.(1)

（2）若不满足上述条件则将该点标记为已被访问，遍历下一边界节点。

在实际应用中，需要对网络数据进行预处理，保证初始网路不存在孤立的点；得到网络分区结果后，将结果进行可视化处理。多层网络分割算法划分示例如图1所示。多层网络分割算法处理流程如图2所示。

3　案例分析

3.1　路网数据采集及可视化准备

利用GIS软件，采集铁路线路数据，包括线路名称、线路走向坐标数据集等信息，采集铁路车站数据，包括车站名称、坐标等信息。将其坐标导入GIS中，对路网数据进行拓扑规则检查、新建字段及赋值处理，生成点层数据和线层数据。最后，将处理后得到的点层数据和线层数据进行空间关联分析处理，以建立路网模型。

在路网模型的基础上，通过GIS建立矢量数据库，搭建基础数据网络，从而为检测方案提供路网基础数据文件，便于路网可视化和数据统计等功能的应用。数据分为车站数据和线路数据2类，包括空间信息数据和属性信息数据2个部分，路网数据内容如表2所示，主要体现线路信息、线路走向、线路上的车站信息、车站位置、车站连接关系等。

空间信息数据保证了高速铁路网可视化、车站位置可视化等功能的实现。属性信息数据保证了检测区域可视化、动车段可视化、其他信息可视化等功能的应用，也可以较好筛选需求线路，形成不同需求的可视化图。优化节点搜索的全路拓扑图如图3所示。

3.2　计算求解

高速铁路网络区域划分方案如图4所示，由于图4所示的区域1和区域10具有特殊的运营条件，为保持其运营管理的连续性，这2个区域未被分割，对除这2个区域外的剩余区域进行分割。研究目标为：将给定的高速铁路网，划分为9个区域，既k=\mathrm{9}；考虑到检测车的检修周期和检测工作量的均衡分配^[17]，区域里程设定为最少5 000 km，即l =5 000；每个区域的路网总里程尽可能均等；针对检测车遇区域边缘折返的实际需求，区域对外的联系边数尽可能少。

3.3　结果分析

各检测区域的任务量较为均衡，检测车检测任务量如表3所示。求解得到的检测区域划分计划，能够满足区域均衡约束和检测区域连通要求，各检测车检测区域互相连通。

计算得出各检测车在优化前后的检测里程，各检测车检测里程优化前后对比如图5所示，在原方案中各检测车检测里程数相差较多，经过优化，各检测车的检测里程分配得更加均匀。总体来看，检测区域划分方案既达到了检测里程均衡化的目标，又综合考虑了车线的适用性和线路的通达性，区域分配结果满足区域划分的目标及约束要求。

提出的多层网络分割算法，应用于检测车区域均衡化检测方案编制，实现了各检测车检测里程均衡化，检测方案区域均衡化。根据计算结果分析，区域均衡化检测方案中各检测车任务量更为均衡，同时保留了检测车遇区域边缘的少折返原则。案例结果表明所提出的多层网络分割算法在针对检测车运用方面，起到了平衡车体运用均衡度、降低工作人员强度、提升编制效率的作用。

多层网络分割算法分区结果统计如图6所示。图6显示分区数从7~11时各统计指标的变化曲线，多层网络分割算法分区统计指标有3个，分别为各分区里程的最小值、最大值和平均值。从3个统计指标可看出，所有分区里程值大致相同；每个分区里程最大值和最小值差较小，算法具有较好的分区均等性；从三者的曲线关系分析，最大值、最小值曲线随着分区数增大而趋近平均值曲线，可知分区数越多算法结果均等性越好。

4　结束语

在处理大规模复杂路网的划分问题时采用多层策略执行效率较高，但存在分割原始路网的缺点。本研究在多层网络分割算法中引入优化车站节点、映射形成边点分区、移动边界节点等优化方法，可快速规划出检测分区，为区域化检测方案提供技术支撑。基于全国铁路网络图进行算例分析，结果表明该算法可保留原始路网的连通拓扑关系，形成完整自然的边界分区，且执行效率较高，能够得到均衡的分区，具有重要的理论价值和广泛的应用前景。随着技术的不断进步，未来的研究可进一步考虑等速检测、车线匹配和加密监测等问题，进一步探索如何将新兴技术与区域化检测深度融合。

参考文献

[1] 刘维桢，张子亮，陈春雷，等. 巨型复杂铁路网基础设施动态检测管理探讨[J]. 中国铁路，2024(4)：57-62.

[2] LIU Weizhen， ZHANG Ziliang， CHEN Chunlei，et al. Reflections on Dynamic Inspection Management of Infrastructure in Giant and Complex Railway Network[J]. China Railway，2024(4)：57-62.

[3] 张景昱，陈家旭，赵泽乾，等. 高速综合检测列车交路计划优化方法研究[J]. 铁道运输与经济，2024，46(7)：15-22.

[4] ZHANG Jingyu， CHEN Jiaxu， ZHAO Zeqian，et al. Optimization Method of Routing Scheme for High Speed Comprehensive Inspection Train[J]. Railway Transport and Economy，2024，46(7)：15-22.

[5] 杨　飞，涂文靖，魏子龙，等. 铁路工务、电务、供电检测装备发展现状综述[J]. 交通运输工程学报，2023，23(1)：47-69.

[6] YANG Fei， TU Wenjing， WEI Zilong，et al. Review on Development Status of Inspection Equipment for Track Maintenance，Communication and Signaling，and Power Supply of Railway[J]. Journal of Traffic and Transportation Engineering，2023，23(1)：47-69.

[7] 中国国家铁路集团有限公司. 高速综合检测列车运用维修管理办法[A]. 北京：中国国家铁路集团有限公司，2020.

[8] DONATH W E， HOFFMAN A J. Lower Bounds for the Partitioning of Graphs[J]. IBM Journal of Research and Development，1973，17(5)：420-425.

[9] FIEDLER M. Algebraic Connectivity of Graphs[J]. Czechoslovak Mathematical Journal，1973，23(2)：298-305.

[10] FIEDLER M. A Property of Eigenvectors of Nonnegative Symmetric Matrices and Its Application to Graph Theory[J]. Czechoslovak Mathematical Journal，1975，25(4)：619-633.

[11] NEWMAN M E J. Spectral Methods for Community Detection and Graph Partitioning[J]. Physical Review E，2013，88(4)：042822.

[12] GOEHRING T， SAAD Y. Heuristic Algorithms for Automatic Graph Partitioning[EB/OL]. (1995-12-31)[2024-06-31].

[13] 秦旭彦，陆化普，马　洪. 道路网络图的区块划分算法[J]. 清华大学学报(自然科学版)，2009，49(3)：333-336.

[14] QIN Xuyan， LU Huapu， MA Hong. Algorithm for Road Network Graph Partitioning[J]. Journal of Tsinghua University (Science and Technology)，2009，49(3)：333-336.

[15] 张　蓝，李佳田，徐　珩，等. 道路网络示意图的多边形生长算法[J]. 测绘学报，2015，44(3)：346-352.

[16] ZHANG Lan， LI Jiatian， XU Heng，et al. Polygon Growing Algorithm for Network Schematic Maps[J]. Acta Geodaetica et Cartographica Sinica，2015，44(3)：346-352.

[17] 周安宇. 网络拓扑图划分算法研究[D]. 哈尔滨：哈尔滨工程大学，2014.

[18] 张梦琳. 基于多层次划分的大规模动态图分割方法研究[D]. 沈阳：辽宁大学，2018.

[19] 撖志恒，芮小平，董承玮，等. 多层分割算法在构建层次道路网络中的应用[J]. 计算机应用研究，2016，33(3)：779-782.

[20] HAN Zhiheng， RUI Xiaoping， DONG Chengwei，et al. Application of Multi-Level Algorithms in Constructing Hierarchical Road Network[J]. Application Research of Computers，2016，33(3)：779-782.

[21] 张梦园，李玲娟. 基于节点重要性和模块度优化的社团划分算法[J]. 计算机技术与发展，2023，33(4)：126-131.

[22] ZHANG Mengyuan， LI Lingjuan. Community Division Algorithm Based on Node Importance and Modularity Optimization[J]. Computer Technology and Development，2023，33(4)：126-131.

[23] FIDUCCIA C M， MATTHEYSES R M. A Linear-Time Heuristic for Improving Network Partitions[EB/OL]. (2006-02-06)‍ [2024-06-31].

[24] 白　鑫. 高速铁路联调联试单列综合检测列车逐级提速计划制订方法研究[J]. 铁道运输与经济，2019，41(9)：79-84.

[25] BAI Xin. A Study on the Method of Formulation of Gradual Speed Increase Plan for the Integration Test and Commissioning of High Speed Railways with Single Comprehensive Inspection Train[J]. Railway Transport and Economy，2019，41(9)：79-84.

基金资助

中国国家铁路集团有限公司科技研究开发计划课题(Q2024X010)

中国铁道科学研究院集团有限公司科研项目(2022YJ239)