智能化开采是露天矿未来发展的主流方向，而电铲是露天矿开采的主要设备之一，因此电铲自主铲装技术研究一直是该领域的热点问题。Singh et al.（1992）和Singh（1994）提出将挖掘设备几何约束与力约束添加到动作空间，为铲斗装载机或反铲挖掘机自动生成挖掘计划，该计划指导挖掘机在对应位置的挖掘方法并设定挖掘任务总量；同时介绍了一种根据经验预测机器人挖掘土壤遇到阻力的方法，即通过土壤平移刀片的简单分析模型，解决挖掘机挖掘运动的某些特定现象（Singh，1995）。Bradley et al.（1998）开发了基于人工智能的控制系统，该系统结合新型运动控制策略，控制铲斗在各种类型和条件的地面上正常自动挖掘高质量的矩形沟槽，并自动清除大型障碍物。Cannon et al.（1999）开发了自动装载系统（Autonomous Loading System，ALS），通过观察挖掘面，挖掘机可以自主决定挖掘位置，并在该位置有效执行挖掘动作，快速准确地识别卡车，定位卡车位置并将物料倾卸至卡车内部。Dunbabin et al.（2006）开发了电铲自动挖掘土壤系统，将该系统在等比例电铲模型上进行了试验，试验结果与人工操作基本相似。Winstanley et al.（2007）利用绳铲智能机器人实现了远程遥控的矿物挖掘。Sakaida et al.（2008）通过分析挖掘机操作人员（选择能够熟练操作挖掘机的技术工）的操作技能，开发了具有高效操作性能的自主挖掘机控制系统。另外，为了提高自主挖掘机器的任务执行效率，规划其移动路径和挖掘区域，Seo et al.（2011）开发了一种用于划分挖掘机工作区域及移动路径的算法，该算法以工作环境三维模型为基础，结合熟练操作员的操作习惯，自动生成高效率的工作计划。Beasley et al.（2013）使用线性松弛算法确定电铲最佳移动路径及在路径上每个作业位置点的挖掘区域，通过模拟仿真生成了具有成本效益的挖掘机器移动路径以及对应的挖掘区域。但是该路径并未考虑电铲在实际生产作业中挖掘、卸矿动作的相关几何约束，导致电铲在生产作业中无法完全遵循该路径进行铲装作业。

本文在已知电铲工作区域的基础上，采用贪婪算法和遗传算法规划出电铲移动路径及相应的挖掘区域，再结合电铲挖掘、倾卸等作业动作的相关几何约束，对已规划出的移动路径及对应挖掘区域进行进一步优化。

根据矿山生产规划，经穿孔爆破后，对应位置的露天矿岩会按照一定块度从矿岩整体中剥落，并堆积成一定形状的矿堆。为了将矿石转移至选矿厂和破碎站等矿山工作场地，需要电铲通过其挖掘机构将矿石从矿堆中铲出，并将矿石装入运输车辆，再由运输车辆运输至对应卸载地点。

电铲挖掘机构的运动由推压运动和提升运动组成，其中推压运动是借助推压齿轮和安装在推压斗杆上的齿条驱动铲斗移动，提升运动则是通过提升钢绳将铲斗提升至一定高度。电铲铲装作业时，需借助推压运动将矿石推入铲斗，之后利用提升运动将铲斗提升至相应高度，与此同时电铲底部的旋转平台进行旋转，带动铲斗旋转至矿用运输卡车可倾卸位置的上方后倾卸矿石；倾卸完成后，旋转平台再反向旋转至待挖掘区域，继续挖掘作业。当电铲当前工作位置对应挖掘区域内的矿石均被铲装完毕后，电铲通过移动机构缓慢移动至已规划的下一个作业位置点，铲装对应目标区域内的矿堆。为了将工作区域内的矿堆全部挖掘完毕，电铲会在多个作业位置点间有序移动，并在每个作业位置持续铲装作业。

由于电铲本身体积巨大，挖掘机构和移动机构持续工作时均消耗大量电能。为了最大化地降低能耗，充分提高电铲自主铲装过程中的工作效率，需最大程度地减少挖掘机构和移动机构的工作时间。因而，开展电铲移动轨迹规划研究，合理设置电铲挖掘区域，规划电铲移动路径，缩短电铲移动路径总长度，形成电铲作业最优轨迹至关重要。

