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

徐偉華 沈文喆 巫仁亮 張婷

摘要：密集型自動化立體倉庫是由在貨架軌道上行走的穿梭板與堆垛機(jī)配合作業(yè)。而影響其系統(tǒng)效率的主要因素是堆垛機(jī)要搬運(yùn)穿梭板。文章研究了倉庫中貨物訂單的最優(yōu)貨位分配與出入庫作業(yè)次序。在研究基礎(chǔ)上建立數(shù)學(xué)模型，運(yùn)用遺傳算法以及MATLAB軟件對模型求解并得出數(shù)據(jù)。用FLEXSIM仿真軟件建立某企業(yè)倉庫1：1實(shí)體模型，先得出優(yōu)化前數(shù)據(jù)，然后對模型優(yōu)化得出優(yōu)化后數(shù)據(jù)。將優(yōu)化前數(shù)據(jù)與求解數(shù)據(jù)和優(yōu)化后數(shù)據(jù)進(jìn)行對比，發(fā)現(xiàn)堆垛機(jī)搬運(yùn)穿梭板的次數(shù)減少了30%，運(yùn)行效率提高了10.4%，且求解數(shù)據(jù)和優(yōu)化后數(shù)據(jù)結(jié)果誤差較小。

關(guān)鍵詞：密集型自動化立體倉庫;貨位分配;遺傳算法

中圖分類號：F406.5文獻(xiàn)標(biāo)識碼：A

0引言

隨著時代的發(fā)展，企業(yè)開始逐漸認(rèn)識到了自動化立體倉庫所帶來的競爭優(yōu)勢。在現(xiàn)如今由穿梭板式貨架、穿梭板、堆垛機(jī)以及輸送裝置組成的密集型存儲系統(tǒng)，在一定投資范圍內(nèi)使得立體倉庫存儲空間增加，提高自動化立體倉庫的存儲密度。國內(nèi)外對自動化立體倉庫貨位分配的研究文獻(xiàn)自1993年開始，2001年，S.Hsieh提出一種基于BOM的自動化立體倉庫貨位分配方法，強(qiáng)調(diào)將貨物先分類，再存儲的策略，并結(jié)合算例驗(yàn)證了該方法的有效性。2006年，Byung等為倉庫的貨位依據(jù)周轉(zhuǎn)率的高低設(shè)定了分區(qū)，高周轉(zhuǎn)率庫區(qū)在出入庫站臺附近，低周轉(zhuǎn)率庫區(qū)距離出入庫站臺較遠(yuǎn)。2007年，朱從民、王衛(wèi)青等詳述了自動穿梭板的設(shè)計及其自動穿梭板的工作方式，為穿梭板應(yīng)用在自動化立體倉庫中奠定了基礎(chǔ)。2011年，Kov6cs A提出了一種MIP模型，用于尋找基于分類的存儲貨位分配策略，它可以最小化訂單周期時間，平均采購工作量或者2個標(biāo)準(zhǔn)的線性組合。2014年，Chuang等首先通過網(wǎng)站統(tǒng)計數(shù)據(jù)與關(guān)聯(lián)規(guī)則挖掘研究了產(chǎn)品類別間的相對強(qiáng)度，然后按類分配。2017年，楊驍?shù)韧ㄟ^分析穿梭式自動化立體倉庫系統(tǒng)的各個設(shè)備的特點(diǎn)及其調(diào)度作業(yè)特點(diǎn)，提出穿梭式自動化立體倉庫的出入庫調(diào)度策略，通過對穿梭板和堆垛機(jī)的調(diào)度運(yùn)行時間的分析對所提出的策略進(jìn)行合理驗(yàn)證，通過數(shù)據(jù)的支撐證明所提出的策略的優(yōu)化性。國內(nèi)外學(xué)者對密集型自動化立體倉庫的研究多集中在貨位分配方法上，對于貨位分配優(yōu)化問題研究相對較少。

本文以某企業(yè)“堆垛機(jī)加穿梭板”式密集型立體倉庫為基礎(chǔ)進(jìn)行研究，該倉庫具體布局圖如圖1所示：

以優(yōu)化貨位分配為目標(biāo)，建立數(shù)學(xué)模型，減少堆垛機(jī)搬運(yùn)穿梭板次數(shù)。

1模型建立

