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

施劍烽　楊勇生

【摘 要】隨著工業(yè)的發(fā)展，自動(dòng)化碼頭已成為眾多碼頭未來(lái)發(fā)展方向，而AGV作為自動(dòng)化碼頭水平運(yùn)輸?shù)闹匾侄危找娴玫街匾暋Ｑ芯緼GV的相關(guān)技術(shù)意義重大，本文僅對(duì)AGV路徑規(guī)劃的Dijkstra算法進(jìn)行研究，以期能應(yīng)用于自動(dòng)化碼頭。

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

1 研究背景及意義

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

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

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

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

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

3 Dijkstra算法

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

Dijkstra算法的具體步驟為：

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

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

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

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

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

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

4 算法改進(jìn)及仿真驗(yàn)證

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

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

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

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

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

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

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

5 結(jié)論

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

【參考文獻(xiàn)】

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

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

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

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

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