基于離散鯨魚優化算法的倉儲物流AGV路徑規劃

張維君，薛成玉

（沈陽航空航天大學 計算機學院，遼寧 沈陽 110136）

0 引言

物流業的迅猛發展使得物流倉儲在快遞行業中的地位愈發重要，而自動導引車（AGV）因自動化、高柔性、高可靠性以及并行作業等特點，已成為物流運輸中的重要工具，越來越多的物流倉儲采用AGV進行運輸，這極大便利快遞的分揀。然而，當AGV數量增時，受作業環境、機器故障、操作失誤、道路容量等影響會使得AGV出現死鎖、碰撞等問題，這些問題嚴重制約AGV的運輸效率，影響整個倉儲的調度甚至造成系統癱瘓。AGV的路徑規劃和沖突的處理一直是研究領域的熱點問題，路徑規劃是AGV在倉儲環境內運行，找出一條滿足約束的可行路徑，沖突處理要求多AGV的路徑是無沖突最優的。智能優化算法在處理路徑規劃問題時有著很高的計算性，許多智能優化算法被用于路徑規劃方面研究，例如：遺傳算法、粒子群算法、模擬退火算法、鯨魚優化算法、灰狼算法等。Lyu，等提出將一種帶時間窗的Dijkstra算法相結合到遺傳算法中解決無沖突路徑規劃問題；Cong提出將蟻群優化算法用于機器人路徑規劃上，并根據一組給定的映射證明所提出的方法的有效性。鯨魚優化算法于2016年被提出。因其參數少、結構簡單、搜索能力強等優點，大量學者對鯨魚優化算法進行了研究。Zhou，等提出基于Lévy飛行軌跡的鯨魚優化算法（LWOA），引入Lévy飛行軌跡促進算法跳出最優，在開發和利用之間取得更好的平衡；劉磊，等引入自適應權重和變螺旋位置更新策略提高尋優能力，引入最優鄰域擾動策略跳出局部最優；劉小龍提出一種多種群縱橫雙向學習的種群劃分思路，向縱橫兩向尋找最優值，避免局部最優。以上都是鯨魚優化算法在處理連續優化問題的研究，在組合問題上的研究較少。但是，當AGV數量增多時，沖突問題隨之而來。國內外學者針對多AGV沖突問題做了大量研究，Saidi-Mehrabad，等提出JSSP和CFRP組合的數學模型并用一種兩階段蟻群算法（ACA）求解車間調度無沖突路徑問題；Yang，等針對碼頭無沖突路徑研究，建立一個基于路徑規劃、集成調度、沖突和死鎖的混合整數規劃模型；Miyamoto，等建立整數規劃模型，并用局部隨機搜索進行有容量約束的AGV系統的調度和無路徑沖突問題求解。

上述研究增強了人們對鯨魚優化算法和AGV沖突的認知，為AGV系統路徑規劃和避障提供了思路。但在離散化WOA和無沖突路徑上仍有不足，提出DWOA算法和基于預約表的避障策略。首先，由于傳統鯨魚算法在解決離散化問題上的不足，提出DWOA算法用于AGV的路徑規劃；然后，結合避障策略，通過預約表實現對沖突的預測。最后，通過仿真實驗，證明基于預約表的避障策略可有效預測沖突，DWOA算法在倉儲物流可以完成路徑規劃，并在路徑規劃時耗費時間縮短17.3%。

1 問題描述和數學模型

1.1 多AGV系統的路徑規劃模型

物流倉儲內多AGV系統的工作可以描述為：多AGV共享同一倉儲環境，將倉儲內貨物根據分配規則從貨架運送到相應的卸貨區。無沖突路徑規劃可以描述為：找到多AGV系統內滿足約束的無沖突路徑。為便于對多AGV進行路徑規劃，采用柵格法為倉儲內環境進行建模，將工作區用平面圖清晰表示。柵格法將AGV的工作空間分為只有白的和黑色的網格單元，如圖1所示為一個20×20的柵格圖，白色區域為可通行區域，用1表示，黑色區域代表障礙區域不可通行，用0表示。將AGV小車視作可在柵格內直徑遠小于柵格單位尺寸的可移動圓，其可行區域為以AGV為中心的八鄰域區域的白色柵格。并將倉儲內的AGV、貨物、卸貨區轉化為環境模型中的節點。為方便建模，對AGV車輛和地圖做如下假設：

圖1 柵格地圖

（1）AGV車速不變，電量充足，取貨放貨時間忽略不計；

（2）AGV為單作業模式，每次只可搬運一個貨物，完成后方可接受其他任務；

（3）地圖內AGV可雙向行駛，轉彎時間固定；

（4）考慮AGV中途損壞情況；

（5）每個柵格同一時刻只容納一個AGV，且確保大小可通過單位柵格。

AGV系統是多個AGV組成的系統，為保證所有AGV到達目標點的情況下使得總時間最短，目標函數式為：

將柵格地圖中節點分為3類：開始節點、終止節點、和路徑節點，對AGV和地圖做如下假設：

