基于改進的Dijkstra算法AGV路徑規(guī)劃研究

施劍烽　楊勇生

【摘 要】隨著工業(yè)的發(fā)展，自動化碼頭已成為眾多碼頭未來發(fā)展方向，而AGV作為自動化碼頭水平運輸?shù)闹匾侄?，日益得到重視。研究AGV的相關(guān)技術(shù)意義重大，本文僅對AGV路徑規(guī)劃的Dijkstra算法進行研究，以期能應(yīng)用于自動化碼頭。

【關(guān)鍵詞】自動化碼頭；AGV；路徑規(guī)劃；Dijkstra算法

1 研究背景及意義

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

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

因此必須研究恰當(dāng)?shù)穆窂揭?guī)劃算法使AGV能實時響應(yīng)碼頭作業(yè)任務(wù)，并且盡可能的規(guī)劃出一條或者幾條最優(yōu)路徑，因此，本文對現(xiàn)有的各種算法進行歸納、總結(jié)，希望找到一種合適的算法以解決自動化碼頭AGV路徑規(guī)劃問題[4]。

2 路徑規(guī)劃技術(shù)

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

3 Dijkstra算法

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

Dijkstra算法的具體步驟為：

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

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

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

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

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

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

4 算法改進及仿真驗證

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

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

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

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

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

表2 算法仿真結(jié)果對比

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

5 結(jié)論

通過對Dijkstra算法的研究，發(fā)現(xiàn)Dijkstra算法可以應(yīng)用于自動化碼頭AGV路徑規(guī)劃，但傳統(tǒng)的Dijkstra算法不能滿足轉(zhuǎn)彎次數(shù)少、能源消耗最少等因素，因此需要對Dijkstra算法進行改進，通過對傳統(tǒng)Dijkstra算法和改進后Dijkstra算法進行MATLAB仿真驗證，驗證了改進后的Dijkstra算法的有效性，因此，改進后的Dijkstra算法可以應(yīng)用于自動化碼頭AGV路徑規(guī)劃。

【參考文獻】

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

[2]鄭見粹，李海波，謝文寧，等.自動化集裝箱碼頭裝卸工藝系統(tǒng)比較研究[J].水運科學(xué)研究，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]李海波，馬文杰，任良成.應(yīng)用自動導(dǎo)引車的港口物流系統(tǒng)的分析與比較[J].水運科學(xué)研究，2010，2：23-27.

[5]馮海雙.AGV自動運輸系統(tǒng)調(diào)度及路徑規(guī)劃研究[D].哈爾濱工業(yè)大學(xué)，2013.

[6]孫奇.AGV系統(tǒng)路徑規(guī)劃技術(shù)研究[D].浙江大學(xué)，2012.

[7]賀麗娜.AGV系統(tǒng)運行路徑優(yōu)化技術(shù)研究[D].南京航空航天大學(xué)，2011.