基于轨迹大数据的路径优化算法

Path Optimization Algorithm Based on Trajectory Big Data

摘要

基于单兵移动轨迹进行行动预测和路径优化的方法被提出。以智能化单兵多跳中继通信系统为前端，获取单兵的轨迹数据并实时传回到指挥控制后台，在后端综合运用数据存储、轨迹预处理、标记任务点、聚类点分析、轨迹分段等实现轨迹数据管理，最后，采用相似性度量算法等开展了最优路径求解计算。结合地试验数据，经验证，表明绘制的轨迹图与实际行动相符，优化后的路径具有距离短、信号覆盖率大等特点，有实际应用价值。

Abstract

An action prediction and path optimization method based on individual soldier movement trajectory is proposed in this paper. First, the intelligent individual soldier multi-hop relay communication system is used as the front-end to obtain individual solider trajectory data, which is then retured to the command and control background in real time. Second, in the back-end, data storage, trajectory pre-processing, marking task points, clustering point analysis, trajectory segmentation are comprehensively used to realize trajectory data tube. Finally, similarity measurement algorithm is employed to deduce the optimal path. Based on the test data of a certain area, the verification results show that the trajectory map drawn is consistent with the actual action, and the optimized path has the characteristics of short distance and large signal coverage, which has practical application value.

Graphical abstract

关键词

大数据 / 轨迹 / 路径优化 / 聚类 / 多跳中继

Key words

big data / trajectory / path optimization / clustering / multi-hop relay

0 引言

海警肩负着海上维权执法任务，由于受现有通信手段制约，经常出现任务分队与指挥舰船之间通信通联不畅等问题，很难远程获取执勤人员的运动轨迹和行动路径，更难于在事后对每次行动做准确地记录取证与复盘分析。随着智能化单兵多跳中继通信系统在海警某部的试用，一种同时具有语音通信、数据传输、北斗定位功能的多跳自组网单兵电台，可以在每次行动过程中将佩戴电台的单兵移动轨迹及时回传到远端指挥控制中心平台。正是基于已获取的大量轨迹数据，行动路径优化研究才能开展^［1］。

实际上，在民用领域已开展了基于轨迹数据的路径分析^［2-3］、行为预测^［4-5］等研究工作，并先后在叫车服务^［6-7］、交通规划^［8］等方面得到了应用。文献[9]提出了在综合考虑时空约束的轨迹相似性度量方法基础上，增加停留点语义信息来获得更加合理的热点路径。文献[10]提出了采用动态时间弯曲解决高维不等长轨迹数据点的距离度量问题，从而完成了监控视频的异常轨迹行为检测。文献[11]针对态势显示系统中机动目标运动状态不确定、卫星定位误差、接收机随机噪声造成的目标轨迹估计精度低的问题，提出了一种基于新息协方差的Kalman滤波算法，实现了加速度方差的实时估计和自适应调整。文献[12]提出了通过挖掘出时序轨迹中的固定活动点以及频繁路径，可以生成个性化的路径网络。文献[13]提出了轨迹数据的管理包括数据清洗、数据存储、相似性度量、轨迹搜索和分析、上端应用等。尤其是指出作为一种新技术，深度学习在合成数据生成、表示学习和移动预测^[14]方面取得了进展。另一个有前景的主题是在线深度轨迹学习^[15]，以满足对动态轨迹数据及时决策的需求^[16-17]。文献[18]指出，轨迹数据语义丰富，蕴含着各种移动对象的时空和行为信息，被广泛应用在诸如大众化经验路径推荐、交通路况精准预测、城市规划智能决策、个性化服务与活动推荐、出租车服务等方面，应建立轨迹数据管理系统。文献[19]提出了将轨迹转换为知识图谱结构的方法。该方法结合轨迹数据的特点及知识图谱的定义，分别抽取出轨迹数据的实体、关系、属性并构造了轨迹图谱，大大提高了轨迹数据查询检索效率。文献[20]研究了将轨迹时空数据和地理静态信息相融合的方法，提出了基于兴趣点的预测框架，用于预测下一个时间段目标区域的停留点变化情况。文献[21]利用出租车轨迹数据来开展载客热点区域的挖掘以及对该区域空间活动特征的研究，并结合城市公交信息给出了出租车承担城市综合交通系统运力补充的综合分析结果，为完善和提高城市管理水平提供了参考。文献[22]给出一种基于轨迹欺骗的GPS导航干扰方法，综合转发式欺骗干扰和生成式欺骗干扰的特点，利用GPS接收机获得目标当前粗略位置欺骗信号参数，生成高度拟真的欺骗信号并发射，可在不同条件下实现对GPS接收机的有效欺骗。

