基于兩階段狼群算法的自動(dòng)化立體倉(cāng)庫(kù)作業(yè)集成優(yōu)化

何 李 陶翼飛 羅俊斌 荀洪凱

1.昆明理工大學(xué)機(jī)電工程學(xué)院，昆明，650504 2.昆明昆船邏根機(jī)場(chǎng)系統(tǒng)有限公司，昆明，650236

0 引言

自動(dòng)化立體倉(cāng)庫(kù)(automated storage/retrieval systems，AS/RS)具有空間利用率高、存儲(chǔ)容量大、人工成本低等優(yōu)點(diǎn)。影響AS/RS工作效率的關(guān)鍵點(diǎn)有貨物的貨位分配和出入庫(kù)任務(wù)的作業(yè)調(diào)度。合適的貨位分配和作業(yè)調(diào)度可以充分利用存儲(chǔ)空間，縮短堆垛機(jī)作業(yè)時(shí)間和運(yùn)行距離，從而降低成本。

針對(duì)AS/RS的貨位分配優(yōu)化問(wèn)題，眾多學(xué)者根據(jù)出入庫(kù)頻率[1]、貨架穩(wěn)定性[2]、貨物相關(guān)性[3]、空間利用率[4]等優(yōu)化目標(biāo)構(gòu)建多目標(biāo)優(yōu)化模型，提出許多改進(jìn)式/混合式優(yōu)化算法。張貴軍等[5]提出一種精英多策略差分進(jìn)化算法，該算法針對(duì)基本差分進(jìn)化算法的變異操作，根據(jù)多個(gè)精英個(gè)體的信息選擇變異策略指導(dǎo)變異，提高了算法的可靠性和效率；JIAO等[6]將多種群遺傳算法用于歸一化后的目標(biāo)函數(shù)，結(jié)果表明該算法所得的各個(gè)目標(biāo)函數(shù)值均優(yōu)于簡(jiǎn)單加權(quán)遺傳算法；蔡安江等[7]建立了適用于兩端式同軌雙車(chē)立體倉(cāng)庫(kù)的多目標(biāo)貨位優(yōu)化模型，并提出了一種集成多目標(biāo)生物地理優(yōu)化算法用于求解。針對(duì)作業(yè)調(diào)度，研究人員將堆垛機(jī)的路徑優(yōu)化問(wèn)題轉(zhuǎn)化為類(lèi)似的旅行商問(wèn)題[8]，并使用各種啟發(fā)式算法求解。AMIRHOSSEIN等[9]針對(duì)多載具AS/RS建立了一種0-1模糊數(shù)學(xué)規(guī)劃模型，并使用遺傳算法求解；蔡安江等[10]針對(duì)兩端式自動(dòng)化立體倉(cāng)庫(kù)，建立了考慮貨物出入庫(kù)臺(tái)分配的堆垛機(jī)調(diào)度模型，并運(yùn)用漩渦搜索算法求取最優(yōu)解。

AS/RS在實(shí)際運(yùn)行中，不同的貨位分配與作業(yè)調(diào)度組合會(huì)導(dǎo)致不同的運(yùn)行結(jié)果，單獨(dú)對(duì)某個(gè)部分進(jìn)行優(yōu)化只能起到部分優(yōu)化的作用。為更好地提高優(yōu)化效果，縮短AS/RS的運(yùn)行時(shí)間，開(kāi)展針對(duì)貨位分配與作業(yè)調(diào)度的集成優(yōu)化研究十分必要。CHEN等[11]以單載具AS/RS最短作業(yè)時(shí)間為優(yōu)化目標(biāo)，先后利用有向連接圖優(yōu)化儲(chǔ)位分配，利用禁忌搜索算法優(yōu)化堆垛機(jī)作業(yè)路徑，但這在本質(zhì)上仍是分開(kāi)優(yōu)化。楊朋等[12]以多載具AS/RS一次指令周期耗時(shí)最短為研究目標(biāo)，設(shè)計(jì)了兩階段禁忌搜索算法用于求解，貨位分配與作業(yè)調(diào)度兩階段能以反饋的方式相互影響，但其研究只針對(duì)多載具堆垛機(jī)一次行程所消耗時(shí)間，并未考慮對(duì)后續(xù)任務(wù)的影響。楊瑋等[13]在此基礎(chǔ)上，按照先到先服務(wù)規(guī)則對(duì)任務(wù)進(jìn)行指令分組，提出一種雙層遺傳算法同時(shí)優(yōu)化指令分組后的貨位分配和子行程作業(yè)調(diào)度。湯洪濤等[14]在優(yōu)化單載具AS/RS揀選作業(yè)時(shí)間時(shí)考慮空閑時(shí)間移庫(kù)的操作，提出一種基于K-中心點(diǎn)聚類(lèi)的粒子群優(yōu)化算法。移庫(kù)不僅能夠縮短作業(yè)時(shí)間，還能將待出庫(kù)貨位直接空出作為備選入庫(kù)貨位，但這只適用于特定的立體倉(cāng)庫(kù)。

