基于改進蟻群算法的露天礦無人駕駛卡車智能調度

張 超，江 松

(1.洛陽欒川鉬業(yè)集團股份有限公司礦山公司，河南欒川471500；2.西安建筑科技大學資源工程學院，陜西西安710055）

礦山智能開采是21世紀礦業(yè)發(fā)展的重要方向和前瞻性目標[1]。實現(xiàn)智能采礦是一個復雜的系統(tǒng)工程，面臨許多科技難題，其中露天礦無人駕駛卡車智能調度問題更是被國內外學者廣泛關注[2]。國內方面，李宏剛等[3]針對礦區(qū)生產、運輸工作環(huán)境惡劣、安全事故頻發(fā)、作業(yè)現(xiàn)場遠離生活區(qū)導致目前面臨人員流動性高、司機老齡化嚴重等現(xiàn)象，提出了一種礦用運輸車輛無人駕駛感知控制方法；趙勇等[4]在建立露天礦卡車調度運輸模型時考慮到車流規(guī)劃目標流率飽和度，較快地實現(xiàn)了車流的轉移；邢軍等[5]給出了目標產量完成度和當前車流飽和度的準則，使卡車實時調度過程及結果更優(yōu)；黃寶祥[6]通過對遺傳算法雜交算子的改進，優(yōu)化了礦山卡車多目標車流分配調度模型。國外方面，加拿大的森科爾能源公司從2019年開始部署超過150輛的露天礦無人卡車；Patterson等[7]考慮到裝載和運輸過程中由于設備閑置而產生的能源消耗問題，以能耗為目標建立了卡車調度運輸模型；Sub等[8]將機器學習方法與大數(shù)據相結合預測露天礦卡車調度運輸時的實時鏈路行程時間，并考慮氣象特征對模型的影響。綜上所述，目前關于露天礦卡車調度問題的研究，大部分是以路徑最短或運費最少為目標建立優(yōu)化模型，對露天礦無人卡車調度中的車流分配與傳統(tǒng)人工卡車車流分配模型的不同之處考慮不足[9]。為合理調配露天礦無人駕駛卡車運輸設備，實現(xiàn)新型露天礦礦山企業(yè)快速發(fā)展，解決無人駕駛卡車運輸車流分配調度的需求，文中以綜合成本最小為目標函數(shù)，構建露天礦無人駕駛卡車最優(yōu)分配調度模型，采用改進的蟻群算法對模型求解，進而實現(xiàn)新型露天礦無人駕駛卡車的車流分配調度。

1 露天礦卡車調度問題

露天礦的開采是在有礦石資源的地表層利用先進技術及先進設備對地表下含有的礦石進行勘探及挖掘，并用卡車將開采的礦石、巖石運送到指定地點再進行一系列操作的過程。露天礦場景及運輸模擬如圖1。卡車的調度運輸是露天礦開采的核心，調度運輸消耗的能耗和產生的成本占整個生產過程的一半以上。因此，合理的調度運輸對礦山的生產效益產生巨大影響。

圖1 露天礦場景及運輸模擬Fig.1 Open pit mine scene and transportation simulation

露天礦卡車調度運輸前，要充分考察礦山的地理環(huán)境，全面考慮卡車、鏟車、破碎站的位置及數(shù)量、每一過程具體如何開展及卡車不能出現(xiàn)扎堆與堵車等現(xiàn)象，當現(xiàn)場出現(xiàn)臨時狀況要能及時處理，提出合理的解決方案，且滿足最初目標。目的是為完成一定任務時，所用的卡車、鏟車等數(shù)量能夠減少，減少無效工作時間，節(jié)省費用支出，提高工作效率。露天礦卡車調度系統(tǒng)包括最佳運輸路線的確定、車流規(guī)劃、實時調度等方面，每個方面對礦石開采過程起重要作用[10]。

1.1 最佳運輸路線的確定

根據露天礦的現(xiàn)場地理環(huán)境，找出挖掘點與破碎站之間的最短路徑，以往求解最佳運輸路線常用的方法主要是以下幾種。

Dijkstra法是以圖論為基礎，將露天礦中電鏟、卡車、道路與道路之間的交叉點等表示成節(jié)點，每條運輸路徑可視為圖上的一條弧線，每條路徑的距離可視為權值，這樣可把露天礦中形成的簡易道路網轉化成帶權的有向圖。假設露天礦運輸網G=(N,E,W)，N 為運輸網絡圖G 中節(jié)點的集合，E 為圖G 中邊的集合，W 為圖G 的權，假設圖G 中包含的各節(jié)點數(shù)為n，對于其他任何一個點p 和q(p,q=1,2,3,…,n,p ≠q)，則最短路徑方程為

式中： dq為道路網中從第1個點到第q 個點距離最短的線路；wpq為道路網中從p 點到q 點的長度。

Floyd法解決小規(guī)模的露天礦最優(yōu)問題時，利用動態(tài)規(guī)劃的特點可快速找到最適合的運輸路徑。將露天礦裝載點、卸載點及其他節(jié)點當作一個加權圖中的各節(jié)點，節(jié)點與節(jié)點之間的連線賦予權值，其權值可用矩陣表示并求出每兩個點之間的距離，即為礦山中各點之間的實際距離。選擇距離最短的值存入矩陣A=[a(i,j)]n×n，按照已知條件將初始矩陣D(0)=A 反復迭代g 次，構造出矩陣D(n)，即為加權圖的距離矩陣。用G′表示給定的加權圖，i 與j 之間的距離用d 表示，即G′(i,j)=d，若在i 與j 之間插入一點k，則G′(i,j)=min[G′(i,j),G′(i,k)+G′(k,j)]。

1.2 車流規(guī)劃

在滿足礦山產量及卡車、鏟車等設備的數(shù)量約束條件下，通常采用線性規(guī)劃等方法對各裝載點和卸載點之間的車流量進行合理分配，使各路徑的車流運輸達到最優(yōu)。

1.3 實時調度

確定最短路徑及車流規(guī)劃后，采用合適的礦山實時調度準則對正在運行的設備和必須完成的作業(yè)給予合理的優(yōu)化調度。若任務未完成，應將參與運輸?shù)目ㄜ嚺傻讲恍璧却虻却囕v較少的鏟位處，利用動態(tài)規(guī)劃原則使即將行使的車輛行駛在車流量適中且運輸距離最優(yōu)的道路，提高作業(yè)效率。

