立體庫作業(yè)均衡及貨位優(yōu)化仿生算法研究

杜永華，項 前，呂志軍，陳 東

（1.東華大學(xué) 機械工程學(xué)院，上海 201620；2.上海精星物流設(shè)備有限公司，上海 201611）

立體庫作業(yè)均衡及貨位優(yōu)化仿生算法研究

杜永華1，項 前1，呂志軍1，陳 東2

（1.東華大學(xué) 機械工程學(xué)院，上海 201620；2.上海精星物流設(shè)備有限公司，上海 201611）

在批量訂單的情況下，為了提高自動化立體倉庫（AS/RS）的整體作業(yè)效率，提出了以堆垛

貨位優(yōu)化；作業(yè)均衡；作業(yè)效率；二進制粒子群算法；遺傳算法

0 引言

自動化立體倉庫（AS/RS）由于具有空間利用率較高、入出庫能力較大、管理較智能化等優(yōu)點，己成為現(xiàn)代企業(yè)生產(chǎn)管理中不可缺少的組成部分[2]。貨位分配是影響立體倉庫工作效率高低、揀選成本高低的一大主要因素，因此為了提高自動化立體庫的性能，對倉儲貨位優(yōu)化的研究越來越引起人們的重視。研究主要從兩方面展開，一方面從分配策略或貨位分區(qū)方面進行研究，文獻[3]給出一種基于BOM（Bill of Material）分類的貨位優(yōu)化方法；文獻[4]通過對產(chǎn)品頻度和偏離度的研究，來實現(xiàn)出入庫貨位的優(yōu)化；文獻[4～6]則運用分區(qū)的策略來實現(xiàn)貨位優(yōu)化。另一方面建立貨位優(yōu)化數(shù)學(xué)模型，主要通過仿生算法來對模型進行優(yōu)化求解，文獻[6,7]分別運用貪婪算法、非支配遺傳算法，以存儲能耗、貨架穩(wěn)定性、運行效率為目標對立體倉庫貨位分配進行優(yōu)化；文獻[8]以存耗低、運行時間短為目標，運用離散粒子群算法來實現(xiàn)立體庫貨位優(yōu)化。可以看出，上述貨位優(yōu)化研究大多集中在策略研究或者以路徑、能耗及時間為目標的優(yōu)化，但是在進行批量出入庫操作時，由于各巷道作業(yè)的不均衡容易造成一些堆垛機閑置或超負荷運作，從而導(dǎo)致揀選效率和揀選質(zhì)量的下降、資源的閑置，這顯然不能滿足批量作業(yè)的實際情況。另外，以上仿生算法的運用主要表現(xiàn)為遺傳算法（Genetic Algorithm，GA）與粒子群算法（Particle Swarm Optimization），對二進制粒子群算法（Binary Particle Swarm Optimization，BPSO）的運用較少。據(jù)此，在批量訂單操作中，本文提出了以堆垛機作業(yè)均衡以及工作效率高為目標的優(yōu)化模型，與標準遺傳算法比較，設(shè)計了一種基于二進制粒子群的模型求解仿生算法。

1 問題描述與數(shù)學(xué)模型

1.1 問題描述

所研究的貨位優(yōu)化問題可描述如下：在一個K排R層C列的儲存區(qū)（其簡易圖如圖1所示）進行批量出庫或者入庫操作，每張訂單中的貨物需要通過所處巷道堆垛機來實現(xiàn)出入庫，當堆垛機執(zhí)行完最后一個任務(wù)后返回到出入庫臺[9]。其中，每個巷道的堆垛機同時工作，堆垛機的工作效率通過其運行路徑來衡量，每個巷道堆垛機的作業(yè)均衡也由該巷道堆垛機的運行路徑來衡量。

圖1 儲存區(qū)簡易圖

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

任意一個貨位b均可用一個六元組（kb,rb,cb,Mb,Qb,Sb）表示，其中：（kb,rb,cb）表示貨位b的坐標即（排，層，列），Mb表示貨位b上所存貨物的品項號，Qb表示貨位b上所存貨物的數(shù)量，Sb表示貨位b的狀態(tài)（有四種狀態(tài)：任務(wù)完成、任務(wù)失敗、任務(wù)正在執(zhí)行、任務(wù)懸掛，默認的狀態(tài)是任務(wù)完成）。

每次任務(wù)T可用如下向量表示：

