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

(1.鹽城工學(xué)院 經(jīng)濟(jì)管理學(xué)院，江蘇 鹽城 224051; 2.遼寧工程技術(shù)大學(xué) 礦業(yè)學(xué)院，遼寧 阜新 123000; 3.遼寧工程技術(shù)大學(xué) 遼寧省高等學(xué)校礦產(chǎn)資源開發(fā)利用技術(shù)及裝備研究院,遼寧 阜新 123000)

露天礦山路徑優(yōu)化問題是滿足特定物理和經(jīng)濟(jì)約束之下搜索最佳運輸線路的組合優(yōu)化問題，長期以來一直都是卡車調(diào)度、物料流規(guī)劃等相關(guān)領(lǐng)域的重點研究課題之一，對于降低礦山運營成本具有重要意義[1-2]。

目前，針對于露天礦山路徑優(yōu)化算法大致可分為兩類，第一種方法是使用等效運距作為權(quán)重或優(yōu)化指標(biāo)，采用靜態(tài)網(wǎng)絡(luò)分析方法來搜索最佳路線。如，WHITE和OLSON[3]以全局等效運距的總和最小化為優(yōu)化目標(biāo)，建立露天礦山運輸路徑優(yōu)化模型;CHANG等[4]在綜合考慮等效距離和運輸系統(tǒng)收益的情況下，針對卡車調(diào)度需求，提出一種尋徑算法;ADENSO-DIAZ[5]指出煤礦的運輸路線存在波動變化，并結(jié)合這種動態(tài)特點，提出了一種用于自動更新靜態(tài)網(wǎng)絡(luò)的新方法;LI J Q等[6]提出了一種同時考慮設(shè)備作業(yè)和時效性成本最小化的露天礦山灑水車線路優(yōu)化策略;HU[7]采用和聲搜索算法設(shè)計了露天礦山路徑優(yōu)化算法;陳應(yīng)顯[8]、孫臣良[9]、李勇[10]等分別將群智能算法引入靜態(tài)運輸網(wǎng)絡(luò)圖中，提出適用于露天礦路徑優(yōu)化問題的解決方案;另一類方法則是在多種約束條件下，結(jié)合圖論中網(wǎng)絡(luò)分析方法，通過求解數(shù)學(xué)規(guī)劃模型來實現(xiàn)礦山運輸路徑優(yōu)化，頗有代表性的研究如CHOI,PARK和 SUNWOO[11]指出“目前很少有關(guān)于卡車最佳運輸路線的研究，這主要是因為在以前的研究中，人們總是假設(shè)路面狀況在其生命周期內(nèi)總是相同的，這種假設(shè)對露天礦山進(jìn)行優(yōu)化分析往往是不現(xiàn)實的”，基于此種考慮將多指標(biāo)評價方法與最小成本路徑分析方法相結(jié)合，提出適用于大型露天礦山線路優(yōu)化的新方法;CHOI和NLETO[12]通過對最小成本路徑分析算法的改進(jìn)，提出一種適用于不同路面類型的優(yōu)化方法，并對地形和曲線設(shè)計變化對交通效率的影響進(jìn)行了分析。

事實上，路徑優(yōu)化算法在物流、交通運輸和路由器尋址[13-14]等相關(guān)領(lǐng)域有著極為廣泛的應(yīng)用，近年來也形成了一系列極為成熟的動態(tài)網(wǎng)絡(luò)尋徑算法，但這些算法很難被直接應(yīng)用于露天礦山路線優(yōu)化問題中，其主要原因在于:在露天礦山實際作業(yè)場景中,運輸系統(tǒng)常受到多種綜合因素限制,運輸成本常表現(xiàn)出周期性的隨機波動效應(yīng)，如直接采用傳統(tǒng)的物理距離或單一靜態(tài)常量來表征，則存在明顯的局限性。特別是當(dāng)路面受到頻繁碾壓破壞和周期性維護(hù)后，這種成本波動效應(yīng)的周期性特征則更為明顯。筆者在充分考慮上述問題的基礎(chǔ)上，將Clifford代數(shù)引入到露天礦山路徑優(yōu)化問題中，利用其拓?fù)溥B通性計算與標(biāo)量表達(dá)的無關(guān)性，構(gòu)建了線路拓?fù)溥壿嬘嬎惴椒?，并建立了?biāo)量場動態(tài)表達(dá)模型;考慮道路運輸網(wǎng)絡(luò)具有動態(tài)隨機特性，提出基于時變運輸功最小化的優(yōu)化目標(biāo)，并定義了時變運輸功公式，提出了一種有效估計時變滾動阻力系數(shù)的新方法，給出了計算此類時變指標(biāo)的優(yōu)化計算策略;最終結(jié)合遺傳算法構(gòu)建了路徑優(yōu)化算法。經(jīng)多組仿真對比實驗驗證，文中算法對于求解礦山路徑優(yōu)化問題可行且有效。

