方 磊，吉衛(wèi)喜，彭 威，馮 晨

江南大學(xué) 機械工程學(xué)院，江蘇 無錫 214122

倉庫作為實業(yè)公司實現(xiàn)儲運功能的主體，快速精準(zhǔn)地響應(yīng)公司需求是倉庫的第一使命。隨著信息化、自動化以及相關(guān)技術(shù)快速發(fā)展，自動化立體倉庫的建立與運行維護成本顯著降低，且自動化立體倉庫有著作業(yè)高效穩(wěn)定、空間利用率高等優(yōu)點[1]，因而廣受實業(yè)公司的青睞。對于配置確定、已經(jīng)投入使用的自動化立體倉庫而言，決定其作業(yè)效率的關(guān)鍵在于儲位分配和任務(wù)調(diào)度（或稱路徑優(yōu)化），采用適宜的儲位分配策略與任務(wù)調(diào)度方法可以減少儲運成本，有效提升倉儲作業(yè)效率。

現(xiàn)有文獻中，國內(nèi)外學(xué)者對儲位分配與任務(wù)調(diào)度以及二者集成優(yōu)化問題進行大量研究。對于儲位分配，一些學(xué)者[2-5]通常采用的方法是將儲物分類、儲位分區(qū)，按一定規(guī)則將每類儲物固定分配到某區(qū)儲位的靜態(tài)分類方法。Kübler等[6]提出適時再分配的方法，通過給儲位、儲物定義屬性，計算成本。儲位分配一段時間后，判斷重新進行儲位分配帶來優(yōu)化效果是否大于再分配的成本，如果大于就執(zhí)行新一輪的儲位分配。Wang等[7]介紹了一種按時段進行儲位劃分的方法，對于服飾制造等周期性企業(yè)，根據(jù)需求預(yù)測結(jié)果劃分時段，并在每個時段之初進行儲位分配。Zhang等[8]提出貨架穩(wěn)定性約束條件，以最小化運輸距離、最大化貨架穩(wěn)定性、同類最相近原則建立多目標(biāo)貨位分配模型。對于任務(wù)調(diào)度，顏波等[9]以訂單為調(diào)度整體，將出庫和入庫任務(wù)組合，建立以最大完工時間和最大訂單拖期綜合指標(biāo)最小化為目標(biāo)的數(shù)學(xué)模型，采用離散型帝國競爭算法進行求解。夏莉等[10]考慮含周轉(zhuǎn)箱容量約束的任務(wù)調(diào)度問題，提出混合模擬退火與遺傳算法的求解方法并加以驗證。韓冬亞等[11]考慮多出入口情況下，批次執(zhí)行過程中任務(wù)排序與出入口選擇的雙約束優(yōu)化問題，并采用兩階段的啟發(fā)式算法求解。對于集成優(yōu)化，Tostani等[12]提出一種雙層多目標(biāo)優(yōu)化模型，上層采用基于類的儲位分配模型，下層是考慮帶有時間約束的多臺起重機工作平衡的能耗模型，最后利用改進協(xié)同優(yōu)化算法求解并設(shè)計實驗進行驗證。Chen等[13]以最小化作業(yè)總時間為目標(biāo)，研究共享貨位存取策略下自動化立體倉庫的貨位分配與任務(wù)調(diào)度集成優(yōu)化問題。劉愷文等[14]考慮帶有時間約束的自動化立體倉庫作業(yè)調(diào)度的設(shè)備能耗問題，以最近鄰策略進行儲位分配，建立了堆垛機能耗模型，并采用改進灰狼算法進行求解。湯洪濤等[15]提出了儲位共享與訂單動態(tài)揀選策略下的儲位分配與任務(wù)調(diào)度的集成優(yōu)化方法。楊瑋等[16]考慮多載具自動化立體倉庫的特點，構(gòu)建以最小化總行程時間為目標(biāo)的儲位分配與任務(wù)調(diào)度的集成優(yōu)化數(shù)學(xué)模型，并設(shè)計雙層遺傳算法求解。

