露天煤矿车辆的不确定调度模型与优化求解

薛雪，孙伟，刘晓文

（中国矿业大学 信电学院，江苏 徐州，221008）

露天煤矿车辆的不确定调度模型与优化求解

薛雪，孙伟，刘晓文

（中国矿业大学 信电学院，江苏 徐州，221008）

以内蒙古一露天煤矿为研究对象，对露天矿车辆调度过程中的关键时间参数进行统计分析，确定其随机性，建立车辆调度的不确定模型。在对不确定调度模型优化分析的过程中，训练神经网络逼近函数，对于粒子群算法容易陷入局部收敛的缺陷，结合模拟退火算法的局部搜索技术，得到模拟退火算法和粒子群算法相结合的混合智能算法。计算实验结果证明该算法的有效性和优越性。

不确定调度；车辆调度；粒子群算法；模拟退火算法；混合智能算法

车辆调度问题（VRP）是广泛应用于交通运输、物流配送等领域的一类组合优化问题，而在车辆实际的服务过程中，总会遇到这样或那样的不确定信息，必须根据一定的准则对已安排好的车辆路径进行及时调整更新。在这种情况下，确定型VRP的理论和方法不再具有处理这些问题的能力，需要研究一整套新的与确定型VRP相对应的不确定信息VRP理论和方法。目前对于不确定车辆调度的研究主要集中在随机VRP和模糊VRP方面，基本上都是采用启发式算法进行求解。如陆琳等[1]运用一种新型的混合粒子群算法，康喜兵等[2]应用禁忌搜索算法，陈宝文等[3]运用蚁群算法、宋远清等[4]应用遗传算法求解随机需求车辆路径问题。张杨等[5]对随机旅行时间车辆路径问题进行了研究；娄山佐[6]针对多库房随机车辆路径问题，设计一个自适应交叉熵法解决子系统随机VRP；骆正山等[7]应用一种基于模糊可能性的混合遗传算法求解模糊需求VRP；甘勤涛等[8]运用禁忌搜索算法求解模糊需求VRP；Zheng等[9]运用一种混合智能算法求解车辆模糊旅行时间FVRP问题；张建勇等[10]]对模糊预约时间FVRP问题进行了研究。而对于露天煤矿车辆调度问题，目前主要还是通过建立具有严格约束的数学模型，采用精确的求解算法来解决。但是，由于露天煤矿车辆调度模型的复杂性，很多计算参数很难确定，模型的建立和求解的结果有时不能符合实际需求，这就给不确定优化提供了空间[11−13]。目前，对于露天煤矿车辆调度的不确定优化研究较少，因此，研究露天煤矿车辆调度不确定优化有很重要的理论意义。在此，本文作者以内蒙古一露天煤矿为例，对车辆调度过程中的关键时间参数进行统计分析，确定其随机性，在确定型模型的基础上，建立车辆的不确定调度模型——随机期望值模型。对于该模型的求解，通过训练神经网络逼近不确定函数，并且针对粒子群算法容易陷入局部收敛的缺陷，结合模拟退火算法的局部搜索策略，经过仿真证明这种混合智能算法提高了全局收敛性，得到了较满意的结果。

1 问题的提出

以内蒙古某一露天煤矿达产时期运输系统为例[13]，对车辆调度系统建立模型并求解。该矿主要开采中、上两层煤，设计能力为100万t/a，采用国产4.6 m3斗容的单斗挖掘机和苏制42 t贝拉斯汽车。该矿有8个铲位，包括6个装岩点、2个装煤点；3个卸点，包括2个排土场、1个煤转站。剥离电铲6台，采煤电铲2台，电铲容量4.6 m3，现有容量为42 t的卡车51台，班出动率0.55。卸煤时间1.5 min，卸岩时间1.0 min。露天矿生产实行三班制，每班8 h，除去吃饭、休息和换班的时间，班纯工作时间为6 h。剥离电铲1个班内的最大产量为960 m3，采煤电铲1个班次内的最大产量为1 290 t，剥采比：4.6 m3/t。

采用完成生产任务的条件下，出动卡车数最少为目标函数的车流规划模型[13]。将确定车辆调度模型描述如下：

