袁 斌,王偉博,王 輝

(浙江科技學(xué)院 機(jī)械與能源工程學(xué)院,杭州 310023)

當(dāng)今電子商務(wù)、物流市場的巨大規(guī)模和爆發(fā)式增長,推動著物流體系向更加高效、智能的方向發(fā)展。以無人倉儲、無人搬運車等為代表的物流無人化技術(shù)成為推進(jìn)物流產(chǎn)業(yè)進(jìn)一步發(fā)展的新動力[1]。在無人倉儲系統(tǒng)中,自動導(dǎo)航車對物品進(jìn)行運送作業(yè)的時間占整個系統(tǒng)作業(yè)時間的50%～60%,而揀選作業(yè)的時間由自動導(dǎo)航車運送時間和存/取貨時間兩部分組成,其中對單個商品存取時間基本上不變[2]。因此,優(yōu)化運送路徑,對促進(jìn)無人物流行業(yè)的進(jìn)一步發(fā)展具有重要意義。

常用的路徑規(guī)劃方法按其環(huán)境是否已知,分為全局路徑規(guī)劃和局部路徑規(guī)劃。對于環(huán)境已知的全局路徑規(guī)劃,方法有柵格法[3]、神經(jīng)網(wǎng)絡(luò)法[4]及可視圖法[5]等;對于環(huán)境未全知的局部路徑規(guī)劃,方法有模糊邏輯算法[6]、人工勢場算法[7]及人工蜂群算法[8]等。以上方法在實際路徑規(guī)劃中存在規(guī)劃結(jié)果不佳或規(guī)劃效率較低的問題,因此在這些方法的基礎(chǔ)上涌現(xiàn)了很多改進(jìn)的路徑規(guī)劃方法。胡立華等[9]提出一種基于蟻群算法的動態(tài)路徑規(guī)劃方法,對初始信息使用不均勻分配方式,并在轉(zhuǎn)移概率中引入鄰域安全因子,提高了路徑規(guī)劃效率。周馳等[10]在粒子群(particle swarm optimization,PSO)算法基礎(chǔ)上結(jié)合動態(tài)慣性權(quán)重、變鄰域搜索等策略設(shè)計了一種混合PSO算法對窄巷道倉儲內(nèi)揀選路徑求解,縮短了揀選作業(yè)的路徑時間。藺一帥等[11]將路徑規(guī)劃和貨架優(yōu)化歸為一個整體,提出了一種協(xié)調(diào)優(yōu)化的算法,提高了倉儲內(nèi)的運輸效率。以上算法和模型僅解決了點對點的最優(yōu)路徑規(guī)劃,然而無人倉儲系統(tǒng)內(nèi)自動導(dǎo)航車(automated guided vehicle,AGV)實際運送過程中的目標(biāo)點往往并非單一點,對多個目標(biāo)點的訪問路徑進(jìn)行規(guī)劃才能更貼近實際情況。

針對無人倉儲內(nèi)多目標(biāo)點路徑規(guī)劃的問題,本研究以基于數(shù)字孿生思想構(gòu)建出的虛擬倉儲系統(tǒng)為研究對象,由A-Star算法建立僅保留多目標(biāo)點間節(jié)點關(guān)系的完全圖模型,并提出了一種改進(jìn)的PSO算法對模型求解,通過結(jié)合作物育種學(xué)中遠(yuǎn)緣雜交思想,提高了對模型的求解能力,更易得到孿生倉儲系統(tǒng)內(nèi)多目標(biāo)點的最優(yōu)路徑。

1 基于數(shù)字孿生的倉儲場景設(shè)計

本文所述多目標(biāo)點路徑規(guī)劃問題的研究場景為基于數(shù)字孿生思想構(gòu)建的倉儲系統(tǒng),系統(tǒng)主要包括AGV運動實際場景、AGV運動的虛擬場景及作為孿生數(shù)據(jù)的多目標(biāo)點路徑,基于數(shù)字孿生的倉儲系統(tǒng)如圖1所示。

