何 李 陶翼飛 羅俊斌 荀洪凱

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

0 引言

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

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

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

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

1 問題描述

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

1.1 基本假設(shè)

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

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

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

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

(1)

(2)

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

表1 貨物特征表

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

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

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

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

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

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

(3)

(4)

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

Yi，qTq，I)+4tsc

(5)

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

(6)

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

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

(7)

(8)

(9)

(10)

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

3 算法描述

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

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

圖2 兩階段狼群算法流程

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

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

3.1.2游走

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

3.1.3召喚

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

圖3 猛狼奔襲過程

3.1.4圍攻

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

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

3.2 貨位分配階段

3.2.1編碼和初始化種群

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

圖4 貨位分配編碼示例

3.2.2游走

計算探狼i的目標適應(yīng)度Yi，若Yi

3.2.3召喚

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

3.2.4圍攻

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

3.3 方案可行性判斷

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

3.4 算法終止條件

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

4 實驗與分析

4.1 仿真實驗設(shè)計

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

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

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

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

4.2 算法參數(shù)選擇

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

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

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

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

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

4.3 結(jié)果分析

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

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

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

(a)20對指令

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

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

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

5 結(jié)語

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