綜上所述，學(xué)者們提出的靜態(tài)分類方法雖然有效提高了倉儲作業(yè)效率，但不能應(yīng)對變化的市場，隨著時間推移，原本劃分的儲區(qū)出現(xiàn)部分滿載、部分閑置或新產(chǎn)生的分類無區(qū)可分的情況，這時需要進行儲位再分配，這會增添倉儲作業(yè)負(fù)擔(dān)。且由于儲位分配與任務(wù)調(diào)度相互影響，單獨優(yōu)化儲位分配或任務(wù)調(diào)度只能起到部分作用。因此同時考慮動態(tài)儲位分配與任務(wù)調(diào)度集成優(yōu)化方法，可以更好提升自動化立體倉庫的作業(yè)效率。

此外，學(xué)者們對自動化立體倉庫任務(wù)的執(zhí)行順序也有所忽略，因為通常假定任務(wù)連續(xù)不斷，但實際上考慮質(zhì)檢、復(fù)核等操作以及管理上的方便，存在較多按批次執(zhí)行訂單的倉庫。故本文在前人基礎(chǔ)上，考慮任務(wù)優(yōu)先級不同而產(chǎn)生任務(wù)順序約束的問題，提出一種動態(tài)儲位分配策略，即在每批次任務(wù)調(diào)度時，將當(dāng)前批次內(nèi)揀貨產(chǎn)生的空庫位也納入可用庫位，進行局部最優(yōu)儲位分配。該策略要求相應(yīng)出庫任務(wù)執(zhí)行順序在前，即任務(wù)順序約束，提高了任務(wù)調(diào)度的復(fù)雜性。因而一般的啟發(fā)式尋優(yōu)算法不能滿足需求，故提出一種校正機制，并采用一種改進離散型帝國競爭算法求解。另外，為應(yīng)對日益嚴(yán)重的全球氣候問題，我國提出“碳達峰、碳中和”的目標(biāo)，這就要求各行各業(yè)采取綠色環(huán)保相關(guān)措施。對于自動化倉庫行業(yè)，設(shè)備能耗最優(yōu)既是對環(huán)保政策的響應(yīng)，同時也降低了倉儲運行成本，故本文以設(shè)備能耗最低為目標(biāo)，研究倉儲作業(yè)能耗優(yōu)化調(diào)度問題。

1 問題描述及模型說明

本文研究的自動化立體倉庫采用具有單一載具的巷道堆垛機，其特點為：貨架之間獨立，堆垛機每次執(zhí)行任務(wù)時只能運載一個單元的貨物，不考慮缺貨、空庫、滿庫等異常情況。倉儲作業(yè)管理上，分批次執(zhí)行訂單，即把出入庫訂單按抵達時段劃分批次，當(dāng)前執(zhí)行任務(wù)為上一時段到達訂單。因此每批次都有相應(yīng)的批次截止時間約束。

基于上述條件，研究以堆垛機運行時總能耗最低為目標(biāo)的倉儲作業(yè)調(diào)度問題，本文通過動態(tài)儲位分配策略，將出入庫訂單分解為堆垛機可執(zhí)行的出入庫任務(wù)，同時指派儲位坐標(biāo)，并產(chǎn)生任務(wù)順序約束；依據(jù)儲位指派結(jié)果，在滿足約束的前提下將分配儲位坐標(biāo)相近的出入庫任務(wù)兩兩組合，以使堆垛機一次運行完成一個出庫任務(wù)和入庫任務(wù)，其流程如圖1所示。

圖1 模型流程說明圖Fig.1 Model process description diagram

1.1 動態(tài)儲位分配策略

倉儲儲位分配策略分為隨機（非定位）存儲和定位存儲。根據(jù)倉儲所服務(wù)客體的需求與行業(yè)特點，在不同策略下對貨物周轉(zhuǎn)率、貨物相關(guān)性、安全性、時效性等因素的側(cè)重點有所區(qū)別。