綜上可知，盡管已有學(xué)者對(duì)AS/RS集成優(yōu)化進(jìn)行了研究，但缺少對(duì)單載具AS/RS通用作業(yè)集成優(yōu)化模型的研究，因此，本文針對(duì)單載具AS/RS的一系列出入庫(kù)任務(wù)，同時(shí)對(duì)入庫(kù)任務(wù)的貨位分配和出庫(kù)任務(wù)的作業(yè)調(diào)度進(jìn)行決策、建立集成優(yōu)化模型，采用貨架預(yù)分區(qū)策略使貨物分區(qū)分類(lèi)存儲(chǔ)，縮短算法的運(yùn)算時(shí)間，并提出一種兩階段狼群算法用于模型求解。

1 問(wèn)題描述

自動(dòng)化立體倉(cāng)庫(kù)的作業(yè)集成優(yōu)化是指同時(shí)對(duì)貨位分配與作業(yè)調(diào)度進(jìn)行優(yōu)化，達(dá)到作業(yè)時(shí)間最短、作業(yè)效率最高的效果。本文的研究對(duì)象為單載具堆垛機(jī)自動(dòng)化立體倉(cāng)庫(kù)，該立體倉(cāng)庫(kù)會(huì)根據(jù)接收的出入庫(kù)任務(wù)形成單指令(single command，SC)作業(yè)和雙指令(dual command，DC)作業(yè)兩種運(yùn)行方式。對(duì)于一系列入庫(kù)任務(wù)和出庫(kù)任務(wù)，不同的安排會(huì)導(dǎo)致不同的作業(yè)效率。因此，在貨架現(xiàn)有貨位狀態(tài)下，本文針對(duì)入庫(kù)任務(wù)的貨位選擇問(wèn)題，以及出庫(kù)任務(wù)的出庫(kù)順序問(wèn)題進(jìn)行集成優(yōu)化，使得在整個(gè)指令序列下的堆垛機(jī)作業(yè)時(shí)間最短。

1.1 基本假設(shè)

為便于研究，針對(duì)問(wèn)題作如下假設(shè)：研究對(duì)象為單巷道、單載具堆垛機(jī)立體倉(cāng)庫(kù)；出入庫(kù)任務(wù)針對(duì)巷道左右的兩排貨架；所有貨位尺寸相同且只存放一個(gè)貨物；巷道出入庫(kù)臺(tái)在同一側(cè)；堆垛機(jī)初始位置在巷道出入庫(kù)臺(tái)；堆垛機(jī)運(yùn)行加速度恒定；堆垛機(jī)貨叉裝/卸貨時(shí)間恒定；入庫(kù)任務(wù)采用先到先服務(wù)規(guī)則，出庫(kù)任務(wù)順序可調(diào)。

1.2 貨架預(yù)分區(qū)

以往對(duì)AS/RS貨位分配的研究通常考慮貨物出入庫(kù)頻率、貨物質(zhì)量等影響因素，雖能對(duì)AS/RS作業(yè)效率和貨架穩(wěn)定性進(jìn)行一定的優(yōu)化，但研究大多基于貨架初始狀態(tài)全為空的靜態(tài)條件，實(shí)用性不高。對(duì)入庫(kù)任務(wù)進(jìn)行動(dòng)態(tài)貨位分配具有較高的實(shí)用性，但當(dāng)貨架容量較大時(shí)，較多的備選貨位會(huì)使算法計(jì)算時(shí)間大大延長(zhǎng)。因此本文在進(jìn)行動(dòng)態(tài)貨位分配之前，考慮貨物的出入庫(kù)頻率及貨物質(zhì)量，使用多色集合理論對(duì)貨架進(jìn)行分區(qū)[15]。對(duì)貨架上的貨物進(jìn)行分區(qū)分類(lèi)存儲(chǔ)，不僅使貨物的存放有條不紊，便于管理，而且能減少入庫(kù)任務(wù)備選貨位的選擇項(xiàng)，縮小可行解空間，提高運(yùn)算效率。

