基于遺傳算法的軍隊立體倉庫貨位再分配研究

陳元文，吳曉波，孫耀磊

解放軍后勤工程學院后勤信息與軍事物流工程系，重慶 401311

基于遺傳算法的軍隊立體倉庫貨位再分配研究

陳元文，吳曉波，孫耀磊

解放軍后勤工程學院后勤信息與軍事物流工程系，重慶 401311

在信息化環境下作戰的今天，后勤補給在戰爭中占據著越來越重的地位。以自動化立體倉庫為代表的軍隊后勤建設在信息技術高速發展的現在受到越來越多的重視。相比普通立體倉庫，軍用立體庫具有出入貨速率快、穩定性高、靈活度大等使用需求。為滿足這些要求，除了要有先進的硬件基礎設施，管理平臺、調度策略等軟件平臺也亟待提高[1]。

在立體倉庫的貨位優化方面，關于倒庫[2]等為導向的貨位優化方法和技術路線少有研究。特別在軍隊等需求較特殊的場合，季節、戰時等時段性需求還未得到重視和滿足。本文提出了一種基于遺傳算法的存儲貨位優化思想，在堆垛機閑時，根據用戶按季節性、戰備需求等級、特殊用途等需求的預設分類方法，生成分類存儲L形分區的目標存儲區域，利用遺傳算法規劃出堆垛機完成搬運的總時間最短和貨架重心最低的貨品目標貨位，并調度堆垛機完成作業。從而提高立體庫的出庫速度。

1 存儲策略與分區介紹

1.1 軍隊自動化立體倉庫特點與現狀

根據個人在軍隊倉庫的調研和參與的相關工作，與一般立體倉庫對比，軍隊自動化立體倉庫具有以下特點：對出入庫效率要求較高，貨品類別明顯，按季節性、戰備需求、特殊用途等相對集中，倉庫穩定性要求高，安全系數要求高。因此，針對軍隊立體倉庫的研究具有迫切的需求價值，對提高我軍后勤保障能力有一定作用。

目前軍用倉庫的管理系統一般有“倒庫”等功能，但是一般靠人工手動干預或低自動化完成，國內外對靜態環境下的貨位優化也少有研究，大多集中于貨架貨位為空的情況下，所有貨物完成入庫的貨位最優分配[3-4]。

1.2 基本存儲策略與L形分類存儲貨位分區

目前自動化立體倉庫使用的基本存儲策略有分類存儲、定位存儲、隨機存儲、臨近存儲和全周轉率存儲，以及各基本存儲策略的復合型和改進型[3-4]。

本文鑒于軍隊物資類別明顯，物資需求與時間或環境有較大關聯性，因此采用分類存儲策略。在貨架的分區上，每個巷道兩側的貨架構成一個分區，每個分區所存貨物的類別和數量基本一致。該設計能較大程度地提高倉庫的穩定性，即使某一巷道堆垛機出現故障，對倉庫的正常作業也不構成較大影響，并且，由于多個堆垛機可并行出貨，保障了最大出貨效率。

分類存儲是按照貨物的種類，存放在貨架已經劃分的存儲區域中。并且讓存儲頻率高的種類存放在出入庫貨臺最近的區域。根據Rosenblatt[5]、Eynan[6]等人的研究，貨物分類數在10種以下，特別在3種左右的情況下，出入貨物的效率可以達到全周轉率存儲的水平。Hausman[7]等分別證明了在單雙指令行程下和等時正方（square-in-time）貨架的情況下，A、B、C三類貨物按照L形區域劃分有最高的存取效率。

2 貨位優化模型

2.1 貨位優化過程

在存貨品具有季節、戰時需求度等屬性，以季節更替為例，當夏季來臨時，軍隊倉庫需要將夏季物品搬運到A區，方便出庫，春秋季和冬季物品分別搬運到B、C區。

