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

張東旭

(1.中煤科工集團(tuán)沈陽(yáng)研究院有限公司，遼寧省撫順市，113122；2.煤礦安全技術(shù)國(guó)家重點(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)輸路徑很不固定。近年來(lái)，我國(guó)進(jìn)入智能化露天煤礦發(fā)展階段，無(wú)人駕駛技術(shù)逐漸成熟，合理的運(yùn)輸路徑規(guī)劃是實(shí)現(xiàn)礦山內(nèi)無(wú)人駕駛卡車運(yùn)行的基礎(chǔ)和前提，也是降低礦山投入成本、提高經(jīng)濟(jì)效益的有效方式。

露天煤礦路徑優(yōu)化問(wèn)題一直是礦山研究領(lǐng)域的熱點(diǎn)問(wèn)題，國(guó)內(nèi)外專家學(xué)者已對(duì)其進(jìn)行過(guò)大量的研究，并取得豐富的研究成果。孫臣良等[2]研究人員基于粒子群算法作為優(yōu)化算法，以路面質(zhì)量、坡度和承載能力等因素建立運(yùn)輸?shù)缆纺Ｐ退阉髯顑?yōu)路徑。但算法中由于所有的粒子都易向局部最優(yōu)解的方向飛去，粒子方向失去多樣性，導(dǎo)致算法精度不高，且后期收斂速度越來(lái)越慢；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ò)引入到路徑基因編碼過(guò)程中對(duì)遺傳算法進(jìn)行改進(jìn)，以此提高算法的迭代收斂速度，但改進(jìn)后遺傳算法仍存在染色體的交叉和編譯后，種群已無(wú)法產(chǎn)生優(yōu)于本體的子代個(gè)體，出現(xiàn)局部最優(yōu)的情況。

在以上研究中，由于優(yōu)化算法在實(shí)現(xiàn)過(guò)程中的隨機(jī)性，使得大多都存在優(yōu)化算法易陷入局部最優(yōu)解、收斂速度慢、建立路徑優(yōu)化模型時(shí)考慮影響因素不全面等問(wèn)題。為了優(yōu)化路徑擇優(yōu)模型，提高算法收斂速度和精確度，本文通過(guò)對(duì)卡車工作過(guò)程中行駛路面狀況進(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 問(wèn)題描述與模型建立

1.1 問(wèn)題描述

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

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

1.2 模型建立

露天煤礦運(yùn)輸路徑優(yōu)化問(wèn)題可描述為：在露天煤礦運(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)過(guò)各弧段消耗的運(yùn)輸功所組成的矩陣。

1.2.1影響因素分析

影響卡車做功的因素眾多，但路面質(zhì)量以及路段坡度對(duì)卡車行駛消耗的程度不可忽視。路面質(zhì)量的好壞直接影響著卡車克服滾動(dòng)阻力所做功的大小，路段坡度越大卡車克服坡度阻力做功越大。以卡車重載經(jīng)過(guò)之后路面留下車轍程度為評(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)輸功的加和，而卡車在行駛過(guò)程中總運(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í)際長(zhǎng)度，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)輸路徑無(wú)關(guān)，由于卡車選擇最優(yōu)路徑之前已確定好裝載點(diǎn)與卸載點(diǎn)的位置，因此，所選路徑集中，重力做功相同，在建立最小運(yùn)輸功模型時(shí)可略去重力做功以簡(jiǎn)化模型，僅比較克服阻力做功即能選出最優(yōu)路徑。

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

(4)

2 布谷鳥搜索算法

劍橋大學(xué)YANG X S和Suash Deb教授通過(guò)觀察某些種屬布谷鳥的寄生性育雛行為，并發(fā)現(xiàn)將其行為轉(zhuǎn)化為數(shù)學(xué)方式可有效求解最優(yōu)化問(wèn)題，于是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)化問(wèn)題[10]。

CS算法的主要思想是種屬布谷鳥類的巢穴寄生行為以及其獨(dú)有的冪律規(guī)律萊維飛行行為。在應(yīng)用CS算法求解工程實(shí)例問(wèn)題時(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è)解，算法迭代過(guò)程中的目標(biāo)是利用優(yōu)質(zhì)解替換掉劣質(zhì)解。當(dāng)采用局部隨機(jī)游走更新方式表示見式(5)：

?——步長(zhǎng)縮放因子；

S——步長(zhǎng)；

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

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

Pa——概率；

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

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

(6)

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

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

通過(guò)式(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.通過(guò)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ù)較少、步驟簡(jiǎn)單、容易實(shí)現(xiàn)等優(yōu)點(diǎn)，有著較好的全局搜索能力。眾多學(xué)者研究并在實(shí)例中應(yīng)用后表明布谷鳥搜索算法是非常有效的[11-12]。在應(yīng)用布谷鳥算法求解露天煤礦最優(yōu)化問(wèn)題時(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，步長(zhǎng)縮放因子?=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)場(chǎng)實(shí)際的運(yùn)輸路徑；編號(hào)2、3、7、8的現(xiàn)場(chǎng)實(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算法迭代過(guò)程如圖3所示。

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

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

圖3 CS算法迭代過(guò)程

4 結(jié)語(yǔ)

本文將卡車行駛過(guò)程中克服重力做功與克服阻力做功之和作為卡車消耗總運(yùn)輸功，以最小化總運(yùn)輸功為目標(biāo)建立了露天煤礦卡車運(yùn)輸路徑優(yōu)化模型。在給定起始節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)后，以布谷鳥搜索算法搜尋卡車行駛最優(yōu)路徑，結(jié)合寶日希勒露天煤礦現(xiàn)場(chǎng)實(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à)值。