本文的倉儲任務(wù)調(diào)度問題以自動化立體倉庫能耗最低為目標(biāo)，因此選用考慮周轉(zhuǎn)率影響的隨機儲位分配策略，即將比重大、周轉(zhuǎn)快的貨物分配在靠近倉庫進出口（I/O）位置的儲位。通過計算目標(biāo)儲位與I/O 位置距離，并考慮貨物的比重和周轉(zhuǎn)率對儲位分配的影響，以Wki值來衡量儲位分配的優(yōu)劣，其計算方式為：

式（1）中Wki表示貨物i存放在儲位k的適宜程度，值越小表示越適宜；Dk表示儲位k到I/O的距離；式（2）中DTIi表示貨物i的運輸屬性，值越大表示越應(yīng)該安排在靠近I/O的儲位；VEi表示貨物i的體積；Mi為貨物i的質(zhì)量；Qti表示貨物i在時間t內(nèi)的周轉(zhuǎn)率。

本文的動態(tài)儲位策略是指：對每批次訂單都進行一次局部最優(yōu)儲位分配。具體步驟如下：

步驟1以一托盤為計量單位將出入庫訂單分解為相應(yīng)的出入庫單元任務(wù)，并編號。

步驟2根據(jù)庫存情況，以先進先出原則向出庫任務(wù)指派儲位，這部分儲位稱為待出庫儲位。

步驟3分別計算待入庫貨物的屬性DTI值，并降序排列；將部分待出庫儲位和空閑儲位共同作為可用儲位，并計算可用儲位與I/O的距離Dk，升序排列。

步驟4待入庫貨物和可用儲位按照排序組合，即可得到符合Wki最小原則的儲位指派結(jié)果。

上述流程如圖2 所示。將其中入庫任務(wù)復(fù)用的待出庫儲位，稱為約束儲位，它對應(yīng)的一組出入庫任務(wù)稱為約束任務(wù)，要求對應(yīng)的出庫任務(wù)必須在相應(yīng)入庫任務(wù)之前進行，并將此條件作為任務(wù)調(diào)度模型中一項必要約束。

圖2 儲位分配流程圖Fig.2 Flowchart of storage allocation

對于約束儲位的選擇，通常將倉庫儲區(qū)劃分成不同等級的區(qū)域，如黃金庫區(qū)（super，S）、一般庫區(qū)（average，A）和較差庫區(qū)（bad，B）等[17]。約束儲位根據(jù)實際情況，可選S 區(qū)或S 區(qū)和A 區(qū)的儲位作為約束儲位，B 區(qū)儲位則不作為約束儲位。分區(qū)依據(jù)為儲位與I/O位置接近程度，分類比重為S 區(qū)儲位占比20%、A 類占比30%、B 類占比50%。

1.2 任務(wù)組合調(diào)度模型

1.2.1 任務(wù)組合

堆垛機執(zhí)行任務(wù)時，分為單指令模式和復(fù)合指令模式。單指令模式，即堆垛機執(zhí)行一個出庫或入庫任務(wù)后，立即返回I/O位置。而復(fù)合指令模式是指，將一組出入庫任務(wù)捆綁在一起，堆垛機執(zhí)行入庫任務(wù)后不返回I/O位置，而是直接移動至出庫儲位執(zhí)行出庫任務(wù)，將待出庫貨物搬運至I/O位置完成一次復(fù)合作業(yè)，如圖3所示。

圖3 堆垛機任務(wù)分配與路徑圖Fig.3 Stacker task allocation and path diagram

當(dāng)堆垛機在復(fù)合指令模式下運行時，一個出庫任務(wù)與入庫任務(wù)構(gòu)成一個任務(wù)組，任務(wù)組分三階段執(zhí)行，每階段距離如下：

第一階段距離D1：由I/O位置移動至入庫任務(wù)儲位；

第二階段距離D2：由該儲位移動至出庫任務(wù)儲位；

第三階段距離D3：由出庫任務(wù)儲位返回I/O位置。