1 基于Clifford代數(shù)的運輸網(wǎng)絡(luò)建模

1.1 有向圖的幾何代數(shù)編碼

在Clifford代數(shù)空間內(nèi)進(jìn)行基于有向圖的路徑分析，實質(zhì)上是對歐式空間內(nèi)的網(wǎng)絡(luò)分析法的一種多維推廣，是有效降低網(wǎng)絡(luò)分析復(fù)雜度的重要手段之一。在Clifford代數(shù)空間內(nèi)，任意歐式空間中的一條帶有n個節(jié)點的路徑方案，均可以被抽象表達(dá)為一個n階片積對象(n-blade)，并總是可以通過blade對象的幾何代數(shù)運算來實現(xiàn)路徑拓?fù)潢P(guān)系的生成、遍歷和篩選[15]。因此，對于一個包含n個路徑節(jié)點的運輸系統(tǒng)有向圖G=(V,E)，則可進(jìn)行如下的幾何代數(shù)描述:對于有向圖G，存在一簇向量{e1,e2,…,en}為幾何代數(shù)空間Cln,0的向量集合，其中每一個元素ei均對應(yīng)有向圖網(wǎng)絡(luò)中的惟一節(jié)點;同理，空間中的另一簇向量{e13,e24,…,eij};for1

1.2 Cln,0空間內(nèi)拓?fù)潢P(guān)系計算

Cln,0空間中對象的維度擴(kuò)張和形體的構(gòu)建與表達(dá)均是通過外積運算來實現(xiàn)，這種內(nèi)蘊的外積拓?fù)溲油靥匦阅芙⒕W(wǎng)絡(luò)圖中節(jié)點、有向邊以及路徑間的統(tǒng)一表達(dá)。因此，對于網(wǎng)絡(luò)圖中節(jié)點與有向邊間的二目幾何運算關(guān)系則可形式化表達(dá)為

(1)

式(1)描述了有向圖節(jié)點到有向邊的拓?fù)溲油胤椒?，對于路徑中有向邊之間的進(jìn)一步延拓也可以采用類似的外積運算來實現(xiàn)。故對于圖中具備連通性的n個節(jié)點v1,v2,…,vn，其有序排列所組成的有效路徑則可描述為具有n個基向量ei的連續(xù)外積形式，即L=e1∧e2…∧en=e1,2,…,n，e1,2,…,n為空間中的n階片積對象，它所對應(yīng)的路徑即為可行解。

上述運算介紹了路徑拓?fù)溲油氐木唧w方法，但并不能判斷出路徑間的拓?fù)溥B通性。為此，文中引入片積維度的概念，并通過片積的維度運算實現(xiàn)延拓路徑的連通性判斷。由路徑Cln,0可以看出，對具備連通性的路徑進(jìn)行連續(xù)的外積運算，其本質(zhì)上是將一維向量ei擴(kuò)展拉伸為n維片積對象e1,2,…,n的過程。因此，可以廣義的認(rèn)為基的每一次外積運算，其維度均向上延拓一階，也就是說片積的重復(fù)外積運算將滿足維度的可加性條件。根據(jù)這種可加性，就可以通過外積的維度變化來判別路徑的連通性。因此，文中采用判據(jù):grade(ei∧ej)=grade(ei)+grade(ej)來判斷拓?fù)溲油氐倪B通性。相反，當(dāng)路徑間不具備連通性時，由于有向邊運算結(jié)果為變量0，可加性判別則將不再成立，即grade(0)≠grade(ei)+grade(ej)。綜合上述兩組判據(jù)，即可實現(xiàn)路徑延拓與連通性拓?fù)涞目焖僮R別。

