考慮時間和能耗的立體倉庫三維空間路徑優化

夏緒輝，朱 強，王 蕾,2，曹建華

(1.武漢科技大學冶金裝備及其控制教育部重點實驗室，湖北 武漢，430081；2.武漢科技大學服務科學與工程研究中心，湖北 武漢，430065)

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

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

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

1 問題描述和數學模型

1.1 問題描述

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

圖1 自動化立體倉庫簡圖

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

對于單指令作業：在入庫環節，堆垛機裝載目標貨物后，從O點出發，沿著巷道運動到待入庫貨位所在的列和行，完成入庫任務后沿作業巷道回到O點；在出庫環節，堆垛機從O點出發，沿著作業巷道運動到待出庫貨位所在的列和行，裝載貨物后沿作業巷道返回至O點。

對于雙指令作業：堆垛機完成入庫環節后，空載運動到待出庫貨位所在的列和行，裝載貨物后沿作業巷道返回至O點，完成出庫任務。

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

圖2 兩類運動的位移-速度曲線

Fig.2Displacement-velocitycurvesoftwokindsofmovement

1.2 數學模型

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

1.2.1 堆垛機路徑時間模型

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

(1)

(2)

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

(3)

(4)

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

(5)

(6)

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

(7)

(8)

機器人從出入庫臺運行至目標貨位，總的行駛時間是水平和垂直行駛時間的最大值，即：

t=max(tx,tz)

(9)

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

(10)

1.2.2 堆垛機路徑能耗模型

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

(11)

(12)

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

(13)

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

ez1=(1+μz)gSz

(14)

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

ez2=(1-μz)gSz

(15)

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

(16)

1.2.3 目標函數的建立

考慮堆垛機作業過程的環境友好性，可通過量化計算體系的綠色度來判斷作業的綠色性[12]。以時間和能耗作為堆垛機作業過程綠色度G的定量指標，以最大化綠色度為目標，建立堆垛機作業路徑優化數學模型：

(17)

約束條件：

l≤Sx≤L

(18)

h≤Sz≤H

(19)

0

(20)

(21)

2g(H+L+W)]

(22)

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

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

2.1 免疫蟻群算法數學描述

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

圖3 免疫蟻群算法流程

2.1.1 編碼方式選擇

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

圖4 混合整數路徑編碼圖

2.1.2 親和度函數

針對堆垛機三維空間路徑優化問題的特點，用每次迭代路徑總長度作為親和度評價算子。假設路徑有N個節點，基于歐式距離構造親和度函數aff如下：

(23)

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

2.1.3 自適應變異算子

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

foru=1∶Nmax

ifu==1

變異率=p

else

end

end

2.2 免疫蟻群算法步驟

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

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

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

τs=τc+τd

(24)

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

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

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

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

(25)

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

步驟6若k≥A，則表明每只螞蟻已經遍歷完所有貨位，繼續進行下一步，否則返回步驟4。

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

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

(26)

(27)

(28)

式中：Q為常數，表示信息素強度；Lk為最優螞蟻所走路徑的長度。

3 案例分析

3.1 案例數據與算法參數設置

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

表1 堆垛機實際運行參數

表2 入庫作業序列

表3 出庫作業序列

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

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

(29)

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

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

3.2 仿真實驗結果與分析

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

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

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

圖5 不同作業規模下3種算法的收斂曲線

表5 50次作業規模的仿真結果

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

由表4和表5可知，以PT為優化目標時，采用各算法得到的優化方案作業時間較少，但能耗較大且綠色度很低，因為在路徑優化時，載重對能耗有一定的影響，單獨優化時間會以增加能耗為代價達到時間最少的目標；以PE為優化目標時，優化方案的能耗最小，但作業時間較長且綠色度偏低，因為能耗的大小取決于運輸距離和載重，在路徑優化時，一味追求低能耗而忽視距離與載重的配合關系，會導致工作效率降低；以PW為優化目標時，可兼顧作業時間與能耗，優化方案的綠色度最大，例如30次作業采用免疫蟻群算法所得優化方案的總時間與以PT為目標的優化方案相比僅增加2.07%，但能耗降低了11.33%，而與以PE為目標的優化方案相比能耗僅增加4.45%，但作業時間降低了13.41%，其路徑優化結果如圖6所示。綜合比較，PW優化方案明顯優于其余兩個優化方案，因此，在路徑優化時不能一味追求高效率或者低能耗，而應該考慮機器人作業過程的綠色度，提高自動化立體倉庫的綜合運行效益。

圖6 堆垛機30次作業的優化路徑

4 結語

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