基于改进粒子群算法的露天矿运输调度优化

李 勇,胡乃联,李国清

(1.北京科技大学土木与环境工程学院，北京 100083；2.北京科技大学金属矿山高效开采与安全教育部重点实验室，北京 100083)

基于改进粒子群算法的露天矿运输调度优化

李 勇1,2,胡乃联1,李国清1

(1.北京科技大学土木与环境工程学院，北京100083；2.北京科技大学金属矿山高效开采与安全教育部重点实验室，北京100083)

针对露天矿运输调度问题，以运输费用达到最小为目标，构建露天矿运输调度系统的优化数学模型，基于群体智能优化理论，提出用粒子群算法对露天矿运输调度模型进行解算的方法，并在求解过程中设计了带双引子的粒子搜索策略。以MATLAB软件为平台，应用计算机编程技术，实现模型解算。最后，用露天矿实际生产数据验证了带双引子粒子群算法求解露天矿运输调度问题的有效性。

粒子群算法；露天矿；运输调度；优化

露天矿开采是集矿岩采掘和运输为一体的综合系统[1]。其中，矿岩运输的有效组织和调配对露天矿采剥过程的实施和完成生产任务具有重要意义，因为运输调度对矿山生产设备的利用效率、矿石产量、设备的运营状态检测、故障排查、维修、不同质量开采矿石的搭配及相关调度控制有重要作用[2]。因此，对露天矿运输调度问题展开优化研究，对提升矿山生产设备的利用率、降低生产成本具有直接影响，从而决定了露天矿整个生产系统的生产效率和经济效益的好坏[3]。

露天矿运输调度优化的目标是在满足一定生产条件下，寻求运输成本最小的运输调度方案，属于函数最值优化问题。针对函数优化问题，近些年来，受自然界生物的群体行为启发而产生的群体智能计算已成为新兴的优化算法[4]。其中Eberhart与Kennedy提出的粒子群(Particle Swarm Optimization,PSO)算法是一种模拟鸟群飞行觅食的仿生算法，具有简洁、易于实现、鲁棒性好等特点，在函数优化领域已被广泛接受。PSO算法虽然在函数优化求解过程中能够快速收敛，但出现陷入局部区域而无法逃出的可能性很大，导致得到的最优解是局部优化解[5]。因此，针对露天矿运输调度问题的复杂性，本文首先对PSO算法搜索系数进行改进，以增强其全局搜索能力，并在此基础上，结合露天矿运输调度问题，对PSO算法的粒子搜索策略进行改进，并尝试用改进的PSO算法对露天矿运输调度问题进行优化研究。

1 露天矿运输调度数学模型

设露天矿当前各作业采区运往各卸料点的矿量为xij,其中下标字母i表示采区个数，且有i=1,2,…,I;下标字母j表示卸料点个数，且有j=1,2,3…,J；在各采区开采量和各卸料点受矿能力已知的条件下，以完成生产任务前提下的运输费用最小为目标，以露天矿各采区的开采量和各卸料点的受矿能力为约束条件，构建露天矿运输调度的数学模型。

1) 露天矿最小运输成本目标。通常情况下，露天矿山一般采用多个采区同时开采，而采出的矿石要运往不同的卸料点，由于各采区至每个卸料点的运距不同，运输矿石的成本随运距的变化也会不同，由此建立目标函数如下：

式中，Cij表示将矿量xij从露天矿第i个采区运往第j个卸料点的的运输成本，元/m3。

2) 开采矿量约束。露天矿每个采区的矿石采出以后被运往各卸料点，而从每个采区运出的矿石量要等于每个采区开采的矿石量。约束条件表达式如式(2)所示。

式中，Qi表示第i个采区开采矿量，m3。

3) 受矿能力约束。每个卸料点的受矿能力时一定的，因此各采区运往同一卸料点的总矿石量应当满足卸料点的受矿能力。

式中，Rj表示第j个卸料点的容量，m3。