本文首先介绍了如何获取轨迹数据，其次详细说明了对历史数据的管理和分析方法，最后给出了基于轨迹大数据的最优行动路径求解公式。结合海警某部在某地历次维权执法行动的数据验证表明，基于所提的智能化单兵多跳中继通信系统指挥控制软件具备对轨迹数据的记录、回放功能，同时能根据任务点和聚类点自动求解行动路径，而且可结合通信系统信号强弱和多跳中继状态优化推荐最佳行动路径。这既大大提高了部队对每次行动的现场掌控和事后分析能力，又可为指挥人员针对特定目标和地域等条件形成推荐战法提供有力支撑。

1 轨迹数据获取

智能化单兵多跳中继通信系统是由多个固定台和移动台组成的多跳自组网系统，这两型电台都具有多跳中继、高接收灵敏度、对空引导等多波形通信能力，支持语音、即时消息、北斗定位信息传输功能，能够在复杂海况条件下，以不超过6跳中继方式，覆盖直径不小于24 n mile的区域（假设单个移动台的海上最大通信距离为3 n mile，理想状态下以不少于37个移动台采用蜂窝状布局），如图1所示。

在数字组网状态下，每个移动台都可以将内置北斗接收机的定位信息以网络多跳中继方式发送到远端固定台上。通常固定台都安装在指挥舰船上，移动台由执行任务的单兵以背夹方式佩戴在战术背心上。暂时不考虑指挥舰船的运动问题，轨迹数据只记录单兵行动过程中的定时、定位、信号强弱等数据。

对于1个记录点的定义如式（1）所示：

P=(x,y,t,s)（1）

式中：x\mathrm{、}y为P点的平面坐标值；t为P点时刻；s为P点信号强度。用3个维度定义了1个轨迹点的信息，即空间域、时间域和信号域，从而为后续轨迹分析及行动规划提供了较好的数据基础。

移动台每隔30 s（间隔可设置）会将P点信息采样回传给固定台，固定台收到后将这些轨迹数据后即可开展轨迹数据管理和分析。

2 轨迹数据管理

2.1 数据存储

使用MySQL数据库存储P点数据，可以支持单一查询类型，例如范围查询（在矩形中查找轨迹）。尽管一些地理空间数据库如ArcGIS、Tile38、PostGIS、GeoMesa，也可以扩展用于轨迹管理，但考虑到系统平台的适用性，仍然选择了MySQL数据库并对其进行了扩展，使其支持线段的存储和查询、范围查询和邻近算法查询。

2.2 轨迹预处理

由于95%的轨迹数据通常都包含有噪声，因此需要对有偏差的轨迹数据进行清洗。通常采用的方式为结合道路特征和多次历史数据比对的方法。

1）首次行动数据。对于首次采集的轨迹数据，需要优先约束到就近的道路上，除非当前任务为非道路行动。如果是约束到道路网络的，可以采用霍夫曼编码对每个路段进行唯一编码，每个轨迹都可以简洁地表示为码字的串联，这样形成的轨迹数据压缩比更高。约束到道路的数据处理方法一定要提前进行人工干预，避免丢失非道路行动信息。

2）重复行动数据。对于重复行动数据，完全可以采用轨迹简化，即叠加多次数据后剔除明显偏离的噪声值，修正因个别数据缺失造成的轨迹不连续。修正偏离和轨迹简化也应引入人工审查，避免丢失有用数据，特别是一些响应规划外行动信息。

