車(chē)輛的優(yōu)化調度

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