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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、有元素都為零；Step6：得到第二種卡車的數(shù)量，同時(shí)得到每輛車所走的路線。5.4 模型求解為了便于計(jì)算，我們進(jìn)一步分析題意，可以先考慮卸點(diǎn)，找出與每個(gè)卸點(diǎn)距離最近的鏟位，再考慮鏟位，找出與每個(gè)鏟位距離最近的卸點(diǎn)，結(jié)果見表1：表 1 鏟位與卸點(diǎn)的距離鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏5.265.194.214.002.952.742.461.900.641.27倒裝場(chǎng)1.900.991.901.131.272.251.482.043.093.51倒裝場(chǎng)4.423.863.723.162.252.810.781.621.270.50巖場(chǎng)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ù)對(duì)上述規(guī)劃模型運(yùn)用lingo求解得到以下結(jié)果。計(jì)算得到最小總運(yùn)量是80820.74噸公里。巖石量38192噸，礦石量32186噸pspan鏟車放置在鏟位 1 、 2 、 3 、 4 、 8 、 9 、 10 ，卡車運(yùn)輸次數(shù)結(jié)果如下表：p 表 2 原則一的 卡車運(yùn)輸次數(shù) 鏟位1鏟位2鏟位3鏟位4鏟位8鏟位9鏟位10礦石漏0130

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

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

19、問題，但是滿足原則二時(shí)其實(shí)質(zhì)是一個(gè)主次分明的多目標(biāo)問題。我們同時(shí)需要在優(yōu)先考慮巖石產(chǎn)量的情況下兼顧考慮主要目標(biāo)總產(chǎn)量，在產(chǎn)量相同時(shí)選取總運(yùn)量最小的方案。由于運(yù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同時(shí)做為約束條件，求次要目標(biāo)總運(yùn)量并使之最小。而在之后的組合優(yōu)化過程同樣可一采用原則一中的貪心算法的思路減小搜索范圍，加快運(yùn)行速度，得到最優(yōu)運(yùn)

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

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