傳統(tǒng)集合論用于各種系統(tǒng)仿真，但在對(duì)生產(chǎn)系統(tǒng)、工藝過(guò)程等復(fù)雜離散事件系統(tǒng)進(jìn)行仿真時(shí)，不能描述集合及其元素的性質(zhì)，導(dǎo)致其應(yīng)用受限。多色集合理論[16]應(yīng)用矩陣論、模糊數(shù)學(xué)等對(duì)傳統(tǒng)集合論進(jìn)行改進(jìn)，建立了標(biāo)準(zhǔn)的數(shù)學(xué)模型，可仿真不同對(duì)象，使得仿真系統(tǒng)更具柔性，且其基本成分是布爾矩陣，易于計(jì)算機(jī)編程實(shí)現(xiàn)。

(1)

(2)

針對(duì)本文所研究的單巷道立體倉(cāng)庫(kù)，以10列10層的單側(cè)貨架為例進(jìn)行貨架分區(qū)說(shuō)明。該立體倉(cāng)庫(kù)出入庫(kù)的貨物共4類(lèi)，每類(lèi)貨物的出入庫(kù)頻率(貨物出入庫(kù)任務(wù)數(shù)量占總?cè)蝿?wù)數(shù)量的比例)和質(zhì)量如表1所示，按貨物類(lèi)別將貨架分為4個(gè)區(qū)域。為建立立體倉(cāng)庫(kù)貨位分區(qū)的數(shù)學(xué)模型，將各貨位視為元素ai，則貨位編號(hào)可視為多色集合的統(tǒng)一顏色；將貨位特征(層數(shù)、列數(shù))、貨物的出入庫(kù)頻率和貨物的質(zhì)量設(shè)為設(shè)計(jì)元素，組成布爾圍道矩陣，見(jiàn)表2。

表1 貨物特征表

表2 貨架分區(qū)圍道布爾矩陣

集合A由貨架中100個(gè)貨位組成，即A={a1，…，ai，…，a100}，其中，i=10(y-1)+x，x、y分別對(duì)應(yīng)貨位所在的列數(shù)和層數(shù)。F1～F12組成設(shè)計(jì)元素F(A)，表示貨位ai的性質(zhì)，其中，F(xiàn)1表示貨物出入庫(kù)頻率大于30%，F(xiàn)2表示貨物出入庫(kù)頻率位于10%～30%，F(xiàn)3表示貨物出入庫(kù)頻率位于10%以下，F(xiàn)4表示貨物出入庫(kù)質(zhì)量大于600 kg，F(xiàn)5表示質(zhì)量為200～600 kg，F(xiàn)6表示質(zhì)量小于200 kg，F(xiàn)7表示位于貨架1～4層，F(xiàn)8表示位于貨架5～8層，F(xiàn)9表示位于貨架9～10層，F(xiàn)10表示位于貨架1～4列，F(xiàn)11表示位于貨架5～8列，F(xiàn)12表示位于貨架9～10列。F(ai)表示元素ai的個(gè)人著色，例如一層一列的貨位a1，F(xiàn)(a1)=(F1，F(xiàn)4，F(xiàn)7，F(xiàn)10)，用布爾矢量表示為F(a1)=(1，0，0，1，0，0，1，0，0，1，0，0)。對(duì)于每個(gè)元素ai，將對(duì)應(yīng)的布爾矢量中的0和1分別用空格和“●”代替填入表2所示的圍道布爾矩陣中，則該表從整體上表現(xiàn)了貨位與貨位特征、貨物出入庫(kù)頻率和貨物質(zhì)量之間的關(guān)系。根據(jù)表2所示的布爾圍道矩陣，將上述單側(cè)10行10列貨架分為區(qū)域Ⅰ、Ⅱ、Ⅲ、Ⅳ，分別存放A、B、C、D這4類(lèi)貨物。如圖1所示，對(duì)單巷道立體倉(cāng)庫(kù)左右兩排貨架進(jìn)行區(qū)域劃分，以此作為入庫(kù)任務(wù)貨位分配的前提。

圖1 貨架分區(qū)示意圖

2 作業(yè)集成優(yōu)化模型構(gòu)建

本文的研究對(duì)象為單巷道立體倉(cāng)庫(kù)，用(x，y，z)表示貨位坐標(biāo)，其中，x為貨位列數(shù)，y為貨位層數(shù)，z為貨位排數(shù)，由于研究的是單巷道，所以z為1或2。堆垛機(jī)在巷道內(nèi)進(jìn)行水平和垂直的運(yùn)動(dòng)即可完成左右兩排貨架的出入庫(kù)任務(wù)，因此在計(jì)算堆垛機(jī)運(yùn)行時(shí)間時(shí)可只考慮坐標(biāo)(x，y)，取堆垛機(jī)出入庫(kù)臺(tái)I坐標(biāo)為(0，1)。