圖1 基于數(shù)字孿生的倉儲系統(tǒng)

實際場景運行所用AGV為筆者自主設(shè)計的基于視覺和射頻識別(radio frequency identification,RFID)的復(fù)合式導(dǎo)航AGV,在運行環(huán)境內(nèi)的地面上嵌入存有位置信息的無源射頻卡,AGV在運行過程中通過前端的攝像頭及底部的RFID傳感器識別和讀取當(dāng)前位置信息,實現(xiàn)對AGV的導(dǎo)航和定位功能。虛擬場景是基于Three.js3D引擎和超文本5.0構(gòu)建的數(shù)字孿生倉儲系統(tǒng),其尺寸按照實際比例的場景進(jìn)行設(shè)計。場景由位置固定的貨架及運動的AGV模型構(gòu)成,其中AGV模型由實際AGV的裝配體文件轉(zhuǎn)換為模型文件和材質(zhì)文件后導(dǎo)入場景中。虛、實場景內(nèi)的AGV沿孿生數(shù)據(jù)中的多目標(biāo)點軌跡行駛,并通過WebSocket通信協(xié)議實時通信完成虛、實場景內(nèi)的位置同步,以達(dá)到對無人倉儲環(huán)境中AGV運行的監(jiān)控目的。

2 基于遠(yuǎn)緣雜交策略的多目標(biāo)點路徑規(guī)劃

2.1 構(gòu)建柵格化地圖

本研究采用柵格法對孿生倉儲環(huán)境地圖進(jìn)行建模,虛擬場景俯視圖和柵格地圖如圖2所示。虛擬場景柵格化后對應(yīng)的柵格地圖用像素為350×312的圖像表示,其中黑色的區(qū)域代表障礙區(qū)域,白色區(qū)域代表非障礙區(qū)域,貨架的每個貨位在柵格地圖中都對應(yīng)一個駐停點且坐標(biāo)已知。

圖2 虛擬場景俯視圖和柵格地圖

2.2 A-Star算法構(gòu)建圖模型

A-Star算法是一種在靜態(tài)網(wǎng)格地圖中求解點對點最優(yōu)路徑的啟發(fā)式算法,相比其他啟發(fā)式算法具有準(zhǔn)確度高、速度快的優(yōu)點[12]。由于虛擬倉儲對應(yīng)柵格地圖中兩兩目標(biāo)點間可任意連通,因而可將A-Star算法規(guī)劃所得多目標(biāo)點間路徑簡化為圖論中的完全圖,完全圖中節(jié)點表示場景內(nèi)AGV需訪問的目標(biāo)節(jié)點,邊表示由規(guī)劃路徑僅保留兩端節(jié)點關(guān)系抽象出的線段,且用該路徑的長度作為邊的權(quán)值。

A-Star算法搜尋路徑節(jié)點過程中估價函數(shù)為

f(n)=g(n)+h(n)。

(1)

式(1)中:f(n)為起點到目標(biāo)點的總代價;g(n)為起點到當(dāng)前節(jié)點n的實際代價;h(n)為當(dāng)前節(jié)點n到目標(biāo)點的估計代價。

AGV在場景中的運動方式偏向于歐氏距離[13],因此本研究采用歐氏距離作為啟發(fā)式函數(shù):

(2)

式(2)中:xi和yi分別為當(dāng)前節(jié)點在柵格化地圖中的橫、縱坐標(biāo);xn和yn為目標(biāo)節(jié)點在柵格化地圖中的橫、縱坐標(biāo)。

圖3 構(gòu)建5個目標(biāo)點的完全圖模型

