1、露天礦生產的車輛安排于俊泊，肖 川，楚玉強指導教師：韓鐵民（東北大學，沈陽 110004）編者按：面對問題既要選擇鏟位，又要考慮產量、晶位限制，及車輛不等待等諸多要求，本文將問題分為幾個階段用不同方法處理，達到了滿意的效果文章精煉，論述清晰摘 要：如何利用最小的資源消耗取得理想的產量要求,是本文討論的重點問題文章采用兩種方法貪心法和線性規劃建立模型，針對兩個目標進行安排 第1階段：采用貪心法按距離、產量、晶位等要求依次取得最優、次優等若干較優的鏟位，獲得一些鏟位的組合方案 第2階段：對這些組合進行線性規劃：以車次為變量，根據不同目標建立目標函數，根據產量等條件限制建立約束方程，然后求整數解，在

2、這些解中取最優者 第3階段：根據每條路線上的車次數再次利用貪心法進行具體的車輛安排關鍵詞：貪心法；線性規劃；車次；車輛安排分類號：AMS(2000) 90C05 中圖分類號：02211 文獻標識碼：A1 問題的分析變量說明M：卡車總數（20輛）V：卡車行駛速度（28公里/時）L：卡車載重量（154噸）T：一個班次的總時間（8小時）Ta：電鏟的平均裝車時間（5分鐘）Tb：卡車的平均卸車時間（3分鐘）i：卸點編號（5個，分別為礦石漏、倒裝場I、倒裝場II、巖石漏、巖場，前3個用于卸礦石，后2個卸巖石）j： 鏟位編號（10個）Dij：卸點i與鏟位j之間的距離（公里）Ni：卸點i的產量要求（噸）Qaj

3、：鏟位j的礦石數量（噸）Qbj：鏟位j的巖石數量（噸）Pj： 鏟位j的礦石平均鐵含量Kij：一輛卡車一個班次內在卸點i與鏟位j之間可往返的次數Xij：卸點i與鏟位j之間需要安排的車次數 如果直接從題意出發，安排運輸路線是比較困難的，因為卡車的行駛路線可以改變可以通過求出每條路線的車次數達到解決問題的目的 鏟車的安排方法共有種，計算復雜度較大，可用貪心法找出較優的若干位置，確定較優的安排方案，對這些安排方案，有如下方法： 目標及各個產量要求、品位要求等均為每條路線上車次的一次函數，故可用線性規劃求解 由已知條件可以得到線性規劃的目標函數、約束方程 對貪心法篩選過的鏟車安排方法分別求出其線性規劃的

4、最優解，然后在其中再選出最優者，可得最優的鏟車安排和車次，依據車次安排每輛卡車2 模型的建立過程一 鏟車安排基于分析，首先得到鏟車安排方法共有種，如果直接計算120種組合，耗時太多，通過分析，最優解只可能存在于一些較優的組合中，可以采用貪心法獲得這些組合貪心法的思想是：每次選擇當前最優的點，如不滿足條件，再選擇次優點，以此類推通過分析知，鏟車應先選擇距離卸點最近的鏟位，才能以最小的運量獲得足夠的產量，若此鏟位不能滿足產量要求，再取次近的鏟位，若不能達到品位要求，還需要選擇可以平衡品位的點如本題的實例，先選取距離礦石漏最近的鏟位9，鏟位9可滿足產量，但無法滿足品位要求，再選擇可均衡品位的最近的點

5、鏟位3同理，選擇距離倒裝場I的較近鏟位2，鏟位4，距離倒裝場II較近的鏟位10，平衡品位的鏟位1確定1，2，3，4，9，10六個最優點，再從剩下的四個點中選取一個即可，經過這種方法篩選后的鏟車安排方法為4種 對于篩選后的方法，用線性規劃逐一建立模型求解，下面以將鏟車安排在1，2，3，4，5，6，7鏟位為例（非上文提到的較優組合，僅作舉例說明） 過程二線性規劃求解車次 1針對目標1建立模型 目標函數 總運量約束方程： 1）各個卸點的產量要求： （1）2）各個卸點的品位要求：下限 （2）上限 （3）3）各個鏟位的礦石（巖石）數量，即該鏟位允許的最大礦石（巖石）開采量礦石 （4）巖石 （5） 4）由

6、于鏟車每次裝載需Ta分鐘，故一個班次內最多可裝載60TTa=4805=96次：， （6） 5）同理，由于卸點每次卸載需Tb分鐘，故一個班次內最多可卸載60TTb=4803=160次 ， （7） 6）由于一輛卡車在卸點i與鏟位j之間往返行駛一次需120Dij/V分鐘，裝卸需Ta+Tb分鐘，共需Ta+Tb+120 DijV分鐘，這條線路上一輛卡車一個班次內可往返次（ 表示取整），則該線路需要卡車輛，卡車總數最多不能超過M=20輛： （8）7）， （9）8）（）為非負整數 （10）至此目標函數及約束方程構造完畢由于車次數為整數，此題轉化為對整數規劃的求解 題目中還要求在總運量最小的情況下出動最少的卡

