徐 興，錢譽欽，趙 蕓，張 云，陳小依，呂曉姝

(1.浙江科技學院 機械與能源工程學院，浙江 杭州 310023；2.心怡科技股份有限公司，浙江 杭州 310023；3.浙江科技學院 信息與電子工程學院，浙江 杭州 310023;4.阿爾托大學 建筑學院，芬蘭 赫爾辛基 02150)

0 引言

智能倉儲系統(tǒng)(Intelligent Storage System，ISS)是一種通過計算機控制，能夠?qū)}庫實時容量和貨物位置全面掌握的一種管理系統(tǒng)，其主要通過貨運小車和相關(guān)搬運設(shè)備來實現(xiàn)貨物的自動出入庫和倉儲的管理。在制造企業(yè)的智能倉儲系統(tǒng)中，貨物的轉(zhuǎn)移作業(yè)是智能倉儲系統(tǒng)中最常見作業(yè)方式，同時也是體現(xiàn)其效率的最關(guān)鍵點。選擇最優(yōu)化的倉位間的三維運行路徑是提高智能倉儲系統(tǒng)整體運行效率的有效方法。

目前，國內(nèi)外主流的運用于運動機器人的路徑規(guī)劃算法主要包括局部搜索算法[1-2]、模擬退火算法、禁忌搜索算法、狼群算法、蟻群算法等[3]。這些算法中部分算法具有較好的運行時間優(yōu)勢，但是又很容易陷入局部最優(yōu)。在這些算法成果中，對于倉儲系統(tǒng)三維路徑優(yōu)化問題的研究成果不在少數(shù)，如夏緒輝等[4]將時間和能耗引入倉庫三維空間內(nèi)的路徑優(yōu)化，提高了算法的全局優(yōu)化性能，并有效地平衡了作業(yè)的能耗和作業(yè)的效率，提高了整體作業(yè)過程的綠色程度；楊瑋等[5]在密集倉儲系統(tǒng)的路徑優(yōu)化中對蟻群算法進行改進，引入遺傳算法從而優(yōu)化了其初始信息素的參數(shù)，使算法具有更好的全局性能，提高了整個系統(tǒng)的運行效率；劉利強等[6]研究了水下下潛器的三維空間路徑優(yōu)化，以蟻群系統(tǒng)(Ant Colony System, ACS)作為基礎(chǔ)，詳細研究了算法中信息素的表示方法和更新規(guī)則、路徑點的選取原則以及啟發(fā)函數(shù)的設(shè)計；李浩宇等[7]運用柵格離散的方法創(chuàng)建三維空間環(huán)境地圖并引入了蟻群算法，得到了較快的收斂速度、較好的穩(wěn)定性和更高的計算效率；陳家照等[8]將改進粒子群優(yōu)化算法引入三維空間路徑規(guī)劃，對迭代過程中算法慣性系數(shù)分段設(shè)置和隨機擾動粒子位置的方式進行改進，有效地提高了粒子群優(yōu)化算法的計算效率和可靠性；方彥軍等[9]主要針對軌道小車，采用人工狼群算法并引入禁忌表和擁堵因子采取自適應(yīng)步長來避免算法陷入局部最優(yōu)，同時也加快了后期收斂的速度；趙威等[10]將局部搜索算法結(jié)合三維空間路徑優(yōu)化，引入信息素因子和勢場因子，使得迭代次數(shù)降低，路徑點軌跡也更加平穩(wěn)；Ma等[11]考慮作業(yè)載重和行駛距離等各方面因素,建立了一個多目標的路徑優(yōu)化模型，通過一種集成學習的優(yōu)化算法降低了時間復(fù)雜度，解決了自動化的立體倉庫的時間規(guī)劃問題。

上述研究雖然對路徑優(yōu)化或者三維空間的適用性提出了各自的方法，但是在制造企業(yè)倉儲系統(tǒng)中，特別是基于貨架式的倉庫中，自動導(dǎo)引小車(Automated Guided Vehicle，AGV)的三維空間路徑優(yōu)化研究尚存在一定缺陷，主要在三維空間中多目標點的路徑選擇方面，目前研究僅針對二維平面的AGV路徑選擇；算法的選擇與優(yōu)化方面，目前研究使用的算法時間復(fù)雜度較高、運行時間冗余。因此，本文主要針對制造企業(yè)倉儲系統(tǒng)的AGV在貨架間的三維空間路徑優(yōu)化開展研究，在提高程序運行效率的同時，實現(xiàn)AGV的運行路線距離最短。