假設(shè)目標(biāo)點的個數(shù)為N,即形成一個含有N個節(jié)點的完全圖Kn=(V,E),V和E表示2個集合,其中元素分別為完全圖Kn中的節(jié)點和邊,每對不同節(jié)點間有且只有一條邊相連接,所以E中元素是V的2元子集,即集合E中包含N(N-1)/2個元素。以場景內(nèi)4個目標(biāo)點為例,則包括AGV初始位置需構(gòu)建完全圖K5,K5中包含5個頂點和10條邊。構(gòu)建出5個目標(biāo)點的完全圖模型如圖3所示。

2.3 改進(jìn)的PSO算法的全局規(guī)劃

多目標(biāo)點完全圖的構(gòu)建是將多目標(biāo)點路徑規(guī)劃轉(zhuǎn)化為旅行商的組合優(yōu)化問題,即在完全圖中求解一組編號順序,使得兩兩相鄰編號對應(yīng)邊的權(quán)重和最小。

本研究采用離散的PSO算法[14]對完全圖求解,并在傳統(tǒng)PSO算法基礎(chǔ)上引入基于遠(yuǎn)緣雜交的更新策略。該策略將初始種群進(jìn)行劃分,多個種群相互獨立進(jìn)化,迭代過程中將親緣關(guān)系差異較大的種群進(jìn)行雜交操作,并用雜交后代對種群更新,以提高種群的多樣性,從而優(yōu)化求解效果。

2.3.1 離散的PSO算法

當(dāng)搜索空間為N維時,粒子群中第i個粒子的位置可用向量xi=(xi1,xi2,…,xin)表示,該粒子的速度可用向量vi=(vi1,vi2…vin)表示,其中下角標(biāo)i1,i2…in表示向量xi和向量vi在N維空間內(nèi)不同維度的分量;每個粒子所經(jīng)歷過的最優(yōu)位置稱為個體歷史最優(yōu)位置,記為p;整個粒子群所經(jīng)歷的最優(yōu)位置稱為全局歷史最優(yōu)位置,記為g。各粒子迭代過程中,通過對p和g進(jìn)行學(xué)習(xí)來更新自身的位置xi和速度vi,逐漸向最優(yōu)解靠近。根據(jù)PSO算法處理離散域中交換子和交換序的定義,粒子的速度和位置更新公式[15]可描述為

(3)

(4)

迭代過程中,由適應(yīng)度函數(shù)得到粒子更新后的適應(yīng)度值,并與粒子的p及粒子所處粒子群的g進(jìn)行比較,從而更新p和g。單個粒子的p更新公式如下:

(5)

單個粒子群內(nèi)g更新公式如下:

(6)

2.3.2 粒子個體編碼

基于多目標(biāo)點路徑規(guī)劃模型和完全圖的特點,采用整數(shù)排列方式編碼。單個粒子的編碼序列代表一個完整的運送方案,起始位置始終從0開始,如粒子信息為(4,1,3,2,0)代表的揀選路徑為:起始位置(0)—貨物4—貨物1—貨物3—貨物2—起始位置(0),不同粒子對應(yīng)不同的目標(biāo)點訪問順序。

2.3.3 適應(yīng)度函數(shù)

根據(jù)多目標(biāo)點路徑規(guī)劃的優(yōu)化目標(biāo)和完全圖,得到的適應(yīng)度公式和距離矩陣為

(7)

(8)

式(7)～(8)中:x為單個粒子;m為粒子的長度;i為粒子的位置;xi為粒子中第i個位置對應(yīng)的編號;D(xi,xj)為編號xi到編號xj的距離dxi,xj;D為帶權(quán)完全圖得到的距離矩陣,滿足D=DT,dm,n=dn,m;dm,n為(m-1)與(n-1)對應(yīng)邊的權(quán)重。

2.3.4 基于遠(yuǎn)緣雜交的更新策略

