王　輝 ， 朱龍彪 ， 王景良 ， 陳紅艷 ， 邵小江 ， 朱志慧

(1.南通大學 機械工程學院， 江蘇 南通 226019; 2.江蘇海事職業(yè)技術(shù)學院， 江蘇 南京 211199;3.江蘇金冠立體停車股份有限公司， 江蘇 南通 226003)

?

基于Dijkstra-蟻群算法的泊車系統(tǒng)路徑規(guī)劃研究

王輝1， 朱龍彪1， 王景良2， 陳紅艷1， 邵小江1， 朱志慧3

(1.南通大學 機械工程學院， 江蘇 南通 226019; 2.江蘇海事職業(yè)技術(shù)學院， 江蘇 南京 211199;3.江蘇金冠立體停車股份有限公司， 江蘇 南通 226003)

針對智能停車庫中自動導引運輸車(automated guided vehicle， AGV)存取車路徑規(guī)劃問題，提出了一種基于Dijkstra-蟻群算法(Dijkstra-ACO)的泊車系統(tǒng)路徑規(guī)劃方法.首先利用鏈接可視圖法建立環(huán)境模型，并在此環(huán)境模型下，采用Dijkstra算法規(guī)劃出AGV的初始路徑；其次，通過引入節(jié)點隨機選擇機制、調(diào)整信息素更新方式和限定信息素閾值策略等對基本蟻群算法進行優(yōu)化改進；最后，選用改進的蟻群算法對初始路徑進行優(yōu)化.結(jié)果顯示：Dijkstra算法和混合算法均能使AGV有效避開障礙物，然后搜索到一條從起點到終點的無碰優(yōu)化路徑；與Dijkstra算法相比，混合算法能有效提高路徑搜索效率，縮短搜索路徑長度，改善搜索路徑質(zhì)量，表明該算法正確、可行及有效，且具有較強的全局搜索能力和較好的收斂性能，能夠滿足AGV存取車路徑規(guī)劃的要求.

Dijkstra算法; 蟻群算法; 泊車系統(tǒng); AGV; 路徑規(guī)劃

汽車保有量的急劇增加，致使城市交通擁擠、停車困難等社會問題不斷涌現(xiàn)，嚴重影響了市民的居住環(huán)境，因此，停車難已成為社會亟待解決的難題.而基于自動導引小車(AGV)的平面移動式智能停車庫憑借占地面積少、有效停車數(shù)量多以及智能化程度高等優(yōu)點而備受社會各界廣泛關(guān)注.研究平面移動式智能停車庫的核心，就是要解決AGV存取車路徑規(guī)劃問題.車庫路徑規(guī)劃的主要目的是讓AGV運行在有障礙物的未知環(huán)境中，根據(jù)某些評價標準(如最短時間、最短距離或最少轉(zhuǎn)彎次數(shù))，尋找一條從預存停車位到目標停車位的最優(yōu)無碰路徑，確保車輛在最短時間內(nèi)完成存取，提高停車位利用率，減少存取車等待時間，實現(xiàn)停車設(shè)備自動化管理.針對路徑規(guī)劃問題，國內(nèi)外學者已對其進行了深入研究，并相繼提出了多種算法，主要有可視圖法、圖搜索法以及人工勢場法等.隨著智能算法的不斷發(fā)展，Dijkstra算法、A*算法、遺傳算法、粒子群算法以及蟻群算法等也被廣泛用于解決各領(lǐng)域路徑規(guī)劃問題[1-2].

