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

1、露天礦生產(chǎn)車輛運輸安排摘 要對于本文所涉及的問題，首先根據(jù)題意，分析出其不同于常見的運輸問題，按照原題對兩個原則的劃分，分別建立模型，再在此基礎(chǔ)上，將每個原則分為兩步解決：第一步：找到最佳物流結(jié)果；第二步：對各條線路車輛進(jìn)行合理安排。針對原則一，首先將其劃分為兩步，明確其第一步為運輸規(guī)劃問題，建立總運量最小的目標(biāo)函數(shù)，列寫約束條件，求解出卡車運輸次數(shù)（見表2）、總運量以及巖石量和礦石量。第二步為組合優(yōu)化問題，設(shè)計出貪心算法，得到最終對卡車的運輸安排表（見表3）。遵循原則一的情況下需要至少出動13輛卡車，其中7輛固定在線路上運輸，最小總運量是80820.74噸公里。巖石量38192噸，礦石量32

2、186噸。針對原則二，同樣按照問題分析中所述，分為與原則一相同的兩步解決，根據(jù)第一步的模型計算得到遵循原則二的卡車運輸次數(shù)（見表4）以及總運量、巖石量、礦石量等。再通過第二步得到最終遵循原則二的卡車運輸安排表（見表5）。遵循原則二的情況下需要出動20輛卡車，其中14輛固定在線路上運輸，最小總運量是134181.7噸公里，巖石量61292噸，礦石量42504噸。關(guān)鍵字：多目標(biāo)規(guī)劃，組合優(yōu)化，NPC問題，貪心算法，非線性規(guī)劃一. 問題重述鋼鐵工業(yè)是國家工業(yè)的基礎(chǔ)之一，鐵礦是鋼鐵工業(yè)的主要原料基地。許多現(xiàn)代化鐵礦是露天開采的，它的生產(chǎn)主要是由電動鏟車（以下簡稱電鏟）裝車、電動輪自卸卡車（以下簡稱卡車

3、）運輸來完成。提高這些大型設(shè)備的利用率是增加露天礦經(jīng)濟(jì)效益的首要任務(wù)。露天礦里有若干個爆破生成的石料堆，每堆稱為一個鏟位，每個鏟位已預(yù)先根據(jù)鐵含量將石料分成礦石和巖石。一般來說，平均鐵含量不低于25%的為礦石，否則為巖石。每個鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的。卸貨地點（以下簡稱卸點）有卸礦石的礦石漏、2個鐵路倒裝場（以下簡稱倒裝場）和卸巖石的巖石漏、巖場等，每個卸點都有各自的產(chǎn)量要求。從保護(hù)國家資源的角度及礦山的經(jīng)濟(jì)效益考慮，應(yīng)該盡量把礦石按礦石卸點需要的鐵含量（假設(shè)要求都為29.5%1%，稱為品位限制）搭配起來送到卸點，搭配的量在一個班次（8小時）內(nèi)滿足品位限

4、制即可。一個班次的生產(chǎn)計劃應(yīng)該包含以下內(nèi)容：出動幾臺電鏟，分別在哪些鏟位上；出動幾輛卡車，分別在哪些路線上各運輸多少次（因為隨機(jī)因素影響，裝卸時間與運輸時間都不精確，所以排時計劃無效，只求出各條路線上的卡車數(shù)及安排即可）。一個合格的計劃要在卡車不等待條件下滿足產(chǎn)量和質(zhì)量（品位）要求，而一個好的計劃還應(yīng)該考慮下面兩條原則之一： 1. 總運量（噸公里）最小，同時出動最少的卡車，從而運輸成本最??；2. 利用現(xiàn)有車輛運輸，獲得最大的產(chǎn)量（巖石產(chǎn)量優(yōu)先；在產(chǎn)量相同的情況下，取總運量最小的解）。就兩條原則分別建立數(shù)學(xué)模型，并給出一個班次生產(chǎn)計劃的快速算法。針對下面的實例，給出具體的生產(chǎn)計劃、相應(yīng)的總運量及

