動(dòng)態(tài)儲(chǔ)位分配策略下倉儲(chǔ)作業(yè)能耗優(yōu)化調(diào)度

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

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

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

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

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

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

1 問題描述及模型說明

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

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

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

1.1 動(dòng)態(tài)儲(chǔ)位分配策略

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

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

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

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

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

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

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

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

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

圖2 儲(chǔ)位分配流程圖Fig.2 Flowchart of storage allocation

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

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

1.2.1 任務(wù)組合

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

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

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

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

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

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

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

1.2.2 能耗計(jì)算

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

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

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

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

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

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

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

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

2 基于改進(jìn)帝國競(jìng)爭(zhēng)算法的作業(yè)調(diào)度

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

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

2.1 編碼與解碼

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

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

圖5 編碼格式Fig.5 Encoding format

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

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

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

2.3 帝國同化及殖民地革命

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

2.3.1 帝國內(nèi)同化

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

圖6 同化機(jī)制Fig.6 Assimilation mechanism

步驟1每次在宗主國編碼中隨機(jī)選擇兩個(gè)交叉點(diǎn)；

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

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

2.3.2 殖民地革命

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

圖7 革命機(jī)制Fig.7 Revolutionary mechanism

2.3.3 國家校正

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

圖8 校正機(jī)制Fig.8 Correction mechanism

2.4 帝國競(jìng)爭(zhēng)

帝國競(jìng)爭(zhēng)行為是帝國競(jìng)爭(zhēng)算法的核心思想，勢(shì)力強(qiáng)大的帝國通過競(jìng)爭(zhēng)掠奪弱小帝國的殖民地增強(qiáng)自身勢(shì)力，而勢(shì)力弱小帝國則因此覆滅。

2.4.1 帝國間競(jìng)爭(zhēng)

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

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

2.4.2 外界帝國集團(tuán)入侵

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

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

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

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

2.5 帝國覆滅及算法終止

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

3 實(shí)例分析

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

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

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

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

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

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

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

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

3.2 仿真實(shí)驗(yàn)

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

3.3 結(jié)果分析

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

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

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

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

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

4 結(jié)束語

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