式中：Nt为实动卡车台数；Tij为从卸载点i到装载点j路径上的空运时间；Lij为从卸载点i到装载点j路径上的装载时间；Qij为从卸载点i到装载点j路径上的等装时间；Xij为从卸载点i到装载点j路径上的空车流量，单位为车/min；m和n分别为卸载点数和装载点数。约束条件如下。

式中：Rj为第j个电铲最大生产能力；Di为第i个卸矿点最大卸载速率，单位为车/min；∆V为允许的剥离产量波动量，单位为m3/min；Po为卡车载矿容量，单位为t；Pw为卡车载岩容量，单位为m3；Sr为生产剥采比，单位为m3/t；m1和n1分别为卸载岩石点数和装载岩石点数。

约束条件中，式（2）和式（3）是车流连续性约束，保证各装（卸）载点的流入与流出车流量相等；式（4）是电铲采装能力约束，保证采掘速率不超过其最大生产能力；式（5）是卸矿点处理能力约束，保证卸载速率不超过最大处理能力；式（6）是生产剥采比约束，用于平衡生产；式（7）是非负约束。

2 露天煤矿车辆调度不确定模型的建立

2.1 露天煤矿车辆调度不确定信息统计分析

露天煤矿生产系统庞大且复杂，运输环节也包含很多方面，实际上，运输中存在许多不确定因素，如道路运行时间、装载点产量、卸载点产量、剥采比等。露天矿车辆调度中有3个关键的时间参数，即道路运行时间、电铲装车时间和卸点卸车时间。掌握准确的道路运行时间、电铲装车时间和卸点卸车时间，是车辆调度中车流规划的基础。王强等[14]对这3个主要时间参数的概率分布进行了分析，分析结果为：道路运行时间符合正态分布；电铲装车时间的分布相对复杂，符合对数正态分布、对数逻辑分布、逆高斯分布；卸点卸车时间比较稳定，可近似看作1个常数。

本文对卸点卸车时间不进行进一步分析，直接使用历史经验数据，而对道路运行时间和电铲装车时间进行数据采集，并对数据进行分布拟合，求得其分布函数。

2.1.1 装车时间随机性统计

电铲装车时间是指从卡车进入装车区域开始到电铲装载完毕卡车离开装车区域为止所需时间。其中，装车时间包括电铲装车时间和待装时间，当然也包括调车时间，在这种意义上说，统计装车时间，更符合现场数据需求，也更方便。

露天煤矿中有采煤电铲和剥离电铲，采煤和剥离工作有所区别，并且由于煤矿和岩石的块度以及松散度不同，所以电铲装载煤矿和岩石的时间就有所差别，其装车时间是不同的。该矿有2台采煤电铲，6台剥离电铲，本文对两种电铲装车时间数据分开采集，并分开进行处理。在现场，分别对剥离电铲的装车时间和采煤电铲的装车时间，进行1个班次内的统计，对统计数据处理以后，各取出100个数据，剥离电铲的装车时间（min）为：6.58，7.28，7.71，6.76，9.70，8.17，7.56，8.00，6.68，8.16，6.73，8.49，7.25，7.81，7.26，6.51，6.88，7.00，8.51，9.10，7.90，8.37，8.43，7.97，7.67，6.55，7.85，6.00，6.71，7.37，6.06，9.29，8.15，7.81，7.52，7.56，6.22，7.73，7.00，7.28，7.14，6.24，6.19，6.77，6.45，7.00，7.32，8.42，7.26，7.08，7.34，6.48，6.20，6.96，6.33，7.32，6.63，7.15，6.85，7.78，7.32，7.26，5.84，7.08，7.44，6.48，8.31，7.15，7.36，6.04，7.10，6.80，8.10，8.10，6.26，7.41，8.69，6.67，6.56，6.83，10.15，7.87，6.98，5.50，6.73，7.52，5.80，6.70，6.41，6.96，9.40，8.25，6.21，6.88，7.92，7.10，7.24，7.73，7.77，6.50。

对装车时间数据只用对数逻辑分布、逆高斯分布和对数正态分布进行拟合，拟合结果如图1所示。由于对数正态分布曲线和逆高斯拟合曲线基本一致，所以在图中看来是重合的。通过拟合发现：剥离电铲装车时间服从对数正态分布或逆高斯分布。经计算，该分布的均值（期望）为7.28，方差为0.872，为方便描述，用LN（7.28, 0.872）表示该分布。

