基于遺傳算法的自動化立體倉庫貨物配載研究

姚琪， 周樂， 陳寶生， 何明凱

(國網(wǎng)吳忠供電公司，寧夏 吳忠 751100)

?

基于遺傳算法的自動化立體倉庫貨物配載研究

姚琪， 周樂， 陳寶生， 何明凱

(國網(wǎng)吳忠供電公司，寧夏 吳忠 751100)

針對自動化立體倉庫貨物倉位的配載問題建立了一個(gè)多目標(biāo)數(shù)學(xué)模型。首先根據(jù)立體倉庫貨位分配的原則與策略建立合理的貨架重心模型與目標(biāo)函數(shù)，其次根據(jù)貨物出/入庫的高效性建立貨物存取效率最優(yōu)模型。采用基于種群操作的遺傳算法求解最優(yōu)配載結(jié)果，通過優(yōu)化遺傳算法，并利用MATLAB程序設(shè)計(jì)對實(shí)際貨架的貨位分配仿真實(shí)例進(jìn)行計(jì)算求解。結(jié)果表明：采用改進(jìn)的遺傳算法對貨位進(jìn)行優(yōu)化分配，可降低貨架的重心目標(biāo)函數(shù)值及堆垛機(jī)訪問時(shí)間目標(biāo)值，增強(qiáng)了貨架的穩(wěn)定性，提升了堆垛機(jī)的效率，有效的提高倉庫性能。

自動化立體倉庫；貨位分配；多目標(biāo)優(yōu)化；遺傳算法；MATLAB仿真

0 引 言

自動化立體倉庫(AS/RS)是現(xiàn)代物流系統(tǒng)中迅速發(fā)展的一個(gè)重要組成部分。如何合理規(guī)劃和設(shè)計(jì)自動化倉庫，實(shí)現(xiàn)自動化倉庫的高效運(yùn)行，已經(jīng)成為重要的研究課題，是自動化立體倉庫中貨物分配方面首先需要考慮的問題。

自動化立體倉庫的效率主要取決于庫區(qū)和貨位的分配策略，良好的優(yōu)化策略可以大大提高貨物周轉(zhuǎn)效率，方便盤點(diǎn)及移庫。貨位分配制約著立體倉庫的整體性能的提升，研究貨位分配算法具有重要的意義[2]。

本文結(jié)合立體倉庫的構(gòu)造模型，根據(jù)貨位分配的原則和策略建立了合理的貨位分配數(shù)學(xué)模型，重點(diǎn)研究遺傳算法在貨物分配中的使用。利用遺傳算法進(jìn)行多目標(biāo)優(yōu)化求解，得到貨物分配的方法。

1 自動化立體倉庫

1.1 立體倉庫的組成結(jié)構(gòu)

自動化立體倉庫(AS/RS)是由立體貨架、有軌巷道堆垛機(jī)、出入庫托盤輸送機(jī)系統(tǒng)、尺寸檢測條碼閱讀系統(tǒng)、通訊系統(tǒng)、自動控制系統(tǒng)、計(jì)算機(jī)監(jiān)控系統(tǒng)、計(jì)算機(jī)管理系統(tǒng)以及其他如電線電纜橋架配電柜、托盤、調(diào)節(jié)平臺、鋼結(jié)構(gòu)平臺等輔助設(shè)備組成的復(fù)雜的自動化系統(tǒng)[3]。典型的自動化立體倉庫結(jié)構(gòu)圖如圖1所示。

圖1 典型的自動化立體倉庫結(jié)構(gòu)圖

1.2 立體倉庫貨位分配原則與策略

自動化立體倉庫貨位分配主要考慮的因素有貨架的穩(wěn)定性、貨物出入庫的效率、保證貨物的質(zhì)量、安全經(jīng)濟(jì)等。在倉儲管理中，首先要保證立體倉庫的穩(wěn)定性，其次，充分發(fā)揮倉儲設(shè)施和設(shè)備的作用，可以提高倉儲設(shè)施的勞動生產(chǎn)率。一般來說，貨位分配需要遵循以下的幾個(gè)原則[4]：貨架受力均勻和穩(wěn)定性原則；分巷道存放原則；就近出/入庫原則；產(chǎn)品相關(guān)性原則；先入先出原則。

2 系統(tǒng)數(shù)學(xué)模型建立

2.1 系統(tǒng)參數(shù)

自動化立體倉庫系統(tǒng)由模擬立體倉庫和出入庫輸送設(shè)備組成[5-6]。立體倉庫為4層×6列立體貨架，倉位編碼規(guī)定：從左到右，從下到上。相關(guān)參數(shù)如表1所示。

