王金亮

（中鐵十一局集團有限公司）

近年來，隨著物流運輸科技的飛速發(fā)展，采礦業(yè)如何通過降低運輸成本提高生產效益成為學者普遍關注的焦點。目前，國內外針對露天礦卡車調度的研究主要集中在運輸費用、運輸臺班生產作業(yè)時間、非生產時間等方面。以運輸環(huán)節(jié)為例，在露天礦生產過程中，運輸費用占整個礦山生產費用的50%以上。因此，有必要對露天礦卡車調度問題進行研究，進一步完善調度系統，減少運輸成本。

露天礦卡車調度問題是一類復雜的優(yōu)化問題，按卡車車型分為單車型調度問題和多車型調度問題。過去的幾十年里，國內外學者對單車型露天礦卡車調度問題進行了大量的研究。而對于多車型調度問題的研究僅僅停留在物流配送領域，涉及露天礦卡車調度的多車型問題很少。王旭［1］、劉波［2］、魏明［3］、SarangKulkarni［4］針對單車型調度問題進行了研究，并給出求解此類問題的量子遺傳算法、混合遺傳算法、離散粒子群算法、兩階段啟發(fā)式算法。為了解決露天礦卡車調度問題，許茂增等［5］在一般模型的基礎上進一步細化了運輸費用的組成，將卡車折舊、卡車輪胎磨損以及司機工資等費用考慮在內，建立了綜合成本最小化的調度模型。此外，霍曉宇等［6］以卡車總運營成本最小為目標建立調度模型，并采用自適應變異粒子群算法對模型進行求解。曹慶奎等［7］以最小化系統總成本為目標，建立了帶時間窗約束的車輛調度模型，并提出求解該問題的模擬植物生長算法?？紤]到卡車運輸量和車輛利用率對運輸效率的影響作用，蹇潔等［8］建立了卡車油耗成本和固定用車成本綜合最小化的調度模型，并根據問題的特點設計了1 種云自適應遺傳算法。Chang Y 等［9］考慮不同的運輸收入及最優(yōu)解的2 個性質和2 個上界，構建了混合整數規(guī)劃模型，并提出了1 種具有2 種改進策略的啟發(fā)式算法，實現了露天礦卡車優(yōu)化調度。S R Patterson 等［10］為最大限度地減少滿足生產要求所需的設備數，以最小化卡車和電鏟的能耗為目標，提出了1 種混合整數線性規(guī)劃（MILP）調度模型，并開發(fā)了1種構造性算法和禁忌搜索方案，實現了露天礦卡車的節(jié)能調度。上述學者都是研究單車型露天礦卡車調度問題，而實際礦山生產中，運輸卡車車型并非只有1種。因此，本項目在上述研究的基礎上提出了露天礦多車型卡車調度模型。此外，雖然目前已有學者對多車型卡車調度問題進行研究，但該類研究大多停留在一般物流配送問題上。葛顯龍［11］在分析不同車型調度問題的基礎上，對具有動態(tài)需求的多車型調度問題進行了研究，并利用云模型對遺傳算法進行了改進，設計了1種云自適應遺傳算法對調度模型進行求解。之后，葛顯龍等［12］考慮車輛運輸的固定成本和油耗成本，以總運輸成本最小化為目標建立了多車型車輛調度模型，最后采用量子遺傳算法對該問題進行解決。國外對該問題的研究大多停留在最短配送路徑研究方面，如Salhi［13］對多車場多車調度問題進行了研究，設計了1種改進的遺傳算法用于求解最佳的運輸路徑。此后，Comaniciu［14］基于模擬退火算法求解了多車場多車型最短配送路徑問題。A Ceder［15］針對多車型車輛調度問題開發(fā)了一種結合偶數車頭和均勻載荷概念構建時間表的方法，并將該問題轉化為具有NP 復雜度級別的成本流網絡問題。Stephan Hassold［16］針對多車型車輛調度問題（MVT-VSP）提出了基于多組帕累托最優(yōu)時間表的最小成本網絡流量模型，結果表明使用帕累托有效時間表作為輸入，可以將調度成本降低15%以上。Subramanian［17］提出自適應記憶規(guī)劃求解多車型車輛調度問題。Artur［18］采用禁忌搜索算法研究了多車型車輛調度問題。