接着，对采煤电铲装车时间数据也进行如上分布拟合，同样取100个数据，由于篇幅有限，所取数据在此没有列出。拟合结果显示，采煤电铲装车时间服从期望为8.75、方差为1.062的对数正态分布，即LN（8.75,1.062）。

2.1.2 道路运行时间随机性统计

图1 剥离电铲装车时间分布拟合Fig.1 Distribution fitting of loading time of stripper shovel

鉴于数据量比较大，重车运行时间的统计结果没有列出，直接把数据放在MATLAB中进行拟合，对其他每个重车运行时间都进行同样处理，求出分布参数，如表1所示。

表1 重车运行时间Table 1 Travel time of laden trucks min

2.2 露天煤矿车辆调度不确定模型

作为不确定优化的一种类型，根据不同的决策准则，随机规划可分为期望值、机会约束规划和相关机会规划这3种基本模型[15]。由于露天煤矿车辆调度该模型中，随机参数只存在于目标函数中，所以，采用随机期望值模型。

对于优化问题中出现的不确定变量，相应地都有该变量的数学期望的概念。基于此，建模方法是在期望约束成立下极大化这些不确定目标函数的数学期望即期望值模型，其一般形式如下：

其中：x为决策向量；ξ为随机变量；f（x,ξ）表示目标函数；gi（x,ξ）表示随机约束函数；E表示期望值算子。

在实际的露天煤矿车辆调度建模过程中，根据式（8）的一般期望值模型，结合式（1）的确定型模型，目标函数仍采用班车辆出动最少的模型，可以得到不确定模型——随机期望值约束模型如下：

在目标函数中，E为期望算子，Xij和Yji为决策变量，Tij和Dji为确定性参数，Lij和Tji为随机时间参数变量。由于目标函数中含有不确定变量，所以，将出动车辆的期望值最小作为目标函数。

由于约束条件均不包含不确定变量，所以，约束条件不变，见式（2）～（7）。另外，规定岩石卸载时间为1.0 min，卸煤的时间为1.5 min。

把2.1节求得的参数的概率分布代入，得到具体的不确定模型如下：

其中：X为空车流量；Y为重车流量；L1为剥离电铲的装车时间；L2为采煤电铲的装车时间；T为相应的重车运行时间。

3 露天煤矿车辆调度不确定模型的求解

近年来，粒子群算法在车辆调度方面得到了广泛的应用。因此，对于所建立的露天煤矿车辆的不确定调度模型，首先训练神经网络逼近不确定函数，接着采用粒子群算法进行优化，并且针对粒子群算法容易陷入局部最优的缺陷，结合模拟退火算法局部搜索策略，提出一种混合智能策略。

3.1 策略思想

粒子群算法因其计算简单、参数设置少和良好的算法收敛性，已被广泛应用于各个领域。但是，在应用过程中，人们发现粒子群算法也具有随机搜索算法比较普遍的缺点，主要有：

（1） 粒子群算法容易陷入局部极值点中，导致得不到全局最优解。造成这种现象的原因有2个：一是待优化函数许多是多峰函数，形状复杂，而粒子群优化算法并不能从理论上严格证明收敛于任何类型函数的全局极值点，因此，对于复杂的应用模型，有时可能难以得到满意的结果；二是由于算法的参数设计或者粒子数的选择不当，使得在计算过程中，粒子的多样性迅速消失，造成算法“早熟”，从而导致算法不能收敛到全局极值点。

（2） 粒子群优化算法的收敛速度比较慢。原因是粒子群优化算法并没有很充分的利用计算过程中得到的信息，在每次迭代时，只是利用了个体最优和全局最优，因此，不能在一定的时间内达到相应的精度[16−17]。

粒子群算法中粒子通过跟踪2个极值来更新自己，算法结构运行简单，不需调整太大参数且不需要梯度信息，早期收敛速度快，但后期受随机振荡现象的影响，使其在全局最优值附近需要较长的搜索时间，收敛速度慢，极易陷于局部极小值，精度降低，易发散，调整学习因子和惯性因子也无法完全避免。因此，将粒子群算法与模拟退火算法融合在一起，以克服局部收敛的缺陷。