3）标记任务点。任务点（Point of Target, POT）是每次任务需要处置的对象的地理定位信息，POT由指挥人员在每次行动前标记，POT可以有多个，如式（2）所示：

T_i=\{x_i,y_i\}（2）

式中，x_i、y_i为第i个任务点T_i的坐标。通常，标记POT后，总可以找到若干条朝向任务点的主轨迹线，这些主轨迹线以及其他一些辅助轨迹线构成了轨迹预处理结构图，如图2所示。

3 轨迹分析

3.1 聚类点分析

聚类点（Point of Clustering, POC）主要分析不同行动轨迹的聚合点，用于识别行动过程中重要的集合区域、协同区域以及与POT的重合区域。由于事先并不能严格地规定现场行动路径，只有根据多次行动轨迹的聚类点分析，找到每次行动的必然规律，即在什么地方集合、在什么地方协同移动、在POT如何开展行动等，采用了多轨迹k-means算法进行POC分析。其基本思路如下。

首先假定任意两个轨迹之间连线为最小距离K_min；在两个轨迹间移动这根连线，当发现当前距离小于K_min时令K_min=当前值；遍历完整个轨迹线后找到K_min点即为POC点。

如果有多个POC点，则剔除当前K_min点后重复搜索的步骤直至找到下1个K_min点。

使用K_min点去验证其他轨迹线是否也保持距离最近或相对较近，从而确认k-means值确保所有POC点都不再变化。

采用POC分析4条轨迹线后识别出的两个聚类点，如图3所示，其中第1个点（图中虚线圆圈部分）为行动出发点，第2个点（图中虚线椭圆部分）为行动聚集点。

3.2 轨迹分段

对于特别长的轨迹，在存储、检索、分析等方面都会带来较大的系统开销，且很容易造成算法不收敛。可以采用自动或人工两种方式，将一个特别长的轨迹划分为若干较短的轨迹，表示为

T_{\mathrm{r}\mathrm{a}\mathrm{j}}={\displaystyle \sum _{i=\mathrm{1}}^n}{T}_{\mathrm{r}i}（3）

式中：T_{\mathrm{r}i}为第i段短轨迹；T_{\mathrm{r}\mathrm{a}\mathrm{j}}为长轨迹。

轨迹分段的原则可以根据POT或POC分段、根据两个轨迹交叉点/临近点分段、根据轨迹总长的平均值分段，也可采用人工手段强制分段。分段后，每一片段轨迹的处理方法同前面所述，只是相同轨迹分段后各段之间不做计算，根据时间戳t的不同，选择不同分段参与其他段对应时间戳的计算。

4 最优路径求解

4.1 常用算法

在其行动中，最优路径并非最短路径，它往往需要和POT设置、地形地貌、通信系统和北斗定位信号强弱、以及战法预案中的POC设置有关。因此，选择了以下假定条件进行优化求解。

1）POT设置优先。即如果在行动中设置了一个或多个POT点，则路径算法优先围绕POT进行求解。

2）POC设置优先。即如果在行动中设置了一个或多个POC点，则各路径在相应时空点应满足POC会聚要求。

3）信号强弱优先。即如果在行动中出现轨迹点会造成信号中断的，则规避路径以满足信号连续性要求。

4）道路匹配优先。即如果在行动中要求就近使用道路，则路径尽可能沿地图中现有道路展开。

5）历史数据优先。即如果在行动中需要参考历史数据，则采用相似性度量方式挖掘出热点路径推荐。

1）~4）的算法都比较容易实现，重点研究历史数据优先的求解过程。

4.2 相似性度量算法

时空相似性度量（Spatio-Temporal Similarity Measure）描述了两个轨迹在时间和空间上的相似程度。轨迹T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_i}\mathrm{、}{T}_{\mathrm{r}\mathrm{a}{\mathrm{j}}_j}的相似程度表示为

\mathrm{S}\mathrm{i}\mathrm{m}(T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_i},T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_j})=\frac{L_c(T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_i},T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_{\mathrm{j}}})}{L(T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_i})+L(T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_j})-L_c(T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_i},T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_j})}（4）

