基于改進(jìn)RRT算法的露天礦路徑優(yōu)化模型

黃金彪，白潤才，劉 威，柴森霖，劉光偉

(1. 遼寧工程技術(shù)大學(xué) 礦業(yè)學(xué)院，遼寧 阜新 123000；2. 寧夏煤炭基本建設(shè)有限公司，寧夏 銀川 750004；3. 遼寧工程技術(shù)大學(xué) 遼寧省高等學(xué)校礦產(chǎn)資源開發(fā)利用技術(shù)及裝備研究院，遼寧 阜新 123000；4. 遼寧工程技術(shù)大學(xué) 理學(xué)院，遼寧 阜新 123000；5. 鹽城工學(xué)院 經(jīng)濟(jì)管理學(xué)院,江蘇 鹽城 224051)

露天礦道路運(yùn)輸系統(tǒng)優(yōu)化問題一直是礦山系統(tǒng)工程及規(guī)劃、優(yōu)化建模所需要重點(diǎn)考慮的關(guān)鍵問題之一，對于提高露天礦的產(chǎn)量規(guī)模、作業(yè)效率具有重要意義[1-4]。特別是，隨著部分礦山產(chǎn)量規(guī)模及作業(yè)設(shè)備的逐步大型化，運(yùn)輸系統(tǒng)對于剝、采、排各系統(tǒng)的銜接紐帶作用逐步凸顯，原本靜態(tài)的道路優(yōu)化及路徑規(guī)劃方法難以應(yīng)付復(fù)雜條件下的優(yōu)化、規(guī)劃任務(wù)。因此，嘗試采用特定的優(yōu)化、規(guī)劃模型對露天礦運(yùn)輸?shù)缆芳皩絾栴}進(jìn)行有效求解，對于提高礦山產(chǎn)能及效率、優(yōu)化現(xiàn)場生產(chǎn)調(diào)度流程將具有切實(shí)意義。

目前，國內(nèi)外學(xué)者對于運(yùn)輸線路及運(yùn)輸系統(tǒng)規(guī)劃問題研究主要集中于2類：① 為對礦山初始運(yùn)輸溝道的開拓定線及既有坑線的動(dòng)態(tài)更新算法的研究，如余鼎[5]針對于山坡露天礦的特殊地理地形條件，提出山坡型露天礦開拓定線的具體方法；朱明海[6]結(jié)合廠礦道路規(guī)范內(nèi)容要求提出了三維選線方法；劉光偉等[7-8]在時(shí)變運(yùn)輸功框架下，結(jié)合時(shí)空拓?fù)渑袆e地方提出了全新的道路選線及線路更新判別算法；DIAZ等[9]從露天煤礦運(yùn)輸系統(tǒng)布置過程中的波動(dòng)變化入手，提出了一種用于自動(dòng)更新靜態(tài)道路網(wǎng)絡(luò)基有向圖的新方法；② 為基于既有坑線形態(tài)及道路運(yùn)輸網(wǎng)絡(luò)圖進(jìn)行尋徑算法設(shè)計(jì)，此類研究的經(jīng)典求解算法為以張幼蒂教授引入的有向圖理論[2]及其發(fā)展模型為代表，如WHITE和OLSON[10]在靜態(tài)有向圖的基礎(chǔ)上，基于場內(nèi)等效距離全局最優(yōu)化為目標(biāo)，建立路徑規(guī)劃模型；HU[11]采用和聲搜索算法設(shè)計(jì)了露天礦路徑優(yōu)化算法；LI等[12]提出了一種兼顧設(shè)備作業(yè)和時(shí)效性成本最小化的車輛線路優(yōu)化策略；柴森霖等[13-15]在傳統(tǒng)有向圖規(guī)劃建模的基礎(chǔ)上，將時(shí)變運(yùn)輸功與時(shí)空拓?fù)溥B通性的方法引入到優(yōu)化建模中，提出了路徑規(guī)劃及運(yùn)輸系統(tǒng)費(fèi)用建模的全新方法。