Dijkstra算法是一種典型的單源最短路徑算法，因其采用遍歷搜索方式求解最短路徑，故得到的最短路徑往往具有可靠性高、魯棒性好的特點，但也存在時間復雜度高、搜索效率低、占用內(nèi)存大等缺陷[3].蟻群算法是一種新型的仿生算法，該算法憑借并行性、強魯棒性、全局最優(yōu)以及易與其他啟發(fā)式算法相結(jié)合等優(yōu)點，被廣泛用于解決TSP問題、路由問題、二次分配問題以及車間調(diào)度問題等，并取得了不錯的效果[4-9].Johnson等[2]研究了蟻群算法中信息素對車輛路徑選擇的影響，仿真結(jié)果顯示在允許時間范圍內(nèi)，蟻群算法可有效解決逆向物流車輛路徑規(guī)劃問題；康冰等[4]將折返螞蟻策略應(yīng)用到蟻群算法中，極大地提高了算法的收斂速度；黃震等[8]將蟻群算法和遺傳算法進行了有效融合，通過將時間窗因素引入蟻群算法來產(chǎn)生初始種群，然后由遺傳算法對其進行交叉和變異操作，得到了更優(yōu)路徑；Chaari等[9]針對機器人在靜態(tài)環(huán)境中的路徑規(guī)劃問題，提出將蟻群算法與遺傳算法進行有效結(jié)合，并通過仿真實驗驗證了算法的可行性和有效性；王美珍等[10]將粒子群算法和蟻群算法進行了有效融合，極大地提高了算法的搜索效率，縮短了路徑長度；何少佳等[11]利用Dijkstra算法的優(yōu)點對蟻群算法進行了改進，解決了逃生路徑規(guī)劃問題.

針對AGV存取車路徑規(guī)劃問題，將Dijkstra算法和蟻群算法的優(yōu)點結(jié)合起來，提出一種基于Dijkstra-蟻群(ACO)的混合算法.利用鏈接可視圖法建立環(huán)境模型，采用Dijkstra算法規(guī)劃出AGV的初始路徑，通過節(jié)點隨機選擇機制及信息素局部更新和全局更新相結(jié)合的方式對基本蟻群算法進行優(yōu)化改進，然后選用改進的蟻群算法對初始路徑進行優(yōu)化，并通過仿真測試驗證混合算法的可行性和有效性.

1　問題描述及環(huán)境建模

1.1問題描述

為實現(xiàn)算法在AGV路徑規(guī)劃中的應(yīng)用，須對運行環(huán)境作如下假設(shè)[12]：1) 假設(shè)AGV運行環(huán)境為二維有限空間；2) 假設(shè)圖中障礙物已知，位置確定，以不規(guī)則多邊形表示，且忽略其高度方向；3) 假設(shè)AGV在運行環(huán)境中勻速行駛，忽略AGV的啟動、轉(zhuǎn)向、制動以及液壓系統(tǒng)舉升操作等因素；4) 以AGV實際尺寸為基準，適當擴大障礙范圍，為便于仿真，將AGV視為質(zhì)點.

1.2環(huán)境建模

圖1　AGV二維工作環(huán)境模型Fig.1　Two-dimensional working environment model of AGV

利用AGV自帶的攝像頭、雷達傳感器及紅外傳感器等采集AGV運行環(huán)境信息，其包括AGV的起始車位、目標車位、障礙物以及AGV待充電位置等，根據(jù)上述信息通過鏈接可視圖法創(chuàng)建AGV運行環(huán)境模型.圖1所示為采用鏈接可視圖法在MATLAB環(huán)境下創(chuàng)建的環(huán)境模型，模型規(guī)格為250 m×250 m，模型用6個黑色凸多邊形表示障礙物區(qū)域.圖中各障礙物區(qū)域以及邊界區(qū)域頂點之間的虛線為自由鏈接線，黑色實線為AGV的可行路徑，以V開頭的序列數(shù)代表各鏈接線的中點，S和T為AGV的起點和終點位置.

1.3建立目標函數(shù)

在智能停車庫中，AGV路徑規(guī)劃的任務(wù)是根據(jù)當前位置以及存取車位置，在有效避開障礙物的前提下，快速找到一條自起點(車位預存取位置或目標停車位)至目標點(目標停車位或車位預存取位置)的無障礙最優(yōu)路徑，并確保該路徑長度最短[13]：

Length=min{Length(iter,m)}，

(1)

式中:iter表示迭代次數(shù)，iter∈{1， 2， 3， … ，n}；Length(iter，m)表示在混合算法搜索過程中，第m只螞蟻在第iter次迭代中所走過的路徑長度.

2　Dijkstra算法規(guī)劃初始路徑

2.1初始路徑

E.W.Dijkstra提出的Dijkstra算法具有最短路徑可靠性高和魯棒性好的特點，被廣泛用于求解路徑規(guī)劃中任意兩點間最短路徑.基于此，文中采用該算法規(guī)劃了AGV從起點S到目標點T的初始路徑，算法實現(xiàn)流程如下[14]：

Step1：根據(jù)圖1可行路徑，計算各節(jié)點間距離并建立權(quán)值鄰接矩陣D，對于不連通節(jié)點間的權(quán)值可賦值inf (無窮大)；

