露天礦生產(chǎn)的車輛安排

1、露天礦生產(chǎn)的車輛安排 問題的提出 問題的提出: 現(xiàn)代化鐵礦是露天開采的，它的生產(chǎn)主要有電動鏟車（以下簡稱電鏟）裝車，電動輪自卸卡車（以下簡稱卡車）運輸來完成。提高這些大型設(shè)備的利用率是增加露天礦經(jīng)濟效益的首要任務(wù)。 露天礦場里有若干個爆破生成的石料堆，每堆稱為一個鏟位，每個鏟位已預(yù)先根據(jù)鐵含量將石料分成礦石和巖石。一般來說，平均鐵含量不低于25%的為礦石，否則為巖石。每個鏟位的礦石、巖石數(shù)量，以及礦石的平均含鐵量（稱為品位）都是已知的。每個鏟位至多能安置一臺電鏟，電鏟的平均裝車時間為5分鐘。 問題的提出 卸貨地點（以下簡稱卸點）有卸礦石的礦石漏、2個鐵路倒裝場（以下簡稱倒裝場）和卸巖石的巖石漏

2、、巖場等，每個卸點都有各自的產(chǎn)量要求。從保護(hù)國家資源的角度及礦山的經(jīng)濟效益考慮，應(yīng)該盡量把礦石按礦石卸點需要的鐵含量（假設(shè)要求都是29.5% 1%，稱為品位限制）搭配起來送到卸點，搭配的量在一個班次（8小時）內(nèi)滿足品位限制即可。從長遠(yuǎn)來看，卸點可以移動，但一個班次內(nèi)不變?？ㄜ嚨钠骄盾嚂r間為3分鐘。 所用卡車載重量為154噸，平均時速28?？ㄜ嚨暮挠土亢艽螅總€班次每臺車消耗將近1噸柴油。發(fā)動機點火時需要消耗相當(dāng)多的電瓶能量，故應(yīng)該班次中指在工作時點火一次?？ㄜ囋诘却龝r所消耗的能量也是相當(dāng)可觀的，原則上在安排時不應(yīng)發(fā)生卡車等待的情況。電鏟和卸點都不能同時為兩輛及兩輛以上卡車服務(wù)?？ㄜ嚸看味际菨M

3、載運輸。 問題的提出 每個鏟位到每個卸點的道路都是專用的寬60的雙向車道，不會出現(xiàn)堵車現(xiàn)象，每段道路的里程都是已知的。 一個班次的生產(chǎn)計劃應(yīng)該包括以下內(nèi)容：出動幾臺電鏟，分別在哪些鏟位上；出動幾輛卡車，分別在哪些路線上各運輸了幾次（因為隨機因素影響，裝卸時間與運輸時間都不精確，所以排時計劃無效，只求出各條路線上的卡車數(shù)及安排即可）。一個合格的計劃要在卡車不等待條件下滿足產(chǎn)量和質(zhì)量（品位）要求，而一個好的計劃還應(yīng)該考慮下面兩條原則之一： 1: 總運量（噸公里）最小，同時出動最少的卡車，從而運輸成本最?。?2: 利用現(xiàn)有車輛運輸，獲得最大產(chǎn)量（巖石產(chǎn)量優(yōu)先；在產(chǎn)量相同的情況下，取總運量最小的解）。

4、 問題的提出問題的提出(續(xù)): 我們將就兩條原則分別建立數(shù)學(xué)模型，并給出一個班次生產(chǎn)計劃的快速算法。針對下面的實例，給出具體的生產(chǎn)計劃、相應(yīng)的總運量及巖石和礦石產(chǎn)量。 然后細(xì)化到一個具體的實際問題：某露天礦有鏟位10個，卸點5個，現(xiàn)有鏟車7臺，卡車20輛。各卸點一個班次的產(chǎn)量要求：礦石漏1.2萬噸、倒裝場1.3萬噸、倒裝場1.3萬噸、巖石漏1.9萬噸、巖場1.3萬噸。 問題的提出問題的提出(續(xù)): 鏟點和卸點位置的二維示意圖如下，各鏟點和各卸點之間的距離（公里）如下表: 鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏5.265.194.214.002.952.742.46