4) 变量非负条件。每个采区运往每个卸料点的矿量不能为负值，即要求每个变量不小于0。

基于上述目标函数和约束条件描述，构建露天矿运输调度数学模型：

2 用PSO算法求解露天矿运输调度问题的方法

2.1 粒子群算法及其参数计算

本文不对基本粒子群算法过程做详细描述，仅列出算法相关公式，以供后文描述应用。设在D维搜索空间，xi=(xi1,xi2,…,xiD)表示第i个粒子的位置信息，其速度vi=(vi1,vi2,…,viD)。BestPi=(Pi1,Pi2,…,PiD)为第i个粒子在D维空间的最好位置，粒子群当前的最好位置记为BestG=(G1,G2,…,GD)。粒子的每一维属性信息将根据式(6)和式(7)进行更新。

vid(t+1)=ω×vid(t)+

c1rand()[Pid(t)-xid(t)]+

式中:t表示粒子更新次数；vid(t)表示当前粒子的每一维速度信息，xid(t)表示当前粒子的每一维位置信息；rand()在[0,1]之间的随机产生；ω为粒子搜索的惯性系数。c1和c2为学习因子，用于控制粒子搜索的步长。需要说明的是为了引导粒子能够进入搜索空间，粒子的搜索速度不能太大，也不能太小，通常会被限制在给定的搜索区间[-v(max),v(max)]中，一般选择用v(max)=σx(max)，0.1≤σ≤1.0[6]，其中[-x(max),x(max)]为粒子每一维的搜索空间范围。

由于PSO算法在寻优搜索过程中容易出现早熟并陷入局部最优，从而使PSO算法的应用得到了巨大限制。而当惯性权重ω以不变或线性方式递减时，搜索粒子会出现进入局部极值点邻域而难以跳出的情况，致使算法无法找到全局最优解[7]。另外，学习因子对粒子的算法的寻优速度具有重要的影响。因此，为了改善粒子的寻优能力，采用用如下方式计算粒子的搜索参数。

1) 惯性权重。对惯性权重ω采用以“S”形函数递减[8]。如式(8)所示，粒子在搜索过程的初期以较高的飞行速度进行搜索，在搜索过程的中期，粒子飞行速度快速下降，在搜索过程的后期，粒子则保持一定的搜索速度进行最后的收敛.

式中：ωmax、ωmin为惯性系数的最大取值和最小取值，这里ωmax=0.9，ωmin=0.4；t和tmax分别为当前粒子更新次数和最大更新次数；τ为控制系数，用于调节惯性权重变化速度的快慢，一般τ=10。

2) 学习因子调节。为加快粒子搜索速度，在搜索开始采用较大的c1和较小的c2,目的是使粒子遍历整个搜索空间而不屈于局部极值点；在迭代后期则采用较小的c1和较大的c2,以便粒子趋于全局最优解。学习因子调节公式如式(11)、式(12)所示[9].

式中，c1initial=2.5，c2initial=0.5，c1final=0.5，c2final=2.5。

通过对PSO算法的惯性权重和加速系数的调节，可保证粒子在全局范围内快速搜索寻优。因此，在对PSO算法搜索参数进行调整的基础上，结合露天矿运输调度模型，下文将研究用PSO算法解算露天矿运输调度模型。

2.2 求解露天矿运输调度问题的带双引子PSO算法

本文讨论的露天矿运输调度问题是一个带约束的函数优化问题，约束条件的有效处理，对于函数优化求解至关重要.因此本文考虑用约束条件构建目标函数，将单目标露天矿运输调度问题转化为多目标问题.依据上述思想，首先对式(5)中的约束条件进行如下处理：

式中：vio(x)用于衡量计算结果违反约束条件的程度；θj(x)为不等式约束条件；φ(x)为等式约束条件；ε为等式约束容忍度，表明计算的各采区输出矿量和开采矿量出入在[-ε,ε]之间是可接受的，ε通常取很小的正数。