如圖3所示，單指令作業(yè)模式下作業(yè)距離為2(D1+D3)，而復(fù)合指令作業(yè)距離為D1+D2+D3,由三角形三邊關(guān)系可知，單指令作業(yè)模式堆垛機運行路徑必然大于復(fù)合指令作業(yè)模式。當(dāng)任務(wù)儲位指定時，D1與D3是堆垛機執(zhí)行任務(wù)所不可改變的距離，定義為絕對距離，所產(chǎn)生的能耗稱為絕對能耗；D2是任務(wù)組合所產(chǎn)生的儲位相對距離，不同任務(wù)組合方式，距離不同，因此定義為相對距離，所產(chǎn)生能耗稱為相對能耗。其中，入庫任務(wù)4 與出庫任務(wù)5 指派在同一儲位，要求出庫任務(wù)5 的執(zhí)行順序要在入庫任務(wù)4之前，即動態(tài)儲位分配策略產(chǎn)生的約束任務(wù)樣例。

1.2.2 能耗計算

巷道堆垛機水平方向與垂直方向運動由各自電機提供驅(qū)動，運動間相互獨立。對巷道堆垛機在作業(yè)過程中的受力平衡與運動特性分析，可計算其運行時能耗E大小，以水平方向上能耗Ex計算為例：

水平方向能量Ex計算如式（3）～（5）所示，其中Mx為電機驅(qū)動扭矩；r為行走輪半徑；Dx為水平位移；Vx為堆垛機水平運行額定速度；η為電機能量轉(zhuǎn)化效率；kr為滾動阻力系數(shù)；m表示質(zhì)量；g表示重力加速度；ax為堆垛機水平運行加速度，當(dāng)處于勻速運動時，ax=0；Ax為額定水平運行加速度；tx為水平運行電機作業(yè)時間。

考慮電機處于不同運動狀態(tài)時作業(yè)時間存在明顯差異，由加速度與速度位移基本公式推導(dǎo)運行電機作業(yè)時間，其中距離表示堆垛機恰好先加速至額定速度再減速至靜止時的臨界值，當(dāng)任務(wù)距離大于臨界值時，堆垛機存在加減速和勻速運動，反之則只進行加減速運動。

垂直方向上能耗Ey與水平方向上能耗Ex同理，由Ey與Ex共同構(gòu)成堆垛機作業(yè)能耗E。

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

根據(jù)上述理論基礎(chǔ)，構(gòu)建數(shù)學(xué)模型如下：

模型中使用的數(shù)學(xué)符號定義如下：R為任務(wù)集合，其中Rin和Rout為R的子集，k∈R為任務(wù)索引；Rin為入庫任務(wù)集合，i∈Rin為入庫任務(wù)索引；Rout為貨物出庫任務(wù)集合，j∈Rout為出庫任務(wù)索引；Cj,f為出庫任務(wù)j在設(shè)備f上的完成時間；為入庫任務(wù)在設(shè)備f上的開始執(zhí)行時間，其中j*為約束任務(wù)號；TR,f為任務(wù)集R在堆垛機f上完成的作業(yè)時間；決策變量表示在堆垛機f上，任務(wù)k在任務(wù)k*前執(zhí)行，反之則順序相反；決策變量uk,f=1 表示任務(wù)k在設(shè)備f上執(zhí)行，反之則為否。

約束條件說明：式（6）中E為目標(biāo)函數(shù)，表示執(zhí)行全部出入庫任務(wù)堆垛機所消耗能量和，與Ej即絕對能耗，其中表示堆垛機從I/O口移動至任務(wù)i所在儲位時能耗，j*為約束任務(wù)號；Ej表示堆垛機從任務(wù)j所在儲位移動至I/O 口時能耗；ΔEij即相對能耗，表示堆垛機由任務(wù)i所在儲位移動至任務(wù)j所在儲位時能耗。式（7）表示同一時間下，每個出入庫任務(wù)僅在一個設(shè)備上執(zhí)行。式（8）和（9）表示在堆垛機f上執(zhí)行的兩個任務(wù)有先后順序。（10）表示有約束關(guān)系任務(wù)，出庫任務(wù)執(zhí)行順序先于對應(yīng)的入庫任務(wù)。式（11）表示批次任務(wù)全部完成的最大完成時間要在批次截止時間Td內(nèi)。

