基于改進自適應遺傳算法的入庫貨位優化研究

劉瑋瑋

摘 要： 探討了基于Srinivas M提出的線性自適應遺傳算法，在此基礎上，從種群多樣性的表示上，對算法進行了改進，得出了一種新型自適應遺傳算法。根據基本入庫原則和庫存現狀，將入庫時庫位選擇歸納為一個多目標優化問題，建立對應的數學模型。將改進的算法用于入庫貨位模型求解，結果表明，該算法能夠較好的解決入庫問題，選擇出最佳貨位，從而證明了算法的有效性。

關鍵詞： 倉儲效率； 貨位優化； 改進的自適應遺傳算法； 多目標優化

中圖分類號：TP393.09 文獻標志碼：A 文章編號：1006-8228（2018）08-57-04

Study on the warehousing slotting optimization based on

improved adaptive genetic algorithm

Liu Weiwei

（Faculty of Informatics， Fujian Vocational College of Agriculture， Fuzhou， Fujian 350001， China）

Abstract： This paper discusses the linear adaptive genetic algorithm which is presented by Srinivas M， on this basis， improves the algorithm from the representation of population diversity， and proposes a new adaptive genetic algorithm. According to the basic principle of warehousing and the status of inventory， the storage location selection is summarized as a multi-objective optimization problem， and a corresponding mathematical model is established. Using the improved algorithm to solve the storage location model， the result indicates that the algorithm can better work out the problem of warehousing and choose the best location， and then the validity of the algorithm is proved.

Key words： storage efficiency； slotting optimization； the improved adaptive genetic algorithm； multi objective optimization

0 引言

貨位優化的目的是將倉庫黃金區域分給高頻撿取的貨物，從而實現最大化揀選效率以及最小化揀選成本， 還可方便補貨及平衡各工作區的工作量，這些能為倉儲管理提供有效的支撐并提高揀選的準確性。當前世界各物流管理公司推出了許多貨位優化軟件，大致分為兩種，一種是與WMS綁定，另一種是適合中小規模倉庫使用并與WMS分離的。在貨位分配時考慮的原則一般包括[1]：貨架承載均勻，上輕下重；加快周轉，先入先出；提高可靠性，分巷道存放；提高效率，就近出入庫及產品相關性等。存儲位置的分配和實現策略[2]有分類存儲策略；改進的先進先出策略；隨機存儲策略；貨物相關性策略；共享存儲策略等。

1 入庫貨位分配模型的建立

入庫貨位優化問題可描述如下。

已知：參見表1數據和擬入庫貨物的相關數據。

約束：⑴ 貨位分配原則；

⑵ 當前倉庫貨位存儲狀況。

目標：優化貨位，提高貨位利用率及倉儲運作效率。

本文的入庫分配模型由五個子模型組成，在貨物入庫對庫位進行選擇時，需要綜合考慮這五個模型的值來選擇最優貨位，根據商允偉等[3]、鄭凌鶯等[4]、邰世文[5]等人的研究成果，將貨位分配歸結為多目標優化問題，建立入庫貨位分配模型見式⑴，相關變量說明見表1。

2 改進的自適應遺傳算法

遺傳算法（Genetic Algorithm，GA）是一種基于生物進化機制的隨機搜索算法，能夠有效地進行概率意義下的全局搜索[6]。目前常見的自適應遺傳算法有：線性自適應遺傳算法、余弦自適應遺傳算法、指數自適應遺傳算法，本文改進算法基于Srinivas M的線性自適應遺傳算法[7]，見公式⑵：

當個體適應度較大而接近種群適應度最大值時，Pc和Pm都會變的很小。在種群中個體適應值為最優值時，其變異概率為零，對最優個體不進行交叉和變異操作。Srinivas M以fmax-favg為標準來衡量種群多樣性，在整個種群適應值水平較為平均時是可行的，但在種群最優個體的適應值是一個離群值，即其值是遠離序列的一般水平極大值和極小值的情況下，再使用fmax-favg衡量種群多樣性就會失去意義。為防止此情況出現，使用種群個體適應度的標準差代替fmax-favg，得出改進的自適應遺傳算法，即自適應變異交叉概率公式[8]，即見式⑶，其中Pc1=0.7， Pc2=0.1，Pm1=0.1，Pm2=0.001：

⑶

為驗證該改進遺傳算法的性能，本文選取一個含有四個局部最優解的函數作為測試函數， 因全局最優解常被最差解包圍，如果遺傳算法的種群收斂性不好，則極易陷入局部最優[9]。同時引用線性自適應遺傳算法（LAGA）[7]、余弦自適應遺傳算法（CAGA）[10]、冪指數自適應遺傳算法（IAGA）[11]與本文算法進行性能上的比較，本文改進算法因使用了反三角函數故簡稱為AAGA[8]。測試函數f說明見表2所示。

可以看到在平均適應度方面，本文算法的種群比其他自適應遺傳算法的種群擁有更多的優良個體和相對較強的自適應能力，無論求解最大值還是最小值，該算法都有一定的優勢。在最優適應度方面，本文算法也能更快地達到最優解，且有較強的自適應能力，從局部最優走向全局最優；且在收斂次數、平均收斂代數和平均收斂值三個方面，本文算法也具有一定優勢。

3 入庫貨位分配模型求解

貨位優化問題實際上是一個多目標求解問題，多目標優化問題沒有絕對意義上的最優，而只能平衡、協調多個目標達到Pareto最優解[12]。目前有許多使用遺傳算法對多目標求解的方法，其中常用的有權重系數法、并列選擇法、排列選擇法等， 本文使用并列選擇法對前文所建立貨位分配模型求解。求解過程主要由四個部分組成：編碼機制、控制參數、適應度函數和遺傳算子[6]，流程圖如圖3所示。