Step2：初始化參數(shù)，令D(V1，V1)=0，D(V1，Vj)=w1j(j=2， 3， …，n)，建立空表R和Q，并把圖中節(jié)點分別放入R和Q中，R={V1}，Q={V2，V3， …，Vn}；

Step3：在Q中尋找一頂點Vk，使D(V1，Vk)=min{D(V1，Vj)}，Vj∈Q，將Vk加入R中.判斷R=?是否成立，若是，則算法終止，否則算法轉(zhuǎn)入Step4；

Step4：根據(jù)節(jié)點k修正D(V1，Vj)，令D(V1,Vj)=min{D(V1，Vj)，D(V1，Vk)+wkj}，然后轉(zhuǎn)入Step3；

Step5：重復Step3和Step4，即可計算出AGV從起點到其他節(jié)點間的路徑長度，然后反向追蹤即可得到起點至目標點的最短路徑.

圖2所示黑色粗實線為利用Dijkstra算法規(guī)劃的初始路徑：S→V1→V2→V3→V4→V5→V6→V9→V10→V11→V12→T，最短路徑長度為319.628 1 m.

圖2　Dijkstra算法規(guī)劃出的AGV初始路徑Fig.2　The initial path of AGV planned with Dijkstra algorithm

2.2空間解表示

采用Dijkstra算法規(guī)劃了AGV初始路徑，該路徑依次通過節(jié)點S，P1，P2，…，Pd和T，在此基礎(chǔ)上，對初始路徑所經(jīng)過的自由鏈接線Li進行定長分段處理，定長設(shè)為δ，各條鏈接線上的分段數(shù)可由式(2)確定[15]：

(2)

蟻群算法在初始路徑所經(jīng)過的鏈接線Li上，尋找一組優(yōu)化參數(shù)組合(λ1，λ2， …，λd)，確保鏈接線上各分點坐標能夠滿足方程(3)，便可在離散化的空間中得到一條新的優(yōu)化路徑：

λi∈[0, 1],i=1, 2, …, d，

(3)

式中:Pi(0)和Pi(1)代表鏈接線Li的2個端點;λi表示鏈接線比例參數(shù);d表示鏈接線劃分節(jié)點數(shù).

3　蟻群算法設(shè)計

3.1傳統(tǒng)蟻群算法

傳統(tǒng)蟻群算法的基本原理是：螞蟻在覓食過程中，各螞蟻間通過遺留在路線上的信息素相互傳遞信息并根據(jù)信息素強度的高低來指引下一步行進方向，基于這種正反饋機制，最終搜索出一條最短路徑[16].通常情況下，食物周圍環(huán)境是未知的，在選擇路徑時，螞蟻需要根據(jù)轉(zhuǎn)移概率pij來確定，狀態(tài)轉(zhuǎn)移概率可由式(4)計算得到：

(4)

式中:allowedk={0，1，…,n-1}表示下一步允許選擇的節(jié)點集合；τij(t)表示在t時刻螞蟻k遺留在路徑(i，j)上的信息素；ηij表示距離啟發(fā)函數(shù)因子，通常用ηij=1/dij表示，dij表示節(jié)點i,j間的距離；α為螞蟻信息素軌跡的相對重要性因子；β為啟發(fā)函數(shù)的相對重要性因子.

隨著時間的推移，螞蟻遺留在路線上的信息素會逐漸揮發(fā)丟失，為避免因信息素量過多或過少而影響螞蟻節(jié)點選擇，在螞蟻完成1次循環(huán)后，須通過式(5)對可行路徑上的信息素進行調(diào)整：

τij(t+1)=ρτij(t)+Δτij(t,t+1),

(5)

(6)

(7)

3.2改進蟻群算法

在AGV存取車路徑規(guī)劃中，選用傳統(tǒng)蟻群算法雖然能夠使AGV規(guī)劃出一條從起始位置到目標位置的強魯棒性優(yōu)化路徑，但依然存在諸多不足，表現(xiàn)為全局搜索能力弱、收斂速度慢、搜索效率較低、易出現(xiàn)早熟或停滯以及易陷入局部最優(yōu)等.針對上述問題，通過節(jié)點隨機選擇機制及信息素局部更新和全局更新相結(jié)合的方式對基本蟻群算法進行改進.

