车辆的优化调度

第18卷第2期四川理工学院学报(自然科学版)Vol.18No. 2JOURNAL OF SICHUAN UNIVERSITY OF2005年6月SCIENCE & ENGNNEERING( NATURAL SCIENCE EDITION )Jun.: 2005文章编号: 1673- -1549 ( 2005) 02- 0094 -05车辆的优化调度兰恒友(四川理工学院数学系，四川自贡643000)摘要:建立露天矿生产及车辆安排问题的多目标规划模型，综合考虑卡车、铲车、卸点、铲位等生产设备的利用，并给出了其相应的遗传算法和最大熵算法。关键词:多目标规划模型;车辆安排;露天矿生产;遗传算法;最大熵算法中图分类号: 0221.3文献标识码: A钢铁工业是国家工业的基础之- -， 铁矿是钢铁工业的主要原料基地。为了提高露天矿生产的大型设备的利用率，建立一个班次的最优生产计划是非常有必要的。该计划主要包括:出动几台电铲，分别在哪些铲位上;出动几辆卡车，分别在哪些路线上，各运多少次。此外，还应该考虑总运量最小，同时出动最少的卡车，从而运输成本最小;或者考虑利用现有车辆，获得最大的产量(岩石产量优先;在产量相同的情况下，取总运量最小的解)。本文就上述两条原则分别建立露天矿生产及车辆安排问题的多目标规划模型,综合考虑卡车、铲车、卸点、铲位等生产设备的利用，并给出了求解该问题的遗传算法和最大熵算法。最后以一实例验证了上述算法的可行性和快速性。1模型的建立全文假设各种设备在一一个班次内不会出现故障;电铲和卸点都不能同时为两辆及两辆以上卡车服务;卡车每次都是满载;空载与重载的速度相同,总运量只考虑重载运量;道路不会发生堵车的现象;不考虑天气对车辆行使的影响;矿石运往矿石漏和铁路倒装场,岩石运往岩石漏和岩场; -一个班次内卸点不移动;每个铲位至多能安置一台电铲; 生产规模为电铲和卡车数量小于或等于现有数量。约定:Z为总运量的上限，Nb为现有电铲数量，Nr为现有卡车数量, q为卡车的载重量(单位为吨), m .为铲位的个数，n为卸点的个数, T为-一个班次的时间(单位为分钟), v为卡车的平均速度(单位为公里/分钟), t、t,分别为电铲的平均装车时间和卡车的平均卸货时间(单位为分钟)，B, 和B2分别为品位限制的上、下限值，n为卸岩石的点的个数。对任意的i=1,2,..,m， j=1,2,",n，Q为铲位i与卸点j的路线上卡车运输的车次，Ly为铲位i与卸点j之间的距离(单位为公里)，Yq;、 Tq,分别为铲位i的岩石数量和矿石数量(单位为吨), r; 为铲位i的矿石的平均铁含量，Cq ;为卸点j的产量下限(单位为吨)。1.1模型(1)针对原则一:以总运量最小和出动的车辆最少为目标,其它的限制为约束,建立双目标规划模型。根据实际问题分析易得如下目标:中国煤化工min q.22q.. n+ ssMYHCNMHG(1)收稿日期: 2005-03-09基金项目:四川省教育厅自然科学基金(2004C018)作者简介:兰恒友(1969-).男，四川资中人，副教授，主要从事运筹与优化研究。第18卷第2期兰恒友:车辆的优化调度9若视(1)中两目标函数具有相同的优先级,则(1)可化为下列具有相同优先因子(记为p )的目标规划形式":min p(w.d* +wz.df)(2)其中w、W2 为相应目标偏差的权系数, dt (k =1,2)为正偏差变量。而原目标函数转化为目标约柬其中d (k =1,2)为负偏差变量。综合(2) (3)和卡车不等待等约束条件，可建立如下模型():min p(m.dt +w2.d5)st.q. 2Ze,Ly+d;-d'=z问j=l上之iC:+).2+d:-d;=Nvv问问12q,≤T，i2.,..m， r:ZQ,sr， 1-=.,... .(4)简q.之e,;2Cq， j=,.,n(5)ieqZQ,≤Yq，qq之2, s7qg， i-12.-.m(6)j=n+l之e,B.≤年-SBz， j=n +1,n +2,-,n(7)Ze,Nb≤m(8)、dj≥0, k=1,2,整数Qq20，i=1,-,m，j=,-,n(9)中(4)为卡车不等待约束(即装车或卸货所用的总时间不超过一-个班次的时间), (5)为对各卸点产量的要求，(6)为各铲位矿石和岩石数量约束，(7)为品位限制(在一个班次内矿石从各铲位运输到矿石卸点的矿石铁含量), (8)为铲位与铲车的关系(若铲位有岩石或矿石产量.则意味着该铲位用了一台铲车), (9)为非负约束。中国煤化工MHCNMHG1.2模型(u)针对原则二:利用现有车辆运输，获得最大的产量(岩石产量优先;在产量相同的情况下，取总运量最小的解),建立多目标规划模型。其目标是:第- -优先级目标是岩石的产量,第二优先级目标是96四川理工学院学报(自然科学版)2005年6月矿石的产量，第三优先级目标是总的运量最小。如果p、pz和p3分别为第-级、第二级和第三级目标的优先权因子，df 和d[ (k =1,2,..,n+1)分别为正、负偏差变量，0, (j =1,2..,n)为相同优先因子下各个目标的权系数，则与模型([)类似，我们可建立模型(I)min2w,d;" +P2 So,d; +psd*s.qS(Q,+d;-d)=Cq，1-2.,.(10) .q.Z2ey .Ly +dm+1-d$u=Z(11(12)之立已业+5)0,sNr旨局1Zasr，92o,srq. q _0,sTq.12...j=lj=n+1之e,r;≤7， j=,2,,n， B.≤且≤B2， j=n +1,n +2,.*,n二2,Nb≤md、d 20, k=1,2,..,n+1,整数Qj20，i=1,2...,m， j=.,2,..,n其中(10)和(11)分别为产量最大和总运量最小的要求", ( 12 )为投入运输的车辆与总的车辆数的关系。2模型的求解2.1模型()的求解根据遗传算法(GA)原理2),模型([I)的遗传算法步骤可表述如下:Step0变量编码(染色体), 针对本模型将决策变量Q用mxnx 7位二进制字符串表达(一条线路上的车次用7位二进制编码可以实现);Step 1确定计算群体， 在0~ 100之间随机产生初始群体的个数;Step2确定适度函数max f=-q.之立o,以maxg=-中国煤化工2，YHCNMH GStep3交叉: 判断约束条件，得可行交叉群体,计算各目标有关值;Step4变异: 判断约束条件,得可行变异群体，计算各目标有关值;Step5评估: 将初始种群，交叉种群，变异种群合并后按字典序排序;j伊数据选择:从中选择m xn个最好的染色体;第18卷第2期兰恒友:车辆的优化调度9Step7检查终止条件,若满足则停止，否则，转Step3。2.2模型(I)的求解利用偏差变量的等价表示B一4)和极大熵方法",求解逼近(等价)模型,从而得到模型(I)的近似解。记模型(I)中的第I(1 = 1,2,3)优先层的目标函数为g(x)=1/ Pry)n(exp(Pyw,(Cq, -q.. 2e,m)同g2(x)= Za/ Pz)n(exp(Pz,W/(Cq, -q.2.))j=m+11=g3(x)= (1/ P3,n+)n(exp( P3,n+(Z -q.i= j=l2 (y这里x为m个铲位与n个卸点的路线上:卡车运输的车次向量。具体的计算步骤为:Step 0给定充分大的p;>0 (i=1,2,3;j=1,.,",n+1), -般取10' ~ 10°。将模型转化为等价模型，置X=Xo，k:=1;Step 1求解max g,(x)得最优解xk，并计算8,(x*)(l=1,2,3)。若k= s,则停止，输出最优解x' =x*;否则，给出第l优先层的宽容量σ,≥0。若x*唯一,则要求σ,>0;Step2置X={x∈Xkl8l(x)≤ g1(x' )+σ,l=1,2,3}, k:=k+1. 返回Step1。3实例分析取q=154吨，v= 28公里/小时，t =5分钟, 12=3分钟, m=10, n=5, n=2, T = 480分钟，B,= 0.285，B2 = 0.305，各卸点的任务需求为(1.2,1.3,1.3,1.9,1.3)x 10000吨,其余情况见表1和表2。表1各铲位和各卸点之间的距离Ly铲位1铲位2铲位3铲位4__ 铲位5铲位6铲位7铲位8铲位9铲位10.矿石漏5.265.194.214.002.952.742.460.641.27倒装场11.900.99.1.132251.482.04 .3.512.045.895.614.563.651.06.57岩石漏1.761.832.603.725.056.10倒装场I4.423.863.162.252.810.781.620.50表2各铲位矿石数最Tq.、岩石数tYq, (万吨)和矿石的平均铁含r _产位1 铲位2铲位3铲位4 铲位5. 铲位6铲位7 铲位8 铲位9 .铲位10矿石量1.051.001.101.251.35岩石量1.15铁含量30%28% .29%32%33%31%对模型( I),把“尽量满足品位限制”看成是表3各装点和卸点之间的运输关系表“必须满足”，不考虑铲车利用率，取种群个体数目起止装、鯽点运输运量分配卡车为10,最大代数为100,交叉概率、变异概率和选次数____ (吨公里)择概率分别为0.6、0.05和0.08,利用前面所给出铲位1到岩石漏879832铲位2到矿石漏10390的遗传算法和MATLAB软件编程，可得到如下结铲位2到倒装场I62510322果:共需13辆卡车, 7台铲车分别派到铲位1、2、中国煤化工2143.4、8.9和10,总产量为70070吨(其中岩石32032二483吨，矿石38038吨),总运量为8.4728万吨公里(详YHCN MH G3800铲位9到岩场711427见表3)。铲位10到岩场1:1317对模型( I),根据前面的最大熵算法给出等价铲位10到矿石漏12151铲位10到倒装场I5390模型，运用MATLAB软件编写程序，并考虑电铲总计_45484728)8四川理工学院学报(自然科学版)2005年6月数量的限制，取X。的每个分量均为1, s= 100,可得计算结果:需出动电铲7台,分别派往铲位1.2、3、4、8、9和10,岩石产量为48972吨，矿石产量为54054吨,具体运量和车次见表4。表4卡车的运输路线及车次表运输车运量分配卡车运输起止装、卸点起止装、餌点也(吨公里)(辆)车次铲位1到岩石湖727096铲位4到岩场1404铲位I到矿石漏810铲位4到矿石漏616铲位I到倒装场I2铲位4到倒装场I611485铲位1到倒装场π680487铲位2到岩石漏287589铲位8到岩场4925铲位2到岩场864铲位8到矿石漏3811199铲位2到矿石湖799铲位8到倒装场I314铲位2到倒装场I991010977铲位2到倒装场n593铲位9到岩场8814铲位3到岩石漏3:6259铲位9到矿石谝33843铲位3到岩场铲位9到倒装场I476铲位3到矿石满5187391铲位3到倒装场I10534铲位10到岩场509110884铲位10到矿石漏587铲位4到岩石谳7609铲位10到倒装场I2695317582363224露天矿生产的车辆安排问题是~个优化问题，如果将卸点的移动以及品位限制作为目标约束,那么上述结果将会更加符合实际。此外，如果-个铲位可对应多台铲车，需要考虑车辆可实行实时调度等问题，那么上述问题会更有意义和研究价值。参考文献:([1] 胡运权.运筹学教程[M].北京:清华大学出版社，1999.[2] 苑清敏.遗传算法在多目标运输问题的应用[]天津理工学院学报, 2003, 19(3): 57-60.[3] 陆磊.非线性目标规划的一类有效方法[小]. 系统工程学报，1999, 17(4): 14.14} 施保昌，胡新生.极大熵方法与非单调曲线搜索可行方向法[I] 计算数学，1997, 19(3); 241-256.Optimal Scheduling Problem for VehicleLAN Heng-you(Department of Mathematics, Sichuan University of Science & Engineering, Zigong 643000, China)Abstract: In order to consider the use of truck, forklift, discharging place, shovel bit and so on, somemultiobjective programming models for produce of strip mine and a plan of vehicle is obtained, and geneticalgorithm and maximal entropy algorithm are given.Key words: multiobjective programming model; vehicle scheduling; produce of strip mine; geneticalgorithm; maximal entropy algorithm中国煤化工MYHCNMHG