侯忠，鄭國華

(中南大學(xué) 交通運輸工程學(xué)院，湖南 長沙 410075)

?

基于遺傳算法的汽車零配件倉庫貨位優(yōu)化研究

侯忠，鄭國華

(中南大學(xué) 交通運輸工程學(xué)院，湖南 長沙 410075)

倉庫貨位優(yōu)化問題是倉儲管理的重要內(nèi)容之一。針對配件庫汽配貨物種類繁多、出入庫頻率差異較大、需求時間與需求數(shù)量具有隨機性等特點，對配件庫汽配件貨物的貨位分配與優(yōu)化問題進行討論，在明確庫內(nèi)配件貨物貨位優(yōu)化思路的基礎(chǔ)上，建立基于貨位優(yōu)化的多目標(biāo)規(guī)劃模型。最后將此多目標(biāo)規(guī)劃模型轉(zhuǎn)化成單目標(biāo)規(guī)劃模型，并設(shè)計求解此模型的遺傳算法。實例結(jié)果表明：采用此優(yōu)化策略能夠有效地解決汽配件貨物的貨位優(yōu)化分配問題。

倉儲管理；貨位優(yōu)化；遺傳算法；汽車配件

倉儲是物流系統(tǒng)的一個重要組成部分。據(jù)估算，儲存和物料搬運成本占物流總成本的26%，因此加強倉儲管理，提高倉儲運作效率，降低倉儲運作成本是降低物流成本的重要途徑。汽車配件倉儲是一種特殊的倉儲類別，配件庫汽配貨物具有種類繁多、出入庫頻率差異較大、需求時間與需求數(shù)量具有隨機性等特點。汽車配件倉儲作為汽車行業(yè)售后物流的一個重要環(huán)節(jié)，在整個供應(yīng)鏈中也扮演了非常重要的角色[1]。

貨位優(yōu)化是倉庫布局研究的一個主要分支，隨著現(xiàn)代計算機技術(shù)以及控制技術(shù)的不斷發(fā)展，生產(chǎn)企業(yè)和物流倉儲企業(yè)倉庫管理呈現(xiàn)出控制最優(yōu)化、運行智能化的發(fā)展趨勢，對倉庫的貨位優(yōu)化已成為物流技術(shù)發(fā)展的一個重要標(biāo)志[2]。國外對倉儲貨位優(yōu)化研究相對較早。Hesket[3]研究了貨物存儲所需要的存儲空間以及貨物的訂單數(shù)量對倉儲效率的影響。Goetschalckx等[4]證明了N類貨物分配下最低COI值的貨物存儲在最適宜的貨位，訂單揀選和存儲時間得到了優(yōu)化。Graves等[5]分析了貨物組合成更少的類別時，高周轉(zhuǎn)率的貨物可能會占據(jù)不理想的貨位。Rosenwein[6]提出了貨位布局的分級存儲策略。Larson等[7]在Rosenwein研究基礎(chǔ)上，使用啟發(fā)式算法對分級存儲策略進行探討。Sooksaksun等[8]基于分類存儲策略對巷道的數(shù)量、長度、產(chǎn)品的分類存儲建立數(shù)學(xué)模型，模型以最小化平均行走距離為目標(biāo)。Zhan等[9]研究了帶鄰接約束的多層次倉庫布局問題，建立了描述同類產(chǎn)品的臨近放置的整數(shù)規(guī)劃模型，并采用禁忌搜索算法求解。

