基于GWO?NSGA?Ⅱ混合算法的露天礦低碳運輸調度

文家燕， 聞海潮， 程洋， 羅紹猛， 何偉朝

（1. 廣西科技大學 自動化學院，廣西 柳州 545616；2. 柳州鐵道職業技術學院 通信信號學院，廣西 柳州 545616；3. 廣西柳工機械股份有限公司，廣西 柳州 545007）

0 引言

隨著“雙碳”政策的逐步實施，低碳化將成為露天礦開采的重要方向[1]。運輸是露天礦開采重要環節之一，運輸成本占礦石成本的30%～40%[2]。礦用自卸燃油卡車是我國露天礦主要運輸工具，其運輸途中碳排放量大、效率低，極大地增加了運輸成本。與傳統的燃油卡車相比，純電動卡車可有效降低碳排放量及運輸成本，但受充電限制及卡車運輸排隊影響，露天礦純電動卡車運輸調度仍需深入研究。

露天礦低碳運輸調度問題可視為一個多目標函數最值優化問題。近年來，在自然界生物啟發下，許多學者采用智能群搜索算法來解決露天礦卡車運輸調度問題。蘇楷等[3]以運輸成本最小為目標函數，構建了露天礦運輸調度數學模型，并利用自適應果蠅優化算法進行求解，有效降低了運輸成本。程平等[4]采用非支配鄰域免疫算法求解露天礦新能源卡車多目標優化調度模型，有效降低了電能消耗所引起的碳排放成本。此外，在求解露天礦卡車運輸調度優化模型方面，還有粒子群算法[5]、模擬退火算法[6]、差分進化算法[7]、遺傳算法[8]、蟻群算法[9]等。上述算法在一定程度上解決了露天礦運輸調度問題，但存在全局尋優能力較差、待調節參數較多等問題。

非支配排序遺傳算法（Non-dominated Sorting Genetic Algorithm?Ⅱ，NSGA?Ⅱ）[10]可有效解決多目標優化問題，且全局尋優能力較強。灰狼優化（Gray Wolf Optimization，GWO）算法[11]具有收斂性強、參數少、較易編程實現、局部搜索能力強等特點[12-13]。這2 種算法被應用于求解礦山卡車調度[14]、流水線車間調度[15]、函數優化[16-18]、車輛路徑優化[19]和多輸入多輸出系統調度優化[20]等問題。但NSGA?II在求解有約束多目標問題時中后期容易收斂緩慢，GWO 算法種群的多樣性在迭代進化過程中逐步降低，易陷入局部最優。因此，本文以純電動卡車為研究對象，建立了運輸成本最小、總排隊時間最短和礦石品位偏差最小的多目標露天礦低碳運輸調度優化模型；在NSGA?II 中后期引入GWO 算法來改善其收斂緩慢的問題，提出了一種GWO?NSGA?Ⅱ混合算法，并將其用于求解露天礦低碳運輸調度優化模型。

1 露天礦低碳運輸調度優化模型

1.1 目標函數

露天礦卡車調度是復雜的綜合系統工程，在實際開采過程中往往是多個采礦場和破碎場間的協同作業。采礦場與破碎場之間的距離不同，則卡車運輸作業時間不同，產生的碳排放和運輸費用也不同。露天礦卡車作業調度涉及的優化目標包括運輸時間最短、距離最短、設備利用率最高、運輸成本最小等。為更好地反映實際狀況，本文采用多目標優化卡車調度，以實際生產中企業重點關注的運輸成本、總排隊時間、礦石品位偏差為目標，構建露天礦低碳運輸調度優化模型。

某露天礦實際開采過程中，有n個 采礦場Ai(i=1,2,···,n)、m個 破碎場 Bj(j=1,2,···,m)和k輛純電動卡車，純電動卡車在采礦場與破碎場之間往返作業，采礦場 Ai到 破碎場 Bj的距離為Di j。模型的各個優化目標用函數表示，純電動卡車調度參數統稱為S，構建的露天礦低碳運輸調度優化模型的目標函數為

式中：F1(S)為 運輸成本；F2(S)為 總排隊時間；F3(S)為礦石品位偏差。

純電動卡車所需的電能來自火力發電，因此在模型構建中增加了來自電能產生的碳排放成本，以更全面地考慮運輸成本。碳排放成本以行駛距離作為指標進行計算。根據碳排放計算理論，卡車的碳排放成本為[21]

式中： η為單位電量火力發電占比；Cr1為 第r(r=1,2,···,k)輛 卡車單位碳排放的環境成本； λ為電能產生的碳排放系數；Xrij,Yr ji分別為第r輛卡車滿載和空載次數； ρ1,ρ2分別為卡車重載和空載時的單位里程電能消耗量。