2 基于改進帝國競爭算法的作業(yè)調(diào)度

本文采用帶有校正機制的離散型帝國競爭算法（C-ICA）求解自動化立體倉庫出入庫作業(yè)組合及排序問題。帝國競爭算法（imperialist competitive algorithm，ICA）是一種受社會啟發(fā)的隨機優(yōu)化搜索算法，在大規(guī)模組合優(yōu)化問題上具有一定優(yōu)越性[9]，但由于ICA 算法產(chǎn)生的初解若在解空間分布不均，則會使最終解易于偏向局部最優(yōu)解。針對此，陳禹等[18]提出忠誠度概念優(yōu)化同化機制，通過劃分時間節(jié)點，動態(tài)劃分迭代階段而優(yōu)化競爭機制，以提升算法精度和搜索廣度。而王貴林等[19]在帝國競爭算法中引入春秋戰(zhàn)國合縱連橫的思想，改進競爭機制，從而有效避免“早熟”現(xiàn)象。本文則引入外來帝國入侵的概念，提出一種入侵機制以擴大解的搜索廣度，提升收斂速度；同時建立一種校正機制以解決儲位分配產(chǎn)生的任務(wù)順序約束。為了便于理解算法的過程，圖4給出了改進算法求解的具體流程。

圖4 算法流程圖Fig.4 Algorithm flowchart

2.1 編碼與解碼

每個任務(wù)由儲位分配的結(jié)果指定堆垛機及貨架，無需編碼。任務(wù)順序以及出入庫任務(wù)組合，組成帝國競爭算法初始化編碼。每個編碼表示一個國家，即一個可行解。

在編碼過程中，為了方便說明編碼規(guī)則，將任務(wù)順序與組合放在不同維度。假設(shè)3 個入庫訂單、2 個出庫訂單，可拆解為8個出庫任務(wù)、10個入庫任務(wù)，在調(diào)度計算時，如果出入庫任務(wù)數(shù)量不相等，則補充原點任務(wù)使兩者數(shù)量相等，以保證編碼正確。如圖5 所示，入庫任務(wù)序列右上角標(biāo)識為其約束任務(wù)的索引號。解碼時，列為出入庫作業(yè)組合的解，行為出入庫任務(wù)組順序的解。

圖5 編碼格式Fig.5 Encoding format

2.2 適應(yīng)度函數(shù)

本文以堆垛機執(zhí)行完全部出入庫任務(wù)時能耗最低為優(yōu)化目標(biāo)，在算法中每個國家的能耗值可通過式（6）計算?？紤]上述模型具備批次截止時間約束，即在倉儲任務(wù)執(zhí)行過程中，要在批次截止時間前完成，且電機作業(yè)時間與任務(wù)完成時間不同。因此設(shè)定適當(dāng)?shù)膽土P函數(shù)，對搜索到不能滿足截止時間約束的劣質(zhì)解進行懲罰，使得對搜索到相近能耗的解中選取能夠較好滿足時間約束的解。由于任務(wù)完成的時間與能耗具有數(shù)量級差異，對此構(gòu)建算法的適應(yīng)度函數(shù)，如下：

式（12）為每批次任務(wù)完成時間計算公式，式（13）為適應(yīng)度函數(shù)計算公式。其中β為懲罰因子（本文取堆垛機平均額定功率），α為比例系數(shù)（本文取值為5%），tx為執(zhí)行r任務(wù)時水平電機作業(yè)時間，ty為執(zhí)行r任務(wù)時起升電機作業(yè)時間，t0為堆垛機作業(yè)時平均準(zhǔn)備時間，包含等待時間、定位時間、貨格檢測、載貨臺負(fù)載時間、伸縮叉作業(yè)時間等。