经式(11)对露天矿运输调度模型的约束条件处理后，式(5)可被转化成如下多目标优化问题形式：

需要说明的是，当vio(x)=0时，当前解满足约束；当vio(x)≠0时，当前解不满足约束。这里定义vio(x)=0的区域为可行解区域，vio(x)≠0的区域为不可行解区域。在粒子搜索过程中，在不可行解区域内的粒子经过迭代更新运算以后向可行解区域运动，为了加速这一运动过程，提高粒子算法的搜索效率，本文提出带双引子的PSO算法，所谓双引子是指粒子在搜索过程中采用两个个体极值对自身的速度和位置信息进行更新运算。对处于可行解区域外的粒子，使用离自己最近而且在可行解区域内的粒子(BestPS)和全局最优粒子(BestG)更新其信息,该策略可以吸引整个种群快速进入可行域；对处于可行解区域内的粒子，可依据粒子自身的个体极值和粒子群的全局极值更新其位置和速度.带双引子的粒子移动搜索原理如图1所示。图1显示，在一般粒子群的搜索策略下，粒子被BestG和BestP吸引，从P(t)移动到P1(t+1);在带双引子的搜索策略下，粒子被BestG和BestPS吸引，从P(t)移动到P2(t+1);粒子在双引子吸引下，以更快的进入至阀值内区域。

图1 双吸引子作用下的粒子移动搜索原理

2.3 算法应用实现

根据前文构建的露天矿运输调度优化数学模型，设计粒子群算法的粒子编码方式。用每个粒子代表一种露天矿运输调度方案，粒子的每一维表示一条露天矿采区至卸料点的运输路径(粒子的维数可用I×J表示)，粒子的每一维位置信息表示露天矿每个运输路径上的运输矿量，将露天矿运输的综合生产作业成本作为PSO算法的适应度函数。在此基础上，采用带双引子PSO算法对露天矿运输调度模型进行解算，其解算过程描述如下。

1) 粒子群初始化。随机给定一个初始粒子群，且保证有粒子在可行域内。

2) 确定粒子群解算初始参数。粒子初始速度和初始位置在允许范围内随机生成，根据粒子的适应度值，计算粒子群的初始个体极值BestP和全局极值BestG.

3) 停止条件判定。在实际应用中，一般以限定迭代次数或连续几次迭代记录的最优解无法改善为限定条件。本文采用限定最大迭代次数作为终止条件，即t≤tmax。

4) 计算惯性权重ω和加速系数c1和c2。

5) 粒子更新操作。可行解区域外粒子以BestPS和BestG为双引子，用式(6)、式(7)更新其位置和速度信息；可行解区域内粒子用BestP和BestG直接以式(6)、式(7)更新其位置和速度信息.

6) 极值更新操作。依据粒子的适应度函数，计算更新粒子群的个体极值和全局极值.

7) 令t=t+1,返回(3)停止条件判定。

8) 解算结束，输出最优结果。

3 实例验证

为验证应用带双引子PSO算法优化露天矿运输调度问题的有效性，以某露天矿实际生产数据为验证实例进行实证研究。已知露天矿共有9个矿石开采采区和5个处在不同位置的矿石卸料点。各采区的开采矿量、各卸料点的受矿能力及各采区至每个卸料点的运输费用如表1所示。

依据实例数据，确定粒子群的初始化参数为：粒子数m=50，粒子维数k=45，惯性权重由式(8)计算得到，学习因子由式(9)、式(10)计算得到，粒子的每一维搜索变化范围为[0，xij(max)]，粒子最大搜索速度Vmax=0.1*xij(max)，取最大迭代次数tmax=1000。结合实例数据和上述参数，以MATLAB 7.1为平台，用计算机编程技术，实现露天矿运输调度数学模型解算，通过控制最大迭代次数tmax，给出露天矿运输调度数学模型的PSO解算迭代过程(图2)，求得各运输路径上运输矿量X的解如表2所示。按照优化给出的各运输路径的运输矿量，可对每个采区和运输路径的运输设备进行合理分配，实现整个运输调度系统的优化。