在國內(nèi)，對貨位優(yōu)化研究方面，文獻[10]和[11]為本文在算法方面的探究提供了算法的支持,認為遺傳算法在解決貨位優(yōu)化NP-難問題方面具有有效性。譚澤波[12]以貨物的位置、貨物的質(zhì)量和存取次數(shù)為變量建立貨位優(yōu)化模型，文章對貨物的相關(guān)性等因素缺乏考慮。董溪哲等[13]提出了以物品周轉(zhuǎn)率為標(biāo)準(zhǔn)的貨位優(yōu)化模型。王建[14]以貨物出入庫效率、貨架穩(wěn)定性以及貨品存放的相關(guān)性為目標(biāo)建立了多目標(biāo)的優(yōu)化模型，采用權(quán)重系數(shù)法將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題，但沒有對不同量綱的目標(biāo)函數(shù)做標(biāo)準(zhǔn)化處理。吳璟等[15]重點討論了影響揀貨效率的因素，根據(jù)這些因素引入揀貨成本系數(shù)，在路徑、周轉(zhuǎn)率等關(guān)鍵指標(biāo)基礎(chǔ)上建立線性規(guī)劃的貨位模型。鄭凌鶯[16]在解決貨物相關(guān)性即產(chǎn)品族的問題方面，綜合考慮貨物的周轉(zhuǎn)率、重量和類聚現(xiàn)象的三個主次目標(biāo)，建立貨位優(yōu)化的多目標(biāo)模型。馬永杰等[17]基于隨機存儲策略對自動化倉庫的庫區(qū)和貨位分配以及堆垛機行駛時間進行優(yōu)化，在約束條件中考慮到堆垛機容量和速度。馬婷[18]提出基于最小時間算法的貨位優(yōu)化方法，建立自動化立體倉庫三維立體模型，實現(xiàn)了對煙草倉庫貨位的優(yōu)化。

應(yīng)當(dāng)看到的是，上述研究成果大多僅局限于理論探索層面，由于每個倉儲企業(yè)的業(yè)務(wù)范圍、服務(wù)對象的差異，特別是在倉庫的規(guī)模、物料的規(guī)格、包裝、形狀、市場銷售等諸多方面存在的差異性，需要我們在實際生產(chǎn)過程中加強具體的實用性研究。因此本文主要考慮汽配件倉儲特點，基于汽配件入庫頻率等因素建立倉儲貨位優(yōu)化模型，以實現(xiàn)汽配件倉儲貨位優(yōu)化，滿足生產(chǎn)對汽配件的配送要求。

1 汽車配件倉庫的貨位優(yōu)化問題

1.1 貨位優(yōu)化思路

汽車配件庫的倉儲管理貨物品類相對較多，對于高架立體倉儲區(qū)在存儲策略選擇方面適宜采用分類管理策略，把不同的貨物進行歸類處理，以方便管理(見圖1)。

圖1 貨物歸類示意圖Fig.1 Goods classification diagram

在實際優(yōu)化中本著為取而存的思想，首先將貨物分為若干大類，每大類貨物又包含若干小類貨物，對各大類貨物的平均在庫量 (按每大類貨物月均在庫的托盤數(shù)量計算)進行統(tǒng)計。下面給出大類的平均在庫量的統(tǒng)計公式，見式(1)。

(1)

式中：P為大類的貨物平均在庫量；p為小類貨物的平均在庫量。

接著在統(tǒng)計數(shù)據(jù)的基礎(chǔ)上對未來一個周期的各大類貨物平均在庫量進行預(yù)測，根據(jù)預(yù)測結(jié)果確定該類貨物需要分配的貨架排數(shù)。對大類貨物出入庫頻率(按每大類貨物每月的平均出入庫量計算)進行預(yù)測。

考慮到本文貨位分配的依據(jù)是平均出入庫頻率，因此會存在某個時間段內(nèi)某排貨架的貨物在庫量超出該排貨架的容量，所以分配完貨架還應(yīng)考慮建立適量的機動貨架來存放超出部分的貨物。

圖2 立體倉貨架庫示意圖Fig.2 Stereoscopic warehouse shelves library

最后對每排貨架進行細致到貨格的貨位優(yōu)化，每排貨架的結(jié)構(gòu)示意圖如圖3所示。

圖3 貨架單排結(jié)構(gòu)示意圖Fig.3 Shelves with single structure diagram

1.2 貨位優(yōu)化的流程圖

為了更加清楚描述本文的優(yōu)化思路，本文以流程圖方式表示如圖4。

