露天矿卡车SA-GA算法实时调度的实现

郭天中，郝静

（包头职业技术学院 材料工程系，内蒙古 包头 014010）

0 引言

卡车运输作为露天矿开采中最为主要的生产环节，其能否得到合理的调度直接影响着露天矿开采的生产效率，若卡车调度不合理容易造成其它环节的等待或不协调问题而浪费时间、降低经济效益。本文在对露天矿开采实际调研的基础上，充分分析了卡车运输过程中的各个环节，采用计算机技术和人工智能算法对十分复杂的卡车调度系统进行研究，并最终应用模拟退火算法和遗传算法相结合的方法动态地搜索卡车与挖掘机、破碎站之间的最佳组合，力求降低露天矿生产运输的经济成本。

1 SA-GA算法与GA算法搜索能力比较

1.1 TSP问题描述及算法的实现

TSP（Traveling Saleman Problem）问题即旅行商问题，它是一个涵盖广泛应用背景和重要理论价值的组合优化问题，其已被证明是一个经典的NP难题。与卡车调度的问题具有相似之处，因此以此对比GA算法与SA-GA算法的性能。

TSP问题可以描述为：已知m个城市之间的相对距离，一名旅行者由某一个城市出发遍历这m个城市且每个城市仅访问一次，而且最终必须返回出发的城市，求如何安排这些城市的访问次序能够使得旅行者行走的距离最短。

其数学模型描述如下：设一组城市集合M={m1，m2，…，mn}，其中任意2个城市mi、mj∈M间的距离为D（mi，mj），求解一条经过所有城市且仅经过一次的路径（mp（1）,mp（2）,mp（3））使得式（1）值最小。

式中，（p(1),p(2),…，p(n)）为1,2,3…，n的一个置换。

1.2 实验结果的比较与分析

对于上节所述的TSP问题，应用所述的编码方式及参数设置方式，由Matlab软件分别编制遗传算法和改进的模拟退火遗传算法程序，并对随机生成的30个城市地点的TSP问题进行寻优，其中30座城市的坐标位置如表1所示。

表1 30座城市坐标

30座城市的位置分布如图1所示。

图1 30座城市的位置分布图

对于编制的遗传算法程序和模拟退火算法程序分别在配置为Intel Core（TM）i5-2520 CPU@2.50 GHz、内存为2.00 GB的32位Win7操作系统中运行。

首先应用遗传算法寻找最佳路径。

在遗传算法寻优时，首先初始种群中的一个随机路径为：20→18 →27 →4→7→19→3→24→30→17→10→5→25→11→6→9→13→1→8→22→12→21→14→15→16→2→26→28→29→23→20。其表示由城市20开始出发一次经过城市18，城市27，如此类推，直至回到出发城市20，总距离为161.308 2。其路径轨迹图如图2所示。

图2 GA算法初始种群随机路径

然后，由遗传算法进行迭代寻优，经多次迭代最终获得的最优路径为：11→17 →9 →29 →7 →6 →16 →30→28→10→3→22→13→2→24→23→21→12→5→26→8→25→18→20→4→19→15→1→27→14→11。

其获得的最优路径图如图3所示。最终获得的寻优路径的总距离为47.689 5。比此前随机生成路径的总距离161.308 2缩短了许多，其具体优化过程曲线如图4所示。从图4中可以看出，GA算法前期迭代过程比较缓慢，局部搜索能力较弱且在近140代前就收敛至最优解。

图3 GA寻优路径轨迹图

同样由模拟退火算法与遗传算法结合的SA -GA 算法对上述的30座城市的最佳路径进行寻优。起初同样随机生成初始种群中的一个随机值为：22 →1 →24 →8 →9 →30 →21 →4 →13 →6 →20 →25 →14 →17 →26 →18 →11 →2 →29 →19 →23→3→16→7→15→5→27→10→12→28→22；其随机生成路径的总距离为154.128 4，其具体路径轨迹图如图5所示。