在考慮堆垛機(jī)加速度的情況下，堆垛機(jī)從點(diǎn)(xa，ya)運(yùn)行到點(diǎn)(xb，yb)的運(yùn)行時(shí)間Ta，b=max(tc，tr)，其中，tc為水平方向運(yùn)動(dòng)時(shí)間，tr為垂直方向運(yùn)動(dòng)時(shí)間，它們的求解公式分別為

(3)

(4)

其中，l為單個(gè)貨位寬度；h為單個(gè)貨位高度；vc為堆垛機(jī)水平方向最大速度；ac為堆垛機(jī)水平加速度；vr為堆垛機(jī)垂直方向最大速度；ar為堆垛機(jī)垂直加速度。由此，可以得出堆垛機(jī)完成第i個(gè)雙指令作業(yè)任務(wù)的時(shí)間：

Yi，qTq，I)+4tsc

(5)

堆垛機(jī)完成第i個(gè)單指令作業(yè)任務(wù)的時(shí)間：

(6)

式中，SL為備選入庫(kù)貨位集合，由空貨位與取貨貨位組成；RL為取貨貨位集合；m為入庫(kù)任務(wù)數(shù)量；n為出庫(kù)任務(wù)數(shù)量；Xi，p為0-1變量，第i個(gè)入庫(kù)指令選擇備選貨位p為目的地址，Xi，p取1，否則取0；Yi，q為0-1變量，第i個(gè)出庫(kù)指令選擇貨位q為源地址，Yi，q取1，否則取0；TI，p為堆垛機(jī)從巷道出入庫(kù)臺(tái)I到入庫(kù)貨位p的時(shí)間；Tq，I為堆垛機(jī)從出庫(kù)貨位q到巷道出入庫(kù)臺(tái)I的時(shí)間；Tp，q為堆垛機(jī)從入庫(kù)貨位p到出庫(kù)貨位q的時(shí)間；tsc為堆垛機(jī)貨叉裝/卸一次貨物所用時(shí)間。

對(duì)于一批出入庫(kù)任務(wù)，取P1=max(m，n)，P2=min(m，n)，則這批出入庫(kù)任務(wù)可拆解為P2個(gè)雙指令作業(yè)和P1-P2個(gè)單指令作業(yè)。由此，本文建立的數(shù)學(xué)模型如下：

(7)

(8)

(9)

(10)

式(8)確保分配一個(gè)空貨位給入庫(kù)的貨物，式(9)確保每個(gè)空貨位只能存儲(chǔ)一個(gè)貨物，式(10)確保每個(gè)取貨貨位都有出庫(kù)任務(wù)。

3 算法描述

狼群算法(wolf pack algorithm，WPA)[17]模擬狼群分工協(xié)作的狩獵過(guò)程，效仿游走、召喚和圍攻三種智能行為，以“勝者為王”“強(qiáng)者生存”兩種生成機(jī)制對(duì)狼群進(jìn)行更新，能以較大概率搜索到問(wèn)題的更優(yōu)解，具有較好的尋優(yōu)性能。為實(shí)現(xiàn)針對(duì)貨位分配和作業(yè)調(diào)度問(wèn)題的集成優(yōu)化，本文提出基于集成分層優(yōu)化思想的兩階段狼群算法，在不同優(yōu)化層之間對(duì)所得的最優(yōu)解進(jìn)行及時(shí)反饋，從而獲取集成優(yōu)化問(wèn)題的最優(yōu)解。

算法的基本思想是：首先根據(jù)出入庫(kù)訂單和初始貨位狀態(tài)分配初始貨位，安排1個(gè)符合邏輯的進(jìn)出庫(kù)任務(wù)；算法第一層是作業(yè)調(diào)度層，通過(guò)狼群算法對(duì)出庫(kù)任務(wù)進(jìn)行合理的安排，生成最優(yōu)作業(yè)調(diào)度；將第一層所得的最優(yōu)解作為約束條件并使用狼群算法來(lái)優(yōu)化貨位分配，完成一個(gè)循環(huán)；然后將上一循環(huán)的貨位分配結(jié)果反饋到作業(yè)調(diào)度層，構(gòu)成閉環(huán)，開(kāi)始下一循環(huán)。算法流程如圖2所示。由于編碼方式不同，因此下文將從作業(yè)調(diào)度、貨位分配兩個(gè)階段，詳細(xì)描述算法的關(guān)鍵步驟。