式中：L_c(T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_i},T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_j})表示轨迹T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_i}和轨迹T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_j}重叠子轨迹累积长度；L(T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_i})、L(T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_j})表示轨迹T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_i}、T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_j}在空间或时间特性上的累积长度。

根据以上定义，两个轨迹的空间相似度(Spatial Similarity, 简称为SimS)与时间相似度（Temporal Similarity, 简称为SimT）可分别计算。两个轨迹的时空相似度（Spatio-Temporal Similarity, 简称为SimST）可由空间相似度与时间相似度的乘积得到，表示为

\mathrm{S}\mathrm{i}\mathrm{m}\mathrm{S}\mathrm{T}(T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_i},T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_j})=\mathrm{S}\mathrm{i}\mathrm{m}\mathrm{S}(T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_i},T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_j})\cdot \mathrm{S}\mathrm{i}\mathrm{m}\mathrm{T}(T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_i},T_{\mathrm{r}\mathrm{a}{\mathrm{j}}_j})（5）

通过计算相同区域内若干条轨迹的相似性，可以形成针对某个行动任务的特定轨迹预测，进而在下一次行动前，提前规划战术路径和行动预案。

例如，不考虑时空相似度情况下的行动轨迹表现为分布在大量区域内的离散点集合，如表1所示。

考虑时空相似度情况下，行动轨迹表现为聚集在POC区域内的聚集点集合，如表2所示。

在表2所述轨迹簇基础上，设置分段轨迹权重阈值为0.5，分析每个子轨迹在各轨迹簇的权重并发现热点路径，进而即可推荐出关注程度最高的优化路径。

4.3 路径优化算法

结合前面提到的多种算法，提出了一种具有自动识别POT和POC点、能自适应接入节点信号强弱、可根据道路数据和历史数据优先匹配的路径优化算法，该算法流程如图4所示。

在路径优化过程中，系统给出各种优先模式下的路径选择权重值w_i，由人工方式做出选择，并将实际结果对权重的影响反馈到w_i^{\text{'}}中，通过（w_i^{\text{'}}-w_i ）实现累积修正。后期，可以考虑通过隐马尔科夫（Hiden Markov Model, HMM）模型等人工智能算法增强路径优化的自动化和智能化水平^[23]。在相似性度量算法的基础上，当前围绕POT从POC展开，首先还是要保证通信系统信号传输稳定可靠，使得多跳中继状态得以延续，这主要依靠多跳系统拓扑结构冗余性、单跳信号的灵敏度和通信距离保证。具体为信号强弱分析过程中的网络节点分析和信号灵敏度分析，这里就不赘述。

5 试验验证

图5为未计算轨迹的某分队在某岛礁记录点信息，图6为转化为行动轨迹的图例。

图7为设置POT和POC点后的轨迹分析，图8为软件计算的相似行动下推荐路径。

通过试验数据和模拟绘制的轨迹路径可以看出，当前软件推荐路径如图8所示与历史轨迹如图5所示相比，只需要较少的节点（即投入较少力量），沿历史轨迹（即少走弯路），围绕POT从POC展开（即选择了针对POT从POC展开的最短路径），且保持了各节点间相对接近的距离（实现每跳间信号有效情况下通信距离最远），可以实现最大的行动部署效能。

6 结束语

本文只是初步探讨了基于智能化单兵多跳中继通信系统在武警部队海上登岛/礁行动中进行轨迹数据采集和行动路径优化的尝试，还缺乏大量轨迹数据进行支撑以利于做更深入研究。同时，在本文中，也仅仅考虑了单一静止目标，暂未考虑多目标或目标移动等情况，且路径优化求解时并未引入地形地貌对各节点间信号的影响因素。但是，所述成果对于武警部队乃至其他各军兵种部队在日常训练、应急行动和作战任务中的行动规划有着很好的启发意义。未来完全可以在累积了大量轨迹数据的基础上，引入轨迹知识图谱，加强多信源数据融合和挖掘力度，不断优化路径算法，推出更贴合实际的行动预案甚至战法创新。