圖4 貨位優(yōu)化思路流程圖Fig.4 Flow chart of slotting optimization idea

2 汽車配件倉庫貨位優(yōu)化模型

2.1 模型的假設(shè)

為了將研究問題簡化，本文單排貨架貨位優(yōu)化模型建立在以下假設(shè)基礎(chǔ)上：

1)倉庫每個巷道均有一臺堆垛機；

2)堆垛機的行走的水平速度和垂直速度均為勻速；

3)每個貨格的規(guī)格是一樣的，即貨格的長度和高度是固定的；

4)每一類貨物的出庫頻率都能得到滿意的預(yù)測結(jié)果。

2.2 模型中變量的定義

wxy為放在第x列、第y層的貨物的重量；

rxy為放在第x列、第y層的貨物的出庫頻率預(yù)測值；

txy為第x列、第y層貨格的貨物到達出庫口所需時間；

l為貨格的長度；

h為貨格的高度；

Vi為堆垛機行走的平均水平速度；

Vj為堆垛機行走的平均垂直速度；

2.3 模型設(shè)計

2.3.1 目標(biāo)函數(shù)一

單排貨架上貨物的優(yōu)化最主要目的是提升訂單的響應(yīng)速度，這里衡量響應(yīng)速度的指數(shù)當(dāng)中最直接的就是時間，使出入庫頻繁高的貨物放置在靠近巷道口處是節(jié)約出庫時間的良好策略，依據(jù)上面的思想，建立第一目標(biāo)函數(shù)如式(2)。

(2)

其中rxy可以由預(yù)測方法得到。

(3)

2.3.2 目標(biāo)函數(shù)二

單排貨架上貨物的優(yōu)化的同時應(yīng)注意保持貨架的穩(wěn)定性，要遵循“上輕下重”的優(yōu)化原則，該目標(biāo)可以轉(zhuǎn)化為所有貨物的整體重心高度最低。依據(jù)以上思想，建立第二目標(biāo)函數(shù)如式(4)。

(4)

(5)

綜合以上可得出單排貨位優(yōu)化的多目標(biāo)規(guī)劃的模型如下：

(6)

s.t.

1≤x≤a

1≤y≤b

x,y為整數(shù)

3 貨位優(yōu)化模型的算法設(shè)計

3.1 多目標(biāo)優(yōu)化問題描述

多目標(biāo)優(yōu)化(multiple objective program,簡記為MOP)問題由FY Edgeworth 最先提出，V Pareto對其進行了完整的定義。在求解多目標(biāo)問題時候，各個目標(biāo)函數(shù)存在著相互沖突，很難求到滿足所有目標(biāo)函數(shù)的最優(yōu)解，只在非劣解的基礎(chǔ)上不斷尋找滿意解，即帕累托(Pareto)最優(yōu)解。

多目標(biāo)優(yōu)化問題可以描述如下：

s.t.

X?Ω

(7)

n≥2

本文采用乘除法，通過目標(biāo)函數(shù)的相乘使所得函數(shù)具有明確的含義，這樣就把多目標(biāo)函數(shù)轉(zhuǎn)化成單目標(biāo)函數(shù)，這個單目標(biāo)函數(shù)中包含了多目標(biāo)優(yōu)化的意圖，并利用遺傳算法進行求解。

3.2 遺傳算法設(shè)計

遺傳算法(Genetic Algorithm,GA)最早是由Holland教授在20世紀(jì)70年代提出并發(fā)展起來的智能優(yōu)化算法，具有更好的全局尋優(yōu)的能力。遺傳算法對種群的每個個體進行搜索，算法通過有效的設(shè)計可以跳出局部最優(yōu)的“陷阱”，有利于得到全局最優(yōu)解，并且全局最優(yōu)的獲得往往不依賴于初始解。而傳統(tǒng)優(yōu)化算法的尋優(yōu)能力往往比較依賴于初始解，且不易得到全局最優(yōu)。

1)目標(biāo)函數(shù)的處理