過程如下所示：當收到用戶的分類需求后，系統按照指定屬性進行分類，按類別生成貨品在存位置清單Sour_A、Sour_B、Sour_C，質量清單mx_A、mx_B、mx_C，并進行順序編號。再根據所屬類別的數量和空貨位裕量生成L形目標貨位清單Des_A、Des_B、Des_C，并對原貨位和目標貨位分別進行順序編號。以堆垛機完成搬運的距離最短和搬運后貨架重心最低為目標，使用遺傳算法解決這一多目標優化問題。在求解到Pareto最優解，即在存的每一個貨品的目標貨位后，按照當前堆垛機位置的鄰近貨位的目標空貨位為原則，調用堆垛機逐一對所有未搬運的貨品完成搬運。如圖1所示。

圖2 三類貨物按L形分區分類存儲示意圖

圖1 貨位優化流程圖

2.2 貨架等基本參數假設和L形貨位分區

貨架等基本參數假設[8-9]：

因貨品按巷道均勻分布，因此本文僅考慮單個貨架的情況。

單元立體式貨架，貨架高度H=20 m，貨架長度L=60 m，貨格尺寸長寬高為l×w×h=1.35 m×1.25 m×1.35 m，存放方式為單貨位式。共15×45=675個貨位。

堆垛機為單貨位巷道式，水平運動速度vh、垂直運動速度vv分別為120 m/min，80 m/min，貨叉伸縮速度30 m/min。

貨品按季節分類，夏季、春秋季、冬季屬性的數量依次為：nA=120，nB=180，nC=200。貨品質量滿足500 kg到2 300 kg的均勻分布。

L形貨位分區：

由于堆垛機可以在水平和垂方向同時運動，不考慮堆垛機加減速的情況，第m列，第n層的貨品被運輸到出入庫貨臺的時間tm,n可以表示為：

因此，由上文假設可得，該模型L形貨位分區如圖2，貨格中的數字為該貨品從貨格經堆垛機運輸到出入庫貨臺的單位時間。

2.3 數學模型建立

為實現貨位優化，不僅要考慮堆垛機完成搬運的行程和耗時，以節約時間和能源，還要讓優化后的貨架重心盡量最低，以滿足貨架的穩定性需求。A、B、C類貨品在求解目標貨位過程中相互獨立，因此，以A類貨品為例，建立如下數學模型[10-11]：

其中，i、j分別表示原貨位和目標貨位的編號值，mi表示第i個貨品的質量，tij表示某貨品從原貨位到目標貨位所耗時間，hDes_Ai、lDes_Ai為第i個貨品在目標貨位的層和列，hSes_Ai、lDes_Ai為第i個貨品在原貨位的層和列，aij為0，1變量。式（2）表示求取堆垛機完成搬運的平均時間，式（3）表示完成搬運后的貨架重心高度。

3 求解貨位分配的遺傳算法

3.1 多目標優化問題的Pareto遺傳算法

本文優化的實質為排列問題的優化，涉及兩個無直接關聯的目標函數，存在無法比較和沖突的現象，可能得不到對兩目標函數均為最優的解，只能求出較為均衡的解，即Pareto最優解[12]。

求解多目標優化問題，傳統方法如分支定界法、動態規劃法一般僅能求解小規模問題。單目標化法如權重和法，對權系數非常敏感，在目標函數值域差別較大或估計不清的情況下，很難得到最優效果[13]。對于文中的問題，貨位達到幾百個，很容易出現組合爆炸等情況。以上方法均有不妥之處，故該文采用一種新的基于混合偏好的遺傳算法來解決該多目標優化問題。

3.2 貨位優化的遺傳算法實現過程

遺傳算法中的幾個關鍵求解過程[14-15]：

（1）初始化：根據nA、nB或nC，確定編碼長度Ln，確定初始種群數量po，最大遺傳代數maxgen，交叉概率pc、變異概率pm等參數。

（2）編碼：采用順序編碼法，根據編碼長度Ln和種群數量，生成從1到Ln的po個隨機排列（如（2，3，6，5，1，4）、（5， 2，1，4，3，6）），為便于交叉，本文生成兩個父代的初始種群，其中M和N的每一列構成一個個體Mi或Ni。

