張 磊 冷杰武 龔 粵

1. 廣東工業(yè)大學(xué)廣東省計算機(jī)集成制造重點實驗室，廣州，510006 2. 廣東工業(yè)大學(xué)省部共建精密電子制造技術(shù)與裝備國家重點實驗室，廣州，510006

0 引言

隨著智能制造在全球的不斷推進(jìn)，物流的重要性日益凸顯，作為現(xiàn)代物流系統(tǒng)核心和樞紐的自動化立體倉庫受到企業(yè)界和學(xué)術(shù)界的高度關(guān)注。自動化立體倉庫可提高倉儲作業(yè)效率，實現(xiàn)智能化、無人化。實現(xiàn)倉儲高效作業(yè)和智能化的關(guān)鍵在于能否實現(xiàn)貨位優(yōu)化，而自動倉儲系統(tǒng)(automated storage and retrieval system,AS/RS)的貨位優(yōu)化屬于NP難問題，一方面，工程上不斷將新技術(shù)應(yīng)用于AS/RS以實現(xiàn)智能化；另一方面，學(xué)術(shù)界采用智能優(yōu)化理論對AS/RS的研究相當(dāng)豐富。對AS/RS的研究從起初的硬件結(jié)構(gòu)研究轉(zhuǎn)向庫位優(yōu)化及出入庫調(diào)度等軟件方面。HESKETT等[1]提出了COI索引值的貨位分配方法，主要思想是某種貨物的最大在庫量和周轉(zhuǎn)率的比值越小，該貨物的貨位就越應(yīng)靠近入口；LEE等[2]在一直固定取貨指令的前提下，對存取指令進(jìn)行排序，以所有存取任務(wù)的時間最短為目標(biāo)，結(jié)果表明對提高立體倉庫的存取效率有明顯作用；SARKER等[3]采用貪婪排序算法對比雙載位立體倉庫的吞吐量和單載位立體倉庫的吞吐量，結(jié)果表明雙載位立體倉庫的吞吐量比單載位高40%左右；KIM等[4-5]對立體倉庫的揀選作業(yè)進(jìn)行研究分析，將其歸納為旅行商問題，以行程最短為目標(biāo)建立模型，并采用改進(jìn)啟發(fā)式算法進(jìn)行求解；KHOJASTEH-GHAMARI等[6]對多巷道立體倉庫的貨物揀選作業(yè)進(jìn)行分析，建立以最短揀選時間為目標(biāo)的數(shù)學(xué)模型，并采用遺傳算法對模型進(jìn)行求解；BYUNG等[7]提出根據(jù)貨物周轉(zhuǎn)率的高低劃分貨位存儲分區(qū)，方便貨物的管理；THOMSON等[8]通過對立體倉庫的貨物揀選作業(yè)進(jìn)行詳細(xì)分析，提出路徑協(xié)調(diào)規(guī)劃方法進(jìn)行求解；EKREN等[9]提出利用矩陣幾何方法和半開放式排隊網(wǎng)絡(luò)，對立體倉庫的主要性能進(jìn)行分析。

國內(nèi)對自動化立體倉庫的研究也相當(dāng)豐富，李詩珍等[10]研究了揀貨方式、路徑策略、存儲策略對人工揀選效率的協(xié)同作用，并確定各策略的適用場合；唐江峰[11]分析了板式定制家具生產(chǎn)的工藝特點，改造并設(shè)計滿足板材生產(chǎn)自動分揀工藝的立體倉庫，并對加入分揀約束的立體倉庫貨位分配進(jìn)行分析；王進(jìn)業(yè)等[12]對旁通式自動化立體倉庫的揀選作業(yè)和復(fù)合作業(yè)的運動路徑和出入口選擇進(jìn)行分析，以堆垛機(jī)運行時間最短和運行次數(shù)最少為優(yōu)化目標(biāo)建立數(shù)學(xué)模型，分別采用遺傳算法和單親遺傳算法來求解，結(jié)果表明該模型可明顯提高旁通式立體倉庫運行效率；薛婷等[13]采用組態(tài)軟件和可編程控制器設(shè)計了立體倉庫的自動控制系統(tǒng)軟件和上位機(jī)控制軟件；泮家麗等[14]采用物流仿真方法對立體倉庫進(jìn)行優(yōu)化；劉欣[15]在貨物質(zhì)量數(shù)據(jù)缺失的情況下，對立體倉庫揀選作業(yè)進(jìn)行優(yōu)化，并采用數(shù)據(jù)仿真方法進(jìn)行驗證。