本文建立的目標(biāo)函數(shù)有兩個，一個關(guān)注出入庫的效率，另一個關(guān)注貨架的穩(wěn)定性。為了便于模型的求解，這里利用乘除法把兩個目標(biāo)轉(zhuǎn)化成單個目標(biāo)。則原目標(biāo)函數(shù)就變成了：

(8)

2)染色體編碼

本文對單排貨架上的貨物采用真值編碼，編碼串的長度為a*b位，即編碼串的長度是單排貨架的層數(shù)與列數(shù)的乘積，也就是單排貨架上的所有貨物數(shù)。如c1c2…cn…ca*b,代表1到a*b之間所有的整數(shù)的一個排列組合，cn表示第cn個貨物放在第x列第y層的貨架上(其中x的取值為a整除n的商加1，y的取值為b整除n的余數(shù))。

3)初始化種群

1到a*b之間所有的整數(shù)的一種排列組合組成了一個完整的個體的染色體，隨機產(chǎn)生M個染色體即可組成初始種群，一般種群的規(guī)模在20～100之間。

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

適應(yīng)度函數(shù)又叫評價函數(shù)，在遺傳算法中適應(yīng)度值高的個體遺傳到下一代的概率比較大，本文的模型是求解最小值，因此需要在目標(biāo)函數(shù)和適應(yīng)度函數(shù)之間做出變換。由于兩個目標(biāo)函數(shù)的最小值均為非負，因此可以將目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)，目標(biāo)函數(shù)值越大的解對應(yīng)的適應(yīng)度函數(shù)值就越小，這樣的解被“優(yōu)勝”的可能性也就會越小。

(9)

(5)選擇策略

(10)

那么個體被選中次數(shù)的期望為n·p(i)。

圖5 輪盤賭示意圖Fig.5 Roulette schematic

6)交叉算子

在交叉運算前先將種群中的M個體以隨機的方式組成[M/2]對配對，交叉操作就是在這些配對的父代中進行的。本文在交叉策略方面選取單點交叉，在個體的編碼串隨機設(shè)置一個點，對該點以后的部分染色體進行相互交換，對于長度為N位的編碼串個體，則交叉點的位置有N-1種可能。單點交叉的示意圖如圖6。

圖6 單點交叉示意圖Fig.6 A single point of cross schematic diagram

7)變異算子

本文在編碼中采用的是整數(shù)編碼，為了使變異后的個體染色體仍然能表示可行解，在變異操作中選取個體染色體的指定位置上的基因進行對調(diào)(見圖7)，從而既通過變異產(chǎn)生新個體又能保持染色體基因組的完備性。

圖7 變異運算示意圖
Fig.7 Mutation operation schematic diagram

8)終止條件

這里采用迭代次數(shù)達到預(yù)設(shè)的代數(shù)來判斷算法是否終止。

9)算法步驟

Step1：初始化,設(shè)置控制參數(shù)和終止條件；

Step2：GenN:=0，隨機產(chǎn)生初始種群Pop(0)；

Step3：計算初始種群個體的適應(yīng)度值和目標(biāo)函數(shù)值；

Step4：按照輪盤賭選擇策略，從Pop(GenN)種群中選擇出Pop(GenN+1)種群；

Step5：對Pop(GenN+1)種群進行交叉、變異運算，GenN:=GenN+1；

Step6：判斷算法是否滿足終止條件，滿足則停止,不滿足則轉(zhuǎn)Step3，繼續(xù)迭代；

Step7：輸出最優(yōu)解。

4 實例分析

先根據(jù)指數(shù)平滑預(yù)測方法，對倉庫的貨物進行預(yù)測。假定已得到庫內(nèi)某排貨架上的16種貨物(共計200托盤的量)的屬性，具體如表1所示。

把以上貨物按照上表中的順序，以托盤為單位編號1～200，然后將1～200號貨物隨機排列作為一個初始解見下表2，表中的單元格表示該排貨架某個貨位對應(yīng)的貨物，如第二列第三層的貨格對應(yīng)的是第133號貨物。該初始解對應(yīng)的目標(biāo)函數(shù)為9.216 8*108。