其中每張訂單中的一個品項表示一個任務(wù)Ti，j=（Md, Qd），Md表示所需貨物的品項號，Qd表示所需貨物的數(shù)量。

為了讓問題的復(fù)雜度降低，同時結(jié)合實際情況，做出如下模型假設(shè)：1）每次任務(wù)向量T都是單純的出庫或者入庫；2）倉庫里貨物的品項和數(shù)量能夠充分滿足訂單需求，且一個貨位只能滿足一個任務(wù)；3）堆垛機操作每個品項所用時間相等，且每趟只對一個目標儲位進行操作；4）每個儲位只能存放一個貨物單元（托盤或集裝箱）[11]，并且在作業(yè)之前對每個貨位的狀態(tài)（任務(wù)執(zhí)行完成、任務(wù)失敗、任務(wù)正在執(zhí)行、任務(wù)懸掛，默認每個貨位狀態(tài)都是任務(wù)執(zhí)行完成）、儲位上品項信息（品項、數(shù)量、規(guī)格等）已知。

以堆垛機作業(yè)行程均衡和運行效率為目標建立優(yōu)化模型，具體如下：

式中：i為巷道號，i = 1，2，…，I；Ni為巷道i中目標貨位的集合；N為倉庫中可行貨位（根據(jù)任務(wù)所需的品項并且貨位的狀態(tài)是任務(wù)完成來確定）的集合；K為倉庫中貨架總的排數(shù)；R為倉庫中每排貨架總的層數(shù)；C為倉庫中每排貨架總的列數(shù)；j為粒子位索引號，j = 1，2，…，J；Length（xj=1）表示粒子中粒子位為1的個數(shù)；Length（T）為任務(wù)向量中任務(wù)的的個數(shù)；Length（xi,j=1）表示粒子中粒子位所對應(yīng)的貨位號位于巷道i且該粒子位為1的個數(shù)；Length（Ti）為每個任務(wù)中的貨物品項號位于巷道i的任務(wù)個數(shù)S為各巷道工作行程的平均值；D為各個巷道工作行程的最大值；P為懲罰函數(shù)。

模型以最小化巷道工作行程（即最高的效率）以及各個巷道堆垛機工作量均衡為目標。約束(7)表示最后揀選的貨位數(shù)與任務(wù)數(shù)相等；約束(9)表示具體到每一個巷道的任務(wù)數(shù)和該巷道揀選的貨位數(shù)相等；懲罰系數(shù)(8)、(10)運用靜態(tài)懲罰函數(shù)的方法來處理約束(7)、(9)[13]，對于約束(7)、(9)將其違反程度分為2個等級，不同等級采用不同懲罰系數(shù)。

2 基于二進制粒子群算法的模型求解

因為動態(tài)貨位優(yōu)化是一個離散型優(yōu)化問題，所以適用于Kennedy和Eberhart提出的二進制粒子群算法（BPSO）[12]?；贐PSO的貨位編碼、解碼及算法求解過程描述如下：

1）貨位編號

給每個貨位采取實數(shù)編號，從1開始，則每個貨位的編號可以表示為：

式(11)中C和R表示的是每排貨架總的列數(shù)、層數(shù)，（k，c，r）為當前貨位的位置坐標。

2）粒子解碼

圖2 解碼實例

BPSO中粒子位只有0和1兩種，所以先根據(jù)任務(wù)向量中品項編號、每個貨位的狀態(tài)來確定可行域，讓可行域的長度和粒子維度相等。粒子上相應(yīng)的粒子索引號與可行域相應(yīng)的貨位索引是一一對應(yīng)的，當該粒子位上是1時就表示相對應(yīng)的貨位被選中，反之就表示該貨位沒被選中。

則最后所選擇的貨位為15、20、77、89。

基于二進制粒子群的模型基本求解過程如下：

begin

確定可行貨位N（根據(jù)任務(wù)所需的品項并且貨位的狀態(tài)是任務(wù)完成）；

參數(shù)值（主要有：種群規(guī)模（M）、粒子維度、學(xué)習(xí)因子c1、c2值、最大迭代代數(shù)等）的初始化；

t←0；

將每個可行貨位采用二進制編碼，初始化粒子群P（t）中每個粒子的位置、速度和個體極值；

while（not termination condition）do

for j←1 to M do

將每個粒子（xj）解碼（具體見解碼過程）成貨位信息（Nj）；