2 露天礦無人駕駛卡車最優(yōu)調度模型

文中針對礦石從出礦口到達處理點的一個調度運輸，考慮礦山運輸?shù)奶攸c及環(huán)保問題，綜合考慮卡車在調度運輸過程中的各項成本，以裝載點的最大產量、卸載點的最大承載量、卡車裝卸時間及品位要求等為約束條件，構建以總成本最小為優(yōu)化目標的露天礦低碳調度模型。礦山中有m 個可裝載卡車的點、n 個破碎站、k 輛車可參與運輸，且每輛裝載車的工作能力和每個破碎站的傾卸能力已知，制定一個可行的方案使能夠參與工作的各機械設備在規(guī)定時間內完成計劃任務，同時可使總費用達到最低。

2.1 運輸成本

運輸成本與運輸距離有直接關系。用Dij表示卡車在裝載點i 到破碎站j 之間的距離，Xrij表示第r 輛車從裝載點i 運輸?shù)V石到破碎站j，Xrji表示第r 輛卡車卸載完礦石后從破碎站返回裝載點，Cr1表示第r 輛卡車單位距離的重車運輸費用，Cr2表示第r 輛卡車單位距離的空車運輸費用，則卡車從裝載點i 到破碎站j 的重車、空車運輸成本費用C1，C2分別為

2.2 維修成本

卡車在運輸過程中隨時會出現(xiàn)故障問題，假設卡車維修費用與卡車運行路徑長短有關，Dr表示第r 輛卡車運行路徑的長度，Cr3表示第r 輛卡車單位距離的維修費用，則卡車運輸過程中的維修費用C3如

2.3 油耗成本

假設卡車行駛路徑不存在坡度，且卡車運輸?shù)挠秃馁M用受車輛載重和行駛距離的影響。當卡車在i，j兩點間運行時，假設卡車滿載時單位距離油耗為yij1，空載時單位距離油耗為yij2，單位燃油成本為y，卡車滿載質量為m1，空載質量為m2，則重車、空車下的油耗成本分別C4，C5為

2.4 碳排放成本