结合矿山当天具体生产计划及矿山品位数据库，可确定电铲某班次对应挖掘工作区域。由于挖掘工作区域总面积相比电铲在单个作业位置的铲装有效区域大得多，电铲将当前位置对应挖掘区域的矿堆全部铲装至运输卡车后，需移动至下一作业位置，循环以上作业过程，直至将该班次的目标矿堆铲装和倾卸完毕。为了提高电铲工作效率，减少电铲作业时的移动次数，本文结合经典最小集合覆盖问题（The Classical Minimum Set Cover Problem，CMSCP）（冯富宝，2006；姚国辉，2009；王艺源，2017），使用贪婪算法计算得出电铲铲装作业位置数量最少的作业位置集（Al-shihabi et al.，2015）。

经典最小集合覆盖问题是给定一个全集U=｛u₁，u₂，…，u_k｝及包含N个子集的集合S=｛s₁，s₂，…，s_N｝（s_i⊆U，1≤i≤N），集合S内所有子集的并集为集合U，求解集合S中数目最少的点集组成的集合T（例如T=｛s₁，s₃，…，s_k-1｝），以使T内所有子集的并集为全集U。

借助经典最小集合覆盖问题思想，可计算得出目标区域内的矿堆全部被挖掘完毕而电铲移动次数最少的电铲作业位置集，具体流程如图1所示。电铲工作区域U确定后，依据电铲挖掘范围及工作区域，按照一定范围对工作区域进行栅格划分，将得到一系列栅格点u₁，u₂，…，u_k，每个栅格点作为电铲铲装作业位置点。在每个电铲铲装作业位置点处，以最大铲装半径为有效挖掘半径，计算并存储在该位置能挖掘的矿堆区域s_i（1≤i≤k），所有电铲作业位置处的有效挖掘区域组成集合S=｛s₁，s₂，…，s_k｝。

电铲作业位置点与对应挖掘区域示意图如图2所示，每个栅格点均可作为作业位置点，且均具有对应挖掘区域，这里仅展示其中1个作业位置点及其对应挖掘区域。假设电铲最大挖掘半径为2个栅格对角线长度，某作业位置点对应挖掘区域为以该作业位置点为中心，边长为2个挖掘半径大小的正方形区域。若设置作业位置点对应挖掘区域为圆形区域，尽管在一定程度上增加了每个作业位置点的挖掘区域面积，但由于相邻圆形区域之间存在较小面积的未被挖掘区域，导致电铲作业位置点数量大幅增加，继而电铲移动路径变长。为便于观察和理解，每个栅格内都有一个圆圈，该圆圈与某作业位置点连接，即代表该栅格位于作业位置点的挖掘区域内，电铲在该作业位置点铲装作业时会挖掘该栅格内矿石并倾卸至运输车辆。

为快速计算出电铲移动次数最少的作业位置集T，同时确保电铲工作区域U内的矿堆可被挖掘完毕，结合贪婪算法易于实现且高效等优点，本文采用贪婪算法规划电铲移动作业位置点集。具体流程如下：每次从集合S中选择覆盖区域面积最大的挖掘矿堆区域，将其对应的作业位置点U_i放入电铲铲装作业位置集T，并从工作区域U中将该挖掘区域删除，重复以上选择过程，直至所有待挖掘区域全部被选择，集合U变为空集。

第2.1节中计算了电铲铲装作业位置集T=｛T₁，T₂，…，T_k｝（k为电铲作业位置的个数），其中T_i=｛T_ix，T_iy｝（i=1，2，…，k）。结合待铲装矿堆区域边界信息，在作业位置集T内选择一点T_j（1≤j≤k），将该点作为电铲在当前区域的起始作业点。电铲在起始作业点开展独立生产铲装作业，直至该区域矿堆铲装完毕，电铲移动至下一作业位置点。下一作业位置点从作业位置集T中选取，且T内每点只能被选取一次。将选取的作业位置点依次放入移动路径集合D内存储，电铲移动总距离dis为

式中：d_i，i+1为集合D内第i个和第i+1个电铲作业位置的欧氏距离；TDix，TDiy分别为集合D第i个点的x，y坐标值。

