考慮時間和能耗的立體倉庫三維空間路徑優(yōu)化

夏緒輝，朱 強(qiáng)，王 蕾,2，曹建華

(1.武漢科技大學(xué)冶金裝備及其控制教育部重點(diǎn)實(shí)驗(yàn)室，湖北 武漢，430081；2.武漢科技大學(xué)服務(wù)科學(xué)與工程研究中心，湖北 武漢，430065)

自動化立體倉庫系統(tǒng)(Automatic Storage & Retrieval System，AS/RS)集存儲、輸送、分發(fā)、管理等功能于一體，具有存儲容量大、占地面積小、運(yùn)轉(zhuǎn)速度快等特點(diǎn)，是現(xiàn)代物流系統(tǒng)的重要組成部分，在物料供給部門、大型商業(yè)系統(tǒng)等領(lǐng)域有著廣泛的應(yīng)用。搬運(yùn)作業(yè)是自動化倉庫中最常見的作業(yè)方式，合理選擇作業(yè)路徑是提高自動化立體倉庫運(yùn)行效益的有效手段。

近年來，針對AS/RS路徑優(yōu)化問題的研究成果有不少。例如：田國會等[1]在分析立體倉庫揀選作業(yè)時間組成的基礎(chǔ)上建立優(yōu)化模型，采用混合遺傳算法進(jìn)行求解；方彥軍等[2]以軌道引導(dǎo)小車作業(yè)距離最短為目標(biāo)建立數(shù)學(xué)模型，通過改進(jìn)人工狼群算法求解，提高了倉庫的運(yùn)行效率；朱文真等[3]研究立體倉庫中單一作業(yè)和復(fù)合作業(yè)的路徑優(yōu)化問題，設(shè)計(jì)了一種遺傳禁忌混合算法對堆垛機(jī)作業(yè)路徑進(jìn)行求解；楊瑋等[4]構(gòu)建了以時間最少為目標(biāo)且考慮加速度影響的調(diào)度優(yōu)化模型，采用混合蟻群算法求解，提高了密集倉儲系統(tǒng)進(jìn)出庫效率；蔡安江等[5]建立以堆垛機(jī)調(diào)度時間最小為目標(biāo)的優(yōu)化模型，采用遺傳算法求解，提高了立體倉庫的運(yùn)行效率；Ma等[6]為解決自動化立體倉庫的時間規(guī)劃問題，考慮作業(yè)載重和行駛距離等因素建立多目標(biāo)路徑優(yōu)化模型，設(shè)計(jì)一種基于集成學(xué)習(xí)的優(yōu)化算法，降低了調(diào)度時間；Azzi等[7]在堆垛機(jī)運(yùn)行時間模型中考慮加速度的影響，采用蒙特卡洛分析方法來求解，并通過實(shí)例驗(yàn)證了模型的可行性；Nia等[8]針對單機(jī)負(fù)載多機(jī)架AS/RS，建立以時間成本和碳排放成本最小為優(yōu)化目標(biāo)的低碳數(shù)學(xué)模型，通過具體實(shí)例驗(yàn)證模型的有效性；Meneghetti等[9]研究了立體倉庫中貨位分配問題并建立能耗模型，將能量消耗最少的位置分配給存取頻率最高的貨物，減少了倉庫貨物分配時間和能耗；Lerher等[10]針對微型負(fù)載AS/RS建立以電能消耗為基礎(chǔ)的能效模型，通過仿真驗(yàn)證了模型的有效性；Ene等[11]在立體倉庫訂單分配過程中考慮能耗因素，建立以貨叉電機(jī)耗電量最少為優(yōu)化目標(biāo)的數(shù)學(xué)模型，采用遺傳算法對其求解。