2.3 帝國同化及殖民地革命

在初始化的N個國家中，選取M個適應(yīng)度函數(shù)最小的國家作為宗主國，剩余N-M個國家作為殖民地國家，并按照一定概率分配給M個宗主國，由宗主國和其所有的殖民地國家共同組成一個帝國，多個帝國構(gòu)成帝國集團。

2.3.1 帝國內(nèi)同化

在現(xiàn)實社會中，宗主國將向殖民地國家傳播自身的文化思想、經(jīng)濟制度等以加強對殖民地的統(tǒng)治力，而殖民地國家也將向著宗主國移動以提高自身實力，如圖6所示。這一現(xiàn)象在算法中表現(xiàn)為：

圖6 同化機制Fig.6 Assimilation mechanism

步驟1每次在宗主國編碼中隨機選擇兩個交叉點；

步驟2將宗主國編碼中所選交叉點間的片段復(fù)制到殖民地編碼對應(yīng)的位置，并去除殖民地編碼中與宗主國編碼片段相同的序列號；

步驟3將殖民地編碼中剩余的片段按照原有順序放置到對應(yīng)的位置上，形成新殖民地。

2.3.2 殖民地革命

本文采取革命的方法是隨機多點位交換。具體操作為：分別隨機確定殖民地出入庫任務(wù)編碼的交換點位數(shù)，然后針對出入庫任務(wù)序列產(chǎn)生各自的兩個隨機向量，其值為交換位置，尺寸為交換點位數(shù)，進行交換，如圖7所示。

圖7 革命機制Fig.7 Revolutionary mechanism

2.3.3 國家校正

對于動態(tài)儲位分配策略產(chǎn)生的任務(wù)順序約束，要求有約束關(guān)系的出庫任務(wù)在入庫任務(wù)前執(zhí)行，若任務(wù)順序顛倒將導(dǎo)致任務(wù)序列無法進行。因此需要一種校正機制，算法表現(xiàn)為：定位到每個擁有約束條件的入庫任務(wù)，查詢到對應(yīng)約束出庫任務(wù)號，在任務(wù)序列中判斷該出庫任務(wù)號是否在前，如果是，跳過。如果否，則約束出庫任務(wù)前移，約束入庫任務(wù)后移，非約束任務(wù)組保留配對關(guān)系。當(dāng)約束任務(wù)占總?cè)蝿?wù)比不超過50%時，該機制能夠確保解滿足任務(wù)順序約束。國家校正后，計算各國最新成本，擇出最優(yōu)者為新任宗主國，如圖8所示。

圖8 校正機制Fig.8 Correction mechanism

2.4 帝國競爭

帝國競爭行為是帝國競爭算法的核心思想，勢力強大的帝國通過競爭掠奪弱小帝國的殖民地增強自身勢力，而勢力弱小帝國則因此覆滅。

2.4.1 帝國間競爭

帝國間通過總成本值而區(qū)分勢力強弱，帝國總成本越小，則帝國勢力越強。因此競爭前需要計算每個帝國的總成本值，其值由殖民地成本和宗主國成本組成，而二者對帝國勢力影響程度不同，因此需要構(gòu)造帝國總成本目標(biāo)函數(shù)來衡量帝國勢力，即：

其中，Empn表示第n個帝國的總成本；Costcol為殖民地成本，col表示殖民地個數(shù)；Costimp為宗主國成本，δ表示殖民地成本對帝國成本的影響程度（本文取δ=0.1）。帝國間的競爭方法是：將勢力最弱的帝國中成本最大的殖民地釋放，交由其他帝國進行競爭，通常勢力越強的帝國獲得該殖民地的概率越高。

2.4.2 外界帝國集團入侵