SA算法的最主要特征就是具有跳出局部极值点区域的能力，能寻找到全局最优或近似最优，而与初始点的选择无关。模拟退火算法由于其固有的密集计算特性，存在运行时间长和计算内存大等问题，这是大数据库求解的主要瓶颈。模拟退火算法的并行实现技术能大幅度地提高其性能，从本质上减少计算时间。

3.2 算法流程

步骤1通过随机模拟为不确定函数产生输入输出数据（即训练样本）。

将式（10）中模型的车流量依次转化为x1,x2, …,xn（n为路径总数）。根据随机变量qi（这里表示时间参数）的分布，应用随机模拟技术为不确定函数

产生N个输入输出数据（xl,yl），每次均模拟T1代。

步骤2根据产生的训练样本训练神经网络以逼近不确定函数。

步骤3初始化包含popsize个个体的粒子种群，初始化个体最优pbest、全局最优gbest和最优适应度。设置包括最大迭代次数gen、惯性权重w、加速常数c1和c2等在内的各参数。初始化退火模拟算法的参数：搜索步长η，退温系数λ，初始温度，最大搜索步数L。

步骤4通过训练好的神经网络计算每个粒子的目标值，并根据目标值计算每个粒子的适应度。

步骤5对约束条件进行处理，并根据处理原则更新每个粒子的最优和全局最优，记录历史最优值，更新最优位置。

步骤6对群体最佳位置应用基于SA的局部搜索策略。

步骤7更新各粒子的速度和位置。

步骤8重复步骤4～7，直到达到迭代结束条件为止。

步骤9找到最好的粒子作为最优解，求出最优目标。

3.3 基于模拟退火的局部搜索

为避免PSO算法早熟收敛，结合SA的局部搜索技术，对第k代种群的最优位置gbestk进行更新，以帮助种群跳出局部最最小。

局部搜索的算法流程如下。

步骤1令m=1，gbest’=gbestk

步骤2采用下式产生1个新解：

其中：η为搜索步长；N（0,1）为服从均值为0、方差为1的高斯分布的随机数；Xmax和Xmin分别为变量的上、下界。

步骤3计算pa。

（1） 若x′可行，gbest′不可行，则pa=1；

（2） 若x′不可行，gbest′可行，则pa=0；

（3） 若x′和gbest′均可行，则

步骤4随机产生0到1之间均匀分布的随机数rand（ ），若pa≥rand（ ），则gbest′=x′。

步骤5令m=m+1。若m＞L（其中L是事先设定的最大局部搜索步数），则输出gbest′作为种群的最优位置，否则返回步骤2。

在算法中，f是目标值，也是适应度函数；viol是约束违反量函数；另外，初始温度按如下经验公式确定：

其中：fmax和fmin分别为初始种群中粒子的最大目标值和最小目标值。另外，算法采用指数退温，即T（k+1）=λ·T（k）。

3.4 仿真结果

参数选取如下。

（1） 随机模拟3 000代，产生2 000个训练样本，神经网络训练中网络结构为38-20-1：输入神经元38个，隐含神经元20个，输出1个。

（2） 粒子群参数：粒子种群规模为200，迭代次数为300次，学习因子c1=c2=2.05，惯性权重w采用线性递减法，wmax=0.9，wmin=0.4。

（3） 模拟退火参数：搜索步长η=0.005，局部最大搜索步数L=40，退温指数λ=0.94。

经过20次的独立仿真，取最好的优化结果，其迭代曲线如图2（a）所示。

最优的车流数据如下：

20次目标值的平均值为28.085 5，即最少出动卡车28台。

为了便于比较，直接应用粒子群算法，参数设置与前相同，经过仿真调试，重新进行20次仿真，求得目标值为34.794 7，迭代曲线如图2（b）所示。

图2 迭代曲线图Fig.2 Relationship between fitness values and generation

通过对上述典型算例的仿真研究，可对混合优化策略得到如下结论：

（1） 从图2（b）可看出：粒子群算法收敛速度较快，但是最终结果并不是最优解，而是陷入了局部最优，得到的结果并不是全局最优值。