图4 GA算法寻优迭代过程

图5 SA-GA算法初始种群随机路径

根据模拟退火和遗传算法的各个参数，然后由SA-GA算法寻得的最佳路径的最优解为：13→22 →3 →10 →28 →30 →1 →6 →16 →7 →29 →9 →17 →11 →14 →27→4→20→18→25→8→26→5→12→19→15→21→23→24→2→13。

最终总距离为45.533 7，其具体寻优路径轨迹如图6所示。同样比SA-GA算法随机生成的路径距离154.128 4小，比由GA算法寻得的最优路径的总距离47.689 5也小。且将SA-GA算法的优化过程曲线（如图7）与GA算法优化曲线（如图4）相比可知，SA-GA算的局部搜索能力更强，而且前期收敛迅速，后期收敛缓慢，最终在近160代左右收敛。以优化算法的评价指标进行评价，对GA算法与SAGA算法各运行10次求得的各项评价指标如表2所示。其中时间性能指标直接求取10次运行结果的平均值，其值越小，运行时间越短。由表1可以看出优化性能和鲁棒性SA-GA算法均优于GA算法，优化性能和鲁棒性能值越小越好，因此尽管SA-GA算法在运行时间上略长于GA算法,但在优化性能和鲁棒 性 上SA-GA算法均优于GA算法。

图6 SA-GA寻优路径轨迹图

图7 GA算法寻优迭代过程

表2 GA算法与SA-GA算法性能比较

由此可得，将SA算法与GA 算法结合起来的SA-GA算法无论是从最终的优化结果还是优化过程中的搜索能力都比单纯的GA算 法 优越，因此将SA-GA算法应用到露天矿用卡车的调度过程中将能够获得更优的结果。

2 哈尔乌素露天矿卡车的SA-GA实时调度的实现

2.1 哈尔乌素露天矿开采状况

哈尔乌素露天煤矿是我国自行设计并施工的特大型露天煤矿，位于准格尔煤田中部，可采原煤储量达14.98亿t，设计生产能力为每年2000 万t。其开采选用的主要设备许多都是从国外引进的当今最先进的采矿设备，包括1台P&H公司2800型电铲及日本小松德莱赛630E型154 t电动轮自卸卡车58台等设备。同时其调度管理系统采用的是由某公司提供的露天煤矿GPS智能矿山管理系统，其系统能够通过采用全球卫星定位技术（GPS）、计算机及网络技术、无线数字通信技术、矿山系统工程及优化理论、地理信息系统技术（GIS）、电子技术等高新技术对传统的人工调度系统及管理体制进行改造，通过采集生产设备动态信息，实时监控和优化调度卡车、电铲、辅助设备等设备的运行。在其车辆智能调度模块中为了实现车辆智能调度，其采用的流程如图8所示。

图8 智能调度系统流程

最佳线路子系统能够根据矿山地形计划出相对两点间的最短路径；而线性规划子系统采用最佳线路子系统生成的运行时间和最优路径，以及当前露天坑内配置的信息：如可用于作业的电铲和卡车的数量，在电铲和卸载点的装载时间和卸载时间，在相应卸载点和破碎站的配矿要求及电铲的优先权。然后建立线性规划的约束条件。该模型的最终解是优化的最佳路线的货流量，在坑内配置既定时，使卡车运输需求量最少。最后，动态规划子系统利用线性规划的结果，申请分派指令（由卸载点至电铲）的卡车名单，当前的运行时间和运输距离，为每台卡车生成一个最优的实时调度表。每当卡车请求分派指令时，调用动态规划程序，生成一个按照需求排序的由卸载点至电铲的路径表，并将卡车分派给各条路径。最后，系统运用滑动平均值更新运输时间。

智能调度采用两阶段模型法进行：首先，根据班计划及生产的进行情况对通往各装载点、卸载点的车流进行车流规划；然后，在卡车需要调度时，根据生产的实际情况以车流规划为基础进行实时调度。