（1）每個路徑節點一次最多容納一個AGV；

（2）每個AGV在起始節點上的時間約束。

1.2 多AGV沖突問題描述

在AGV系統中當多AGV被規劃出路徑后，多AGV將按照規劃出的路徑執行任務，倉儲內容量有限，多AGV一起行動將出現沖突等問題，這使得倉儲內的運輸效率降低。為解決上述問題，通常將沖突類型分為四類，相向沖突、障礙物沖突、節點沖突和多機沖突。沖突類型具體描述為：

（1）如圖2(a)所示為相向沖突，兩個相對方向行駛的AGV小車的下一個路徑節點為同一個的節點；

（2）如圖2(b)所示為障礙物沖突，故障AGV或者掉落貨物占據一個可通行節點，阻礙行駛中的AGV；

（3）如圖2(c)所示為節點沖突，兩個不同方向AGV下一個節點為同一節點；

（4）如圖2(d)所示為多機沖突，多個不同方向AGV的下一節點為同一節點。

圖2 沖突類型

本章的研究目標是建立一個多AGV系統的無沖突路徑規劃模型。將倉儲物流內部工作情況簡化成一個二維平面圖，實現對環境的建模；以完成時間最短為任務目標，建立對柵格、AGV和任務的約束；對節點沖突進行描述，為解決沖突問題做準備。

2 基本鯨魚優化算法（WOA）

鯨魚優化算法是一種新型的啟發式搜索算法，該算法模擬座頭鯨的狩獵行為進行復雜問題的尋優。算法中每條鯨魚位置都代表一個可行解，算法包含收縮包圍、泡泡網攻擊和尋找獵物三種不同搜索方式。

（1）收縮包圍。座頭鯨在搜索獵物時，識別獵物位置并包圍獵物。WOA算法模擬該行為時，以最優個體為參照，逐漸向著最優方向靠攏，并更新位置，其數學模型為:

其中，t表示當前迭代次數；X*(t)表示最優解的位置向量；X(t)表示當前個體位置向量；D表示最優個體和當前個體之間的距離；系數向量A、C的公式為：

其中，a代表收斂因子，隨迭代從2到0線性遞減；→是[0，1]內的隨機向量。

（2）螺旋更新機制。當座頭鯨找到獵物后，不斷收縮包圍圈并以螺旋形式游向獵物，其更新位置的數學公式為：

其中，→為當前鯨魚和獵物之間的距離；b為定義螺旋形狀的一個常數，為處于[-1,1]間的常數。

（3）隨機搜索。在座頭鯨未確定獵物位置之前，鯨魚個體會以彼此之間的位置為參考隨機搜索更合適的獵物。其數學模型為：

初始時的鯨魚群隨機均勻分布在搜索空間，|A|可以決定鯨魚群在更新位置時的方向，|A|＞1時，為全局搜索階段，采用隨機搜索方式，擴大種群搜索范圍；|A|＜1時，座頭鯨處于局部開發階段，利用收縮包圍和螺旋更新方式縮小搜索范圍靠近獵取，其概率各50%。

3 算法設計

原始鯨魚算法善于處理連續優化問題，而路徑規劃問題屬于組合問題，在路徑的搜索時需離散化處理，因此需重新定義鯨魚算法的隨機搜索、螺旋更新以及收縮包圍三個階段。

3.1 改進隨機搜索策略

在基本鯨魚優化算法的隨機搜索階段中，鯨魚以種群內隨機個體位置為指導進行對空間的探索，更新鯨魚個體位置時是隨機的，是全局搜索階段。不影響全局搜索的前提下，根據隨機特性模仿鯨魚優化算法的隨機搜索階段，步驟為：

（1）在當前序列X中隨機找到兩個節點z1和z2；（2）對z1節點進行加一操作，對z2進行減一操作；

（3）將z1節點和z2節點間的序列連接通順；

（4）替換掉當前序列中z1和z2間的序列。

3.2 改進螺旋更新和收縮包圍策略

在基本的鯨魚優化算法中，由于收縮包圍和螺旋更新總是朝著當前最優方向更新，因此最優位置的周圍會存在更多的優秀的解，使得最優解只存在于最優解所在的局部位置，這使得種群喪失多樣性，為更好地發掘最優解，提高其搜索能力，增強種群的多樣性，且保留收縮包圍和螺旋更新的特性。

螺旋更新階段是鯨魚個體以螺旋形狀向著最優驅趕獵物的過程，步驟為：

（1）找出當前序列X和最優序列X*相同節點集合Q，在集合Q中隨機搜索兩個不同數r1和r2；

（2）找到r1和r2位于兩個序列中的位置序號z1、z2和z3、z4；

（3）將最優個體中z3和z4節點間的路徑移動到當前序列的z1和z2節點間,最優序列保持不變。

收縮包圍階段為當前鯨魚個體向著最優個體方向攻擊獵物，步驟為：

（1）找出當前序列X和最優序列X*不同集合Q，在集合Q中隨機搜索1個數r；

（2）找到r位于兩個序列中的位置序號z1和z2；