近年來，隨著人工智能、深度學(xué)習(xí)以及最優(yōu)化理論方法的快速發(fā)展，國內(nèi)外學(xué)者在機(jī)器人避障、運(yùn)動(dòng)學(xué)規(guī)劃等多方面提出了大量效果顯著成果，其中頗具代表性的算法如：張衛(wèi)波等[16]在考慮存在大量復(fù)雜障礙物避障問題的前提下，基于改進(jìn)搜索策略構(gòu)建了智能機(jī)器人快速尋徑算法；張玉偉等[17]基于啟發(fā)式策略對RRT*算法的尋徑策略進(jìn)行了啟發(fā)式修正；鄒啟杰等[18]基于強(qiáng)化學(xué)習(xí)框架驅(qū)動(dòng)，提出了一種未知環(huán)境下機(jī)器人快速盲尋路徑的規(guī)劃算法。雖然上述方法在其領(lǐng)域范圍內(nèi)的實(shí)際應(yīng)用情景中，均給出了自身運(yùn)動(dòng)規(guī)劃過程的理想化解決方案，但由于露天礦山場景的獨(dú)特性及其尋徑策略間存在主、客觀因素的自耦合現(xiàn)象，導(dǎo)致現(xiàn)有的此類優(yōu)秀算法均無法被直接應(yīng)用于指導(dǎo)礦山實(shí)際生產(chǎn)。

鑒于對露天礦尋徑算法設(shè)計(jì)重要性的考量，筆者在前述成果的基礎(chǔ)上，為進(jìn)一步彌補(bǔ)現(xiàn)有算法在目標(biāo)函數(shù)建模、執(zhí)行效率等方面的局限問題，將改進(jìn)RRT算法引入到求解露天礦路徑規(guī)劃問題中，嘗試?yán)肦RT算法的檢索能力擴(kuò)展尋徑算法的備選路徑解，從而進(jìn)一步實(shí)現(xiàn)路徑連通性計(jì)算與目標(biāo)函數(shù)指標(biāo)值計(jì)算的分離；另外，考慮到路面受到重載卡車頻繁碾壓及周期性養(yǎng)護(hù)作用，對現(xiàn)有的時(shí)變運(yùn)輸功模型[13,15]進(jìn)行改進(jìn)，建立全局時(shí)變成本的綜合評價(jià)模型并將其作為規(guī)劃模型的目標(biāo)函數(shù)，給出了路面條件浮動(dòng)狀態(tài)的下評價(jià)模型估計(jì)方法，并最終結(jié)合改進(jìn)的RRT算法實(shí)現(xiàn)對露天礦運(yùn)輸線路規(guī)劃問題的快速求解。結(jié)合現(xiàn)場數(shù)據(jù)仿真實(shí)驗(yàn)，論證了文中算法對于解決露天礦運(yùn)輸線路規(guī)劃、優(yōu)化問題現(xiàn)實(shí)可行且有效。

1 RRT算法基本原理

快速搜索隨機(jī)樹算法(Rapidly-exploring Random Tree，RRT)是美國愛荷華州立大學(xué)的LAVALLE教授于1998年提出，是一種通過增量采樣進(jìn)行隨機(jī)構(gòu)建空間填充樹的高效搜索算法，由于其算法自身的索引邏輯及特性對于提升非凸、高維空間的搜索效率具有極好的適應(yīng)性，且無需提前對搜索區(qū)域的環(huán)境狀態(tài)進(jìn)行系統(tǒng)化建?；蛱厥獾淖R(shí)別及幾何劃分，便可實(shí)現(xiàn)對存在代數(shù)約束(存在移動(dòng)障礙的環(huán)境)或微分約束(局部動(dòng)態(tài)或全局動(dòng)態(tài)環(huán)境)的高維空間進(jìn)行高效搜索，而被廣泛應(yīng)用于機(jī)器人避障、運(yùn)動(dòng)規(guī)劃等相關(guān)問題的求解過程中。

對于經(jīng)典RRT算法的執(zhí)行邏輯原理如圖1所示，其偽代碼見表1。

圖1 RRT算法基本原理

表1 經(jīng)典RRT算法偽代碼

表1算法中參數(shù)、方法定義及執(zhí)行流程如下：Q為場景圖，即道路網(wǎng)絡(luò)圖；qinit為選線起始位置節(jié)點(diǎn)；qgoal為選線目標(biāo)位置節(jié)點(diǎn)；n為有向圖中節(jié)點(diǎn)數(shù)量；R為最終搜索到的目標(biāo)路徑；r搜索路徑的節(jié)點(diǎn)及有向邊集合；rinit()為初始化備選路徑的節(jié)點(diǎn)和有向邊的方法。算法從qinit開始，循環(huán)遍歷n個(gè)節(jié)點(diǎn)，其中i為當(dāng)前遍歷節(jié)點(diǎn)的索引。在遍歷循環(huán)中，通過隨機(jī)散布qrandom節(jié)點(diǎn)構(gòu)造備選節(jié)點(diǎn)集，并通過查找距離qrandom節(jié)點(diǎn)最近的qnear節(jié)點(diǎn)來確定算法前進(jìn)方向，前進(jìn)方向上以step為前進(jìn)步長，從而生產(chǎn)qnew節(jié)點(diǎn)。當(dāng)具備qnew節(jié)點(diǎn)條件后，算法以qnew,qnear節(jié)點(diǎn)構(gòu)建有向邊，并最終通過CollisionFree方法判斷當(dāng)前路徑是否可行，如可行，則確立當(dāng)前路徑，直至最終到達(dá)目標(biāo)節(jié)點(diǎn)為止。

