露天礦山開拓運輸系統道路選線算法

劉光偉，柴森霖,3，白潤才，趙景昌，李浩然，張 靖

(1.遼寧工程技術大學 礦業學院，遼寧 阜新 123000; 2.遼寧工程技術大學 遼寧省高等學校礦產資源開發利用技術及裝備研究院,遼寧 阜新 123000; 3.鹽城工學院 經濟管理學院，江蘇 鹽城 224051)

露天礦山線路工程是礦山開拓運輸系統建設的重點工程之一，是建立采場、排土場以及地面輔助設施運輸聯系的重要保障，同時也是直接影響剝離物運輸效率、運輸成本的關鍵因素，對于露天礦山降低生產運營成本具有十分現實的經濟意義[1-3]。

目前，關于露天礦山開拓運輸道路選線問題的研究仍十分有限，現有的研究成果多以露天礦設計規范[4-5]中給出的開拓定線原則為基礎，采用人工經驗試錯的方法制定選線方案，最終采用典型方案對比確定最優化線路，如余鼎等[6]根據山坡露天礦的地理、地形條件，提出一種適合山區特殊地質概況的道路選線方法。這種依賴主觀經驗的手工定線方法，其優點在于全程均包含主觀設計，適應性強，方案設計相對更靈活，但也存在極為明顯的局限性，如人工試錯工程量大、精度低、主觀經驗錯誤易造成全局性的錯誤決策。近年來，隨著數據采集手段的發展，孫效玉等[7]針對既有線路提取過程中存在路段缺失、線路偏移等問題，修正了傳統路網采樣過程中存在GPS數據偏移嚴重、路網連通性差等問題，并結合濾波方法和柵格圖像細化算法，提出重新構建道路運輸網絡骨架，實現采樣線路的矢量化重構的新方法，在一定程度上改善了現有運輸系統優化的基礎運輸網絡建設問題。其實，對于前述的這類道路選線問題的研究在高速公路施工選線應用中更為廣泛，如JYH-CHERNG和JONG等[8]基于連續剖面法和遺傳算法提出高速公路選線算法;JHA M K等[9]結合城際高速公路選線問題，提出智能選線計算框架。這類算法的優勢在于自動化程度高、以費用為優化目標、主觀經驗性干預小、能顯著減輕選線的任務量，極大限度地優化道路設計、施工及使用成本。但這類方法在實際礦山應用中也存在一定的局限性，如算法迭代過程中易陷入局部最優、基于隨機特性的尋優策略計算效率低、JONG提出的選線理論會自動舍棄礦山中的折返路徑解等。

筆者在綜合上述研究成果的基礎上，針對城際高速公路選線方法直接應用于礦山道路選線問題時存在的局限性，提出一種考慮折返路徑解的分階段選線剖面布置方法，并結合三維路徑樁點的幾何特性分析、曲線線形約束檢測等方法，構建了一種適用于求解露天礦山選線問題的高效算法;為進一步提高算法的求解效率，筆者對遺傳算法進行了改進，并將生物激勵神經網絡全局激勵、抑制本地駐留的特性引入遺傳算法的基因編碼過程中，來實現啟發式路徑修正。本文以神華新疆準東露天煤礦為研究實例，進行算法仿真實驗，經應用實例驗證，改進后的算法實用可靠，能滿足礦山高效、最優化開拓運輸系統定線的工程需求。

1 選線基礎理論

1.1 分階段的選線剖面布置方法

露天礦山開拓運輸系統定線本質上與公路選線相同，其目標都是在三維空間中選出一條符合運輸條件且在壽命周期內總成本最低的道路中心線，以建立源節點和目標節點間的有效運輸聯系。目前，主流的三維道路選線算法多基于JONG等[8-9]提出的連續剖面選線理論，其原理如圖1所示，即在源節點和目的節點間建立多組連續剖面，通過隨機初始化剖面上的控制點并連線，建立備選道路中心線方案，最終結合群智能算法和費用目標函數進行路徑的優選。

圖1 連續剖面選線算法原理Fig.1 Schematic diagram of continuous profile route selection algorithm