為了降低車輛碳排放的同時使企業收益最大，設運輸成本最小為目標，綜合考慮重載、空載成本，碳排放成本及人工成本，與燃油卡車相比，純電動卡車后期保養費用低，不納入成本計算。卡車運輸成本為

式中：Cr2，Cr3分別為第r輛卡車作業時每度電的單位成本和人工費用；Tr為1 個班次內第r輛卡車運行時間。

實際工況中希望開采任務工期短，因此將時間成本作為單獨目標進行優化可以有效避免不合理調度導致的卡車排隊時間較長問題。總排隊時間包含生產過程中的卡車充電時間、運行時間及維修等待時間，則有

式中：Tlimit為1 個班次時間，設定為8 h；T1rij為第r輛卡車滿載運輸時間；T0rij為第r輛卡車空載運輸時間；Trrepair為第r輛卡車維修保養時間；Trvcharge為第r輛卡車在第v（v=1,2,···,z，z為充電樁數量）臺充電樁充電時間。

礦石品位偏差為

式中：Wi為 第i個 采礦場的開采量；Wφ為目標品位礦石總量；Lr為第r輛卡車容量。

1.2 約束條件

卡車裝載量應不小于破碎場的計劃產量：

式中pj為第j個破碎場的計劃產量。

卡車裝載量應不大于破碎場的破碎量：

式中qj為 第j個破碎場的破碎量。

卡車裝載量應不大于采礦場的開采量：

1 個班次內采礦場裝車數量應小于采礦場最大裝車數量：

式中bi為1 個班次內采礦場最大裝車數量。

破碎場礦石品位誤差應小于品位允許誤差：

式中： φi為第i個 采礦場的礦石品位； φmin為最低礦石品位； ?φ為品位允許誤差。

1 個充電樁1 次只能給1 輛純電動卡車充電，不能多個充電樁同時給1 輛卡車充電：

式中urv為 第r輛卡車在第v臺充電樁上的狀態，urv=1時 表示充電，urv=0時表示不充電。

卡車充電量應不大于充電站提供的最大電量：

式中：Emin為 卡車作業的最低電量；Emax為充電站提供的最大電量。

2 GWO?NSGA?Ⅱ混合算法

2.1 GWO 算法

GWO 算法是模擬自然界灰狼種群狩獵機制的群智能搜索算法?；依欠N群內社會階層等級嚴格分明，自頂向下分為 α，β，δ，ω 4 個階層。4 個階層的灰狼獵食分工不同： α層為灰狼領導層，負責狼群所有事務； β層為灰狼管理層，負責輔佐 α層頭狼領導和狩獵事務； δ層為灰狼普通層，負責執行 α,β層灰狼發出的狩獵指令； ω層為灰狼底層，聽從 α，β，δ層灰狼的指令，朝狩獵最優方向移動。GWO 算法基本思想：首先，灰狼種群在追捕獵物過程中，根據獵物的味道等信息，頭狼及管理層灰狼逐步確定獵物的方向，帶領普通層及底層的灰狼接近獵物并建立狩獵包圍圈；然后，底層灰狼根據 α，β，δ層灰狼的領導逐漸縮小包圍圈；最后，狼群在頭狼和管理層灰狼的組織下對獵物發動攻擊，直至捕獲到獵物為止。GWO 算法求解問題的步驟如下：

Step1：初始化算法參數（收斂因子、方位向量及參數向量），產生若干個體，設置最大迭代次數。

Step2：計算每個個體的適應度函數值。

Step3：比較個體的適應度函數值和方位向量的適應度函數值，確定當前最優搜索單元、次優搜索單元和第3 優搜索單元。

Step4：計算收斂因子、方位向量及參數向量的適應度函數值，更新當前最優搜索單元、次優搜索單元和第3 優搜索單元空間坐標。

Step5：計算最優搜索單元、次優搜索單元和第3 優搜索單元空間坐標的平均值，得到更新后當前每個個體位置。

Step6：若達到最大迭代次數，輸出最優個體的適應度函數值，否則轉到Step2。

2.2 NSGA?Ⅱ

NSGA?Ⅱ是一種帶精英保留策略的多目標優化遺傳算法，其核心為非支配排序、擁擠度距離計算和擁擠度比較算子。

NSGA?Ⅱ求解問題的一般步驟：首先初始化種群，判斷是否生成第1 代子種群，未生成則采用非支配排序后通過選擇、交叉、變異操作生成第1 代子種群；其次引入精英保留策略，合并父代與子代生成新種群，擴大下一代個體的篩選范圍以增加種群解的多樣性；然后對新的種群進行非支配排序，同時對非支配層中的個體遍歷并進行擁擠度距離計算，根據非支配關系及個體的擁擠度選取合適的個體組成新的父代種群；最后通過選擇、交叉、變異產生新的子代種群，并計算適應度函數值，直至滿足結束條件，輸出Pareto 最優解集。