2 露天礦路徑優(yōu)化問題建模

2.1 模型的參、變量定義

為表述模型方便，現(xiàn)對模型中的參變量做如下定義。

(1)有向圖參、變量定義：Ω={1,2,…,n}為道路網(wǎng)絡(luò)有向圖中的非空節(jié)點(diǎn)集合；ei,j=(i,j)∈E，為道路網(wǎng)絡(luò)有向圖中的非空節(jié)點(diǎn)i，j間的有向邊，i,j∈Ω。其中，E為圖中有向邊集合。

(3)規(guī)劃模型的決策變量：xi為有向邊是否為最優(yōu)路徑的可行解。

2.2 約束條件

計(jì)算模型是對現(xiàn)實(shí)工程場景的合理抽象，故對于場景內(nèi)的部分特殊的礦山工程條件，則需通過特定的指標(biāo)值約束來進(jìn)行有效表達(dá)。為進(jìn)一步保證模型的合理性及完整性，筆者對模型中的數(shù)值型指標(biāo)約束進(jìn)行如下分類。

(1)道路網(wǎng)絡(luò)圖中任意單一有向邊上的車流密度約束。

(1)

(2)

(2)道路網(wǎng)絡(luò)飽和狀態(tài)下全路徑車流密度約束。

(3)

(4)

(3)尋徑?jīng)Q策階段的道路通過能力約束。

(5)

2.3 目標(biāo)函數(shù)

當(dāng)尋徑算法選擇不同的路段組合時(shí)，不僅會(huì)觸發(fā)線路總長度、提升高度等運(yùn)輸功、能耗屬性的變化，同時(shí)也會(huì)誘發(fā)路面平整度等能耗特征指標(biāo)產(chǎn)生波動(dòng)，加之重型卡車的頻繁碾壓與路面的周期性養(yǎng)護(hù)，會(huì)導(dǎo)致車-路系統(tǒng)間形成內(nèi)蘊(yùn)的耦合聯(lián)系，并進(jìn)一步促進(jìn)功、能關(guān)系產(chǎn)生極為明顯的時(shí)間效應(yīng)[13-15]。鑒于對上述因素的綜合考量，在尋徑算法的規(guī)劃建模中，以差異路段及周期性道路養(yǎng)護(hù)作用下的路面平整度分析為切入點(diǎn)，結(jié)合對路面平整度時(shí)效性變化的擾動(dòng)分析，建立全局時(shí)變成本綜合評價(jià)模型，并將綜合評價(jià)模型確立為優(yōu)化問題的全局目標(biāo)函數(shù)，具體評價(jià)模型為

Q(t)=k1U(t)+k2C(φ)

(6)

式中，Q(t)為具有時(shí)間效應(yīng)的綜合評價(jià)模型；U(t)為時(shí)變運(yùn)輸功函數(shù)，表達(dá)形式如式(7)所示；k1為評價(jià)模型的能耗折算系數(shù)；C(φ)為以時(shí)變阻力系數(shù)的隸屬度函數(shù)為參數(shù)的路面養(yǎng)護(hù)費(fèi)用及成本估計(jì)函數(shù)；φ為分類型時(shí)變道路阻力系數(shù)(f(t))的隸屬度函數(shù)；k2為路面養(yǎng)護(hù)費(fèi)用函數(shù)的折算系數(shù)。

(7)

式中，F(xiàn)ei,j為有向圖中任意有向邊上的時(shí)變阻力的估計(jì)值。

2.4 模型中的波動(dòng)參數(shù)估計(jì)

