基于遺傳算法的自動化立體倉庫貨位優(yōu)化研究

0 引言

現(xiàn)代物流企業(yè)對于倉儲的現(xiàn)代化管理要求越來越高，自動化立體倉庫（AS/RS）在提升庫存量，提升空間利用率、減少占地和節(jié)約人力等方面具有巨大優(yōu)勢，是物流系統(tǒng)發(fā)展和優(yōu)化的關(guān)鍵環(huán)節(jié)。如何進行貨位分配是影響自動化立體倉經(jīng)濟效益和安全性的核心問題，貨位在遵循貨位分配原則的基礎(chǔ)上如何優(yōu)化，通常從優(yōu)化目標以及優(yōu)化算法入手。由于自動化立體倉庫會因為建筑形式、貨架樣式等因素產(chǎn)生不同的細分類別，也會因為揀選輸送系統(tǒng)、存取作業(yè)設(shè)備、存儲條件和策略等因素的不同，在對貨位分配問題上應(yīng)用的優(yōu)化方法有很大的區(qū)別。

Fonseca[1]將貨位優(yōu)化問題總結(jié)為多目標的求解問題，并且分析了多目標進化方法，提出多目標優(yōu)化問題難以求得最優(yōu)解，只能通過平衡、協(xié)調(diào)多個目標達到Pareto 最優(yōu)解。此外，許多國內(nèi)外學(xué)者把貨位優(yōu)化問題總結(jié)為以出入庫效率、貨架穩(wěn)定性、堆垛機路徑優(yōu)化為主的多目標優(yōu)化模型[2-4]。對于貨位優(yōu)化的多目標優(yōu)化問題，在優(yōu)化算法的選擇上許多學(xué)者采用遺傳算法進行求解。鄧愛民等[5]以貨架穩(wěn)定性、分巷道存放和出入庫效率為目標的基于時間的多目標模型，李梅娟[6]提出了采用Pareto 遺傳算法解決該問題，針對提高貨架穩(wěn)定性和存取效率取得了不錯的優(yōu)化效果。

除此之外有非常多的優(yōu)化算法被應(yīng)用在貨位優(yōu)化問題上，陳月婷、何芳[7]提出了基于Pareto 最優(yōu)解的改進粒子群算法來解決貨位優(yōu)化問題。李鵬飛等[8]通過對比分析提出病毒協(xié)同遺傳算法是解決貨位優(yōu)化問題的一種有效方法。大量學(xué)者熱衷于算法應(yīng)用上的創(chuàng)新，在優(yōu)化目標選擇上主要集中于提高存取效率以及貨架穩(wěn)定性，鮮有考慮工作量均衡的研究，雖然目標優(yōu)先級是次要的，在實際應(yīng)用中也是容易被忽視，但卻是很可能出現(xiàn)的問題。此方面的研究首先要界定工作量的定義，通常是指進行存取作業(yè)的設(shè)備工作量，立體倉庫的作業(yè)設(shè)備不盡相同，除堆垛機外也有應(yīng)用提升機與子母穿梭車的立體倉庫，著眼于作業(yè)設(shè)備工作量均衡的優(yōu)化模型在設(shè)計過程中要考慮實際情況下會產(chǎn)生許多工程上的限制因素，同時模型所需數(shù)據(jù)存在一定的難度，在尋求通用的優(yōu)化模型上，唐文獻等[9]在貨位優(yōu)化模型中設(shè)計了以出入庫頻率為核心的巷道工作量均衡模型，并以細菌覓食算法進行求解，在仿真過程中驗證了單一考慮某個優(yōu)化目標時的優(yōu)化效果，由于目標函數(shù)之間可能存在約束或沖突，同時考慮多個優(yōu)化目標才更符合自動化立體倉庫的實際需求。

本文正是針對我國應(yīng)用最為廣泛的單元貨格式立體倉庫[10]，在以提高存取效率和貨架穩(wěn)定性為優(yōu)化目標以外，考慮到可能出現(xiàn)部分巷道任務(wù)過多，而部分巷道任務(wù)偏少的工作量不均衡問題，為減少此類生產(chǎn)浪費，額外設(shè)置工作量均衡的優(yōu)化目標?？紤]到數(shù)據(jù)的獲取難度，在模型中通過控制巷道與巷道之間總出入庫數(shù)量差值最小來達到基于任務(wù)量的巷道工作量均衡目標，該模型不會被巷道操作設(shè)備的選擇所影響，對這個多目標優(yōu)化問題采用遺傳算法進行求解，通過仿真驗證模型的優(yōu)化效果良好。