相比于傳統的手工定線方法，JONG提出的選線算法有效提高了選線的效率和精度，但在露天礦山開拓定線的實際應用中卻存在明顯的局限性，這主要表現在此種方法要求路徑的矢量方向應始終一致，即路徑與剖面間有且僅有唯一交點，如圖2(a)所示，這也限制了備選線路徑解中不應包含折返路段。但對于露天礦山運輸道路選線問題，特別是當采場內的開拓運輸線路存在移動坑線時，被布置于工作幫的多條運輸線路極可能存在折返現象，如圖2(b)所示，這將導致直接應用JONG法選線將存在明顯的局限性。

圖2 JONG選線算法的剖面布置形式Fig.2 Profile layout of JONG’s route selection algorithm

為使JONG論證的剖面交點唯一的條件假設對于所有的路徑備選解均成立，文中對JONG算法中的剖面布置形式進行了改進，提出一種分階段的剖面布置形式，具體布置方法如下:

步驟1:首先根據采場內的開采參數，沿臺階垂線方向計算線路的極限投影δ，并按照階段寬度恒大于極限投影δ設置選線剖面，如圖3所示，即保證階段寬度能包住整個折返路段;

步驟2:按照第1階段剖面布置設計路徑骨架樁點。對于如圖2所示的線路形態，其骨架樁點即可布置為如圖3所示的X1～X6藍色多段線節點所示的形式;

圖3 分階段選線剖面布置形式Fig.3 Stage route selection profile layout

步驟3:選取第1階段路徑骨架線中相鄰節點，分別構建第2階段選線剖面，如圖3所示的X3～X4區間內的虛線所示;

步驟4:在第2階段選線剖面上初始化路徑樁點，如圖3中黃色樁點所示，即可在滿足假設條件下逼近所有路徑解。

1.2 分階段三維路徑節點代數化表達

上述選線剖面的布置方式描述了線路樁點的幾何形態組成，但卻無法對各樁點具體的幾何位置進行有效表達。因此，為實現對線路中幾何約束的代數化運算，以各剖面為單位構造獨立的坐標系統，并利用坐標系統中心點間的位置關系來建立各樁點之間的位置聯系。其計算步驟如下:假設圖1中線路已知起點、終點分別為A(xA,yA,zA),B(xB,yB,zB)，各干線剖面的直角坐標系原點為Oi(xB,yB,zB)，兩者之間聯系可以采用單位向量的方式來表達，故源節點和目的節點間的單位向量可表示為

(1)

故按照式(1)中所示的單位向量，各坐標系之間的關系可表示為

(2)

則每個干線樁點在各自坐標系中的位置坐標可表示為

(3)

式中，di為Pi至Oi的歐式距離;θ為向量OiPi與X軸正方向的夾角，θ∈[0,π]。

考慮剖面存在兩個階段的嵌套布置，故在剖面階段內仍可采用與式(1)～(3)相類似的坐標嵌套，故可推導出分階段的剖面內部的樁點位置坐標，其階段內單位向量可表示為

(4)

階段內嵌套后的坐標系關系則可表示為

(5)

全路徑的樁點坐標則可以表示為

(6)

式中，d′i為節點P′i與O′i的歐式距離;γ為在以O′i為原點的坐標系下，向量O′iP′i與X軸正方向的夾角，γ∈[0,π]。

1.3 曲線設計與約束檢驗

由上述樁點序列坐標連接而成的備選路徑中心線,其實質上均為存在曲率突變的參考路徑解。但是，按照此種方式構造出的備選路徑解是存在行車安全隱患的。通常，為消除這種曲率突變隱患，使道路行車安全、平順，手工選線方法會在主觀選定中心線的局部位置進行元素設計，以保證各區間路徑滿足相應的道路規范要求。因此，為保證算法虛擬出的路徑能滿足后期主觀線形修正的要求，筆者按照《廠礦道路規范》[4]中給出的道路線形指標(具體參數見表1)，利用相鄰樁點屬性建立每一個幾何特性突變點的檢驗判據，從而為后續算法對路徑的判別檢驗提供基礎。

1.3.1平曲線約束檢驗