按照上述的幾何拓?fù)潢P(guān)系，將有向圖中的有向邊的幾何拓?fù)潢P(guān)系抽象為幾何鄰接矩陣描述為A，矩陣A中的任意一個元素皆描述了圖中任意兩點之間的幾何拓?fù)潢P(guān)系和連通性。

(2)

觀察式(2)不難發(fā)現(xiàn)，其本質(zhì)上就是2-blade有向邊的矩陣表達(dá)，因此外積運算仍適用于其所對應(yīng)的矩陣表達(dá)?；诖朔N考慮，根據(jù)鄰接矩陣的運算特性，將外積運算進(jìn)一步推廣，按照矩陣“叉乘”運算定義鄰接矩陣的外積運算規(guī)則:A2=A∧A，按照此種運算規(guī)則，幾何鄰接矩陣A每參與外積運算(A∧A)就等同于片積維度延拓一次，也就是向外擴(kuò)展一層節(jié)點的路徑，其路徑延拓原理如圖1所示，對于圖1中包含有9個節(jié)點的有向圖，帶有2-blade有向邊的幾何鄰接矩陣A，經(jīng)過一次外積運算即可計算出所有3-blade的路徑，即包含3個任意節(jié)點的有效路徑(其中A2矩陣中“+”并不指代數(shù)學(xué)運算，僅表示可能路徑的組合)。故通過多次迭代上述外積運算即可得到任意節(jié)點間的拓?fù)溥B通性關(guān)系。

1.3 Cln,0空間內(nèi)標(biāo)量計算

權(quán)重信息是尋徑問題的求解基礎(chǔ)，在露天礦山的路徑優(yōu)化問題中，這種權(quán)重信息多表現(xiàn)為數(shù)值型變量，且變量常以節(jié)點或有向邊的關(guān)聯(lián)函數(shù)形式存在。但在之前定義的幾何代數(shù)空間中，空間對象間所有二目運算均基于外積的形式參與代數(shù)運算，這使得標(biāo)量場數(shù)據(jù)均以積的形式表達(dá)，導(dǎo)致部分標(biāo)量場數(shù)據(jù)喪失了可加性關(guān)系。為保證計算模型的合理性，需要對標(biāo)量場內(nèi)的關(guān)聯(lián)函數(shù)進(jìn)行如下可加性變換:考慮網(wǎng)絡(luò)自身與權(quán)重間的無關(guān)性，將如式(3)所示的帶有標(biāo)量權(quán)重的外積拓?fù)溥\算的標(biāo)量部分嵌入可加性映射Φ。

aei∧bej=(a*b)ei∧ej

(3)

eaei∧ebej=(ea*eb)ei∧ej=ea+beij

(4)

圖1 幾何鄰接矩陣外積運算原理Fig.1 Operation principle of geometric adjacency matrix exterior product

2 數(shù)值約束標(biāo)量場建模

2.1 定義模型變量

為定義模型方便，文中首先對約束模型中的參數(shù)變量做以下說明，其中:

(2)待估計參數(shù):Fei,j為相鄰有向邊之間的阻力集合,kN。

(3)規(guī)劃模型的決策變量:xi為各弧段上決策變量。

2.2 數(shù)值型約束模型

數(shù)值型約束是描述路徑屬性特征的依據(jù)，也是建立路徑優(yōu)化問題的數(shù)值計算基礎(chǔ)。對于文中所述的優(yōu)化問題與傳統(tǒng)的混合整數(shù)規(guī)劃模型建模過程相同，只是無需在考慮模型中的決策變量和相關(guān)約束。因此，對于有向邊約束的標(biāo)量場建模，仍可采用規(guī)劃建模的思路，按照全局時變運輸功最小化進(jìn)行建模，其優(yōu)化問題的目標(biāo)函數(shù)如式(5)所示。

(5)

式中,Fei,j阻力為時變函數(shù)，其主要由3部分組成:滾動阻力Ffeij、坡度阻力Freij以及空氣阻力Fweij，其關(guān)聯(lián)函數(shù)的形式化表達(dá)如式(6)所示。

考慮所選路徑差異以及因路面頻繁碾壓而造成的路面阻力系數(shù)變化，定義相鄰節(jié)點路徑間的阻力公式:

(6)

不等約束以及等式約束條件如下:

(1)對于各個路徑弧段的車流密度約束:

(7)

(8)

(2)所選路徑的總體車流密度約束:

(9)

式中,KE應(yīng)滿足計算條件如下式:

(10)

