基于SA—GA模型的露天矿卡车调度系统优化研究
张新文
摘 要：针对露天“卡调”系统路线寻优的非线性问题，利用模拟退火算法和遗传算法相结合，弥补了传统遗传算法容易陷入局部极值的缺陷。仿真结果表明，改进的遗传算法在找到同样最短距离的情况下，节省了7代的迭代次数，节省了路径优化时间，为该领域提供了一条新思路。
关键词：卡车调度；遗传算法；模拟退火算法；路径优化
DOI：10.16640/j.cnki.37-1222/t.2019.07.056
1 序言
露天“卡调”系统于20世纪中叶就被提出，随着计算机技术的日益发展，国内外各个高校及科研院所的学者将最先进的技术及理论都集成到露天矿的生产调度过程中，通信方式也经历了由有线到无线的质的飞跃，一改传统通过人为调度方法，改善了卡车滞留、拥堵等事件的发生，提高了露天矿的整体生产效率，从而带动了经济增长点。
随着卡车调度系统的发展，系统已经由理论研究过渡到实际应用，尤其是GPS技术的诞生，美国公司于1990年将该技术应用于卡调系统中，感知了卡车速度，并使定位精度得到了大幅度提升；1990年到2000年期间，国内如西安煤科院、抚顺煤科院和中国矿业大学等高校及科研院所都涌入了该领域的研究，获得了较多科研成果。21世纪初期，中国东方测控集团也研发了卡调系统，将最先进的定位技术和无线电技术等集成于系统，实现了全矿井生产、调度系统于一体，该套系统在鞍钢矿业公司得到推广与使用，提高了矿山的整体效率，经济效益突出。卡车调度体统究其根本是非线性系统，随着人工智能的发展，神经网络、粒子群、遗传算法等最先进的理论可以解决非线性问题，可以应用在优化调度方面。
2 应用于卡调系统的遗传退火算法
2.1 模拟退火算法
模拟退火算法（SA）早于1953年提出，该算法构思来源于物理学的物体退火降温过程。根据物理学原理，固体从加热到冷却的过程中，原子运动由剧烈变为缓和，内能也伴随着温度的降低而由升高变为降低，此时，固体内部原子已发生重新排列，打破了原有平衡达到了一种新的稳态，以上是模拟退火算法的物理学意义。退火算法与粒子群一般都适用于寻找全局最优解，但是由于存在温度初值和模拟退火V及温度管控方面的问题，使其参数寻优过程比较困难。
2.2 遗传算法
该算法于20世纪70年代由美国教授提出来，算法主要来自于仿生进化思想，即“适者生存”原则，是机器学习领域主要算法，适用于模型构建，算法本身具有自组织、自学习能力。算法的具体实施流程是：第一步，种群随机化形成，并选择适合的循环次数及适应函数；第二部：优胜劣汰，保留强壮个体，舍弃不适类别；第三部，交叉选择，迭代更强种类，并进行变异化改进；第四部：参数寻优，找到全局最优解。
2.3 应用于卡调系统的遗传退火算法
由于传统遗传算法在迭代后期容易陷入局部极值，而退火算法可以规避此类问题，因此综合二者优势，找到全局最优，具体原则如下：
SA-GA算法首先由退火算法提出最初群体，并通过种群进化，形成更优初始值，得到更高效率结果；利用模拟退火跳出局部最优值，强化寻优能力；在退火过程中，温度降低，退火效率更快，具体流程如下：
3 算法效能分析
以某矿井为应用示范，以选择的某段行程为参考对象，在matlab里分别利用GA算法，SA-GA算法进行模拟，群体初始粒子数为80，迭代次数为150，初始T选择30℃，选取的每一点世界坐标系如表1，表2所示，模拟效果如图2、图3所示。
4 总结
由图2得到，SA在第42代得到最優解，最短S为30.68km；由图3得到，SA-GA算法在第35代找到全局最优，最短S为31.9548km。因此，加入模拟退火算法后的遗传算法在找到同样最优解的过程中节省了7代，这在露天矿卡车调度实际应用中可以节省时间，提供了一条新思路。
参考文献：
[1]刘浩洋.基于改进蚁群算法的露天矿卡车优化调度研究[D].西安：西安建筑科技大学，2013.
[2]高登来.露天矿卡车自动化调度系统的考察[J].露天采煤技术，1999增刊：80-81.
[3]李军才.Dispatch系统在我国大型露天矿山中的应用[J].中国矿业，2000（09）：62-65.
[4]Ahangaran，Daryoush Kaveh，Yasrebi，Amir Bijan，Wetherelt，Andy.Real-time dispatching modeling for trucks with different capacities in open pit mines[J].Archives of Mining Sciences，2012（57）：39-52.
[5]王训斌，陆慧娟，陈五涛.带时间窗动态车辆路径问题的改进蚁群算法[J].工业控制计算机，2009，22（01）：41-43.
[6]周四根.特大型露天矿道路优化设计研究[J].采矿技术，2014，5
（05）：13-14.