平曲線設計的首要任務是在滿足安全視距條件下，進行合理的轉彎半徑設計，最大限度地提高轉彎路段的行車安全性[4-5]。通常，在手工定線過程中，此部分設計需要在滿足最小曲線半徑的前提下，尋求安全性和運輸經濟性間的一個有效折中，即設計的半徑過小，運距短有利于運輸經濟性，但視距短、清障工程量大、存在安全隱患、行車速度受限、需外側設置超高;而轉彎半徑設計過大，則運距長、不利于運輸經濟性，但視野開闊、行車速度快、有利于行車安全及道路平順性。由于優化選線算法可將運輸經濟性轉換為對應的優化問題，因此該部分只關注線形約束，并考慮平曲線的曲線半徑，可通過曲線上任意3點來計算，本文采用相鄰樁點坐標建立最小轉彎半徑判據:

表1 曲線設計參數
Table 1 Curve design parameters

參數道路等級ⅠⅡⅢ設計行車速度/(km·h-1)403020平曲線半徑/m45(60)25(40)15(25)豎曲線半徑/m凸1 000500300凹500400300最大縱坡/%789坡長限制/m≤500≤350≤250坡長換算系數/m1.62.33.2停車視距/m503020

(7)

(8)

式中，Rmin為平曲線的最小曲線半徑;Ri為任意3點計算的平曲線曲線半徑。

1.3.2豎曲線約束檢驗

礦山卡車運輸線路設計的另一個關鍵環節為豎曲線設計，這主要是因為重型卡車在縱坡下行時，極易造成事故及車輛故障，豎曲線設計的質量直接影響著行車安全性及運輸平順性。因此，為避免線路中存在極限縱坡及頻繁連續下坡，豎曲線設計應滿足兩方面的約束限制:

(1)最大縱向坡度限制。為保證備選路徑在相鄰樁點間能夠滿足最大縱向坡度要求，對相鄰路段的最大縱向坡度做如下限制:

gmax≥gi=|zi+1-zi|/dg(i)

(9)

式中，gmax為最大縱向坡度;dg(i)為坡度計算出的坡面間隔距離;zi+1-zi為相鄰兩線路節點的高程值。

(2)緩坡段的長度限制。為確保設計的線路能夠滿足充足視距以及運輸平順性的要求，避免車輛因縱向爬坡或下坡，而導致制動系統安全隱患及零部件損耗對緩坡段極限長度進行了約束，其長度約束如式(10)～(11)所示。

緩坡段長度上限:

(10)

緩坡段長度下限:

(11)

式中，L為豎曲線長度;S為停車距離;A為坡度差值;h1為視線高度;h2為障礙物平均高度。

1.4 線路費用成本模型

對于礦山道路的費用成本分析是指對在經濟有效期內發生的所有與道路相關的全部資源代價投入的經濟分析折算[4-5,10]，主要成本費用包括道路的建設費用和使用費用兩部分。基于上述考慮，筆者將成本費用分為如下3種類型，并結合索引柵格技術，將模型中的位置信息、單元費用成本等屬性進行關聯，建立費用柵格地圖，從而實現算法對給定線路費用成本的有效表達和快速索引。

(1)筑路費用成本(KP):主要包括鑿巖爆破費用Kp、土巖結構穩定性維護折算費用Ks、構筑物移設折算費用Kd。

(12)

(2)道路使用成本費用(Ku):主要包括因道路使用而產生的道路構筑、變更、路面管理、設備維護和管理等費用以及因特殊交通狀況而引起的附加費用。

Ku=ktLn+G(ρ)

(13)

(14)

式中，kt為卡車的壽命周期內單位公里費用折算;ρ為車流密度;G(ρ)為關于車流密度對運輸系統管理、調度和經濟效益影響的非線性表達，取正為抑制生產效益，反之增強;Ti，Ci+1為曲線相鄰切點。

(3)土石方量工程費用(Kv):包括因填、挖方而產生的工程費用和運輸費用。

(15)

綜上所述，選線道路的生命周期內總體費用成本可表示為

C=KP+Ku+Kv

(16)

2 基于IGA模型的開拓定線算法設計

2.1 改進遺傳算法(IGA)設計

采用改進遺傳算法[11-12]用于道路選線設計，本質上是一類在技術可行的道路布設方案中逼近預期費用目標最優化的數學規劃問題，該規劃問題建立在選線方案的費用成本最小目標之上，故其優化問題的目標函數可定義為

minC=Kp+Ku+Kv

(17)