圖2 兩階段狼群算法流程

3.1 作業(yè)調(diào)度階段

此階段采用整數(shù)編碼，編碼長(zhǎng)度等于出庫(kù)任務(wù)個(gè)數(shù)n。將1、2、…、n隨機(jī)排列產(chǎn)生初始狼群，根據(jù)編碼的排序安排出庫(kù)順序，1個(gè)編碼個(gè)體代表1個(gè)可行的作業(yè)調(diào)度方案。根據(jù)式(7)計(jì)算初始狼群個(gè)體的適應(yīng)度，選擇適應(yīng)度最小的個(gè)體作為頭狼，記其適應(yīng)度為Ylead，將除頭狼之外的Ns個(gè)適應(yīng)度最小的個(gè)體作為探狼，將剩余個(gè)體作為猛狼。

3.1.2游走

探狼在解空間中搜索獵物。計(jì)算探狼i的目標(biāo)適應(yīng)度Yi，若Yi

3.1.3召喚

頭狼召喚所有猛狼向頭狼所在位置迅速靠攏，猛狼快速向頭狼位置奔襲，即在頭狼的編碼中隨機(jī)選取長(zhǎng)度為Sb的一段，來(lái)替換猛狼編碼中與該編碼段的起始或末尾編碼相同且長(zhǎng)度也為Sb的編碼段，并更新猛狼編碼。如圖3所示，假設(shè)Sb=3，隨機(jī)選取的頭狼編碼段為[4，5，6]，該編碼段的起始編碼與猛狼奔襲前的第5個(gè)編碼相同，因此在執(zhí)行召喚操作時(shí)需將猛狼編碼中的[4，1，2]替換為[4，5，6]，并根據(jù)位置映射關(guān)系5→1、6→2對(duì)其他沖突位置的編碼進(jìn)行調(diào)整。根據(jù)奔襲規(guī)則，猛狼編碼中“1”和“2”分別被替換成“5”和“6”。為避免重復(fù)，根據(jù)映射關(guān)系，猛狼編碼中原來(lái)的“5”和“6”被映射替換成“1”和“2”。這種調(diào)整方式保留了猛狼大部分的編碼，將猛狼的部分編碼段替換為頭狼對(duì)應(yīng)位置的編碼段，體現(xiàn)了頭狼對(duì)個(gè)體的指導(dǎo)作用。奔襲途中，若Yi

圖3 猛狼奔襲過(guò)程

3.1.4圍攻

奔襲之后的狼群距離頭狼較近，因此，可將頭狼位置視為獵物所在位置，頭狼指揮探狼和猛狼對(duì)獵物進(jìn)行圍攻，即視探狼和猛狼為圍攻狼，保留圍攻狼編碼中與頭狼相同編碼位的相同編碼，對(duì)圍攻狼編碼中與頭狼相同編碼位的不同編碼進(jìn)行隨機(jī)變換，使之符合編碼要求。

回到家里，紫云拿出那個(gè)黑色公文包，里面有一張調(diào)令文書(shū)。所有的手續(xù)都辦好了，新的工作單位是華夏出版社。她把房子賣(mài)了，帶著兒子，到上海去了。

3.2 貨位分配階段

3.2.1編碼和初始化種群