3.2.1節(jié)點選擇策略

當螞蟻在鏈接線Li上移動時，為提高節(jié)點選擇多樣性，避免陷入局部最優(yōu)，采用隨機選擇機制選擇下一鏈接線Li+1上的節(jié)點，具體計算方法如式(8)所示[17].當節(jié)點j需在q>q0的條件下確定時，則應(yīng)先計算節(jié)點i到節(jié)點j的轉(zhuǎn)移概率pij，在此基礎(chǔ)上，再采用輪盤賭法確定下一節(jié)點j.

(8)

式中：pij表示螞蟻由節(jié)點i向節(jié)點j轉(zhuǎn)移的概率；ηik為距離啟發(fā)函數(shù)因子；τik表示鏈接線(i，k)上的信息素；allowedi表示下一步允許選擇的節(jié)點集合，i表示鏈接線上所有分節(jié)點集合；q為隨機變量，q∈[0， 1]；q0為可調(diào)參數(shù)，q0∈[0， 1].

3.2.2信息素更新策略

為進一步增強算法的全局搜索能力，加快收斂速度，提高搜索效率，提出了局部更新和全局更新相結(jié)合的信息素更新方式.

1)局部更新.在路徑搜索中，當螞蟻每經(jīng)過一條鏈接線(i，j)時，都需利用式(9)更新剛經(jīng)過的鏈接線：

τij(t+1)=(1-ρ)τij(t)+ρτ0,

(9)

式中:τ0為初始條件下的信息素;ρ表示信息素揮發(fā)系數(shù)，取值范圍為[0， 1].

2)全局更新.當所有螞蟻在完成本次迭代路徑搜索后，選取本次迭代所有路徑中長度最短的一條，并對該條路徑上每一點的信息素進行全局更新，信息素更新可按照式(10)計算：

τij(t+1)=(1-ρ)τij(t)+ρΔτij(t,t+1),

(10)

(11)

式中:Δτij為全局更新中螞蟻留在路徑(i，j)上的信息素增量；Lh表示本次迭代所有螞蟻搜索到的最優(yōu)路徑長度.

3)信息素閾值限定.采用上述信息素更新策略雖然能夠提高最優(yōu)解的質(zhì)量和算法的搜索效率，但也可能導致算法出現(xiàn)過早收斂的問題，基于此，提出通過引入信息素閾值限定策略來解決蟻群算法的過早收斂問題.在算法的每次迭代中，全局更新最優(yōu)路徑上信息素閾值的上下界可由下式確定[18-19]：

(12)式中τmax和τmin分別表示信息素濃度的最大值和最小值.

3.3算法具體實施步驟

Step1：采用鏈接可視圖法建立環(huán)境模型；

Step2：利用Dijkstra算法規(guī)劃出一條AGV從起點至終點的初始路徑；

Step3：蟻群算法參數(shù)初始化；

Step4：蟻群算法開始搜索，螞蟻根據(jù)當前節(jié)點位置i按照式(8)選擇下一節(jié)點j；

Step5：下一節(jié)點j確定后，螞蟻需對剛走過的路徑(i，j)上的信息素進行局部更新；

Step6：判斷螞蟻是否到達終點，若是，則轉(zhuǎn)至Step7，否則轉(zhuǎn)至Step4；

Step7：統(tǒng)計當前m只螞蟻搜索到的最優(yōu)路徑，選出其中長度最短的一條，將其代入式(10)和式(11)，更新全局信息素；

Step8：判斷迭代次數(shù)是否滿足iter≤NC，若是，則轉(zhuǎn)至Step4，否則程序結(jié)束，輸出結(jié)果.

4　仿真實驗分析

為驗證混合算法在AGV存取車路徑規(guī)劃中的可行性和有效性，采用MATLAB對Dijkstra算法和混合算法進行仿真測試.AGV運行環(huán)境模型如圖1所示，算法中各參數(shù)設(shè)置如下：α=1，β=2.5，τ0=0.00 008，ρ=0.1，q0=0.9，螞蟻數(shù)量m=20，最大迭代次數(shù)NC=500.上述2種算法仿真結(jié)果如圖3至圖6所示.

圖3　AGV從起始點S到目標點T的路徑軌跡迭代圖Fig.3　Path trajectory iteration graph of AGV from the starting point S to the target point T