卡車在運輸過程中排放的CO2是由油耗量間接轉化而來的，可通過CO2的單位轉換率δ 計算碳排放成本。CO2單位排放成本為c，卡車在i，j 兩點間單位距離的CO2排放量為δyij1δyij2，則卡車在重車、空車下的碳排放成本C6，C7分別為

2.5 卡車固定成本

無論卡車運輸距離如何變化，載重都不會影響卡車固定成本費用，平均分攤到每輛卡車上即為卡車固定啟用成本，用b 表示，則礦山運輸中卡車固定啟用成本C8為

綜上所述，露天礦無人駕駛卡車最優(yōu)調度模型的目標函數(shù)為

3 蟻群算法的改進

3.1 算法基本原理

蟻群算法是通過自身釋放的信息素來判斷路徑距離，初期螞蟻在經過路徑上的信息素含量較少，需很長時間積累才能增加路徑上信息素的量，因此螞蟻很難在短時間內找到合適路徑，收斂到最優(yōu)值的速度較慢[11]。當螞蟻多次經過這條路徑使信息素增多才能加快算法收斂于最優(yōu)值。遺傳算法開始時搜索范圍較廣，剛開始的種群較豐富，找到最優(yōu)值的速度快，但遺傳算法經過反復迭代，后期種群規(guī)模不再繼續(xù)擴大，導致收斂速度明顯減弱，且沒有蟻群算法正反饋的優(yōu)點，算法很難快速找到最優(yōu)解，產生冗余現(xiàn)象。為解決以上問題，文中提出一種新的混合蟻群算法(ant colony genetic algorithm,ACGA)，用改進的混合算法求解低碳卡車調度問題。

3.1.1 編碼方式與初始種群的產生

編碼方式的選擇會影響算法的優(yōu)劣。文中對露天礦卡車低碳調度模型采用整數(shù)編碼方式記錄每條染色體點的順序，即每輛卡車的運行路線。假設露天礦中有3個卸載點，卡車從0號鏟裝點運送礦石往1，2，3號卸載點；4，5，6，7，8 為路徑交叉點編號，則[0，1，2，3，4，5，6，7，8，9，10]可表示一條染色體的順序，[0，4，5，1，…，…，0，7，6，2，…，…，0，8，3]代表染色體對應的卡車運輸路徑，即有3輛卡車從0號裝載點出發(fā)分別往卸載點1,2,3，隨即產生3條運輸路徑0-4-5-1，0-7-6-2，0-8-3。

3.1.2 計算種群適應度

3.1.3 選擇過程

在基本遺傳算法中交叉率Pc和變異率Pm是固定值，算法在運行過程中沒有發(fā)生大的變化，運行速度依然很慢，且易產生局部最優(yōu)現(xiàn)象。為改變這一缺點，用適應度來計算Pc和Pm，使Pc和Pm成為動態(tài)的。交叉率Pc和變異率Pm的計算公式為：

式中：fmax-favg用來判斷種群的多樣性；f′≥favg用來判斷個體與種群的離散程度；fmax為最大適應度值；favg為平均適應度值；f′為參與交叉兩個個體中的較大適應度值；f 為變異個體的適應度值；Pcmax為最大交叉率；Pcmin為最小交叉率；Pmmax為最大變異率；Pmmin為最小變異率。

通過式(11)和(12)得到Pc和Pm后，需選擇Pc和Pm值較大的個體進行交叉和變異，因此選取一個(0,1)之間的隨機數(shù)u 與Pc和Pm比較，大于u 的個體才能進行下一步。

3.1.4 交叉過程

文中采用算術交叉的方法將尋優(yōu)過程中表現(xiàn)良好的個體保留下來繼續(xù)迭代，算數(shù)交叉公式為：

式中：X(i)，X(i+1)表示不同的個體；X′(i)，X′(i+1)表示交叉后產生的新個體；u 為（0,1）之間產生的隨機數(shù)。

3.1.5 變異過程

基本遺傳算法只對固定的字符變異，文中提出的混合蟻群算法對每次發(fā)生變異時的字符和位置都發(fā)生變化，使之產生多種新個體，種群更龐大，算法迭代尋優(yōu)過程更順利。此變異操作可表示為：利用已知的變異率乘以每個個體的字符長度，得到每個需變異個體的字符數(shù)，如