對比式(6)，(7)兩組模型可知，模型中的未知參數(shù)主要分為：①k1，k2為2個(gè)未知參數(shù)；②U(t)，C(φ)均為未知估計(jì)。其中，k1，k2均為折算系數(shù)，為計(jì)算這部分折算系數(shù)及2組未知函數(shù)的估算結(jié)果，以神華新疆公司紅沙泉露天煤礦為例，通過利用該礦部分生產(chǎn)運(yùn)營數(shù)據(jù)及相關(guān)數(shù)理統(tǒng)計(jì)進(jìn)行分析。從統(tǒng)計(jì)結(jié)果來看，對比U和C兩組函數(shù)均勻滾動(dòng)阻力的發(fā)展存在正向相關(guān)性，并通過對比該礦近4個(gè)月內(nèi)會(huì)計(jì)統(tǒng)計(jì)出的噸公里運(yùn)輸及養(yǎng)護(hù)費(fèi)用結(jié)果，將最終評價(jià)函數(shù)Q的線性權(quán)重指標(biāo)定為k1=k2=0.5。

考慮到綜合評價(jià)模型Q(t)主要包括U(t)(時(shí)變運(yùn)輸功函數(shù))和C(φ)(浮動(dòng)線路條件下的路面養(yǎng)護(hù)費(fèi)用及成本估計(jì)函數(shù))2個(gè)部分。其中，對于時(shí)變運(yùn)輸功函數(shù)，筆者團(tuán)隊(duì)曾給出具體的函數(shù)估計(jì)方法[13]。在前述成果介紹方法的基礎(chǔ)上，以紅沙泉露天煤礦生產(chǎn)運(yùn)營數(shù)據(jù)為例，直接給出時(shí)變阻力系數(shù)的估算過程。其中，根據(jù)紅沙泉露天礦測試路段的阻力特征變化分析結(jié)果，研究中將該礦測試研究路段共劃分為4組不同類型路面，宏觀路面特征描述及阻力系數(shù)變化范圍數(shù)據(jù)見表2。

表2 紅沙泉露天煤礦不同路面條件下的滾動(dòng)阻力系數(shù)分類

當(dāng)具備路面類型的分類基準(zhǔn)后，采用趨勢估計(jì)及最小二乘方法，建立不同路面類型下的滾動(dòng)阻力系數(shù)隨養(yǎng)護(hù)時(shí)間及累計(jì)物料量間的趨勢面估計(jì)，具體的估計(jì)結(jié)果如圖2所示。

圖2 不同特征路面上的阻力系數(shù)估計(jì)結(jié)果

對于上述滾動(dòng)阻力系數(shù)的精準(zhǔn)估計(jì)是時(shí)變運(yùn)輸功計(jì)算及養(yǎng)護(hù)成本估計(jì)的重要基礎(chǔ)，當(dāng)給定任意時(shí)段的滾動(dòng)阻力系數(shù)的估計(jì)函數(shù)形式后，按照前述方法其運(yùn)輸功計(jì)算則相對簡單，但對于路面養(yǎng)護(hù)則容易因超載重車頻繁碾壓、集中降雨以及養(yǎng)護(hù)不及時(shí)等問題，極易誘發(fā)路面養(yǎng)護(hù)成本出現(xiàn)2次波動(dòng)。為保證在養(yǎng)護(hù)成本計(jì)算過程中，可以對上述偶發(fā)性問題進(jìn)行有效評估，以該礦采場南側(cè)端幫不同水平上的2條平直運(yùn)輸干線為測試區(qū)域(S1線全長2.78 km，S2線全長2.64 km)，分別進(jìn)行差異環(huán)境下的道路養(yǎng)護(hù)成本測試，以期構(gòu)造出全局合理的養(yǎng)護(hù)費(fèi)用成本估計(jì)。

2.4.1均衡路面條件下的養(yǎng)護(hù)成本估計(jì)

對于所述的均衡路面條件是指預(yù)先設(shè)計(jì)的運(yùn)輸?shù)缆吩谟?jì)劃場景中被使用，且以路面平整度范圍指標(biāo)為基礎(chǔ)嚴(yán)格按照養(yǎng)護(hù)周期執(zhí)行對應(yīng)養(yǎng)護(hù)的部分路面。為保證上述條件，研究中以該礦南端幫干線S1為例，對生產(chǎn)運(yùn)營期間該路段進(jìn)行均衡路面條件養(yǎng)護(hù)，并排除場內(nèi)的部分偶發(fā)擾動(dòng)因素，如雨雪天氣、超重超負(fù)荷運(yùn)載等現(xiàn)象，在此基礎(chǔ)上對不同狀態(tài)下養(yǎng)護(hù)費(fèi)用進(jìn)行合理估計(jì)及分析。