圖3至圖6分別表示不同路徑規(guī)劃要求下，AGV存取車路徑運行軌跡迭代圖.圖3表示AGV從起始點S到目標點T的路徑軌跡迭代圖，圖4表示AGV從S到V13的路徑軌跡迭代圖，圖5表示AGV從S到V24的路徑軌跡迭代圖，圖6表示AGV從S到V26的路徑軌跡迭代圖.上述圖形中的(a)圖表示AGV運行路徑仿真曲線圖，(b)圖表示算法的路徑迭代曲線圖.在圖(a)中，粗實線表示AGV在Dijkstra算法下的存取車運行軌跡，粗虛線表示AGV在Dijkstra-ACO混合算法下的運行軌跡.圖(b)中實線表示Dijkstra算法下AGV的路徑迭代變化曲線，虛線表示Dijkstra-ACO算法下AGV的路徑迭代變化曲線.分析圖3至圖6可知，上述2種算法均能使AGV在存取車過程中有效避開障礙物，然后搜尋到一條從預存泊車位到目標泊車位的無碰優(yōu)化路徑.

圖5　AGV從起始點S到目標點V24的路徑軌跡迭代圖Fig.5　Path trajectory iteration graph of AGV from the starting point S to the target point V24

圖6　AGV從起始點S到目標點V26的路徑軌跡迭代圖Fig.6　Path trajectory iteration graph of AGV from the starting point S to the target point V26

對比表1數(shù)據(jù)，結(jié)合圖3至圖6可知，在路徑長度方面，當AGV從起始點S到目標點T運行時，采用Dijkstra算法規(guī)劃的路徑長度為319.628 1 m，Dijkstra-ACO算法規(guī)劃的為264.266 5 m，Dijkstra-ACO算法比Dijkstra算法減少了55.361 6 m；當AGV從起始點S到目標點V13運行時，采用Dijkstra算法規(guī)劃的路徑長度為237.208 5 m，Dijkstra-ACO算法規(guī)劃的為195.779 8 m，Dijkstra-ACO算法比Dijkstra算法減少了41.428 7 m；當AGV從起始點S到目標點V24運行時，采用Dijkstra算法規(guī)劃的路徑長度為300.848 7 m，Dijkstra-ACO算法規(guī)劃的為279.922 9 m，Dijkstra-ACO算法比Dijk-stra算法減少了20.925 8 m；當AGV從起始點S到目標點V26運行時，采用Dijkstra算法規(guī)劃的路徑長度為301.029 1 m，Dijkstra-ACO算法規(guī)劃的為282.294 5 m，Dijkstra-ACO算法比Dijkstra算法減少了18.734 6 m.在路徑平滑度方面，與Dijkstra算法相比，Dijkstra-ACO算法規(guī)劃的路徑具有較好的平滑度.在收斂代數(shù)方面，當S→T時，Dijkstra-ACO算法在第81代開始收斂；當S→V13時，Dijkstra-ACO算法在第28代開始收斂；當S→V24時，Dijkstra-ACO算法在第18代開始收斂；當S→V26時，Dijkstra-ACO算法在第21代開始收斂.

綜上分析可知，在S到T，S到V13，S到V24及S到V26的存取車路徑規(guī)劃中，

AGV采用Dijkstra-

ACO算法搜索得到的路徑的平滑度和長度均明顯優(yōu)于Dijkstra算法.另外，從圖中迭代曲線變化情況可以看出，Dijkstra-ACO算法具有較快的搜索速度、較高的搜索效率和較短的搜索路徑長度.

5　結(jié)　論

針對智能車庫AGV存取車路徑規(guī)劃問題，提出了一種混合算法(Dijkstra-ACO算法)，根據(jù)MATLAB軟件仿真測試結(jié)果，可得如下結(jié)論：混合算法能夠使AGV在存取車過程中有效避開障礙物，然后搜尋到一條無碰優(yōu)化路徑；與Dijkstra算法相比，混合算法規(guī)劃的路徑長度和路徑質(zhì)量明顯優(yōu)于Dijkstra算法；收斂圖顯示混合算法具有較好的收斂性、較快的搜索速度、較高的搜索效率以及較短的搜索路徑長度等優(yōu)點.

表1　2種算法運行結(jié)果

