基于混合蟻群粒子群的多AGV路徑規(guī)劃研究

魏宏源，茅 健

（上海工程技術(shù)大學(xué) 機(jī)械工程學(xué)院，上海 201620）

0 引言

近年來，工業(yè)4.0戰(zhàn)略規(guī)劃在促使整個(gè)工業(yè)生產(chǎn)體系進(jìn)入全新的水平。作為工業(yè)4.0的核心組成部分，智能物流是連接客戶、供應(yīng)鏈和制造業(yè)的重要環(huán)節(jié)，也是構(gòu)建未來智能工廠的基石[1,2]，自動(dòng)導(dǎo)引運(yùn)輸車（AGV）是智能物流中重要設(shè)備之一[3]。其路徑的好壞決定了倉庫的運(yùn)作效率，因此對(duì)AGV路線的規(guī)劃也成為了研究熱點(diǎn)，國內(nèi)外學(xué)者已經(jīng)做出了很多貢獻(xiàn)。

劉高強(qiáng)[4]等人通過引入變異算子優(yōu)化遺傳算法，對(duì)AGV的路徑分配進(jìn)行優(yōu)化，得到了更為優(yōu)化的小車路徑。湯旻安[5]等人利用改進(jìn)的量子微粒群算法，克服了傳統(tǒng)算法陷入局部最優(yōu)的問題，對(duì)小車路徑優(yōu)化提出了改進(jìn)。王娜[6]以VB6.0為開發(fā)系統(tǒng)，混合Matlab編程解決了AGV在路口的交互碰撞問題。王立春[7]等人結(jié)合實(shí)際情況，在A*算法中引入拐彎系數(shù)，提高了實(shí)際運(yùn)行效率。WaldemarMa.opolski[8]把制造系統(tǒng)的資源數(shù)量和AGV的數(shù)量作為優(yōu)化的對(duì)象，利用軟件模擬對(duì)AGV的數(shù)量與成本進(jìn)行了優(yōu)化。Spyros A. Reveliotis[9]對(duì)傳統(tǒng)的無沖突小車路徑進(jìn)行優(yōu)化，針對(duì)AGV資源分配系統(tǒng)的類別開發(fā)了一種適合的結(jié)構(gòu)控制策略。S. RAJOTIA[10]等人應(yīng)用Dijkstra算法尋找車輛最不擁堵的最快路線，并且對(duì)雙向流動(dòng)路徑進(jìn)行了仿真研究，所提出的策略有助于減少車輛阻塞時(shí)間，提高系統(tǒng)的吞吐量潛力。

本文根據(jù)立體庫的實(shí)際情況，基于混合蟻群粒子群方法，建立了多臺(tái)AGV小車路徑快速分配與優(yōu)化模型，對(duì)多AGV小車路徑優(yōu)化問題進(jìn)行研究，結(jié)果表明該方法可以加快AGV小車在倉庫運(yùn)輸?shù)乃俣?，提高智能倉儲(chǔ)的物流傳輸效率。

1 問題描述與建模

一般情況下，在立體貨倉中，產(chǎn)品由滾筒線推送至分道口，觸發(fā)AGV小車搬運(yùn)貨物至立體倉庫中，整個(gè)過程可以細(xì)分為滾筒線運(yùn)輸貨物，觸發(fā)光電開關(guān)分配小車任務(wù)，小車搜尋路徑將貨物送至倉庫中，如圖1所示。

圖1 立體倉庫入口

AGV小車在接收到任務(wù)后，首先由起始位置到接受貨物位置，然后從接受貨物位置送貨至指定貨架，最后回到原來車庫中。第一步任務(wù)中為單一路徑，優(yōu)化空間較少；第二步中為已知起點(diǎn)與終點(diǎn)的路徑尋優(yōu)問題。若利用傳統(tǒng)的A*算法進(jìn)行路徑優(yōu)化，會(huì)出現(xiàn)車輛排隊(duì)，相互管制等問題，而且AGV的路線利用率較低。在以往AGV的路徑尋優(yōu)中，這種問題被歸屬于旅行商問題，即希望小車在到達(dá)貨架后回到原來的車庫，走過的路徑最短。