假設(shè)貨格的長度和高度均為1米，堆垛機的垂直和水平行走速度均為1 m/s，取種群規(guī)模NIND=100，代溝GGAP=0.7，交叉概率Pc=0.7， 變異概率Pm=0.1，迭代次數(shù)為4 000代，可以得到優(yōu)化后的解如表3，該優(yōu)化后的解對應(yīng)的目標(biāo)函數(shù)值為4.684 9*108。

表1 某排架內(nèi)貨物的屬性

表2 貨位優(yōu)化前的隨機初始解

表3 貨位優(yōu)化后的解

由表1和表3可以看出優(yōu)化后的貨位較大程度上保留了貨物的相關(guān)性，即屬性類似的貨物臨近放置。

圖8為算法的優(yōu)化過程。

圖8 算法優(yōu)化的過程Fig.8 Algorithm optimization process

由圖8算法的優(yōu)化過程可以看出，算法在1 500代時已經(jīng)較好的收斂，整個優(yōu)化時間為164.25 s，優(yōu)化后解的目標(biāo)函數(shù)值降至原隨機解的目標(biāo)函數(shù)的50.83%。也就是說本文建立的貨位優(yōu)化模型，在保持貨架的穩(wěn)定性即貨物的擺放遵循“上輕下重”的優(yōu)化原則的同時，最大限度地把出入庫頻繁的貨物放置在靠近巷道口處，這將極大地提升訂單的響應(yīng)速度。

5 結(jié)論

1)本文建立了基于出庫時間和貨物重心最低的貨位優(yōu)化的雙目標(biāo)優(yōu)化模型，并利用乘除法將雙目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)函數(shù)，并設(shè)計了求解此模型的遺傳算法。

2)通過遺傳算法求解，優(yōu)化后的目標(biāo)函數(shù)值降至原隨機解的目標(biāo)函數(shù)值的50.83%，說明了遺傳算法在解決此類問題時的有效性，為企業(yè)節(jié)約倉儲成本，提高作業(yè)效率奠定了基礎(chǔ)。

[1] Ballou R H. Enterprise logistics management:Plan,organize and control of the supply chain[M].Beijing:Mechanical Industry Press, 2006.

[2] 佘曉波. 義烏共同倉儲系統(tǒng)設(shè)施規(guī)劃與布局設(shè)計[J]. 中小企業(yè)管理與科技, 2012 (4): 275-277. SHE Xiaobo.Yiwu common storage facility planning and layout design system[J].Management&Technology,2012(4):275-277.

[3] Heskett J L. Cube-per-order index-a key to warehouse stock location[J]. Transportation and Distribution Management, 1963, 3(4): 27-31.

[4] Goetschalckx M, Ratliff H D. Shared storage policies based on the duration stay of unit loads[J]. Management Science, 1990, 36(9): 1120-1132.

[5] Graves S C, Hausman W H, Schwarz L B. Storage-retrieval interleaving in automatic warehousing systems[J]. Management Science, 1977, 23(9): 935-945.

[6] Rosenwein M B . An application of cluster analysis to the problem of locating items within a warehouse [J]. IIE Transcations,1994,26(1):101-103.

[7] Larson T N, March H, Kusiak A. A heuristic approach to warehouse layout with class based storage[J].IIE Transactions,1997，1(29):337-348.

[8] Roodbergen K J, Vis I F A. A model for warehouse layout[J]. IIE Transactions, 2006, 38(10): 799-811.

[9] Zhang G Q, Lai K K. Tabu search approaches for the multi-level warehouse layout problem with adjacency constraints[J]. Engineering Optimization, 2010, 42(8): 775-790.

[10] 羅勇，陳治亞.基于改進遺傳算法的供應(yīng)鏈金融質(zhì)押物配送路勁優(yōu)化[J].鐵道科學(xué)與工程學(xué)報，2015，12(4)：949-955. LUO Yong,CHEN Zhiya.Distribution path optimization of pledge in supply chain finance based on improved genetic algorithm[J]. Journal of Railway Science and Engineering, 2015，12(4):949-955.