現(xiàn)有關(guān)于AS/RS路徑優(yōu)化問題的研究多以時間、距離等為優(yōu)化目標(biāo)，雖有涉及能耗，但大多只考慮單目標(biāo)優(yōu)化。本文針對自動化立體倉庫在三維空間內(nèi)的路徑規(guī)劃問題，在考慮堆垛機(jī)運(yùn)動過程中加速度、搬運(yùn)距離及載重對能耗影響的基礎(chǔ)上，從運(yùn)動學(xué)的角度建立能耗模型，為綜合體現(xiàn)時間與能耗兩方面因素對路徑選擇的影響，構(gòu)建以堆垛機(jī)作業(yè)過程綠色度[12]最大為目標(biāo)的優(yōu)化模型。為提高基本蟻群算法的收斂速度及避免陷入局部最優(yōu)，提出一種基于免疫蟻群的路徑優(yōu)化算法對模型進(jìn)行求解，并通過實(shí)例仿真驗(yàn)證所建模型的適用性及算法的有效性，以期為堆垛機(jī)作業(yè)路徑選擇提供一種新的思路和方法。

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

1.1 問題描述

自動化立體倉庫主要包括巷道式、貫通式、水平旋轉(zhuǎn)式和垂直旋轉(zhuǎn)式等類型，其中巷道式立體倉庫是一種最為典型的倉儲形式，如圖1所示。假設(shè)各貨位可存儲某種尺寸的貨物，坐標(biāo)(x,y,z)分別對應(yīng)貨位所在的排、列和層，各貨格的長、寬、高分別為l、w、h。圖1中O為出入庫臺，P為第i次入庫貨位，R為第j次出庫貨位，堆垛機(jī)在作業(yè)巷道往返運(yùn)動并負(fù)責(zé)貨物搬運(yùn)。

圖1 自動化立體倉庫簡圖

堆垛機(jī)的作業(yè)形式分為單指令作業(yè)和雙指令作業(yè)。單指令作業(yè)指堆垛機(jī)進(jìn)入倉庫只完成一次貨物的出庫或入庫作業(yè)；雙指令作業(yè)指堆垛機(jī)執(zhí)行的任務(wù)序列中同時存在出庫與入庫指令，堆垛機(jī)進(jìn)入倉庫一次完成一個入庫任務(wù)和一個出庫任務(wù)。為了便于分析，將堆垛機(jī)運(yùn)動沿水平和垂直方向分解，每個方向上有其自身的運(yùn)動形式。

對于單指令作業(yè)：在入庫環(huán)節(jié)，堆垛機(jī)裝載目標(biāo)貨物后，從O點(diǎn)出發(fā)，沿著巷道運(yùn)動到待入庫貨位所在的列和行，完成入庫任務(wù)后沿作業(yè)巷道回到O點(diǎn)；在出庫環(huán)節(jié)，堆垛機(jī)從O點(diǎn)出發(fā)，沿著作業(yè)巷道運(yùn)動到待出庫貨位所在的列和行，裝載貨物后沿作業(yè)巷道返回至O點(diǎn)。

對于雙指令作業(yè)：堆垛機(jī)完成入庫環(huán)節(jié)后，空載運(yùn)動到待出庫貨位所在的列和行，裝載貨物后沿作業(yè)巷道返回至O點(diǎn)，完成出庫任務(wù)。

考慮堆垛機(jī)在運(yùn)動過程中存在加速度，根據(jù)其運(yùn)行速度能否達(dá)到額定速度(vmax)，將運(yùn)動形式分為第I類運(yùn)動(SI≤Slim)和第II類運(yùn)動(SII>Slim)，如圖2所示。

圖2 兩類運(yùn)動的位移-速度曲線

Fig.2Displacement-velocitycurvesoftwokindsofmovement

1.2 數(shù)學(xué)模型

模型假設(shè)：①貨物質(zhì)量小于機(jī)器人的額定載荷；②堆垛機(jī)在下一輪入庫作業(yè)時，貨物已到達(dá)出入庫臺，以保證任務(wù)的連續(xù)性；③堆垛機(jī)的啟動、停止、裝載、卸載及定位的時間均為固定值，不考慮其對優(yōu)化結(jié)果的影響。

