基于改进RRT算法的露天矿路径优化模型

黄金彪，白润才，刘 威，柴森霖，刘光伟

(1. 辽宁工程技术大学 矿业学院，辽宁 阜新 123000；2. 宁夏煤炭基本建设有限公司，宁夏 银川 750004；3. 辽宁工程技术大学 辽宁省高等学校矿产资源开发利用技术及装备研究院，辽宁 阜新 123000；4. 辽宁工程技术大学 理学院，辽宁 阜新 123000；5. 盐城工学院 经济管理学院,江苏 盐城 224051)

露天矿道路运输系统优化问题一直是矿山系统工程及规划、优化建模所需要重点考虑的关键问题之一，对于提高露天矿的产量规模、作业效率具有重要意义[1-4]。特别是，随着部分矿山产量规模及作业设备的逐步大型化，运输系统对于剥、采、排各系统的衔接纽带作用逐步凸显，原本静态的道路优化及路径规划方法难以应付复杂条件下的优化、规划任务。因此，尝试采用特定的优化、规划模型对露天矿运输道路及寻径问题进行有效求解，对于提高矿山产能及效率、优化现场生产调度流程将具有切实意义。

目前，国内外学者对于运输线路及运输系统规划问题研究主要集中于2类：① 为对矿山初始运输沟道的开拓定线及既有坑线的动态更新算法的研究，如余鼎[5]针对于山坡露天矿的特殊地理地形条件，提出山坡型露天矿开拓定线的具体方法；朱明海[6]结合厂矿道路规范内容要求提出了三维选线方法；刘光伟等[7-8]在时变运输功框架下，结合时空拓扑判别地方提出了全新的道路选线及线路更新判别算法；DIAZ等[9]从露天煤矿运输系统布置过程中的波动变化入手，提出了一种用于自动更新静态道路网络基有向图的新方法；② 为基于既有坑线形态及道路运输网络图进行寻径算法设计，此类研究的经典求解算法为以张幼蒂教授引入的有向图理论[2]及其发展模型为代表，如WHITE和OLSON[10]在静态有向图的基础上，基于场内等效距离全局最优化为目标，建立路径规划模型；HU[11]采用和声搜索算法设计了露天矿路径优化算法；LI等[12]提出了一种兼顾设备作业和时效性成本最小化的车辆线路优化策略；柴森霖等[13-15]在传统有向图规划建模的基础上，将时变运输功与时空拓扑连通性的方法引入到优化建模中，提出了路径规划及运输系统费用建模的全新方法。

近年来，随着人工智能、深度学习以及最优化理论方法的快速发展，国内外学者在机器人避障、运动学规划等多方面提出了大量效果显著成果，其中颇具代表性的算法如：张卫波等[16]在考虑存在大量复杂障碍物避障问题的前提下，基于改进搜索策略构建了智能机器人快速寻径算法；张玉伟等[17]基于启发式策略对RRT*算法的寻径策略进行了启发式修正；邹启杰等[18]基于强化学习框架驱动，提出了一种未知环境下机器人快速盲寻路径的规划算法。虽然上述方法在其领域范围内的实际应用情景中，均给出了自身运动规划过程的理想化解决方案，但由于露天矿山场景的独特性及其寻径策略间存在主、客观因素的自耦合现象，导致现有的此类优秀算法均无法被直接应用于指导矿山实际生产。

鉴于对露天矿寻径算法设计重要性的考量，笔者在前述成果的基础上，为进一步弥补现有算法在目标函数建模、执行效率等方面的局限问题，将改进RRT算法引入到求解露天矿路径规划问题中，尝试利用RRT算法的检索能力扩展寻径算法的备选路径解，从而进一步实现路径连通性计算与目标函数指标值计算的分离；另外，考虑到路面受到重载卡车频繁碾压及周期性养护作用，对现有的时变运输功模型[13,15]进行改进，建立全局时变成本的综合评价模型并将其作为规划模型的目标函数，给出了路面条件浮动状态的下评价模型估计方法，并最终结合改进的RRT算法实现对露天矿运输线路规划问题的快速求解。结合现场数据仿真实验，论证了文中算法对于解决露天矿运输线路规划、优化问题现实可行且有效。

1 RRT算法基本原理