(3)道路通過能力約束:

(11)

式中,N應(yīng)滿足計算條件如下:

(12)

2.3 時變阻力系數(shù)估計

由權(quán)重指標(biāo)的關(guān)聯(lián)函數(shù)式(5),(6)不難看出，模型中最難計算的參數(shù)即為對模型中時變阻力系數(shù)的估計，這主要是因為該參數(shù)在不同路段以及相同路段的不同養(yǎng)護(hù)周期內(nèi)均存在波動變化，進(jìn)而導(dǎo)致阻力系數(shù)存在時變效應(yīng)。因此，為了更好地模擬卡車在運輸?shù)缆飞弦驖L動阻力系數(shù)變化而造成的這種阻力時變效應(yīng)，筆者采用多標(biāo)簽?zāi)Ｊ阶R別(分類)和趨勢面技術(shù)來構(gòu)建阻力系數(shù)的時變參數(shù)估計。其估計算法的基本思路是:首先利用統(tǒng)計所得路面屬性指標(biāo)和特定的人為路面分級，建立多標(biāo)記的模式分類模型;利用模式分組后所得的指標(biāo)參數(shù)進(jìn)一步構(gòu)建其阻力系數(shù)趨勢面模型;最終按照給定路徑的指標(biāo)參數(shù)，實現(xiàn)阻力系數(shù)的時變估計，其算法實現(xiàn)過程如下:

第1步，道路表面類型的分類。根據(jù)露天礦山的運輸?shù)缆窢顩r及文獻(xiàn)[16]中匯總的各類路面特征和阻力系數(shù)分布范圍，對扎哈淖爾露天煤礦不同養(yǎng)護(hù)周期內(nèi)的路面特征進(jìn)行分類，并將各類路面特征及阻力系數(shù)分布范圍進(jìn)行統(tǒng)計，其分類統(tǒng)計結(jié)果見表1。

表1 不同路面條件下的滾動阻力系數(shù)分類
Table 1 Classification of rolling resistance coefficient under different road conditions

路面類型分類阻力系數(shù)范圍1.非常堅硬,光滑的路面或污垢表面,沒有滲透或彎曲0.010～0.0182.堅硬、光滑、穩(wěn)定的路面,不滲透、澆灌、定期養(yǎng)護(hù)0.018～0.0203.堅固、光滑、滾動的道路,有泥土或彎曲的表面,微微彎曲,保持輕微,保持相當(dāng)?shù)囊?guī)律性澆水0.020～0.0304.泥路,在負(fù)荷作用下彎曲,很少維護(hù),沒有水,25 mm的輪胎滲透或彎曲0.030～0.0455.泥路,在負(fù)荷作用下彎曲,很少維護(hù),沒有水,50 mm的輪胎滲透或彎曲0.045～0.0606.坑坑洼洼的土路,在負(fù)荷作用下變?nèi)彳?沒有維護(hù),不穩(wěn)定,100 mm的輪胎滲透或彎曲0.060～0.0757.坑坑洼洼的土路,在負(fù)荷作用下變?nèi)彳?沒有維護(hù),不穩(wěn)定,200 mm的輪胎滲透和彎曲0.075～0.1008.非常柔軟,泥濘,坑坑洼洼的道路,300 mm的輪胎滲透,沒有彎曲0.100～0.140

第2步，多標(biāo)簽?zāi)Ｊ椒诸愑?xùn)練數(shù)據(jù)處理。根據(jù)滾動阻力系數(shù)的測試表明[16-17]，車輛的滾動阻力系數(shù)易受多種因素綜合影響，如路面條件、行駛速度、輪胎結(jié)構(gòu)、輪胎材料和輪胎壓力等，但考慮問題自身、數(shù)學(xué)模型抽象及問題求解的復(fù)雜性，本文僅討論因路面頻繁碾壓和因周期性路面養(yǎng)護(hù)，而引起的滾動阻力系數(shù)波動變化。為此，筆者將對路面碾壓破壞的三大主要因素作為多標(biāo)簽分類模型的屬性指標(biāo)，即路段上平均行駛速度、養(yǎng)護(hù)周期內(nèi)的累積運輸物料量以及距上一個路面養(yǎng)護(hù)周期的時間間隔。按照上述屬性和對應(yīng)路面類型，統(tǒng)計扎礦2017年指標(biāo)數(shù)據(jù)作為模式分組的訓(xùn)練數(shù)據(jù)，數(shù)據(jù)統(tǒng)計結(jié)果如圖2所示。