1.2.1 堆垛機(jī)路徑時間模型

堆垛機(jī)在水平和垂直方向上的運(yùn)動形式取決于其在兩個方向上行駛的距離。根據(jù)基本位移公式，堆垛機(jī)在兩個方向上達(dá)到額定速度所需的臨界距離為：

(1)

(2)

對于第I類運(yùn)動，當(dāng)水平和垂直方向上運(yùn)行距離分別為Sx和Sz時，其所用的時間為：

(3)

(4)

對于第II類運(yùn)動，當(dāng)水平和垂直方向上運(yùn)行距離分別為Sx和Sz時，其所用的時間為：

(5)

(6)

綜合考慮以上兩類運(yùn)動形式，得到水平和垂直方向上的行駛時間tx、tz分別為：

(7)

(8)

機(jī)器人從出入庫臺運(yùn)行至目標(biāo)貨位，總的行駛時間是水平和垂直行駛時間的最大值，即：

t=max(tx,tz)

(9)

由堆垛機(jī)單雙指令流程可知，完成Q1次單指令任務(wù)及Q2次雙指令任務(wù)所用的總時間為：

(10)

1.2.2 堆垛機(jī)路徑能耗模型

堆垛機(jī)運(yùn)動過程中消耗的總能量包括其在水平和垂直方向上變速和勻速時所需的能量，以及克服工作軌道摩擦力所需的能量。

(11)

(12)

因此，堆垛機(jī)在水平方向上的能量消耗為：

(13)

在垂直方向上，第I類運(yùn)動和第II類運(yùn)動所需能量用于克服重力及摩擦力做功，因此，垂直上升階段單位質(zhì)量消耗的能量ez1為：

ez1=(1+μz)gSz

(14)

垂直下降階段單位質(zhì)量消耗的能量ez2為：

ez2=(1-μz)gSz

(15)

由堆垛機(jī)單雙指令流程可知，完成Q1次單指令任務(wù)及Q2次雙指令任務(wù)總能耗為：

(16)

1.2.3 目標(biāo)函數(shù)的建立

考慮堆垛機(jī)作業(yè)過程的環(huán)境友好性，可通過量化計(jì)算體系的綠色度來判斷作業(yè)的綠色性[12]。以時間和能耗作為堆垛機(jī)作業(yè)過程綠色度G的定量指標(biāo)，以最大化綠色度為目標(biāo)，建立堆垛機(jī)作業(yè)路徑優(yōu)化數(shù)學(xué)模型：

(17)

約束條件：

l≤Sx≤L

(18)

h≤Sz≤H

(19)

0

(20)

(21)

2g(H+L+W)]

(22)

約束條件中，式(18)和式(19)為堆垛機(jī)在水平和垂直方向上運(yùn)行距離的取值范圍；式(20)保證堆垛機(jī)每次搬運(yùn)貨物的質(zhì)量不超過其額定載荷；式(21)和式(22)為堆垛機(jī)完成一次搬運(yùn)任務(wù)時的時間和能耗的取值范圍。

2 基于免疫蟻群算法的模型求解

2.1 免疫蟻群算法數(shù)學(xué)描述

堆垛機(jī)路徑優(yōu)化已被證明是NP-hard問題，通常采用啟發(fā)式優(yōu)化算法求解[13]。蟻群算法具有并行計(jì)算、無中心控制等優(yōu)點(diǎn)，是求解復(fù)雜優(yōu)化問題的一種常用方法，但由于其在搜索初期缺乏有效的信息素，導(dǎo)致初期尋優(yōu)時間較長、求解效率低且較易落入局部最優(yōu)。免疫算法具有有效的全局尋優(yōu)能力，搜索過程具有隨機(jī)性、多樣性，可獲得很好的隨機(jī)解，因此可以考慮利用免疫算法獲得的隨機(jī)解為蟻群算法提供初始信息，以避免蟻群算法因初值選擇不當(dāng)而陷入局部最優(yōu)的問題。免疫蟻群算法流程如圖3所示。