本研究受作物育種學(xué)中遠(yuǎn)緣雜交思想[16]的啟迪,在PSO算法中引入遠(yuǎn)緣雜交的策略,分為3個步驟:對種群進(jìn)行劃分;計算不同種群間親緣關(guān)系的遠(yuǎn)近程度;獲取雜交后代并更新粒子群?；谶h(yuǎn)緣雜交的更新策略具體步驟如下:

1) 對種群進(jìn)行劃分。將種群規(guī)模為n的粒子群劃分為規(guī)模為m的k個種群,其中k滿足m×k=n。在迭代進(jìn)化中k個粒子群相互獨立進(jìn)化,每個粒子群內(nèi)單獨使用式(5)和式(6)對p和g進(jìn)行更新,并將單個粒子群內(nèi)的g作為該粒子群的特征代表粒子參與后續(xù)雜交過程。

2) 多粒子群間親緣關(guān)系的計算。在迭代陷入局部最優(yōu)解后,將多個粒子群的特征代表粒子g組成最優(yōu)解集gs。以窗口長度為2、步長為1的滑動窗口法對最優(yōu)解集內(nèi)的兩兩特征代表進(jìn)行計算,得到表示親緣關(guān)系遠(yuǎn)近的S,S初始值為0,取值范圍為[0,L]內(nèi)整數(shù),L表示粒子的維度即目標(biāo)個數(shù)。假設(shè)取出2個特征代表A、B,A中以窗口截取相鄰編號片段(Pi,Pi+1),在B中滑動窗口從起始位置起依次滑動一個步長尋找是否存在Pi和Pi+1相連片段,若存在則將S的值加1。B中對片段(Pi,Pi+1)搜尋結(jié)束后,A中滑動窗口后移得到片段(Pi+1,Pi+2),并在B中重復(fù)尋找過程和對S更新。重復(fù)上述過程,直至A中的所有相連片段完成尋找過程,得到2個特征代表間的S。圖4為表示相同方案的2個粒子,即S=15,圖5為親緣關(guān)系為3的2個粒子。

圖4 相同方案的2個粒子

圖5 親緣關(guān)系為3的2個粒子

3) 更新粒子群。選取親緣關(guān)系較遠(yuǎn)的g,即S值較小的一對特征代表作為父代雙親,以部分匹配交叉[17](partially matched crossover,PMX)交換雙親粒子內(nèi)的片段獲得雜交后代,并從多個粒子群中選取表現(xiàn)較差的種群,將該粒子群內(nèi)粒子用雜交后代進(jìn)行替換,替換比例記為δ。

2.4 多目標(biāo)點路徑規(guī)劃實現(xiàn)步驟

多目標(biāo)點路徑規(guī)劃流程圖如圖6所示,步驟可總結(jié)如下:

圖6 多目標(biāo)點路徑規(guī)劃流程圖

1) 使用A-Star算法對多個目標(biāo)點兩兩進(jìn)行路徑規(guī)劃,計算得出兩兩目標(biāo)點之間的最短路徑及對應(yīng)長度;

2) 以路徑長度為權(quán)重構(gòu)建多目標(biāo)點的完全圖,并得到式(8)形式的距離矩陣D;

3) 初始化改進(jìn)粒子群算法參數(shù),將粒子群分為種群規(guī)模為m的k個小粒子群,隨機(jī)初始化各粒子群的粒子,得到各粒子的初始位置xi;

4) 使用式(7)和式(8)計算各粒子群中各個粒子的適應(yīng)度值,記錄每個粒子群中每個粒子的p和每個粒子群的g;

5) 使用式(3)和式(4)對粒子速度及位置進(jìn)行更新,并計算更新后的各粒子適應(yīng)度;

6) 每個粒子群內(nèi)獨立使用式(5)和式(6),更新粒子的p及每個粒子群內(nèi)的g,并將多個粒子群的g放入多粒子群最優(yōu)解集gs中,其中的最優(yōu)粒子作為最優(yōu)值A(chǔ);

7) 是否滿足終止條件,是則將點對點路徑與A結(jié)合得到多點路徑,否則轉(zhuǎn)步驟8);