1 貨位分配原則

對自動化立體倉庫進行貨位分配時應(yīng)當遵循以下原則：（1）貨架穩(wěn)定性原則。貨架首先應(yīng)當保證具有足夠安全性，貨品的存放應(yīng)當從下至上，上輕下重，降低貨架重心。（2）就近出入庫原則。在自動化立體倉庫中，使存儲位置放置在距離出庫臺附近，尤其是出入庫頻率高的貨物，存放在出庫口附近可以有效減少作業(yè)距離，從而提高存取效率。（3）先進先出原則。同一種貨物在出庫時，應(yīng)當遵循入庫早的先出庫的原則。避免貨物存放時間過長而造成不必要的損失。

2 問題描述與基本假設(shè)

描述如下：在M 公司的倉庫庫區(qū)中選擇共有a 排貨架，每排貨架有b 列c 層，將距離出庫口最近的一排貨架記為第一排，最近的一列記為第一列，最底下一層為第一層。那么，貨位坐標(x,y,z)代表位于第X 排Y 列Z 層的貨格，（x=1,2,…,a;y=1,2,…,b；z=1,2,…,c；a 為偶數(shù)）。每一組貨架都由兩排貨架組成，兩排貨架共用一臺堆垛機完成出入庫作業(yè)，如圖1 所示。出庫臺位置記作(0,0,0)，數(shù)學(xué)模型涉及的符號說明如表1 所示。

圖1 一組貨架示意圖

表1 符號說明

根據(jù)如上描述，將本文進行貨位優(yōu)化的基本假設(shè)總結(jié)如下：（1）該自動化立體倉庫系統(tǒng)的存取方式是單元貨格式，即倉庫的每一個通道中都有一臺巷道堆垛機，其兩側(cè)各有一排貨架，每一排貨架都是相同的，貨架上的每個貨格也都大小相同，每個貨格只能存儲一個貨品，由托盤承托，所有托盤尺寸相同。（2）堆垛機可以對其兩側(cè)的貨架托盤進行存取作業(yè)且兩側(cè)作業(yè)情況一致。（3）立體倉庫的出入庫方式為單端口，采用隨機存儲策略。（4）存取貨品消耗時間忽略不計。（5）巷道堆垛機可以在水平和垂直方向即Y 向和Z 向向上同時做勻速運動。

3 數(shù)學(xué)模型的建立

3.1 出入庫效率最高的目標

根據(jù)就近出入庫原則，要實現(xiàn)距離最短，使得作業(yè)時間最短即可，則所有貨物的存取頻率和堆垛機運行時間乘積之和最小，由此建立數(shù)學(xué)模型：

3.2 貨架穩(wěn)定性的目標

根據(jù)貨架穩(wěn)定性原則，要降低貨架整體的重心，使得貨架整體下重上輕，即使貨品的質(zhì)量mxyz與貨位(x,y,z)所在的層數(shù)z的乘積之和最小，由此建立數(shù)學(xué)模型：

3.3 工作量均衡的目標

為了達到工作量均衡的目標，即每個巷道的工作量均衡，通過控制巷道與巷道之間的出庫任務(wù)量差來使得巷道達到工作量均衡的狀態(tài)，在此策略下還能一定程度上使得貨位數(shù)量均勻分布，間接達到工作量均衡的目的，配合目標函數(shù)（2）可以使貨架有較好的抗傾覆能力[11]，由此建立數(shù)學(xué)模型：

3.4 約束條件

由空間約束條件可知，貨位(x,y,z)是處于貨架內(nèi)的坐標，因此有：

3.5 多目標貨位優(yōu)化模型

根據(jù)以上三個目標函數(shù)和約束條件可得貨位優(yōu)化的多目標函數(shù)表達為：

4 多目標遺傳算法模型求解

解決多目標優(yōu)化問題的基本思路是把多目標問題轉(zhuǎn)化為單目標問題，遺傳算法全局搜索能力強，魯棒性好，在解決多目標優(yōu)化問題的研究領(lǐng)域內(nèi)應(yīng)用廣泛且效果顯著。故本文采用遺傳算法對模型進行求解。