在確立優化目標后，遺傳算法將模擬“優勝劣汰”的生物進化模式，在問題潛在可行解中逼近現實路徑最優解。為描述潛在可行解在尋優場景中適應性，采用式(18)作為基因個體的適應度評估函數，以保證生物選擇能按照優化目標方向擇優選擇。

(18)

式中，M為適應度函數的鎮定系數，其作用是防止當C極大時f(x)趨近于0而導致算法無法決策。

種群初始化主要通過在剖面位置隨機選點以建立空間節點與基因編碼之間的坐標映射，其中各路徑的基因編碼形式為

Γ=[γ1,γ2,γ3,…,γ3n-2,γ3n-1,γ3n]=

[x1,y1,z1,…,xn,yn,zn]

(19)

在上述種群初始化時，可行域內解的規模有限且缺乏節點位置的曲線設計，為進一步增強種群多樣性、實現隱患節點的判別，文中對遺傳算法進行了改進，主要包括3個方面:① 采用隨機交叉和變異的方式以增強種群的多樣性;② 采用基因位和基因段的變異以增強優秀個體多樣性，避免陷入“過早熟”現象;③ 采用精英選擇結合輪盤賭的方式，實現優秀種群個體的快速篩選。改進算法的設計流程如圖4所示。

圖4 IGA算法流程Fig.4 IGA algorithm flow

2.2 對比試驗

由圖4算法設計流程可知，上述遺傳算法改進的基本思想即為通過改進種群多樣性來增加搜索出最優解的概率。為進一步說明改進遺傳算法的實際效果，筆者從種群基因個體的近似程度、收斂效率以及曲線的梯度趨勢等幾個方面考慮，分別采用普通遺傳算法和文中改進遺傳算法，設計對比實驗來驗證優化算法的有效性，并繪制種群各代基因相似度曲線如圖5所示。

圖5 種群基因相似度Fig.5 Population genetic similarity

由對比上述種群算法的迭代過程中的基因相似度可知，改進的遺傳算法能大幅度提高迭代初期的種群多樣性，后期種群個體差異性逐漸穩定，能有效提高算法逼近現實最優解的概率。

為進一步說明IGA算法的優化效果，文中在同一工程位置上分別采用兩種算法進行仿真模擬，并繪制成本費用曲線如圖6所示。

圖6 GA與IGA算法費用成本對比Fig.6 Algorithm cost comparison for GA and IGA

通過對比圖6中兩組算法模擬的成本費用，可以看出GA算法搜索出的最優解并非全局最優解，且隨算法迭代過程，頻繁存在局部最優現象，且迭代效率也不如改進算法明顯。

2.3 基于生物激勵的啟發式算法改進

綜合上述分析和重復多次上述對比實驗可發現，改進的遺傳算法雖在一定程度上改進了種群多樣性，但仍存在求解效率低、求解過程不穩定、易陷入局部最優解等問題，為有效提高算法的收斂效率和尋優能力，筆者將生物啟發神經網絡模型引入改進遺傳算法中，試圖通過其在線學習能力對算法進行啟發式改進基因個體質量，從而最大程度上優化尋優過程。

2.3.1生物激勵神經網絡(Bio-Inspired NN)

生物激勵神經網絡(Biologically Inspired Neural Network)是1998年由Yang和Meng在Grossberg的生物分流模型基礎上，為解決機器人動態尋徑問題，提出的一種自適應的神經網絡。因其網絡模型中結構簡單、計算任務量小、具有極強的自組織適應能力及連續光滑的有界輸出，被廣泛應用在機器人的三維路徑規劃、避障控制以及軌跡跟蹤等時變動力學控制系統中，其網絡的二維結構如圖7所示，網絡中各神經元活性的微分方程[13-16]為

(20)

式中，xi為神經元個體的活性值;A為被動衰減率;B為神經激勵活性值上限;D為神經激勵活性值下限;[S]+為激勵輸入;[S]-為抑制輸入。

圖7 生物激勵神經網絡二維結構Fig.7 2D structure diagram of biologic excitation neural network

2.3.2線路曲線設計算法的啟發式改進

