第18卷第2期四川理工學(xué)院學(xué)報(bào)(自然科學(xué)版)Vol.18No. 2JOURNAL OF SICHUAN UNIVERSITY OF2005年6月SCIENCE & ENGNNEERING( NATURAL SCIENCE EDITION )Jun.: 2005文章編號(hào): 1673- -1549 ( 2005) 02- 0094 -05車(chē)輛的優(yōu)化調(diào)度蘭恒友(四川理工學(xué)院數(shù)學(xué)系，四川自貢643000)摘要:建立露天礦生產(chǎn)及車(chē)輛安排問(wèn)題的多目標(biāo)規(guī)劃模型，綜合考慮卡車(chē)、鏟車(chē)、卸點(diǎn)、鏟位等生產(chǎn)設(shè)備的利用，并給出了其相應(yīng)的遺傳算法和最大熵算法。關(guān)鍵詞:多目標(biāo)規(guī)劃模型;車(chē)輛安排;露天礦生產(chǎn);遺傳算法;最大熵算法中圖分類(lèi)號(hào): 0221.3文獻(xiàn)標(biāo)識(shí)碼: A鋼鐵工業(yè)是國(guó)家工業(yè)的基礎(chǔ)之- -， 鐵礦是鋼鐵工業(yè)的主要原料基地。為了提高露天礦生產(chǎn)的大型設(shè)備的利用率，建立一個(gè)班次的最優(yōu)生產(chǎn)計(jì)劃是非常有必要的。該計(jì)劃主要包括:出動(dòng)幾臺(tái)電鏟，分別在哪些鏟位上;出動(dòng)幾輛卡車(chē)，分別在哪些路線(xiàn)上，各運(yùn)多少次。此外，還應(yīng)該考慮總運(yùn)量最小，同時(shí)出動(dòng)最少的卡車(chē)，從而運(yùn)輸成本最小;或者考慮利用現(xiàn)有車(chē)輛，獲得最大的產(chǎn)量(巖石產(chǎn)量?jī)?yōu)先;在產(chǎn)量相同的情況下，取總運(yùn)量最小的解)。本文就上述兩條原則分別建立露天礦生產(chǎn)及車(chē)輛安排問(wèn)題的多目標(biāo)規(guī)劃模型,綜合考慮卡車(chē)、鏟車(chē)、卸點(diǎn)、鏟位等生產(chǎn)設(shè)備的利用，并給出了求解該問(wèn)題的遺傳算法和最大熵算法。最后以一實(shí)例驗(yàn)證了上述算法的可行性和快速性。1模型的建立全文假設(shè)各種設(shè)備在一一個(gè)班次內(nèi)不會(huì)出現(xiàn)故障;電鏟和卸點(diǎn)都不能同時(shí)為兩輛及兩輛以上卡車(chē)服務(wù);卡車(chē)每次都是滿(mǎn)載;空載與重載的速度相同,總運(yùn)量只考慮重載運(yùn)量;道路不會(huì)發(fā)生堵車(chē)的現(xiàn)象;不考慮天氣對(duì)車(chē)輛行使的影響;礦石運(yùn)往礦石漏和鐵路倒裝場(chǎng),巖石運(yùn)往巖石漏和巖場(chǎng); -一個(gè)班次內(nèi)卸點(diǎn)不移動(dòng);每個(gè)鏟位至多能安置一臺(tái)電鏟; 生產(chǎn)規(guī)模為電鏟和卡車(chē)數(shù)量小于或等于現(xiàn)有數(shù)量。約定:Z為總運(yùn)量的上限，Nb為現(xiàn)有電鏟數(shù)量，Nr為現(xiàn)有卡車(chē)數(shù)量, q為卡車(chē)的載重量(單位為噸), m .為鏟位的個(gè)數(shù)，n為卸點(diǎn)的個(gè)數(shù), T為-一個(gè)班次的時(shí)間(單位為分鐘), v為卡車(chē)的平均速度(單位為公里/分鐘), t、t,分別為電鏟的平均裝車(chē)時(shí)間和卡車(chē)的平均卸貨時(shí)間(單位為分鐘)，B, 和B2分別為品位限制的上、下限值，n為卸巖石的點(diǎn)的個(gè)數(shù)。對(duì)任意的i=1,2,..,m， j=1,2,",n，Q為鏟位i與卸點(diǎn)j的路線(xiàn)上卡車(chē)運(yùn)輸?shù)能?chē)次，Ly為鏟位i與卸點(diǎn)j之間的距離(單位為公里)，Yq;、 Tq,分別為鏟位i的巖石數(shù)量和礦石數(shù)量(單位為噸), r; 為鏟位i的礦石的平均鐵含量，Cq ;為卸點(diǎn)j的產(chǎn)量下限(單位為噸)。1.1模型(1)針對(duì)原則一:以總運(yùn)量最小和出動(dòng)的車(chē)輛最少為目標(biāo),其它的限制為約束,建立雙目標(biāo)規(guī)劃模型。根據(jù)實(shí)際問(wèn)題分析易得如下目標(biāo):中國(guó)煤化工min q.22q.. n+ ssMYHCNMHG(1)收稿日期: 2005-03-09基金項(xiàng)目:四川省教育廳自然科學(xué)基金(2004C018)作者簡(jiǎn)介:蘭恒友(1969-).男，四川資中人，副教授，主要從事運(yùn)籌與優(yōu)化研究。第18卷第2期蘭恒友:車(chē)輛的優(yōu)化調(diào)度9若視(1)中兩目標(biāo)函數(shù)具有相同的優(yōu)先級(jí),則(1)可化為下列具有相同優(yōu)先因子(記為p )的目標(biāo)規(guī)劃形式":min p(w.d* +wz.df)(2)其中w、W2 為相應(yīng)目標(biāo)偏差的權(quán)系數(shù), dt (k =1,2)為正偏差變量。而原目標(biāo)函數(shù)轉(zhuǎn)化為目標(biāo)約柬其中d (k =1,2)為負(fù)偏差變量。綜合(2) (3)和卡車(chē)不等待等約束條件，可建立如下模型():min p(m.dt +w2.d5)st.q. 2Ze,Ly+d;-d'=z問(wèn)j=l上之iC:+).2+d:-d;=Nvv問(wèn)問(wèn)12q,≤T，i2.,..m， r:ZQ,sr， 1-=.,... .(4)簡(jiǎn)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)為卡車(chē)不等待約束(即裝車(chē)或卸貨所用的總時(shí)間不超過(guò)一-個(gè)班次的時(shí)間), (5)為對(duì)各卸點(diǎn)產(chǎn)量的要求，(6)為各鏟位礦石和巖石數(shù)量約束，(7)為品位限制(在一個(gè)班次內(nèi)礦石從各鏟位運(yùn)輸?shù)降V石卸點(diǎn)的礦石鐵含量), (8)為鏟位與鏟車(chē)的關(guān)系(若鏟位有巖石或礦石產(chǎn)量.則意味著該鏟位用了一臺(tái)鏟車(chē)), (9)為非負(fù)約束。中國(guó)煤化工MHCNMHG1.2模型(u)針對(duì)原則二:利用現(xiàn)有車(chē)輛運(yùn)輸，獲得最大的產(chǎn)量(巖石產(chǎn)量?jī)?yōu)先;在產(chǎn)量相同的情況下，取總運(yùn)量最小的解),建立多目標(biāo)規(guī)劃模型。其目標(biāo)是:第- -優(yōu)先級(jí)目標(biāo)是巖石的產(chǎn)量,第二優(yōu)先級(jí)目標(biāo)是96四川理工學(xué)院學(xué)報(bào)(自然科學(xué)版)2005年6月礦石的產(chǎn)量，第三優(yōu)先級(jí)目標(biāo)是總的運(yùn)量最小。如果p、pz和p3分別為第-級(jí)、第二級(jí)和第三級(jí)目標(biāo)的優(yōu)先權(quán)因子，df 和d[ (k =1,2,..,n+1)分別為正、負(fù)偏差變量，0, (j =1,2..,n)為相同優(yōu)先因子下各個(gè)目標(biāo)的權(quán)系數(shù)，則與模型([)類(lèi)似，我們可建立模型(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)分別為產(chǎn)量最大和總運(yùn)量最小的要求", ( 12 )為投入運(yùn)輸?shù)能?chē)輛與總的車(chē)輛數(shù)的關(guān)系。2模型的求解2.1模型()的求解根據(jù)遺傳算法(GA)原理2),模型([I)的遺傳算法步驟可表述如下:Step0變量編碼(染色體), 針對(duì)本模型將決策變量Q用mxnx 7位二進(jìn)制字符串表達(dá)(一條線(xiàn)路上的車(chē)次用7位二進(jìn)制編碼可以實(shí)現(xiàn));Step 1確定計(jì)算群體， 在0~ 100之間隨機(jī)產(chǎn)生初始群體的個(gè)數(shù);Step2確定適度函數(shù)max f=-q.之立o,以maxg=-中國(guó)煤化工2，YHCNMH GStep3交叉: 判斷約束條件，得可行交叉群體,計(jì)算各目標(biāo)有關(guān)值;Step4變異: 判斷約束條件,得可行變異群體，計(jì)算各目標(biāo)有關(guān)值;Step5評(píng)估: 將初始種群，交叉種群，變異種群合并后按字典序排序;j伊數(shù)據(jù)選擇:從中選擇m xn個(gè)最好的染色體;第18卷第2期蘭恒友:車(chē)輛的優(yōu)化調(diào)度9Step7檢查終止條件,若滿(mǎn)足則停止，否則，轉(zhuǎn)Step3。2.2模型(I)的求解利用偏差變量的等價(jià)表示B一4)和極大熵方法",求解逼近(等價(jià))模型,從而得到模型(I)的近似解。記模型(I)中的第I(1 = 1,2,3)優(yōu)先層的目標(biāo)函數(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個(gè)鏟位與n個(gè)卸點(diǎn)的路線(xiàn)上:卡車(chē)運(yùn)輸?shù)能?chē)次向量。具體的計(jì)算步驟為:Step 0給定充分大的p;>0 (i=1,2,3;j=1,.,",n+1), -般取10' ~ 10°。將模型轉(zhuǎn)化為等價(jià)模型，置X=Xo，k:=1;Step 1求解max g,(x)得最優(yōu)解xk，并計(jì)算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實(shí)例分析取q=154噸，v= 28公里/小時(shí)，t =5分鐘, 12=3分鐘, m=10, n=5, n=2, T = 480分鐘，B,= 0.285，B2 = 0.305，各卸點(diǎn)的任務(wù)需求為(1.2,1.3,1.3,1.9,1.3)x 10000噸,其余情況見(jiàn)表1和表2。表1各鏟位和各卸點(diǎn)之間的距離Ly鏟位1鏟位2鏟位3鏟位4__ 鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10.礦石漏5.265.194.214.002.952.742.460.641.27倒裝場(chǎng)11.900.99.1.132251.482.04 .3.512.045.895.614.563.651.06.57巖石漏1.761.832.603.725.056.10倒裝場(chǎng)I4.423.863.162.252.810.781.620.50表2各鏟位礦石數(shù)最Tq.、巖石數(shù)tYq, (萬(wàn)噸)和礦石的平均鐵含r _產(chǎn)位1 鏟位2鏟位3鏟位4 鏟位5. 鏟位6鏟位7 鏟位8 鏟位9 .鏟位10礦石量1.051.001.101.251.35巖石量1.15鐵含量30%28% .29%32%33%31%對(duì)模型( I),把“盡量滿(mǎn)足品位限制”看成是表3各裝點(diǎn)和卸點(diǎn)之間的運(yùn)輸關(guān)系表“必須滿(mǎn)足”，不考慮鏟車(chē)?yán)寐?，取種群個(gè)體數(shù)目起止裝、鯽點(diǎn)運(yùn)輸運(yùn)量分配卡車(chē)為10,最大代數(shù)為100,交叉概率、變異概率和選次數(shù)____ (噸公里)擇概率分別為0.6、0.05和0.08,利用前面所給出鏟位1到巖石漏879832鏟位2到礦石漏10390的遺傳算法和MATLAB軟件編程，可得到如下結(jié)鏟位2到倒裝場(chǎng)I62510322果:共需13輛卡車(chē), 7臺(tái)鏟車(chē)分別派到鏟位1、2、中國(guó)煤化工2143.4、8.9和10,總產(chǎn)量為70070噸(其中巖石32032二483噸，礦石38038噸),總運(yùn)量為8.4728萬(wàn)噸公里(詳YHCN MH G3800鏟位9到巖場(chǎng)711427見(jiàn)表3)。鏟位10到巖場(chǎng)1:1317對(duì)模型( I),根據(jù)前面的最大熵算法給出等價(jià)鏟位10到礦石漏12151鏟位10到倒裝場(chǎng)I5390模型，運(yùn)用MATLAB軟件編寫(xiě)程序，并考慮電鏟總計(jì)_45484728)8四川理工學(xué)院學(xué)報(bào)(自然科學(xué)版)2005年6月數(shù)量的限制，取X。的每個(gè)分量均為1, s= 100,可得計(jì)算結(jié)果:需出動(dòng)電鏟7臺(tái),分別派往鏟位1.2、3、4、8、9和10,巖石產(chǎn)量為48972噸，礦石產(chǎn)量為54054噸,具體運(yùn)量和車(chē)次見(jiàn)表4。表4卡車(chē)的運(yùn)輸路線(xiàn)及車(chē)次表運(yùn)輸車(chē)運(yùn)量分配卡車(chē)運(yùn)輸起止裝、卸點(diǎn)起止裝、餌點(diǎn)也(噸公里)(輛)車(chē)次鏟位1到巖石湖727096鏟位4到巖場(chǎng)1404鏟位I到礦石漏810鏟位4到礦石漏616鏟位I到倒裝場(chǎng)I2鏟位4到倒裝場(chǎng)I611485鏟位1到倒裝場(chǎng)π680487鏟位2到巖石漏287589鏟位8到巖場(chǎng)4925鏟位2到巖場(chǎng)864鏟位8到礦石漏3811199鏟位2到礦石湖799鏟位8到倒裝場(chǎng)I314鏟位2到倒裝場(chǎng)I991010977鏟位2到倒裝場(chǎng)n593鏟位9到巖場(chǎng)8814鏟位3到巖石漏3:6259鏟位9到礦石諞33843鏟位3到巖場(chǎng)鏟位9到倒裝場(chǎng)I476鏟位3到礦石滿(mǎn)5187391鏟位3到倒裝場(chǎng)I10534鏟位10到巖場(chǎng)509110884鏟位10到礦石漏587鏟位4到巖石讞7609鏟位10到倒裝場(chǎng)I2695317582363224露天礦生產(chǎn)的車(chē)輛安排問(wèn)題是~個(gè)優(yōu)化問(wèn)題，如果將卸點(diǎn)的移動(dòng)以及品位限制作為目標(biāo)約束,那么上述結(jié)果將會(huì)更加符合實(shí)際。此外，如果-個(gè)鏟位可對(duì)應(yīng)多臺(tái)鏟車(chē)，需要考慮車(chē)輛可實(shí)行實(shí)時(shí)調(diào)度等問(wèn)題，那么上述問(wèn)題會(huì)更有意義和研究?jī)r(jià)值。參考文獻(xiàn):([1] 胡運(yùn)權(quán).運(yùn)籌學(xué)教程[M].北京:清華大學(xué)出版社，1999.[2] 苑清敏.遺傳算法在多目標(biāo)運(yùn)輸問(wèn)題的應(yīng)用[]天津理工學(xué)院學(xué)報(bào), 2003, 19(3): 57-60.[3] 陸磊.非線(xiàn)性目標(biāo)規(guī)劃的一類(lèi)有效方法[小]. 系統(tǒng)工程學(xué)報(bào)，1999, 17(4): 14.14} 施保昌，胡新生.極大熵方法與非單調(diào)曲線(xiàn)搜索可行方向法[I] 計(jì)算數(shù)學(xué)，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中國(guó)煤化工MYHCNMHG