（3）計算適應度：式（2）、式（3）均為求解最小值問題，故作以下處理后作為個體適應度，適應度越大，目標越優。

其中fT、fW分別為目標函數式（2）、式（3）的適應度，Cmax、Zmax為兩個相對較大的數。此過程中，分別對兩目標函數分別完成個體評價，留作后用。

（4）交叉：由于該問題采用的是符號編碼的順序編碼方法，因此采用普通的交叉法，很可能出現非法個體。本文提出了一種新的交叉方法，能避免非法解的出現，較大程度地解決順序編碼對基因位置的敏感。方法為，隨機選擇交叉位置p，將個體編碼Mi，Ni分別分為兩段m1、m2，n1、n2，并設cm1=m1∩n2，cm2=n1∩m2，以生成子代Ci為例：拼接m1、n2構成Ci，逐個判斷cm1和cm2有交集的元素是否在cm2中。若在，用cm2中元素替換Ci中對應位置的元素，并標記去掉cm2已用的該元素；若不在，標記Ci中該位還未被替換。最后將未使用的cm2中元素，逐個填充Ci中標記未被替換的元素，得到最終合法的子代種群Ci。Di的交叉過程類似。如下所示：

（5）變異：隨機選擇個體中的兩個基因位進行交換。

（6）選擇：經過上述過程，計算子代C、D的適應度函數fT、fW，先分別選擇a個在子代C、D中適應度fW較高的子代個體，替代父代M、N中fW較低的a個個體。選擇b個在子代C、D中適應度fT較低的b個個體。此種選擇方法，能將堆垛機運行時間設置為較為優先的考慮位置，并且在此過程中通過控制a、b的值能在一定程度上較好地控制偏好程度。

4 仿真與結果分析

假設貨品原貨位為隨機存放狀態，取初始種群數量po=50，最大遺傳代數maxgen=300，交叉概率pc=0.8，變異概率pm=0.1，a=4，b=5。

（1）遺傳算法性能仿真結果。利用Matlab軟件仿真A、B、C類貨品所求平均搬運時間和重心的收斂情況如圖3～圖5所示。

圖3 A類貨品目標函數W、T的跟蹤曲線

圖4 B類貨品目標函數W、T的跟蹤曲線

圖5 C類貨品目標函數W、T的跟蹤曲線

由于初始貨位是隨機產生的，并且染色體較長，雖然多次實驗的結果較為滿意，但是為了對該算法的結果有較為全面的評估，用Matlab分別進行了20次實驗，均值的統計結果如表1。

表1 單目標與多目標函數優化前后的對比

（2）優化后倉庫出庫能力對比。在Matlab得出Pareto最優解后，即得到貨架所有在存貨品的目標貨位，即新貨位映射關系。通過FlexSim軟件仿真建模，評估了L形分類存儲策略下貨架輸出某類全部物品的堆垛機耗時和行程與原狀態下的對比。如表2所示。

表2 貨位優化后，輸出能力與原狀態對比

5 結語

本文討論了對自動化立體倉庫的貨位按照用戶需要進行L形分區的貨位優化。設計了基于混合偏好和順序編碼的遺傳算法，以尋求堆垛機平均搬運時間最短和貨架重心最低的Pareto最優解，在這過程中，提出了一種實現順序編碼法個體交叉的新算法，避免了非法個體的出現，同時保證了后代的多樣性。經過仿真驗證，該算法能達到較好收斂效果，達到優化目的。

該優化方法除了適用于L形分區的分類存儲之外，對其他任何存儲策略的轉換或一般意義的倒庫均有一定的使用價值。

[1]馬騰，王占俊.試論軍事物流與軍事后勤的關系[J].物流科技，2004（5）：69-72.

[2]馬龍，馬殷元，宋宇博，等.大型周轉型自動化倉庫的倒庫算法[J].起重運輸機械，2009（8）：41-44.