原算法僅在隨機產(chǎn)生的初始國家中迭代，考慮產(chǎn)生的初解若在解空間內(nèi)分布不均勻，則算法易陷入局部最優(yōu)。本文參照現(xiàn)實社會中，外界較強勢力入侵會加劇沖突的演變，通過優(yōu)勝劣汰，使生存下來的各方快速變強，基于這一現(xiàn)象提出一種外來帝國集團入侵策略，以增強解的搜索廣度，提升國家的質(zhì)量，使結(jié)果更加貼近最優(yōu)。

步驟1產(chǎn)生隨機國家群，組建一批外來入侵帝國集團。

步驟2采用二元錦標(biāo)賽的形式在原有帝國集團與入侵帝國集團競選戰(zhàn)勝國。

步驟3戰(zhàn)勝國將挑選與原有帝國殖民地數(shù)量相當(dāng)?shù)膬?yōu)秀殖民地組建戰(zhàn)勝國集團，并進入原有帝國集團進行競爭。

2.5 帝國覆滅及算法終止

在算法迭代過程中，帝國集團中最弱帝國的殖民地會以一定概率被其他帝國競爭得到，當(dāng)存在帝國所擁有的殖民地數(shù)量少于或等于規(guī)定的閾值時（本文閾值取0），表示該帝國毀滅，該帝國中的宗主國貶為殖民地由其他帝國競爭。隨著迭代的進行，弱小的帝國不斷被刪除，最終只剩下一個帝國時或算法迭代到規(guī)定最大迭代次數(shù)時，算法終止。將勢力最強帝國中的宗主國作為算法的最優(yōu)輸出結(jié)果。

3 實例分析

本章通過仿真實驗驗證本文提出的改進帝國競爭算法在求解帶有任務(wù)順序與時間雙重約束的自動化立體倉庫作業(yè)能量調(diào)度問題時的有效性。

3.1 參數(shù)設(shè)置

以某電梯零部件制造企業(yè)自動化倉庫數(shù)據(jù)作為仿真實驗依據(jù)，以其設(shè)施規(guī)劃、堆垛機參數(shù)作為算法參數(shù)。自動化倉庫貨架規(guī)格及堆垛機型號如表1所示。

表1 倉儲環(huán)境參數(shù)Table 1 Storage environment parameters

本文隨機產(chǎn)生初始任務(wù)集，即出入庫任務(wù)各100個，并根據(jù)貨架存取情況指派無順序約束情況下出入庫任務(wù)的儲位坐標(biāo)，初始任務(wù)集儲位指派情況如圖9 所示。順序約束的設(shè)置條件為：以S、A 級儲區(qū)作為約束儲位的選擇區(qū)域；約束任務(wù)數(shù)量上限為總?cè)蝿?wù)50%。為了更好驗證算法性能，將初始任務(wù)集劃分為TS1 到TS9 號不同規(guī)模的子集，按順序分別為[50，0%，2 500]，[50，25%，2 500]，[50，50%，2 500]，[100，0%，5 000]，[100，25%，5 000]，[100，50%，5 000]，[200，0%，10 000]，[200，25%，10 000]，[200，50%，10 000]。其中方括號內(nèi)數(shù)據(jù)分別為出入庫任務(wù)總數(shù)、順序約束任務(wù)數(shù)占總?cè)蝿?wù)比例、總時間約束，采用Matlab 保存為.mat 文件作為算法計算依據(jù)。

圖9 貨架內(nèi)出入庫任務(wù)分布情況Fig.9 Distribution of inbound and outbound tasks in shelves

采用經(jīng)典帝國競爭算法（ICA）、遺傳算法（GA）、粒子群優(yōu)化算法（PSO）作為對比算法。各對比算法都進行相應(yīng)離散化處理，各算法參數(shù)如表2所示。

表2 算法參數(shù)詳情Table 2 Algorithm parameter details

3.2 仿真實驗