2.3 混合算法

GWO 算法具備很強的搜索能力，但由于自身收斂性強，在多目標優化過程中會有很多Pareto 解丟失。NSGA?Ⅱ在運行后期容易陷入收斂緩慢，但NSGA?Ⅱ的精英保留策略和快速非支配排序具有多樣性保持策略，能很好地解決GWO 算法后期Pareto 解丟失的問題。因此將2 種算法進行混合，通過GWO?NSGA?Ⅱ混合算法實現全局搜索和局部搜索的有效結合。GWO?NSGA?Ⅱ混合算法流程如圖1所示。

圖1 GWO?NSGA?Ⅱ混合算法流程Fig. 1 GWO?NSGA?Ⅱ hybrid algorithm flow

GWO?NSGA?Ⅱ混合算法實現步驟如下。

Step1：初始化種群，隨機產生若干個個體，形成初始種群。

Step2：非支配排序后，通過NSGA?Ⅱ的選擇、交叉、變異操作，基于GWO 算法的領導者圍捕策略更新生成第1 代子代種群作為候選解集。

Step3：混合父代和子代種群，經染色體重組后判斷是否生成新的父代種群，若是則執行Step5，否則執行Step4。

Step4：對混合的種群執行快速非支配排序和擁擠度距離計算，并根據設定值篩選合適的個體生成新父代種群。

Step5：計算當前種群中個體的適應度函數值，再次進行非支配排序和擁擠度距離計算。通過計算個體的非支配解和支配解數量，比較種群中所有個體，經過多次迭代后得到非劣解分層，并對不同的Pareto 前沿解集中任意個體的擁擠度距離進行計算，獲得NSGA?Ⅱ的適應度函數值。然后使用GWO 算法的狩獵和攻擊操作進行優化，基于 α,β,δ層灰狼的適應度函數值更新狼群方位，完成狩獵操作，通過收斂因子逐漸遞減完成攻擊操作，最終獲得Pareto 前沿優化解。

Step6：判斷當前迭代次數G是否小于最大迭代次數，若是則執行G=G+1并返回Step3，否則在所有Pareto 前沿解中篩選并輸出最優解。

3 實驗分析

3.1 GWO?NSGA?Ⅱ混合算法收斂性與穩定性分析

為了評估GWO?NSGA?Ⅱ混合算法收斂性與穩定性，在目標優化標準測試函數（ZDT1—ZDT4，ZDT6）上對GWO?NSGA?Ⅱ與實數編碼NSGA?Ⅱ進行測試比較。測試函數具體公式見文獻[22]。

測試參數設置參照文獻[23]：測試函數種群規模大小均為300，最大迭代次數為200，Pareto 前沿解集大小為500。

收斂性指標為

式中：y為求出的Pareto 前沿解；P為求出的Pareto 前沿 解 集；x為 真 實 的Pareto 前 沿 解；P?為 真 實 的Pareto 前沿解集；Ds(x,y)為求出的Pareto 前沿解與真實的Pareto 前沿解的歐氏距離。

穩定性指標為

式中：df為極端解集中邊界解的歐氏距離；dl為非支配解集中邊界解的歐氏距離；dε為最佳非支配解集中第ε（ ε =0，1，… ，N，N為最佳非支配解集中連續解的數量）個與第 ε +1個連續解間的歐氏距離；為dε的平均值。

為保證性能指標的穩定性，對每個標準測試函數連續運行30 次，并對性能指標求取平均值，測試結果見表1?？煽闯鯣WO?NSGA?Ⅱ在保證收斂性指標 γ穩定的情況下，穩定性指標 ?有所提升，最高提升了26.03%。

表1 不同算法的標準測試函數測試結果對比Table 1 Comparison of standard test function test results of different algorithms

GWO?NSGA?Ⅱ混合算法對標準測試函數的測試 結 果 如 圖2 所 示（f1(x),f2(x)為ZDT1—ZDT4 和ZDT6 的 目 標 函 數）?？?看 出GWO?NSGA?Ⅱ的Pareto 優化解分布均勻，可得到良好的分布前沿，說明該算法對于求解多目標有約束問題是有效的。

圖2 GWO?NSGA?Ⅱ混合算法對標準測試函數的測試結果Fig. 2 Test results of GWO-NSGA-Ⅱ hybrid algorithm on standard test functions

3.2 露天礦運輸調度實例分析

為驗證GWO?NSGA?Ⅱ混合算法在實際場景中應用的有效性，以某露天礦某天的礦用純電動卡車實際運輸調度數據為例，將混合算法應用于求解露天礦低碳運輸調度優化模型，并與NSGA?Ⅱ，GWO算法進行對比分析。

