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

魏宏源，茅 健

（上海工程技術大學 機械工程學院，上海 201620）

0 引言

近年來，工業4.0戰略規劃在促使整個工業生產體系進入全新的水平。作為工業4.0的核心組成部分，智能物流是連接客戶、供應鏈和制造業的重要環節，也是構建未來智能工廠的基石[1,2]，自動導引運輸車（AGV）是智能物流中重要設備之一[3]。其路徑的好壞決定了倉庫的運作效率，因此對AGV路線的規劃也成為了研究熱點，國內外學者已經做出了很多貢獻。

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

本文根據立體庫的實際情況，基于混合蟻群粒子群方法，建立了多臺AGV小車路徑快速分配與優化模型，對多AGV小車路徑優化問題進行研究，結果表明該方法可以加快AGV小車在倉庫運輸的速度，提高智能倉儲的物流傳輸效率。

1 問題描述與建模

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

圖1 立體倉庫入口

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

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

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

2）路線的起終點已知，倉庫中地圖已知。

3）分配任務或者下達指令后無網絡延遲問題，小車及時響應控制系統下達的命令。

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

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

多AGV路徑優化可視為一種特殊的旅行商問題（TSP），它也是組合優化中的一個困難的NP問題。如果不能很好的處理該問題，會導致車輛互鎖，甚至碰撞等問題，如圖2所示。1號AGV與2號AGV由于路徑規劃不好，面對面的行駛，最終兩輛車發生互鎖，都無法繼續行駛。

因此，本文基于混合蟻群粒子群算法，提出了一種優化算法，改善AGV小車的路徑規劃問題，同時根據現場規劃找出合適的返回路線，避免交通異常。

2 混合蟻群粒子群算法

2.1 蟻群算法

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

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

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

圖2 AGV互鎖現象

2.2 粒子群算法

粒子群算法（PSO）是一種基于鳥群智能的隨機優化技術，也叫做鳥群算法，該算法具有群體智能、內在并行性、迭代格式簡單、可快速收斂到最優解等優點[12]。PSO算法的優勢在于可以較為簡便的求出多個粒子共存或合作時的最優解。其優化思想在于對于每個粒子都有自己的速度與位置，粒子們在自己速度影響的同時也追隨當前最優的粒子，從而迭代得到最優值。

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

該方法的具體實現流程如下：

步驟1：粒子群初始化，將粒子群中各個參數設置好；步驟2：在適應度函數的基礎上，將每一個粒子適應度值表示出來；步驟3：將粒子的當前適應度值與歷史最優適應度值比較，更新歷史最優值；步驟4：將當前適應度與種群歷史最優位置適應度值比較，更新歷史最優值；步驟5：運用方程(5)與方程(6)進行計算；步驟6：若獲得最優值，則輸出最優值結果，否則跳轉步驟2繼續進行迭代。

2.3 混合蟻群-粒子群算法

粒子群的優點在于其全局搜索能力強，參數的更新比較容易，搜索速度比較快，其缺點在于算法在前期求解速度較慢，而且容易早熟收斂。蟻群算法的優點在于信息素的存在，使得算法擁有正反饋的特性，缺點在于傳統的蟻群算法計算量大，耗時較長。

在衡量了兩個算法的優缺點之后，混合算法首先派出螞蟻在全局進行搜索，然后結合粒子群算法，讓螞蟻在信息素與最優螞蟻兩者的作用下進行路徑尋優。算法的主要實現步驟如下：

1）初始化蟻群算法與粒子群算法參數，讓蟻群隨機分布在求解空間內。

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

3）記錄螞蟻的個體最優值pbest與全局最優值gbest，并記錄螞蟻路徑的平均值mean。

4）再次根據信息素去進行迭代計算，同時找出路徑值超過mean的螞蟻。

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

6）若迭代次數超過設定值則輸出最優值，否則進入步驟4）繼續進行運算。

同時該算法在回庫時設置靠近障礙物的信息素含量最高，這樣可使AGV在回庫時避免與送貨AGV發生道路強占導致一些異常。

在Matlab模擬中設置蟻群算法中迭代次數為100次，信息啟發式因子為2，期望啟發式因子為5，信息素蒸發系數為0.1，信息素增加強度系數為1.2。在粒子群算法中慣性權重取0.5，學習因子c1、c2均為2。

3 應用實例

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

圖3 現場倉庫區AGV路線

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

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

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

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

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

4 結論

本文針對立體化倉庫中AGV的路徑規劃問題，在分析了蟻群算法與粒子群算法的特點后。結合兩種算法提出了混合蟻群粒子群算法來解決路徑規劃問題。并通過軟件模擬與傳統的A*算法對比，該方法可以提高倉儲物流的效率與安全。該研究對目前智能化倉庫中的AGV路徑優化問題有一定的實用價值。