基于改進灰狼算法的共享倉儲動態盤點方法

張富強，許鋒立，邵樹軍，杜 超

(1. 長安大學道路施工技術與裝備教育部重點實驗室，陜西 西安 710064；2. 長安大學智能制造系統研究所，陜西 西安 710064；3. 陜西法士特齒輪有限責任公司，陜西 西安 710119；

1 引言

隨著以物聯網和大數據為代表的信息技術的發展，智慧物流的出現推動了制造業企業轉型與降本增效的速度，對資源優化配置與可持續發展有著重要的現實意義。作為智慧物流貨物存儲的新形態，共享倉儲將逐漸社會化的倉儲資源和趨向專業化的物流服務緊密結合，通過將倉儲和服務有機結合的方式，為制造企業提供了從采購到配送的一體化服務平臺[1，2]。現代企業要求倉儲需求可以得到快速的響應，同時在不影響生產的前提下讓物流的成本盡可能低，而共享倉儲就可以實現這些要求。實時、準確、高效的倉儲貨物動態盤點是實現共享倉儲貨位動態分配與智能化管控的關鍵。

傳統的貨物盤點由人工進行，消耗大量的時間，并易出現盤點錯誤，無法獲取實時的數據支持，準確掌握物品庫存；掃碼槍盤點技術的出現雖然減少了人工盤點出現錯誤的情況發生，但還需要人工參與[3]。共享倉儲總體積龐大，貨架與貨格布置繁多，貨物流通速度快，大大增加了盤點的難度與速度要求，同時共享倉儲庫存貨物種類越來越多，對于盤點的精度要求也大大提高，傳統的盤點技術已無法滿足要求。因此，將基于物聯網的自動定位系統加入到共享倉儲動態盤點過程中，具有重要的工程應用價值和理論研究意義。

共享倉儲一般為室內環境，而在目前的室內無線定位技術中，RFID(Radio Frequency Identification)定位技術以其成本低、實時性、布置方便、非視距性等優點，使其在制造領域的各個方面得到了成熟的應用和推廣[4-8]。目前基于RFID的室內定位技術有測距和非測距兩種。非測距技術的定位方法雖然操作簡單，但其定位精度難以滿足智慧倉儲對貨物的定位精度要求；測距定位技術中的TOA、TDOA、AOA等相關定位方法成本比較高，同時需要一系列的硬件設備支撐才能完成定位。RSSI(Received Signal Strength Indication)定位算法不需要添加額外的設備即可完成定位，并且功耗相對于其它方法低[9]，因此本文采用基于RSSI的定位方法。

目前國內外學者對于RSSI定位技術進行了深入的研究，但仍存在一些不足。宋寧佳等提出的GA-GRNN定位算法，在一定程度上提高了空間物體的定位精度，但是模型存在收斂速度慢、得出的解不一定是全局最優解的問題[10]。鄧昀等提出的定位算法以BP神經網絡為基礎，雖然算法受到數據存在較大偏差的限制，同時需要大量的數據進行模型的訓練，但定位精度有所提高[11]。文獻[12]則提出了融合信號強度與到達角度的定位方法，但這種方法需要提前設置相應的信標節點，定位方法復雜。Byrne等以RSSI定位算法為基礎得到優化算法并應用于室內定位，結果表明該算法一定程度上提高了定位精度，但該算法在信號干擾強度大的環境應用不多[13]。Zhang[14]等使用直接路徑信號對待定位目標進行定位，但是在多徑效應影響下，無法精確定位物體的位置。

為了進一步提高復雜環境下共享倉儲貨物動態盤點的抗干擾能力與定位精度，本文通過對數路徑損耗模型來加強復雜環境下RSSI定位技術的定位穩定性，引入粒子群算法(Particle Swarm Optimization，PSO)對灰狼算法(Grey Wolf Optimization Algorithm，GWO)的位置更新過程進行改進，提高灰狼個體與自身經驗的信息交流，得到粒子群優化后的灰狼算法PSO-GWO(Hybrid Algorithm of Particle Swarm Optimization and Grey Wolf Optimization)，通過仿真與標準的灰狼算法進行了比較，驗證了改進后定位算法的優越性。

2 共享倉儲貨物的空間定位模型

相比于傳統的物流倉儲，共享倉儲可實現社會倉儲資源供需匹配，有效提高資源利用率和降低成本，符合物流行業的可持續發展的需求。基于倉儲環境復雜、貨物種類眾多、倉儲作業繁重、全信息化管理等特征，本文將基于RSSI與優化灰狼算法融合的三維空間定位技術引入動態盤點作業，從而提高倉儲盤點的精度與速度。

2.1 RSSI測距模型

基于RSSI的無線定位技術，可以實現信號強度向距離的轉變，然后通過定位模型實現未知節點的定位。能量-距離的轉換可以通過自由空間傳播模型進行，如式(1)所示。

(1)

式中，Gr為接收信號天線的增益，λ為電磁波的波長，d代表閱讀器和標簽間的距離，PEIRP代表信號功率。

在實際應用時，盡管信號兩端距離是一樣的，但是周圍的環境存在較大的差別，此時直接應用路徑損耗模型會產生較大的差別。可選擇對數路徑損耗模型來描述室內復雜環境因素影響的無線信號所具備的傳輸特性，如式(2)所示。

(2)

式中，PL(d)表示傳輸d米時損耗的能量值，單位為dBm；d0為參考距離；PL(d0)表示傳輸d0米時損耗的能量值；γ是路徑損耗因數；Xσ為陰影衰落，是服從N(0，σ)的隨機變量。

假設d為標簽與閱讀器間的距離，Pr(d)為接收端信號強度值，Pt為發射端信號強度值，并設RSSI0=Pt-PL(d0)是d0米處的信號強度值時，由此可以得到

(3)

2.2 RSSI定位模型

基于RSSI測距模型的未知節點定位的實現主要是通過空間中布置的RFID閱讀器，用于接收貼在貨物上的電子標簽發出的信號，通過記錄信號強度，可以得到一組未知節點關于每個閱讀器的信號強度值。假設RFID空間中布置有n個閱讀器用于接收電子標簽發出的信號同時記錄信號強度，閱讀器的坐標分別為(Xi，Yi，Zi)，i=1，2，…n閱讀器接收到n個信號強度(RSSI1，RSSI2，…，RSSIn)；經過測距模型將信號強度轉換成電子標簽到每個閱讀器的距離(d1，d2，…，dn)；這樣未知節點的定位問題可以轉化為一個優化問題。通過算法不斷迭代，計算出目標函數的最小值，可以提高未知節點的定位精度。本文將待定位節點的坐標作為自變量，以估計坐標與實際坐標到個閱讀器之間距離誤差最小作為優化目標，構建目標函數：

(4)

式中，(x，y，z)為待定位節點的估計坐標，di為節點實際坐標到第i個閱讀器之間的距離，通過測距模型換算可以得到，Di為(x，y，z)到第i個閱讀器之間的距離，定義為：

(5)

3 粒子群改進灰狼算法

3.1 灰狼優化算法

灰狼優化算法是澳大利亞格里菲斯大學 Mirjalili 等于2014年提出的群體智能優化算法[15]。鑒于該算法參數少、收斂性好和易實現等優勢，本文結合上述模型采用該算法進行求解。

1)社會等級分層(Social Hierarchy)