快速搜索随机树算法(Rapidly-exploring Random Tree，RRT)是美国爱荷华州立大学的LAVALLE教授于1998年提出，是一种通过增量采样进行随机构建空间填充树的高效搜索算法，由于其算法自身的索引逻辑及特性对于提升非凸、高维空间的搜索效率具有极好的适应性，且无需提前对搜索区域的环境状态进行系统化建模或特殊的识别及几何划分，便可实现对存在代数约束(存在移动障碍的环境)或微分约束(局部动态或全局动态环境)的高维空间进行高效搜索，而被广泛应用于机器人避障、运动规划等相关问题的求解过程中。

对于经典RRT算法的执行逻辑原理如图1所示，其伪代码见表1。

图1 RRT算法基本原理

表1 经典RRT算法伪代码

表1算法中参数、方法定义及执行流程如下：Q为场景图，即道路网络图；qinit为选线起始位置节点；qgoal为选线目标位置节点；n为有向图中节点数量；R为最终搜索到的目标路径；r搜索路径的节点及有向边集合；rinit()为初始化备选路径的节点和有向边的方法。算法从qinit开始，循环遍历n个节点，其中i为当前遍历节点的索引。在遍历循环中，通过随机散布qrandom节点构造备选节点集，并通过查找距离qrandom节点最近的qnear节点来确定算法前进方向，前进方向上以step为前进步长，从而生产qnew节点。当具备qnew节点条件后，算法以qnew,qnear节点构建有向边，并最终通过CollisionFree方法判断当前路径是否可行，如可行，则确立当前路径，直至最终到达目标节点为止。

2 露天矿路径优化问题建模

2.1 模型的参、变量定义

为表述模型方便，现对模型中的参变量做如下定义。

(1)有向图参、变量定义：Ω={1,2,…,n}为道路网络有向图中的非空节点集合；ei,j=(i,j)∈E，为道路网络有向图中的非空节点i，j间的有向边，i,j∈Ω。其中，E为图中有向边集合。

(3)规划模型的决策变量：xi为有向边是否为最优路径的可行解。

2.2 约束条件

计算模型是对现实工程场景的合理抽象，故对于场景内的部分特殊的矿山工程条件，则需通过特定的指标值约束来进行有效表达。为进一步保证模型的合理性及完整性，笔者对模型中的数值型指标约束进行如下分类。

(1)道路网络图中任意单一有向边上的车流密度约束。

(1)

(2)

(2)道路网络饱和状态下全路径车流密度约束。

(3)

(4)

(3)寻径决策阶段的道路通过能力约束。

(5)

2.3 目标函数

当寻径算法选择不同的路段组合时，不仅会触发线路总长度、提升高度等运输功、能耗属性的变化，同时也会诱发路面平整度等能耗特征指标产生波动，加之重型卡车的频繁碾压与路面的周期性养护，会导致车-路系统间形成内蕴的耦合联系，并进一步促进功、能关系产生极为明显的时间效应[13-15]。鉴于对上述因素的综合考量，在寻径算法的规划建模中，以差异路段及周期性道路养护作用下的路面平整度分析为切入点，结合对路面平整度时效性变化的扰动分析，建立全局时变成本综合评价模型，并将综合评价模型确立为优化问题的全局目标函数，具体评价模型为

Q(t)=k1U(t)+k2C(φ)

(6)

式中，Q(t)为具有时间效应的综合评价模型；U(t)为时变运输功函数，表达形式如式(7)所示；k1为评价模型的能耗折算系数；C(φ)为以时变阻力系数的隶属度函数为参数的路面养护费用及成本估计函数；φ为分类型时变道路阻力系数(f(t))的隶属度函数；k2为路面养护费用函数的折算系数。

(7)

式中，Fei,j为有向图中任意有向边上的时变阻力的估计值。

2.4 模型中的波动参数估计

对比式(6)，(7)两组模型可知，模型中的未知参数主要分为：①k1，k2为2个未知参数；②U(t)，C(φ)均为未知估计。其中，k1，k2均为折算系数，为计算这部分折算系数及2组未知函数的估算结果，以神华新疆公司红沙泉露天煤矿为例，通过利用该矿部分生产运营数据及相关数理统计进行分析。从统计结果来看，对比U和C两组函数均匀滚动阻力的发展存在正向相关性，并通过对比该矿近4个月内会计统计出的吨公里运输及养护费用结果，将最终评价函数Q的线性权重指标定为k1=k2=0.5。