5、1.900.641.27倒裝場 I1.900.991.901.131.272.251.482.043.093.51鹽場5.895.615.614.563.513.652.462.461.060.57巖石漏0.641.761.271.832.742.604.213.725.056.10倒裝場 II4.423.863.723.162.252.810.781.621.270.50問題的提出問題的提出(續(xù)): 各鏟位礦石、巖石數(shù)量（萬噸）和礦石的平均鐵含量如下表:鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石量0.951.051.001.051.101.251.051.301.35

6、1.25巖石量1.251.101.351.051.151.351.051.151.351.25鐵含量30%28%29%32%31%33%32%31%33%31%模型的假設(shè) 模型的假設(shè): 1. 卡車在一個班次中不應(yīng)發(fā)生等待或熄火后再啟動的情況; 2. 在鏟位或卸點處由兩條路線以上造成的沖突問題面前,我們認(rèn)為只要平均時間能完成任務(wù),就認(rèn)為不沖突.我們不排時地進(jìn)行討論; 3. 空載與重載的速度v都是28km/h,耗油相差卻很大; 4. 卡車可能提前退出系統(tǒng); 5. 卡車加油,司機吃飯與上廁所等休息時間忽略不計;符號的說明 符號的說明: 1. T(i,j)為 路線的運行周期; 2. d(i,j)為 路

7、線的距離; 3. 為每條路線上可容納的最大車輛數(shù); 4. ME(i,j)為一輛車在相應(yīng)的路線上運輸次數(shù)的上界; 5. 為第n輛車在 路線上運輸?shù)拇螖?shù); 6. 為第n輛車是否被利用的標(biāo)志數(shù) 7. 為第i個鏟點是否有鏟車的標(biāo)志數(shù)ijSDijSD( , )i j( , )nY i jijSDncih問題的分析 問題的分析: 這是一個多目標(biāo)組最優(yōu)化問題。優(yōu)化目標(biāo)有兩個，最小運輸量和最少卡車數(shù)，兩個目標(biāo)在一定程度上是相互影響的，在運輸成本中，總運量是主要決定因素，把總運量作為主要目標(biāo)，將卡車數(shù)轉(zhuǎn)化為約束條件，使卡車總數(shù)不大于20，得到改進(jìn)模型。根據(jù)多目標(biāo)的主要目標(biāo)法的有效解理論，在此最優(yōu)解集上求最少卡車

8、書的有效解或弱有效解。另外，由于電鏟和卸點只能同時為一輛卡車服務(wù)，若此時還存在其他卡車在該鏟點或卸點需要服務(wù)，就等于出現(xiàn)等待情況，在解決時應(yīng)避免該情況發(fā)生。在裝石料時若一條路線中卡車數(shù)超過一定值時，必然會出現(xiàn)等待。 問題的分析 問題的分析(續(xù)): 為了方便討論，我們按礦石漏,倒裝場I，倒裝場II，巖石漏，巖場的順序?qū)⑺鼈円来斡涀餍饵cD1,D2,D5，裝點S1，S2,S10。于是，每條 路線的運行周期為: T（i,j）=3+5+ (min) 其中的d(i,j)為 與 之間的距離（km），v為卡車速度（km/h）.由于每裝一次車的平均時間為5min（大于卸車時間3min），那么每條路線上可容納的最

9、大車輛數(shù)為: =T(i,j)/5. 此外，每輛車一個班次工作480min，則一輛車在相應(yīng)的路線上運輸次數(shù)的上界為ME(i,j)=480/T(i,j)。120( ,)d ijviSiSiSjDjD( , )i j模型的建立及求解 模型準(zhǔn)備: 在模型建立之前，先給出幾個必要的命題（證明過程略）和分析過程。我們用標(biāo)志數(shù) 來刻畫第n輛車是否被利用。當(dāng)?shù)趎輛車被利用時 =1，否則 =0。 命題1: 第n輛車是否被利用的標(biāo)志數(shù): n=1,2,20; 其中 是第n輛車從 到 的運輸次數(shù)，flag為符號函數(shù)。 命題2: 第i個鏟點是否有鏟車的標(biāo)志數(shù): , i=1,2,10; ncnc10511( ,)nnij