在路徑優(yōu)化中，為了排除一些外界因素的影響，模型首先需要有以下假設(shè)：

1）車間的AGV總數(shù)為定量，忽略AGV的一些硬件故障問題。

2）路線的起終點(diǎn)已知，倉庫中地圖已知。

3）分配任務(wù)或者下達(dá)指令后無網(wǎng)絡(luò)延遲問題，小車及時(shí)響應(yīng)控制系統(tǒng)下達(dá)的命令。

4）所有AGV的起點(diǎn)均在充電樁或者車庫，而且在運(yùn)行中速度相同。

現(xiàn)在假設(shè)車間中有x輛AGV（x≥5），同時(shí)發(fā)出的任務(wù)數(shù)為k，每輛AGV為了完成任務(wù)都要走不同的路程。而且對(duì)于不同的任務(wù)，對(duì)應(yīng)的路線也不一樣。設(shè)Dmn為第m（m≤x）輛車執(zhí)行第n（n≤k）個(gè)任務(wù)所要走的距離。AGV路徑優(yōu)化的目標(biāo)在于使得這k個(gè)距離之和為最小值，目標(biāo)函數(shù)如式(1)所示。同時(shí)，模型還需要滿足同一時(shí)間一輛AGV僅有一個(gè)任務(wù),這個(gè)可以在AGV控制系統(tǒng)中實(shí)現(xiàn)。同時(shí)對(duì)于多臺(tái)AGV調(diào)度，在執(zhí)行相近任務(wù)的時(shí)候每輛車的路徑不能相同，如式(2)所示。

多AGV路徑優(yōu)化可視為一種特殊的旅行商問題（TSP），它也是組合優(yōu)化中的一個(gè)困難的NP問題。如果不能很好的處理該問題，會(huì)導(dǎo)致車輛互鎖，甚至碰撞等問題，如圖2所示。1號(hào)AGV與2號(hào)AGV由于路徑規(guī)劃不好，面對(duì)面的行駛，最終兩輛車發(fā)生互鎖，都無法繼續(xù)行駛。

因此，本文基于混合蟻群粒子群算法，提出了一種優(yōu)化算法，改善AGV小車的路徑規(guī)劃問題，同時(shí)根據(jù)現(xiàn)場規(guī)劃找出合適的返回路線，避免交通異常。

2 混合蟻群粒子群算法

2.1 蟻群算法

蟻群優(yōu)化算法（ACO）[11]是由意大利學(xué)者Dorigo M提出的一種模仿螞蟻覓食的新興群智能算法。該方法利用螞蟻在路上留下的信息素含量來判斷路徑的優(yōu)化程度，具有正反饋與分布協(xié)作式的特點(diǎn)。

一般地，蟻群算法表述為：初始時(shí)刻有m個(gè)螞蟻隨機(jī)分布，并保證沒有螞蟻在同一位置。設(shè)在0時(shí)刻，各條路徑上的信息素量τij（0）=const（const為常數(shù)），螞蟻n（n=1，2，…，m）根據(jù)不同路上所含有的信息素含量決定路線。同時(shí)為了避免路徑重復(fù)，往往在運(yùn)動(dòng)過程中使用禁忌表Ttabu記錄當(dāng)前螞蟻?zhàn)哌^的位置，先假設(shè)t時(shí)刻，螞蟻n從位置i轉(zhuǎn)移到位置j根據(jù)狀態(tài)轉(zhuǎn)移概率（t）決定；

式(4)中τij（t+n）為信息素更新函數(shù)， 1-ρ為信息素殘留因子，ρ∈（0，1）； Δτij（t）表示螞蟻在經(jīng)過路徑（i，j）時(shí)在本次循環(huán)中的信息素增加量。當(dāng)t=0時(shí)Δτij（t）=0。