(1)常規(guī)路面平整養(yǎng)護(hù)狀態(tài)下的成本估計(jì)。平路機(jī)在作業(yè)線路上的隨機(jī)平整屬于常規(guī)路面養(yǎng)護(hù)，通常此類作業(yè)相對較為頻繁，平均每組線路的養(yǎng)護(hù)周期均值一般在24～28 h。為有效描述此種作業(yè)條件下的成本變化趨勢，研究中對累計(jì)物料量、養(yǎng)護(hù)間隔時(shí)間以及等效距離等指標(biāo)分別進(jìn)行相關(guān)性測試，通過對比3組不同時(shí)間段上的干線S1上的采樣數(shù)據(jù)，發(fā)現(xiàn)養(yǎng)護(hù)費(fèi)用僅與等效距離間存在近似線性關(guān)系，且這種線性關(guān)系無法擬合累計(jì)物料量及養(yǎng)護(hù)周期等指標(biāo)。其中，基于60組采樣數(shù)據(jù)所構(gòu)建出的線性擬合結(jié)果如圖3所示。

圖3 路面養(yǎng)護(hù)費(fèi)用與等效距離間的線性擬合關(guān)系

由于上述存在線性表達(dá)，故對于常規(guī)路面平整養(yǎng)護(hù)狀態(tài)下的成本估計(jì)均采用等效距離的線性估計(jì)來處理，其成本估計(jì)模型如式(8)所示。

Cnormal=χLeq+b

(8)

式中，Cnormal為成本估計(jì)值；χ為養(yǎng)護(hù)費(fèi)用的等效距離折算系數(shù)；Leq為待養(yǎng)護(hù)線路的等效距離，km；b為費(fèi)用的軸向截距。

(2)破損路面修整狀態(tài)下的成本估計(jì)?；谏鲜龇治龇椒ǎ瑢τ谄茡p路面上的養(yǎng)護(hù)成本估算，通過與養(yǎng)護(hù)成本間的多因素套合分析發(fā)現(xiàn)，修正破損路面的費(fèi)用模型仍可利用線性模型來表征，僅線性模型中的ε截距項(xiàng)變?yōu)楦?dòng)變量，且通過多組對比分析發(fā)現(xiàn)，其浮動(dòng)狀態(tài)及指標(biāo)變化規(guī)律與全路面的平均滾動(dòng)阻力系數(shù)的3次多項(xiàng)式曲線具有較好的擬合特性。為有效論證上述浮動(dòng)截距與全路面的平均滾動(dòng)阻力系數(shù)間的3次特性，研究中共采集了測試干線上不同時(shí)段內(nèi)的多組滾動(dòng)阻力及浮動(dòng)截距數(shù)據(jù)進(jìn)行擬合，其中采用3次多項(xiàng)式擬合出的2組干線上的曲線結(jié)果如圖4所示。

圖4 浮動(dòng)截距的3次擬合曲線

通過上述分析，可知均衡路面條件下的養(yǎng)護(hù)費(fèi)用與運(yùn)輸線路的等效距離間存在明顯的線性關(guān)系，這也很好的解釋了部分場景中可以通過等效距離進(jìn)行費(fèi)用整體費(fèi)用描述的主要原因。

2.4.2非均衡路面條件下的養(yǎng)護(hù)成本估計(jì)

非均衡路面與均衡路面條件下的成本估計(jì)問題存在著本質(zhì)上的不同，原因在于非均衡路面受多種綜合誘因控制而產(chǎn)生養(yǎng)護(hù)成本偶發(fā)性波動(dòng)，在這種情況下，養(yǎng)護(hù)費(fèi)用將不再與等效距離間存在簡單的線性相關(guān)性。因此，為進(jìn)一步確定該狀態(tài)下的養(yǎng)護(hù)成本，研究中以因子分析法、統(tǒng)計(jì)學(xué)習(xí)方法建立各主控分項(xiàng)作用下的最佳成本估計(jì)。具體方法如下：

(1)識(shí)別成本波動(dòng)的主控誘因。為確定出非均衡路面條件下的成本波動(dòng)控制因素，研究中將統(tǒng)計(jì)數(shù)據(jù)中的主控要素重點(diǎn)分為5組，具體指標(biāo)如圖5所示，其中，0.1，0.2，…，0.5為相關(guān)系數(shù)。并以上述主控指標(biāo)為依據(jù)，結(jié)合論文現(xiàn)有測試線路確定出5種綜合誘因。

圖5 分類型引誘條件下的主控因素作用