表1 各采区至每个卸料点的运输费用

表2 各路径运输矿量计算结果

图2 求解运算迭代分布图

依据表2给出露天矿运输调度优化结果和现行实际结果数据，优化解算得到的运输综合成本为44090万元，而实际现行运输方案的运输综合总成本为49740万元，通过和现行实际数据对比，结果显示优化解算得到的运输综合成本比实际减少了5650万元，另外，从表2给出的各运输路径的运输矿量优化结果可以看出，改进PSO算法优化结果满足实际生产要求，证明带双引子PSO算法在露天矿运输调度优化应用中的有效性。

4 结论

通过对露天矿运输调度问题分析，构建了以最小综合运输成本为目标函数的运输调度数学模型，针对模型提出用改进的PSO算法对模型进行解算的方法。经过实例数据验证，显示计算结果符合露天矿生产实际，并能有效减少运输成本。因此，本文提出的改进PSO算法在露天矿运输调度优化应用中是有效的，可用于指导露天矿实际生产中运输设备的调度和分配，具有较好的应用前景。

[1]姚再兴,刘海娟.遗传算法在大型露天矿卡车优化调度中的应用[J].露天采矿技术,2007(5):44-47.

[2]鞠兴军,李林,刘光伟.基于遗传算法的神经网络在露天矿卡车调度系统中的应用研究[J].露天采矿技术,2009(6):31-33.

[3]孙效玉,宋守志.露天矿卡车优化调度系统实时调度方法[J].金属矿山,2005(8):14-17.

[4]高尚，杨静宇.群智能算法及其应用[M].北京:中国水利水电出版社，2006.

[5]纪震，廖慧连，吴青华.粒子群算法及应用[M].北京：科学出版社，2009.

[6]陈应显，韩明峰.改进粒子群算法的露天矿路径优化研究[J].微电子学与计算机，2011,28(11):61-64.

[7]王洪涛,任燕.基于改进惯性权重的粒子群优化算法[J].计算机应用与软件,2011,28(10):271- 274.

[8]王建国，阳建宏，云海滨,等.改进粒子群优化神经网络及其在产品质量建模中的应用[J].北京科技大学学报，2008,30(10):1188-1193.

[9]Ratnaweera A,Halgamuge S K,Watson H C.Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficient.IEEE Trans Evol Comput,2004:240.

[10]刘衍民,牛奔,赵庆祯.求解约束优化问题的多目标粒子群算法[J].计算机应用研究,2011,28(3):851-853.

Open-pithaulingdispatchingoptimizationbasedonimprovedPSOalgorithm

LI Yong1,2，HU Nai-lian1，LI Guo-qing1

(1.School of Civil and Environmental Engineering,University of Science and Technology Beijing100083,China；2.State Key Laboratory of High-Efficient Mining and Safety of Metal Mines(University of Science and Technology Beijing),Ministry of Education,Beijing100083,China)

A mathematical model of open-pit hauling dispatching was constructed from the view point of minimizing open-pit transportation cost.Based on the theory of swarm intelligence optimization,a method of using particle swarm optimization algorithm to optimize open-pit mining operation plan was proposed in this paper,and the search strategy with double attractor was designed for particles in the calculation process.With MATLAB software as a computation platform,the model was calculated by using computer programming technology.With taking the actual production data of an open pit mine as an example,the effectiveness for using improved PSO(Particle Swarm Optimization) algorithm to solve open-pit hauling dispatching problem was verified.

particle swarm algorithm；open-pit mine；hauling dispatching；optimization

TD57

B

1004-4051(2013)04-0098-04

2012-12-07

中央高校基本科研业务费专项资金资助(编号：FRF-SD-12-001A)；国家自然科学基金项目资助(编号：51104010)

李勇(1985-)，男，博士研究生。E-mail：yongli9898@hotmail.com。