表1 自動化立體倉庫的相關(guān)參數(shù)

2.2 數(shù)學(xué)模型

圖2 實(shí)際貨位與數(shù)學(xué)坐標(biāo)對照示意圖

假設(shè)某個(gè)貨架一共有p層q列，將距離出、入庫最近的列記為第一列，最低層設(shè)為第一層，將處于第i列第j層的貨位坐標(biāo)記為(i,j),i=1,2,3,…,q；j=1,2,3,…,p。設(shè)每個(gè)貨位的長記為L，每個(gè)貨位的高記為H。在圖2中，虛線的交點(diǎn)對應(yīng)著每一個(gè)貨位的幾何重心。設(shè)堆垛機(jī)的水平運(yùn)行速度為VX,垂直速度設(shè)為VY。VX、VY分別為各自運(yùn)行方向上單位長度(垂直方向?yàn)镠，水平方向?yàn)長)與單位運(yùn)行時(shí)間之比。

立體倉庫貨位分配的關(guān)鍵有兩方面：一是貨架的安全性，其受力的均勻性與穩(wěn)定性；二是出/入庫的時(shí)間能夠盡量縮短，貨物出/入庫的效率要高。從這兩個(gè)方面出發(fā)來建立立體倉庫貨位數(shù)學(xué)模型[7]。

3 倉庫模型建立與求解

3.1 建立貨架的重心穩(wěn)定模型

對于任意貨位，虛線位置是其幾何重心，易得到對于貨位(i,j)重心位置為((i﹣0.5)L,(j﹣0.5)H)。整個(gè)貨架的重心坐標(biāo)可以表示為：

(1)

其中Gij是相應(yīng)貨位上貨物的重量，Gx為重心X軸坐標(biāo)，GY為重心Y軸坐標(biāo)。

為了滿足貨架的穩(wěn)定性，在垂直方向上要求重心不能太高，即重心Y坐標(biāo)要盡量小，從水平方向上要求重心X坐標(biāo)盡量落在貨架幾何中軸線，于是建立重心穩(wěn)定數(shù)學(xué)模型如公式(2)、(3)所示：

(2)

(3)

由式(2)、(3)可見，貨架重心模型包含了兩個(gè)目標(biāo)函數(shù)，為了簡化，通過權(quán)衡重心X坐標(biāo)和Y坐標(biāo)對整個(gè)貨架穩(wěn)定的重要性，分別賦予公式(2)、(3)一個(gè)加權(quán)因子，可得公式(4)：

(4)

3.2 建立存取效率最優(yōu)模型

為了建立存取效率最優(yōu)模型，做以下假設(shè)[8-9]：

① 所涉及的貨物種類，出/入庫頻率已知；

② 假設(shè)其出/入庫站臺在貨架的同一端。

由于存取貨物所花費(fèi)的總時(shí)間是所有貨物的訪問時(shí)間之和，設(shè)位于(i,j)的貨物出入庫頻率為fij，每次取該貨物所花費(fèi)的時(shí)間為tij，令eij=fij×tij，可得存取所費(fèi)時(shí)間的數(shù)學(xué)模型為：

(5)

其中tij為堆垛機(jī)從(0，0)處移動到(i,j)處的時(shí)間，且有：

(6)

綜上所述可知，貨物分配的數(shù)學(xué)模型由式(4)和式(5)組成。

3.3 遺傳算法求解模型

本文選擇遺傳算法作為求解貨位分配優(yōu)化問題的算法[10-11]。通過修正遺傳算法使其應(yīng)用于貨位分配建模的求解[12]，具體步驟如下：

(2) 改進(jìn)交叉策略:對于p層q列的貨架，一共有p×q個(gè)貨位，所以貨物編號從1號到p×q號。為了克服種群只在單一目標(biāo)上進(jìn)化，必須引入限制交叉策略。

圖3 限制交叉策略流程圖

首先初始化一個(gè)數(shù)目為N的群體P(t)，將其分為兩個(gè)種群，個(gè)數(shù)都為2/N個(gè)，分別使用改進(jìn)的重心選擇操作數(shù)和改進(jìn)的效率選擇操作數(shù)作用于兩個(gè)群體，對得到的兩個(gè)下一代子種群設(shè)定不同的標(biāo)簽，禁止子種群內(nèi)部進(jìn)行交叉，讓這兩個(gè)子種群之間進(jìn)行兩兩隨機(jī)配對，具體流程如圖3所示。

4 遺傳算法貨位分配仿真實(shí)例

4.1 仿真實(shí)例