式中：gene(i)為第i 個個體需要變異的字符個數(shù)；d 為個體字符長度；Pm(i)為個體的變異率。根據需要變異的字符個數(shù)，可從個體的最后一位字符開始隨機變異：Xn=X1+b+rand(a-b)，Xn為變異產生的最終個體，X1為不參與變異的個體，a 和b 分別為所求解中每個字符的最大值和最小值，rand()為(0,1)之間的隨機函數(shù)。完成一輪交叉變異后對得到的所有解進行比較，采用輪盤賭的方式保留與初始種群個數(shù)相同的個體，可留下大部分較優(yōu)解，增加解的多樣性。

3.2 算法基本流程

混合蟻群算法流程圖如圖2。其中遺傳算法主要步驟為如下1)～7)；蟻群算法主要步驟如下8)～12)。

1)設置參數(shù)，種群規(guī)模為N，最初迭代次數(shù)為0，最大迭代次數(shù)gmax；

2)染色體編碼方式為整數(shù)編碼；

3)計算種群適應度，定義種群適應度函數(shù)為綜合成本的倒數(shù)；

4)依據適應度值計算Pc和Pm，選擇Pc和Pm大的個體參與到下一步；

5)采用算數(shù)交叉方法選擇優(yōu)良性高的個體進行交叉操作；

6)采用隨機變異字符數(shù)和位置的方法對新個體進行變異操作，并對新個體與父代個體進行比較，選擇最優(yōu)個體作為最終的子代個體；

7)使用比較策略判斷遺傳算法與蟻群算法的最佳切換時間，并對迭代次數(shù)進行比較，若g ＞gmax，則遺傳算法結束，進入蟻群算法，否則繼續(xù)步驟3)；

8)選用遺傳算法運行結果中排名前20%的個體為蟻群算法中的初始值，并對算法的參數(shù)進行取值，螞蟻個數(shù)為m′，初始迭代數(shù)設置為0，迭代最大次數(shù)設置為gmax；

10)當一只螞蟻完成路徑尋優(yōu)后，將其放入禁忌表中，并對路徑上的信息素進行局部更新；

11)當所有螞蟻完成一次循環(huán)后，尋找到一條合適的運輸路徑，對所有可能經過路徑的信息素進行更新，重復上述過程繼續(xù)循環(huán)找尋最優(yōu)解；

12)當g ＞gmax，循環(huán)結束，輸出最優(yōu)解，否則轉步驟9)。

圖2 混合蟻群算法流程圖Fig.2 Flow chart of hybrid ant colony algorithm

4 實例應用

為解決露天礦卡車低碳調度運輸問題，以河南省某露天礦為例進行求解，該礦采區(qū)有6個裝載點、4 個卸載點、卡車20 輛。車隊在一個班次內需完成4個卸載點的任務，如表1。破碎站處對礦石品位的約束范圍為0.10%～0.13%。

4.1 裝載點與卸載點的距離

礦山中裝載點到卸載點的距離是通過經緯度獲得的，通過GPS監(jiān)測可得到各點之間卡車的運行軌跡，根據卡車在每時間段內運行的軌跡疊加計算裝載點1與卸載點a之間的距離，據此得到其他點之間的距離，結果如表2。

表1 各卸載點任務量Tab.1 Tasks of each unloading point

表2 各點之間的距離，kmTab.2 Distance between points,km

4.2 鏟位量與礦石品位

礦山中每處礦石的品位不同，且每個電鏟的鏟位量也有差異，表3為6處裝載點礦石品位及電鏟每次裝載量。

4.3 現(xiàn)場設備作業(yè)參數(shù)

裝車時間受電鏟工作效率的影響，根據現(xiàn)場經驗可知，裝載點處電鏟的裝車時間為5 min，卸載點處卡車傾卸礦石所需時間為3 min，卡車在運輸過程中始終保持勻速行駛，重車狀態(tài)下卡車運行速度,空車狀態(tài)下卡車運行速度。

4.4 作業(yè)費用