由前述可知，动态规划虽然具有一定的优点，但其不足是动态规划模型没有统一的标准模型，而且求解时存在维数灾难。而智能算法恰恰能够克服其不足，在组合优化方面和车辆调度领域应用广泛。因此，本节针对智能调度系统中的动态规划系统应用SA-GA算法进行替换，以此获得更优的实时调度效果。

2.2 基于SA-GA算法露天矿卡车调度系统实现

针对影响露天矿生产效率的采运设备调配的特点及现在使用的露天煤矿GPS智能矿山管理系统的不足，本文编写了基于SA-GA算法露天矿卡车调度系统，实现对卡车的实时调度。该系统能够随着采运设备参数的变化而重新寻优，如当增减卡车数量或改动卡车一些参数；增减破碎站数量或改动其一些参数；增减挖掘机数量或改动其一些参数；修改各站点之间的距离等。该程序能够由修改后的数据再次寻优，从而计算出设定时间段内的卡车调度安排表。

2.2.1 基于SA-GA算法露天矿卡车调度系统的主流程

卡车调度系统包括主程序和一些子程序。系统中，主程序的主要功能包括：首先判断程序是否为第一次调用该系统程序。若是，主程序就会调用初始化数据子程序对数据进行初始化；若不是，则会调用最近一次优化结果。然后，便调用计时程序对优化时刻进行实时监控，若到达程序优化时刻，则调用优化子程序，对卡车路径下一时间段卡车最优调度路径进行安排，并给出卡车进度时刻及调度安排的甘特图，接着调用数据调整程序，为下次卡车路径优化准备初始数据；否则就会一直计时，直到达到下次优化时刻。此外，当运输过程中设备调整（如增减卡车、挖掘机、破碎站数量或更改设备的某些参数）后会调用调整后的数据处理程序，由此获得调整后的计算所需要数据，然后再调用路径优化程序获得设备调整以后的卡车最优调度路径。

主程序的流程如图9所示。由图9可知，促使调入卡车路径优化程序的具有两种条件，分别是到了规定的优化时刻，再者是优化过程中调整设备。每次运行SA-GA 优化程序后，就会获得每辆卡车对应的破碎站和挖掘机的甘特图及到达时刻表。

图9 主程序流程图

2.2.2 各程序功能及实现

基于SA-GA算法的露天矿卡车调度程序的主程序、子程序的主要功能如下：

1）主程序（Main）主要功能是：判定系统程序是否被第一次使用；连接各个子程序并最终给出卡车调度的路径。

2）初始数据子程序（InitialData）主要功能是：第一次调用系统程序时设定的基本数据，包括遗传算法的一些基本参数和调度设备的一些参数。

3）卡车路线产生子程序（ProduceRoute）主要功能是：产生最初的一条卡车路线并记录下由此产生的费用及挖掘机和破碎站的任务状态。

4）种群初始化子程序（Initalition）主要功能是：初始化染色体并计算出相应的适应度值（即相应的调度方案费用）及到达破碎站和挖掘机的时刻及它们状态变化。

5）优化子程序（Optimize）主要功能是：按照SA-GA算法流程图完成规定时间内中现有设备条件下的卡车调度路径的寻优，给出最佳的卡车调度结果。有关模拟退火和遗传算法的基本参数如表3、表4所示。

表3 遗传算法参数设定

表4 模拟退火参数设定

