使用改進(jìn)蟻群算法的AGV路徑規(guī)劃研究

葛志遠(yuǎn)，肖本賢

（合肥工業(yè)大學(xué)電氣與自動(dòng)化工程學(xué)院，安徽 合肥 230009）

1 引言

近年來(lái)，伴隨著倉(cāng)儲(chǔ)物流自動(dòng)化快速發(fā)展以及勞動(dòng)力成本的提高，貨物的運(yùn)輸方式正在向系統(tǒng)化，智能化的方向發(fā)展。自動(dòng)導(dǎo)引車（Automated Guided Vehicle，AGV）具有提高生產(chǎn)率和節(jié)約勞動(dòng)成本等優(yōu)點(diǎn)，因此AGV路徑規(guī)劃成為一項(xiàng)重要內(nèi)容。

目前，針對(duì)AGV路徑規(guī)劃問(wèn)題產(chǎn)生一些群智能優(yōu)化算法，如神經(jīng)網(wǎng)絡(luò)算法[1]、遺傳算法[2]、粒子群算法[3]等。蟻群算法[4]（ACO）具有并行性、正反饋性及良好的擴(kuò)充性等優(yōu)點(diǎn)，在解決路徑規(guī)劃[5]、TSP[6]等問(wèn)題都有成功的應(yīng)用。針對(duì)蟻群算法耗時(shí)長(zhǎng)，容易陷入局部最優(yōu)的缺點(diǎn)，文獻(xiàn)[7]提出一種基于蟻群算法的帶時(shí)間窗的啟發(fā)式算法，提高了收斂速度。文獻(xiàn)[8]利用遺傳算法對(duì)蟻群算法參數(shù)的組合優(yōu)化，但由于遺傳算法計(jì)算量大，效果不明顯。

在傳統(tǒng)蟻群算法基礎(chǔ)上，利用改進(jìn)的蟻群算法對(duì)AGV路徑規(guī)劃進(jìn)行了研究。

2 空間環(huán)境模型的建立

空間環(huán)境模型的建立是AGV路徑規(guī)劃的基礎(chǔ)。柵格法[9]（grid method）具有簡(jiǎn)單高效、易于實(shí)現(xiàn)、表達(dá)不規(guī)則障礙物的能力等優(yōu)點(diǎn)，所以采用柵格法建立AGV空間環(huán)境模型。

2.1 環(huán)境建模

利用柵格法將AGV所在的空間環(huán)境劃分為一個(gè)M行N列的二維平面空間，如圖1所示。柵格必須完全容納AGV，并預(yù)留安全間距，定義障礙物所占用的柵格為障礙柵格（黑色），無(wú)障礙物的柵格為可行柵格（白色），單位長(zhǎng)度為1cm且障礙物所占柵格不滿一個(gè)柵格按一個(gè)考慮，通過(guò)直角坐標(biāo)法對(duì)每個(gè)柵格進(jìn)行標(biāo)識(shí)，記為g（x，y）。將障礙柵格組成的集合用Qf表示，可行柵格組成的集合用Qt表示，則AGV路徑規(guī)劃就是在柵格圖中尋找到一條無(wú)碰最優(yōu)路徑。……