基于布谷鳥搜索算法的露天煤礦運(yùn)輸路徑優(yōu)化研究

張東旭

(1.中煤科工集團(tuán)沈陽研究院有限公司，遼寧省撫順市，113122；2.煤礦安全技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，遼寧省撫順市， 113122 )

0 引言

露天煤礦開采伴隨著大量的土石方運(yùn)輸，運(yùn)輸投資占礦山總投資的40%～60%，所占投入成本較大，嚴(yán)重影響著礦山的經(jīng)濟(jì)效益。露天煤礦道路網(wǎng)絡(luò)變化受時(shí)空演化規(guī)律所制約[1]，隨著工程位置的推進(jìn)，不斷有舊的道路被廢除，同時(shí)又有新的道路被生成，如此周而復(fù)始，道路復(fù)雜多變，卡車運(yùn)輸路徑很不固定。近年來，我國進(jìn)入智能化露天煤礦發(fā)展階段，無人駕駛技術(shù)逐漸成熟，合理的運(yùn)輸路徑規(guī)劃是實(shí)現(xiàn)礦山內(nèi)無人駕駛卡車運(yùn)行的基礎(chǔ)和前提，也是降低礦山投入成本、提高經(jīng)濟(jì)效益的有效方式。

露天煤礦路徑優(yōu)化問題一直是礦山研究領(lǐng)域的熱點(diǎn)問題，國內(nèi)外專家學(xué)者已對(duì)其進(jìn)行過大量的研究，并取得豐富的研究成果。孫臣良等[2]研究人員基于粒子群算法作為優(yōu)化算法，以路面質(zhì)量、坡度和承載能力等因素建立運(yùn)輸?shù)缆纺Ｐ退阉髯顑?yōu)路徑。但算法中由于所有的粒子都易向局部最優(yōu)解的方向飛去，粒子方向失去多樣性，導(dǎo)致算法精度不高，且后期收斂速度越來越慢；Choi和Nieto[3]以改進(jìn)的LCPA(least-cost path analysis)方法，在考慮地形起伏和沿途曲線的基礎(chǔ)上，以最小化卡車的運(yùn)輸時(shí)間以及產(chǎn)生的燃料消耗為目標(biāo)求解最優(yōu)路徑，但忽略了路網(wǎng)模型節(jié)點(diǎn)之間的拓?fù)潢P(guān)系；柴森霖等[4]研究人員基于改進(jìn)遺傳算法為方法，建立以最小時(shí)變運(yùn)輸功為目標(biāo)的路徑優(yōu)化模型；劉光偉等[5]研究人員建立了基于選線道路費(fèi)用最優(yōu)的數(shù)學(xué)模型，將生物激勵(lì)神經(jīng)網(wǎng)絡(luò)引入到路徑基因編碼過程中對(duì)遺傳算法進(jìn)行改進(jìn)，以此提高算法的迭代收斂速度，但改進(jìn)后遺傳算法仍存在染色體的交叉和編譯后，種群已無法產(chǎn)生優(yōu)于本體的子代個(gè)體，出現(xiàn)局部最優(yōu)的情況。

在以上研究中，由于優(yōu)化算法在實(shí)現(xiàn)過程中的隨機(jī)性，使得大多都存在優(yōu)化算法易陷入局部最優(yōu)解、收斂速度慢、建立路徑優(yōu)化模型時(shí)考慮影響因素不全面等問題。為了優(yōu)化路徑擇優(yōu)模型，提高算法收斂速度和精確度，本文通過對(duì)卡車工作過程中行駛路面狀況進(jìn)行分析，綜合考慮卡車行駛速度、道路坡度、路面質(zhì)量等因素，建立以最小運(yùn)輸功為目標(biāo)的路徑優(yōu)化模型，以布谷鳥搜索算法為優(yōu)化方法對(duì)最優(yōu)路徑進(jìn)行搜索。該算法擁有獨(dú)特的冪律規(guī)律萊維飛行行為，加快算法的局部搜索能力，并且能隨機(jī)產(chǎn)生新解對(duì)上一迭代中的解進(jìn)行更新，快速跳出局部最優(yōu)解。最后以寶日希勒露天煤礦為實(shí)例應(yīng)用進(jìn)行分析驗(yàn)證模型的精確性與算法的有效性。

1 問題描述與模型建立

1.1 問題描述