10、cflagYij ( , )nY i jnciSjD20511( ,)inijhflagYij 模型的建立及求解問題一的模型: 對于問題1和問題2，都必須滿足： 1.各鏟點向所有卸點提供的巖石和礦石總量應(yīng)分別不大于該鏟點礦石數(shù)量和巖石數(shù)量，即為模型中的（1）式。 2.有所有鏟點向各卸點運輸?shù)氖峡偤蛻?yīng)不小于卸點所需石料的下限，即為模型中的（2）式。 3.品味限制，在三個礦石卸點，礦石的平均鐵含量應(yīng)在給定范圍內(nèi)，即為模型中的（3）式。 4.由于鏟車數(shù)量為7，所以要求利用鏟點不超過7個，即為模型中的（4）式。 5.每個鏟點的工作次數(shù)不大于96次，即為模型中的（5）式。 6.每個卸點的工作次數(shù)不大于

11、160次，即為模型中的（6）式。 模型的建立及求解問題一的模型(續(xù)): 綜上所述，可得問題一的基本模型: 模型: 這里 , n=1,2,20;20105111min154( , ) ( , )nnijfY i j d i j201minnnc10511( , )nnijcflagYi j模型的建立及求解問題一的模型(續(xù)): s.t. i=1,2,10; (1) , j=1,2,5; (2) , j=1,2,3; (3)10311154( , )ninjY i jk20511154( , )ninjY i jy201011154( , )njniY i jMD201011201011( , )2

12、8.5%30.5%( , )nininniY i jY i j模型的建立及求解問題一的模型(續(xù)): , i=1,2,10; (4) , i=1,2,10; (5) , j=1,2,5; (6) , , i=1,2,10, n=1,2,20 (7) , n=1,2,20, i=1,2,10, j=1,2,5 (8)1017iih20511( , )inijhflagY i j20511( , )96nnjY i j201011( , ) 160nniY i j0,1ih (, )0nY i jN 0,1 nc 模型的建立及求解 模型的求解: 模型是雙目標(biāo)規(guī)劃,運輸總量為線性函數(shù)，所需卡車數(shù)是非線

13、性的，并且不連續(xù)，無法用一般的非線性規(guī)劃求解。根據(jù)多目標(biāo)規(guī)劃中的主要目標(biāo)法，將運輸總量設(shè)為主要目標(biāo)，最少卡車數(shù)設(shè)為次要目標(biāo)，將次要目標(biāo)轉(zhuǎn)化為約束條件，從而使得模型簡化為單目標(biāo)規(guī)劃問題。由前面的討論，將最少卡車數(shù)轉(zhuǎn)化為約束條件后，可以求出最優(yōu)解。 模型的建立及求解 模型的求解(續(xù)): 于是，化簡后的改進(jìn)模型為: 模型: s.t. (1) , (2) , (3) , (5) , (6) , (7) , (8)同模型; , , i=1,2,10; (4) , , n=1,2,20; (9) 20105111min154( , )( , )nnijfY i jd i j 1017iih20511( ,

14、 )inijhflagY i j20120nnc10511( , )nnijcflagY i j模型的建立及求解 模型的求解(續(xù)): 由于排時計劃無效，等待問題很難從基本上解決，我們這里深入討論一個班次內(nèi)所有卡車來回于第i個鏟點和第j個卸點次數(shù)的上界M(i,j)，由于每條路線卡車的運行周期是一定的，且相鄰兩車間隔不小于5分鐘，因而在整條路線上的車次也是一定的，加之受到相應(yīng)鏟點巖石和礦石最大產(chǎn)量的限制，可得到: ( , )min ( , )( , ), ( , )/154M i ji jME i jp i j480( ,)( ,)ME i jT i j( ,)ij( , )5T i j,1,2,