（3）對比z1和z2在柵格地圖中的上下位置；

（4）將柵格地圖以z1橫坐標為中心，將柵格地圖分為上下兩部分，當z2位于z1上半部分時，z1進行加一操作，否則進行減一操作。

3.3 預約表的設計

為解決多個AGV導致的沖突問題，設置一個預約表，表內存儲每個AGV的當前位置節點、下一個位置節點，以及鄰域內可通行節點以及整條路徑節點信息。當系統生成路徑后AGV開始行動，此時通過各個預約表間的對比，預測路徑內各個小車的沖突，及時規劃出避障方案。面對不同沖突類型，避障策略如下：

（1）相向沖突。后續路徑節點長的進行重新路徑搜索策略,后續節點短的繼續。

（2）節點沖突。當有連續相同節點時，停車等待策略會增大停車時間，浪費AGV和節點的資源，因此后續路徑節點長的進行重新路徑搜索策略；當相同節點只有一個時，表明兩條路徑沖突節點的下一個節點在相反方向，因此后續路徑短的進行停車等待策略。

（3）障礙物沖突。標記此處障礙并通知管理員，重新搜索該AGV路徑，待管理員移開障礙物后取消此處標記。

（4）多機沖突。此時同一個節點附近有多個沖突類型，先判斷都屬于哪種類型，先處理節點沖突，再處理相向沖突。

碰撞檢測及避障策略流程圖如圖3所示。

圖3 碰撞檢測及避障策略流程圖

3.4 路徑規劃及避碰策略流程

（1）環境建模。依次給每個AGV分配任務，按照分配先后進行路徑規劃。

（2）路徑規劃。

①初始化算法的相關參數：種群大小、最大迭代、問題維度等；

②對種群進行評價，計算種群內每個個體的適應度，找出全局最優解；

③遍歷種群，生成隨機數p，若p＞0.5，轉為步驟④，否則轉為步驟⑤；

④改進隨機搜索策略；

⑤若|A|＞1，進行改進螺旋更新策略；否則，進行改進收縮包圍策略；

⑥對種群進行重新評價，更新全局最優解；

⑦重復以上步驟，直至迭代結束。

（3）預約表設計以及避障策略。預約表跟隨路徑中的AGV的移動而時刻變化，比較預約表，若存在沖突問題，根據避障策略進行調節，并再次比較，直至路徑無沖突。

4 仿真實驗及結果分析

對DWOA算法和基于預約表的避障策略進行可靠性和有效性分析。在20*20的柵格內進行仿真實驗。初始化任務見表1。

表1 初始化任務圖

表2為采用DWOA算法規劃的路徑結果以及避障策略。根據預約表可知AGV1和AGV2在節點68處將處發生碰撞，AGV1和AGV3在節點108處發生碰撞。

表2 AGV路徑結果及其避障策略

由沖突類型可知兩個沖突均為節點沖突，68和108處碰撞處AGV1的后續節點多，因此AGV1進行等待。DWOA路徑規劃圖如圖4所示。

圖4 DWOA路徑規劃圖

為驗證DWOA的有效性，用相同起始點（6，299）進行路徑規劃，將遺傳算法和DWOA進行比較，圖5、圖6為DWOA、GA進行路徑規劃求解30次后，取最優一次的運行結果的最優完工時間收斂圖和平均完工時間收斂圖。由圖5可知，DWOA在第19次達到最優，GA在32次達到最優，就收斂結果看，DWOA擁有更好的迭代速度，迭代次數更短。由圖6可知，DWOA在40代時達到最優，DWOA收斂性明顯優于GA，收斂結果也優于GA。

圖5 最優完工時間收斂圖

圖6 平均完工時間收斂圖

由表3可知：DWOA尋找最優解耗費時間比GA減少17.3%。求解最優解的迭代次數比GA減少36.7%，求解平均解迭代次數比GA減少了43%，提高了算法的收斂速度。由以上數據可知，DWOA在路徑規劃方面上收斂速度和尋優能力優于GA。

表3 DWOA和GA對比表

通過在20×20柵格地圖上進行仿真證明了DWOA算法在倉儲物流路徑規劃上的有效性，在沖突時可通過預約表有效預測沖突，并解決沖突。

5 結語

提出一種DWOA算法，并將路徑規劃和沖突綜合考慮，在提高路徑規劃的實時性和有效性同時，通過沖突預判減少沖突的發生。在考慮AGV系統的沖突問題導致的作業運輸效率低的問題上，建立以最小化完成時間為目標的AGV路徑規劃模型。仿真實驗表明，該算法可以解決倉儲物流內多AGV系統無沖突路徑規劃問題，使得AGV系統中AGV運輸任務時大大縮短運輸時間，提高AGV運輸效率，從而提高倉儲物流的分揀效率。

對AGV的規劃是在基本作業環境和任務分配已知的情況下，而真實的情況可能更加復雜，比如工作場景中可能需要考慮磁道損壞，搬運的貨物過小造成AGV的浪費，以及AGV電量和損壞等問題，有效解決以上問題將是未來研究的一大方向。