4.1 多目標問題轉(zhuǎn)化

給三個目標函數(shù)分別賦予目標相應(yīng)的權(quán)重值Wi(i=1,2,3)，權(quán)重越大表示目標函數(shù)的重要程度越大，因此多目標優(yōu)化問題可以表示為：

4.2 編 碼

編碼方式選擇自然數(shù)編碼。用自然數(shù)1,2,3…來代表貨位(x,y,z)，那么染色體的長度就與貨物的總數(shù)量一致。

4.3 種群初始化

初始化工作采用隨機方法產(chǎn)生種群規(guī)模K=100 的初始種群。

4.4 適應(yīng)度函數(shù)的確定

遺傳算法中采用適應(yīng)度函數(shù)來衡量個體的優(yōu)劣，適應(yīng)度值要求必須為負數(shù)，適應(yīng)度值較大的個體被認為是優(yōu)良的個體，所以適應(yīng)度值越大越好。遺傳算法經(jīng)常把目標函數(shù)作為適應(yīng)度函數(shù)，對于本文三個目標函數(shù)都是求全局最小值，而且都是非負數(shù)，那么可以直接取目標函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)。

為了防止函數(shù)值差值過大影響遺傳算法的性能，在進行倒數(shù)操作前，先將各目標函數(shù)去量綱處理，消除單位對數(shù)值的影響后再對目標函數(shù)求倒數(shù)來構(gòu)造適應(yīng)度函數(shù)。對目標函數(shù)線性變換處理，轉(zhuǎn)化為無量綱函數(shù)。

經(jīng)過線性變換后三個目標函數(shù)均映射到(0,1)區(qū)間，式中fi代表第i 個目標函數(shù)，原目標函數(shù)分布情況不會因為線性變換而改變，不會影響遺傳算法的性能。為了避免出現(xiàn)數(shù)據(jù)溢出的情況，在分母上加1 避免適應(yīng)度函數(shù)值趨向于無窮大。轉(zhuǎn)換后的適應(yīng)度函數(shù)表達式為：

4.5 選擇操作

選擇操作對初始種群的各個染色體進行評價，本文選擇輪盤賭選擇法，首先計算每個染色體得到適應(yīng)度值Fi和整個初始種群的適應(yīng)度總和；其次計算種群中每個染色體個體被選中的概率pi；然后按照次序計算每個染色體個體被選擇的累計概率；最后隨機生成一個介于0 到1 之間的隨機數(shù)R,依次與累計概率進行對比，如果滿足在累計概率范圍內(nèi)則被選中。即R＜P1，就選擇第一個個體，如果PK-1≤R≤PK,則選擇第K 個個體。

4.6 交叉算子

交叉操作是按照一定的方法交換染色體上的部分，從而得到兩個全新的個體。隨機從(0,1)之間生成一個數(shù)r，將這個數(shù)與交叉概率pc進行比較，pc一般取0.4 到0.99 之間，如果r≤pc就進行交叉運算，如果r＞pc則將兩個母代個體重新加入下一代的種群中。結(jié)合自然數(shù)編碼的編碼方式，本文選擇基于位置的交叉（Position-based Crossove）r。

5 基于Matlab 的模型求解和仿真分析

5.1 參數(shù)設(shè)定

本文對M 公司的倉儲信息系統(tǒng)中選擇某一區(qū)域進行采樣，經(jīng)過處理和計算得到重量和初始坐標等信息，為了方便研究，只提取貨架的部分區(qū)域，對此優(yōu)化區(qū)域的參數(shù)作一些假設(shè)，該貨架區(qū)域由4 排，5 列和8 層的貨架構(gòu)成，共160 個貨位，當前優(yōu)化區(qū)域有100 個貨品。立體倉庫貨架和堆垛機的基本參數(shù)、遺傳算法所需要的基本參數(shù)以及多目標模型的權(quán)重設(shè)置具體如表2 所示：

表2 仿真基本參數(shù)表

5.2 結(jié)果分析

為了驗證模型的有效性，對優(yōu)化前后的貨位分配布局和目標函數(shù)值進行對比，優(yōu)化前貨物分布圖如圖2 所示。

圖2 初始貨物分布圖