圖2 AGV互鎖現(xiàn)象

2.2 粒子群算法

粒子群算法（PSO）是一種基于鳥群智能的隨機(jī)優(yōu)化技術(shù)，也叫做鳥群算法，該算法具有群體智能、內(nèi)在并行性、迭代格式簡單、可快速收斂到最優(yōu)解等優(yōu)點(diǎn)[12]。PSO算法的優(yōu)勢(shì)在于可以較為簡便的求出多個(gè)粒子共存或合作時(shí)的最優(yōu)解。其優(yōu)化思想在于對(duì)于每個(gè)粒子都有自己的速度與位置，粒子們?cè)谧约核俣扔绊懙耐瑫r(shí)也追隨當(dāng)前最優(yōu)的粒子，從而迭代得到最優(yōu)值。

定義單個(gè)粒子在飛行過程中所獲取的最優(yōu)解為個(gè)體最優(yōu)解（pBest），在整個(gè)粒子群所獲得的最優(yōu)解記作全局最優(yōu)解（gBest），用N維速度Vi=（vi1，vi2，…，viN）與位置Pi=（pi1，pi2，…，piN）進(jìn)行粒子狀態(tài)的表示，在算法中不斷的通過自身速度與位置進(jìn)行狀態(tài)更新，可以產(chǎn)生新一代群體。

該方法的具體實(shí)現(xiàn)流程如下：

步驟1：粒子群初始化，將粒子群中各個(gè)參數(shù)設(shè)置好；步驟2：在適應(yīng)度函數(shù)的基礎(chǔ)上，將每一個(gè)粒子適應(yīng)度值表示出來；步驟3：將粒子的當(dāng)前適應(yīng)度值與歷史最優(yōu)適應(yīng)度值比較，更新歷史最優(yōu)值；步驟4：將當(dāng)前適應(yīng)度與種群歷史最優(yōu)位置適應(yīng)度值比較，更新歷史最優(yōu)值；步驟5：運(yùn)用方程(5)與方程(6)進(jìn)行計(jì)算；步驟6：若獲得最優(yōu)值，則輸出最優(yōu)值結(jié)果，否則跳轉(zhuǎn)步驟2繼續(xù)進(jìn)行迭代。

2.3 混合蟻群-粒子群算法

粒子群的優(yōu)點(diǎn)在于其全局搜索能力強(qiáng)，參數(shù)的更新比較容易，搜索速度比較快，其缺點(diǎn)在于算法在前期求解速度較慢，而且容易早熟收斂。蟻群算法的優(yōu)點(diǎn)在于信息素的存在，使得算法擁有正反饋的特性，缺點(diǎn)在于傳統(tǒng)的蟻群算法計(jì)算量大，耗時(shí)較長。

在衡量了兩個(gè)算法的優(yōu)缺點(diǎn)之后，混合算法首先派出螞蟻在全局進(jìn)行搜索，然后結(jié)合粒子群算法，讓螞蟻在信息素與最優(yōu)螞蟻兩者的作用下進(jìn)行路徑尋優(yōu)。算法的主要實(shí)現(xiàn)步驟如下：

1）初始化蟻群算法與粒子群算法參數(shù)，讓蟻群隨機(jī)分布在求解空間內(nèi)。

2）根據(jù)貪婪算法生成信息素分布，讓蟻群按照信息素含量去更新位置。

3）記錄螞蟻的個(gè)體最優(yōu)值pbest與全局最優(yōu)值gbest，并記錄螞蟻路徑的平均值mean。

4）再次根據(jù)信息素去進(jìn)行迭代計(jì)算，同時(shí)找出路徑值超過mean的螞蟻。

5) 將超過mean的螞蟻替換為臨近的優(yōu)解，重新加入運(yùn)算。