圖3 免疫蟻群算法流程

2.1.1 編碼方式選擇

采用混合整數(shù)編碼方式，如圖4所示。假設(shè)有P個入庫貨位及R個出庫貨位，當(dāng)P=R時，機(jī)器人需進(jìn)行P次雙指令作業(yè)；當(dāng)P≠R時，機(jī)器人需進(jìn)行min(P,R)次雙指令作業(yè)及|P-R|次單指令作業(yè)。P個入庫貨位編碼為1～P，R個出庫貨位編碼為 (P+1)～(P+R)，每個編碼都與貨位一一對應(yīng)，各編碼組成一條路徑規(guī)劃方案，入庫和出庫貨位分別是第奇數(shù)個元素和第偶數(shù)個元素。

圖4 混合整數(shù)路徑編碼圖

2.1.2 親和度函數(shù)

針對堆垛機(jī)三維空間路徑優(yōu)化問題的特點(diǎn)，用每次迭代路徑總長度作為親和度評價算子。假設(shè)路徑有N個節(jié)點(diǎn)，基于歐式距離構(gòu)造親和度函數(shù)aff如下：

(23)

式中：dis(i,i+1)為路徑(i,i+1)(即從貨位i到貨位i+1)的距離。

2.1.3 自適應(yīng)變異算子

為避免無指導(dǎo)突變導(dǎo)致突變結(jié)果優(yōu)劣不定，從而使變異后的路徑均不包含某一關(guān)鍵的優(yōu)秀解決方案，因此本文提出采用基于親和度的自適應(yīng)變異率，根據(jù)迭代次數(shù)的不同，將每代中具有最大親和度的抗體考慮到變異算子中，自適應(yīng)調(diào)節(jié)變異算子，保證算法往更好的空間搜索。

foru=1∶Nmax

ifu==1

變異率=p

else

end

end

2.2 免疫蟻群算法步驟

步驟1參數(shù)初始化。迭代開始之前，設(shè)置螞蟻數(shù)量A、終止條件NC_max、信息和期望啟發(fā)因子α和β、每只螞蟻攜帶的信息素蒸發(fā)系數(shù)ρ(0<ρ<1)。

步驟2確定初始信息素。采用混合整數(shù)編碼，利用rand函數(shù)隨機(jī)生成一定數(shù)量的初始種群，根據(jù)親和度函數(shù)選擇執(zhí)行免疫操作的抗體，對其進(jìn)行克隆復(fù)制，克隆得到的抗體進(jìn)行自適應(yīng)變異處理，改變抗體的親和度；再次對變異結(jié)果進(jìn)行選擇以抑制具有低親和度的抗體并保留親和度高的抗體。

要使上述免疫算法求解結(jié)果有效，關(guān)鍵是要保證免疫算法的迭代次數(shù)。次數(shù)過大，蟻群算法得不到最優(yōu)值；次數(shù)過小，無法提供有用的信息素值。選取10代為一個單位，若迭代曲線連續(xù)20個單位的目標(biāo)值相同則停止迭代。免疫算法按照上述規(guī)則執(zhí)行完后，將迭代后的可行路徑對應(yīng)的親和度值作為蟻群算法部分初始信息素，因此，本文算法信息素的初值可以表示為：

τs=τc+τd

(24)

式中：τc表示信息素常數(shù)，相當(dāng)于τ0；τd表示免疫算法提供的信息素。

步驟3初始化蟻群。把A只螞蟻隨機(jī)分派至n個貨位上，并在禁忌表tau中記錄各自位置。

步驟4每只螞蟻從隨機(jī)分配的貨位出發(fā)，將走過的貨位加入到禁忌表中，初始化解空間。