綜上，當(dāng)前學(xué)術(shù)界對AS/RS的研究方向主要集中在立體倉的揀選作業(yè)、單一作業(yè)及復(fù)合作業(yè)三大方面的貨位優(yōu)化和調(diào)度問題上，主要目標(biāo)是縮短存取時間，減少能耗，提高效率。研究對象主要集中在單元貨格式立體倉庫，其特點是貨架由同一尺寸的貨格組成；而對懸臂式貨架立體倉庫的研究幾乎沒有，懸臂式貨架是由在立柱上裝設(shè)懸臂梁構(gòu)成的，在懸臂梁上加擱板后，則適合空間小和高度低的庫房，管理方便，視野寬闊，比普通擱板式貨架利用率高。懸臂式貨架立體倉庫沒有固定的貨位，每個位置都可能是貨位，從理論上分析，其平面利用率可達(dá)100%。當(dāng)前因為懸臂式貨架立體倉庫的自動化程度較低，貨位最主要是根據(jù)經(jīng)驗分配。本文采用智能算法對懸臂式貨架立體倉庫的貨位優(yōu)化進(jìn)行分析，研究結(jié)論為懸臂式貨架立體倉庫的貨位分配提供參考。

1 問題描述

有一批矩形貨物集合{G1,G2,…,Gn}，貨物具有{形狀，質(zhì)量，材料，密度}等多種屬性，現(xiàn)將其全部裝入一個2n層的單軌雙貨架立體倉庫中，在保證倉庫平穩(wěn)的情況下實現(xiàn)貨位利用率最大化。為了方便建立立體倉庫的入庫庫位分配模型，對問題論述的前提作以下規(guī)定：①立體倉庫的貨架左邊編號為單數(shù)，右邊編號為雙數(shù)，最低層分別為第1層、第2層，從下往上遞增；②入庫作業(yè)時堆垛機(jī)為單一作業(yè)模式，堆垛機(jī)只進(jìn)行入庫作業(yè)，整個作業(yè)期間無貨物出庫；③為了保證貨物安全出入庫，貨物與貨架兩端以及貨物與貨物之間的間隔設(shè)為10 cm，貨物的高必須比所在貨架高度低10 cm；④一個大的貨位段允許分配成多個貨位給多個貨物，貨位段內(nèi)的貨物順序不做排序；⑤已被利用的貨物段一旦不能再被分配貨位，則剩下的貨位段將被視為浪費;⑥由于影響貨物在立體倉庫中貨位的主要因素是貨物的形狀和質(zhì)量，故忽略貨物的其他屬性。

為了保證貨架的安全性以及貨位分配的合理性，要求滿足下列約束條件：①每個貨位段中裝載的貨物不超出裝載空間的邊界；②所裝貨物的質(zhì)量之和不超過貨架允許載質(zhì)量。

2 數(shù)學(xué)建模

記G={G1,G2,…,Gn}為n個矩形貨物集合；T={T1,T2,…,Tm}為m個貨位段集合；li、wi、hi、ki分別為貨物Gi的長、寬、高、質(zhì)量；Lj、Wj、Hj、Nj、Xj分別為貨位段Tj的長、寬、高、所在貨架層號以及貨位段起始點距離本層貨架起始端點的距離，空貨架所包含的貨位段X值為0；aij=1或0，若貨物Gi分配給貨位段Tj，則aij取1，否則取0；M為貨架的最大載質(zhì)量；D1為貨物與貨架兩端以及貨物與貨物之間的間隔；D2為貨物頂部與上層貨架擋板之間的最小安全距離。根據(jù)上述設(shè)定，建立約束條件的數(shù)學(xué)模型：