立體倉庫貨架為4層6列的形式。其中貨架長L=0.18 m，高度H=0.12 m。堆垛機(jī)的運(yùn)動參數(shù)為VX=0.5 m/s，VY=0.5 m/s(所用為最大速度)。為了使模型理想化，設(shè)堆垛機(jī)的加速、減速耗時(shí)為0。對貨叉伸縮所耗時(shí)間忽略不計(jì)。貨架的貨位編號如表2所示。未經(jīng)優(yōu)化前，將貨物放入與之編號一樣的貨位中。

表2 立體倉庫貨位編號

假設(shè)待存入的24件托盤貨物的質(zhì)量和出入庫頻率表及其貨物編號如表3所示。

表3 托盤貨物的質(zhì)量和出入庫頻率

4.2 仿真求解

根據(jù)之前算法的研究，可得出具體操作過程如下：

(1) 編碼：根據(jù)貨位的特點(diǎn)，首先建立一個(gè)4*6的矩陣，如果矩陣的第i行第j列位置的元素為m，則表示編號為m的貨物放在貨架的第(p+1-i)層第j列上。

(2) 確定適應(yīng)度評價(jià)方法：由式(4)，(5)知該函數(shù)的優(yōu)化目標(biāo)是要求解函數(shù)的最小值，因此函數(shù)的值越大其遺傳到下一代的概率應(yīng)該越小，故設(shè)計(jì)適應(yīng)度函數(shù)如公式(7)、(8)所示：

(7)

(8)

式中fg對應(yīng)于貨架重心位置的適應(yīng)度，fe對應(yīng)于存取效率的適應(yīng)度；G和E是個(gè)體對應(yīng)的子函數(shù)目標(biāo)值，Gmax和Emax是進(jìn)化到最近若干代中目標(biāo)函數(shù)的最大值。

(4) 相關(guān)參數(shù)設(shè)定：① 壓力操作數(shù)μ取0.25。② 按照流程，選擇N/2個(gè)染色體用于交叉操作，N(種群個(gè)數(shù))取100。③ 交叉運(yùn)算中取pc=0.4～0.99。 ④變異概率取0.001～0.1。⑤最大進(jìn)化代數(shù)T=20～100。

(5) 算法結(jié)束后，根據(jù)最終得到的群體，繼續(xù)計(jì)算每個(gè)染色體所對應(yīng)的兩個(gè)目標(biāo)函數(shù)值，通過比較選擇兩方面性能都較優(yōu)的染色體作為最優(yōu)解。

4.3 仿真結(jié)果分析

編寫MATLAB程序進(jìn)行仿真，初始化種群數(shù)目為100，最大進(jìn)化代數(shù)100，交叉概率0.9，變異概率為0.099。依據(jù)上述算法進(jìn)行編程求解，最終得出相應(yīng)的仿真結(jié)果。

以2號個(gè)體為例，在優(yōu)化前，其經(jīng)過隨機(jī)貨物分配后貨物擺放情況如下：

進(jìn)化后貨物分配情況則為：

再分別任意選用59號、88號、93號參與運(yùn)算，也將分別得出其優(yōu)化后的重心目標(biāo)函數(shù)值和效率目標(biāo)函數(shù)值。則優(yōu)化前后目標(biāo)函數(shù)值對比情況如表4所示。

表4 優(yōu)化前后目標(biāo)函數(shù)值對比

用59號72號93號個(gè)體參與運(yùn)算時(shí)，優(yōu)化后相應(yīng)的貨物分配方案分別如下所示：

結(jié)合表3、4中的數(shù)據(jù)可以得出：采用改進(jìn)的遺傳算法后，貨架的重心目標(biāo)函數(shù)值降低，貨架的穩(wěn)定性增強(qiáng)；同時(shí)，堆垛機(jī)的訪問時(shí)間目標(biāo)值降低了，堆垛機(jī)的效率得到了提升。由此可見，使用改進(jìn)的遺傳算法對貨位進(jìn)行優(yōu)化分配可以取得較好的效果。

5 結(jié)束語

結(jié)合立體倉庫的構(gòu)造模型，根據(jù)立體倉庫貨位分配的幾種原則與策略建立了合理的貨位分配數(shù)學(xué)模型，運(yùn)用遺傳算法求解多目標(biāo)函數(shù)的最優(yōu)解。使用基于Pareto最優(yōu)解的改進(jìn)遺傳算法進(jìn)行算法設(shè)計(jì)，并使用MATLAB語言進(jìn)行程序設(shè)計(jì)，對實(shí)際一個(gè)4*6(即4層6列貨架)貨架的貨位分配進(jìn)行仿真計(jì)算。通過對比優(yōu)化前后倉庫的性能發(fā)現(xiàn)，其算法可降低貨架的重心目標(biāo)函數(shù)值及堆垛機(jī)訪問時(shí)間目標(biāo)值，增強(qiáng)了貨架的穩(wěn)定性，提升了堆垛機(jī)的效率，倉庫的性能得到了有效的提升。