步驟5螞蟻根據(jù)式(25)計(jì)算各可選貨位的轉(zhuǎn)移概率[14-15]，再根據(jù)輪盤賭法則選擇下一步轉(zhuǎn)移的貨位并繼續(xù)前進(jìn)。

(25)

式中：tovisitk=(s-tau(k))，其中s為所有貨位集合。

步驟6若k≥A，則表明每只螞蟻已經(jīng)遍歷完所有貨位，繼續(xù)進(jìn)行下一步，否則返回步驟4。

步驟7更新全局信息素。當(dāng)所有螞蟻對貨位進(jìn)行了一次遍歷之后，選出一只路徑最短的螞蟻，作為本次迭代的最優(yōu)螞蟻，并按下式更新信息素[15]：

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

(26)

(27)

(28)

式中：Q為常數(shù)，表示信息素強(qiáng)度；Lk為最優(yōu)螞蟻所走路徑的長度。

3 案例分析

3.1 案例數(shù)據(jù)與算法參數(shù)設(shè)置

以某中纖板切分企業(yè)自動化立體倉庫為工況背景，該倉庫設(shè)置有26排8層14列的固定貨架，貨物的質(zhì)量分別為100、120、150 kg。堆垛機(jī)的最大承載數(shù)量為一個托盤，表1為堆垛機(jī)實(shí)際運(yùn)行參數(shù)。為了更好地體現(xiàn)算法的優(yōu)越性能，分別選取堆垛機(jī)執(zhí)行30次和50次作業(yè)任務(wù)進(jìn)行分析計(jì)算，表2和表3所示為30次作業(yè)的貨位及其編碼。采用Matlab R2014b進(jìn)行仿真計(jì)算，運(yùn)算平臺配置為：處理器Inter?Celeron?CPU 1005M@2.5 GHz和內(nèi)存4 GB的個人計(jì)算機(jī)。免疫蟻群算法的參數(shù)設(shè)置為：A=16，Q=100，α=1，β=5，ρ=0.5。

表1 堆垛機(jī)實(shí)際運(yùn)行參數(shù)

表2 入庫作業(yè)序列

表3 出庫作業(yè)序列

為滿足用戶多樣化的需求偏好，確定ω1和ω2時采用組合加權(quán)法將主觀權(quán)重和客觀權(quán)重綜合考慮，使其更具實(shí)用性。先采用層次分析法確定主觀權(quán)重，再采用變異系數(shù)法獲得客觀權(quán)重，通過式(29)計(jì)算出最終的組合權(quán)重系數(shù)[16]：

ωj=λAj+(1-λ)Vj

(29)

式中：ωj為第j個指標(biāo)的組合權(quán)重系數(shù)；Aj和Vj分別為通過層次分析法和變異系數(shù)法確定的權(quán)重；λ表示偏好系數(shù)，λ∈(0,1)。

根據(jù)該企業(yè)對于時間、能耗的需求偏好度，采用層次分析法確定的權(quán)重A=[0.431,0.569]，采用變異系數(shù)法分析時間和能耗數(shù)據(jù)，確定權(quán)重V=[0.397,0.603]，本文λ取0.5，根據(jù)式(29)計(jì)算出組合權(quán)重系數(shù)ω=[0.414,0.586]。

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

為了驗(yàn)證算法的優(yōu)越性，根據(jù)目前對路徑優(yōu)化的研究方法，按照優(yōu)化目標(biāo)的不同將堆垛機(jī)路徑優(yōu)化問題分為以下3種：①)以作業(yè)時間最小為優(yōu)化目標(biāo)(記為PT)；②以能耗最小為優(yōu)化目標(biāo)(記為PE)；③以綠色度最大為優(yōu)化目標(biāo)(記為PW)。針對不同規(guī)模(30次和50次)的作業(yè)任務(wù)，分別采用傳統(tǒng)蟻群算法、免疫算法和免疫蟻群算法進(jìn)行路徑優(yōu)化，得到各算法的迭代收斂過程如圖5所示，各優(yōu)化目標(biāo)(總時間、總能耗及綠色度)的求解結(jié)果如表4和表5所示。

