露天矿导航系统总体架构设计与关键技术研究

钟小宇 赵庆丰 孙效玉 孙 健 肖开泰6

（1.鞍钢集团鞍千矿业有限责任公司，辽宁鞍山112000；2.东北大学智慧矿山研究中心，辽宁沈阳110819；3.东北大学资源与土木工程学院，辽宁沈阳110819；4.紫金矿业集团股份有限公司，福建龙岩364000；5.鞍钢集团矿业公司，辽宁鞍山112000；6.煤科集团沈阳研究院有限公司通风防灭火研究分院，辽宁抚顺113112）

露天矿道路网是露天矿设备行驶的道路和关键点（装载点、卸载点、停车场、加油站等）的集合，通常分为固定道路、半固定道路、移动道路、临时道路4种类型，具有空间形态复杂、路段性质与动态变化不一的特点［1］。露天矿运输设备规格大，驾驶室在卡车左侧，前方与右方视线被遮挡，存在较大盲区与安全隐患［2］。露天矿生产环境复杂，存在灰尘、风沙、夜间照明效果不佳、能见度较低等问题［3］。上述特点导致驾驶员在行驶过程中容易走错路，行驶的安全性较低。因此，开发露天矿导航系统十分必要。

目前导航系统按平台可大致分为3类：基于地理信息系统平台的导航系统［4］（借助 ArcGIS［5］、MapX［6］、SuperMap［7］、MapGIS［8］等软件提供的二次开发接口开发导航系统），基于电子地图服务的导航系统（借助百度地图 API［9］、GoogleMap API［10］等提供的二次开发接口开发导航系统），基于自主开发式电子地图的导航系统（借助Unity3d［11］、C++［12］等自主开发导航系统）。

针对露天矿运输设备运行过程中存在的问题，结合当前导航技术的最新进展，设计了系统总体架构与道路网络结构，自主开发了后台的标准算法接口（导航路径规划算法、路网匹配算法、运行距离与时间预测算法和路口转向提示算法）。考虑到部分露天矿山采用了卡车调度系统，但缺乏导航功能，因此开发了适用于卡车调度终端的独立导航；针对部分露天矿山没有安装卡车调度终端的问题，开发了百度地图导航，可用于手机等其它终端。

1 系统总体架构设计

系统总体架构如图1所示，本研究将系统总体架构分为数据访问层、业务逻辑层、接口层、应用层4层，各部分特征论述如下。

（1）数据访问层。数据访问层主要实现对基础数据、流水数据、道路网数据的访问。基础数据存储设备、司机、生产计划等基础信息；流水数据存储车载终端上传的数据，包括设备位置、状态、速度、方向等信息；道路网数据为露天矿道路网的数据信息。

（2）业务逻辑层。业务逻辑层实现系统业务逻辑的处理，为后台标准算法，接口层将其封装为接口，应用层通过接口调用后台标准算法，包括导航路径规划、路网匹配、运行距离与时间预测、路口转向提示算法。导航路径规划算法用于规划起点到终点的导航路径，路网匹配算法用于将定位点进行修正并匹配至对应的路段上，运行距离与时间预测算法用于计算到达目的地的距离，路口转向提示算法用于判断前方路口左右转向，进而进行语音提示。

（3）接口层。接口层将业务逻辑层的算法进行封装，给外部应用提供了访问接口，分为导航算法接口、百度地图接口两部分。其中，导航算法接口包括导航路径规划算法、路网匹配算法、运行距离与时间预测算法、路口转向提示算法接口；百度地图接口包括地图初始化、折线绘制、覆盖物添加等接口，用于实现前端图像绘制。

（4）应用层。应用层分为独立导航、百度地图导航两部分。独立导航通过调用导航算法接口实现导航功能，独立导航主要用于车载终端；百度地图导航通过调用导航算法接口与百度地图接口实现导航功能，百度地图导航主要用于手机等其他移动终端。

通过以上架构可知，接口层将应用层的应用与业务逻辑层的标准算法分开，应用层各部分的应用可以通过接口层的接口调用标准算法，使得系统能够解决实际问题，适用于不同矿山，加快了开发进度，加强了系统的实用性、通用性、扩展性。

2 道路网结构设计

2.1 道路网定义