該露天礦有4 個破碎場，8 個采礦場，裝載和卸載時間分別為4，2 min，采礦場至破碎場的距離見表2。根據露天礦的實際布置情況，充電站在距離破碎場約200 m 處，且每個充電站有4 臺充電樁。該露天礦要求1 個班次（12 h）內破碎場的運輸量為8 000 t。卡車的維護保養成本為1 元/km?？ㄜ囍剌d行駛和空載行駛的平均速度分別為20，35 km/h。

表2 采礦場至破碎場距離Table 2 Distance between mining site and crushing site

GWO?NSGA?Ⅱ 參數設置：搜索空間維度為20，初始種群大小為100，進化迭代次數為600，最大精英迭代次數為200，交叉概率和變異概率分別為0.1，0.5。GWO 算法參數設置參照文獻[11]，NSGA?Ⅱ參數設置參照文獻[14]。為降低算法在時間上的復雜度，本文將目標函數作為適應度函數，并使用Matlab 2019b 對露天礦低碳運輸調度問題進行仿真求解，進化曲線如圖3 所示。

從圖3 可看出，與NSGA?Ⅱ和GWO 算法相比，GWO?NSGA?Ⅱ的尋優速度分別提高了48.7%和27.1%，尋優精度分別提高了17.1%和9.3%。GWO?NSGA?Ⅱ的進化曲線在100 次迭代之前變化迅速，在100 次迭代之后趨于平穩。這是由于GWO?NSGA?Ⅱ在初期繼承了NSGA?Ⅱ較強的計算能力和全局搜索能力，使得種群快速收斂到全局最優附近；在中后期，GWO 算法的加入讓種群能夠快速集中到最優種群的周圍，且減少Pareto 前沿解的丟失，降低了NSGA?Ⅱ中后期陷入收斂緩慢的概率，從而均衡了全局最優與局部最優。

圖3 不同算法的進化曲線Fig. 3 Evolution curves of different algorithms

在實際運輸調度中1 個班次需要40 輛純電動卡車，根據式（2）、式（3），結合該露天礦具體參數可知，1 個班次作業調度實際運輸距離為411.9 km，用電費用為889.704 元，碳排放費用為288.33 元，運輸費用為1 178.034 元。分別基于NSGA?Ⅱ，GWO，GWO?NSGA?Ⅱ求解的露天礦低碳運輸調度的用電費用、碳排放費用和運輸費用（不含司機勞務費用）見表3。

表3 不同算法下露天礦低碳運輸調度結果對比Table 3 Comparison of low-carbon transportation scheduling results in open-pit mine under different algorithms

從表3 可看出，與實際運輸數據相比，在同一個班次內采用混合GWO?NSGA?Ⅱ混合算法求解，運輸距離減少了97.086 km，純電動卡車數量減少了10 輛，用電費用節省了209.706 元，碳排放費用節省了67.961 元，運輸費用節省了277.665 元；而采用NSGA?Ⅱ和GWO 算法求解的運輸費用僅分別節省了92.296 元和184.983 元。

為對比燃油卡車與純電動卡車在GWO?NSGA?Ⅱ混合算法下的運輸成本及碳排放量，以某公司同一型號不同版本的卡車作為研究對象進行實驗。電動卡車型號為DW90A?EV，燃油卡車型號為DW90A，額定載質量均為58 t，在1 個班次運輸距離和使用車輛數相同。在考慮發電廠電能產生的碳排放成本的條件下，燃油卡車與電動卡車用電費用、碳排放量和運輸費用對比見表4?？煽闯霾捎肎WO?NSGA?Ⅱ混合算法優化露天礦純電動卡車運輸調度，極大減少了碳排放量和運輸費用。

表4 不同類型卡車露天礦運輸調度結果對比Table 4 Comparison of transportation scheduling results in open-pit mine under different types of truck

4 結論

1） 考慮碳排放費用、維修費用及卡車保養費用，構建了以運輸成本、總排隊時間、礦石品位偏差為優化目標的露天礦低碳運輸調度優化模型。

2） 針對NSGA?Ⅱ后期陷入收斂速度緩慢的缺點，在NSGA?Ⅱ搜索過程中融入GWO 算法，提出了GWO?NSGA?Ⅱ混合算法。該算法不僅能對解空間進行全面搜索，均衡全局尋優能力和局部尋優能力，而且收斂性及穩定性也顯著提升。

3） 將GWO?NSGA?Ⅱ混合算法應用于求解實際露天礦運輸調度優化模型，與NSGA?Ⅱ，GWO 算法相比，不僅提高了算法的收斂精度和速度，而且減少了卡車使用數量、運輸距離和運輸費用。與燃油卡車相比，純電動卡車極大地降低了運輸費用和碳排放量。