目前物流企業(yè)針對配送問題提出了一些解決多車場多車型調度問題的解決辦法，但基本都是由TSP問題引申出的遍歷問題，這些方法往往由于適應范圍太廣，針對性不強。而露天礦卡車調度問題不同于傳統的TSP問題，該問題屬于兼顧配礦與調度的非遍歷調度問題，故此類辦法在露天礦卡車調度問題中往往無法使用。因此，本研究在現有單車型露天礦卡車調度和多車型物流配送問題研究的基礎上，綜合考慮露天礦運輸卡車載質量以及運輸過程中的空載費用、重載費用等影響因素，以最小化運輸成本為目標建立多車型露天礦卡車調度模型，以實現調度卡車的優(yōu)化配置。

1 露天礦卡車調度模型

1.1 問題描述

考慮多種車型卡車組合運輸的露天礦卡車調度問題可描述為設E={ }F,D為1 個代表裝載點、卸載點和點間距離的道路網絡圖，其中F={1,2,…M;1,2,…N} 為節(jié)點集，D={dij},i,j∈F,i≠j為邊集。1 隊載質量不同的卡車從車庫出發(fā)，行駛到裝載點，滿載礦石至卸載點，卡車往返直至滿足1 個班次內卸載點產量需求?？紤]卡車數量的限制和運輸任務的要求，1 輛卡車可以為多個卸載點服務。鏟點產量和卸載點需求量已知。問題的目標是確定1 套卡車調度方案，滿足產量及品位等要求，且運輸總成本最小。

1.2 模型假設

運輸過程中卡車以恒速行駛，假設如下。

（1）電鏟和卡車在1 個班次內可以不停地工作，不會出現機器故障等突發(fā)事件。

（2）1個班次內卸點、鏟點的位置固定。

（3）卡車路線不固定，當其在1 條路線上完成任務之后可以到其他路線上去幫助其他卡車運輸。

（4）卡車僅從車庫出發(fā)和返回1 次，且不同型號卡車空載、重載單位費用相同。

（5）1個鏟位只安排1臺電鏟，同一時間該鏟位只能有1 輛卡車裝車，前1 輛車開走后才允許后1 輛車裝車，當某個鏟位的礦石量低于卡車載質量時，由載質量小的卡車運輸。

1.3 符號變量說明

露天礦卡車調度模型研究是一類大型復雜問題，其涉及約束眾多，模型建立時需考慮參數較多，為便于模型的建立與理解，現對各參數作以下說明，具體見表1。

1.4 目標函數

在滿足約束條件的情況下，取總運輸費用最小的解?？傔\輸費用包括卡車從車庫O到鏟點i、從卸點j到鏟點i和從卸點j返回車庫O的空運費用以及卡車從鏟點i到卸點j的重運費用。目標函數如下。

1.5 約束條件分析

（1）道路通行能力約束。1 個電鏟不能同時為2輛卡車提供服務，因此，1 條路線上能同時運行的卡車數有限，在卡車不等待的前提下，1 條線路上可同時運行的最大卡車數為Zij=[ ]tij÷p，其中[ ]表示向下取整。

按第1 趟卡車裝車來計算，1 個班次內該線路某型號卡車最大運行次數為

2 遺傳算法設計

遺傳算法是模擬生物在自然界中的遺傳和進化過程而開發(fā)的1 種全局優(yōu)化自適應隨機搜索算法。遺傳算法由于全局搜索能力強、魯棒性好，而且適應于并行處理，所以被廣泛應用于求解車輛調度問題、運輸問題及供應鏈網絡設計問題等。

2.1 染色體的編碼與解碼