(1)

wi

(2)

hi+D2

(3)

(4)

(5)

約束條件中，式(1)～式(3)分別表示貨位段所裝載的貨物在保證安全間隔的情況下不超出貨位段的裝載空間；式(4)表示每個貨架裝載貨物的質(zhì)量之和不超過貨架的最大載質(zhì)量；式(5)表示一個貨物只能分配給一個貨位段。

立體倉庫的倉儲利用率是評判立體倉庫優(yōu)劣的基礎(chǔ)指標(biāo)，提高倉庫的空間利用率是提高立體倉庫使用效率、降低成本的有效手段。為提高懸臂式貨架立體倉庫的利用率，實現(xiàn)最大的存儲，需保證貨位段在分配完貨位之后貨位浪費最少,則其目標(biāo)函數(shù)為

(6)

為了保證整個立體倉庫的穩(wěn)定性，并考慮作業(yè)安全和節(jié)約能源，貨物分配需遵循下重上輕的存儲原則，即要求所有貨物的質(zhì)量與所在貨架層的乘積之和最小，使貨架的重心最低，提高整個貨架的穩(wěn)定性，則其目標(biāo)函數(shù)表示為

(7)

顯然，這是一個多目標(biāo)的優(yōu)化問題，采用加權(quán)重的方法將多目標(biāo)轉(zhuǎn)化為單目標(biāo)，將代表目標(biāo)在多目標(biāo)優(yōu)化問題中的權(quán)重系數(shù)u1和u2分別賦予對應(yīng)的目標(biāo)函數(shù)S和Q，權(quán)重的大小表示相應(yīng)的目標(biāo)函數(shù)的重要程度。采用權(quán)重自適應(yīng)方法確定各目標(biāo)函數(shù)的權(quán)重，能根據(jù)種群的當(dāng)前信息實時調(diào)整權(quán)重，提高模型的柔性和適用范圍，有

(8)

式中，Smax、Smin分別為當(dāng)前種群中最大利用率目標(biāo)函數(shù)的最大值和最小值；Qmax、Qmin分別為當(dāng)前種群中平衡性目標(biāo)函數(shù)的最大值和最小值;S、Q分別為當(dāng)前種群中當(dāng)前個體的最大利用率目標(biāo)函數(shù)值和平衡性目標(biāo)函數(shù)值。

3 多種群遺傳算法求解貨位分配優(yōu)化問題

3.1 多種群遺傳算法

標(biāo)準(zhǔn)遺傳算法(standard genetic algorithm， SGA)是通過模擬自然界優(yōu)勝劣汰的進(jìn)化過程而形成的一種搜索全局最優(yōu)解的方法。遺傳算法在解決組合優(yōu)化問題上有操作簡單、魯棒性強(qiáng)和全局搜索性強(qiáng)等優(yōu)點。對于懸臂式貨架立體倉庫的貨位優(yōu)化問題也可以用SGA進(jìn)行求解，但SGA存在早熟和因初始種群不合理而易陷入局部最優(yōu)等問題。而多種群遺傳算法(muti-population genetic algorithm， MPGA)具有初始種群多樣性和多種群協(xié)調(diào)進(jìn)化的特性，并配合參數(shù)的自適應(yīng)控制方法和對適應(yīng)度函數(shù)進(jìn)行縮放，可提高遺傳算法的自適應(yīng)能力和搜索能力。本文采用MPGA進(jìn)行求解，有效地避免了早熟和陷入局部最優(yōu)解等問題，明顯提高了收斂速度。

3.1.1移民算子

多種群遺傳算法中各種群保持相對獨立性，為避免多種群遺傳算法變成簡單的多次遺傳算法實驗，需加強(qiáng)種群之間的聯(lián)系。因此，引入移民算子，可加強(qiáng)各種群間聯(lián)系，豐富種群多樣性，防止未成熟和早熟現(xiàn)象。移民算子是將源種群中的最優(yōu)個體代替目標(biāo)種群中的最差個體，達(dá)到多種群協(xié)同進(jìn)化的目的，見圖1。