（2） 从图2（a）可看出：基于退火−粒子群的混合智能算法比粒子群算法性能优越，使用退火−粒子群算法得到了全局最优解，求得的目标值28.085 5比34.794 7要小得多，并且收敛速度也不比基于粒子群算法的混合智能算法的收敛速度低。

4 结论

（1） 通过对露天煤矿车辆调度中不确定因素的分析，将不确定优化理论引入到露天煤矿车辆调度中，综合运用车辆的不确定调度理论，得到了露天矿车辆的不确定数学模型，能够更好地反映现实问题，得到的调度方案更具有弹性。

（2） 在不确定车辆调度模型的优化求解过程中，训练神经网络进行函数逼近，并且将模拟退火算法的局部搜索技术融入到粒子群算法中，形成的混合智能算法优势互补，提高了算法的收敛速度和全局收敛性，为粒子群算法开辟了新的应用领域，也为不确定优化问题的求解提供了新的方法。

[1] 陆琳, 谭清美. 一类随机需求VRP的混合粒子群算法研究[J].系统工程与电子技术, 2006, 28（2）： 244−247.

LU Lin, TAN Qing-mei. Hybrid particle swarm optimization algorithm for stochastic vehicle routing problem[J]. Systems Engineering and Electronics, 2006, 28（2）： 244−247.

[2] 康喜兵, 甘勤涛. 随机需求车辆路径问题的禁忌搜索算法研究[J]. 科学技术与工程, 2006, 6（13）： 1882−1884.

KANG Xi-bing, GAN Qin-tao. Research on the tabu search for vehicle routing problem in the case of stochastic demand[J]. Science Technology and Engineering, 2006, 6（13）： 1882−1884.

[3] 陈宝文, 宋申民, 陈兴林. 随机需求车辆路径问题及其启发式算法[J]. 计算机工程与设计, 2007, 28（1）： 138−142.

CHEN Bao-wen, SONG Shen-min, CHEN Xing-lin. Vehicle routing problem with stochastic demands and its modify ant colony system[J]. Computer Engineering and Design, 2007, 28（1）： 138−142.

[4] 宋远清, 李永生, 梁慎清, 等. 需求随机车辆调度问题的遗传算法研究[J]. 计算机技术与发展, 2009, 19（2）： 230−233.

SONG Yuan-qing, LI Yong-sheng, LIANG Shen-qing, et al. Study of genetic algorithm for vehicle routing problem with stochastic demands[J]. Computer Technology and Development, 2009, 19（2）： 230−233.

[5] 张杨, 黄庆, 卜祥智. 随机旅行时间局内车辆路径问题的模型及其算法[J]. 管理工程学报, 2006, 20（3）： 82−85.

ZHANG Yang, HUANG Qing, BU Xiang-zhi. Model and algorithm for on-line vehicle routing problem with stochastic travel time[J]. Journal of Industrial Engineering and Engineering Management, 2006, 20（3）： 82−85.

[6] 娄山佐. 一种解决多库房随机车辆路径问题方法[J]. 系统仿真学报, 2009, 19（4）： 879−882.

LOU Shan-zuo. Method for solving multi-depot stochastic vehicle routing problems[J]. Journal of System Simulation, 2009, 19（2）： 230−233.

[7] 骆正山, 王小完. 基于模糊条件下车辆路径问题的研究[J].微电子学与计算机, 2005, 22（3）： 181−184.

LUO Zheng-shan, WANG Xiao-wan. Study of the vehicle routing problem basing fuzzy station[J]. Microelectronics, 2005, 22（3）： 181−184.

[8] 甘勤涛, 阳平华, 童钟灵. 模糊需求车辆路径问题的禁忌搜索算法研究[J]. 长春理工大学学报, 2006, 29（1）： 84−86.

GAN Qin-tao, YANG Ping-hua, TONG Zhong-ling. Research on the tabu search for vehicle routing problem in the case of fuzzy demand[J]. Journal of Changchun University of Science and Technology, 2006, 29（1）： 84−86.