圖2 訓(xùn)練數(shù)據(jù)樣本Fig.2 Training data sample

圖3 四分類邏輯流程Fig.3 Four-classification logic flow

(13)

式中,K(x·xi)為核函數(shù)，筆者選用高斯徑向基核函數(shù)。

(14)

并進(jìn)一步采用最小二乘估計，建立規(guī)劃模型如式(15)所示，8組路面的二次多項式趨勢面擬合結(jié)果如圖4所示。

圖4 不同路面類型的趨勢面估計Fig.4 Trend surface estimates for different road types

(15)

3 基于Clifford代數(shù)的路徑優(yōu)化算法

傳統(tǒng)的路徑優(yōu)化算法都是建立在求解整數(shù)規(guī)劃模型的基礎(chǔ)上，并結(jié)合群智能算法提高求解效率。這類規(guī)劃模型計算常采用決策變量控制路徑的拓?fù)溥B通性，求解過程需要同時考慮拓?fù)溥B通性計算和數(shù)值約束指標(biāo)的目標(biāo)尋優(yōu)。當(dāng)大型網(wǎng)絡(luò)中數(shù)值約束存在動態(tài)特性時，求解這類問題的復(fù)雜度就會明顯增加，易導(dǎo)致優(yōu)化算法陷入局部最優(yōu)，而無法獲得全局最優(yōu)解。在充分考慮這些因素的基礎(chǔ)上，筆者將幾何代數(shù)引入動態(tài)運輸網(wǎng)絡(luò)中，將傳統(tǒng)歐式空間的有向圖推廣到Clifford代數(shù)空間，實現(xiàn)網(wǎng)絡(luò)中的節(jié)點、有向邊和路徑的統(tǒng)一表達(dá)，利用迭代外積運算來表達(dá)出路徑的拓?fù)溥B通性，從而實現(xiàn)拓?fù)溆嬎愫蛿?shù)值約束優(yōu)化計算的分離，并且拓?fù)溥B通性計算結(jié)果可直接為群智能優(yōu)化算法提供啟發(fā)式拓?fù)潢P(guān)系。因此，文中路徑優(yōu)化算法設(shè)計的重點即為考慮如何將數(shù)值型約束嵌入有向圖中，實現(xiàn)在幾何代數(shù)空間內(nèi)處理拓?fù)浣馕鲇嬎愫蛣討B(tài)有向邊權(quán)重的標(biāo)量計算，并利用外積的幾何鄰接矩陣計算結(jié)果為群智能算法提供啟發(fā)式編碼方案，最終實現(xiàn)復(fù)雜大型動態(tài)網(wǎng)絡(luò)的快速尋徑。

3.1 權(quán)重關(guān)聯(lián)函數(shù)優(yōu)化策略

第2節(jié)定義了關(guān)于路面養(yǎng)護(hù)時間間隔(t)的卡車時變行駛阻力的表達(dá)方式和計算方法，它標(biāo)定了網(wǎng)絡(luò)中各有向邊之間的數(shù)值約束關(guān)系，但對于這樣一個動態(tài)網(wǎng)絡(luò)，特別是當(dāng)網(wǎng)絡(luò)節(jié)點規(guī)模較大時，這類數(shù)值計算仍極為復(fù)雜。出于簡化計算提高算法收斂性考慮，文中基于隨機理論和數(shù)理統(tǒng)計知識，引入兩組推論和一組數(shù)值計算優(yōu)化策略。

推論1:對于任意兩個隨機變量X,Y，如果其期望E(·)滿足E(X)≤E(Y)，則事件所對應(yīng)的概率P(X≤Y)>0.5也成立。

為進(jìn)一步說明該推論的正確性，筆者結(jié)合數(shù)理統(tǒng)計知識推導(dǎo)出此推論的證明過程如下:

假設(shè):

E(X)≤E(Y)

(16)

可推知:

E(X)-E(Y)≤0?E(X-Y)≤0

(17)

引入相關(guān)變量Z:

Z=X-Y

(18)

可推得:

E(Z)≤0

(19)

根據(jù)期望定義可推知:

(20)

將公式分為A,B兩部分討論:

考慮公式A,B所在區(qū)間，可推知:

因為

(22)

又

E[Z]≤0

