Dijkstra算法在露天礦運(yùn)輸中的應(yīng)用

武文越 宿海芬

(內(nèi)蒙古包鋼鋼聯(lián)股份有限公司巴潤礦業(yè)分公司)

Dijkstra算法在露天礦運(yùn)輸中的應(yīng)用

武文越 宿海芬

(內(nèi)蒙古包鋼鋼聯(lián)股份有限公司巴潤礦業(yè)分公司)

由于露天礦路況復(fù)雜，汽車運(yùn)輸中油耗、輪胎消耗、汽車磨損嚴(yán)重，且隨著采場推進(jìn)、運(yùn)距增大，運(yùn)費(fèi)大幅提升。選擇最短的運(yùn)輸路徑，降低運(yùn)輸成本是當(dāng)務(wù)之急。采用Dijkstra算法，能夠快速找出最短運(yùn)輸路徑，有效降低運(yùn)輸成本。

露天礦 汽車運(yùn)輸 Dijkstra算法 最短路徑

內(nèi)蒙古某露天鐵礦采用φ310 mm機(jī)鉆穿深孔，高精度雷管和組合雷管2種爆破網(wǎng)絡(luò)連接方式,高精度雷管逐孔起爆爆破礦巖。礦巖破碎效果較好，為節(jié)約成本，該礦也采用普通雷管排間起爆方式爆破。在巖性允許的條件下，普通雷管爆破后礦巖塊度，能夠滿足小型挖機(jī)作業(yè)要求。爆破后采用6～8 m3，16 m3大型電鏟裝車，220、108 t級電動輪礦用自卸汽車運(yùn)礦。由于電動輪礦用自卸汽車回轉(zhuǎn)半徑及設(shè)備體積和噸位的限制，只能將礦石從采場拉運(yùn)至采場南礦石臺，再由雙橋卡車將礦石運(yùn)至破碎站。

該出礦點(diǎn)位于采場西1536段，開采條件復(fù)雜，不利于大型設(shè)備作業(yè)，采用雙橋卡車運(yùn)輸，可有多條路徑選擇。40 t雙橋卡車相對于該礦自有電動輪汽車，具有曲線半徑小、運(yùn)輸坡度大、不受地形限制等優(yōu)點(diǎn)，可減少運(yùn)輸線路長度，降低運(yùn)輸成本。

汽車運(yùn)輸合理開采深度為100～150 m，合理運(yùn)距為3 km。該露天礦現(xiàn)采深為162 m，露天礦進(jìn)入深部開采后，汽車運(yùn)輸成本逐漸增加。運(yùn)距增加后，運(yùn)輸燃料、輪胎消耗巨大，制約了汽車運(yùn)輸?shù)倪\(yùn)用。為此，在目前汽車運(yùn)輸條件下，采用Dijkstra建立數(shù)學(xué)模型，計(jì)算選擇最短運(yùn)輸路徑，以有效節(jié)約運(yùn)輸成本。

1 數(shù)學(xué)模型建立及求解

1.1 Dijkstra算法

Dijkstra算法也稱為雙標(biāo)號法，是由狄克特斯拉(Dijkstra，1959)提出的，是目前多數(shù)系統(tǒng)解決最短運(yùn)輸路徑問題通常采用的理論[1]。Dijkstra算法主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到終點(diǎn)為止。該算法在工程中容易實(shí)現(xiàn)，故而引起相關(guān)領(lǐng)域內(nèi)學(xué)者的關(guān)注[2-3]。

雙標(biāo)號法，即對圖中的點(diǎn)Vi賦予標(biāo)號P(Vi,λi),標(biāo)號P(Vi)表示從起點(diǎn)Vs到Vi的最短路徑的長度，標(biāo)號λi表示在Vs到Vi的最短路徑上Vi前面一個鄰點(diǎn)的下標(biāo)，即用于標(biāo)識路徑，從而可對終點(diǎn)到始點(diǎn)進(jìn)行反向追蹤，找到Vs到Vi的最短路徑。Dijkstra算法適用于每條弧權(quán)數(shù)非負(fù)的情況。

1.2 基本步驟

(1)步驟一，給起點(diǎn)vs標(biāo)號(0,s)，表示從v1到v1的距離為0，vs為起點(diǎn)。

(3)步驟三，如果上述弧的集合A=φ，表示從所有已賦予標(biāo)號的頂點(diǎn)出發(fā)，不再有這樣的弧，則計(jì)算停止。對于已經(jīng)標(biāo)號的頂點(diǎn)，可以求出從vi到達(dá)這個頂點(diǎn)的最短路徑，對于沒有標(biāo)號的頂點(diǎn)，則沒有從vi到達(dá)這個頂點(diǎn)的路徑。如果弧集A≠φ，轉(zhuǎn)向步驟4。