[1] 萬曉鳳，胡偉，方武義，等.基于改進蟻群算法的機器人路徑規(guī)劃研究[J].計算機工程與應(yīng)用，2014，50(18): 63-66．

WAN Xiao-feng， HU Wei， FANG Wu-yi， et al. Research on path planning of robot based on improved ant colony algorithm[J]. Computer Engineering and Applications， 2014， 50(18): 63-66．

[2] JOHNSON F， VEGA J， CABRERA G. Ant colony system for a problem in reverse logistic[J]. Studies in Informatics and Control， 2015， 22(2): 133-140．

[3] 王樹西，李安渝.Dijkstra算法中的多鄰接點與多條最短路徑問題[J].計算機科學， 2014， 41(6): 217-224．

WANG Shu-xi， LI An-yu. Multi-adjacent-vertexes and multi-shortest-paths problem of Dijkstra algorithm[J]. Computer Science， 2014， 41(6): 217-224．

[4] 康冰，王曦輝，劉富.基于改進蟻群算法的搜索機器人路徑規(guī)劃[J].吉林大學學報(工學版)， 2014， 44(4): 1062-1068．

KANG Bing， WANG Xi-hui， LIU Fu. Path planning of searching robot based on improved ant colony algorithm[J]. Journal of Jilin University (Engineering and Technology Edition)， 2014， 44(4): 1062-1068．

[5] JIANG Kai， LI Chun-gui. Path planning of robot based on ant colony algorithm[C]. Paris: Atlantis Press， 2015: 757-761．

[6] WANG Jin-guo， WANG Na， JIANG Hui-yu. Robot global path planning based on improved ant colony algorithm[C]. Paris: Atlantis Press， 2015: 2099-2102．

[7] BRAND M， MASUDA M， WEHNER N， et al. Ant colony optimization algorithm for robot path planning[C]. Washington: IEEE Computer Society， 2010: 3436-3440.

[8] 黃震，羅中良，黃時慰.一種帶時間窗車輛路徑問題的混合蟻群算法[J].中山大學學報(自然科學版)， 2015， 54(1): 41-46．