露天矿道路网拓扑关系如图2所示，具体定义论述如下：

定义1（节点）。节点是矿区坐标系中任意一点，包含坐标x、y、z，是道路分岔口、路段起始点或终止点，节点所组成的集合为B={ }B1,B2,B3,…,Bn,n∈N。

定义2（间断点）。间断点是矿区坐标系中的任意一点，包含坐标x、y、z，间断点与间断点间由直线连接，间断组成的集合为A={ }A1,A2,A3,…,An,n∈N。

定义3（关键点）。关键点属于节点，记为kx，x∈N，其中kx∈B，表示排卸点、停车场、加油站等露天矿地点。

定义4（路段）。路段起始于一节点Bi连接于另一节点Bj,i,j∈N，由一系列有序的间断点依次连接成的 直 线 所 组 成 ，可 表 示 为 rs:Bi—Bj,i,j∈N，其 中Bi、Bj∈ B，。图2中B1—B2为路段。

定义5（道路网）。道路网由有限的路段组成。

定义6（路径）。起始于一节点终止于一节点的有序的路段集合，可表示为rp:B1—B2—B3—…—Bn,n∈N，其中B1,B2,B3,…,Bn∈ B。图2中B1—B2—B4为路径。

定义7（区域）。由有序的间断点依次连接成的直线组成的多边形，可表示为 aq:C1—C2—C3—…—Cn,n∈N，其中C1,C2,C3,…,Cn∈A，表示关键点范围。图2中C1—C2—C3—C4—C5为区域。

定义8（导航路径）。起始于一节点终止于一节点的有序的间断点集合，可表示为np:A1—A2—A3—…—An,n∈ N，其中 A1,A2,A3,…,An∈ A。图 2中A1—A2—A3—A4为导航路径。

2.2 道路网类结构

根据道路网定义，节点与间断点为基础部分，节点序列组成路段，路段序列组成路径，间断点序列组成区域和导航路径。据此，建立了点、路段、区域等道路网结构，在此基础上采用面向对象技术，首先建立了节点类与间断点类，进而建立了路段类、区域类、路径类、导航路径类，后续开发的算法通过接口调用道路网结构实体。类结构属性如图3所示，各类之间的组合关系构成了道路网数据结构。

节点类：点名称表示关键点的名称，坐标x、y、z表示关键点的位置。间断点类：坐标x、y、z为间断点的位置。路段类：开始节点与终止节点为路段的开始节点号与终止节点号，间断点集合为路段中所有间断点实例的集合。路径类：路段集合为路径中所有路段实例的集合。导航路径类：间断点集合为导航路径上所有间断点实例的集合，路段集合为导航路径中所有路段实例的集合，路径类为后台各算法服务，导航路径类则用于为前端返回最终路径的详细间断点坐标，以具体的间断点集合来表示。区域类：一个区域对应一个间断点集合，间断点为区域多边形的顶点。

3 导航关键算法研究

3.1 导航路径规划算法

导航路径规划算法即根据当前位置、目的地位置、道路网数据返回当前位置到达目的地的路径。

道路网可视为图的数据结构，定义为G(V ,E)，V为顶点，E为边。常用最短路算法有Floyd（弗洛伊德［13］）、Dijkstra（迪杰斯特拉［14］）、Bellman-Ford（贝尔曼-福特［15］）等，算法的时间复杂度（未经其他措施进行算法优化）分别表示为O(V3)、O(V2)、O(V E)。露天矿道路网中不存在负权值的边，道路网节点（顶点V）有数百个，数据规模较小，对于时间复杂度要求不高，相比于其他算法，Floyd算法更适用于多源最短路径，运用一次算法就可求得任意两个顶点的最短路径，且简单易用，故本研究选取该算法作为导航路径规划算法。

利用数据结构中图的思想，构建了节点与节点之间的邻接矩阵S（n×n阶矩阵，n为节点数量）。为存储图中节点到节点的距离，建立了矩阵P（n×n阶矩阵，n为节点数量）记录两个节点之间的插入点。Floyd最短路径算法步骤如下：

（1）初始化邻接矩阵S。当两个节点有通路时，依次计算两个节点间的相邻间断点的直线距离，累加即可得到两个节点间的最短距离。当两个节点无通路时，设置该距离为所用数据类型的最大值。当两个节点相同时，设置距离为0。