⑴ 編碼使用二進制。假設倉庫有16*32個貨位，每個貨位可以使用橫縱坐標（i，j）（i=1，2，3…16；j=1，2，3…32）進行標定，因使用二進制編碼方式，橫坐標使用四位二進制編碼1111表示，縱坐標使用五位二進制編碼11111表示，標識貨位的坐標形式為（iiii，iiiii）（i=0，l）形式。為更好提高效率，將橫縱坐標組合成為一體（iiii， iiiii）→iiiiiiii進行編碼。

⑵ 解碼：根據編碼中規定的橫縱坐標二進制串的長度，將整個染色體劃分為兩部分，將橫縱坐標當中的二進制子串轉換為對應的十進制，再根據十進制數字得到具體貨位。

⑶ 初始化種群：交叉和變異概率分別為Pc1=0.8，Pc2=0.5，Pm1=0.04，Pm2=0.001，種群規模100，最大演化代數3000。

⑷ 適應度函數設計：適應度值的計算需要用到表1中的數據和入庫貨物的相關數據，包括貨位訂單號、貨物ID號、貨物數量和每件貨物的高度等。確定以上數據后，可使用建立的入庫貨位分配模型的五個數學模型計算倉庫當中所有貨位的適應度值，得到五個16*32的適應度值矩陣，在遺傳算法的遺傳操作當中，查表即可知某個貨位在某個函數下的適應度值。

⑸ 遺傳操作：使用改進自適應遺傳算法計算個體發生交叉和變異的概率。算法的選擇算子采用無放回式隨機余數算法獲得，交叉算子采用單點交叉算法獲得，變異算子采用離散變異算法獲得，貨位高度參考企業提供限高信息，應用時根據實際情況修改貨位限定高度即可。

表5列出了入庫時一些關鍵未知數據，其中倉庫入庫口坐標和倉庫中最大坐標為常量值，據每個倉庫的實際規劃獲得。

為1時表示以（i，j）為坐標的貨位上有同一訂單的貨物；為0時表示該貨位上沒有同一訂單的貨物

決策變量。為1時表示以（i，j）為坐標的貨位上有同一種貨物； 為0時表示該貨位上沒有同一種貨物 ]

圖4和圖5是本文算法AAGA求解入庫貨位分配模型最優解的仿真過程，圖4為初始狀態的倉庫，其中方塊表示高度已經高于250厘米不能再放置的貨位；菱形表示其高度在[100，250）之間的貨位；下三角表示其高度在[50，100）之間的貨位；上三角表示其高度在[0，50）之間的貨位，圖5為經過本文算法標記過的倉庫，其中用五角星標記的坐標（8，18）貨位是推薦的最優貨位。

在具體的倉儲系統中，參照入庫貨位分配模型，本文算法可用Java等高級編程語言實現。進行入庫操作時，倉庫管理員通過Android客戶端掃描貼在貨物上的二維碼，獲得貨物信息，輸入入庫數量， 信息提交給服務器端后， 服務器端根據傳遞的參數和算法進行運算，得出推薦入庫貨位后返回給客戶端顯示。

4 結論

本文首先根據基本的入庫原則和庫存現狀分析了影響倉儲運營效率的入庫操作，將入庫時庫位選擇問題歸納為一個多目標優化問題，建立貨位分配數學模型；接下來闡述一種在自適應函數對種群多樣性的表示上進行改進的遺傳算法，其在平均適應度和最優適應度等方面，較之其他自適應遺傳算法有一定優勢；最后采用遺傳算法的并列選擇法對該貨位分配模型進行求解，解決多目標優化問題。結果表明，這種改進的自適應遺傳算法用于所建立的貨位分配模型，能夠較好的解決入庫問題，選擇出最佳貨位。

參考文獻（References）：

[1] 左生龍，劉軍.現代倉儲作業管理[M].中國物資出版社，2006.

[2] 馬永杰，蔣兆遠，楊志民.基于遺傳算法的自動化倉庫的動態

貨位分配[J].西南交通大學學報，2008，3（43）：415-420.

[3] 商允偉，裘聿皇，劉長有.自動化倉庫貨位分配優化問題研究[J].

計算機工程與應用，2004.26：16-17

[4] 鄭凌鶯，張欣，言勇華.物流中心倉庫貨位優化系統的設計研

究[J].物流技術，2006.6：33-34

[5] 邰世文.汽車零部件物流中心設施布局優化研究[D].大連理

工大學，2013.

[6] 王雄志.配送中心配貨作業方法研究[M].中國經濟出版社，

2008.

[7] Srinivas M，Patnaik L M. Adaptive probabilities of crossover

and mutation in genetic algorithms[J]. Systems， Man and Cybernetics， IEEE Transactions on，1994.24（4）：656-667

[8] 楊志龍.基于遺傳算法的倉庫管理系統的研究與實現[D].中

國海洋大學，2014.

[9] 韓瑞鋒.遺傳算法原理與應用實例[M].兵器工業出版社，

2010.

[10] 石山，勵慶孕，王興華.基于自適應遺傳算法的無刷直流電

機的優化設計[J].西安交通大學學報，2002.12：1215-1218

[11] 金晶，蘇勇.一種改進的自適應遺傳算法[J].計算機工程與應

用，2005.18：64-69

[12] Carlos F M， Peter F J. An overview of evolutionary

algorithms in multiobjective optimization[J]. Evolutionary Computation，1995.3（1）：1-16