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

徐偉華 沈文喆 巫仁亮 張婷

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

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

中圖分類(lèi)號(hào)：F406.5文獻(xiàn)標(biāo)識(shí)碼：A

0引言

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

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

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

1模型建立

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

1.2符號(hào)說(shuō)明（見(jiàn)表1）：

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

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

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

（2）1i

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

其中：約束條件式（2）、式（3）表示根據(jù)第i種貨物托盤(pán)的數(shù)量考慮貨位分配的各個(gè)貨位域;式（4）、式（5）、式（6）表示堆垛機(jī)的運(yùn)行時(shí)間、速度與距離之間的關(guān)系;式（7）表示目標(biāo)函數(shù)中的各個(gè)貨位的時(shí)間的取值;式（8）表示第i種類(lèi)的貨物托盤(pán)的個(gè)數(shù)與密集型貨格列貨位數(shù)之間的關(guān)系，是第i種類(lèi)的貨物托盤(pán)數(shù)分解成密集型貨格列貨位數(shù)的整數(shù)倍部分和剩余的小于密集型貨格列貨位數(shù)的部分;式（9）表示第i種貨物托盤(pán)除密集型貨格列整數(shù)倍外的余數(shù)部分取值范圍;式（10）表示第i種類(lèi)的貨物托盤(pán)的余數(shù)部分存儲(chǔ)在某密集型貨格列中的個(gè)數(shù);式（11）表示當(dāng)?shù)趇種貨物托盤(pán)存儲(chǔ)進(jìn)某貨位，當(dāng)該部分的貨物托盤(pán)的數(shù)量等于1時(shí)，表示不需要搬運(yùn)穿梭板，取值為O，當(dāng)該部分的貨物托盤(pán)的數(shù)量大于1，小于密集型貨格列貨位數(shù)s時(shí)，需要搬運(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)個(gè)體適應(yīng)度都小于等于父代最優(yōu)個(gè)體的適應(yīng)度時(shí)可以終止運(yùn)算。當(dāng)組中結(jié)果趨于平緩，迭代可能達(dá)到算法設(shè)定的迭代次數(shù)而停止，也可能迭代到第n次時(shí)，所得到的結(jié)果與第n-1代的結(jié)果相差較小時(shí)，即△F=（F_n-F_n-1）/F_n，當(dāng)△F=0.5時(shí)，此時(shí)也可認(rèn)定迭代停止，終止運(yùn)算。

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

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

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

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

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

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

3結(jié)論

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