1 三維空間路徑優(yōu)化問題建模

1.1 問題描述

在制造企業(yè)的智能倉儲系統(tǒng)中，AGV是關(guān)鍵的作業(yè)承擔者，AGV參與倉儲系統(tǒng)中入庫作業(yè)和出庫作業(yè)兩種模式。在作業(yè)過程中，多目標點之間遍歷式操作是當前倉儲作業(yè)的一種高效率的作業(yè)方式。對于單一AGV在多目標點之間遍歷式作業(yè),需要多目標點的定位，以及準確且快速的路徑選擇，且現(xiàn)有倉儲系統(tǒng)多為貨架式倉庫需要進行三維定點以及三維空間的路徑規(guī)劃。對于三維平面的路徑規(guī)劃，不僅需要考慮水平面上AGV小車的運動，還要考慮其垂直平面上的運動以及跨貨道間的運行路線。本文研究的工業(yè)場景為立體倉庫，實驗通過模擬現(xiàn)實貨架和AGV來進行操作。所述模型如圖1所示，現(xiàn)實實驗場景如圖2和圖3所示。

本文所述倉庫為某企業(yè)特定形式的立體倉庫，可供AGV在同平面以及跨平面間進行作業(yè)運動，且本文所研究的AGV可以進行多目標點歷遍式作業(yè)，免去了兩點式作業(yè)(起始點到單一目標點)的多余路線與運行時間。基于本文特定實驗場所，AGV能夠在一個貨道內(nèi)進行上下與前后操作，但是跨貨道操作必須退到貨道外。

根據(jù)立體倉庫模型以及多目標定位點定位后，本文中AGV對于貨物的出入庫作業(yè)描述為如下3個環(huán)節(jié)：①AGV到達其自身位置最近的某一目標點，作為起始點開始作業(yè)；②AGV通過計算后得到的目標點運行順序從起始點出發(fā)一次到達下一個目標點，并進行作業(yè)；③AGV在歷遍所有目標點完成相關(guān)作業(yè)以后回到起始位置等待下一步指令。當AGV接收到系統(tǒng)任務(wù)時，其目標點之間的運行順序直接影響了單臺AGV的作業(yè)效率以及運行時間。因此各個目標點最短路徑的優(yōu)化將是系統(tǒng)整體運行效率的體現(xiàn)。

1.2 數(shù)學模型

根據(jù)本文所針對適用的三維立體倉庫模型，假設(shè)AGV能夠在三維空間內(nèi)運動，且運動路徑只能是水平與豎直的兩個方向。水平方向的運動是通過AGV自主運行，而豎直方向的運動是通過升降機來輔助運行，升降機的運動和AGV的運動在啟動與分離時的速度影響與時間影響的考慮均設(shè)定為均值，對之后的路徑選擇與優(yōu)化不會產(chǎn)生影響。

與其他倉儲系統(tǒng)路徑優(yōu)化問題研究不同的是，本文將制造企業(yè)倉儲系統(tǒng)中的路徑優(yōu)化問題擴大到三維平面，并根據(jù)倉庫的實際情況，在路徑中加入添加點，從而實現(xiàn)AGV小車的運行路徑平行于X，Y，Z軸。

本文研究將AGV運行軌跡分為如下三類運動，分別是：①兩點在同一平面內(nèi)，并且有相同的X坐標或Y坐標或Z坐標；②兩點在同一平面內(nèi)，并且X，Y坐標或X,Z坐標或Y，Z坐標均不相同；③兩點在不同平面內(nèi)，且X，Y，Z坐標均不相同。

假設(shè)兩點的空間坐標分別為i=(x1,y1,z1)，j=(x2,y2,z2)。當AGV做一類運動時，其基本的物理位移公式為：

S=|y1-y2|或|z1-z2|。

其次，當要進行X方向上的運行操作時，由于要跨巷道運行，需要將小車退到巷道口來實現(xiàn)X方向上的移動，其基本的物理位移公式為：

S=2|y|+|x1-x2|。

當AGV做二類運動時，由于在同一平面內(nèi)但是又并非同一直線，需要添加一個輔點來幫助AGV小車來實現(xiàn)兩點間的運動。當要進行X方向上的運行操作時，由于要跨巷道運行，需要將小車退到巷道口來實現(xiàn)X方向上的移動，從而實現(xiàn)小車運行的路徑平行于坐標軸。其基本的物理位移公式為：

S=|x1-x2|+|y1|+|y2|或

