A* 算法在露天礦運輸道路最優路線的應用

肖英才

(江西地質科學研究所，江西 南昌 330030)

0 引言

露天礦運輸成本在礦山總投資中，占有很大比重，并且運輸系統安排的合理與否直接關系到礦山的后續的生產作業安排及贏利。因此，通過對運輸系統的優化，建立高效、合理的運輸系統，從而實現充分發揮卡車運輸的潛力，提高運輸效率，最終達到減少運輸卡車的數量，降低運輸成本的目標，并對于減少設備損耗、節能和減少環境污染都具有重要意義［1］。

最優路徑在交通網絡中有著廣泛的應用，其算法有著重要的研究價值。目前，最優路徑算法研究比較多，主要有:Dijkstra 算法及其改進算法、Floyd算法［2］、A*及其改進算法，粒子群算法等，Dijkstra算法要遍歷所有的節點，因此在其求解中必然要產生冗余，時間花費較多;Floyd 算法的時間復雜度為O(n3)，且不能直觀反映出各個頂點之間最短路徑序列的先后關系［3］;粒子群算法有較強的全局搜索能力，但是在搜索時易陷入局部最優并導致搜索停滯的缺點［4］;A*算法利用合適的估價函數，從而減少搜索空間，提高搜索效率［5］。綜上所述，各類算法都有其優缺點，其中Dijkstra 算法是典型的最短路徑搜索算法，且可以保證找到最優路徑，但是由于它要求解當前點到所有的節點，因此其效率低下。

綜上所述，以上各種算法各有其優缺點，本文選用人工智能中的A*算法，通過在估計函數中引入距離和方向兩個參數，使估價值盡可能接近實際值，保證找到最優路徑。

1 露天礦運輸網絡模型

露天礦的運輸網絡是由完成采礦場采出的礦石運送到選礦廠、破碎站或貯礦場，把剝離的巖土送至排土場等運輸工作的路徑組成，在露天礦各生產環節中起著“動脈”和“紐帶”的作用［6］。以露天礦各采區的裝載點為入點，以排土場、卸礦點及貯礦點為收點，中間節點為道路的交匯點或道路性質突變處為中間節點，兩節點間以其直線距離為權值，構成露天運輸網絡模型［7］，某露天礦山的部分運輸網絡示意圖見圖1。

圖1 部分運輸網絡示意圖

通過對運輸網絡圖的研究，在從裝載點到卸載點之間卡車運行的路線有很多種可能，在各結點間的距離已知條件下，求出入點到收點間的最短路徑。該問題的解隨著頂點數目的增加，可行解將呈幾何級數增大，當頂點的規模較大時，由于耗時太長而在實際應用中受限。A*算法通過引入估價函數，大大減少搜索時間，迅速找到最優路徑。

2 A* 算法

2.1 A* 算法的基本原理

A*算法是由Hart，Nilsson，Raphael 等人首先提出的，它是在Dijkstra 算法和BFS(最好優先搜索)算法基礎上建立起來的［8］，被廣泛應用于路徑優化領域［9］。它采用啟發信息來決定哪一個是下一步要擴展的節點，然后搜索就可能沿著某個被認為最有希望的邊緣區段向外擴展［10］，因此可以大大降低計算的空間與時間。這種需要估算節點希望的度量即是估價函數f(n)為:

f(n)=g(n)+h(n)

式中:g(n)是在網絡中從初始節點到目標節點的實際距離，h(n)是從初始點到目標節點最優路徑的估計距離。

搜索算法的可采納性(Admissibility)是指該算法一定能找到一條最佳的路徑［11］;A*算法滿足可采納性的充要條件是:h(n)≤h*(n)，h*(n)為初始點到目標點的實際最短距離。因此只要h(n)小于實際最短距離，則A*算法一定能找到最優解。

2.2 估價函數f(n)的確定

估價函數是影響A*算法效率的重要因素，提高其精確度，算法運行效率也會提高［11］。估價函數f(n)能夠提供一個確定擴展節點的方法，用以決定哪個節點最有可能通往最優路徑，使得搜索沿著最有希望的區段擴展。由于A*算法總是選擇h(n)值最小的節點作為擴展節點，所以若估價函數選h(n)大于實際的最短距離，將不能保證找到一個最優的解，而當h(n)為0 沒有利用啟發信息時，A*算法就變成了Dijkstra 算法［12］;在實際中是不可能達到h(n)=h*(n)的理想狀態，但是可以讓構造的估價函數值應盡可能接近實際值。

構造精確的估價函數常用的方法是計算初始節點到目標節點間的最短路徑的長度，常用的估價函數有:

