魏宏源，茅 健

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

0 引言

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

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

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

1 問題描述與建模

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

圖1 立體倉庫入口

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

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

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

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

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

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

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

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

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

2 混合蟻群粒子群算法

2.1 蟻群算法

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

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

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

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

2.2 粒子群算法

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

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

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

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

2.3 混合蟻群-粒子群算法

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

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

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

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

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

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

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

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

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

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

3 應用實例

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

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

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

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

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

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

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

4 結論

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