S=|x1-x2|+|z1-z2|+2|y|或

S=|y1|+|y2|+|z1-z2|

當AGV做第三類運動時，由于不在同一平面，并且X，Y，Z坐標均不相同，其實現(xiàn)的是跨平面間的運動，因此需要添加兩個輔助點來實現(xiàn)兩點間的運動。當要進行X方向上的運行操作時，由于要跨巷道運行，需要將小車退到巷道口來實現(xiàn)X方向上的移動，從而實現(xiàn)小車的運行路徑平行于坐標軸。其基本的物理位移公式為：

S=|x1-x2|+|y1|+|y2|+|z1-z2|。

2 基于三維空間路徑的改進蟻群算法設(shè)計

2.1 蟻群算法

蟻群算法[12](Ant Colony Algorithm, ACA)由Macro Dorigo在1992年提出，是一種群優(yōu)化算法，模擬自然界中螞蟻群的覓食行為。螞蟻在尋找食物源的時候，會在其經(jīng)過的路徑上釋放一種信息素，其他螞蟻能夠感知這種信息素。將此行為抽象到算法當中時，信息素濃度的大小表征了目標點路徑的遠近，信息素的濃度越高，表示對應(yīng)的路徑越短。通常情況下，螞蟻會優(yōu)先選擇信息素濃度較高的路徑，并且其自身會釋放一定量的信息素，從而增強了該條路徑上信息素的濃度，因此形成了一個正反饋機制，同時信息素的濃度也會隨著時間的推移而減弱。最終，可以通過不斷的迭代獲得一段從出發(fā)點到目的地的最短的路徑。

路徑優(yōu)化問題映射到算法當中就是求解最優(yōu)解的問題，其目的是通過蟻群算法來求解最短路徑。在蟻群算法中，路徑較短的螞蟻釋放的信息素的量較多，隨著時間的推移，在較短路徑上累積的的信息素濃度逐漸增高，因此選擇該路徑的螞蟻數(shù)量也逐漸增多。最終，整個螞蟻群會在正反饋的作用下集中到最短路徑上，此時對應(yīng)的解即為最優(yōu)解。

通過蟻群算法原理，可以得出每一只螞蟻選擇的下一個目標點的概率公式為[13]：

當螞蟻走過所有路徑點以后，返回原來起始點，從而完成一次路徑的循環(huán)，之后再一次更新信息素。因此，每條路徑上的信息素總共分為兩個部分：①前一次螞蟻通過路徑時所遺留且還未揮發(fā)的信息素；②當前螞蟻所經(jīng)過時留下的信息素。因此其信息素的迭代公式為[14]：

τij(t+n)=(1-ρ)·τij+Δτij(t,t+n),

蟻群算法具有如下特點：

(1)采用正反饋機制，使得搜索過程不斷的收斂，最終逼近最優(yōu)解。

(2)每個個體可以通過釋放信息素來改變周圍環(huán)境，且每個個體能夠感知周圍環(huán)境的實時變化，個體間通過環(huán)境間接地通訊。

(3)搜索過程采用分布式的計算方式，多個個體同時進行并行計算，大大的提高了算法的計算能力和運行效率。

(4)啟發(fā)式的搜索方式，不容易陷入局部最優(yōu)解，易于找到全局最優(yōu)解。

2.2 改進蟻群算法三維空間路徑的實現(xiàn)方法

在蟻群算法中，螞蟻被隨機分配到各個點位，并且需要游歷所有的目標點，其目標點順序的選擇與轉(zhuǎn)移概率有關(guān)，而各個點之間的轉(zhuǎn)移概率由路徑間的信息素濃度和啟發(fā)式因子決定。每條路徑上信息素的濃度通過上述的迭代公式來計算，而啟發(fā)式因子根據(jù)現(xiàn)實情況來確定。

針對倉庫內(nèi)三維立體貨架，需要考慮水平面與垂直平面上AGV小車的運行路徑的選擇。本文依托于現(xiàn)有倉庫，以及其中貨架的擺放情況，優(yōu)化了蟻群算法，將原有兩點間直線路徑更改為平行于各個坐標軸的折線路徑。

引入cenpt變量，來確定添加點的個數(shù)，部分MATLAB代碼如下：

cenpt=0;

if C(R(i),1)～=C(R(i+1),1)

cenpt = cenpt+1;

end

if C(R(i),2)～=C(R(i+1),2)

cenpt = cenpt+1;

end

if C(R(i),3)～=C(R(i+1),3)