（2）初始化矩阵P。矩阵P中的元素值为所在列的下标值，经过两次循环遍历矩阵P为元素赋初始值。

（3）基于状态转移方程s[i,j]=min{s[i,k]+s[k,j],s[i,j]}（i、j为矩阵行标、列标，s[i,j]为第i节点到第j节点间的距离，k为0至n之间的任意数，n为矩阵s的阶数）寻找两节点间是否存在插入点k，使得i节点经过插入点到达j节点的距离最短，若s[i,k]+s[k,j]＜s[i,j]，则更新矩阵s与矩阵P对应的值。

（4）在P矩阵中得到起始点、插入点、终止点所组成的节点序列。

3.2 路网匹配算法

由于GNSS的定位精度较低及道路更新不及时，定位点与实际的道路可能存在偏离，需通过路网匹配算法进行修正，以匹配至正确的路段上。

路网匹配算法大致可以分为4类［16］：几何匹配算法［17］、拓扑关系算法［18］、概率统计算法［19］、先进匹配算法［20］。露天矿道路网的拓扑关系较简单，几何匹配算法在道路网拓扑关系较简单的情况下匹配稳定性较好，故本研究选用了几何匹配算法。几何匹配算法可细分为点到点、点到线、线到线匹配算法，点到线匹配算法比点到点匹配算法准确性高，比线到线的匹配算法计算量小，故选用基于几何学点到线的路网匹配算法。步骤为：

（1）定义垂线长度l、定位点所在路段号R、垂足坐标C，进行初始化：l=+∞、R=-1、C=(0,0)。

旅行社实现规范化经营管理有很长的路要走。应完善相关制度体系，按照规范化管理的要求稳步推进各项工作有序开展。在进行旅游产品创新时，旅行社应积极寻求有关部门支持，实现旅游地和旅行社的双赢。各地应提高对旅游业发展的重视程度，鼓励旅行社研发具有地方特色的旅游产品和开展规范化运营，从而带来丰厚的经济效益。

（2）由定位点X直线序列中的直线（由路段中相邻间断点连接而成）作垂线，若直线遍历完毕，则退出并输出垂足坐标C与所在路段R。若垂足的x、y坐标值不在直线上，则继续执行步骤（2），否则，执行步骤（3）。

（3）若垂线长度小于l，则将l更新为该垂线的长度，并将C更新为该垂足，将R更新为直线所在的路段，继续执行步骤（2）。

3.3 运行距离与时间预测算法

定位点实时更新时，应实时显示当前定位点与目的地的距离以及行程时间。将定位点与道路的关系简化为点到线的关系，距离应等于修正后的点在匹配路段的剩余长度与导航路径中其他路段长度的总和。算法步骤为：

（1）定位点经过道路匹配算法修正并匹配至对应路段。

（2）基于距离最近原则匹配对应路段中距离定位点最近的间断点，以该间断点开始到对应路段尾间断点结束，依次累加相邻间断点的距离，得出本路段的剩余长度。

（3）遍历导航路径中的剩余路段，依次累加所遍历路段的间断点序列中相邻间断点的距离，得出导航路径中剩余路段的长度。

（4）累加步骤（2）与步骤（3）中计算的长度，得出定位点至终止点的距离，退出算法。

3.4 路口转向提示算法

在交叉路口应提示左右转向，需要使用路口转向提示算法，步骤为：

（1）定位点经过路网匹配算法修正并匹配至对应路段。

（2）若定位点与路段尾节点距离小于50，则执行步骤（3），否则，退出算法。

（3）令当前路段的起始节点坐标、终止节点坐标分别为A(x1,y1)、B(x2,y2)，导航路径中下一路段终止节点坐标为P(x3,y3)，令转向因子s=(x1-x3)⋅(y2-y3)-(y1-y3)·(x2-x3)。

（4）若s＞ 0，返回“左转”；若s＜ 0，返回“右转”，退出算法。

4 系统接口实现

系统的部分功能通过调用接口层所封装的算法接口来实现，部分功能在其上进行扩展，故而本研究首先实现了系统的接口，然后对独立导航、百度地图导航进行开发。接口实现如下：

4.1 导航算法接口