在相同條件下進行數(shù)值仿真實驗，考慮對比算法無校正操作，不能滿足任務(wù)順序約束則對比無意義，因此分為兩組實驗進行對比，分別為無任務(wù)順序約束組與含任務(wù)順序約束組。其中無任務(wù)順序約束組采用對比算法和C-ICA算法對不含任務(wù)順序約束的任務(wù)集TS1、TS4、TS7進行求解；含任務(wù)順序約束組則僅采用C-ICA算法對全部任務(wù)集進行求解。每個算法獨立運行10次，分別計算各指標(biāo)的平均值、標(biāo)準(zhǔn)差，如表3、表4所示。

3.3 結(jié)果分析

通過表3含任務(wù)順序約束組算法結(jié)果對比，可以得出約束任務(wù)的存在使相對能耗平均上升11.2%，但使絕對能耗平均降低12.09%，而絕對能耗占總能耗比重較大，因而使總能耗平均降低7.34%。這表明本文提出的動態(tài)儲位分配策略能夠有效降低堆垛機作業(yè)的能耗。且相同規(guī)模下，隨著約束任務(wù)增多，會導(dǎo)致相對能耗提升速度大于絕對能耗的下降速度，因而約束任務(wù)不宜設(shè)置過多。綜上分析可知，實現(xiàn)約束任務(wù)的先后關(guān)系，會在一定程度上破壞最優(yōu)任務(wù)組的配對，從而導(dǎo)致相對能耗的提升。當(dāng)約束任務(wù)越多，這種先后關(guān)系越為復(fù)雜，所破壞的最優(yōu)任務(wù)組也就越多。但約束任務(wù)又以耗能較低儲位替換耗能較高儲位，從而減少絕對能耗，并且考慮到絕對能耗占總能耗比重較大，因此總體上能夠降低能耗。

表3 含任務(wù)順序約束組算法結(jié)果Table 3 Algorithm result with task order constraint group

通過表4 無任務(wù)順序約束組算法結(jié)果與圖10 算法收斂曲線對比可以得出，C-ICA算法在不同問題規(guī)模下獲得的解均優(yōu)于其他算法。由于無約束組采用相同任務(wù)集，絕對能耗相同，故只需對比相對能耗指標(biāo)即可。對于相對能耗指標(biāo)，改進量從1.41%～17.44%不等。其中，相比于PSO 改進量最大，平均改進量為14.72%；相比于傳統(tǒng)ICA改進量最小，平均改進量為1.94%。對于作業(yè)時間指標(biāo)，在較小規(guī)模問題上，所有算法結(jié)果作業(yè)時間指標(biāo)均能滿足時間約束；但在較大規(guī)模問題上，任務(wù)集TS7 的案例中PSO 算法的作業(yè)時間平均值已經(jīng)超過時間約束臨界值；而GA 算法雖然均值仍滿足約束，但其部分結(jié)果存在越界現(xiàn)象。與之對比，C-ICA在作業(yè)時間和相對能耗兩指標(biāo)上優(yōu)于其他算法，這表明本文所提入侵機制使算法在尋優(yōu)能力上更加優(yōu)秀。

圖10 算法收斂曲線Fig.10 Algorithm convergence curve

表4 無任務(wù)順序約束組算法結(jié)果Table 4 Algorithm result without task order constraint group

4 結(jié)束語

倉儲作業(yè)調(diào)度對自動化立體倉庫的高效運行有著至關(guān)重要的作用。本文提出一種基于動態(tài)儲位分配策略下的任務(wù)調(diào)度組合優(yōu)化方法，通過加強低能耗儲位的利用率以降低總能耗，但由此產(chǎn)生了復(fù)雜的任務(wù)順序約束。針對此約束，本文采用改進帝國競爭算法，設(shè)計了校正機制將約束任務(wù)集中后兩端分離，以解決任務(wù)順序約束；設(shè)計入侵機制，能夠通過不斷產(chǎn)生優(yōu)質(zhì)解替代劣質(zhì)解以增強算法搜索速度與搜索廣度。通過數(shù)值仿真實驗分別論證動態(tài)儲位分配策略以及改進機制的有效性與合理性。最終結(jié)果表明本文所提優(yōu)化方案能夠有效降低堆垛機作業(yè)能耗，提高倉儲作業(yè)效率。