[1] 陳月婷,何芳.基于遺傳算法的自動化立體倉庫的貨位優(yōu)化分配[J].物流科技, 2008,32(1):2-5.

[2] 張建奇,李墨翰,張建鋒.自動化立體倉庫控制系統(tǒng)設(shè)計(jì)[J].自動化儀表,2012,56(1):24-28.

[3] 陳月婷,何芳.基于改進(jìn)粒子群算法的立體倉庫貨位分配優(yōu)化[J].計(jì)算機(jī)工程與應(yīng)用,2008,45(11):35-39.

[4] 王強(qiáng).基于遺傳算法的自動化立體倉庫出入庫貨位分配優(yōu)化研究[J].物流工程與管理,2012,34(3):11-16.

[5] 陳厚孫.自動化立體倉庫出入庫貨位分配優(yōu)化研究[D].湖北:武漢大學(xué),2011.

[6] 孫嘉煒.立體倉庫出入庫貨位優(yōu)化模型與算法研究[D].沈陽:東北大學(xué),2013.

[7] 馬清悅,張紀(jì)會,宋曉鵬,等. 基于啟發(fā)式算法的自動化立體倉庫揀貨路徑優(yōu)化研究[J].青島大學(xué)學(xué)報(bào),2012,27(3):34-39.

[8] RAO S S,ADIL G K．A mathematical model for optimal partitions of warehouse storage space based on turnover density.[J].Proceedings of the 5thAsia Modelling Symposium,2011(3):24-29.

[9] KOFLER M．Modeling and optimizing storage assignment in a steel slab yard[J].Proceedings of the 4thIEEE International Symposium on Logistics and Industrial Informatics, 2011(6):46-51.

[10] 張學(xué)敏,張航.基于改進(jìn)蟻群算法的最短路徑問題研究[J].控制理論與應(yīng)用,2009,7(28):35-39.

[11] 熊芳敏，芩宇森，曾碧卿. 運(yùn)用蟻群算法解決物流中心揀貨路徑問題[J].華南師范大學(xué)學(xué)報(bào),2010,55(2):56-61.

[12] 龐龍, 陸金桂. 基于蟻群遺傳算法的自動化立體倉庫揀選路徑優(yōu)化[J].計(jì)算機(jī)工程與科學(xué),2012,40(3):45-50.

Research on Cargo Stowage in the Automatic Stereoscopic Warehouse Based on Genetic Algorithm

Yao Qi，Zhou Le，Chen Baosheng，He Mingkai

(State Grid Wuzhong Power Supply Company, Wuzhong, Ningxia 751100, China)

With respect to cargo position stowage in the automatic stereoscopic warehouse, we build up a multi-objective mathematical model. First, we establish a reasonable model for the shelf gravity center and objective function according to the principle and strategy of position assignment in the stereoscopic warehouse. Second, we establish a model for optimal goods access efficiency in the principle of high in and out-warehousing efficiency. An optimal stowage result is achieved by means of genetic algorithm based on population operation. Through optimization of genetic algorithm and Matlab programming, we calculate simulation examples for position assignment in actual shelve. The results show that by adopting the improved genetic algorithm to optimize the allocation of cargo space, we can reduce the objective function value of the gravity center of the shelves as well as the target value of stacker access time, thus enhancing shelf stability, raising stacker efficiency and improving warehouse performance.

automatic stereoscopic warehouse; storage allocation; multi-objective optimization;genetic algorithm; MATLAB simulation

10.3969/j.issn.1000-3886.2016.04.015

TP273

A

1000-3886(2016)04-0045-04

姚琪(1986-)，男，寧夏吳忠人，中級工程師，工學(xué)碩士學(xué)位，主要從事電力系統(tǒng)自動化工作，研究方向電力系統(tǒng)保護(hù)與自動控制。 周樂(1990-)，男，寧夏吳忠人，助理工程師，工學(xué)學(xué)士學(xué)位，主要從事電力系統(tǒng)自動化工作，研究方向電力系統(tǒng)保護(hù)與自動控制。 陳寶生(1986-)，男，遼寧阜新人，高級技師，工學(xué)雙學(xué)士學(xué)位，主要從事電力系統(tǒng)自動化工作，研究方向自動控制與應(yīng)用。 何明凱(1987-)，男，寧夏鹽池人，技師，工學(xué)學(xué)士學(xué)位，主要從事電氣自動化工作，研究方向自動控制。

定稿日期: 2015-12-30