为降低矿山生产经营成本，减少电铲移动时的电能消耗，需规划电铲铲装移动的最短路径，使得电铲在该路径上所有作业位置点的直线总距离dis最小。该路径规划问题类似于旅行商问题（Travelling Salesman Problem，TSP）（袁豪，2017），即在已知各城市之间旅游费用的基础上，旅行商从某固定城市出发，使用TSP算法规划旅行商到每一个城市旅游并最终返回初始城市的最短旅行路线，且每个城市只能旅游一次。TSP问题本身是优化组合类的一道典型难题，目前已经证明没有明确清晰的算法能在多项式时间内完美解决TSP问题（于莹莹等，2014；李俊纬，2017；岳鹏齐，2019）。而遗传算法（Genetic Algorithm，GA）借鉴自然界生物遗传进化的繁衍过程，结合计算机模拟仿真，抛弃传统思维方法，将生物遗传中染色体基因的选择、交叉以及变异过程与现有组合优化问题相结合，能够快速获得TSP问题近似最优的结果（孙文彬等，2016；任昊南，2008）。值得注意的是，使用TSP规划电铲移动路径时，电铲将该班次矿堆铲装完毕后并不需要回到起始挖掘点，即规划的路径首尾不必相连。

基于遗传算法解决TSP问题的流程如图3所示。首先获取电铲作业位置集T，对作业位置进行编号，如0，1，…，n-1，以此确定算法编码机制，继而确定遗传算法的参数如下：种群规模为80、迭代次数为50 000次、交叉概率为90%、变异概率为20%。

因TSP问题目标是求解电铲最短移动距离，设定遗传算法选择适应度函数为总移动距离的倒数，这样电铲总移动距离越长，适应度越小，可逐步将总移动距离长的路径所对应的群体淘汰。

式中：T_i为电铲作业点集中第i点的坐标信息；d（T_i，T_i+1）为电铲作业点集中第i点和第i+1点的欧氏距离；f（T₁，T₂，…，T_n）为选择适应度函数。

设置好迭代次数等参数后，随机生成初始种群，在迭代次数内循环计算所有作业位置之间的距离，群体经选择、交叉和变异等操作后，遗传算法选择的电铲移动路线会逐渐缩短，最后逐渐接近移动最短距离。图4所示为使用遗传算法规划旅行商路径示意图。

上述使用遗传算法确定电铲移动路径时，由于未考虑电铲实际生产作业过程中铲装操作的条件限制和操作可行性的要求，生成的电铲移动路径及对应挖掘区域存在以下2个方面的问题：（1）电铲在卸矿时，需为运输卡车提供一定空间大小的受矿区域，以使运输卡车顺利驶入驶出，且由于电铲旋转速度缓慢，电铲铲斗旋转至指定位置的角度应尽量小，以减少能耗。而电铲在上述已规划路径上的某位置点进行铲装作业时，可能存在运输卡车受矿位置距离电铲较远或运输卡车受矿位置难以规划等情况。（2）电铲从某一铲装位置点移动至下一铲装位置点时，路径上可能存在一定体积的矿堆阻碍电铲移动，而此矿堆在下一位置点才能被挖掘铲装，二者存在逻辑矛盾。

因此，本文提出在电铲移动路径中设置过渡点的方法来解决上述问题。当电铲在某作业位置点的挖掘区域不合理时，将重新规划一个新的挖掘点即过渡点，使得电铲在上述作业位置点的不合理挖掘区域均在过渡点的合理挖掘范围内，并将不合理挖掘区域设为过渡点的挖掘区域（图5）。

当电铲在移动至下一待铲装点的过程中遇到障碍时，将电铲移动时遇到的第一个障碍点作为过渡点，即新的电铲铲装点，并将路径上遇到的障碍添加到过渡点的挖掘区域目标规划中（图6）。同时为最大限度地发挥电铲在过渡点的铲装效率并消除其他路径可能存在的障碍，过渡点的挖掘区域扩大至包含其有效挖掘范围内所有未被挖掘的矿堆，并更新剩余待挖掘位置的挖掘区域规划。

选择某矿航拍地形图中某区域爆破后的矿堆作为电铲待铲装矿堆，如图7所示。矿堆实际最大长度为280 m，最大宽度为76 m，矿堆开放区域和待挖掘矿堆如图7（a）所示，待挖掘矿堆俯视图如图7（b）所示。矿山使用电铲的最大挖掘半径为14 m，最大挖掘高度为10.1 m。

结合经典最小集合覆盖问题及贪婪算法，计算得到对应的电铲作业位置集。具体计算流程如下：