cenpt = cenpt+1;

end

當cenpt=3時，表示兩點X，Y，Z坐標均不相同，則需要加入3個添加點，其坐標分別是a=(x1,0,z1),b=(x2,0,z1),c=(x2,y2,z1),以及實現(xiàn)的兩點間具體路徑為：i→a→b→c→j;當cenpt=2時，表示兩點的某一個坐標值相同，只需要加入一個添加點，(當X坐標相同)添加點坐標為a=(x,y2,z1),兩點間的具體路徑為：i→a→j，(當Y或Z坐標相同)則需要3個添加點，其坐標為a=(x1,0,z),b=(x2,0,z),c=(x2,y2,z)，以及實現(xiàn)的兩點間具體路徑為：i→a→b→c→j;當cenpt=1時，表示兩點間的某兩個坐標值相同，則不需要加入添加點，兩點間的具體路徑為：i→j。

本文提出的基于三維空間路徑的改進蟻群算法具體步驟如下：

步驟1將算法內(nèi)的變量初始化，設(shè)置算法的最大迭代次數(shù)Nc_max，以及螞蟻的總數(shù)為m，并且將螞蟻隨即放在各個點位上。信息素因子設(shè)置為Alpha,啟發(fā)因子Beta，信息素的蒸發(fā)系數(shù)Rho，以及信息素的加強系數(shù)Q。

步驟2每只螞蟻隨機分配起始點，確定每個螞蟻初始的信息素，逐個螞蟻進行路徑選擇，將到達的目標點位加入到禁忌表中，避免重復(fù)訪問，并且初始化解空間。通過概率函數(shù)來進行下一個目標點的選擇，m只螞蟻按照概率函數(shù)選擇下一個點，完成各自周游。概率函數(shù)通過當前點與其余點的距離的倒數(shù)來確定，并在每一步訪問后實時更新禁忌表，且運用cumsum函數(shù)將每段路徑元素累加求和。其概率計算公式如下[15]：

ηij=λexp(ιn,e-ιn+1,e)。

當完成一次所有點的訪問循環(huán)，比較每一只螞蟻的路徑距離，記錄本次迭代的最短路徑以及所有螞蟻循環(huán)后的平均距離。具體代碼如下：

for i=1:(ceil(m/n))

Randpos=[Randpos,randperm(n)];

end

Tabu(:,1)=(Randpos(1,1:m))';

for j=2:n

for i=1:m

visited=Tabu(i,1:(j-1));

J=zeros(1,(n-j+1));

P=J;

Jc=1;

for k=1:n

If length(find(visited==k))==0

J(Jc)=k;

Jc=Jc+1;

end

End

%下面計算待選點的概率分布

for k=1:length(J)

P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);

end

P=P/(sum(P));

%按概率原則選取下一個點

Pcum=cumsum(P);

Select=find(Pcum>=rand);

to_visit=J(Select(1));

Tabu(i,j)=to_visit;

end

end

if NC>=2

Tabu(1,:)=R_best(NC-1,:);

End

步驟2判斷k的值，若k≥m，表明該螞蟻已經(jīng)歷遍了所有目標點則繼續(xù)步驟4，否則返回步驟2。

步驟3更新全局信息素，迭代后將下一次路徑循環(huán)上的信息素蒸發(fā)系數(shù)Rho，以及信息素加強系數(shù)Q進行更新。再進行全局信息素更新時，該模型能夠很好地將全局路徑上的信息素統(tǒng)一歸納更新。其更新信息素公式如下[11]：

τij(t+1)=ρ·τij(t)+Δτij(t),

L=zeros(m,1);

for i=1:m

R=Tabu(i,:);

for j=1:(n-1)

L(i)=L(i)+D(R(j),R(j+1));%原距離加上第j個點到第j+1個點的距離

end

L(i)=L(i)+D(R(1),R(n));

end

L_best(NC)=min(L);

pos=find(L==L_best(NC));

R_best(NC,:)=Tabu(pos(1),:);

L_ave(NC)=mean(L);%此輪迭代后的平均距離

NC=NC+1;

Delta_Tau=zeros(n,n); %更新信息素

for i=1:m

for j=1:(n-1) Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);

End

步驟5禁忌表的清零與實驗結(jié)果的輸出。當達到最大迭代次數(shù)以后，將禁忌表清零。最后優(yōu)化信息素增量函數(shù)，進行多次迭代，待算法能夠收斂，比較所有次迭代的最短路徑與其最短距離，得到巡回所有點的最優(yōu)調(diào)度順序。該算法的基本思維運行結(jié)構(gòu)如圖4所示。