根據上文所述，當采用遺傳算法進行線路的優化設計時，角度突變位置的線形設計將主要依賴于交叉、變異等基因操作來產生多樣性的路徑解，屬于無先驗的隨機枚舉，易產生冗余線路參與算法尋優，導致算法難以收斂于全局最優解。因此，為進一步提高算法的收斂速度及泛化能力，筆者將神經動力學模型引入種群個體的基因編碼過程中，即將道路的曲線設計過程視為一種類區間勻速的動力學行為，并采用動力學的特征約束對所選路徑進行判別和啟發式修正。其基本原理:在每一次路徑編碼完成后，算法首先建立如圖8所示的運動質點狀態遷移模型，并利用式(21)中的神經動力學模型構造出單質點的虛擬瞬時線速度、角速度等時變狀態量;結合幾何設計中的參數約束，利用線速度、角速度等運動狀態參量的運動學計算重新建立幾何約束指標;利用速度的積分量模擬虛擬路徑，最終結合網絡內部構造出的虛擬誤差，對基因種群實現進一步修正，從而保證每一次隨機枚舉所獲得的路徑解，均能啟發式地找出滿足其自身修正關系的全新路徑。

(21)

式中，V為虛擬速度;[xi,yi,zi,wi]T為單質點的遷移運動；e為運動狀態與運動學約束間的修正誤差;exi為e在X軸向上的矢量化投影。

f(ej)=max(ej,0),g(ej)=max(-ej,0),

j=xi,yi,zi,wi

其中，Vxi,Vyi,Vzi決定了質點的線速度；Vwi決定了質點的角速度。

圖8 時變單質點曲線軌跡狀態遷移模型Fig.8 Migration model of time-varying single point curve

通過上述分析，利用神經動力學模塊進行基因種群的啟發式改進，主要表現在兩個方面:一是生物激勵神經網絡可利用運動狀態的遷移過程，構造出一組虛擬、有界且連續的線速度和角速度，對上述虛擬的瞬時變量的積分可構造出一條虛擬路徑;二是具有啟發指向性地將基因變異范圍控制在誤差變化速度的鄰域內，提供有界且平滑的中間誤差，為整個系統的誤差修正提供有效的鎮定輸入。

具體算法工作原理如圖9所示，[x,y,z]T是種群個體中的一組離散路徑，利用式(21)構造出的連續、平滑的虛擬速度[Vx,Vy,Vz,Vw]，該組速度變量對時間的積分即為平滑后的虛擬路徑。利用所設計的門限閾值指標對曲線設計的指標約束進行限制，并構建一組經過過濾的修正速度[Vsx,Vsy,Vsz,Vsw]T。利用上述兩組速度向量，構造關于速度的虛擬誤差[ex,ey,ez,ew]T，對上述誤差積分便可反映出路徑的運動狀態變化量，以此狀態變化量為變異鄰域，表征路徑的修正區間，最終按照修正區間進行路徑修正即可自適應地構造出一組新的變異路徑基因。

圖9 啟發式種群路徑曲線的在線修正Fig.9 Heuristic population path curve correction

3 應用實例分析

3.1 選線算法仿真及應用效果分析

為進一步驗證文中算法對于處理露天礦山選線問題可行且有效，本文以國能投新疆準東露天煤礦計劃工程位置上剝離運輸系統選線為研究對象，對3DMine礦業工程三維建模軟件進行二次開發，以實現文中算法。利用二次開發后的運輸線路優化模塊對該礦2019年計劃工程位置上剝離運輸系統的定線實例進行仿真，其仿真優化后的開拓運輸系統定線結果如圖10所示。

圖10 選線算法三維可視化仿真結果Fig.10 3D visualization simulation results of the algorithm

為進一步體現前述算法的尋徑優勢，筆者采用軟件內置的費用計算單元對沿用該礦現行的路徑方案B(移動坑線+西-南端幫運輸路線)的成本進行核算，并與圖10中方案的仿真結果進行對比，利用軟件輸出兩組路徑方案隨剝離物料量波動的費用成本數據，繪制關系曲線如圖11所示。

圖11 不同路徑方案下的成本費用對比Fig.11 Cost comparison under different route scheme

對比現實工程位置、優化出的三維線路以及圖10數據可知，該礦2019年年初進度計劃工程位置上，A，B兩條路徑方案距排土場西側入口的線路長度分別為1.74 km和2.48 km。隨著工程進度發展，A線路長度首先逐漸變短，后因需要克服高差繞行而逐漸變長，其間線路最短長度為1.13 km;而B方案線路長度則持續縮減，但因受環繞東、南端幫影響，其線路最短長度也仍需2.07 km。