[11] 張得志，李雙艷.物流節(jié)點動態(tài)布局優(yōu)化模型及其求解算法研究[J].鐵道科學(xué)與工程學(xué)報，2011,8(5)，96-100. ZHANG Dezhi, LI Shuangyang. Research on an optimization model for logistic nodes dynamic location and its solution algorithm[J]. Journal of Railway Science and Engineering, 2011,8(5),96-100.

[12] 譚澤波.立體倉庫庫位選擇優(yōu)化模型研究[J].中心企業(yè)科技，2007(10)：56-58. TAN Zebo.Warehouse location optimization model of choice[J].Enterprise Technology Center,2007(10):56-58.

[13] 董溪哲.倉儲貨位優(yōu)化模型及算法研究[D]. 哈爾濱: 哈爾濱工業(yè)大學(xué), 2006. DONG Xizhe.Models and algorithms for warehousing slotting optimization[D]. Harbin:Harbin Institute of Technology, 2006.

[14] 王建.基于遺傳算法的倉儲貨位優(yōu)化研究[D]. 西安: 西安建筑科技大學(xué), 2009. WANG Jian. Genetic algorithm basedwarehousing slotting optimization[D].Xi’an:Xi’an University of Architecture and Technology,2009.

[15] 吳璟,蘇強.基于路徑、周轉(zhuǎn)率、揀貨成本系數(shù)的線性規(guī)劃在貨位優(yōu)化中的應(yīng)用[J].中國高新技術(shù)企業(yè)，2011(9)：46-48. WU Hao, SU Qiang. Based on the path,turnover,cost coefficient of linear picking planning application in slotting optimization[J]. Chinese High-tech Enterprises, 2011(9):46-48.

[16] 鄭凌鶯.醫(yī)藥物流中心倉庫貨位優(yōu)化系統(tǒng)的研究[D]. 上海: 上海交通大學(xué), 2005. ZHENG Lingying.The research on medicine logistics center warehouse slotting optimization system[D].Shanghai:Shanghai Jiaotong Unicersity,2005.

[17] 馬永杰，蔣兆遠，楊志民,等.基于遺傳算法的自動化倉庫的動態(tài)貨位分配[J].西南交通大學(xué)學(xué)報，2008,43(3):415-421. MA Yongjie,JIANG Zhaoyuan,YANG Zhimin, et al. Dynamic location assignment genetic algorithm-based automated warehouse[J]. Southwest Jiaotong University, 2008,43(3):415-421.

[18] 馬婷.包裝產(chǎn)品倉儲貨位的優(yōu)化問題研究[D]. 西安: 西安理工大學(xué), 2008. MA Ting.Research on optimization of packaging products warehousing cargo space[D]. Xi’an： Xi’an University of Technology, 2008.

The research on auto parts warehouse slottingoptimization based on genetic algorithm

HOU Zhong，ZHENG Guohua

(School of Traffic and Transportation Engineering，Central South University，Changsha 410075，China)

Warehouse Slotting optimization is an important part of warehouse managements. In this paper, the type of accessories for auto goods, warehousing large frequencies, time needs and the number of the randomness of demand characteristics, the goods allocation and optimization problems of the auto parts library package were discussed. On the basis of the library explicitly cargo accessories of Slotting Optimization, slotting optimization mathematical model was established and the multi-objectives were added into a single objective programming problem. Finally, this multi-objective programming model was converted into a single objective programming model, and a genetic algorithm to solve this model was chosen. The results show that using this optimization strategy can effectively solve the auto package goods position optimization allocation problem.

warehouse management;slotting optimization;genetic algorithm;auto parts

2016-01-21

鄭國華(1963-)，男，湖南汨羅人，副教授，博士，從事物流與供應(yīng)鏈管理、物流系統(tǒng)規(guī)劃設(shè)計等方面研究；Email:zgh@csu.edu.cn

F252

A

1672-7029(2016)11-2305-08