計算目標函數(shù)值F(Nj)、F(pbestNj)、F(gbestNj)；

將貨位信息（Nj）、當前最好解的貨位信息（pbestNj）以及近鄰中最好解的貨位信息（gbestNj）分別編碼（解碼的逆過程）成粒子信息（xj）、當前最好的解粒子信息（pbestj）和近鄰中最好解粒子信息（gbestj）

其中，N為可行貨位的集合；Nj為可行貨位中被選中的貨位；t表示迭代次數(shù)；P(t)表示第t次迭代時的粒子群；pbestNj為j粒子當前發(fā)現(xiàn)的最好解貨位；gbestNj為j粒子的近鄰當前所發(fā)現(xiàn)的最好解貨位；pbestj為j粒子當前所發(fā)現(xiàn)最好的解粒子；gbestj為j粒子的近鄰當前所發(fā)現(xiàn)的最好解粒子；Vj為粒子群中第j個粒子的速度；函數(shù)F( )表示計算粒子的目標函數(shù)值；rand( )為屬于（0，1）內(nèi)的一個隨機數(shù)； S（v）是sigmoid函數(shù)具體的表達式為：

3 試驗及分析

為了驗證優(yōu)化模型的有效性，研究設(shè)計了基于BPSO和GA的模型求解仿生算法，以VS為編程環(huán)境，進行了多品項出庫作業(yè)，最后對兩種算法的優(yōu)化結(jié)果做了對比和分析。試驗對象為6排6層8列貨架組成的單庫型區(qū)域，有三條揀貨巷道。因為進行批量出庫或批量入庫的時候其可行域的確定、優(yōu)化模型基本都一致，所以試驗中的任務(wù)向量設(shè)定為出庫任務(wù)T，具體如下所示：

3.1 參數(shù)的確定

通過在不同種群規(guī)模下目標函數(shù)值的對比試驗，來選取種群規(guī)模數(shù)，當種群規(guī)模小于100時，其目標函數(shù)值有明顯減小的趨勢，當種群規(guī)模大于100時又有上升，而種群規(guī)模等于100的時候目標函數(shù)值最小，所以種群規(guī)模選擇100。具體的變化如圖3所示，其中所用到的任務(wù)向量為出庫任務(wù)向量T，并且每次的學(xué)習(xí)因子相同。

圖3 不同種群規(guī)模目標函數(shù)值的對比（每種規(guī)模試驗10次）

試驗中用到的遺傳算法（GA）是標準的遺傳算法，具體的算法參數(shù)設(shè)置詳情如表1所示。

表1 試驗案例算法參數(shù)設(shè)置

3.2 不同優(yōu)化方法的試驗結(jié)果對比

試驗中任務(wù)向量為出庫任務(wù)向量T，圖4、圖5分別表示的是經(jīng)過BPSO、GA優(yōu)化后，目標函數(shù)值的迭代情況，它們優(yōu)化結(jié)果對比如表2所示。

圖4 基于BPSO的目標函數(shù)值迭代情況

圖5 基于GA的目標函數(shù)值迭代情況

表2 BPSO與GA的優(yōu)化結(jié)果對比

在立體庫中每個巷道的堆垛機是并行作業(yè)的，所以每次任務(wù)所用時間取決于行程值最大的那個巷道，因此可以通過巷道的行程來表示作業(yè)效率。由圖4、圖5以及表2可以看出基于二進制粒子群和標準遺傳的仿生算法對模型的求解都能取得較好的結(jié)果，BPSO經(jīng)過245代后可得到目標函數(shù)值10.28、堆垛機行程均衡值B11為0.022及行程值D13為41.05，GA經(jīng)過316代后可得到目標函數(shù)值31.47、堆垛機行程均衡值B12為3.55及行程值D23為75.21，顯然BPSO比GA具有如下四點優(yōu)勢：1）可以以較少的代數(shù)得到較好的目標函數(shù)值；2）每代的種群差異較大，全局搜索能力更強；3）因為B11遠小于B12，各堆垛機作業(yè)更加均衡；4）工作效率η提高了45.42%。通過以上分析，基于二進制粒子群算法求解的模型較符合實際的批量訂單操作，提高了倉儲作業(yè)的整體效率和質(zhì)量。

4 結(jié)束語