①曼哈頓距離(Manhattan distance):h(n)=abs(x-xn)+abs(y-yn)

②對角線距離:h(n)=max(abs(x-xn)，abs(y-yn))

③歐幾里德(Euclid)距離:h(n)=sqrt((x-xn)2+(y-yn)2)

上述構造的估價函數在實際應用中有著明顯的弊端，因為節點的選擇不僅僅受距離的影響，還受到很多其他因素的影響，因此，需在估價函數中加入更多的約束信息，保證算法快速準確向目標移動。為此需要在估價函數中引入距離和方向兩個因素，其啟發函數為:

其中:a 為當前節點線段與當前節點到目標節點線段的夾角;L 為歐幾里得距離;起始點(Xst，Yst)，目標點(Xend，Yend)，當前節點(Xi，Yi)，當前節點的下一節點(Xi+1，Yi+1);w1和w2是距離和角度加權值，取值范圍為0.55～0.65 與0.35～0.45。通過引入權值w1和w2，可使搜索在深度淺的地方靠啟發函數發揮作用，在深度較深的地方，搜索變為寬度優先，從而保證到達目標的最優路徑最終被找到。

3 利用A* 算法對道路網絡路徑優化

根據圖1 所建立的運輸網絡模型，運用A*算法對其進行優化。其實現步驟為:

(1)首先建立2 個表格，OPEN 表和CLOSED表;OPEN 表內存放已生成而未考察的節點;CLOSED 表記錄已訪問過的節點。

(2)將起始節點加入到OPEN 表中;選取OPEN表中沒有設置過的且有最小估價值的最佳節點放入CLOSED 表中，對最佳節點考察，如果是目標點，則成功求得一解;如果不是，則擴展之，產生后繼節點，計算后繼節點能進行選擇的價值，把與其相鄰的節點加入OPEN 表中，然后根據這個方法，完成所有節點的訪問價值排序。

(3)重復第二步，直至找到終點為止。

選取網絡中的兩點做為裝載點和卸載點，利用改進了的A*算法對網絡進行優化，在matlab 軟件中進行仿真試驗，啟發函數的值h 取不同的值，其求解的路徑相同，但是程序運行的時間有差別，當w1取0 時，程序運行時間為0.047 ms;當w1取0.6 時，運行時間為0.32 ms;當w1取1 時，運行時間為0.15 ms，其運行結果見圖2。由運行結果可知，改進的A*算法能夠提高搜索的效率，同時也可以保證找到最優解。

圖2 求解結果

4 結語

通過對運輸系統的優化，建立高效、合理的運輸系統，提高運輸效率，從而達到減少運輸卡車的數量，降低礦山運營成本的目標，本文利用A*算法，通過選擇合適的啟發信息，對運輸網絡的最短運輸路徑進行優化，并仿真求解，計算出較合理的卡車運輸路線。露天礦運輸系統是個復雜而動態的網絡，且道路條件多變，還需要選取更合適的啟發函數用以提高算法的效率，需要考慮到網絡的動態性，使其更好地解決實際問題。

［1］王純義.露天礦道路質量是影響卡車運輸能力、成本、安全的重要因素［J］.煤礦安全，2001，(1):59-61.

［2］周春輝，李詩高.Dijkstra 算法與A*算法研究［J］.軟件導刊，2007，(1):102-103.

［3］代修宇，程國中.Floyd 算法的改進與優化［J］.西昌學院學報，2012，(3):63-65.

［4］孫臣良，劉 靜.粒子群算法分析及其求解露天礦道路路徑優化問題［J］.計算機系統應用，2011，(11):142-145.

［5］史 輝，曹 聞，朱述龍，等.A*算法的改進及其在路徑規劃中的應用［J］.測繪與空間地理信息，2009，(6):208-211.

［6］駱中洲.露天采礦學［M］.北京:中國礦業學院出版社，1986:77-91.

［7］孫臣良，劉 靜.露天礦運輸道路網絡的建立及其路徑優化［J］.科技導報，2011，(9):47-51.

［8］Steven M.Lava the Planning Algorithms ［M］.Cambridge University Press，2006.

［9］Nilsson N J.Principles of Artificial Intelligence［M］.New York:Tioga Publishing Co.，1980.

［10］蔡自興，徐光佑.人工智能及其應用［M］.北京:清華大學出版社，2003.

［11］林堯瑞，馬少平.人工智能導論［M］.北京:清華大學出版社，1989.

［12］I Chabini，S Lan.Adaptations of the A*Algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks ［J］.IEEE Transactions onIntelligent Transportation Systems，2002，(3):60-74.