露天煤礦運(yùn)輸路徑優(yōu)化即在道路網(wǎng)絡(luò)中保證安全、經(jīng)濟(jì)效益與滿足現(xiàn)場實(shí)際的條件下進(jìn)行卡車行駛最優(yōu)路徑選取的問題研究[6]。傳統(tǒng)的路徑優(yōu)化模型多是以最少運(yùn)輸費(fèi)用或最短運(yùn)輸距離為目標(biāo)而建立優(yōu)化模型，其考慮的影響因素較為單一，但影響露天煤礦路徑優(yōu)化的因素眾多，包括維修成本、油耗成本、路面質(zhì)量等。本文根據(jù)露天煤礦的現(xiàn)場地理環(huán)境，找出卡車從裝載點(diǎn)到卸載點(diǎn)往返之間的最小運(yùn)輸功，以此求出最佳運(yùn)輸路徑。露天煤礦運(yùn)輸路徑示意圖如圖1所示。

圖1 露天煤礦運(yùn)輸路徑示意圖

1.2 模型建立

露天煤礦運(yùn)輸路徑優(yōu)化問題可描述為：在露天煤礦運(yùn)輸系統(tǒng)網(wǎng)絡(luò)中，采剝工作面節(jié)點(diǎn)(裝載點(diǎn))與排棄工作面節(jié)點(diǎn)(卸載點(diǎn))之間存在多條可供選擇的運(yùn)輸路徑，但每條運(yùn)輸路徑卡車行駛消耗運(yùn)輸功差別很大，利用優(yōu)化算法動(dòng)態(tài)搜索出一條運(yùn)輸路徑，使此路徑卡車行駛消耗運(yùn)輸功最小。假設(shè)露天煤礦道路網(wǎng)絡(luò)表示為G{V,E,W}，其中V={1,2,3,…,n}表示路網(wǎng)中所有非空節(jié)點(diǎn)集合；E表示弧段集合，i,j節(jié)點(diǎn)之間弧段ei,j=(i,j)∈E；W表示卡車經(jīng)過各弧段消耗的運(yùn)輸功所組成的矩陣。

1.2.1影響因素分析

影響卡車做功的因素眾多，但路面質(zhì)量以及路段坡度對(duì)卡車行駛消耗的程度不可忽視。路面質(zhì)量的好壞直接影響著卡車克服滾動(dòng)阻力所做功的大小，路段坡度越大卡車克服坡度阻力做功越大。以卡車重載經(jīng)過之后路面留下車轍程度為評(píng)判依據(jù)，將路面質(zhì)量劃分為5個(gè)等級(jí)及其不同等級(jí)所對(duì)應(yīng)的滾動(dòng)阻力系數(shù)見表1。

表1 路面質(zhì)量等級(jí)及滾動(dòng)阻力系數(shù)

1.2.2最優(yōu)路徑規(guī)劃模型

假設(shè)卡車在相同等級(jí)的路面上行駛的速度是一致的，卡車速度在裝載點(diǎn)與卸載點(diǎn)之間服從正態(tài)分布。一條完整路徑總運(yùn)輸功是由組成該路徑的各路段運(yùn)輸功的加和，而卡車在行駛過程中總運(yùn)輸功主要由克服重力做功和克服阻力做功這2部分組成。

卡車在行駛時(shí)克服重力做功見式(1)：

We=G·H

(1)

式中：We——克服重力做功，N；

G——卡車載重，t；

H——坡路高程，m。

卡車在行駛時(shí)克服阻力做功見式(2)：

(2)

式中：Wf——克服阻力做功，N；

Ff——滾動(dòng)阻力，N;

Fw——空氣阻力，N;

Fp——坡度阻力，N;

L——卡車的實(shí)際運(yùn)輸距離，km；

f——滾動(dòng)阻力系數(shù)；

C——空氣阻力系數(shù)；

A——卡車迎風(fēng)面積，m2；

μ——坡度阻力新系數(shù)，μ=sinθ。

卡車以最小運(yùn)輸功為目標(biāo)的最優(yōu)路徑規(guī)劃模型見式(3)：

(3)

式中：n——節(jié)點(diǎn)個(gè)數(shù)，個(gè)；

i——第i個(gè)節(jié)點(diǎn)；

j——第j個(gè)節(jié)點(diǎn)；

Fij——道路阻力，N；

Sij——道路狀態(tài)變量，其中Sij=0時(shí)，eij為不可行弧段，Sij=1時(shí)，eij為可行弧段；

Lij——弧段eij的實(shí)際長度，km；

eij——ij節(jié)點(diǎn)之間弧段；

R——可選弧段集；

△Hij——路段eij的高程差，km。