(2)非主控誘因的非均衡路面成本估計(jì)。當(dāng)識(shí)別出主控成本波動(dòng)誘因后，5種誘因形成對波動(dòng)函數(shù)的綜合作用，且作用函數(shù)待估計(jì)，且函數(shù)形態(tài)未知。為進(jìn)一步提高此類估計(jì)過程的精度，研究中嘗試采用SVR(支持向量非線性回歸模型，Support Vector Regression)進(jìn)行回歸建模，基于最小二乘思想，同時(shí)考慮在希爾伯特空間內(nèi)多元回歸問題具有線性可分特性，故對于任意擬合點(diǎn)均可嘗試擬合基于y=ωTx的線性表達(dá)，故其具有損失的目標(biāo)函數(shù)均可按照式(9)，(10)中函數(shù)形態(tài)進(jìn)行建模。

(9)

s.t.δi=ωTφ(xi)+η-yi,i=1,2,…，N

(10)

式中，ω為權(quán)系數(shù)向量；φ(xi)為輸入?yún)?shù)到希爾伯特空間的映射；x為對主探誘因進(jìn)行量化后的指標(biāo)向量；C為懲罰因子；η為模型偏差；λ為誤差權(quán)重向量；λi為向量中的一個(gè)值。

當(dāng)具備全局目標(biāo)函數(shù)后，多元回歸問題則轉(zhuǎn)化為在希爾伯特空間線性可分的最優(yōu)化問題，對應(yīng)指標(biāo)值的求解則可通過智能優(yōu)化算法(如遺傳算法、蟻群算法等)進(jìn)行迭代求解。

3 基于改進(jìn)RRT的路徑優(yōu)化算法

露天礦的路徑優(yōu)化問題與機(jī)器人避障等傳統(tǒng)的運(yùn)動(dòng)學(xué)規(guī)劃問題隨同屬路徑規(guī)劃或?qū)絾栴}，但2者間對于優(yōu)化及規(guī)劃建模則有著本質(zhì)上的差異。其中，避障問題更注重對于場景地圖連通性的判別，且場景地圖一般不可知，存在無現(xiàn)實(shí)可行解的情況；而露天礦尋徑問題的運(yùn)輸網(wǎng)絡(luò)在計(jì)劃階段內(nèi)其圖結(jié)構(gòu)是可知的，且其路徑的可行解定然滿足連通性條件，但解集內(nèi)路徑會(huì)存在明顯的費(fèi)用差異，且費(fèi)用計(jì)算任務(wù)更為繁重。因此，為保證算法在具體尋徑過程中具有更好的效果及效率表現(xiàn)，將改進(jìn)的RRT算法引入到路徑優(yōu)化算法的設(shè)計(jì)過程中，試圖通過RRT算法隨機(jī)特性，為優(yōu)化算法提供啟發(fā)式策略及路徑連通性的判別結(jié)果，最終輔助優(yōu)化算法實(shí)現(xiàn)快速尋徑計(jì)算。

3.1 基于改進(jìn)RRT算法的啟發(fā)式策略

原始的RRT算法在地圖空間內(nèi)多以均勻隨機(jī)采樣策略來完成對尋徑算法的建模，以最大限度的保證算法的避障能力，但對于文中基于改進(jìn)有向圖內(nèi)的尋徑算法設(shè)計(jì)將直接影響算法的執(zhí)行效率。為保證算法可以具有快速拓?fù)浼皟?yōu)化能力，文中從采樣策略及鄰近點(diǎn)選擇2個(gè)方面入手，對RRT算法進(jìn)行改進(jìn)，以期為后續(xù)的遺傳算法快速迭代計(jì)算提供連通性判別依據(jù)。

3.1.1采樣策略修正

在經(jīng)典RRT算法中，對區(qū)域內(nèi)擴(kuò)展點(diǎn)的采樣采用均勻隨機(jī)采樣策略，其優(yōu)點(diǎn)在于可以發(fā)現(xiàn)更多不同類型的路徑來參與碰撞檢測，但也受制于采樣規(guī)模，當(dāng)采樣規(guī)模較大時(shí)，算法迭代效率較低，特別是類似于文中需要頻繁計(jì)算全局的費(fèi)用指標(biāo)的決策過程，經(jīng)典算法無法滿足特定工程背景下的效率需求。

為有效解決上述局限性問題，嘗試引入浮動(dòng)同心圓采樣策略[16-17]，并結(jié)合文中算法的尋徑目標(biāo)對采樣策略的浮動(dòng)策略進(jìn)行修正。其核心思想是嘗試?yán)萌缡?11)所示的圓的極坐標(biāo)方程，以目標(biāo)點(diǎn)為中心、浮動(dòng)半徑ρ向外逐步擴(kuò)展采樣，計(jì)算新的隨機(jī)點(diǎn)坐標(biāo)(xqrandom,yqrandom)。其中，隨機(jī)點(diǎn)(xqrandom,yqrandom)的隨機(jī)采樣位置指導(dǎo)后續(xù)尋徑過程中的采樣方向。