(a) 30次作業(yè)PT收斂曲線 (b) 30次作業(yè)PE收斂曲線 (c) 30次作業(yè)PW收斂曲線

(d) 50次作業(yè)PT收斂曲線 (e) 50次作業(yè)PE收斂曲線 (f) 50次作業(yè)PW收斂曲線

圖5 不同作業(yè)規(guī)模下3種算法的收斂曲線

表5 50次作業(yè)規(guī)模的仿真結(jié)果

由圖5可知，對于不同規(guī)模的作業(yè)任務(wù)，本文提出的免疫蟻群算法收斂速度最快，對時間和能耗的優(yōu)化值也有一定的改善，且算法的求解性能不會因?yàn)槿蝿?wù)規(guī)模的增加而受到影響，具有較好的魯棒性，而另外兩種算法由于沒有引入改進(jìn)策略導(dǎo)致易陷入局部最優(yōu)值。由此可見，免疫算法的解提供了有效的初始信息素，提高了蟻群算法的搜索能力，使得免疫蟻群算法可以有效解決堆垛機(jī)的路徑優(yōu)化問題。

由表4和表5可知，以PT為優(yōu)化目標(biāo)時，采用各算法得到的優(yōu)化方案作業(yè)時間較少，但能耗較大且綠色度很低，因?yàn)樵诼窂絻?yōu)化時，載重對能耗有一定的影響，單獨(dú)優(yōu)化時間會以增加能耗為代價達(dá)到時間最少的目標(biāo)；以PE為優(yōu)化目標(biāo)時，優(yōu)化方案的能耗最小，但作業(yè)時間較長且綠色度偏低，因?yàn)槟芎牡拇笮∪Q于運(yùn)輸距離和載重，在路徑優(yōu)化時，一味追求低能耗而忽視距離與載重的配合關(guān)系，會導(dǎo)致工作效率降低；以PW為優(yōu)化目標(biāo)時，可兼顧作業(yè)時間與能耗，優(yōu)化方案的綠色度最大，例如30次作業(yè)采用免疫蟻群算法所得優(yōu)化方案的總時間與以PT為目標(biāo)的優(yōu)化方案相比僅增加2.07%，但能耗降低了11.33%，而與以PE為目標(biāo)的優(yōu)化方案相比能耗僅增加4.45%，但作業(yè)時間降低了13.41%，其路徑優(yōu)化結(jié)果如圖6所示。綜合比較，PW優(yōu)化方案明顯優(yōu)于其余兩個優(yōu)化方案，因此，在路徑優(yōu)化時不能一味追求高效率或者低能耗，而應(yīng)該考慮機(jī)器人作業(yè)過程的綠色度，提高自動化立體倉庫的綜合運(yùn)行效益。

圖6 堆垛機(jī)30次作業(yè)的優(yōu)化路徑

4 結(jié)語

本文系統(tǒng)分析了AS/RS中堆垛機(jī)作業(yè)時間和能耗的構(gòu)成，在此基礎(chǔ)上，針對其三維路徑規(guī)劃問題，建立了以綠色度最大為目標(biāo)的優(yōu)化模型。針對該模型特點(diǎn)，采用免疫蟻群算法進(jìn)行尋優(yōu)求解，利用免疫算法結(jié)果提供蟻群算法的初始信息素，加快了算法收斂速度，同時避免了蟻群算法因初值選擇不當(dāng)而陷入局部最優(yōu)。通過具體案例，分別從時間、能耗及綠色度三方面分析驗(yàn)證了本文提出的路徑優(yōu)化方法的可行性和實(shí)用性，其能夠很好地平衡作業(yè)時間與能耗之間的關(guān)系。