3.1.2精華種群

精華種群大小決定了多種群遺傳算法的迭代代數(shù)，而精華種群的提取需人工選擇每一代中每一個種群的最優(yōu)個體，并將其放入精華種群加以保存，保證各種群產(chǎn)生的最優(yōu)個體不被破壞和丟失，見圖2。

圖1 移民算子操作Fig.1 Operation of Immigrant operator

圖2 人工選擇精華種群Fig.2 Artificial selection of the elite population

3.1.3控制參數(shù)

遺傳算法中的交叉概率和變異概率參數(shù)的選擇是影響遺傳算法收斂性和性能的關(guān)鍵所在，交叉概率影響全局搜索能力，變異概率影響局部搜索能力，而目前沒有具體可行的方法選擇參數(shù)，通常隨機(jī)選擇交叉概率Px為0.7～0.9，變異概率Pm取0.001～0.05，具有相當(dāng)大的盲目性。為避免發(fā)散和陷入局部最優(yōu)問題,在適應(yīng)度值高時需減小Px和Pm的值，加快收斂；適應(yīng)度值低時需提高Px和Pm的值，防止陷入局部最優(yōu)：

其中，avg(f)表示當(dāng)前種群中平均適應(yīng)度；max(f)表示當(dāng)前種群中最大適應(yīng)度；f表示當(dāng)前種群中交叉?zhèn)€體的最大適應(yīng)度；f′表示當(dāng)前種群中變異個體的適應(yīng)度；參數(shù)v1，v2∈(0.7,0.9)且v1

3.2 算法實現(xiàn)

3.2.1編碼設(shè)計

編碼的目的是確定各個貨位段的貨物分配狀況。由于貨物在貨位段中的擺放順序不影響整體的貨位優(yōu)化結(jié)果，故每個貨位段只需知道有哪些貨物分配在該貨位段中即可。本文采用二進(jìn)制編碼來表示貨位分配狀況，其所包含的信息如下：

aji∈{0,1}

由于每一個貨物只能分配一個貨位，所以A的每個行向量bi=(a1i,a2i,…,ani)中只能有一個值為1。已知某個j貨位段的貨物分配狀況時，根據(jù)貨位短信息和貨物信息就可求得該貨位段中分配的所有貨物的貨位信息。

3.2.2初始種群

初始種群的質(zhì)量、規(guī)模都會影響最優(yōu)解的搜索，通常初始種群采用隨機(jī)方式生成，會生成滿足約束條件的可行個體和不滿足約束的非可行個體，導(dǎo)致種群的質(zhì)量無法保證。初始種群加入強(qiáng)約束會增大初始種群的復(fù)雜度，延長初始種群的生成時間。采用弱約束的方式生成初始種群，即在所有約束條件中選取少數(shù)約束，既保證初始種群的生成時間不至于過長，又能提高初始種群的質(zhì)量，保證算法的盡快搜索最優(yōu)解。考慮到多種群的初始種群量較大，初始種群時只滿足每一個貨物只能分配一個貨位和一個約束條件。

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

適應(yīng)度函數(shù)是用來區(qū)分群體中個體優(yōu)劣的標(biāo)準(zhǔn)，是進(jìn)行遺傳算法進(jìn)化選擇的唯一標(biāo)準(zhǔn)，通常情況下由目標(biāo)函數(shù)變換得來。采用輪盤賭進(jìn)行選擇操作的最大問題如下：前期當(dāng)適應(yīng)度比較分散時，容易產(chǎn)生超級個體，出現(xiàn)早熟；后期當(dāng)適應(yīng)度比較集中時，又不易選出適應(yīng)度高的個體，出現(xiàn)爬山能力不足。對適應(yīng)度進(jìn)行放縮，能快速聚集種群，提高適應(yīng)度值。由于本文中的目標(biāo)函數(shù)是求最小值，首先需要對目標(biāo)值求倒數(shù)：