1.1問題描述。密集型自動化立體倉庫貨架由n個貨架區(qū)組成，密集型貨架最外側(cè)均為單排貨架區(qū)，用來存儲零散的貨物托盤，中間由任意組S排單排貨架緊密排列在一起組成P組密集型貨架組。密集型自動化立體倉庫中各個貨位尺寸相同，承載的貨物托盤以及各個穿梭板大小相同;堆垛機(jī)在水平方向做勻速運(yùn)動，豎直方向做初速度為0的加速運(yùn)動，穿梭板在貨架軌道上做勻加速直線往復(fù)運(yùn)動，堆垛機(jī)和穿梭板作業(yè)的速度、加速度已知;在該密集型自動化立體倉庫中貨位的位置、存儲的物料種類、頻率以及穿梭板所在的位置均是已知的;密集型貨架的每一個密集貨格列中，存儲的貨物種類是一樣的。

1.2符號說明（見表1）：

1.3模型分析。在單排貨架區(qū)O，n上的貨物托盤的分配作業(yè)中，不需要堆垛機(jī)搬運(yùn)穿梭板;在密集型貨架區(qū)1，2，…，n-l中，需要堆垛機(jī)搬運(yùn)穿梭板，將某一時刻的某種類出入庫的任務(wù)訂單個數(shù)M以密集型貨格列的貨位數(shù)s進(jìn)行分解，即M=n_is+c_in_i，進(jìn)行如下工況分析：

工況一：當(dāng)M_i=1時，此時出入庫第i種貨物托盤的臺數(shù)數(shù)量較少，可以選擇貨架系統(tǒng)的單排貨架，或者密集型貨架組中存儲該類貨物托盤的近巷道的密集型貨位;上述兩種情況是基于不用堆垛機(jī)搬運(yùn)穿梭板的情況下進(jìn)行的貨位分配，搬運(yùn)穿梭板的次數(shù)為O;

工況二：當(dāng)M_i>s時，將M_i以密集型貨架組的貨格列中的總貨位數(shù)s為單元進(jìn)行分解，即M=n_is+C_i;其中：（1）n_i≥1：這種情況下的出入庫作業(yè)的貨位分配，以密集型貨架組的貨格列為全空或者全實(shí)為出入庫作業(yè)的貨位研究對象，建立貨位分配模型時將該種類的全空或者全實(shí)貨物托盤簡化成第i種類有n_i個貨物托盤進(jìn)行出入庫作業(yè)，將密集型貨格列簡化成單排貨架的形式，第i種貨物托盤的出入庫貨位分配的托盤個數(shù)為密集型貨格列貨位總數(shù)的整數(shù)部分，即選定某一密集型貨格列存儲該種類貨物托盤，堆垛機(jī)從站臺至該貨位需要搬運(yùn)s次，由此對該種貨物托盤的頻次和存儲該種類的密集型貨格列的位置與堆垛機(jī)搬運(yùn)托盤次數(shù)的乘積之和求最小。

（2）1i

1.4建立模型。根據(jù)上述分析建立密集型自動化立體倉庫的貨位分配模型目標(biāo)函數(shù)：

其中：約束條件式（2）、式（3）表示根據(jù)第i種貨物托盤的數(shù)量考慮貨位分配的各個貨位域;式（4）、式（5）、式（6）表示堆垛機(jī)的運(yùn)行時間、速度與距離之間的關(guān)系;式（7）表示目標(biāo)函數(shù)中的各個貨位的時間的取值;式（8）表示第i種類的貨物托盤的個數(shù)與密集型貨格列貨位數(shù)之間的關(guān)系，是第i種類的貨物托盤數(shù)分解成密集型貨格列貨位數(shù)的整數(shù)倍部分和剩余的小于密集型貨格列貨位數(shù)的部分;式（9）表示第i種貨物托盤除密集型貨格列整數(shù)倍外的余數(shù)部分取值范圍;式（10）表示第i種類的貨物托盤的余數(shù)部分存儲在某密集型貨格列中的個數(shù);式（11）表示當(dāng)?shù)趇種貨物托盤存儲進(jìn)某貨位，當(dāng)該部分的貨物托盤的數(shù)量等于1時，表示不需要搬運(yùn)穿梭板，取值為O，當(dāng)該部分的貨物托盤的數(shù)量大于1，小于密集型貨格列貨位數(shù)s時，需要搬運(yùn)穿梭板，取值為1。

2遺傳算法與仿真實(shí)例驗(yàn)證