用遺傳算法求解多車型露天礦卡車調度問題時，確定染色體的編碼方法是一項非常關鍵的工作，它直接決定算法實現的難易程度和性能的優(yōu)劣。本研究采用對運輸車次數按照x11,x12,…x1n,x21,x22,…,xm1,xm2,…xmn直接進行實數編碼的方式，對于1 個包含M個鏟位，N個卸點，V種車型，每種車型包含S輛卡車的露天礦卡車調度問題，染色體編碼就是M×N個非負整數0 到max的一個隨機排列，其長度為S×V×M×N。每個基因對應一個非負整數，基因值表示運輸次數。這種編碼和解碼方法是隨機產生1個1到V的整數表示調用哪種車型；然后隨機產生1 個1 到S的整數表示調用哪輛車，按照卡車具體分配給哪個鏟位，將該卡車寫入該鏟位對應解的編碼中，重復以上操作，直至所有路線卡車分配完畢，得到1個完整的配送方案。

例如，1 個調度中心有3 種卡車車型（編號為Ⅰ、Ⅱ、Ⅲ），每種車型均有2輛相同的卡車（編號為1，2），需要為3 個鏟位、2 個卸點服務。假設根據鏟位最大礦石量和卡車最小載質量算得僅1 輛卡車參與運輸時的最大運輸次數為8，設染色體的編碼為，通 過 如下解碼過程可以得到上述染色體對應的1 個可行解（即配送方案）。

表示路線（1，1）安排Ⅰ型1 號卡車運輸3 次，Ⅰ型2 號卡車運輸0 次，Ⅱ型1 號卡車運輸1 次，Ⅱ型2號卡車運輸2 次，Ⅲ型1 號卡車運輸0 次，Ⅲ型2 號卡車運輸2次；重復以上步驟直到安排完所有路線的配送計劃，可得到1個完整的調度方案。各鏟位服務卡車均從車庫出發(fā)，最后回到原車庫。容易看出這種編碼和解碼方式在交叉、變異過程中極易跳出可行解的范圍（例如交叉后車次數遠大于8）。因此在第1次編碼的基礎上進行二次編碼，這里可以采用四位二進制編碼。例如路線（1，1）的運輸方案為301202，其二進制編碼為。

2.2 初始種群的確定

隨機產生1 個由N個染色體組成的初始種群，對其進行解碼操作可得到每個個體對應的車輛調度方案。

2.3 適應度函數

本研究選取目標函數作為適應度函數去評價車輛調度問題中可行解的優(yōu)劣。

2.4 精英選擇

從每一代種群中選擇一定數量的適應度最好的個體直接進入下一代，并參與下一代種群適應度的比較及交叉和變異操作。精英選擇不僅可以保證優(yōu)秀個體不會在進化過程中丟失，加速算法收斂，而且可以保證下一代種群中的最優(yōu)個體不會比上一代差，使得進化曲線保持單調下降趨勢。

2.5 交叉操作

設交叉概率為Pc，首先在上一代種群中隨機選取2 個個體作為父代，然后生成1 個介于（0，1）的隨機數P，如果P＞Pc，則2 個父代不進行交叉，因而不產生新個體，如果P＜Pc，則隨機確定1個交叉點再進行交叉操作。

設父代染色體A1的1個基因組為，B1的1個基因組為，則按照如下步驟進行交叉操作。

Step 1：隨機產生1 到3 之間的1 個隨機整數組，長度為6，表示基因的交叉點，如122321。

Step 2：將染色體B1中的6 組基因分別從第2、3、3、4、3、2 個基因開始的所有基因依次加到A1染色體的前面，同時將染色體A1中從第2、3、3、4、3、2個基因開始的所有基因依次加到染色體B1的前面，得到A1=，B1=。

Step 3：A1、B1中每組只保留前4 位自然數，得到新的染色體A1′，A2′=。

與傳統方法相比，這種交叉操作能夠避免交叉后由于基因長度的增加而產生的跳出解空間的現象。

2.6 變異操作

本研究采用的變異方法為多點變異，設種群的變異概率為PM，首先生成1 個介于（0，1）之間的隨機數P1，如果P1＞PM則染色體不發(fā)生變異，因而不產生新個體；如果P1≤PM，則染色體發(fā)生變異。這里采用六點反轉變異，首先隨機產生整數1 到4 的1 個長度為6 的隨機排列，序列數代表基因位數，將排列中整數對應的染色體基因做0-1互換即可。

如父代染色體為A1′=，則按如下規(guī)則進行變異操作：首先給出整數1～4 的1 個隨機排列，如232141，然后將染色體各組基因的第2、3、2、1、4 及第1 個基因做0-1 互換，則得到1 個新的染色體A1"=。