考虑到综合评价模型Q(t)主要包括U(t)(时变运输功函数)和C(φ)(浮动线路条件下的路面养护费用及成本估计函数)2个部分。其中，对于时变运输功函数，笔者团队曾给出具体的函数估计方法[13]。在前述成果介绍方法的基础上，以红沙泉露天煤矿生产运营数据为例，直接给出时变阻力系数的估算过程。其中，根据红沙泉露天矿测试路段的阻力特征变化分析结果，研究中将该矿测试研究路段共划分为4组不同类型路面，宏观路面特征描述及阻力系数变化范围数据见表2。

表2 红沙泉露天煤矿不同路面条件下的滚动阻力系数分类

当具备路面类型的分类基准后，采用趋势估计及最小二乘方法，建立不同路面类型下的滚动阻力系数随养护时间及累计物料量间的趋势面估计，具体的估计结果如图2所示。

图2 不同特征路面上的阻力系数估计结果

对于上述滚动阻力系数的精准估计是时变运输功计算及养护成本估计的重要基础，当给定任意时段的滚动阻力系数的估计函数形式后，按照前述方法其运输功计算则相对简单，但对于路面养护则容易因超载重车频繁碾压、集中降雨以及养护不及时等问题，极易诱发路面养护成本出现2次波动。为保证在养护成本计算过程中，可以对上述偶发性问题进行有效评估，以该矿采场南侧端帮不同水平上的2条平直运输干线为测试区域(S1线全长2.78 km，S2线全长2.64 km)，分别进行差异环境下的道路养护成本测试，以期构造出全局合理的养护费用成本估计。

2.4.1均衡路面条件下的养护成本估计

对于所述的均衡路面条件是指预先设计的运输道路在计划场景中被使用，且以路面平整度范围指标为基础严格按照养护周期执行对应养护的部分路面。为保证上述条件，研究中以该矿南端帮干线S1为例，对生产运营期间该路段进行均衡路面条件养护，并排除场内的部分偶发扰动因素，如雨雪天气、超重超负荷运载等现象，在此基础上对不同状态下养护费用进行合理估计及分析。

(1)常规路面平整养护状态下的成本估计。平路机在作业线路上的随机平整属于常规路面养护，通常此类作业相对较为频繁，平均每组线路的养护周期均值一般在24～28 h。为有效描述此种作业条件下的成本变化趋势，研究中对累计物料量、养护间隔时间以及等效距离等指标分别进行相关性测试，通过对比3组不同时间段上的干线S1上的采样数据，发现养护费用仅与等效距离间存在近似线性关系，且这种线性关系无法拟合累计物料量及养护周期等指标。其中，基于60组采样数据所构建出的线性拟合结果如图3所示。

图3 路面养护费用与等效距离间的线性拟合关系

由于上述存在线性表达，故对于常规路面平整养护状态下的成本估计均采用等效距离的线性估计来处理，其成本估计模型如式(8)所示。

Cnormal=χLeq+b

(8)

式中，Cnormal为成本估计值；χ为养护费用的等效距离折算系数；Leq为待养护线路的等效距离，km；b为费用的轴向截距。

(2)破损路面修整状态下的成本估计。基于上述分析方法，对于破损路面上的养护成本估算，通过与养护成本间的多因素套合分析发现，修正破损路面的费用模型仍可利用线性模型来表征，仅线性模型中的ε截距项变为浮动变量，且通过多组对比分析发现，其浮动状态及指标变化规律与全路面的平均滚动阻力系数的3次多项式曲线具有较好的拟合特性。为有效论证上述浮动截距与全路面的平均滚动阻力系数间的3次特性，研究中共采集了测试干线上不同时段内的多组滚动阻力及浮动截距数据进行拟合，其中采用3次多项式拟合出的2组干线上的曲线结果如图4所示。

图4 浮动截距的3次拟合曲线

通过上述分析，可知均衡路面条件下的养护费用与运输线路的等效距离间存在明显的线性关系，这也很好的解释了部分场景中可以通过等效距离进行费用整体费用描述的主要原因。

2.4.2非均衡路面条件下的养护成本估计

非均衡路面与均衡路面条件下的成本估计问题存在着本质上的不同，原因在于非均衡路面受多种综合诱因控制而产生养护成本偶发性波动，在这种情况下，养护费用将不再与等效距离间存在简单的线性相关性。因此，为进一步确定该状态下的养护成本，研究中以因子分析法、统计学习方法建立各主控分项作用下的最佳成本估计。具体方法如下：

(1)识别成本波动的主控诱因。为确定出非均衡路面条件下的成本波动控制因素，研究中将统计数据中的主控要素重点分为5组，具体指标如图5所示，其中，0.1，0.2，…，0.5为相关系数。并以上述主控指标为依据，结合论文现有测试线路确定出5种综合诱因。