15、3( , ),4,5iik jp i jy j模型的建立及求解 模型的求解(續(xù)): 經(jīng)過計算后得到: 于是， , 得到最終求解模型。61 68 64 6871 72 68 84 877061 68 64 68 7081 66 84 87 8061 68 64 6871 81 68 64 708181 71 70 68 72 75 68 74 808181 71 84 68 74 8068 74 7681TM10 5( , )M i j201( , )( , )nnY i jM i j1,2,.,5i 模型的建立及求解 模型的求解(續(xù)): 模型III: s.t. (1),(2),(9)同模型II

16、; , i=1,2,10, j=1,2,5 (10)10520111min154()( , )( , )nijnfY i jd i j 201( , )( , )nnY i jM i j模型的建立及求解 模型的求解(續(xù)): 根據(jù)以上的改進(jìn)模型，為了便于求解，暫時不考慮約束條件（9），將 看成一個變量，一共50個變量。這恰好是個整數(shù)線性規(guī)劃問題，利用Microsoft Office Excel軟件對其進(jìn)行求解，得到最優(yōu)解:最小運量=556.03 154=85628.62噸公里。此時5，6，7三個鏟點沒有運輸量，恰好滿足鏟車和鏟位數(shù)量的約束，主要目標(biāo)已經(jīng)解決。201( , )nnY i j模型的建

17、立及求解 模型的求解(續(xù)): 在此基礎(chǔ)上，分析車輛分配方案，使所用卡車數(shù)量最少。如果 成立，則安排一輛卡車在一個班次內(nèi)就只行駛 路線。但當(dāng) 不是 的整數(shù)倍時，必然還要其他卡車將剩余的石料運輸完，其車次為: 通過調(diào)整卡車在各路線的運輸可使卡車最少。 201( , )( , )nnY i jME i jijSD201( , )nnY i j( , )ME i j201( , )mod( , ),( , )nnZ i jY i j ME i j模型的建立及求解 模型的求解(續(xù)): 這里運用貪心算法，具體算法如下: 1.將剩余車次矩陣 中非零元素對應(yīng)時間周期矩陣 從大到小排序； 2.首先盡可能多運輸

18、中最大元素對應(yīng)的路線，但不能超過班次總工作時間，如有時間剩余，則轉(zhuǎn)移到 次大元素對應(yīng)的路線，選擇其中不超過班次總工作時間的最大路線；運輸以后就在 減去已運輸?shù)拇螖?shù)； 3.依次策略直至一輛卡車的工作時間排滿為止； 4.若 中還存在非零元素就返回1，按上述方法重復(fù)，直至剩余矩陣 中元素都為零,結(jié)束。 10 5Z10 5T10 5T10 5T10 5Z10 5Z10 5Z模型的建立及求解 模型的求解(續(xù)): 表1 問題1一班次的運輸方案: 其中， 表示第3輛卡車在鏟點2與卸點1之間共運輸了13車次，其它類似。 鏟點卸點12348910品位1000030. 50%20000030. 02%300003

19、0. 49%400000500000(4)(7)37 ,44(3)13(1)(8)3 ,39(5)13( 6 )2(6)(9)8 ,35(4)(10)6 ,37(1)(11)25 ,29(12)(2)38 ,32(2)(3)5,6(6)(12)23 ,47(5)15(3)13模型的建立及求解 模型的求解(續(xù)): 經(jīng)過調(diào)整并且考慮到轉(zhuǎn)移時間差，我們得到第一問所需最小車輛數(shù)為13輛，即以下定理: 定理1:在該問題中所利用的最少的車輛數(shù)為13輛。證明:在最優(yōu)解中，我們將運輸周期 和運輸計劃安排車次 相乘并求和得出在此方案下的理想工作時間總和: =6038.976分鐘每輛卡車的有效工作時間都是480分