7、車，在解上述線性規劃時，如果有多組解滿足總運量最小，需要取，即卡車總數最少的解在對篩選過的4種安排方法分別進行線性規劃后，取其中總運量最小的解，即為題目所求2針對目標2建立模型目標2與目標1的主要區別是目標函數不同，其約束方程相同，只須改變目標函數即可目標函數產量： 約束方程：（同目標1）如有多組解滿足最大產量，依題目要求取，即巖石產量優先，如果巖石產量相同，依題取，即總運量最小的解過程三車輛安排 選取最優解中每條路線的車次，即可為每輛卡車安排行駛路線及運輸次數由可知共需要多少卡車可再次采用貪心法，使每輛卡車發揮最大工效，先安排固定路線的卡車，然后安排改變路線的卡車以下面一組解為例，具體說明卡

8、車的安排方法：每條路線上的車次見表1表1鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏0130000054011倒裝場I042043000000巖 場000000007015巖石漏810430000000倒裝場II013200000070由求得需要13輛卡車通過，使固定運行的卡車盡可能地往返于卸點和鏟位之間，求出每條路線上固定運行的卡車數，見表2表2Ij路 線卡車數18礦石漏鏟位8122倒裝場I鏟位2124倒裝場I鏟位41310倒裝場II鏟位10141巖石漏鏟位1143巖石漏鏟位3159巖場鏟位91固定運行的卡車共7輛，其它6輛車需要改變工作路線此時每條線上剩余的車次見表

9、3表3Ij路 線車次數12礦石漏鏟位21318礦石漏鏟位825110礦石漏鏟位101122倒裝場I鏟位2324倒裝場I鏟位4632倒裝場II鏟位21333倒裝場II鏟位32310倒裝場II鏟位102341巖石漏鏟位13743巖石漏鏟位3859巖場鏟位932510巖場鏟位1015在改變路線的6輛車中：第一輛：在1-2線路運輸13次，剩余時間分鐘，可以繼續在1-8線路運輸次剩余時間極小，忽略，此時1-8線路剩余車次25-5=20第二輛：在1-8線路運輸20次，剩余時間分鐘，可以繼續在1-10線路運輸次剩余時間極小，忽略，此時1-10線路無剩余車次第三輛第六輛的安排方法同上按上述方法，即貪心法計算剩

10、余時間，即可得到具體的車輛安排，問題得解3、模型的計算目標1：總運量85628噸公里8.6萬噸公里 總產量70378噸7.0萬噸磁矩石產量38192噸3.8萬噸 巖石產量32186噸3.2萬噸出動7臺鏟車，分別安排在1，2，3，4，8，9，10七個鏟位出動13輛卡車，安排如表4：表4編號路 線運輸次數1礦石漏鏟位8 292倒裝場I鏟位2393倒裝場I鏟位4374倒裝場II鏟位10475巖石漏鏟位1446巖石漏鏟位3357巖場鏟位9388礦石漏鏟位213礦石漏鏟位859礦石漏鏟位820礦石漏鏟位101110倒裝場I鏟位23倒裝場I鏟位46倒裝場II鏟位213倒裝場II鏟位32倒裝場II鏟位108

11、11倒裝場II鏟位1015巖石漏鏟位13012巖石漏鏟位17巖石漏鏟位38巖場鏟位92313巖場鏟位99巖場鏟位1015目標2：總產量103488噸10.3萬噸 總運量146791噸公里14.7萬噸公里礦石產量54308噸5.4萬噸 巖石產量49280噸4.9萬噸出動7臺鏟車，分別安排在1，2，3，4，8，9，10七個鏟位出動20輛卡車，安排如表5：表5編號路 線運輸次數1礦石漏鏟位3182礦石漏鏟位3183倒裝場I鏟位2394倒裝場I鏟位4375倒裝場I鏟位3206倒裝場II鏟位8327巖石漏鏟位1448巖場鏟位9389巖場鏟位93810巖場鏟位104511礦石漏鏟位828礦石漏鏟位9212

12、礦石漏鏟位914倒裝場I鏟位12013倒裝場I鏟位14倒裝場I鏟位229倒裝場I鏟位4414倒裝場I鏟位427倒裝場II鏟位3515倒裝場II鏟位33倒裝場II鏟位825倒裝場II鏟位10316倒裝場IO鏟位1024巖石漏鏟位12217巖石漏鏟位16巖石漏鏟位22618巖石漏鏟位22巖石漏鏟位332巖石漏鏟位4119巖石漏鏟位427巖場鏟位8220巖場鏟位89巖場鏟位94巖場鏟位10244 模型的分析 運用貪心法，可迅速求得鏟車的可能位置，確定可能取得最優解的若干組合，大大減少了線性規劃的計算次數確定鏟車位置后，列出線性規劃議程，用Lindo等工具求解，要迅速得到結果對于一些特殊情況，如多數鏟位的優劣程度很接近時，采用貪心法無法準確地確定較優的鏟位，此時需要進行線性規劃的鏟車安排方案數會大大增加，求解的時間會較長在解線性規劃時，需要考慮多解的情況，即多種方案均可取得最優解，此時需要根據題目要求(巖石產量優先、總運量最小、卡車數最少)取得相應的最優解 模型優點： 使用貪心法，迅速確定鏟車的可能位置； 采用線性規劃的思想，化整為零，使模型簡化，大大減少了計算的復雜度； 模型缺點： 對于一些情況，可能存在很多較優點，使用貪心法后不能有效的減少鏟車的安排方式； 解線性規劃過程中存在誤差，導致最后結果會有細小偏