基于離散鯨魚優(yōu)化算法的倉儲物流AGV路徑規(guī)劃

張維君，薛成玉

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

0 引言

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

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

1 問題描述和數(shù)學模型

1.1 多AGV系統(tǒng)的路徑規(guī)劃模型

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

圖1 柵格地圖

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

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

（3）地圖內(nèi)AGV可雙向行駛，轉(zhuǎn)彎時間固定；

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

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

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

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

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

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

1.2 多AGV沖突問題描述

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

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

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

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

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

圖2 沖突類型

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

2 基本鯨魚優(yōu)化算法（WOA）

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

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

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

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

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

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

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

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

3 算法設計

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

3.1 改進隨機搜索策略

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

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

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

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

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

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

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

（1）找出當前序列X和最優(yōu)序列X*相同節(jié)點集合Q，在集合Q中隨機搜索兩個不同數(shù)r1和r2；

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

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

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

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

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

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

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

3.3 預約表的設計

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

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

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

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

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

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

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

3.4 路徑規(guī)劃及避碰策略流程

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

（2）路徑規(guī)劃。

①初始化算法的相關(guān)參數(shù)：種群大小、最大迭代、問題維度等；

②對種群進行評價，計算種群內(nèi)每個個體的適應度，找出全局最優(yōu)解；

③遍歷種群，生成隨機數(shù)p，若p＞0.5，轉(zhuǎn)為步驟④，否則轉(zhuǎn)為步驟⑤；

④改進隨機搜索策略；

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

⑥對種群進行重新評價，更新全局最優(yōu)解；

⑦重復以上步驟，直至迭代結(jié)束。

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

4 仿真實驗及結(jié)果分析

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

表1 初始化任務圖

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

表2 AGV路徑結(jié)果及其避障策略

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

圖4 DWOA路徑規(guī)劃圖

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

圖5 最優(yōu)完工時間收斂圖

圖6 平均完工時間收斂圖

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

表3 DWOA和GA對比表

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

5 結(jié)語

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

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