懸臂式貨架立體倉貨位智能優化

張 磊 冷杰武 龔 粵

1. 廣東工業大學廣東省計算機集成制造重點實驗室，廣州，510006 2. 廣東工業大學省部共建精密電子制造技術與裝備國家重點實驗室，廣州，510006

0 引言

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

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

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

1 問題描述

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

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

2 數學建模

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

(1)

wi

(2)

hi+D2

(3)

(4)

(5)

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

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

(6)

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

(7)

顯然，這是一個多目標的優化問題，采用加權重的方法將多目標轉化為單目標，將代表目標在多目標優化問題中的權重系數u1和u2分別賦予對應的目標函數S和Q，權重的大小表示相應的目標函數的重要程度。采用權重自適應方法確定各目標函數的權重，能根據種群的當前信息實時調整權重，提高模型的柔性和適用范圍，有

(8)

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

3 多種群遺傳算法求解貨位分配優化問題

3.1 多種群遺傳算法

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

3.1.1移民算子

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

3.1.2精華種群

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

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

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

3.1.3控制參數

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

其中，avg(f)表示當前種群中平均適應度；max(f)表示當前種群中最大適應度；f表示當前種群中交叉個體的最大適應度；f′表示當前種群中變異個體的適應度；參數v1，v2∈(0.7,0.9)且v1

3.2 算法實現

3.2.1編碼設計

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

aji∈{0,1}

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

3.2.2初始種群

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

3.2.3適應度函數

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

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

3.2.4多種群操作

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

4 仿真實驗及分析

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

表1 SGA和MPGA性能對比

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

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

圖3 SGA適應度函數值變化曲線Fig.3 Fitness function value change curve of SGA

圖4 MPGA適應度函數值變化曲線Fig.4 Fitness function value change curve of MPGA

5 結論

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