運(yùn)用遺傳算法求解，取種群規(guī)模為250，選擇算例貨架區(qū)中的貨位作為本研究的初始解，選取變異概率為P_m=0.05，交叉概率取P_n=0.8。當(dāng)連續(xù)Ⅳ代子代種群的最優(yōu)個體適應(yīng)度都小于等于父代最優(yōu)個體的適應(yīng)度時可以終止運(yùn)算。當(dāng)組中結(jié)果趨于平緩，迭代可能達(dá)到算法設(shè)定的迭代次數(shù)而停止，也可能迭代到第n次時，所得到的結(jié)果與第n-1代的結(jié)果相差較小時，即△F=（F_n-F_n-1）/F_n，當(dāng)△F=0.5時，此時也可認(rèn)定迭代停止，終止運(yùn)算。

利用MATLAB軟件對密集型自動化立體倉庫的貨位優(yōu)化模型進(jìn)行遺傳算法求解，將預(yù)先設(shè)定好的參數(shù)（見表2）代入目標(biāo)函數(shù)。

隨著迭代次數(shù)的增加，適應(yīng)度值在減小，當(dāng)?shù)螖?shù)達(dá)到230次，適應(yīng)度函數(shù)的值基本趨于穩(wěn)定，取迭代到232次時的最優(yōu)適應(yīng)度值為57.12min，完成訂單搬運(yùn)穿梭板的次數(shù)為7次。數(shù)據(jù)計算統(tǒng)計結(jié)果如表3所示：

以某卷煙廠密集型自動化立體倉庫的貨物托盤的存取為例，該密集型自動化立體倉庫同本文研究的密集型自動化立體庫貨架結(jié)構(gòu)相一致，抽取80條出入庫貨物托盤的訂單任務(wù)。

根據(jù)卷煙廠密集型自動化立體倉庫的實(shí)體模型，使用Flexsim仿真軟件建立1：1的實(shí)體模型，并按照該卷煙廠密集型自動化立體倉庫的出入庫作業(yè)流程進(jìn)行實(shí)體連接。按照密集型自動化立體倉庫的運(yùn)作流程，對實(shí)體參數(shù)進(jìn)行設(shè)置，通過Flexsim的dbopen（）函數(shù)連接編程數(shù)據(jù)庫，通過dbsqlquery（）函數(shù)編寫執(zhí)行sql語句，以數(shù)據(jù)庫中的貨位信息表和出入庫作業(yè)表作為輸入進(jìn)行仿真。對模型進(jìn)行調(diào)試運(yùn)行后，基于目前該廠在密集型自動化立體倉庫的出入庫作業(yè)中使用的隨機(jī)貨位分配策略對80條出入庫作業(yè)任務(wù)進(jìn)行仿真模擬運(yùn)行。在對數(shù)據(jù)進(jìn)行總結(jié)的時候，取不同時間段作業(yè)的平均值，選擇適中的一組仿真統(tǒng)計輸出數(shù)據(jù)。依據(jù)仿真數(shù)據(jù)對該卷煙廠密集型自動化立體倉庫的堆垛機(jī)搬運(yùn)穿梭板的次數(shù)以及貨物托盤的出入庫過程中堆垛機(jī)搬運(yùn)貨物托盤的出入庫時間等進(jìn)行計算統(tǒng)計如表4所示：

將本文優(yōu)化后的貨位分配方案輸入仿真模型，運(yùn)行后輸出仿真結(jié)果。在對數(shù)據(jù)進(jìn)行總結(jié)的時候，取不同時間段作業(yè)的平均值，選擇適中的一組仿真統(tǒng)計輸出數(shù)據(jù)。依據(jù)仿真數(shù)據(jù)對密集型自動化立體倉庫的堆垛機(jī)搬運(yùn)穿梭板的次數(shù)以及貨物托盤的出入庫過程中堆垛機(jī)搬運(yùn)貨物托盤的出入庫時間等進(jìn)行計算統(tǒng)計如表5所示：

將得到的仿真結(jié)果與該卷煙廠原始作業(yè)的仿真結(jié)果進(jìn)行對比如表6所示：

3結(jié)論

與通過遺傳算法計算出的堆垛機(jī)作業(yè)時間相比較，仿真得到的結(jié)果偏大，兩者誤差約為0.77%，誤差較小。該卷煙廠采取的貨位分配策略與本文提出的貨位分配策略相比較，煙廠目前采用的貨位分配策略中堆垛機(jī)搬運(yùn)穿梭板的次數(shù)要較后者多，搬運(yùn)穿梭板次數(shù)減少了30%。本文提出的密集型自動化立體倉庫貨位分配優(yōu)化研究中，相較于該廠現(xiàn)有作業(yè)策略，堆垛機(jī)搬運(yùn)穿梭板次數(shù)減少了，堆垛機(jī)搬運(yùn)作業(yè)的總時間減少，堆垛機(jī)搬運(yùn)貨物托盤出入庫的效率提高了10.4%。