（1）导航路径规划算法接口。double［］The Shotest Path（int startPoint，int endPoint），规划开始节点到终止节点间的导航路径，其中startPoint为开始节点，endPoint为终止节点，返回的double类型数组为路径的间断点集合。

（2）路网匹配算法接口。double［］The Road Network Matching（double x，double y，double z），将定位点进行修正并匹配到路段上，其中x、y、z为定位点的x、y、z坐标值，double数组前3位为修正后的x、y、z坐标值，第4位为点所在的路段号。

（3）运行距离与时间预测算法接口。double Update Distance（double x，double y，double z，int［］path-Section），获取到达目的地的距离，其中x、y、z为定位点的x、y、z坐标值，pathSection数组为导航路径的路段集合，返回的double类型值为到达目的地的距离。

（4）路口转向提示算法接口。string Turn Around（double x，double y，double z，int［］pathSection），判断路口左右转向，其中x、y、z为定位点的x、y、z坐标值，pathSection数组为导航路径的路段集合，返回的string类型值为左右转向。

4.2 百度地图接口

（1）地图初始化接口。center And Zoom（center:Point，zoom：Number），地图初始化，Point为地图中心，Number为级别。

（2）折线绘制接口。Polyline（points：Array＜Point＞，opts：PolylineOptions），创建折线覆盖物对象，Array＜Point＞为折线的转折点，Polyline Options为线的属性。

（3）标注创建接口。Marker（point：Point，opts：Marker Options），创建图像标注实例，Point为标注的坐标，Marker Options为标注的属性。

（4）覆盖物添加接口。add Overlay（overlay：Overlay），将覆盖物实例（折线、标注等）添加到地图中，Overlay为覆盖物。

5 系统应用开发

本研究以华能集团伊敏露天矿的道路网数据为基础进行了导航系统开发，该系统包括独立导航、百度地图导航两部分。独立导航部分开发语言为C#语言，采用Visual Studio 2015为开发工具，运行环境为.NET Framework 4；百度地图导航部分开发语言为Java、HTML、CSS、JavaScript，采用 eclipse jee 2019 为开发工具，java开发工具包为jdk1.8.0_91。

5.1 独立导航

终端界面如图4所示，界面中显示了道路网，规划了开始点到终止点的导航路径，可实现对地图的放大、缩小、平移等操作，实时显示设备的当前位置，箭头指向为设备的方位，同时每间隔固定时间提示到达目的地的距离与时间，在前方路口转弯处可提示左转、右转。

5.2 百度地图导航

5.2.1 地图显示与操作

导航系统的地图显示与操作界面如图5所示。界面最左侧提供了显示控制控件，点击控件或通过鼠标的点击、移动可实现地图的放大、缩小、平移功能，分别如图5（a）、图5（b）和图5（c）所示。

5.2.2 路径规划

导航系统的路径规划界面如图6所示，分别提供了二维地图、卫星地图两种显示模式，如图6（a）和图6（b）所示。图中560、680、二破为排卸点，2005、1205为装载点，箭头为当前设备的定位点，箭头方向为设备的朝向，开始点为设备的起始位置，终点为设备的目的地，图中规划了从一号机修厂前往装载点2005的导航路径。

5.2.3 信息实时更新

导航设备的位置、到达目的地的距离与时间、路口转向等信息会实时更新，界面如图7所示。卡车从一号机修厂前往装载点2005，运行至中途某点，箭头为设备的当前位置，到达装载点的距离为7.22 km。基于历史行车数据，统计该车的平均速度为20 km/h，预测该车到达装载点2005需耗时21.66 min。

6 结论

（1）将露天矿导航系统总体架构分为数据访问层、业务逻辑层、接口层、应用层4层，接口层为应用层与业务逻辑层之间的桥梁，具有较强的通用性、实用性和扩展性。

（2）基于Floyd算法、路网匹配算法、运行距离与时间预测算法、路口转向提示算法，开发了导航路径规划、定位点修正与路段匹配、到达目的地的运行距离与行程时间预测、路口转向提示等功能，导航功能全面、实用、可靠。

（3）导航算法与应用有效分离，通过接口实现有效衔接，既可实现自主独立运行，用于卡车调度系统终端；也可兼容百度地图，用于手机App导航，通用性和扩展性强。