優(yōu)化后的貨位分配情況如圖3 所示。

圖3 優(yōu)化后貨位分配模擬圖

目標函數(shù)由三個子函數(shù)構(gòu)成，每個子函數(shù)的權(quán)重都會直接影響最終的優(yōu)化效果，權(quán)重的大小可以根據(jù)企業(yè)對于目標函數(shù)體現(xiàn)的存儲策略的側(cè)重程度靈活調(diào)整，在三個權(quán)重分別為0.4、0.3 和0.3 時貨位分配結(jié)果合理，模型運行結(jié)果如圖4 所示。

圖4 優(yōu)化算法迭代曲線圖

將優(yōu)化前后三個目標函數(shù)值及加權(quán)結(jié)果進行對比，結(jié)果如表3 所示。

由表3 可知，三個目標函數(shù)經(jīng)過優(yōu)化后都有不同程度的降低，三個目標函數(shù)的降低比率分別為15.83%,50.24%和100%，加權(quán)后的目標函數(shù)值降低比率達到50.21%。

表3 優(yōu)化效果對比表

對子目標的權(quán)重進行調(diào)整，觀察權(quán)重對于優(yōu)化結(jié)果的影響程度。倉儲貨品重量普遍較大的企業(yè)較之于貨品重量普遍較輕的企業(yè)，在存儲策略上往往在注重提高存取效率的前提下同樣非常重視貨架穩(wěn)定性，因此將目標函數(shù)f1的權(quán)重保持不變，目標函數(shù)f2的權(quán)重提高0.1 之后重新運行，最終模型得出的優(yōu)化結(jié)果如表4 所示。

表4 重設(shè)權(quán)重后的優(yōu)化效果對比表

由表4 可以看出，再對目標函數(shù)的權(quán)重進行略微調(diào)整之后，總體優(yōu)化效果依然超過了50%，優(yōu)化效果顯著。

實際應(yīng)用中部分立體倉庫對于貨架穩(wěn)定性的要求不高，例如蔬果類乳品類企業(yè)會更加追求存取效率上的優(yōu)化提升，出于對比目的以便觀察目標函數(shù)（1）的權(quán)重對于優(yōu)化效果的影響，再次對子目標的權(quán)重進行調(diào)整，當三個目標函數(shù)的權(quán)重分別為0.5、0.3 和0.2 時，模型運行結(jié)果如表5 所示：

表5 二次調(diào)整權(quán)重后的優(yōu)化效果對比表

由表5 數(shù)據(jù)可以發(fā)現(xiàn)，再次微調(diào)權(quán)重后的運行結(jié)果有略微變化，優(yōu)化效果相比前文兩種權(quán)重配比變化不大，模型的優(yōu)化效果仍然比較顯著，說明優(yōu)化模型依舊充分發(fā)揮作用，起到了較明顯的優(yōu)化效果。

6 結(jié)論與展望

本文通過對某食品企業(yè)M 公司自動化立體倉庫作業(yè)案例的考察，建立多目標優(yōu)化的數(shù)學(xué)模型并以真實數(shù)據(jù)進行Matlab 仿真研究，優(yōu)化結(jié)果表明該模型可以提高存取效率以及貨架穩(wěn)定性，除此以外還能有效解決巷道工作量均衡的問題，以加權(quán)后的目標函數(shù)值為例，試用三種不同比例的權(quán)重分配模擬不同類型企業(yè)在存儲策略上可能做出的微調(diào)，模型運行結(jié)果比較穩(wěn)定，加權(quán)后的目標函數(shù)值平均降低比率為50.23%，說明此優(yōu)化模型在常規(guī)權(quán)重設(shè)置的條件下能夠達到50%左右的優(yōu)化效果，對于不同存儲策略的單元貨格式自動化立體倉庫都可以發(fā)揮出實際應(yīng)用價值。

本文是基于我國目前廣泛應(yīng)用的單元或格式立體倉庫，隨著技術(shù)與設(shè)備的更新升級，像雙深位立體倉等新式立體倉不斷出現(xiàn)，也為該領(lǐng)域的研究開辟了新的疆土。另一方面，一些對模型的簡化所作的假設(shè)會對實際運行效果產(chǎn)生不同程度的影響，此方面仍有改善的空間，將作為今后進一步研究的方向。