灰狼種群的社會等級分層可以分為α、β、δ、ω四個等級。每次迭代后產生的α、β、δ指導完成灰狼算法的優化過程。

2)包圍獵物(Encircling Prey)

狼群首先確定獵物所在位置獵物與灰狼之間的距離可表示為：

D=c*XP(t)-X(t)

(6)

其中D表示灰狼個體和狩獵獵物之間的距離，t表示迭代次數，XP(t)為獵物迭代t次后的位置，X(t)為灰狼迭代t次后的位置，A和C為灰狼優化算法中的系數因子：

A=2a*r1-a

C=2r2

(7)

通過迭代，a由2可以線性降到0；r1和r2是[0，1]中的隨機向量。

3)狩獵(Hunting)

灰狼算法的每次迭代會產生α、β、δ狼，以適應度進行選擇。其位置信息對ω狼的位置進行更新。該行為的數學模型可表示如式(8)所示。

(8)

當|A|>1時，灰狼分散在各個區域內搜尋獵物。當|A|<1時，灰狼逐漸接近獵物。

4)攻擊獵物(Attacking Prey)

在攻擊過程中，A隨著a的減小不斷變化。A是區間[-a，a]上隨a的線性下降而變化的隨機向量。當A在[-1，1]區間上時，通過一次迭代之后，搜索代理的位置會變化到灰狼個體與獵物之間的某一位置。