露天煤礦工作空間具有固定封閉的特性，巖石剝離物的排棄空間相對(duì)固定，不能隨機(jī)選擇卸載點(diǎn)，在道路網(wǎng)絡(luò)卡車運(yùn)輸工作中需給定起始節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)。而重力做功只跟卡車從初始節(jié)點(diǎn)到終了節(jié)點(diǎn)的高程差有關(guān)，與運(yùn)輸路徑無關(guān)，由于卡車選擇最優(yōu)路徑之前已確定好裝載點(diǎn)與卸載點(diǎn)的位置，因此，所選路徑集中，重力做功相同，在建立最小運(yùn)輸功模型時(shí)可略去重力做功以簡化模型，僅比較克服阻力做功即能選出最優(yōu)路徑。

當(dāng)裝載點(diǎn)與卸載點(diǎn)之間卡車重載或空載行駛時(shí)克服阻力做功最小即為最優(yōu)路徑。最優(yōu)路徑規(guī)劃模型可簡化為式(4)：

(4)

2 布谷鳥搜索算法

劍橋大學(xué)YANG X S和Suash Deb教授通過觀察某些種屬布谷鳥的寄生性育雛行為，并發(fā)現(xiàn)將其行為轉(zhuǎn)化為數(shù)學(xué)方式可有效求解最優(yōu)化問題，于是2009年提出了布谷鳥搜索算法CS(Cuckoo Search)[7]。研究發(fā)現(xiàn)，CS算法比遺傳算法(Genetic Algorithm，GA算法)、人工蜂群算法(Artificial Bee Colony，ABC算法)和粒子群算法(Particle Swarm Optimization，PSO算法)等典型群體智能算法具有更高的效率，可在部分求最優(yōu)化函數(shù)下得到相對(duì)較好的優(yōu)化結(jié)果[7-9]。目前，CS算法已被應(yīng)用于多種工程優(yōu)化問題[10]。

CS算法的主要思想是種屬布谷鳥類的巢穴寄生行為以及其獨(dú)有的冪律規(guī)律萊維飛行行為。在應(yīng)用CS算法求解工程實(shí)例問題時(shí)，需假設(shè)以下幾項(xiàng)理想化規(guī)則：

(1)假設(shè)每只布谷鳥每次隨機(jī)選擇寄生巢穴并只下1個(gè)蛋；

(2)具有優(yōu)質(zhì)蛋的最佳巢穴將保留至下一代；

(3)寄生鳥巢數(shù)量n不變，可認(rèn)為鳥巢、蛋、函數(shù)解三者數(shù)量相等，蛋被寄主發(fā)現(xiàn)后丟出鳥巢或棄巢新建的概率為Pa∈[0,1]。

基于以上3條準(zhǔn)則，從實(shí)際角度出發(fā)，設(shè)置概率Pa控制選擇局部隨機(jī)游走或全局隨機(jī)游走，巢穴中的寄生蛋即為函數(shù)的一個(gè)解，算法迭代過程中的目標(biāo)是利用優(yōu)質(zhì)解替換掉劣質(zhì)解。當(dāng)采用局部隨機(jī)游走更新方式表示見式(5)：

?——步長縮放因子；

S——步長；

?——元素點(diǎn)乘；

H(u)——一個(gè) Heaviside 函數(shù)；

Pa——概率；

ε——從均勻分布中抽取的隨機(jī)數(shù)；

采用全局隨機(jī)游走更新方式表示見式(6)：

(6)

式中：β——萊維指數(shù)；

Lévy(β)——服從萊維指數(shù)β的萊維飛行搜索路徑。

通過式(5)或者式(6)進(jìn)行位置更新后，生成隨機(jī)的數(shù)字r(r∈[0，1])，對(duì)r與Pa進(jìn)行比較，如果r

以下為CS算法偽代碼：

1.建立優(yōu)化目標(biāo)函數(shù)；

3.while(t

4.隨機(jī)取一個(gè)布谷鳥；

5.通過Lévy飛行產(chǎn)生一個(gè)解；

6.評(píng)估解的質(zhì)量或目標(biāo)函數(shù)值fi；

7.從n個(gè)鳥巢中隨機(jī)抽取一個(gè)(假設(shè)為j)；

8.iffi

9.將j用解i代替；

10.end if；

11.一部分(Pa)糟糕的巢被拋棄；

12.新巢(解)由式(4)產(chǎn)生；

13.保存最佳的解；

14.排列解找出當(dāng)前最佳；

15.更新t←t+1；

16.end while；

17.后處理與可視化。

經(jīng)上述描述可以看出，CS算法具有設(shè)置參數(shù)較少、步驟簡單、容易實(shí)現(xiàn)等優(yōu)點(diǎn)，有著較好的全局搜索能力。眾多學(xué)者研究并在實(shí)例中應(yīng)用后表明布谷鳥搜索算法是非常有效的[11-12]。在應(yīng)用布谷鳥算法求解露天煤礦最優(yōu)化問題時(shí)，由于路網(wǎng)模型存在拓?fù)潢P(guān)系，各節(jié)點(diǎn)之間不能采用隨機(jī)的方式進(jìn)行聯(lián)通，因此，在種群初始化時(shí)，從起始節(jié)點(diǎn)開始，選擇相鄰節(jié)點(diǎn)作為第二位置，并重復(fù)此步驟直至目標(biāo)節(jié)點(diǎn)為止，由此構(gòu)成一條完整路徑。