因此，從路徑長度上來看，軟件所規劃出的方案A具有明顯的優勢。從費用曲線對比結果來看，線路初始布設費用分別為A方案:34.63萬元;B方案:21.12萬元。隨著后期發展A方案費用成本受運距變化的影響，增長幅度中期平穩遞增，且總體費用小于方案B，最終兩方案的成本核算結果分別為A方案:922.85萬元;B方案:1 363.66萬元。因此，A方案費用優化效果更為明顯。另一方面，根據模擬開采結果，該礦自2020年開始實現內排，且外排土場開始接近最大收容量。因此，從未來縱采工程發展及布設內排線路的角度分析，方案A中的部分線路可以作為西段幫內排環線參與內排運輸。因此，從未來發展角度，方案A也更符合現實工程需求。故綜合上述3方面的因素，可認為方案A中規劃的路徑費用最優且能滿足現實工程需求，具有可行性。

3.2 算法收斂性優化效果分析

為提高算法收斂性，文中將生物激勵神經網絡全局激勵、抑制本地駐留的特性引入到IGA算法的基因編碼過程中，用于啟發式地提高算法收斂能力和尋優效率。因此，為驗證此種啟發式修正對改進遺傳算法的突出作用，筆者以5組計劃工程位置上的選線問題為例，采用改進的IGA算法和生物激勵啟發式改進IGA算法分別進行仿真模擬，其中5組工程位置上所對應的線路方案，采用圖12中的5組線路來表示，即線路A～E，并通過對適應度的線性計算，統計了線路方案迭代過程中各代種群中的最優解來驗證算法的收斂性和執行效率，各路徑方案逐代的費用成本統計如圖12所示。

圖12 線路的費用成本統計Fig.12 Route cost statistics

由圖12的總體下降梯度變化來看，引入生物神經網絡模型前后，曲線總體均表現出持續下降趨勢，說明種群適應度在迭代過程中不斷向低費用目標逼近，且父代中的優良基因能隨進化過程遺傳個子代個體。

進一步對比分析圖12(a)，(b)，可明顯發現如下差異:① 種群的進化初期，Bio-Inspired NN-IGA方案中各路線費用解收斂的最優適應度均優于IGA方案中的結果;② IGA方案中路線B、路線E均存在明顯的過早熟現象，經多次重復實驗驗證，也均存在上述問題;③ 兩種優化方案的最終收斂的最優費用解見表2，對比表2中數據可發現IGA方案中路線C和路線E存在過早熟問題，且無法收斂于全局最優解;④ 對比圖12曲線可以看出，Bio-Inspired NN-IGA方案曲線具有更明顯的下降梯度，并且收斂速度也明顯優于IGA方案。

表2 兩方案最終收斂的費用解
Table 2 Final convergent cost solution of the twoschemes/ten thousand萬元

方案ABCDEIGA146.5697.86176.94114.99172.54BI NN-IGA146.5697.86142.34114.99132.54

通過上述4個方面對比分析，說明啟發式改進的Bio-Inspired NN-IGA方案對于處理文中選線問題可行且有效，較之IGA算法具有更好的優化效果和執行效率。

4 結 論

(1)經典的城際高速公路定線理論中的剖面布置形式無法包含折返路徑解，與礦山實際應用場景不符，無法直接應用于存在折返路徑的露天礦山開拓選線問題中。

(2)以JONG的選線理論為基礎，采用分階段的選線剖面布置形式能有效解決折返路徑的樁點枚舉問題，并且通過坐標嵌套，計算出樁點位置坐標的代數化表達。

(3)改進的遺傳算法在處理實際礦山優化選線問題時，存在無法收斂于最優解、收斂效率低下等問題，采用生物激勵神經網絡模型對路徑基因序列進行啟發式修正，能提高算法的收斂能力及效率，這種通過在線學習獲得的啟發式修正對于其他優化問題具有一定借鑒意義。

(4)通過費用成本對比，改進的IGA算法對于露天礦山選線問題可行且有效，對于豐富露天礦山線路工程理論具有一定的促進作用。