3.2 改進的灰狼優化算法

GWO算法在位置更新時僅通過灰狼個體位置和最優三匹灰狼的位置信息實現個體與種群之間的信息交流，忽略了灰狼個體與自身經驗的信息交流。

亳文化譯介是從漢語譯成英語、日語、韓語等語種，翻譯和譯介效果的好壞直接關系到亳文化的國際傳播效果，為了提高亳文化的譯介質量和國際傳播實效，應當以國外受眾對亳文化譯文的感受和反應為準繩構建起譯介效果評價體系。

為了加強對GWO算法中灰狼個體的記憶能力的應用，本文引入粒子群算法對灰狼算法位置更新過程進行改進。PSO算法可以對粒子運動過程中自身所攜帶的歷史最優解進行保存，將這一特性融入到GWO算法中，對GWO算法中灰狼個體自身移動過程中的最優解進行記憶保存。

PSO算法中，粒子可以在空間中實現有方向的變速運動，可以通過粒子自身的記憶和粒子種群進行交流，進而找到下一位置，實現最優解的尋找。本文結合PSO算法思想，將灰狼個體位置的更新變為粒子位置的更新，使灰狼算法具有記憶性。位置和速度更新公式如(9)所示。

(9)

式(6)中的第一式變為

Dα=C1*Xα-ωX

Dβ=C2*Xβ-ωX

(10)

Dδ=C3*Xδ-ωX

通過PSO算法對灰狼算法的改進，可以在算法搜索過程中不斷協調灰狼種群之間的交流與灰狼個體歷史記憶對算法的影響。

本節的PSO-GWO具體實現步驟如下：

Step1：初始化算法參數A，C，a值。

Step2：初始化種群個體，隨機產生種群個體。

Step3：根據每個灰狼的適應度值，選出α，β，δ狼，確定位置信息Xα，Xβ，Xδ。

Step4： 根據式(7)更新A、C的值。

Step5： 根據式(9)更新灰狼個體位置，并返回step3重新計算，更新灰狼α，β，δ及其對應的位置信息。

Step6：如果t達到Tmax值則輸出最佳解，即a值的適應度值，否則返回Step4繼續執行。

PSO-GWO算法流程如圖(1)所示

基于PSO-GWO的共享倉儲貨物定位算法以電子標簽的坐標為灰狼的位置，以上式的f(x，y，z)為衡量標準進行優化求解。具體流程如圖2所示。

圖1 PSO-GWO算法流程圖

1)測量并記錄處理數據。閱讀器發射無線信號，接收并統計有標簽信息的RSSI值，通過平均值法對接收到的數據進行處理。

圖2 PSO-GWO定位流程圖

2)建立信號傳播模型。把RSSI值用作輸入，距離用作輸出，通過能量與距離之間的轉換函數關系，估計出待測標簽與每個閱讀器之間的距離。

3)將m個閱讀器與待測標簽之間的距離用作公式的參數，求得待測標簽的估計坐標。

4)把待測標簽的估計坐標與實際坐標作為公式參數構造目標函數的具體形式。

5)經由優化灰狼算法逐步迭代獲得最優解，并把該解作為待測標簽坐標的最終估計值。

3.3 偽代碼

input：

N，Tmax，dim，ub，lb

P=initialization(N，Tmax，dim，ub，lb)

output：

P＿alpha，F

while l

for i=1：size(P，1)

if F

S＿alpha=F；

P＿alpha=P(i，：)；

end

if F>S＿alpha && F

S＿beta=F；

P＿beta=P(i，：)；

end

if F>S＿alpha && F>S＿beta && F

S＿delta=F；

P＿delta=P(i，：)；

end

end

其中，N表示狼群數量，Tmax表示最大迭代次數，dim表示維數，lb表示參數取值下界，ub表示參數取值上界，P表示灰狼當前位置坐標，F表示灰狼的適應度。

