随着“国家烈度速报与预警工程”项目（以下简称预警工程）的持续推进，截止2023年6月，全国共建成地震预警台站15 391个^[1]，地震监测能力和覆盖范围有了极大地提高。高质量的数字地震台网需要长期稳定的运行和维护^[2]，根据现行管理办法，省级地震监测中心站（以下简称中心站）需对辖区内地震预警台站开展每年不少于两次的定期巡检任务。由于地震预警台站分布较广、中心站运维人员较少，如何设计合理的巡检路径，成为中心站面临的一个问题。以云南为例，截止2023年6月，云南共建设地震预警台站1460个，云南省地震局下设地震监测中心站8个，每个中心站平均运维182.5个台站，中心站人员编制16人/站，大部分中心站均未满编。因此，研究如何利用更少的巡检成本完成更多巡检任务，具有较强的现实意义。

图1中三角形代表基准站，正方形代表基本站，圆形代表一般站，云南省内共有基准站202个，基本站228个，一般站1230个，数据来源云南地震台。

图1 云南省地震预警台站分布图Fig.1 The distribution of earthquake early warning stations in Yunnan Province.

寻找地震台站最优巡检路径本质上属于经典的组合优化问题——旅行商问题（Traveling Salesman Problem，TSP）。TSP一般描述为：给定一组城市和每两个城市之间的距离，求解访问每一座城市一次并回到起始城市的最短路径，现实生活中的计算机网络布线、集成电路设计、交通运输、人员调度安排等问题都可以抽象成TSP问题进行求解。TSP属于NP-hard问题，目前有两个研究方向：完全算法和近似算法。完全算法通过遍历全部解空间寻找全局最优解，算法开销较大，常见的完全算法包括线性规划法^[3]、动态规划法^[4]、分支列定法^[5]等。近似算法可分为构造算法和环路改进算法，常见的构造算法有最邻近算法^[6]、贪心算法^[7]、Clarke-Wright算法^[8]等。这类算法从某个非法解开始，通过某种增广策略逐步改变该解，直到得到一个合法解为止。环路改进算法主要包括蚁群算法^[9]、模拟退火算法^[10]和遗传算法^[11]，这些算法一般通过给定初始的合法解，使用某种策略来改进初始解，最后输出最优解^[12]。张广林等认为遗传算法优点在于易与其他算法结合，充分发挥自身迭代的优势，缺点是运算效率不高^[13]。在台站巡检路径规划问题中，结合样本数量不会太大、运算效率要求不高，台站巡检顺序可直接作为遗传算法个体基因等特点，本文采用遗传算法作为路径规划的核心算法。

遗传算法由Holland^[11]提出，算法借鉴生物界中遗传和选择机制，在每次迭代中保留一组候选解，并按照某种指标从解群中选取较优的个体，利用遗传算子（选择、交叉和变异）对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。与传统的启发式优化搜索算法相比，遗传算法的本质特征在于群体搜索策略和简单的遗传算子。群体搜索使遗传算法得以突破领域搜索限制，可以实现整个解空间上的分布式信息采集和探索^[14]。

在实际应用中，吴晓涛等利用遗传算法对避障路径规划进行了研究^[15]。袁豪等基于百度地图，将TSP运用于旅游路线规划，为游客行程安排游玩计划^[12]。蒋丽等基于改进的蚁群算法和高德API对外卖配送路径进行了研究^[16]。戴波等结合江苏省地震台站巡检实际工作，提出一种基于“开放组体系结构框架”TOGAF的地震台站巡检系统架构，方便巡检人员直观掌握地震台站分布，规范了巡检工作流程^[17]。本文采用高德地图API，基于遗传算法编写python程序自动求解最低成本的台站巡检路径的近似最优解。

将台站巡检序列作为遗传算法中个体的基因，个体间的交叉变异操作就是对巡检序列中的部分片段进行变更。将每个巡检序列的巡检成本（个体适应度）作为衡量个体表现，挑选进入候选解的依据，遗传算法的迭代过程就是不断寻找巡检成本最低的巡检序列的过程。为更贴近现实，考虑实际巡检过程路况等因素，系统引入高德地图API服务。通过高德API可获取两点间的行驶距离、行驶时间和过路费等信息作为巡检成本，为简便计算，本文仅采用行驶距离作为巡检成本。由于地图服务商使用了坐标偏移算法，为精确计算行驶距离，需调用其API进行坐标转换，生成新的位置信息。因此，系统由坐标转换、巡检路径获取、遗传算法计算和可视化展示四个模块组成，接收巡检台站位置信息作为输入，将生成的最终的巡检路线作为输出。