参考文献

[1] 周旦，孙家煜，顾国斌，基于轨迹数据的出租车司机寻客路径优化方法［J］.重庆交通大学学报（自然科学版），2024，43（1）：83-90.

[2] 赛斌，曹自强，谭跃进，基于目标跟踪与轨迹聚类的行人移动数据挖掘方法研究［J］.系统工程理论与实践，2021，41（1）：231-239.

[3] 段宗涛，任国亮，康军，基于频繁轨迹序列模式挖掘的路径推荐方法［J］.太原理工大学学报，2022，53（2）：240-247.

[4] 谢添丞，乔少杰，张桃，基于情景感知与移动数据挖掘的行人轨迹预测方法［J］.无线电通信技术，2023，49（4）：606-615.

[5] 杜泉成，王晓，李灵犀，行人轨迹预测方法关键问题研究：现状及展望［J］.智能科学与技术学报，2023，5（2）：143-162.

[6] 王桐，高山，龚慧雯，基于分时MDP的出租车载客预测推荐技术研究［J］.通信学报，2021，42（2）：37-51.

[7] 韩勇，樊顺，周林，基于聚类算法的出租载客点时空分布特征研究［J］.中国海洋大学学报（自然科学版），2019，49（）：155-162.

[8] 年光跃，黄建云，潘海啸.基于机器学习空间聚类的出租车停靠站点布局规划［J］.交通运输研究，2024，10（1）：10-17.

[9] 夏英， 温海平， 张旭. 基于轨迹聚类的热点路径分析方法［J］. 重庆邮电大学学报（自然科学版），2011，23（5）： 602-606.

[10] 康凯， 王家宝， 刘方鑫. 基于轨迹聚类的公共安全异常检测［J］. 计算机工程与应用，2016，52（14）：7-11.

[11] 张强， 孙红胜， 胡泽明. 基于新息协方差的机动目标轨迹估计算法研究［J］. 信息工程大学学报，2012，13（6）：93-97.

[12] 袁华， 钱宇， 杨锐. 基于GPS轨迹的用户兴趣点及路径挖掘研究［J］. 系统工程理论与实践，2015，35（5）：1276-1282.

[13] WANG S， BAO Z， SHANE CULPEPPER J， et al. A survey on trajectory data management， analytics， and learning［J］. ACM Computing Surveys， 2021，54（2）：39.

[14] 向晓倩，陈璟.基于双重注意力时空图卷积网络的行人轨迹预测［J］.浙江大学学报（工学版），2024，58（12）：2586-2595.

[15] 栗波.基于深度学习的轨迹挖掘算法研究［D］.青岛：青岛科技大学，2023.

[16] 赵涛，张宁，王小超，基于图神经网络轨迹预测的合流区交通冲突预测方法［J］.山东大学学报（工学版），2024，54（2）：36-46.

[17] 张小芳，冯慧芳.基于轨迹大数据的动态最优路径规划［J］.计算机与现代化，2021（11）：82-88.

[18] 许佳捷， 郑凯， 池明旻， 轨迹大数据： 数据、应用与技术现状［J］. 通信学报，2015，36（12）：97-105.

[19] 吴瑕， 赵小明， 余建坤. 轨迹图谱： 一种基于知识图谱结构的轨迹信息抽取方法［J］. 计算机应用研究，2020，37（11）：3255-3262.

[20] 孙瑞， 胡亮. 基于轨迹和POI数据的热点区域实时预测［D］.长春：吉林大学，2017.

[21] 赵玲， 王建伟. 基于出租汽车轨迹数据的城市载客热点区域挖掘发现及空间活动特征研究［D］.西安：长安大学，2017.

[22] 廖琪， 郝金明， 郑娜娥， 基于轨迹欺骗的GPS导航干扰试验研究［J］. 信息工程大学学报，2020，21（2）：17-21.

[23] 卞大鹏，余珊珊，张诗，基于隐式马尔科夫模型的舰队应召搜潜方法［J］.中国舰船研究，2019，14（6）：192-200.