2.7 生成新種群

在遺傳算法中，新個體來源于精英選擇、交叉和變異3 種操作，假設通過上述3 種途徑得到的種群大小為N′，如果N′＞N，則按照適應度由小到大的順序選取前N個個體組成新種群，如果N′＜N，則再隨機生成(N-N′)個個體加入新種群，保持新種群與上一代種群大小相同，既可以避免因為種群規(guī)模越來越大而增加交叉和變異的難度，也可以防止因為種群規(guī)模越來越小而使算法趨于早熟［16］。

3 模型應用

3.1 基本數據

以國內某露天礦生產調度為例對所建模型進行求解。采場內共有5 個裝載點，3 個卸載點，各鏟位均分布1臺電鏟，車庫有3種車型，每個車型有2輛卡車，不同車型車輛的載貨量如表2所示。各個鏟點和卸點位置如圖1 所示，在1 h 內，卸載點的產量要求：礦石漏1 600 t，倒裝場Ⅰ為1 850 t，倒裝場Ⅱ為1 513 t。根據統計數據，得知電鏟的平均裝車時間約為5.5 min，卡車的平均卸載時間約為3.5 min。鏟點到卸點及車庫到鏟點、卸點的距離如表3 所示，假設礦石品位要求為29.5%±1%，各鏟位礦石儲量以及礦石的平均鐵含量如表4 所示。所用卡車平均時速32 km/h，3 種車型卡車的空車單位運輸成本均為10 元，重車單位運輸成本分別為15、20、30元。在1 h內，主要生產計劃目標是利用現有卡車，根據生產計劃要求和卡車數量，規(guī)劃出1 h 內所要出動卡車的臺數、型號、每條路線卡車運行次數，并安排其運輸路線，即生產調度方案。

3.2 結果分析

設種群規(guī)模為150，交叉率為0.9，變異率為0.05，最大迭代次數為500，ε=0.01。采用MATLAB 編程實現上述算法，得到最優(yōu)調度方案，如表5所示。Ⅰ型1號卡車分別在路線（1，3）、（2，1）、（3，1）、（3，2）、（4，2）、（4，3）、（5，3）上運輸3 次、2 次、6 次、4 次、3 次、8次、2 次；Ⅰ型2 號卡車分別在路線（1，2）、（2，2）、（3，1）、（3，2）、（4，1）、（5，3）上運輸4 次、5 次、2 次、2 次、6次、5 次；Ⅱ型1 號卡車分別在路線（1，2）、（2，1）、（2，2）、（3，1）、（4，2）、（4，3）上運輸6 次、3 次、3 次、5 次、4次、4 次；Ⅱ型2 號卡車分別在路線（1，2）、（2，2）、（3，2）、（4，1）上運輸5次、7次、5次、6次；Ⅲ型1號卡車分別在路線（1，3）、（2，2）、（3，1）、（3，2）、（4，1）上運輸6次、3次、4次、1次、2次；Ⅲ型2號卡車分別在路線（1，2）、（4，1）、（4，3）、（5，3）上運輸4 次、6 次、5 次、3 次；總運輸成本為1409 元，相比單車型卡車運輸分別節(jié)約11.2%、9.7%、6.2%。最優(yōu)解收斂情況見圖2。

4 結論

（1）針對露天礦卡車調度問題，采用整數規(guī)劃方法，建立了以最小運輸成本為目標的卡車調度模型，實現了卡車運輸費用最小化。該模型考慮了卡車多車型調度問題，與傳統單車型卡車調度模型相比，多車型卡車配合調度減少了因非滿載而造成的資源浪費，節(jié)約運輸費用，同時也更加貼近礦山生產實際。

（2）提出了1種全新的染色體二次編碼和解碼方法，一定程度上減小了染色體編碼的復雜度，對于求解大規(guī)模問題，可有效降低計算時間和對電腦內存的要求。最后，通過仿真計算實現了多車型露天礦卡車調度問題的求解，結果表明，本研究選用的算法及遺傳操作策略對于多車型露天礦卡車調度問題的求解具有良好的適應性。