基于改進的Dijkstra算法AGV路徑規劃研究

施劍烽　楊勇生

【摘 要】隨著工業的發展，自動化碼頭已成為眾多碼頭未來發展方向，而AGV作為自動化碼頭水平運輸的重要手段，日益得到重視。研究AGV的相關技術意義重大，本文僅對AGV路徑規劃的Dijkstra算法進行研究，以期能應用于自動化碼頭。

【關鍵詞】自動化碼頭；AGV；路徑規劃；Dijkstra算法

1 研究背景及意義

隨著經濟一體化、全球化趨勢的發展，集裝箱碼頭在全球航運中的地位愈加重要，集裝箱碼頭之間的競爭也日趨激烈，提高碼頭的工作效率成為集裝箱碼頭不斷改進和完善的目標。因此許多發達國家提出建設自動化集裝箱碼頭（簡稱“自動化碼頭”）的方案[1]。

自動化碼頭比傳統碼頭更加安全、管控更加全面、極大降低人力成本等[2]。因此，國內外學者著手研究如何提高自動化碼頭水平運輸環節效率，而自動化碼頭中的水平運輸環節主要由AGV、岸橋、場橋組成。如圖1所示，是銜接岸橋作業和場橋作業的中轉區域。但隨著技術的改進，岸橋、場橋裝卸能力得到提升，因此AGV的運輸效率將日益成為影響自動化碼頭作業效率重要因素，決定了碼頭的整體作業效率[3]。

因此必須研究恰當的路徑規劃算法使AGV能實時響應碼頭作業任務，并且盡可能的規劃出一條或者幾條最優路徑，因此，本文對現有的各種算法進行歸納、總結，希望找到一種合適的算法以解決自動化碼頭AGV路徑規劃問題[4]。

2 路徑規劃技術

AGV路徑規劃是在地圖中按照路徑最短評價指標搜索出一條從起始節點到目標節點的最優或次優的路徑，即f（n）=∑w。由于設定AGV速度不變，因此等價于考慮AGV最短路徑的問題。目前常見的AGV 路徑規劃算法主要有人工勢場法、Dijkstra算法、A*算法等[5]，本文僅對Dijkstra算法進行研究及改進，使之能應用于自動化碼頭。

3 Dijkstra算法

Dijkstra算法是圖論G=（V，E）中的求解兩點之間最短路徑的算法[6]，其中V代表節點集合，E代表邊的集合。它的搜索方式是從初始節點開始逐層向外搜索，直到所有節點都被搜索到，然后進行比較最終確定最短路徑[7]。

Dijkstra算法的具體步驟為：

1）首先，集合S中只包含源節點S0，U包含除去S0之外的其他所有節點。

2）從U中選取與S0相鄰連接的Sk，把Sk添加到S中，最短路徑就是S0-Sk。

3）以Sk為新的中間節點，評估U中與Sk連接的節點。若從源點S0經過Sk再到U中節點Sk+1的距離比從源點S0不經過Sk再到U中節點Sk+1的距離短，則路徑中的Sk的下一節點為Sk+1，把路徑S0-Sk-Sk+1更新到集合E中。同時Sk+1加入集合S。

4）重復以上過程直至所有節點都加入集合S。最終由這些節點所連成的路徑即為最短路徑。

以圖2中的節點圖為模型，表1展示了從A點搜索到各點的最短路徑的步驟。

通過以上算法過程，可以發現Dijkstra算法在搜索最短路徑問題上表現良好，因此可以考慮應用在自動化碼頭。但明顯發現Dijkstra算法搜索范圍大，基本遍歷所有路徑，雖然能搜索到最優解，但搜索時間長、效率低。因此需要對Dijkstra算法進行改進。

4 算法改進及仿真驗證

對于改進Dijkstra算法，以便能應用于自動化碼頭，本文以圖3某自動化碼頭AGV作業區域模型為例，圖中中每一條邊都為80米，然后進行算法改進研究。

如下所示為使用Dijkstra算法在上圖3所示電子地圖中搜索節點V1到節點V10的路徑結果。

Dijkstra算法一共生成6條可選路徑，對于如果中間節點更多的情況下就搜索的可選路徑更多，對系統的響應比較慢，因此有必要對Dijkstra算法進行改進。

由于AGV在行駛過程中，多次轉彎會比直線行駛時間消耗、能源消耗都多，因此本文采用在之前的評價f（n）=∑w中添加轉彎次數代價因素∑h，能源消耗代價因素∑p，路徑通暢度∑q，即f（n）=∑w+∑h +∑p+∑q。每當AGV多轉彎一次，整個系統的時間相應就越長，能源消耗越大，通過改進的Dijkstra算法重新對節點V1到節點V10進行路徑規劃，得出新的路徑結果。

新的可選路徑只有2條，減少了轉彎次數，提高了算法的效率，增強了系統的響應能力。在MATLAB中分別對Dijkstra算法和改進的Dijkstra算法進行仿真，搜索從V1點到V18的AGV最優路徑，比較這兩種算法搜索的路徑長度、轉彎次數，數據如表2所示。

表2 算法仿真結果對比

可以看出Dijkstra算法搜索到11條備選最短路徑，但存在多條備選路徑時，所走的路徑不盡相同。但是通過觀察改進的Dijkstra算法搜索到的路徑可以發現，改進的Dijkstra算法搜索到的路徑的轉彎次數最少，即只有1次轉彎，軌跡明顯優于其他備選路徑，且提高了路徑搜索效率。

5 結論

通過對Dijkstra算法的研究，發現Dijkstra算法可以應用于自動化碼頭AGV路徑規劃，但傳統的Dijkstra算法不能滿足轉彎次數少、能源消耗最少等因素，因此需要對Dijkstra算法進行改進，通過對傳統Dijkstra算法和改進后Dijkstra算法進行MATLAB仿真驗證，驗證了改進后的Dijkstra算法的有效性，因此，改進后的Dijkstra算法可以應用于自動化碼頭AGV路徑規劃。

【參考文獻】

[1]田洪，吳富生.自動化碼頭的發展現狀及趨勢[C].物流工程三十年技術創新發展之道，中國鐵道出版社，2010：232-236.

[2]鄭見粹，李海波，謝文寧，等.自動化集裝箱碼頭裝卸工藝系統比較研究[J].水運科學研究，2011，2：26-33.

[3]Héctor J. Carloa，， Iris F.A. Visb ， Kees Jan Roodbergenb. Transport operations in container terminals： Literature overview， trends， research directions and classification scheme[J]. European Journal of Operational Research， 2014， 236： 1-13.

[4]李海波，馬文杰，任良成.應用自動導引車的港口物流系統的分析與比較[J].水運科學研究，2010，2：23-27.

[5]馮海雙.AGV自動運輸系統調度及路徑規劃研究[D].哈爾濱工業大學，2013.

[6]孫奇.AGV系統路徑規劃技術研究[D].浙江大學，2012.

[7]賀麗娜.AGV系統運行路徑優化技術研究[D].南京航空航天大學，2011.