(11)

式中，ρ為同心圓采樣區(qū)域的浮動(dòng)半徑，由后續(xù)鄰近點(diǎn)選擇策略控制；(xqgoal,yqgoal)及(xqrandom,yqrandom)分別為描述目標(biāo)點(diǎn)及隨機(jī)點(diǎn)坐標(biāo)值。

3.1.2鄰近點(diǎn)的選擇

浮動(dòng)同心圓采樣策略雖在一定程度上可以減緩全區(qū)隨機(jī)采樣的枚舉規(guī)模，但由于可以在圓周上全角度的初始化坐標(biāo)角度，則仍存在隨機(jī)采樣規(guī)模不可控的現(xiàn)實(shí)問題。因此，為進(jìn)一步保證采樣范圍可控且路徑前進(jìn)方向不存在回溯問題，文獻(xiàn)[16]利用路徑點(diǎn)夾角特性而非物理距離指標(biāo)進(jìn)行采樣區(qū)域臨近點(diǎn)選擇的具體方法，對啟發(fā)式算法進(jìn)行設(shè)計(jì)。

具體原理如圖6所示，選擇過程為：在規(guī)劃初始階段，算法以起始點(diǎn)為RRT算法隨機(jī)樹r的根節(jié)點(diǎn)，并以該點(diǎn)為基礎(chǔ)采用同心圓采樣策略向外擴(kuò)展隨機(jī)點(diǎn)qrandom。當(dāng)確定隨機(jī)點(diǎn)后，算法首先在浮動(dòng)同心圓內(nèi)搜索有向圖節(jié)點(diǎn)，若在同心圓內(nèi)存在節(jié)點(diǎn)ni，則遍歷r上的所有qi節(jié)點(diǎn)，分別計(jì)算每一組qrandom，qi組成的有向邊與x軸向的夾角，記為φr-i，以及qi，ni組成的有向邊與x軸向間的夾角，記為φn-i，并利用式(12)進(jìn)行判斷，保證每組角度應(yīng)控制在φΔ角度容差范圍內(nèi)；否則，調(diào)整浮動(dòng)同心圓采樣半徑大小。

圖6 鄰近點(diǎn)方向性約束原理

Δ(qrandom,qi,ni)=|φr-i-φn-i|<φΔ

(12)

式中，φΔ為鄰近點(diǎn)角度約束，該角度控制在6°以內(nèi)。

3.2 融合啟發(fā)式策略的尋徑算法設(shè)計(jì)

對于RRT算法的改進(jìn)僅能實(shí)現(xiàn)對備選路徑解連通性的判別，并不能對路徑規(guī)劃模型進(jìn)行求解。因此，為保證尋徑算法可以快速搜索出路網(wǎng)中的全局最優(yōu)解，文中嘗試將連通性的啟發(fā)式計(jì)算策略融合到遺傳編碼過程中，實(shí)現(xiàn)對備選路徑解的啟發(fā)式編碼，并以min[1/Q(t)]為目標(biāo)函數(shù)進(jìn)行最優(yōu)化建模，最終利用遺傳算法迭代出全局最優(yōu)解。具體最優(yōu)化算法設(shè)計(jì)及執(zhí)行邏輯流程如圖7所示，其中G表示遺傳算法種群迭代的次數(shù)。

圖7 改進(jìn)遺傳算法邏輯流程

4 仿真實(shí)驗(yàn)對比分析

為有效驗(yàn)證算法的現(xiàn)實(shí)有效性及性能表現(xiàn)，在前述分析結(jié)果的基礎(chǔ)上，以常規(guī)養(yǎng)護(hù)狀態(tài)、偶發(fā)性的天氣變化以及多類型車型參與運(yùn)輸?shù)惹闆r的分析任務(wù)為基礎(chǔ)，在采場內(nèi)選擇不同的5組路線，分別計(jì)算綜合折算費(fèi)用(運(yùn)輸功轉(zhuǎn)化成本+路面養(yǎng)護(hù)成本)。試驗(yàn)?zāi)Ｐ椭?條線路的初始化條件及指標(biāo)參數(shù)賦值情況如下，其中R1～R5五條線路的平均路面滾動(dòng)阻力系數(shù)分別為0.047 1,0.024 6,0.033 9,0.046 8,0.041 2。遺傳算法試驗(yàn)參數(shù)：算法種群規(guī)模為50；最大進(jìn)化次數(shù)150次；交叉概率0.8，變異概率0.05。實(shí)例運(yùn)輸卡車采用MT5500B，空車質(zhì)量223 t，額定載質(zhì)量326 t，最大載質(zhì)量360 t，平裝容積158 m3，2∶1堆裝218 m3。通過重復(fù)多次優(yōu)化迭代計(jì)算，遺傳算法穩(wěn)定迭代后，費(fèi)用評價(jià)指標(biāo)收斂結(jié)果如圖8所示。

