第18卷第2期四川理工學院學報(自然科學版)Vol.18No. 2JOURNAL OF SICHUAN UNIVERSITY OF2005年6月SCIENCE & ENGNNEERING( NATURAL SCIENCE EDITION )Jun.: 2005文章編號: 1673- -1549 ( 2005) 02- 0094 -05車輛的優(yōu)化調度蘭恒友(四川理工學院數(shù)學系，四川自貢643000)摘要:建立露天礦生產及車輛安排問題的多目標規(guī)劃模型，綜合考慮卡車、鏟車、卸點、鏟位等生產設備的利用，并給出了其相應的遺傳算法和最大熵算法。關鍵詞:多目標規(guī)劃模型;車輛安排;露天礦生產;遺傳算法;最大熵算法中圖分類號: 0221.3文獻標識碼: A鋼鐵工業(yè)是國家工業(yè)的基礎之- -， 鐵礦是鋼鐵工業(yè)的主要原料基地。為了提高露天礦生產的大型設備的利用率，建立一個班次的最優(yōu)生產計劃是非常有必要的。該計劃主要包括:出動幾臺電鏟，分別在哪些鏟位上;出動幾輛卡車，分別在哪些路線上，各運多少次。此外，還應該考慮總運量最小，同時出動最少的卡車，從而運輸成本最小;或者考慮利用現(xiàn)有車輛，獲得最大的產量(巖石產量優(yōu)先;在產量相同的情況下，取總運量最小的解)。本文就上述兩條原則分別建立露天礦生產及車輛安排問題的多目標規(guī)劃模型,綜合考慮卡車、鏟車、卸點、鏟位等生產設備的利用，并給出了求解該問題的遺傳算法和最大熵算法。最后以一實例驗證了上述算法的可行性和快速性。1模型的建立全文假設各種設備在一一個班次內不會出現(xiàn)故障;電鏟和卸點都不能同時為兩輛及兩輛以上卡車服務;卡車每次都是滿載;空載與重載的速度相同,總運量只考慮重載運量;道路不會發(fā)生堵車的現(xiàn)象;不考慮天氣對車輛行使的影響;礦石運往礦石漏和鐵路倒裝場,巖石運往巖石漏和巖場; -一個班次內卸點不移動;每個鏟位至多能安置一臺電鏟; 生產規(guī)模為電鏟和卡車數(shù)量小于或等于現(xiàn)有數(shù)量。約定:Z為總運量的上限，Nb為現(xiàn)有電鏟數(shù)量，Nr為現(xiàn)有卡車數(shù)量, q為卡車的載重量(單位為噸), m .為鏟位的個數(shù)，n為卸點的個數(shù), T為-一個班次的時間(單位為分鐘), v為卡車的平均速度(單位為公里/分鐘), t、t,分別為電鏟的平均裝車時間和卡車的平均卸貨時間(單位為分鐘)，B, 和B2分別為品位限制的上、下限值，n為卸巖石的點的個數(shù)。對任意的i=1,2,..,m， j=1,2,",n，Q為鏟位i與卸點j的路線上卡車運輸?shù)能嚧?，Ly為鏟位i與卸點j之間的距離(單位為公里)，Yq;、 Tq,分別為鏟位i的巖石數(shù)量和礦石數(shù)量(單位為噸), r; 為鏟位i的礦石的平均鐵含量，Cq ;為卸點j的產量下限(單位為噸)。1.1模型(1)針對原則一:以總運量最小和出動的車輛最少為目標,其它的限制為約束,建立雙目標規(guī)劃模型。根據實際問題分析易得如下目標:中國煤化工min q.22q.. n+ ssMYHCNMHG(1)收稿日期: 2005-03-09基金項目:四川省教育廳自然科學基金(2004C018)作者簡介:蘭恒友(1969-).男，四川資中人，副教授，主要從事運籌與優(yōu)化研究。第18卷第2期蘭恒友:車輛的優(yōu)化調度9若視(1)中兩目標函數(shù)具有相同的優(yōu)先級,則(1)可化為下列具有相同優(yōu)先因子(記為p )的目標規(guī)劃形式":min p(w.d* +wz.df)(2)其中w、W2 為相應目標偏差的權系數(shù), dt (k =1,2)為正偏差變量。而原目標函數(shù)轉化為目標約柬其中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,整數(shù)Qq20，i=1,-,m，j=,-,n(9)中(4)為卡車不等待約束(即裝車或卸貨所用的總時間不超過一-個班次的時間), (5)為對各卸點產量的要求，(6)為各鏟位礦石和巖石數(shù)量約束，(7)為品位限制(在一個班次內礦石從各鏟位運輸?shù)降V石卸點的礦石鐵含量), (8)為鏟位與鏟車的關系(若鏟位有巖石或礦石產量.則意味著該鏟位用了一臺鏟車), (9)為非負約束。中國煤化工MHCNMHG1.2模型(u)針對原則二:利用現(xiàn)有車輛運輸，獲得最大的產量(巖石產量優(yōu)先;在產量相同的情況下，取總運量最小的解),建立多目標規(guī)劃模型。其目標是:第- -優(yōu)先級目標是巖石的產量,第二優(yōu)先級目標是96四川理工學院學報(自然科學版)2005年6月礦石的產量，第三優(yōu)先級目標是總的運量最小。如果p、pz和p3分別為第-級、第二級和第三級目標的優(yōu)先權因子，df 和d[ (k =1,2,..,n+1)分別為正、負偏差變量，0, (j =1,2..,n)為相同優(yōu)先因子下各個目標的權系數(shù)，則與模型([)類似，我們可建立模型(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)之立已業(yè)+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,整數(shù)Qj20，i=1,2...,m， j=.,2,..,n其中(10)和(11)分別為產量最大和總運量最小的要求", ( 12 )為投入運輸?shù)能囕v與總的車輛數(shù)的關系。2模型的求解2.1模型()的求解根據遺傳算法(GA)原理2),模型([I)的遺傳算法步驟可表述如下:Step0變量編碼(染色體), 針對本模型將決策變量Q用mxnx 7位二進制字符串表達(一條線路上的車次用7位二進制編碼可以實現(xiàn));Step 1確定計算群體， 在0~ 100之間隨機產生初始群體的個數(shù);Step2確定適度函數(shù)max f=-q.之立o,以maxg=-中國煤化工2，YHCNMH GStep3交叉: 判斷約束條件，得可行交叉群體,計算各目標有關值;Step4變異: 判斷約束條件,得可行變異群體，計算各目標有關值;Step5評估: 將初始種群，交叉種群，變異種群合并后按字典序排序;j伊數(shù)據選擇:從中選擇m xn個最好的染色體;第18卷第2期蘭恒友:車輛的優(yōu)化調度9Step7檢查終止條件,若滿足則停止，否則，轉Step3。2.2模型(I)的求解利用偏差變量的等價表示B一4)和極大熵方法",求解逼近(等價)模型,從而得到模型(I)的近似解。記模型(I)中的第I(1 = 1,2,3)優(yōu)先層的目標函數(shù)為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個卸點的路線上:卡車運輸?shù)能嚧蜗蛄?。具體的計算步驟為:Step 0給定充分大的p;>0 (i=1,2,3;j=1,.,",n+1), -般取10' ~ 10°。將模型轉化為等價模型，置X=Xo，k:=1;Step 1求解max g,(x)得最優(yōu)解xk，并計算8,(x*)(l=1,2,3)。若k= s,則停止，輸出最優(yōu)解x' =x*;否則，給出第l優(yōu)先層的寬容量σ,≥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各鏟位礦石數(shù)最Tq.、巖石數(shù)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各裝點和卸點之間的運輸關系表“必須滿足”，不考慮鏟車利用率，取種群個體數(shù)目起止裝、鯽點運輸運量分配卡車為10,最大代數(shù)為100,交叉概率、變異概率和選次數(shù)____ (噸公里)擇概率分別為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月數(shù)量的限制，取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露天礦生產的車輛安排問題是~個優(yōu)化問題，如果將卸點的移動以及品位限制作為目標約束,那么上述結果將會更加符合實際。此外，如果-個鏟位可對應多臺鏟車，需要考慮車輛可實行實時調度等問題，那么上述問題會更有意義和研究價值。參考文獻:([1] 胡運權.運籌學教程[M].北京:清華大學出版社，1999.[2] 苑清敏.遺傳算法在多目標運輸問題的應用[]天津理工學院學報, 2003, 19(3): 57-60.[3] 陸磊.非線性目標規(guī)劃的一類有效方法[小]. 系統(tǒng)工程學報，1999, 17(4): 14.14} 施保昌，胡新生.極大熵方法與非單調曲線搜索可行方向法[I] 計算數(shù)學，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