貨位分配的目的是根據(jù)貨架當(dāng)前狀態(tài)為入庫(kù)貨物選擇合適的貨位，提高作業(yè)效率。本文研究的是動(dòng)態(tài)貨位分配，貨物根據(jù)分區(qū)約束在相應(yīng)的區(qū)域隨機(jī)選擇合適的貨位。為避免將一些較好的貨位閑置，影響作業(yè)的效率，因此將出庫(kù)貨位重新設(shè)為入庫(kù)任務(wù)的存儲(chǔ)貨位。貨位分配階段的編碼由兩層構(gòu)成，上層為備選貨位層，由當(dāng)前貨架空貨位號(hào)和取貨貨位號(hào)組成。貨位編號(hào)采用自然數(shù)編碼，水平方向按照從出/入庫(kù)臺(tái)一側(cè)至立庫(kù)另一側(cè)的順序依次遞增，垂直方向按照貨架層級(jí)由低到高的順序依次遞增。下層采用0-1編碼，決定對(duì)應(yīng)的上層貨位能否作為入庫(kù)貨位。如圖4所示，以10層10列貨架為例，因本文研究對(duì)象為單巷道左右兩排貨架，故上層編碼的選擇范圍是1～200。根據(jù)貨架分區(qū)情況對(duì)上層進(jìn)行劃分，分區(qū)編碼按從小到大順序排列，滿足貨物依次從低層貨位向高層貨位存放的原則，保證貨架的穩(wěn)定性。下層編碼為“1”的貨位為被選中的存貨貨位。如圖4所示，下層編碼為“1”的位置對(duì)應(yīng)上層貨位即選取的入庫(kù)貨位，如上層編碼為2、134、16、26等的貨位。根據(jù)入庫(kù)任務(wù)，在編碼第二層相應(yīng)區(qū)域內(nèi)隨機(jī)分配“0”“1”(共計(jì)m個(gè)“1”)，產(chǎn)生初始狼群，并計(jì)算適應(yīng)度，選擇頭狼、探狼和猛狼。后續(xù)的編碼變換中，上層的編碼不會(huì)改變，下文所述編碼操作只針對(duì)下層編碼。由于貨位分配階段的編碼方式有別于3.1節(jié)的作業(yè)調(diào)度階段的編碼方式，因此，貨位分配階段的游走、召喚和圍攻操作也有別于作業(yè)調(diào)度階段，下文將進(jìn)行詳細(xì)描述。

圖4 貨位分配編碼示例

3.2.2游走

計(jì)算探狼i的目標(biāo)適應(yīng)度Yi，若Yi

3.2.3召喚

頭狼召喚所有猛狼向頭狼迅速靠攏，猛狼快速向頭狼位置奔襲。奔襲途中，若Yi

3.2.4圍攻

奔襲之后的狼群距離頭狼較近，因此，可將頭狼位置視為獵物所在位置，指揮探狼和猛狼對(duì)獵物進(jìn)行圍攻。若頭狼與圍攻狼相同編碼位的編碼均為“1”，則保留圍攻狼當(dāng)前編碼位的編碼；否則，將相同編碼位的編碼“1”隨機(jī)變換至其他編碼位上，并使之符合編碼要求。

3.3 方案可行性判斷

本文研究的動(dòng)態(tài)貨位分配問(wèn)題將貨物出庫(kù)后閑置貨位重新考慮為入庫(kù)任務(wù)的存儲(chǔ)貨位，所以一個(gè)符合邏輯的進(jìn)出庫(kù)指令安排需保證同一貨位對(duì)應(yīng)的出庫(kù)任務(wù)在入庫(kù)任務(wù)執(zhí)行之前完成。在算法運(yùn)行過(guò)程中，并非所有編碼個(gè)體都能滿足上述要求，因此每個(gè)編碼個(gè)體在進(jìn)行適應(yīng)度計(jì)算之前都需進(jìn)行可行性判斷。把判斷之后可行的編碼個(gè)體按照式(7)計(jì)算適應(yīng)度，將不可行的編碼個(gè)體對(duì)應(yīng)的適應(yīng)度設(shè)置為相對(duì)較大值，以避免不可行解的出現(xiàn)，導(dǎo)致計(jì)算錯(cuò)誤。

3.4 算法終止條件

算法經(jīng)過(guò)一次作業(yè)調(diào)度階段和一次貨位分配階段后完成一次完整迭代。判斷算法當(dāng)前迭代次數(shù)是否大于設(shè)置的最大迭代次數(shù)Gmax：若是，則算法終止；否則，將當(dāng)前最優(yōu)解個(gè)體進(jìn)行保留，并反饋給作業(yè)調(diào)度層開(kāi)始新一次循環(huán)。

4 實(shí)驗(yàn)與分析

4.1 仿真實(shí)驗(yàn)設(shè)計(jì)

以10列10層、單巷道左右兩排貨架為研究對(duì)象，每側(cè)貨架都被分為4個(gè)區(qū)域。相鄰貨位水平方向間距l(xiāng)=2.5 m，垂直方向間距h=1.2 m，堆垛機(jī)水平方向的最大速度vc=1.0 m/s，加速度ac=0.4 m/s2，垂直方向的最大速度vr=0.5 m/s，加速度ar=0.5 m/s2，堆垛機(jī)貨叉裝/卸一次貨物所用時(shí)間tsc=5 s。

算例采取隨機(jī)生成的方式：隨機(jī)在單巷道左右兩排貨架上各生成60個(gè)貨物(已在庫(kù)中貨物)。AS/RS中，單載具堆垛機(jī)全程采取雙指令周期作業(yè)，即令出庫(kù)指令數(shù)量n等于入庫(kù)指令數(shù)量m。選擇20、40、60三種入庫(kù)規(guī)模，四類(lèi)貨物A～D的入庫(kù)數(shù)量相同，并從在庫(kù)貨物中隨機(jī)選擇同等數(shù)量的貨物出庫(kù)。仿真實(shí)驗(yàn)中，各算例運(yùn)算10次，結(jié)果取平均值。