HUANG Zhen， LUO Zhong-liang， HUANG Shi-wei. Application research of hybrid ant colony algorithm in vehicle routing problem with time windows[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni， 2015， 54(1): 41-46．

[9] CHAARI I， KOUBAA A， TRIGUI S, et al. Smart path: an efficient hybrid ACO-GA algorithm for solving the global path planning problem of mobile robots[J]. International Journal of Advanced Robotic System， 2014， 11(11): 399-412．

[10] 王美珍，劉學軍，吳勇，等.基于可定位視頻的電子導游系統(tǒng)[J].測繪通報，2011(2): 48-51.

WANG Mei-zhen， LIU Xue-jun， WU Yong， et al. Design of tour guide map based on locatable video[J]. Bulletin of Surveying and Mapping， 2011(2): 48-51．

[11] 何少佳，史劍清，王海坤.基于改進蟻群粒子群算法的移動機器人路徑規(guī)劃[J].桂林理工大學學報， 2014， 34(4): 765-770．

HE Shao-jia， SHI Jian-qing， WANG Hai-kun. Path planning for mobile robot based on improved ant colony and particle swarm optimization[J]. Journal of Guilin University of Technology， 2014， 34(4): 765-770.

[12] 李青欣.自動導引車路徑規(guī)劃的遺傳算法研究[D].廣州:廣東工業(yè)大學自動化學院，2011: 12-18.

LI Qing-xin. Research on genetic algorithm for automated guided vehicle path planning problem[D]. Guangzhou: Guangdong University of Technology， College of Automation， 2011: 12-18．

[13] 黃月，吳成東，董晶晶，等.基于WSN的災(zāi)難現(xiàn)場最優(yōu)逃生路徑規(guī)劃[J].東北大學學報(自然科學版)，2013， 34(2): 162-165．

HUANG Yue， WU Cheng-dong， DONG Jing-jing， et al. WSN-based optimal path planning for escaping from disaster scene[J]. Journal of Northeastern University (Natural Science)， 2013， 34(2): 162-165．

[14] 李明.詳解MATLAB在最優(yōu)化計算中的應(yīng)用[M].北京:電子工業(yè)出版社，2011: 340-362．

LI Ming. The application of MATLAB in the optimal calculation[M]. Beijing: Publishing House of Electronics Industry， 2011: 340-362.

[15] 金純，王升剛，尹遠陽.礦井中多機器人搜救系統(tǒng)路徑規(guī)劃[J].機床與液壓， 2014， 42(15): 10-14．

JIN Chun， WANG Sheng-gang， YIN Yuan-yang. Path planning for multi-robot rescue system under coal mine[J]. Machine Tool & Hydraulics， 2014， 42(15): 10-14．

[16] 王沛棟，唐功友，李揚.帶容量約束車輛路由問題的改進蟻群算法[J].控制與決策，2012， 27(11): 1633-1638．

WANG Pei-dong， TANG Gong-you， LI Yang. Improved ant colony algorithm for capacitated vehicle routing problems[J]. Control and Decision， 2012， 27(11): 1633-1638．

[17] CHEN Xiong， KONG Ying-ying， FANG Xiang， et al. Fast two-stage ACO algorithm for robotic path planning[J]. Neural Computing and Applications， 2013， 22(2): 313-319．

[18] 談曉勇，林鷹.基于改進遺傳蟻群算法的災(zāi)后救援路徑規(guī)劃[J].計算機工程與設(shè)計， 2014， 35(7): 2526-2530．

TAN Xiao-yong， LIN Ying. Study of disaster relief path planning based on improved genetic ant colony hybrid algorithm[J]. Computer Engineering and Design， 2014， 35(7): 2526-2530.

[19] 屈鴻，黃利偉，柯星.動態(tài)環(huán)境下基于改進蟻群算法的機器人路徑規(guī)劃研究[J].電子科技大學學報， 2015， 44(2): 260-265．

QU Hong， HUANG Li-wei， KE Xing. Research of improved ant colony based robot path planning under dynamic environment[J]. Journal of University of Electronic Science and Technology of China， 2015， 44(2): 260-265．

Research on path planing of parking system based on Dijkstra-Ant colony hybrid algorithm

WANG Hui1， ZHU Long-biao1， WANG Jing-liang2， CHEN Hong-yan1，SHAO Xiao-jiang1， ZHU Zhi-hui3

(1. School of Mechanical Engineering， Nantong University， Nantong 226019， China; 2. Jiangsu Maritime Institute， Nanjing 211199， China; 3. Jiangsu Jinguan Solid Parking System Engineering Co.， Ltd.， Nantong 226003， China)

Aiming at path planning problem of AGV accessing cars in intelligent solid garage， a hybrid algorithm is proposed by combining Dijkstra algorithm with ant colony algorithm. Firstly， Link Method was used to establish environment model of AGV， Dijkstra algorithm was applied to plan the initial path of AGV. Then， with the methods of nodes random selection mechanism and the combination of local renewal and global renewal of the pheromone， the traditional ant colony algorithm was optimized and improved. Finally， the initial path planned by Dijkstra algorithm was optimized by improved ant colony algorithm. The simulation results showed that the optimized path from starting point to ending point could be attained with Dijkstra algorithm and Dijkstra-Ant colony algorithm on the premise of effectively avoiding obstacles. Moreover， compared with Dijkstra algorithm， Dijkstra-Ant colony algorithm could effectively raise search efficiency， shorten the search path length， and improve the quality of search path. The results indicate that Dijkstra-Ant colony hybrid algorithm is correct， feasible and effective， and simultaneously exhibits stronger global search ability and better convergence performance， and can meet the requirement of AGV accessing cars in path planning．

Dijkstra algorithm; ant colony algorithm; parking system; AGV; path planning

2016-02-23.

國家自然科學基金資助項目(51405246);江蘇省產(chǎn)學研聯(lián)合創(chuàng)新基金資助項目(BY2014081-07);南通市重點實驗室項目(CP2014001).

王輝(1989—),男,河南周口人,碩士,從事機械設(shè)備可靠性分析、機電控制和智能算法等研究,E-mail: whzl2014@126.com.http://orcid.org//0000-0002-0563-5801

朱龍彪,男,江蘇如皋人，教授,碩士，從事機電控制和故障診斷等研究, E-mail:zhulb@ntu.edu.cn.

10.3785/j.issn. 1006-754X.2016.05.012

TP 301.6

A

1006-754X(2016)05-0489-08

本刊網(wǎng)址·在線期刊：http://www.zjujournals.com/gcsjxb

http://orcid.org//0000-0002-9913-5348