張維君，薛成玉

（沈陽航空航天大學(xué) 計(jì)算機(jī)學(xué)院，遼寧 沈陽 110136）

0 引言

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

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

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

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

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

圖1 柵格地圖

（1）AGV車速不變，電量充足，取貨放貨時(shí)間忽略不計(jì)；

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

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

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

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

AGV系統(tǒng)是多個(gè)AGV組成的系統(tǒng)，為保證所有AGV到達(dá)目標(biāo)點(diǎn)的情況下使得總時(shí)間最短，目標(biāo)函數(shù)式為：

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

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

（2）每個(gè)AGV在起始節(jié)點(diǎn)上的時(shí)間約束。

1.2 多AGV沖突問題描述

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

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

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

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

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

圖2 沖突類型

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

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

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

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

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

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

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

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

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

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

3 算法設(shè)計(jì)

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

3.1 改進(jìn)隨機(jī)搜索策略

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

（1）在當(dāng)前序列X中隨機(jī)找到兩個(gè)節(jié)點(diǎn)z1和z2；（2）對(duì)z1節(jié)點(diǎn)進(jìn)行加一操作，對(duì)z2進(jìn)行減一操作；

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

（4）替換掉當(dāng)前序列中z1和z2間的序列。

3.2 改進(jìn)螺旋更新和收縮包圍策略

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

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

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

（2）找到r1和r2位于兩個(gè)序列中的位置序號(hào)z1、z2和z3、z4；

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

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

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

（2）找到r位于兩個(gè)序列中的位置序號(hào)z1和z2；

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

（4）將柵格地圖以z1橫坐標(biāo)為中心，將柵格地圖分為上下兩部分，當(dāng)z2位于z1上半部分時(shí)，z1進(jìn)行加一操作，否則進(jìn)行減一操作。

3.3 預(yù)約表的設(shè)計(jì)

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

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

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

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

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

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

圖3 碰撞檢測(cè)及避障策略流程圖

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

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

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

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

②對(duì)種群進(jìn)行評(píng)價(jià)，計(jì)算種群內(nèi)每個(gè)個(gè)體的適應(yīng)度，找出全局最優(yōu)解；

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

④改進(jìn)隨機(jī)搜索策略；

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

⑥對(duì)種群進(jìn)行重新評(píng)價(jià)，更新全局最優(yōu)解；

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

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

4 仿真實(shí)驗(yàn)及結(jié)果分析

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

表1 初始化任務(wù)圖

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

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

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

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

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

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

圖6 平均完工時(shí)間收斂圖

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

表3 DWOA和GA對(duì)比表

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

5 結(jié)語

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

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