本文仿真優(yōu)化模型的建立均在Plant Simulation 15.0軟件中完成，通過(guò)HBW(high bay warehouse)模塊可實(shí)現(xiàn)一組出入庫(kù)訂單的完整運(yùn)行，同時(shí)也能驗(yàn)證當(dāng)前作業(yè)安排是否符合實(shí)際工況，采用Simtalk語(yǔ)言編寫(xiě)優(yōu)化算法，仿真實(shí)驗(yàn)在Inter i5-9300H CPU主服務(wù)器構(gòu)建的分布式仿真優(yōu)化環(huán)境上運(yùn)行。

為證明本文算法的適用性和優(yōu)越性，除將兩階段狼群算法用于AS/RS集成作業(yè)，還分別應(yīng)用狼群算法、禁忌搜索(tabu search，TS)[12]算法、遺傳算法(genetic algorithm，GA)[13]、粒子群優(yōu)化(particle swarm optimization，PSO)[14]算法對(duì)所述問(wèn)題進(jìn)行優(yōu)化。為驗(yàn)證集成優(yōu)化的優(yōu)越性，對(duì)貨位分配和作業(yè)調(diào)度的分開(kāi)優(yōu)化與集成優(yōu)化進(jìn)行仿真比較。各算法的最大迭代次數(shù)Gmax都取500。在貨位分配階段和作業(yè)調(diào)度階段結(jié)束時(shí)分別記錄結(jié)果，故每次運(yùn)算所得最終結(jié)果記錄數(shù)G為2Gmax。

4.2 算法參數(shù)選擇

算法參數(shù)的選擇會(huì)對(duì)優(yōu)化問(wèn)題的結(jié)果產(chǎn)生一定的影響。為在相同條件下進(jìn)行不同算法的對(duì)比仿真實(shí)驗(yàn)，設(shè)計(jì)正交試驗(yàn)獲取不同算法的參數(shù)。下面以狼群算法為例進(jìn)行說(shuō)明：對(duì)種群大小Npop、判斷距離dnear、探狼召喚階段步長(zhǎng)Sb、游走最大次數(shù)Tmax設(shè)計(jì)L9(34)正交試驗(yàn)(每個(gè)因素有3個(gè)水平)，共計(jì)9個(gè)試驗(yàn)組合。通過(guò)查閱大量狼群算法相關(guān)文獻(xiàn)，選擇常用參數(shù)值作為本文正交試驗(yàn)的參數(shù)值。文獻(xiàn)[17-18]中的種群規(guī)模為50和100，因此選擇種群規(guī)模為50、80、100；文獻(xiàn)[18-19]中的游走最大次數(shù)為10和15，因此選擇游走最大次數(shù)5、10、15；判斷距離dnear、探狼召喚階段步長(zhǎng)Sb都與編碼長(zhǎng)度n相關(guān)，根據(jù)現(xiàn)有文獻(xiàn)，選定dnear為2n/5、n/2、3n/5，Sb為n/5、n/4、3n/10。確定狼群算法參數(shù)的正交試驗(yàn)選擇訂單規(guī)模n=20，探狼數(shù)量Ns=Npop/2。每種實(shí)驗(yàn)組合單獨(dú)運(yùn)行10次并取平均值，所得結(jié)果如表3所示。

表3 正交試驗(yàn)結(jié)果

由實(shí)驗(yàn)結(jié)果可知，組合8的結(jié)果最優(yōu)，故后續(xù)實(shí)驗(yàn)中，不同訂單規(guī)模n的狼群算法均采用以下參數(shù)：狼群大小Npop=100，召喚階段dnear=n/2，步長(zhǎng)Sb=n/4，探狼最大游走次數(shù)Tmax=10。

同理，對(duì)TS算法、GA、PSO算法的參數(shù)采取相同的方式設(shè)計(jì)正交試驗(yàn)，由于篇幅有限，僅在表4中列出以上算法最終確定的關(guān)鍵參數(shù)。

表4 對(duì)比算法參數(shù)選擇

4.3 結(jié)果分析