图5 分类型引诱条件下的主控因素作用

(2)非主控诱因的非均衡路面成本估计。当识别出主控成本波动诱因后，5种诱因形成对波动函数的综合作用，且作用函数待估计，且函数形态未知。为进一步提高此类估计过程的精度，研究中尝试采用SVR(支持向量非线性回归模型，Support Vector Regression)进行回归建模，基于最小二乘思想，同时考虑在希尔伯特空间内多元回归问题具有线性可分特性，故对于任意拟合点均可尝试拟合基于y=ωTx的线性表达，故其具有损失的目标函数均可按照式(9)，(10)中函数形态进行建模。

(9)

s.t.δi=ωTφ(xi)+η-yi,i=1,2,…，N

(10)

式中，ω为权系数向量；φ(xi)为输入参数到希尔伯特空间的映射；x为对主探诱因进行量化后的指标向量；C为惩罚因子；η为模型偏差；λ为误差权重向量；λi为向量中的一个值。

当具备全局目标函数后，多元回归问题则转化为在希尔伯特空间线性可分的最优化问题，对应指标值的求解则可通过智能优化算法(如遗传算法、蚁群算法等)进行迭代求解。

3 基于改进RRT的路径优化算法

露天矿的路径优化问题与机器人避障等传统的运动学规划问题随同属路径规划或寻径问题，但2者间对于优化及规划建模则有着本质上的差异。其中，避障问题更注重对于场景地图连通性的判别，且场景地图一般不可知，存在无现实可行解的情况；而露天矿寻径问题的运输网络在计划阶段内其图结构是可知的，且其路径的可行解定然满足连通性条件，但解集内路径会存在明显的费用差异，且费用计算任务更为繁重。因此，为保证算法在具体寻径过程中具有更好的效果及效率表现，将改进的RRT算法引入到路径优化算法的设计过程中，试图通过RRT算法随机特性，为优化算法提供启发式策略及路径连通性的判别结果，最终辅助优化算法实现快速寻径计算。

3.1 基于改进RRT算法的启发式策略

原始的RRT算法在地图空间内多以均匀随机采样策略来完成对寻径算法的建模，以最大限度的保证算法的避障能力，但对于文中基于改进有向图内的寻径算法设计将直接影响算法的执行效率。为保证算法可以具有快速拓扑及优化能力，文中从采样策略及邻近点选择2个方面入手，对RRT算法进行改进，以期为后续的遗传算法快速迭代计算提供连通性判别依据。

3.1.1采样策略修正

在经典RRT算法中，对区域内扩展点的采样采用均匀随机采样策略，其优点在于可以发现更多不同类型的路径来参与碰撞检测，但也受制于采样规模，当采样规模较大时，算法迭代效率较低，特别是类似于文中需要频繁计算全局的费用指标的决策过程，经典算法无法满足特定工程背景下的效率需求。

为有效解决上述局限性问题，尝试引入浮动同心圆采样策略[16-17]，并结合文中算法的寻径目标对采样策略的浮动策略进行修正。其核心思想是尝试利用如式(11)所示的圆的极坐标方程，以目标点为中心、浮动半径ρ向外逐步扩展采样，计算新的随机点坐标(xqrandom,yqrandom)。其中，随机点(xqrandom,yqrandom)的随机采样位置指导后续寻径过程中的采样方向。

(11)

式中，ρ为同心圆采样区域的浮动半径，由后续邻近点选择策略控制；(xqgoal,yqgoal)及(xqrandom,yqrandom)分别为描述目标点及随机点坐标值。

3.1.2邻近点的选择

浮动同心圆采样策略虽在一定程度上可以减缓全区随机采样的枚举规模，但由于可以在圆周上全角度的初始化坐标角度，则仍存在随机采样规模不可控的现实问题。因此，为进一步保证采样范围可控且路径前进方向不存在回溯问题，文献[16]利用路径点夹角特性而非物理距离指标进行采样区域临近点选择的具体方法，对启发式算法进行设计。

具体原理如图6所示，选择过程为：在规划初始阶段，算法以起始点为RRT算法随机树r的根节点，并以该点为基础采用同心圆采样策略向外扩展随机点qrandom。当确定随机点后，算法首先在浮动同心圆内搜索有向图节点，若在同心圆内存在节点ni，则遍历r上的所有qi节点，分别计算每一组qrandom，qi组成的有向边与x轴向的夹角，记为φr-i，以及qi，ni组成的有向边与x轴向间的夹角，记为φn-i，并利用式(12)进行判断，保证每组角度应控制在φΔ角度容差范围内；否则，调整浮动同心圆采样半径大小。