8) 是否滿足雜交條件,是則從gs中的選取親緣關(guān)系較遠(yuǎn)的雙親粒子對進(jìn)行PMX雜交操作,并將gs中適應(yīng)度值最低粒子對應(yīng)粒子群以δ的比例用雜交后代進(jìn)行替換,否則轉(zhuǎn)步驟5)。

3 實例驗證與分析

為了驗證本文算法的有效性和可行性,以場景內(nèi)實例進(jìn)行試驗,對改進(jìn)算法中的相關(guān)參數(shù)進(jìn)行分析,并用引入遠(yuǎn)緣雜交策略的改進(jìn)的PSO算法與PSO算法、禁忌搜索(tabu search,TS)算法分別對多目標(biāo)點的完全圖進(jìn)行求解,對試驗結(jié)果進(jìn)行比較。試驗中最大迭代次數(shù)設(shè)為100,其中PSO算法中粒子數(shù)目設(shè)為40,p到粒子交換子的保留概率α設(shè)為0.7,g到粒子交換子的保留概率β設(shè)為0.8;改進(jìn)的PSO算法中上述參數(shù)與PSO算法相同;TS算法中禁忌表長度設(shè)為20。試驗運行環(huán)境:操作系統(tǒng)為Windows10,處理器為AMD5800H,CPU為3.20 GHz,內(nèi)存為16 GB,試驗平臺為PyCharm2020。

3.1 替換比例δ的試驗分析

為驗證雜交后代替換粒子群比例δ對路徑尋優(yōu)效果的影響,以場景內(nèi)20個點作為訪問目標(biāo)點構(gòu)建完全圖,并對δ∈{0,0.2,0.4,0.6,0.8,1}的每個取值分別進(jìn)行10次試驗,記錄每次試驗的最優(yōu)路徑長度。δ取不同值時本文算法的試驗結(jié)果、10次結(jié)果的平均值分別如圖7、圖8所示,從圖中可知,起初隨著δ取值的增大,路徑尋優(yōu)的總長度逐漸減小,達(dá)到某一閾值后,替換比例的增加會導(dǎo)致尋優(yōu)效果下降。從結(jié)果可知,本試驗中當(dāng)δ=0.6時算法的尋優(yōu)性能更好。

圖7 δ取不同值時本文算法的試驗結(jié)果

圖8 10次結(jié)果的平均值

3.2 種群劃分的試驗分析

遠(yuǎn)緣雜交策略中對種群的劃分參數(shù)直接影響算法的搜索效果,為選取遠(yuǎn)緣雜交策略中種群的劃分個數(shù)k和單個種群規(guī)模m的最佳值,分別在(m,k)取值為(10,4)、(8,5)、(5,8)和(4,10)且其他參數(shù)相同的條件下進(jìn)行10次試驗,結(jié)果見表1。由表1可知,在粒子群總規(guī)模為40時,將粒子群劃分為4個規(guī)模為10的小種群,搜索到的路徑長度在最短路徑和平均值上都更優(yōu)。

表1 不同劃分方式的10次試驗結(jié)果

3.3 算法對比試驗

為了檢驗本文算法的優(yōu)越性,采用場景內(nèi)目標(biāo)點個數(shù)為15、30、50三種規(guī)模的實例進(jìn)行驗證,由A-Star算法構(gòu)建出實例的完全圖后,分別使用改進(jìn)的PSO算法、PSO算法和TS算法進(jìn)行10次試驗,不同規(guī)模下的路徑長度迭代收斂對比結(jié)果如圖9所示。

圖9 本文算法與PSO算法、TS算法不同規(guī)模下的路徑長度迭代收斂對比