5、巖石和礦石產(chǎn)量。某露天礦有鏟位10個，卸點5個，現(xiàn)有鏟車7臺，卡車20輛。各卸點一個班次的產(chǎn)量要求：礦石漏1.2萬噸、倒裝場1.3萬噸、倒裝場1.3萬噸、巖石漏1.9萬噸、巖場1.3萬噸。二. 模型假設(shè)1. 假設(shè)鏟位同時開工；2. 每個班次為8小時；3. 每個班次內(nèi)機(jī)器全部能夠正常工作，不出現(xiàn)故障；4. 卡車在點火前的等待不算等待；5. 卡車空載和滿載速度相同，但是耗油量不同；6. 卡車在運輸途中流暢行駛，不出現(xiàn)停車等待等現(xiàn)象；7. 在鏟位或卸點處由兩條路線以上造成的沖突問題面前，我們認(rèn)為只要平均時間能完成任務(wù)，就算作不沖突；8. 卡車不允許從一個卸點到另一個卸點。三. 符號說明符號說明第個鏟

6、位是否安置電鏟第個鏟位到第個卸點的卡車運輸?shù)V石的次數(shù)第個鏟位到第個卸點的卡車運輸巖石的次數(shù)第個卸點的產(chǎn)量要求從第個鏟位到第個卸點的距離第個鏟位的礦石量第個鏟位的巖石量第個鏟位的礦石的平均含鐵量從第個鏟位到第個卸點往返一次的時間（包括裝車時間和卸車時間）第個卸點的總量第個卸點的鐵含量從第個鏟位到第個卸點的路線上最多允許的卡車數(shù)從第個鏟位到第個卸點的一個班次所允許的最大運輸次數(shù)第一類卡車從第個鏟位到第個卸點的數(shù)量四. 問題分析鋼鐵工業(yè)是一個國家工業(yè)的基礎(chǔ)，因而鐵礦開采所涉及的問題自然成為其核心問題。在鐵礦開采過程中，我們考慮使得在盡量多地開采鐵礦石的前提下，也要使得成本相對較少。為使開采礦石多，需

7、要考慮安排比較多的電鏟裝車、比較多的卡車運輸、設(shè)備比較高的利用率以及方便捷徑的運輸路線。為使成本較少，需要考慮減少電鏟和卡車、提高設(shè)備利用率、安排捷徑的運輸線路。綜上所述，我們需要安排合理數(shù)量的電鏟和卡車以及合理捷徑的運輸路線，在原則一和原則二的要求下，分別做出相應(yīng)的合理安排。本題屬于運輸問題，但是它又區(qū)別于典型的運輸問題，其不同點表現(xiàn)在如下幾個方面：1. 本題屬于運輸巖石和礦石兩種原料的運輸問題；2. 屬于產(chǎn)量與銷量不等的不平衡運輸問題；3. 產(chǎn)銷地都有單位流量的限制；4. 為了滿足品位約束，礦石需要搭配運輸；5. 鏟位數(shù)多于電鏟數(shù)，也即是說，需要在所有10個鏟位選擇最優(yōu)的7個作為產(chǎn)地；6.