[3]Gu J，Goetschalckx M，Mcginnis L F.Research on warehouse operation：acomprehensivereview[J].EuropeanJournalof Operational Research，2007，177（1）：1-21.

[4]Gu J，Goetschalckx M，Mcginnis L F.Research on warehouse design and performance evaluation：a comprehensive review[J]. European Journal of Operational Research，2010，203（3）：539-549.

[5]Rosenblatt M J，Eynan A.Deriving the optimal boundaries for class-based automatic storage/retrieval systems[J].Management Science，1989，35（12）：1519-1524.

[6]Eynan A，Rosenblatt M J.An interleaving policy in automated storage/retrieval systems[J].International Journal of Production Research，1993，31（1）：1-18.

[7]Hausman W H，Schwarz L B，Graves S C.Optimal storage assignment in automatic warehousing systems[J].Management Science，1976，22（6）：629-638.

[8]劉昌祺，董良.自動化立體倉庫設計[M].北京：機械工業出版社，2004.

[9]張進.軍隊自動化立體倉庫系統的設計與實現[D].濟南：山東大學，2008.

[10]商允偉，裘聿皇，劉長有.自動化倉庫貨位分配優化問題研究[J].計算機工程與應用，2004，40（26）：16-17.

[11]陳璐，André L，Diane R.自動化立體倉庫中的動態儲位分配問題[J].上海交通大學學報，2011（1）：115-119.

[12]玄光男，程潤偉.遺傳算法與工程優化[M].于歆杰，周根貴，譯.北京：清華大學出版社，2004.

[13]崔遜學.多目標進化算法及其應用[M].北京：國防工業出版社，2006.

[14]冷亮，杜慶東.基于遺傳算法解決車輛最優路徑誘導問題[J].信息通信，2012（2）：14-15.

[15]管小艷.實數編碼下遺傳算法的改進及其應用[D].重慶：重慶大學，2012.

CHEN Yuanwen,WU Xiaobo,SUN Yaolei

Department of Logistical Information&Military Logistics Engineering,Logistic Engineering University of PLA,Chongqing 401311,China

To improve the military AS/RS delivery speed and running stability,this paper proposes a design that the stacker carries on a class-based L-shaped zone oriented optimization at leisure.According to user’s choice,it generates class-based L-shaped zone information.Each goods’coupled destination location is sought for when shortest stackers total run time and lowest center of gravity are treated as the target by building corresponding mathematical model.Genetic Algorithm based on hybrid preference is adopted for the multi-objective optimization problem.The results have shown that this method can greatly improve output efficiency of certain goods in a specific environment and reduce the center of gravity.Meanwhile,the study also has a certain value on the general sense of storage location reassignment.

class-based L-shaped zone;Genetic Algorithm（GA）;multi-objective optimization;storage location reassignment

為提高軍隊自動化立體倉庫出貨速度和運行穩定性，提出了在堆垛機閑時對貨位進行以分類存儲L形分區為導向的再分配優化設計。根據用戶需求，生成分類存儲的L形分類存儲目標貨位分區信息，以堆垛機總運行時間最短和貨架重心最低為目標，研究貨品新的目標耦合貨位并建立了相應數學模型，利用基于混合偏好的遺傳算法對該多目標優化問題進行了求解。結果顯示，該方法能較大提高自動化立體倉庫某類貨品在特定環境下的出庫效率并降低貨架重心。同時，該研究對一般意義的貨位再分配也具有一定價值。

分類存儲L形分區；遺傳算法；多目標優化；貨位再分配

A

TP3

10.3778/j.issn.1002-8331.1307-0338

CHEN Yuanwen,WU Xiaobo,SUN Yaolei.Optimization for military AS/RS storage location reassignment based on Genetic Algorithm.Computer Engineering and Applications,2013,49（24）：233-237.

陳元文（1987—），男，碩士研究生，主要從事自動化立體倉庫的研究。E-mail：darlingyw@126.com

2013-07-25

2013-09-10

1002-8331（2013）24-0233-05