（1）沿矿堆的长和宽2个方向进行栅格划分，相邻栅格间距为2 m，共划分出3 263个栅格，每个栅格的中心点均可作为电铲作业位置点；

（2）根据第2.1小节所述，结合电铲最大挖掘半径，计算出每个作业位置点的挖掘区域为边长等于10个栅格长度的正方形；

（3）根据上述电铲作业位置点及矿堆区域位置信息，计算出每个作业位置点对应的有效挖掘矿堆区域，组成有效挖掘矿堆区域集；

（4）结合贪婪算法，从有效挖掘矿堆区域集中选择面积最大的挖掘区域，将其对应的作业位置点放入电铲作业位置集中，并从有效挖掘矿堆区域集中将该挖掘区域删除，重复本过程直至有效挖掘矿堆区域为空集，矿堆即被挖掘完毕。

如图8（a）所示，35个电铲作业位置点组成电铲移动次数最少的作业位置集，其中黑色点代表电铲作业位置。

设定挖掘区域西北角为电铲初始作业点，使用遗传算法将电铲作业位置依次连接，每个作业位置点将被访问且只能被访问一次，生成电铲移动最短路径，如图8（b）所示，路径总长度为601.57 m。图中黑色圆圈代表电铲起始挖掘点，电铲根据红色线条即电铲移动路径铲装作业。

如图 9所示，每个电铲作业位置点都有其对应的挖掘区域，为充分详细地展示挖掘区域，每隔2 m展示一个挖掘区域，电铲作业位置与其所有挖掘区域用直线连接。

上述生成的电铲移动路径不能直接应用于实际生产，结合电铲生产作业相关几何约束，通过新增过渡点对上述移动路径及对应挖掘区域进行优化，结果如图 10所示。优化后总路径长度为599.46 m，小于优化前路径总长度，这是因为在优化电铲移动路径时，由于部分作业位置点对应的挖掘区域仅有个位数，导致电铲在该位置铲装效率较低。为最大程度地提升铲装效率，减少电铲移动路径长度，将上述区域添加至最近的电铲作业位置挖掘区域中，并移除对应作业位置点。

选取电铲起始挖掘点附近的优化前后移动路径做对比，结果见图11。从图 11（a）中可以看出，电铲在作业位置点1处即起始挖掘点开始挖掘工作，但当电铲从开放区域移动至作业位置点1时会被矿堆阻挡，而该矿堆本应在作业位置点1处被挖掘，二者存在明显矛盾。即使电铲已移动至作业位置点1，在铲装该位置点北部矿堆时，仍然会出现无合适受矿位置的情况。电铲从作业位置点3移动至作业位置点4时也存在类似问题。另外，电铲从作业位置点2移动至作业位置点3时，移动路径上也存在障碍矿堆，而该区域矿堆是作业位置点4的对应挖掘区域。

为解决上述问题，通过新增过渡点优化电铲移动路径及对应挖掘区域规划。如图11（b）所示，将起始挖掘点调整至作业位置点1，此时电铲可从开放区域直接移动至作业位置点1，且在铲装过程中，只需要保证电铲旋转较小角度即可将矿石卸载至运输卡车。从作业位置点4移动至作业位置点6时，由于新增作业位置点5，电铲在该位置可将移动路径障碍区域全部铲装。由此电铲从作业位置点1移动至作业位置点7的铲装工作可全部顺利进行。通过该方法对已生成的电铲移动路径及挖掘区域进行优化，既保证了移动路径长度较短，又确保了电铲在实际生产作业中操作的合理性。

（1）为提高电铲自主铲装过程中的工作效率，降低矿山生产成本，提出了一种电铲铲装移动路线优化方法。该方法使用贪婪算法和遗传算法得出电铲铲装移动最短路径，并结合电铲作业的相关几何约束，调整电铲移动路径，优化相应挖掘区域规划。

（2）选取某矿山矿堆对该方法进行验证，结果表明生成的电铲移动路径距离较短，相应挖掘区域的规划遵循电铲铲装约束条件，证明该方法能够为自主铲装电铲的移动轨迹规划提供指导。

（3）将矿堆三维地形纳入电铲挖掘区域规划的考量因素，针对爆堆的空间形态规划相应电铲的最优挖掘轨迹，进一步降低电铲工作能耗，将是未来的主要研究方向。