根據露天礦卡車低碳調度優(yōu)化模型，文中實例模型參數(shù)設定為：卡車重載運輸費用為60 元/km,空載運輸費用為50 元/km，維修費用1.5 元/km，卡車空載單位距離油耗量為0.08 L·km-1·t-1，卡車重載單位距離油耗量0.22 L·km-1·t-1，卡車運輸過程中燃油消耗轉化為二氧化碳的單位轉化率2.65 kg/L，單位距離消耗燃油成本7.99 元/L，卡車固定啟用成本20 元/輛，CO2單位排放成本0.25 元/kg，卡車重車狀態(tài)下的質量40 t，卡車空車狀態(tài)下的質量12 t。

4.5 優(yōu)化求解

采用MATLAB軟件依據文中研究的內容對混合蟻群算法編程，對卡車低碳調度過程優(yōu)化求解，得到6個裝載點與4個卸載點形成的各條道路能同時運送礦石的卡車數(shù)目(如表4)，各線路卡車運行次數(shù)如表5。根據各條線路卡車的運行次數(shù)，調度方案中派車時只針對這些線路派車，結果如表6。

表3 各裝載點的鏟位量及品位Tab.3 Shovel position and grade of each loading point

表4 各條路徑上能同時運行的卡車數(shù)，輛Tab.4 The number of trucks running simultaneously on each route

表5 各條路徑卡車運行次數(shù)，次Tab.5 Truck operation times of each route

表6 最佳派車方案線路Tab.6 Route of the best vehicle dispatching scheme

由表6可知調度運輸方案中14條路線的具體數(shù)據，依照此數(shù)據對礦區(qū)內卡車進行實時調度，使卡車按一定方式運輸，卡車可在同一線路運輸，依照先后次序并保證前一輛車與后一輛車間隔運輸，不發(fā)生卡車等待情況。卡車也可完成自己路線的任務后到其他線路運輸，但不能與其他線路的卡車運輸發(fā)生沖突。這些線路卡車每班運行的各項成本如表7(以前5個路線為例)。由表7可知：1-c路線的距離比1-b，1-d的長，但1-c的總成本低于1-b，1-d，而1-d路線的距離小于1-c，但1-d的成本比1-c的高，說明裝載點與卸載點之間運輸距離不是決定運輸成本的唯一因素；距離長的路段在一個班次內的維修成本、油耗成本、碳排放成本不一定比距離短的成本高，卡車運行速度一定時，維修成本、油耗成本、碳排放成本和固定成本除與運輸距離有關外，還與每條路徑的路況、運輸趟數(shù)、使用卡車數(shù)有關。因此距離最短運輸路徑的維修成本、油耗和碳排放成本不一定最低，運輸距離相差較大的卡車固定成本差距并不是最大的，若只從運輸距離最短來衡量卡車運輸過程中的成本，其運輸方案不一定最優(yōu)。

表7 各線路調度成本Tab.7 Dispatching cost of each line

為證明本文建立模型的優(yōu)異之處，分別以卡車運輸距離最短、油耗成本最小、碳排放成本最小和綜合成本最小為目標，利用混合蟻群算法對其中一條路徑5-d進行求解，得到相應目標下的最優(yōu)調度方案的各項成本，對比結果見表8。由表8可知：以距離最短為優(yōu)化目標時并未考慮油耗和碳排放量對成本的影響，導致其油耗和碳排放成本較高，因此總成本不是最優(yōu)；以綜合成本為優(yōu)化目標時考慮的因素較全面，雖卡車運輸距離不是最優(yōu)，但在完成相同任務的前提下使用的卡車數(shù)最少，卡車得到了充分合理利用，減少了卡車的固定啟用成本，同時維修、油耗和碳排放成本均較低，使綜合成本最小。

表8 不同優(yōu)化目標下最優(yōu)調度方案對比Tab.8 Comparison of optimal scheduling schemes under different optimization objectives

4 結 論

建立綜合成本最小的露天礦卡車最優(yōu)調度優(yōu)化模型，包括卡車在重車、空車狀態(tài)下的運輸費用、維修費用、卡車啟用成本、油耗成本和碳排放成本。同時提出采用混合蟻群算法來優(yōu)化總成本最小的露天礦卡車低碳調度問題。實例應用結果表明，卡車在運輸過程中考慮不同因素作為目標函數(shù)得到的優(yōu)化結果不同，以綜合成本最小為優(yōu)化目標消耗的能耗最少，產生的碳排放最少，降低了生產成本的目標。