20、鐘，所需卡車數(shù) =12.5813輛，所以所需卡車數(shù)必然大于12輛。而表1中已給出了13輛車的可行運輸方案，所以命題成立。 10 5T10 5N10511( , )( , )iitotalT i jN i j/480n total模型的建立及求解 轉(zhuǎn)移時間差: 在以上的討論中，我們均沒有考慮當(dāng)一輛卡車從一條路線轉(zhuǎn)移到另一條路線上的時間差。時間差的產(chǎn)生主要是在運輸過程中，這輛車無需再回到原來的鏟點，而是直接到另一條路線上相應(yīng)的鏟點，由于兩條路線的不同，造成了卡車在轉(zhuǎn)移過程中的轉(zhuǎn)移時間差。不妨設(shè)（i，j）為一條從 到 的運輸路線，那么當(dāng)一輛卡車從路1線轉(zhuǎn)移到路線2時，其轉(zhuǎn)移時間差:iSjD12112

21、22111120,:( ,)( ,)( ,)( ,),:2if iit ijijT ijT ijif ii模型的建立及求解 轉(zhuǎn)移時間差(續(xù)): 由于原來的理想時間總和并沒有考慮到轉(zhuǎn)移時間差，從而有: 結(jié)論：根據(jù)最優(yōu)結(jié)果進(jìn)行分配車次，考慮轉(zhuǎn)移時間差，其時間的總量必然比原來的理想時間總和6038.976大。 模型的建立及求解 等待問題的討論: 由于對任何多于兩輛車的討論都可以轉(zhuǎn)化為兩輛車的情況，所以，在此僅討論兩輛車產(chǎn)生等待的情況。根據(jù)卡車出現(xiàn)的位置對等待情況進(jìn)行分類: 1.在鏟點處產(chǎn)生等待。如果兩輛車在同一條路 線上運行，那么它們的運行可以用右圖表示， 只有當(dāng) 時，兩車才會在裝車點發(fā)生等待。 其

22、中AB表示裝貨時間(5min)，CD表示卸貨時間(3min)，S1,S2表示 兩輛卡車，t1,t2分別表示兩輛車開始在A點裝貨的時間。ABDCS1S22112mod(, ),mod(, )5Maxtt Ttt T模型的建立及求解 等待問題的討論(續(xù)): 如果這兩車在不同的路線 上但是在同一鏟點裝貨運 行，如圖二，則只有當(dāng)以 下三式: 聯(lián)立有解的時候，兩車才會產(chǎn)生等待。 D1C1A1B1A2B2D2C2S1S210mod(, )5tt T20mod(, )5tt T12max( ,)480t tt模型的建立及求解 等待問題的討論(續(xù)): 2.卸點處產(chǎn)生等待。類似于1的 討論，可以分為兩種情況:

23、當(dāng)兩輛車在同一條路線上面運行 時，如右圖，那么必須滿足:ABDCS1S22112mod(, ),mod(, )3Maxtt Ttt T模型的建立及求解 等待問題的討論(續(xù)): 當(dāng)兩輛車在不同一條路 線上運行時，如右圖， 只有當(dāng)以下三式: 聯(lián)立有解的時候，兩車才會產(chǎn)生等待。 其中表示時間段 ,T表示一圈所用的時間。 S1S2A1B1D1C1D2C2A2B21111mod(, )3CCttt Tt 2222mod(, ) 3CCttt Tt 12max( ,)480t tt1(2)Ct1(2)1(2)ABC模型的建立及求解問題二的模型: 對于問題2，基于問題1的約束條件，求最大產(chǎn)量且運輸量最小，可得出模型如下: 模型： s.t.(1)(9)同模型 20105111max154( , )nnijpYi j 10520111min154()( , )( , )nijnfY i jd i j 模型的建立及求解問題二的模型(續(xù)): 采用類似于問題1的解法，首先不考慮約束條件（9），按鏟點分布不同，共分為 個整數(shù)線性規(guī)劃子問題，求出其產(chǎn)量的最大的解。然后，將最大產(chǎn)量作