4 案例仿真

4.1 實驗布局

首先搭建出一個模擬的共享倉庫，如圖3所示，其長、寬、高分別為30米，在倉庫中放置有5列貨架，每列貨架分別有3層5列。在倉庫中選擇20個貨柜放入貼有電子標簽的貨物，然后對貨物所放貨柜進行編號，然后在房間不同位置放置4個閱讀器，其中四個閱讀器的位置分別為(0，0，0)，(30，0，0)，(0，30，30)，(30，30，30)最后采用灰狼算法對貨物進行定位定盤點。

圖3 仿真案例建模

4.2 測試結果及對比

本文主要針對原灰狼算法與粒子群優化灰狼算法進行結果對比。

法與粒子群優化灰狼算法的收斂曲線圖分別如圖4所示。

實際坐標與測試坐標三維空間中的位置分布如圖5所示(中，“o”表示測試節點的實際位置，“+”表示灰狼優化算法的測試節點的位置，“×”表示粒子群優化灰狼算法的測試加點位置)

圖4 收斂曲線圖

本文采用歐氏距離表示測試點實際坐標和估計坐標的誤差

圖5 實際坐標與計算坐標

(11)

e表示定位誤差，xj、yj、zj表示測試點實際坐標，xi、yi、zi表示測試點估計坐標。

經過計算可以得出當算法迭代次數為500次，測試點數目為20個時，兩種算法的定位誤差如圖6所示。

圖中實線表示GWO算法定位誤差，虛線表示PSO-GWO算法的定位誤差。GWO算法的平均誤差為2.91m，PSO-GWO算法的平均誤差為1.09m。通過上述兩種結果的對比，GWO算法的定位誤差具有明顯的波動，最大誤差達到了7.2m，而PSO-GWO的定位誤差基本在1m左右變化，說明PSO-GWO具有更高的穩定性與定位精度。

圖6 兩種算法定位誤差

本實驗通過對相關參數變化，可以得到不同的優化結果。改變定位參數定位結果變化情況如下：

1)定位測試點數目變化對測試點定位結果的影響

測試點數目分別為10，20，30時定位精度的比較結果如圖7所示。

圖中白色柱狀線表示GWO算法定位誤差，虛線表示PSO-GWO算法的定位誤差。通過比較，當測試點的數目發生變化時，GWO算法的定位誤差出現較大偏差，而PSO-GWO算法定位誤差保持在1m以下且基本持平，說明測試點數目的變化對PSO-GWO算法定位結果的影響很小，該定位算法具有較高的穩定性。

圖7 測試點數目對定位精度的影響

2)算法迭代次數變化對測試點定位結果的影響

迭代次數分別為100，300，500時定位精度的比較結果如圖8所示。

圖8 迭代次數對定位精度的影響

圖中白色柱狀線表示GWO算法定位誤差，虛線表示PSO-GWO算法的定位誤差。通過比較，在測試點數目相同的條件下，GWO算法的定位隨著算法迭代次數的變化而急劇波動，而PSO-GWO算法定位誤差沒有發生太大變化，迭代次數的變化對算法定位精度影響很小。說明該算法能夠在較低的迭代次數下實現定位，即算法定位速度快。同時還具有較高的精度。

5 結論

針對當前共享倉儲貨物動態盤點中定位精度與抗干擾能力較低的問題，提出了一種基于RSSI和改進灰狼算法的共享倉儲貨物動態盤點方法。

1)采用粒子群算法對灰狼算法的位置更新過程進行改進，提高了灰狼個體與自身經驗的信息交流，防止求解陷入局部最優。

2)通過定位測試點數目變化和迭代次數變化對定位結果的影響分析可知，PSO-GWO算法定位誤差控制在1m以下，具有較好的穩定性和定位精度。

下一步的研究方向：隨著共享倉儲技術的深入發展，倉儲貨物的品類會越來越多，周轉頻率越來越快，基于算法的三維定位技術可以為貨位的動態分配和智能管控提供基礎，提高共享倉儲的實時信息更新，及時掌控倉儲貨物信息，加快倉儲決策優化速度以及自我決策能力，使共享倉儲向數字化、網絡化和智能化方向發展。