6）各类设备状态调整子程序。其中：增加卡车子程序（Add_Truck）的主要功能是给新增卡车编号，确定起始站点，设定卡车的各种参数并启动卡车路径优化子程序；卡车参数修改子程序(Amend_Truck)主要功能是找出卡车编号对应的卡车，修改相关参数（如卡车速度、容量、各种费用）；卡车删除子程序（Delete_Truck）主要功能是删除相应编号卡车的所有信息；增加挖掘机子程序（Add_Excavator）主要功能是将挖掘机编号并将其编排到挖掘机状态矩阵中并启动重新优化卡车路径子程序；挖掘机参数修改子程序(Amend_Excavator)主要功能是找出预修改的挖掘机编号，修改挖掘机与破碎站之间的距离，修改挖掘机的工作效率；挖掘机删除子程序（Delete_Excavator）找出预删除的挖掘机编号并删除所有相关参数；增加破碎站子程序（Add_Crush）主要功能是将破碎站编号，给定其到各个挖掘机站点的距离，给出破碎站的工作效率，激发卡车路径优化子程序；破碎站参数修改子程序(Amend_Crush)主要功能是找出预修改的破碎站并修改相应参数；破碎站删除子程序（Delete_Crush）主要功能是找出预删除的破碎站并删除相应参数。

7）计时子程序（TimeLong）主要功能是计算出两个卡车调度间的时间长度。其实现过程是以开始优化时的电脑时刻开始计时，其计时格式为年、月、日、时、分、秒，每当卡车完成一次运输过程其就会记录下每个节点的时刻。

8）时刻比较子程序（CompareTime）主要功能是比较多辆卡车往返于挖掘机与破碎站之间时刻的先后顺序。其实现过程是对于记录的两个时刻t1和t2进行比较，若经过比较结果为0，则t1先到；若比较结果为1，则t2先到。

对于以上主程序及子程序，结合前述建立的露天矿卡车调度模型，应用Matlab编制并实现主程序和各个子程序。对于基于SA-GA算法的露天矿卡车调度系统实际应用中涉及到的主要设备参数如下。

1）优化时间间隔。由露天矿实际开采情况可知，采掘点和一些设备是不断变化的，其只能在一定时间内保持不变，因此在实际使用系统程序时优化时间间隔，可以根据实际生产状况设定，可以是1 h、8 h等。

2）卡车载重和挖掘机工作效率。由此便能够计算出正常工作条件下，挖掘机装满卡车所需要的时间。

3）挖掘机到破碎站之间的距离。距离矩阵如下：

式中：矩阵的行数为挖掘机的数量n；列数为破碎站的数量m；dij（其中i=1，2，…，n；j=1，2，…，m）表示挖掘机i到破碎站j的距离。在实际生产中，尽管挖掘机到破碎站之间的距离一定，但由于不同道路间的路面质量、坡度不同，卡车在运行时的速度也不同，为了平衡由此带来的影响，在给定它们之间的距离时，根据其影响大小折算为适当的距离。

4）卡车速度。包括卡车重载时的速度和空载时的速度，其可表示为

式中：t为卡车的数量；第一列vi1（i=1，2，…，t）为重载时的速度；第二列vi2为空载时的速度。

5）运输费用。包括卡车重载时的费用、空载时的费用及维修时的费用，其可表示为

式中：t为卡车的数量；第一列ci1（i=1，2，…，t）为重载时的卡车运输的费用；第二列ci2为空载时卡车运输的费用；第三列ci3为卡车的维修费用。

2.3 基于SA-GA算法露天矿卡车调度实例

针对哈尔乌素露天矿某一开采区2014年12月份某一工作日的开采数据应用基于SA-GA算法的调度程序进行调度。在此开采区投入使用的设备情况为20辆卡车、12台挖掘机和3台破碎机。卡车和挖掘机设备的参数如表5、表6所示。

表5 卡车参数

表6 挖掘机参数

其中卡车的速度根据采掘工艺要求空载时不高于40 km/h，重载时不低于30 km/h。因此在应用程序时所有卡车空载的速度都设定为40 km/h，重载时都设定30 km/h。根据现场工人的开采经验得到各型号卡车的运输费用矩阵如下：MT5500B型的矩阵C1=[350 300 1.5]；MT4400AC型的矩阵C2=[260 200 1]；930-E型的矩阵C3=[320 260 1.5]；SF33900型的矩阵C4=[250 190 1]；HMTK600B型的矩阵C5=[390 330 2]。12台挖掘机到3台破碎站之间的距离矩阵为