坐标转换模块接收台站原始经纬度坐标，调用高德API接口后生成转换后的台站经纬度坐标，为避免频繁网络请求带来的时间开销，将获取的结果进行本地存储。巡检路径获取模块将台站列表中的点两两取出，调用高德API接口获取两台站之间的行驶距离，过路费。为简化计算，默认两站点之间起点和终点互换，路径、距离和过路费不变，根据计算的上三角矩阵结果生成所有台站的成本矩阵。遗传算法接收成本矩阵，按照配置的迭代次数重复进行交叉、变异、合并、挑选新个体操作，直到迭代结束，输出最后一代的最优个体作为最佳结果。遗传算法设置的超参数包括种群样本个数、迭代次数和基因变异概率。

高德API路径规划中有丰富的选项，本文选取高德地图API中驾驶路线规划，选择普通汽车，最短时间规划，从返回值中提取行驶距离和过路费。使用高德地图前需要注册高德账号，添加应用并选择使用Web服务，然后将获得的key和参数通过GET请求传递到高德API，并获取API的返回值。

采用Python开发，用jupyter notebook编写代码，使用的Python依赖库有： numpy、 requests、json和matplotlib。系统接收文本文件作为输入，文本中包含需巡检台站的台站名，经度和纬度三列，字段间采用逗号分隔，生成路径规划图作为输出（图2）。

图2 系统流程图Fig.2 System flow diagram.

以临沧中心站所需运维的临沧市、普洱市和西双版纳州三地州57个预警基准站为例，输入包含临沧中心站在内的58个台站名及经纬度的文本文件，模拟从临沧中心站出发，途径所有基准站巡检一圈，回到临沧中心站的巡检记录。迭代次数分别选择200次， 400次， 800次， 1200次， 1 600次，2000次，2500次，3000次，4000次；样本个数分别选择50， 60， 70；变异概率设置为25%。迭代2500次，样本个数选择60时获得最优结果（图3右图），巡检行驶距离4869.41 km，过路费共计439元。

遗传算法通过交叉、变异、合并、选择等操作既实现了收敛，又能保持全局性，不至于陷入局部最优。从图4可以看出，巡检距离在200次迭代内斜率较大，下降较快；200至2000次迭代时下降趋于平缓，2000次迭代后巡检距离趋于稳定。由于遗传算法存在一定随机性，相同条件下并不是迭代次数越多结果越好。

从图5可以看出，候选种群个体个数设置为60比较合适，种群个体太多容易造成混乱，不易收敛到最佳。本系统设置的超参数包括迭代次数、种群个体数和基因突变概率，可编写函数对不同参数组合结果进行测试，寻找满足当下情况的最佳计算结果。在回到原点且无明显绕行的几条巡检路线上，行驶距离最大差距为3 306 km，过路费差距1 177元；行驶距离最小差距401 km，过路费差距44元。因此可以认为，即使是迭代趋于稳定的且看似较为完美的巡检路径，与近似最优的巡检差距依然在百公里之上。

图3 临沧、普洱、西双版纳地区基准站分布及最优巡检路线示意图Fig.3 The distribution of benchmark stations and schematic diagram of the optimal inspection path in Lincang，Pu′er and Xishuangbanna regions

图4 巡检距离迭代示意图。Fig.4 Schematic diagram of inspection distance iterations.

图5 不同参数下巡检路线和巡检距离迭代示意图。Fig.5 Schematic diagram of inspection route and inspection distance iterations under different parameters.

当台站数量较少时，采用人工和遗传算法规划的巡检路径差距并不明显，但当巡检台站数量增加到几十个时，人工往往很难找出最优巡检路径，而利用遗传算法规划的台站巡检路径在同等条件下可以得到获得更低的巡检成本，从图5的几个巡检路径对比可以看出，即使人工选择的路径接近（c）（d）或（e）（f），与最优结果差距仍在百公里以上。由于地图服务的加入，计算结果比起直观判断两点直线距离更贴近现实，结果也更可靠，程序还可以估算出总的路程行驶时间，对台站巡检的行程规划具有一定的参考价值。

如果巡检任务存在分组同时进行的情况，则问题从TSP衍生为多旅行商问题（multiple traveling salesman problems，MTSP），即求解几个旅行商同时同地开始访问周边城市，访问路径不重复，最终再回到原点的最优方案问题。MTSP本质是设置了访问条件的TSP，因为多个旅行商如果只考虑路径成本而不考虑时间成本，最高效的方法还是单个旅行商走完全程。在本例中，只需给各组分配不同的巡检台站，各组实现局部TSP即可。

高德地图的郊区位置路径规划和API响应速度优于百度地图。作者在使用百度API对野外预警台站进行经纬度转换和路径规划时，部分位置存在报错情况，而使用高德API进行路径规划时，经过几千次调用并未出现异常，API响应速度也更快。高德API还提供了丰富的路径规划选项，不仅可以选择速度优先，距离优先、不走高速、避让区域和道路等，还可以选择车辆类型（纯电动车、混动车和一般汽车），合理规划行驶路径。值得一提的是，高德API每天的请求次数有限额，使用完当天限额需申请提额。