3 實(shí)驗(yàn)與分析

為了驗(yàn)證CS算法在露天煤礦運(yùn)輸路徑優(yōu)化中的有效性，在Windows 10操作系統(tǒng)平臺(tái)的MATLAB R2018a進(jìn)行數(shù)值仿真實(shí)驗(yàn)。選取寶日希勒露天煤礦2019年12月路網(wǎng)數(shù)據(jù)進(jìn)行分析，整理出該露天煤礦路網(wǎng)裝載點(diǎn)至卸載點(diǎn)間共有27個(gè)節(jié)點(diǎn)、31條路段。寶日希勒露天煤礦路網(wǎng)分布示意圖如圖2所示。

圖2 寶日希勒露天煤礦路網(wǎng)分布示意圖

該礦應(yīng)用220 t的MT4400型礦用運(yùn)輸卡車，迎風(fēng)面積A=51.28 m2。運(yùn)行布谷鳥搜索算法時(shí)，發(fā)現(xiàn)設(shè)置參數(shù)初始鳥巢數(shù)量n=25，概率Pa=0.25，步長縮放因子?=0.5，萊維指數(shù)β=0.8，迭代次數(shù)設(shè)為200次時(shí)，算法收斂最快。算法運(yùn)行得出的卡車行駛最優(yōu)路徑與所對(duì)應(yīng)消耗的克服阻力做功見表2,該礦卡車實(shí)際運(yùn)輸路徑與所對(duì)應(yīng)消耗的克服阻力做功見表3。

由表2和表3可以看出，編號(hào)1和4的實(shí)際運(yùn)輸路徑即為最優(yōu)路徑；編號(hào)2和6的最優(yōu)路徑雖然運(yùn)輸距離大，但克服阻力做功要小于現(xiàn)場實(shí)際的運(yùn)輸路徑；編號(hào)2、3、7、8的現(xiàn)場實(shí)際運(yùn)輸路徑不是最優(yōu)運(yùn)輸路徑。因此可知，以運(yùn)輸路徑最小為優(yōu)化目標(biāo)不能確定出最優(yōu)路徑。

由上述分析可知，當(dāng)給定起始節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)，算法能在保證精度的前提下快速收斂于全局最優(yōu)解，例如本實(shí)驗(yàn)給定起始節(jié)點(diǎn)2與目標(biāo)節(jié)點(diǎn)21，最終得出路徑2-3-4-27-8-21為最優(yōu)路徑。CS算法迭代過程如圖3所示。

表2 裝載點(diǎn)到卸載點(diǎn)最優(yōu)路徑及所對(duì)應(yīng)消耗的克服阻力做功

表3 裝載點(diǎn)到卸載點(diǎn)現(xiàn)場實(shí)際運(yùn)輸路徑及所對(duì)應(yīng)消耗的克服阻力做功

圖3 CS算法迭代過程

4 結(jié)語

本文將卡車行駛過程中克服重力做功與克服阻力做功之和作為卡車消耗總運(yùn)輸功，以最小化總運(yùn)輸功為目標(biāo)建立了露天煤礦卡車運(yùn)輸路徑優(yōu)化模型。在給定起始節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)后，以布谷鳥搜索算法搜尋卡車行駛最優(yōu)路徑，結(jié)合寶日希勒露天煤礦現(xiàn)場實(shí)際情況，結(jié)果表明運(yùn)輸路徑最小為優(yōu)化目標(biāo)不能確定出最優(yōu)路徑，而在綜合考慮卡車行駛速度、道路坡度、路面質(zhì)量的因素前提下，建立以最小運(yùn)輸功為目標(biāo)的路徑優(yōu)化模型，以布谷鳥搜索算法為優(yōu)化方法對(duì)最優(yōu)路徑進(jìn)行搜索，該算法收斂速度快，在一定程度上達(dá)到了理想優(yōu)化效果，具有較高的實(shí)用價(jià)值。