其中，avg(1/f)表示當(dāng)前種群中目標(biāo)函數(shù)倒數(shù)的平均值；max(1/f)表示當(dāng)前種群中目標(biāo)函數(shù)倒數(shù)的最大值；c表示放縮控制參數(shù)，c取值越小，放縮程度越大，此處取1.5。

3.2.4多種群操作

提取出每一代各種群中適應(yīng)度最好和最差的個體，通過移民算子實現(xiàn)各種群間優(yōu)秀個體的傳播，豐富種群的多樣性，提高算法的全局搜索能力。另外，人工選擇每一代各種群的最優(yōu)個體并保存到精華種群，直到精華種群的規(guī)模達(dá)到設(shè)計要求便結(jié)束算法。

4 仿真實驗及分析

分別采用SGA和MPGA對7組數(shù)據(jù)進(jìn)行優(yōu)化，結(jié)果見表1。圖3和圖4分別為其中第6組數(shù)據(jù)采用SGA和MPGA適應(yīng)度函數(shù)隨進(jìn)化代數(shù)的收斂情況。SGA各參數(shù)值如下：種群規(guī)模p=40，交叉概率Px=0.7，變異概率Pm=0.01，最大遺傳代數(shù)Gmax=200。MPGA各參數(shù)值如下：種群規(guī)模p=40，種群數(shù)量GNum=3，交叉概率Px為0.7～0.9，變異概率Pm為0.001～0.05，最大精華種群規(guī)模Gmax=200。

表1 SGA和MPGA性能對比

對比兩種算法對貨位優(yōu)化的結(jié)果可知，單從SGA和MPGA都收斂并且最佳適應(yīng)度相同的數(shù)據(jù)結(jié)果來看，SGA在平均計算時間方面比MPGA表現(xiàn)稍好，這主要是因為MPGA的整體運算規(guī)模比SGA大。雖然SGA在運算時間上比MPGS有優(yōu)勢，但SGA卻存在致命的早熟問題和不收斂問題。對比圖3和圖4可以看出，多種群遺傳算法在運行到第31代就已經(jīng)收斂，且目標(biāo)函數(shù)值為22 055；而簡單遺傳算法運行到第65代才收斂，其目標(biāo)函數(shù)值為29 880，可見MPGA的全局搜索能力明顯優(yōu)于簡單遺傳算法。

MPGA相比SGA在懸臂式貨架立體倉庫貨位優(yōu)化中具有更好的全局搜索能力，且能較好地解決SGA存在的早熟和不收斂等問題。本文對兩種優(yōu)化策略采用等值處理，在實際應(yīng)用中可以根據(jù)具體問題調(diào)整權(quán)重，以得到更合理、更高效的分配方案。

圖3 SGA適應(yīng)度函數(shù)值變化曲線Fig.3 Fitness function value change curve of SGA

圖4 MPGA適應(yīng)度函數(shù)值變化曲線Fig.4 Fitness function value change curve of MPGA

5 結(jié)論

本文詳細(xì)介紹了懸臂式貨架立體倉庫的結(jié)構(gòu)和貨位分配特點，提出倉庫最大利用率和貨架穩(wěn)定性的策略實現(xiàn)貨位智能優(yōu)化，并建立多目標(biāo)數(shù)學(xué)模型，采用智能算法對模型進(jìn)行優(yōu)化分析。最后采用MATLAB仿真實驗，從平均計算時間、適應(yīng)度函數(shù)變化方面對比MPGA和SGA，結(jié)果表明MPGA在解決懸臂式貨架立體倉庫貨位優(yōu)化問題上比SGA更優(yōu)異高效。本文只考慮倉庫最大利用率和穩(wěn)定性兩個衡量指標(biāo)，下一步將在此基礎(chǔ)上研究如何構(gòu)建數(shù)字孿生系統(tǒng)[16-18],以提高立體倉庫的運行效率。