圖8 5組測試數(shù)據(jù)迭代收斂結(jié)果

觀察分析對比圖8中迭代結(jié)果發(fā)現(xiàn)，5組線路經(jīng)150次迭代完成后，均能收斂于全局費(fèi)用最優(yōu)解。其中，均衡路面(R2,R3,R5三組)收斂速度較快，基本在50～60次迭代后既可以搜索到全局最優(yōu)線路，而非均衡路面由于需要頻繁進(jìn)行費(fèi)用成本計(jì)算，迭代速度相對較慢，但在70～80次迭代計(jì)算后，同樣可以獲得不錯(cuò)的全局最優(yōu)解。因此，從該層面看，改進(jìn)算法具有較好的迭代收斂特性。

同時(shí)，為驗(yàn)證算法具有較好的收斂特性，研究中進(jìn)行了多次重復(fù)測試，以驗(yàn)證算法的穩(wěn)定性。其中，20次重復(fù)試驗(yàn)后，算法精度及穩(wěn)定性評價(jià)的平均指標(biāo)統(tǒng)計(jì)見表3。

表3 20組重復(fù)試驗(yàn)對比數(shù)據(jù)

對5組實(shí)例進(jìn)行20次重復(fù)試驗(yàn)后，對比統(tǒng)計(jì)結(jié)果發(fā)現(xiàn)，在R1,R4,R5三組路徑上，重復(fù)迭代20次后，算法均能收斂于最優(yōu)解；而R2,R3兩組在20次測試過程中，均出現(xiàn)一次無法收斂于參考值的現(xiàn)象，但其平均誤差不到1%，對于路徑規(guī)劃露天礦路徑問題影響不大，能滿足露天礦尋徑算法的現(xiàn)實(shí)需求。

5 結(jié) 論

(1)為有效解決傳統(tǒng)模型評價(jià)建模困難、尋徑效率受限等問題，在時(shí)變運(yùn)輸功計(jì)算的基礎(chǔ)上，將車路兩系統(tǒng)產(chǎn)生的能耗費(fèi)用耦合看待，提出了兼顧路面隨機(jī)損傷作用下的尋徑費(fèi)用評價(jià)函數(shù)及路徑規(guī)劃模型，改善了現(xiàn)有運(yùn)輸系統(tǒng)規(guī)劃建模過程中缺失路面損傷成本考量的部分局限性問題。

(2)從智能優(yōu)化算法隨機(jī)初始化備選路徑效率低下的切實(shí)問題出發(fā)，提出了規(guī)劃模型標(biāo)量計(jì)算與拓?fù)溥B通性判別相分離的基本思想，并基于快速搜索隨機(jī)樹算法改進(jìn)了遺傳算法尋徑過程中的遺傳編碼方式，提出了備選路徑拓?fù)溥B通性判別方法。

(3)車輛運(yùn)輸過程中路面變化不但會(huì)引起車輛能耗變化，同時(shí)也會(huì)帶來路面養(yǎng)護(hù)成本的波動(dòng)變化，通過分析不同路面狀態(tài)下的養(yǎng)護(hù)成本波動(dòng)規(guī)律，證實(shí)了傳統(tǒng)基于等效路徑折算的成本組成僅適用于均衡路面條件，真實(shí)礦山生產(chǎn)過程中，路面狀態(tài)常介于均衡與非均衡之間。因此，傳統(tǒng)的費(fèi)用折算方法在精準(zhǔn)估計(jì)時(shí)并不準(zhǔn)確。

(4)通過對比多組重復(fù)實(shí)驗(yàn)及部分尋徑算法，證實(shí)基于車-路耦合思想所構(gòu)建的兼顧路面隨機(jī)損傷作用的費(fèi)用評價(jià)函數(shù)及路徑規(guī)劃模型現(xiàn)實(shí)有效，能作為現(xiàn)有礦山尋徑任務(wù)的替代算法，對于降低礦山運(yùn)輸系統(tǒng)總體能耗、指導(dǎo)礦山生產(chǎn)實(shí)踐及組織協(xié)調(diào)具有重要現(xiàn)實(shí)意義。