(4)步驟四，對弧集A中的每條弧(vi,vj)，計(jì)算Tij=P(Vi)+ωij，在所有的Tij中，找到值為最小的弧，假設(shè)為(vs,vt)。需要特別注意的是，如果上述Tij值為最小的弧有多條，并且這些弧第二個頂點(diǎn)vj相同，表示存在多條最優(yōu)路徑，此時任意選擇一條路徑，最終最優(yōu)路徑不變，vj應(yīng)得到多個雙標(biāo)號。

(5)步驟五，給弧(vs,vt)的終點(diǎn)vt賦予雙標(biāo)號(P(Vt),s)，返回步驟2。經(jīng)過上述循環(huán)計(jì)算，將會求出v1到一個頂點(diǎn)vj最短路徑及長度，進(jìn)而得到一個頂點(diǎn)vj及雙標(biāo)號。如果圖中共有n個頂點(diǎn)，最多計(jì)算(n-1)個循環(huán)，即能得到最后最短路徑的結(jié)果。

1.3 模型建立

從工作面到卸礦點(diǎn)的路徑很多，線路系統(tǒng)較復(fù)雜時，人工方法找出最短路徑較為困難，用網(wǎng)絡(luò)的方法，對運(yùn)輸線路系統(tǒng)進(jìn)行抽象簡化，用線代替每條線路，固定路口、零時斜坡路口即是節(jié)點(diǎn)，將節(jié)點(diǎn)標(biāo)號[4]。

任意兩點(diǎn)A、B直線距離：

(1)

任意兩點(diǎn)A、B彎道距離：

(2)

將相關(guān)點(diǎn)三維坐標(biāo)輸入Excel，調(diào)入函數(shù)，可得到各路線長度。

1.4 Dijkstra算法求解

給起點(diǎn)v1標(biāo)號(0,1)，表示從v1到v2的距離P(v1)=0，v1為起點(diǎn),圖1為模型建立及求解過程圖。

圖1 模型建立及求解過程

T13=P(v1)+ω13=0+0.5=0.5;T15=P(v1)+ω15=0+1=1;T16=P(v1)+ω16=0+1.3

=1.3;T17=P(v1)+ω17=0+1.2=1.2.

=T13=0.5.

T15=P(v1)+ω15=0+1=1;T16=P(v1)+ω16=0+1.3=1.3;T17=P(v1)+ω17=0+1.2=1.2;T32=P(v3)+ω32=0.5+0.15=0.65;T35=P(v3)+ω35=0.5+0.9=1.4.

重復(fù)上述步驟，直至終點(diǎn)。反向追蹤，求出v1→v5→v8→v9路徑為最短運(yùn)輸距離，運(yùn)距為3.4 km。

2 結(jié) 論

采場道路條件復(fù)雜，既有固定運(yùn)輸線路，也有臨時斜坡路，選擇最短運(yùn)輸路徑對降低汽車運(yùn)輸成本有重要意義。Dijkstra算法可以快速確定多運(yùn)輸路徑條件下的最短運(yùn)距問題，可以有效節(jié)約露天礦汽車運(yùn)輸成本。

[1] 張福浩,劉紀(jì)平.一種基于Dijkstra的海量空間數(shù)據(jù)最短路徑算法[J].遼寧工程技術(shù)大學(xué)學(xué)報，2009，28(4)：554-555.

[2] 李大東,孫秀霞,彭建亮，等.基于可視圖的改進(jìn)Dijkstra 算法[J].電光與控制，2010，17(3)：40-41.

[3] 章永龍.Dijkstra最短路徑算法優(yōu)化[J].南昌工程學(xué)院學(xué)報，2006，25(3)：31-32.

[4] 鞏艷芬,劉 吟,于惠賢，等.Dijkstra 算法在企業(yè)物流運(yùn)輸網(wǎng)絡(luò)中的應(yīng)用[J].大慶石油學(xué)院學(xué)報, 2005, 29 (4): 104-105.

Application of Dijkstra Algorithm in Open-pit Mine Transportation

Wu Wenyue Su Haifen

(Barun Mining Co.,Ltd., Baotou Steel (Group) )

Because of the complex road conditions in open-pit mine,the oil consumption,tire consumption and automobile abrasion are serious,and the automobile transportation's cost is increased with the increasing of distance in open-pit mine.So,it is necessary to choose the shortest transportation path and reduce the cost.The Dijkstra algorithm is adopted so as to identify the transportation shortest path and reduce the cost effectively.

Open-pit mine, Automobile transportation, Dijkstra algorithm, Shortest path

2015-06-10)

武文越(1984—)，男，助理工程師，碩士，014080 內(nèi)蒙古包頭市。