3 仿真實驗對比與結(jié)果分析

本文借助MATLAB R2014a實驗平臺來對該算法進行仿真實驗，以驗證該算法的有效性。以某大型制造企業(yè)內(nèi)部倉儲系統(tǒng)為研究對象，該倉儲系統(tǒng)中有12列貨架，每列貨架有4層，每層包含30個倉位，共計1 440個倉位。針對本文所應(yīng)用的AGV，均可在貨架間的巷道與貨架上按照貨架固有的結(jié)構(gòu)作業(yè)，并且AGV可以進行多目標點歷遍式作業(yè)。為驗證本文算法的優(yōu)越性，采用遺傳算法、普通蟻群算法作為比較對象，對相同數(shù)量的目標點進行路徑優(yōu)化對比，并進行多次實驗對比，以確保其準確性有效地降低了小概率偶然因素的影響。本次實驗優(yōu)化蟻群算法的各個參數(shù)設(shè)置為：最大迭代次數(shù)NC_max=100;螞蟻數(shù)量m=30;信息素因子Alpha=1.5;啟發(fā)因子Beta=2;信息素蒸發(fā)系數(shù)Rho=0.1;信息素加強系數(shù)Q=106。實驗結(jié)果曲線如圖5和圖6所示。

圖5和圖6所表示的是不同算法在不同數(shù)量目標標點作業(yè)之后的收斂效果對比。由圖5和圖6可知，雖然每種算法都能很好地得到收斂效果，但是在不同次作業(yè)下，本文所用的優(yōu)化蟻群算法具有更快的反應(yīng)時間和更少的迭代次數(shù)。

通過具體實驗，由于本文實驗倉庫有12列貨架，而實驗AGV在貨架間運行需要從每一列貨架退出再進入操作，為了能在每列貨架上都有操作機會，檢測最大化的時間，所以本實驗隨機生成了12個目標點來進行仿真實驗，獲得的結(jié)果如圖7和圖8所示。

由圖7可得此次仿真實驗通過迭代得到的最短距離以及平均距離，圖中下方折線即為最短距離，本次仿真實驗的12個目標點之間的最短距離為100個單位，而上方折線即為當次迭代的平均距離。由此可知，迭代次數(shù)的增加對路徑的優(yōu)化有很好的作用，各次平均距離有大幅度的下降。而通過圖8能更加直觀地看到在本次仿真實驗中獲得的12個隨機點的最短路線軌跡，圖中實心點為本次最短路徑的起始點，黑圈點為所要經(jīng)過的各個目標點而白圈點即為生成路徑所需要的添加點。如表1所示，本文隨機生成了12個目標點X坐標范圍是(1，12)，Y坐標范圍是(1，30)，Z坐標范圍是(1，4)。通過表2可以更加直觀地看到本次仿真實驗在12個目標點之間的路徑運行順序。通過圖7與圖8，可以得到本文所用的優(yōu)化蟻群算法對于實驗倉庫有很好的適用性，通過極少次的迭代就能夠獲得多個隨機目標點之間的最短路徑，并且能直觀地看到本文所創(chuàng)新的添加點在軌跡路線中的作用。

表1 仿真實驗的隨機生成的目標點

表2 仿真實驗?zāi)繕它c運行順序

4 結(jié)束語

本文研究了在制造企業(yè)內(nèi)倉儲系統(tǒng)立體貨架中AGV小車對于三維空間下的路徑優(yōu)化算法，在原有二維平面的蟻群算法路徑選擇的基礎(chǔ)上，針對其AGV的運行空間，將二維平面擴張到三維空間中，使其能夠在多個三維空間點中找到最優(yōu)路徑。利用兩目標點之間增加添加點的思想以及現(xiàn)實環(huán)境中立體倉庫貨架的運作方法，拓展了原有蟻群算法中路徑距離的計算方法，雖然增加了具體路線的長度，但是優(yōu)化計算得到的路徑更加適用于當前制造企業(yè)中的倉儲環(huán)境。通過改進算法中的概率模型與禁忌表的思想，有效解決地避免了陷入局部最優(yōu)的情況。最后，通過制造企業(yè)的案例分析，證實了該算法的實用性以及可行性，其能夠很好地解決現(xiàn)實倉庫中AGV的路徑規(guī)劃問題。下一步將針對AGV集群在本實驗環(huán)境中的三維空間路徑優(yōu)化展開研究。