6）若迭代次數(shù)超過設(shè)定值則輸出最優(yōu)值，否則進(jìn)入步驟4）繼續(xù)進(jìn)行運(yùn)算。

同時(shí)該算法在回庫時(shí)設(shè)置靠近障礙物的信息素含量最高，這樣可使AGV在回庫時(shí)避免與送貨AGV發(fā)生道路強(qiáng)占導(dǎo)致一些異常。

在Matlab模擬中設(shè)置蟻群算法中迭代次數(shù)為100次，信息啟發(fā)式因子為2，期望啟發(fā)式因子為5，信息素蒸發(fā)系數(shù)為0.1，信息素增加強(qiáng)度系數(shù)為1.2。在粒子群算法中慣性權(quán)重取0.5，學(xué)習(xí)因子c1、c2均為2。

3 應(yīng)用實(shí)例

某公司立體庫中的AGV現(xiàn)場實(shí)際路線如圖3所示，在Matlab模擬中將有地標(biāo)的點(diǎn)設(shè)為0，倉庫設(shè)為1，障礙為2。從而得到模擬路線的運(yùn)算圖像。在該智能倉庫中，路徑比較單一，在送貨路徑進(jìn)行尋優(yōu)過程中算法一致性較強(qiáng)，均能使小車按最短路徑到達(dá)貨倉，但是在出庫時(shí)，若用傳統(tǒng)算法會(huì)導(dǎo)致AGV原路返回，可能會(huì)與下一輛送貨AGV發(fā)生交通管制，同時(shí)，本文的混合算法在收斂速度上優(yōu)于傳統(tǒng)算法，可以使AGV控制系統(tǒng)更快的下發(fā)任務(wù)，提高倉庫效率。

圖3 現(xiàn)場倉庫區(qū)AGV路線

分別用混合算法與A*算法去優(yōu)化最遠(yuǎn)貨架的路徑，優(yōu)化的結(jié)果如圖4所示，兩種算法在送貨任務(wù)中，得到了同樣的優(yōu)化路徑，且均為最短路徑，但是在回庫任務(wù)中，混合算法由于在障礙物兩旁設(shè)置了最大信息素，使得算法優(yōu)化結(jié)束后一定會(huì)給小車分配沿障礙物的路徑回去，這略微影響了效率，但是可以有效的防止回庫AGV與送貨AGV路線沖突，避免了很多不必要的交通管制。從而提高了智能倉庫的穩(wěn)定性。

圖4 不同算法分配的相同路徑

圖5 兩種算法收斂情況比較

圖5為兩種算法的收斂速度比較，針對(duì)智能物流倉庫的井字形地圖，通過混合算法與A*算法得到的送貨路徑相同，不過混合算法在收斂速度上優(yōu)于A*算法。在實(shí)際應(yīng)用中，可以使得AGV控制系統(tǒng)更為快速的下發(fā)AGV任務(wù)，從而提高倉庫效率。

綜合看來，本文提出的混合算法在多AGV路徑優(yōu)化時(shí)，在送貨段可以比傳統(tǒng)A*算法更為快速的得到優(yōu)化路徑，提高了AGV控制系統(tǒng)的效率。在回庫路線可以使車輛有序的從指定位置回庫，避免了車輛互相管制，發(fā)生事故等問題，加強(qiáng)了倉庫的安全性。

4 結(jié)論

本文針對(duì)立體化倉庫中AGV的路徑規(guī)劃問題，在分析了蟻群算法與粒子群算法的特點(diǎn)后。結(jié)合兩種算法提出了混合蟻群粒子群算法來解決路徑規(guī)劃問題。并通過軟件模擬與傳統(tǒng)的A*算法對(duì)比，該方法可以提高倉儲(chǔ)物流的效率與安全。該研究對(duì)目前智能化倉庫中的AGV路徑優(yōu)化問題有一定的實(shí)用價(jià)值。