[9] ZHENG Yong-shuang, LIU Bao-ding. Fuzzy vehicle routing model with credibility measure and its hybrid intelligent algorithm[J]. Applied Mathematics and Computation, 2006, 176（2）： 673−683.

[10] 张建勇, 李军, 郭耀煌. 具有模糊预约时间的VRP混合遗传算法[J]. 管理科学学报, 2005,8（3）： 64−71.

ZHANG Jian-yong, LI Jun, GUO Yao-huang. Hybrid genetic algorithm to vehicle routing problem with fuzzy due-time[J]. Journal of Management Sciences in China, 2005, 8（3）： 64−71.

[11] 张幼蒂. 卡车−电铲优化调度理论及应用[R]. 徐州： 中国矿业大学采矿工程系, 1993： 22−78.

ZHANG You-di. Theory and application on truck optimization dispatching[R]. Xuzhou： China University of Mining and Technology. Department of Mining Engineering, 1993： 22−78.

[12] 张幼蒂, 苏婧, 李曙光. 计算机控制卡车实时调度的系统研究[J]. 中国矿业大学学报, 1995, 24（2）： 1−6.

ZHANG You-di, SU Jing, LI Shu-guang. Systematic study on computer-controlled truck real-time dispatching[J]. Journal of China University of Mining and Technology, 1995, 24（2）： 1−6.

[13] 苏婧. 计算机控制卡车调度系统的理论与应用研究[D]. 徐州：中国矿业大学采矿工程系, 1995： 25−55.

SU Jing. Theory and systematic study on computer-controlled truck dispatching[D]. Xuzhou： China University of Mining and Technology. Department of Mining Engineering, 1995： 25−55.

[14] 王强, 张莹, 陈冲, 等. 露天矿卡车调度关键时间参数的概率分布[J]. 煤炭学报, 2006, 31（6）： 761−764.

WANG Qiang, ZHANG Ying, CHEN Chong, et al. Probability distribution of key time parameters in open-pit mine truck dispatching[J]. Journal of China Coal Society, 2006, 31（6）： 761−764.

[15] 彭锦, 刘宝碇. 不确定规划的研究现状及其发展前景[J]. 运筹与管理, 2004, 11（2）： 1−10.

PENG Jin, LIU Bao-ding. Uncertain programming： Current status and future prospects[J]. Operations Research and Management Science, 2004, 11（2）： 1−10.

[16] 高鹰, 谢胜利. 基于模拟退火的粒子群优化算法[J]. 计算机工程与应用, 2004, 40（1）： 47−50.

GAO Ying, XIE Sheng-li. Particle swarm optimization algorithms based on simulated annealing[J]. Computer Engineering and Applications, 2004, 40（1）： 47−50.

[17] 王凌, 刘波. 微粒群优化与调度算法[M]. 北京： 清华大学出版社, 2008： 62−69. WANG Ling, LIU Bo. Particle swarm optimization and scheduling algorithms[M]. Beijing： Tsinghua University Press, 2008： 62−69.

（编辑 杨幼平）

Uncertain scheduling model and optimization of vehicle in open mine

XUE Xue, SUN Wei, LIU Xiao-wen
（School of Information and Electrical Engineering, China University of Mining and Technology, Xuzhou 221008, China）

Taking an open mine in Inner Mongolia as the research object, the randomness of the key time parameters in vehicle scheduling was determined through statistical analysis, and the uncertain model of vehicle scheduling was given. Neural network was trained to approximate function. Because the particle swarm algorithm was likely to fall into local convergence, combining the local search method of the simulated annealing algorithm, a hybrid intelligent algorithm which consisted of the simulated annealing algorithm and the particle swarm optimization was proposed to solve the uncertain model. The results show that the high performance and effectiveness of the proposed method is improved through the computational results.

uncertain scheduling; vehicle scheduling; particle swarm optimization; simulated annealing optimization; hybrid optimization algorithm

TP391.9

A

1672−7207（2011）05−1354−07

2010−08−20；

2010−11−29

国家高技术研究发展计划（“863”计划）项目（2007AA06Z114）；中国矿业大学青年科研基金资助项目（0C080250）

薛雪（1980−），女，江苏徐州人，讲师，从事生产调度、智能调度的研究；电话：13512565965；E-mail： cumtxx@126.com