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

侯忠，鄭國華

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

?

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

侯忠，鄭國華

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

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

倉儲管理；貨位優化；遺傳算法；汽車配件

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

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

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

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

1 汽車配件倉庫的貨位優化問題

1.1 貨位優化思路

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

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

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

(1)

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

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

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

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

最后對每排貨架進行細致到貨格的貨位優化，每排貨架的結構示意圖如圖3所示。

圖3 貨架單排結構示意圖Fig.3 Shelves with single structure diagram

1.2 貨位優化的流程圖

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

圖4 貨位優化思路流程圖Fig.4 Flow chart of slotting optimization idea

2 汽車配件倉庫貨位優化模型

2.1 模型的假設

為了將研究問題簡化，本文單排貨架貨位優化模型建立在以下假設基礎上：

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

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

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

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

2.2 模型中變量的定義

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

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

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

l為貨格的長度；

h為貨格的高度；

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

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

2.3 模型設計

2.3.1 目標函數一

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

(2)

其中rxy可以由預測方法得到。

(3)

2.3.2 目標函數二

單排貨架上貨物的優化的同時應注意保持貨架的穩定性，要遵循“上輕下重”的優化原則，該目標可以轉化為所有貨物的整體重心高度最低。依據以上思想，建立第二目標函數如式(4)。

(4)

(5)

綜合以上可得出單排貨位優化的多目標規劃的模型如下：

(6)

s.t.

1≤x≤a

1≤y≤b

x,y為整數

3 貨位優化模型的算法設計

3.1 多目標優化問題描述

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

多目標優化問題可以描述如下：

s.t.

X?Ω

(7)

n≥2

本文采用乘除法，通過目標函數的相乘使所得函數具有明確的含義，這樣就把多目標函數轉化成單目標函數，這個單目標函數中包含了多目標優化的意圖，并利用遺傳算法進行求解。

3.2 遺傳算法設計

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

1)目標函數的處理

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

(8)

2)染色體編碼

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

3)初始化種群

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

4)確定適應度函數

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

(9)

(5)選擇策略

(10)

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

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

6)交叉算子

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

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

7)變異算子

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

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

8)終止條件

這里采用迭代次數達到預設的代數來判斷算法是否終止。

9)算法步驟

Step1：初始化,設置控制參數和終止條件；

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

Step3：計算初始種群個體的適應度值和目標函數值；

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

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

Step6：判斷算法是否滿足終止條件，滿足則停止,不滿足則轉Step3，繼續迭代；

Step7：輸出最優解。

4 實例分析

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

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

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

表1 某排架內貨物的屬性

表2 貨位優化前的隨機初始解

表3 貨位優化后的解

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

圖8為算法的優化過程。

圖8 算法優化的過程Fig.8 Algorithm optimization process

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

5 結論

1)本文建立了基于出庫時間和貨物重心最低的貨位優化的雙目標優化模型，并利用乘除法將雙目標函數轉化為單目標函數，并設計了求解此模型的遺傳算法。

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

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

[2] 佘曉波. 義烏共同倉儲系統設施規劃與布局設計[J]. 中小企業管理與科技, 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] 羅勇，陳治亞.基于改進遺傳算法的供應鏈金融質押物配送路勁優化[J].鐵道科學與工程學報，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] 張得志，李雙艷.物流節點動態布局優化模型及其求解算法研究[J].鐵道科學與工程學報，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] 譚澤波.立體倉庫庫位選擇優化模型研究[J].中心企業科技，2007(10)：56-58. TAN Zebo.Warehouse location optimization model of choice[J].Enterprise Technology Center,2007(10):56-58.

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

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

[15] 吳璟,蘇強.基于路徑、周轉率、揀貨成本系數的線性規劃在貨位優化中的應用[J].中國高新技術企業，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] 鄭凌鶯.醫藥物流中心倉庫貨位優化系統的研究[D]. 上海: 上海交通大學, 2005. ZHENG Lingying.The research on medicine logistics center warehouse slotting optimization system[D].Shanghai:Shanghai Jiaotong Unicersity,2005.

[17] 馬永杰，蔣兆遠，楊志民,等.基于遺傳算法的自動化倉庫的動態貨位分配[J].西南交通大學學報，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] 馬婷.包裝產品倉儲貨位的優化問題研究[D]. 西安: 西安理工大學, 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-)，男，湖南汨羅人，副教授，博士，從事物流與供應鏈管理、物流系統規劃設計等方面研究；Email:zgh@csu.edu.cn

F252

A

1672-7029(2016)11-2305-08