表5給出了3種訂單規(guī)模下，雙指令周期作業(yè)使用兩階段狼群算法集成優(yōu)化所得結(jié)果。從實(shí)驗(yàn)結(jié)果看，與初代最優(yōu)解相比，優(yōu)化后的作業(yè)時(shí)間都顯著縮短，不同訂單規(guī)模下的作業(yè)時(shí)間縮短約15%；隨著訂單規(guī)模的增大，算法計(jì)算時(shí)間也稍微延長(zhǎng)，但變化幅度不大，不影響AS/RS實(shí)際應(yīng)用場(chǎng)景下的決策。

表5 兩階段狼群算法優(yōu)化結(jié)果

雙指令周期作業(yè)使用狼群算法進(jìn)行集成優(yōu)化和分開(kāi)優(yōu)化的過(guò)程如圖5所示。從實(shí)驗(yàn)結(jié)果來(lái)看，不同訂單規(guī)模下，集成優(yōu)化下的狼群算法基本能在750次內(nèi)搜索到對(duì)應(yīng)問(wèn)題的最優(yōu)解，且算法的求解性能不受訂單規(guī)模改變的影響，具有良好的魯棒性；在相同訂單規(guī)模情況下，狼群算法集成優(yōu)化所得結(jié)果更好。

(a)20對(duì)指令

圖6所示為對(duì)比算法求解的尋優(yōu)過(guò)程。3個(gè)訂單規(guī)模下，使用各算法進(jìn)行分開(kāi)和集成優(yōu)化后的實(shí)驗(yàn)結(jié)果如表6所示。由表6可知：相同算法下，集成優(yōu)化與分開(kāi)優(yōu)化的計(jì)算時(shí)間接近，但集成優(yōu)化較分開(kāi)優(yōu)化有明顯提高，且改進(jìn)量隨訂單規(guī)模的增大而增大。這是因?yàn)樵谑褂猛N算法時(shí)，分開(kāi)優(yōu)化和集成優(yōu)化的算法復(fù)雜度是相近的，而集成優(yōu)化不僅能將作業(yè)調(diào)度層生成的出庫(kù)指令順序傳遞到貨位分配層，貨位分配層也能將所得到的入庫(kù)貨物存儲(chǔ)位置反饋給作業(yè)調(diào)度層，從而形成一個(gè)閉環(huán)。此外，在相同的情況下，WPA所得結(jié)果比TS算法、GA、PSO算法所得結(jié)果更優(yōu)。算法運(yùn)行時(shí)間上，WPA所用時(shí)間略長(zhǎng)于TS算法、GA、PSO算法，其原因在于算法中狼群的游走、召喚、圍攻操作雖然具有更好的尋優(yōu)能力，但增加了算法的復(fù)雜度。盡管如此，從算法最終尋優(yōu)效果的角度進(jìn)行分析，WPA運(yùn)行所增加的時(shí)間較短，即WPA能以增加較短的運(yùn)算時(shí)間為代價(jià)換來(lái)更好的尋優(yōu)效果。以上實(shí)驗(yàn)結(jié)果分析證明了兩階段狼群算法在求解AS/RS作業(yè)集成優(yōu)化問(wèn)題上的有效性和實(shí)用性。

(a)TS算法 (b)GA算法 (c)PSO算法

表6 不同優(yōu)化方法的結(jié)果比較

5 結(jié)語(yǔ)

本文研究的AS/RS作業(yè)集成優(yōu)化問(wèn)題立足于自動(dòng)化立體倉(cāng)庫(kù)運(yùn)行的實(shí)時(shí)性，提出的求解算法能對(duì)同時(shí)存在的出入庫(kù)任務(wù)進(jìn)行合理安排。本文提出兩階段狼群算法通過(guò)對(duì)基本狼群算法中的游走、召喚和圍攻機(jī)制的重新設(shè)計(jì)，實(shí)現(xiàn)了算法在較優(yōu)解附近的精細(xì)搜索，具備的隨機(jī)性搜索能力避免了在尋優(yōu)過(guò)程中陷入局部最優(yōu)。將貨位分配和作業(yè)調(diào)度進(jìn)行集成優(yōu)化，求解過(guò)程體現(xiàn)了兩優(yōu)化問(wèn)題之間的關(guān)聯(lián)和反饋。實(shí)驗(yàn)結(jié)果表明，兩階段狼群算法在不同的訂單規(guī)模下均能得出滿意解，且求解性能不受訂單規(guī)模變化的影響，體現(xiàn)了算法的魯棒性。對(duì)比實(shí)驗(yàn)表明：兩階段狼群算法所得結(jié)果相對(duì)更優(yōu)，與初代最優(yōu)解相比，作業(yè)時(shí)間縮短約15%。