图6 邻近点方向性约束原理

Δ(qrandom,qi,ni)=|φr-i-φn-i|<φΔ

(12)

式中，φΔ为邻近点角度约束，该角度控制在6°以内。

3.2 融合启发式策略的寻径算法设计

对于RRT算法的改进仅能实现对备选路径解连通性的判别，并不能对路径规划模型进行求解。因此，为保证寻径算法可以快速搜索出路网中的全局最优解，文中尝试将连通性的启发式计算策略融合到遗传编码过程中，实现对备选路径解的启发式编码，并以min[1/Q(t)]为目标函数进行最优化建模，最终利用遗传算法迭代出全局最优解。具体最优化算法设计及执行逻辑流程如图7所示，其中G表示遗传算法种群迭代的次数。

图7 改进遗传算法逻辑流程

4 仿真实验对比分析

为有效验证算法的现实有效性及性能表现，在前述分析结果的基础上，以常规养护状态、偶发性的天气变化以及多类型车型参与运输等情况的分析任务为基础，在采场内选择不同的5组路线，分别计算综合折算费用(运输功转化成本+路面养护成本)。试验模型中5条线路的初始化条件及指标参数赋值情况如下，其中R1～R5五条线路的平均路面滚动阻力系数分别为0.047 1,0.024 6,0.033 9,0.046 8,0.041 2。遗传算法试验参数：算法种群规模为50；最大进化次数150次；交叉概率0.8，变异概率0.05。实例运输卡车采用MT5500B，空车质量223 t，额定载质量326 t，最大载质量360 t，平装容积158 m3，2∶1堆装218 m3。通过重复多次优化迭代计算，遗传算法稳定迭代后，费用评价指标收敛结果如图8所示。

图8 5组测试数据迭代收敛结果

观察分析对比图8中迭代结果发现，5组线路经150次迭代完成后，均能收敛于全局费用最优解。其中，均衡路面(R2,R3,R5三组)收敛速度较快，基本在50～60次迭代后既可以搜索到全局最优线路，而非均衡路面由于需要频繁进行费用成本计算，迭代速度相对较慢，但在70～80次迭代计算后，同样可以获得不错的全局最优解。因此，从该层面看，改进算法具有较好的迭代收敛特性。

同时，为验证算法具有较好的收敛特性，研究中进行了多次重复测试，以验证算法的稳定性。其中，20次重复试验后，算法精度及稳定性评价的平均指标统计见表3。

表3 20组重复试验对比数据

对5组实例进行20次重复试验后，对比统计结果发现，在R1,R4,R5三组路径上，重复迭代20次后，算法均能收敛于最优解；而R2,R3两组在20次测试过程中，均出现一次无法收敛于参考值的现象，但其平均误差不到1%，对于路径规划露天矿路径问题影响不大，能满足露天矿寻径算法的现实需求。

5 结 论

(1)为有效解决传统模型评价建模困难、寻径效率受限等问题，在时变运输功计算的基础上，将车路两系统产生的能耗费用耦合看待，提出了兼顾路面随机损伤作用下的寻径费用评价函数及路径规划模型，改善了现有运输系统规划建模过程中缺失路面损伤成本考量的部分局限性问题。

(2)从智能优化算法随机初始化备选路径效率低下的切实问题出发，提出了规划模型标量计算与拓扑连通性判别相分离的基本思想，并基于快速搜索随机树算法改进了遗传算法寻径过程中的遗传编码方式，提出了备选路径拓扑连通性判别方法。

(3)车辆运输过程中路面变化不但会引起车辆能耗变化，同时也会带来路面养护成本的波动变化，通过分析不同路面状态下的养护成本波动规律，证实了传统基于等效路径折算的成本组成仅适用于均衡路面条件，真实矿山生产过程中，路面状态常介于均衡与非均衡之间。因此，传统的费用折算方法在精准估计时并不准确。

(4)通过对比多组重复实验及部分寻径算法，证实基于车-路耦合思想所构建的兼顾路面随机损伤作用的费用评价函数及路径规划模型现实有效，能作为现有矿山寻径任务的替代算法，对于降低矿山运输系统总体能耗、指导矿山生产实践及组织协调具有重要现实意义。