在应用卡车调度程序时将20辆卡车分别命名为小写字母a～t；3台破碎站命名为a～c；12台挖掘机分别命名为大写字母A～L；并随机选择卡车出发点，程序调度间隔设定为1 h，对于以上数据逐步输入基于SA-GA算法的卡车调度程序中并在配置为Intel Core （TM） i5 -2520 CPU@2.50GHz、内存为2.00 GB的32位WIN7操作系统运行，最终获得20辆卡车的调度结果如图10～图12所示。

其中图10为基于SA-GA算法露天矿卡车调度结果输出页面的截图。以第一辆卡车的调度结果对其调度输入结果解释，第一台卡车a在设备不变动的1 h内的运行路径为：卡车a从2015年3月8日16时43分48.5秒开始由编号为A的挖掘机满载出发将煤运至编号为c的破碎站，到达c破碎站的时刻是2015年3月8日16时59分19.7秒；接着出发到达编号为I的挖掘机进行装煤，达到挖掘机I的时刻为2015年3月8日17时4分20.9秒，然后又将煤运至破碎站c，此时的时刻为2015年3月8日17时20分38.9秒；接着卡车又跑至编号为F的挖掘机处进行装煤，此时的时刻为2015年3月8日17时28分2.9秒，然后又将煤运达破碎站c处卸载，此时的时刻为2015年3月8日17时42分43.7秒。至此卡车1 h 以内的调度路径就被确定。为了能给工人师傅更直观地显示每辆卡车的调度进度和持续时间，卡车调度系统输出了反映每辆卡车达到破碎站和挖掘机的时刻及持续时间甘特图，其输入结果如图11所示。经过模拟退火优化遗传算法对卡车调度的优化，此20辆卡车运输费用的变化过程如图12所示，从图12中可以看出，卡车运输费用起初较高，经过SA-GA算法的不断优化，算法能够较快地寻得最佳的卡车调度方案，最终获得的在1 h内卡车调度方案总的运输费用为52 747 元；对调度结果进行统计得20辆卡车共运送煤炭5158 t，行驶的总距离为214.4 km，由此便可得其吨公里运输成本约为0.047 6 元/（t·km）。将此结果与此开采区运输环节吨公里成本（2011年为1.014 9元/（t·km），2012年为0.972 9 元/（t·km））相比，基于SA-GA算法调度卡车的运输成本较低，由此可得本文所提出的基于SA-GA算法的露天矿卡车调度方法能够详细地给出矿用卡车调度计划和安排，为现场卡车实时调度提供了决策依据，能够较好地指导实际生产，有利于企业降低生产成本，获得更大的经济效益。

图10 基于SA-GA算法露天矿卡车调度结果

图11 基于SA-GA算法卡车调度甘特图

图12 基于SA-GA算法卡车调度费用迭代过程

3 结论

针对本文提出的模拟退火优化遗传算法的方法，首先应用与露天矿卡车调度具有相同数学背景的典型的优化组合问题——TSP问题对SA-GA算法和GA算法进行比较，结果证明本文提出的模拟退火优化的遗传算法比单纯的遗传算法能够获得更优的全局最优解且鲁棒性更好；接着对哈尔乌素露天矿现行的卡车调度系统中动态规划调度方法中的不足，本文编制了基于SA-GA算法的露天矿用卡车调度程序，并详述了各个程序的功能及实现过程；最后以哈尔乌素露天矿某开采区的采掘设备数据为例，采用SA-GA算法的露天矿用卡车调度程序对卡车进行了调度，调度结果不仅给出了1 h内每台卡车的行驶路径和时刻表，而且给出了总的运输费用为200 元，由此得到吨公里成本为0.047 6 元/（t·km）, 比2011年的1.014 9元/（t·km）和2012年的0.972 9 元/（t·km）成本都低，降低了运输成本，很好地指导了实际生产。