(23)

所以，式A絕對值一定大于式B絕對值:

(24)

故可推得如下P之間的關(guān)系:

P(Z≤0)≥P(Z≥0)

(25)

又因為整個概率空間和恒等于1:

P(Z≤0)+P(Z≥0)=1

(26)

進(jìn)而推得:

P(Z≤0)≥1-P(Z≤0)?2P(Z≤0)≥1

(27)

整理即可證明出推論結(jié)果正確，即

P(Z≤0)≥0.5?P(X≤Y)≥0.5

(28)

推論2:對于路徑優(yōu)化問題中具備聯(lián)通性且參與對比的兩條路徑L和K，可采用P(L≤K)和P(L>K)分別描述L和K成為最優(yōu)路徑的概率。因此，根據(jù)推論1結(jié)論，文中廣義的認(rèn)為min{E(L),E(K)}為最優(yōu)路徑的判據(jù)，判據(jù)所對應(yīng)的路徑即為最優(yōu)路徑。

結(jié)合上述2組推論，采用隨機理論進(jìn)行優(yōu)化建模，其數(shù)值計算優(yōu)化策略可表述為:假設(shè)道路運輸網(wǎng)絡(luò)中存在有效的可行路徑r邊的全路徑運輸功能耗可以表示為一個l維的隨機變量Ω={W1(t),W2(t),…,Wl(t)}，其聯(lián)合概率密度分布函數(shù)可以表示為

fr=f[w1(t),…,wl(t)]=

(29)

因此，對于表征全路徑中最優(yōu)路徑為r的事件γ，且該事件滿足如下路徑間的能耗條件:

wγ(t)≤w1(t),…,wγ(t)≤wl(t)，該路徑成為全局最優(yōu)路徑的概率即可表示為:

Pγ[wγ(t)≤w1(t),…,wγ(t)≤wl(t)]=

(30)

再進(jìn)一步結(jié)合推論1，將路徑事件的概率估計轉(zhuǎn)化為求全局能耗期望值問題，即可實現(xiàn)數(shù)值約束的優(yōu)化計算。

3.2 路徑優(yōu)化算法流程

為進(jìn)一步提高算法的收斂特性，筆者將幾何代數(shù)空間外積計算所得的幾何鄰接矩陣結(jié)果嵌入遺傳算法，利用拓?fù)溆嬎憬Y(jié)果啟發(fā)式的枚舉路徑基因編碼，并將3.1節(jié)所介紹的優(yōu)化策略嵌入到遺傳算法的適應(yīng)度函數(shù)(M/U(t),其中M為一個較大的常數(shù)，防止適應(yīng)度值過小)中，用于簡化時變動態(tài)網(wǎng)絡(luò)中的標(biāo)量場計算，算法具體處理流程將如圖5所示。

圖5 算法邏輯流程Fig 5 Algorithm logic flow

4 仿真實驗對比分析

為了直觀地表達(dá)算法的優(yōu)化效果，文中以扎哈淖爾露天礦為研究對象，選擇了5組測試路徑，對文中算法各代最優(yōu)解的運輸功能耗進(jìn)行統(tǒng)計，如圖6所示。

圖6 路徑優(yōu)化結(jié)果Fig.6 Route optimization results

對比分析圖6可知，N1和N4兩組路徑節(jié)點數(shù)分別為74和77，在早期路徑優(yōu)化過程中運輸功值較大，并在第30～40代左右算法開始快速收斂，最終收斂于全局最優(yōu)解。

考慮現(xiàn)階段對于遺傳算法的精度、可信度和計算復(fù)雜程度尚沒有有效的定量分析方法，為進(jìn)一步論證文中算法的魯棒特性，筆者采用上述5組測試路徑進(jìn)行20次重復(fù)測試，其20次重復(fù)實驗的統(tǒng)計數(shù)據(jù)見表2。對比表2數(shù)據(jù)可知，20組重復(fù)實驗除N1存在錯誤估計外，均收斂于最優(yōu)解。通過平均相對誤差水平和計算用時對比，說明算法具有較強的穩(wěn)定性和較高執(zhí)行效率。

表2 重復(fù)實驗對比數(shù)據(jù)(20組)
Table 2 Repeated test comparison data(20 groups)