根據(jù)圖9(a),在目標(biāo)點規(guī)模為15時改進(jìn)的PSO算法與PSO算法和TS算法相比,搜索到的最短路徑略優(yōu),但由于搜索空間的復(fù)雜度較低,改進(jìn)的PSO算法的優(yōu)勢不明顯。改進(jìn)的PSO算法、PSO算法和TS算法10次路徑長度的平均值分別為683.0、699.7、685.7。

由圖9(b)和(c)可知,目標(biāo)點規(guī)模增大至30、50時,改進(jìn)的PSO算法搜尋到的最短路徑與PSO算法和TS算法相比表現(xiàn)出更明顯的優(yōu)勢。通過觀察圖9(b)和(c),可以發(fā)現(xiàn)在迭代過程中改進(jìn)的PSO算法的階梯下降次數(shù)最多,TS算法的下降次數(shù)最少,即改進(jìn)的PSO算法在跳出局部最優(yōu)解的性能更強(qiáng);而對下降區(qū)域進(jìn)行觀察,可知在迭代前期3種算法的收斂過程差異并不大,主要是因為迭代前期雙親粒子優(yōu)良特性的片段較少,進(jìn)行遠(yuǎn)緣雜交的后代獲取到優(yōu)良特性概率較小。隨著迭代過程的進(jìn)行,粒子群內(nèi)的優(yōu)良片段不斷匯聚,遠(yuǎn)緣雜交策略使得不同粒子群長期積累的優(yōu)良特性得以交換。因此在迭代后期,改進(jìn)的PSO算法在下降次數(shù)上明顯多于PSO算法和TS算法,且最終的收斂值更小。改進(jìn)的PSO算法、PSO算法和TS算法在目標(biāo)點規(guī)模為30時,3種算法所得路徑長度的平均值分別為1 037.3、1 120.9、1 078.9,比PSO算法和TS算法規(guī)劃性能分別提升了7.4%、3.8%;在目標(biāo)點為50時,路徑長度的平均值為1 782.0、1 988.5、1 841.0,比PSO算法和TS算法規(guī)劃性能分別提升了10.3%、3.2%。

3.4 虛擬場景內(nèi)運行測試

采用δ=0.6、m=10、k=4的參數(shù)設(shè)置,對目標(biāo)點個數(shù)為15的實例進(jìn)行規(guī)劃(圖10),實例在柵格地圖中規(guī)劃結(jié)果如圖10(a)所示,其中實線表示最優(yōu)路徑,路徑的總長度為683,路徑1和路徑2為多次迭代中出現(xiàn)的較為接近最優(yōu)解的路徑,路徑長度分別為708和758。最優(yōu)路徑坐標(biāo)經(jīng)過處理后得到AGV在虛擬場景內(nèi)的運動路徑,虛擬場景內(nèi)AGV的運動過程如圖10(b)所示。

圖10 目標(biāo)點為15的實例

4 結(jié) 語

本研究針對無人倉儲系統(tǒng)內(nèi)AGV多目標(biāo)點運送路徑問題,以基于數(shù)字孿生思想構(gòu)建出的AGV運動虛擬倉儲場景為研究對象,結(jié)合A-Star算法和改進(jìn)的PSO算法在虛擬倉儲內(nèi)規(guī)劃出多個目標(biāo)點的最短路徑。針對PSO算法迭代過程中多樣性下降,易陷入局部最優(yōu)解的問題,利用作物育種學(xué)中遠(yuǎn)緣雜交思想設(shè)計了一種改進(jìn)的PSO算法,提高了種群多樣性,更易搜尋到較優(yōu)解。試驗結(jié)果表明,該方法在倉庫多目標(biāo)點路徑優(yōu)化尤其是較大規(guī)模的問題上具有更好的尋優(yōu)性能。然而,本文方法僅適用于多目標(biāo)點間兩兩互通的倉儲場景,今后的研究會考慮更為復(fù)雜的場景。此外,將遠(yuǎn)緣雜交策略應(yīng)用于其他智能算法之中也可能作為下一階段的研究目標(biāo)。