在進行批量出入庫時，為了提高倉儲整體作業(yè)效率，提出了基于二進制粒子群的堆垛機作業(yè)均衡及貨位優(yōu)化模型，并且與標準遺傳算法進行了優(yōu)化效果對比，通過試驗驗證了模型及算法的有效性。由于本文只局限于單純出庫或入庫作業(yè)研究，后續(xù)研究將針對出入庫混合作業(yè)各巷道均衡性進一步展開。所研究的基于二進制粒子群的作業(yè)均衡以及貨位優(yōu)化模型及仿生算法已經(jīng)在企業(yè)倉儲管理系統(tǒng)中得到了應(yīng)用，并取得了良好地成效。

參考文獻：

[1] 丁立言,張鐸.倉儲自動化[M].1版.北京:清華大學(xué)出版社,2002,14-28.

[2] Hsieh S,Tsai K C. A BOM oriented class-based storage assignment in an automated storage/retrieval system[J]. International Journal of Advanced Manufacturing Techology,2001,17(9):683-691.

[3] 穆聰聰,郭敏.基于產(chǎn)品頻度與偏離度的貨位分配策略研究[J].物流科技,2015,06:107-112.

[4] T. A. Ajol, Ismail I, S. S. Gran, et al. An enhanced storage location assignment policy by minimizing handling cost for warehouse XYZ[A].International Conference on Computer, Communications, and Control Technology[C].IEEE,2015.

[5] Park B C, Foley R D, Frazelle E H. Performance of miniload systems with two-class storage[J].European Journal of Operational Research,2006,170(1):144-155.

[6] 張思建,方彥軍,賀瑤,肖勇.基于模擬退火算法的AVS/RS多批貨箱入庫貨位優(yōu)化[J].武漢大學(xué)學(xué)報(工學(xué)版),2016,02:315-320.

[7] 李珍萍,于洋濤,李文玉.基于貪婪算法的倉庫貨位優(yōu)化問題研究[J].物流技術(shù),2015,05:242-244.

[8] 印美,洪榮晶,劉林.基于非支配遺傳算法的自動化倉庫動態(tài)貨位優(yōu)化[J].組合機床與自動化加工技術(shù),2015,03:31-34+37.

[9] Li H P, Fang Z F, Ji S Y. Research on the Slotting Optimization of Automated Stereoscopic Warehouse Based on Discrete Particle Swarm Optimization[A].IEEE the, International Conference on Industrial Engineering and Engineering Management[C].2010:1404-1407.

[10] 李曉,項前,呂志軍,管樹林.基于單雙親混合GA的復(fù)雜揀選作業(yè)優(yōu)化[J].計算機工程與設(shè)計,2015,12:3359-3364.

[11] 張小川.現(xiàn)代倉儲物流技術(shù)與裝備[M].北京:化學(xué)工業(yè)出版社,2013:37-38.

[12] 鄧雪,李家銘,曾浩健,陳俊羊,趙俊峰.層次分析法權(quán)重計算方法分析及其應(yīng)用研究[J].數(shù)學(xué)的實踐與認識,2012,07:93-100.

[13] 黃競偉,朱福喜,康立山.計算智能[M].1版.北京:科學(xué)出版社,2010,6.

[14] Kennedy J,Eberhart R. A.discrete binary version of the particle swarm algorithm[A].Proceeding of the World Multiconference on Systemics,Cybernetics and Informatics[C].New Jersy:Piscatawary,1997,4104-4109.

Bionic algorithm research on AS/RS operation balance and location assignment optimization

DU Yong-hua1，XIANG Qian1，LYU Zhi-jun1，CHEN Dong2

TP18

：A

1009-0134(2017)01-0122-05

2016-09-11

上海市自然科學(xué)基金資助項目（15ZR1400600）；2015松江區(qū)產(chǎn)學(xué)研創(chuàng)新項目計劃

杜永華（1992 -），男，湖南邵陽人，碩士研究生，研究方向為智能制造。

機作業(yè)均衡與高倉儲效率為目標的立體庫貨位優(yōu)化模型。設(shè)計了基于二進制粒子群（Binary Particle Swarm Optimization，BPSO）和遺傳算法（Genetic Algorithm，GA）的模型求解仿生算法。通過同一個立體庫批量訂單作業(yè)實例，驗證了所提模型及算法的有效性，算法試驗及分析表明，基于BPSO的立體庫作業(yè)均衡及貨位優(yōu)化效果較遺傳算法顯著。