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

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

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

0 引言

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

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

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

1 露天礦低碳運輸調(diào)度優(yōu)化模型

1.1 目標函數(shù)

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

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

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

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

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

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

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

實際工況中希望開采任務(wù)工期短，因此將時間成本作為單獨目標進行優(yōu)化可以有效避免不合理調(diào)度導(dǎo)致的卡車排隊時間較長問題?？偱抨爼r間包含生產(chǎn)過程中的卡車充電時間、運行時間及維修等待時間，則有

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

礦石品位偏差為

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

1.2 約束條件

卡車裝載量應(yīng)不小于破碎場的計劃產(chǎn)量：

式中pj為第j個破碎場的計劃產(chǎn)量。

卡車裝載量應(yīng)不大于破碎場的破碎量：

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

卡車裝載量應(yīng)不大于采礦場的開采量：

1 個班次內(nèi)采礦場裝車數(shù)量應(yīng)小于采礦場最大裝車數(shù)量：

式中bi為1 個班次內(nèi)采礦場最大裝車數(shù)量。

破碎場礦石品位誤差應(yīng)小于品位允許誤差：

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

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

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

卡車充電量應(yīng)不大于充電站提供的最大電量：

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

2 GWO?NSGA?Ⅱ混合算法

2.1 GWO 算法

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

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

Step2：計算每個個體的適應(yīng)度函數(shù)值。

Step3：比較個體的適應(yīng)度函數(shù)值和方位向量的適應(yīng)度函數(shù)值，確定當(dāng)前最優(yōu)搜索單元、次優(yōu)搜索單元和第3 優(yōu)搜索單元。

Step4：計算收斂因子、方位向量及參數(shù)向量的適應(yīng)度函數(shù)值，更新當(dāng)前最優(yōu)搜索單元、次優(yōu)搜索單元和第3 優(yōu)搜索單元空間坐標。

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

Step6：若達到最大迭代次數(shù)，輸出最優(yōu)個體的適應(yīng)度函數(shù)值，否則轉(zhuǎn)到Step2。

2.2 NSGA?Ⅱ

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

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

2.3 混合算法

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

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

GWO?NSGA?Ⅱ混合算法實現(xiàn)步驟如下。

Step1：初始化種群，隨機產(chǎn)生若干個個體，形成初始種群。

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

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

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

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

Step6：判斷當(dāng)前迭代次數(shù)G是否小于最大迭代次數(shù)，若是則執(zhí)行G=G+1并返回Step3，否則在所有Pareto 前沿解中篩選并輸出最優(yōu)解。

3 實驗分析

3.1 GWO?NSGA?Ⅱ混合算法收斂性與穩(wěn)定性分析

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

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

收斂性指標為

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

穩(wěn)定性指標為

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

為保證性能指標的穩(wěn)定性，對每個標準測試函數(shù)連續(xù)運行30 次，并對性能指標求取平均值，測試結(jié)果見表1。可看出GWO?NSGA?Ⅱ在保證收斂性指標 γ穩(wěn)定的情況下，穩(wěn)定性指標 ?有所提升，最高提升了26.03%。

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

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

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

3.2 露天礦運輸調(diào)度實例分析

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

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

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

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

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

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

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

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

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

為對比燃油卡車與純電動卡車在GWO?NSGA?Ⅱ混合算法下的運輸成本及碳排放量，以某公司同一型號不同版本的卡車作為研究對象進行實驗。電動卡車型號為DW90A?EV，燃油卡車型號為DW90A，額定載質(zhì)量均為58 t，在1 個班次運輸距離和使用車輛數(shù)相同。在考慮發(fā)電廠電能產(chǎn)生的碳排放成本的條件下，燃油卡車與電動卡車用電費用、碳排放量和運輸費用對比見表4。可看出采用GWO?NSGA?Ⅱ混合算法優(yōu)化露天礦純電動卡車運輸調(diào)度，極大減少了碳排放量和運輸費用。

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

4 結(jié)論

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

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

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