8、 運輸車輛只有一種，而且必須滿載運輸，如果不能滿載運輸就不運輸；7. 運輸車輛可以往返于多個鏟位和多個卸點之間；8. 本題不僅需要找出最佳運輸方案，還需要對各條運輸線路上的車輛進(jìn)行統(tǒng)籌安排。每一個運輸問題其本質(zhì)屬于規(guī)劃問題。雖然對于找到最佳物流方案并不難，但是本題需要對各條線路上的車輛進(jìn)行統(tǒng)籌安排，而這是一個組合優(yōu)化問題，對于這樣的問題不能使用規(guī)劃問題的方法解決。為了便于表述和計算，我們將原題中鏟位用表示(，卸點用表示(分別表示礦石漏、倒裝場、倒裝場，分別表示巖場、巖石漏。所以我們對本題原則一和原則二都分為兩步規(guī)劃。其中第一步，建立規(guī)劃模型，找到最佳物流結(jié)果；第二步，設(shè)計優(yōu)化算法，對各條線路車

9、輛進(jìn)行合理安排。五. 原則一的模型5.1 模型分析針對按照原則一尋找的最終方案，我們發(fā)現(xiàn)按照問題分析中所述，可以將其分為兩步，首先建立類似于常規(guī)運輸問題的規(guī)劃模型，對于原則一，需要遵循總運量最小并且出動最少的卡車，這看起來似乎是一個多目標(biāo)問題，但是實際上對于需要出動多少卡車這一問題，并不能將其作為目標(biāo)值求解出來，因為只能算出在每條線路上有多少卡車在運輸，但是根據(jù)之前的分析，這些卡車可以在多條線路上運輸。所以最終出動的卡車數(shù)是根據(jù)找到的最小總運量來決定的。那么，這一問題就轉(zhuǎn)化為單目標(biāo)規(guī)劃問題，其目標(biāo)是使得總運量最小。然后再設(shè)計優(yōu)化算法安排合理線路，對于組合優(yōu)化問題，不能使用規(guī)劃問題的方法解決，原

10、題中要求設(shè)計快速算法，而對于按原則一解決的非線性規(guī)劃而言，我們自己設(shè)計了一種相對較為快速的優(yōu)化算法。5.2 模型建立第一步：規(guī)劃模型在知道目標(biāo)最小總運量的情況下，需要列寫如下規(guī)劃問題中相應(yīng)的約束條件：(1 卡車最少總運次：因為各個卸點一個班次的產(chǎn)量是已知的，而卡車每次每車運量是一定的,所以一定存在卡車最少運送次數(shù)，即卡車至少要運送這么多次才能滿足卸點的全部產(chǎn)量，我們稱之為卡車最少運次。其值為： (1其中表示高斯取整。(2 每條線路一輛卡車最多運次：因為每一班次的卡車從鏟位到卸點往返一次需要時間，那么每一班次一輛卡車允許的最大運輸次數(shù)即每條線路一輛卡車最多運次： (2其中。(3 每條線路卡車最大

11、數(shù)量：因為運輸過程中不存在等待現(xiàn)象，所以其最大卡車數(shù)量滿足： (3其中表示高斯取整。(4 電鏟能力約束：因為電鏟每次只能為一輛卡車裝車，若電鏟不停歇地工作，則一個班次最多裝車數(shù)，稱之為電鏟能力約束。其值為： (4(5 電鏟數(shù)量約束：因為電鏟能力約束為96次，于是一個鏟位的最大運輸量為96154=14784噸/車，又由于卡車最少總運次為457次，所以至少需要安置的電鏟個數(shù) (5其中表示高斯取整。又根據(jù)題意最多有7個鏟車。那么綜上電鏟數(shù)量滿足： (6將這一范圍稱之為電鏟數(shù)量約束。(6 卡車數(shù)量約束：根據(jù)式(1(2，顯然知道如下關(guān)系成立： (7所以可以計算其值為： (8其中表示高斯取整，表示中的最小

12、值。又由于題意中已知，卡車最多20輛，所以卡車數(shù)量介于1020之間，稱之為卡車數(shù)量約束。(7 礦石量約束：各卸點總礦石量不能大于所有鏟位總礦石量，即 (9(8 巖石量約束：各卸點總巖石量不能大于所有鏟位總巖石量，也即 (10(9 卸點產(chǎn)量約束：運輸?shù)漠a(chǎn)量不能小于各卸點的產(chǎn)量要求，即卸點用來卸礦石時： (11卸點用來卸巖石時： (12(10 品位限制約束：各個卸點運輸?shù)蔫F含量滿足題目給定的品位限制，也即由于品位滿足 (13根據(jù)原題中已知，有不等式 (14將這一約束條件稱之為品位限制約束。于是，綜上目標(biāo)函數(shù)和所有約束條件，得到規(guī)劃模型如下： (15第二步：組合優(yōu)化模型針對需要安排各條線路的車輛搭配

13、運輸情況，通過分析可以發(fā)現(xiàn)，這是一個組合優(yōu)化問題，也是一個NPC問題，對于問題中要求的快速算法，如果將其作為整數(shù)規(guī)劃解決，勢必其運算復(fù)雜程度是難于讓人接受的。所以我們采用貪心算法這種較為簡便的算法來解決這一組合優(yōu)化模型1。算法分析將求得的和相加得到總的運次矩陣，將該矩陣與相對應(yīng)的一個班次內(nèi)的最大運輸次數(shù)矩陣比較，我們發(fā)現(xiàn)可以將每一條線路上的卡車分為兩類，一類只在該條線路上運輸，另一類也在其它的線路上運輸。我們將其作如下定義：第一類卡車：只在一條線路上運輸?shù)目ㄜ?。第二類卡車：在多條線路上運輸?shù)目ㄜ?。下面對這兩類卡車分別進(jìn)行安排。通過計算 (16根據(jù)其最終的值來判定這條線路上有多少第一類卡車。并由

14、此容易得到第二類卡車需要滿足的運次矩陣 (17為了計算方便，我們將中的元素與對應(yīng)的運輸時間相乘再除以一個班次內(nèi)總的時間，即得到該條線路上需要耗費的時間占一個工作班次的比例。以下是考慮第二類卡車的算法思想：先滿足最耗時的線路的運輸需求，再滿足耗時量次之的線路，當(dāng)一輛卡車的工作時間不能再滿足運輸要求時考慮再派出另一輛卡車，直到所有的運輸要求都被滿足。算法設(shè)計*具體算法如下：Step1：初始化第二種卡車數(shù)量；Step2：找到該矩陣中的最大元素，=該元素值，該元素值=0；Step3：找到次大元素，=次大元素值，Step4：若，轉(zhuǎn)到Step5；若，轉(zhuǎn)到Step3；Step5：重新從Step2開始，直至所

15、有元素都為零；Step6：得到第二種卡車的數(shù)量，同時得到每輛車所走的路線。5.4 模型求解為了便于計算，我們進(jìn)一步分析題意，可以先考慮卸點，找出與每個卸點距離最近的鏟位，再考慮鏟位，找出與每個鏟位距離最近的卸點，結(jié)果見表1：表 1 鏟位與卸點的距離鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏5.265.194.214.002.952.742.461.900.641.27倒裝場1.900.991.901.131.272.251.482.043.093.51倒裝場4.423.863.723.162.252.810.781.621.270.50巖場5.895.615.614.

16、563.513.652.462.461.060.57巖石漏0.641.761.271.832.742.604.213.725.056.10從表1中數(shù)據(jù)可以而發(fā)現(xiàn)，,在行列上都是最小值，則鏟位1，2，9，10是比較優(yōu)越的鏟位，所以首先確定在鏟位1，2，9，10放置電鏟。根據(jù)對上述規(guī)劃模型運用lingo求解得到以下結(jié)果。計算得到最小總運量是80820.74噸公里。巖石量38192噸，礦石量32186噸pspan鏟車放置在鏟位 1 、 2 、 3 、 4 、 8 、 9 、 10 ，卡車運輸次數(shù)結(jié)果如下表：p 表 2 原則一的 卡車運輸次數(shù) 鏟位1鏟位2鏟位3鏟位4鏟位8鏟位9鏟位10礦石漏0130

17、054011倒裝場042043000倒裝場013200070巖場00000580巖石漏800440000第二步結(jié)果于是通過計算可以得到固定在一條線路上的卡車有7輛。運用matlab對組合優(yōu)化模型編程求解可得卡車運輸安排表：表 3 原則一的卡車運輸安排表鏟位1鏟位2鏟位3鏟位4鏟位8鏟位9鏟位10礦石漏8(2 10(5 12(61(29 8(2512(11倒裝場2(39 13(33(37 12(2 13(4倒裝場10(1313(24(47 11(20 13(3巖場13(55(45 9(9 11(26巖石漏6(44 9(367(35 12(9表中括號外的數(shù)字表示車號，括號中的數(shù)字表示運輸次數(shù)。所以

18、對于按照原則一安排，出動13輛卡車，最小總運量是80820.74噸公里，巖石量38192噸，礦石量32186噸。六. 原則二的模型6.1 模型分析每一個運輸問題其本質(zhì)屬于規(guī)劃問題2。對于按照原則二尋找最終方案而言，其實質(zhì)是一個多目標(biāo)規(guī)劃問題。解決多目標(biāo)規(guī)劃問題常常采用配權(quán)值、圖解法、分層規(guī)劃等方法。對于本題由于數(shù)據(jù)量不大，所以難于找到權(quán)值，自然如果本題使用配權(quán)值、圖解等方法，會使得最終結(jié)果誤差比較大，所以我們使用分層規(guī)劃的方法。對于滿足原則二的規(guī)劃模型時，其約束條件與滿足原則一時的一樣，不同的是目標(biāo)函數(shù)。與滿足原則一時一樣，滿足原則二時也是多目標(biāo)規(guī)劃，但不同的是滿足原則一時其實質(zhì)只是一個單目標(biāo)

19、問題，但是滿足原則二時其實質(zhì)是一個主次分明的多目標(biāo)問題。我們同時需要在優(yōu)先考慮巖石產(chǎn)量的情況下兼顧考慮主要目標(biāo)總產(chǎn)量，在產(chǎn)量相同時選取總運量最小的方案。由于運用分層規(guī)劃的方法，所以我們采用層層推進(jìn)的思路：1. 約束條件與按原則一求解的約束條件一樣，只考慮巖石產(chǎn)量，將巖石產(chǎn)量作為唯一目標(biāo)函數(shù)，求最大值,記為max1。2. 之前的約束條件不變，將總產(chǎn)量作為目標(biāo)函數(shù)，并將最大巖石產(chǎn)量max1作為約束條件，求目標(biāo)函數(shù)的最大值，記為max。3. 將max1和max同時做為約束條件，求次要目標(biāo)總運量并使之最小。而在之后的組合優(yōu)化過程同樣可一采用原則一中的貪心算法的思路減小搜索范圍，加快運行速度，得到最優(yōu)運

20、輸方案。6.2 模型建立第一步：多目標(biāo)規(guī)劃按照原則二的要求所建立的規(guī)劃模型，其約束條件與原則一時一樣，只是目標(biāo)函數(shù)發(fā)生了變化，其模型如下（約束條件同原則一時省略）目標(biāo)1：最大巖石產(chǎn)量，其模型為： (18目標(biāo)2：最大總產(chǎn)量，其模型為： (19目標(biāo)3：最小總運量，其模型為： (20第二步：組合優(yōu)化對于原則二的第二步，其思想和具體算法與原則一完全一致，不同點僅僅是此時的一些數(shù)據(jù)發(fā)生了相應(yīng)的變化。所以可以根據(jù)原則一第二步對解決組合優(yōu)化問題的算法建立相應(yīng)的模型。6.3 模型求解通過與原則一類似的方法，計算得到最小總運量是134181.7噸公里。巖石量61292噸，礦石量42504噸。鏟車放置在鏟位1、2

21、、3、4、8、9、10，卡車運輸次數(shù)結(jié)果如下表：表 4 原則二的卡車運輸次數(shù)鏟位1鏟位2鏟位3鏟位4鏟位8鏟位9鏟位10礦石漏0140029035倒裝場2938037000倒裝場0160032046巖場000007681巖石漏81607030000計算可以得到第一類卡車有14輛，得卡車運輸安排表：表 5 原則二的卡車運輸安排表鏟位1鏟位2鏟位3鏟位4鏟位8鏟位9鏟位10礦石漏17(219(121(292(35倒裝場3(2915(116(374(37倒裝場18(165(3215(46巖場6(387(388(4518(819(1120(17巖石漏9(4417(3710(3011(3012(3513(3514(30表中括號外的數(shù)字表示車號，括號中的數(shù)字表示運輸次數(shù)。所以對于按照原則一安排，出動20輛卡車，最小總運量是134181.7噸公里，巖石量61292噸，礦石量42504噸。七. 模型改進(jìn)考慮運輸線路在一定時期內(nèi)是相對固定的，那么可以在本問求解基礎(chǔ)上，對運輸卡車進(jìn)行更加詳細(xì)而固定的安排，作出類似于火車站時刻表之類的卡車運輸時刻表，以使安排的結(jié)果對于完成運輸任務(wù)而言更加高效。本文在安排