實例實驗值最優(yōu)解最差解平均誤差/%平均用時/sN1746 932.9746 937.8746 952.10.000 835.09N2677 493.7677 493.7677 507.40.000 392.07N3898 642.1898 642.1898 646.80.000 303.91N4959 358.6959 358.6959 365.60.000 314.87N5955 632.7955 632.7955 632.701.61

筆者曾在文獻(xiàn)[18]中論證過基于時變運輸功最小化的路徑優(yōu)化方法，并采用改進(jìn)的遺傳算法對路徑優(yōu)化模型進(jìn)行求解。為進(jìn)一步說明引入Clifford代數(shù)計算后對于提高尋徑算法效率的改善作用，筆者將此5組測試路徑代入文獻(xiàn)[18]算法模型進(jìn)行仿真，其各代最優(yōu)解的運輸功能耗統(tǒng)計如圖7所示。

圖7 基于改進(jìn)遺傳算法的路徑優(yōu)化結(jié)果Fig.7 Route optimization results based on IGA

對比圖6和7可發(fā)現(xiàn)，圖7中N1和N4兩組模型迭代前期收斂速度緩慢，并且伴有過早熟現(xiàn)象。而圖6中引入幾何代數(shù)方法后算法的收斂速度更快，而且能消除圖7中的過早熟現(xiàn)象，能夠快速的優(yōu)化出全局最優(yōu)解。對比N2,N3和N5節(jié)點相對較少的路徑，圖6中3組曲線收斂方向上的梯度明顯大于圖7中曲線。因此，可以說明文中算法具有更快的收斂速度和過早熟控制能力。

最后為論證采用時變運輸功作為尋徑問題目標(biāo)函數(shù)的優(yōu)勢，筆者進(jìn)一步利用經(jīng)典靜態(tài)網(wǎng)絡(luò)路徑優(yōu)化算法對5組測試路徑進(jìn)行仿真實驗，其仿真計算結(jié)果見表3。通過對比表格中數(shù)據(jù)可看出，較之經(jīng)典算法，文中算法能快速的找出路徑中的能耗最優(yōu)解，對于求解路徑優(yōu)化問題具有更強的現(xiàn)實意義。

表3 對比算法的優(yōu)化效果
Table 3 Comparison of the effect of algorithmic optimization

CaseLoad StatusAlgorithmsNodeAverage speed/(km·h-1)Haul dist-ance/kmTransport energy/kJExecution time/sN11Clifford-GA74341.39746 932.95.16Dijkstra/PSO321.27776 826.421.17/7.79N21Clifford-GA31311.17677 493.72.02Dijkstra /PSO291.08704 826.58.77/3.04N31Clifford-GA39341.68898 642.13.97Dijkstra /PSO331.59914 732.311.87/3.73N41Clifford-GA77351.93959 358.65.07Dijkstra /PSO321.87967 439.525.02/9.35N51Clifford-GA36271.94955 632.71.59Dijkstra /PSO221.67979 261.87.07/4.72

5 結(jié) 論

(1)從有向圖網(wǎng)絡(luò)分析法出發(fā)，將經(jīng)典歐式空間內(nèi)網(wǎng)絡(luò)分析方法推廣至幾何代數(shù)空間，建立了一套路徑的幾何拓?fù)溥B通性和約束指標(biāo)計算的方法，實現(xiàn)了幾何拓?fù)浜蛿?shù)值最優(yōu)化問題的分離，降低了傳統(tǒng)露天礦多約束條件路徑優(yōu)化問題的復(fù)雜度。

(2)將路徑分析中的數(shù)值型約束嵌入到幾何代數(shù)空間，并根據(jù)露天礦山工程實際，建立了基于時變運輸功的路徑優(yōu)化模型，并結(jié)合數(shù)理統(tǒng)計和隨機理論，提出兩組推論和一組優(yōu)化策略，顯著提高了算法的收斂效率。

(3)針對傳統(tǒng)遺傳算法的隨機路徑編碼易存在冗余編碼問題，通過引入外積拓?fù)溥\算結(jié)果進(jìn)行啟發(fā)式遺傳編碼，能有效提高遺傳算法的收斂速度。

(4)通過對比多組尋徑算法，證明采用Clifford代數(shù)與遺傳算法進(jìn)行組合來構(gòu)建路徑優(yōu)化算法是現(xiàn)實可行的，對于降低礦山能耗、指導(dǎo)礦山生產(chǎn)具有極為重要的現(xiàn)實意義。