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

陳元文，吳曉波，孫耀磊

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

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

陳元文，吳曉波，孫耀磊

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

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

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

1 存儲策略與分區(qū)介紹

1.1 軍隊(duì)自動化立體倉庫特點(diǎn)與現(xiàn)狀

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

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

1.2 基本存儲策略與L形分類存儲貨位分區(qū)

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

本文鑒于軍隊(duì)物資類別明顯，物資需求與時(shí)間或環(huán)境有較大關(guān)聯(lián)性，因此采用分類存儲策略。在貨架的分區(qū)上，每個(gè)巷道兩側(cè)的貨架構(gòu)成一個(gè)分區(qū)，每個(gè)分區(qū)所存貨物的類別和數(shù)量基本一致。該設(shè)計(jì)能較大程度地提高倉庫的穩(wěn)定性，即使某一巷道堆垛機(jī)出現(xiàn)故障，對倉庫的正常作業(yè)也不構(gòu)成較大影響，并且，由于多個(gè)堆垛機(jī)可并行出貨，保障了最大出貨效率。

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

2 貨位優(yōu)化模型

2.1 貨位優(yōu)化過程

在存貨品具有季節(jié)、戰(zhàn)時(shí)需求度等屬性，以季節(jié)更替為例，當(dāng)夏季來臨時(shí)，軍隊(duì)倉庫需要將夏季物品搬運(yùn)到A區(qū)，方便出庫，春秋季和冬季物品分別搬運(yùn)到B、C區(qū)。

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

圖2 三類貨物按L形分區(qū)分類存儲示意圖

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

2.2 貨架等基本參數(shù)假設(shè)和L形貨位分區(qū)

貨架等基本參數(shù)假設(shè)[8-9]：

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

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

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

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

L形貨位分區(qū)：

由于堆垛機(jī)可以在水平和垂方向同時(shí)運(yùn)動，不考慮堆垛機(jī)加減速的情況，第m列，第n層的貨品被運(yùn)輸?shù)匠鋈霂熵浥_的時(shí)間tm,n可以表示為：

因此，由上文假設(shè)可得，該模型L形貨位分區(qū)如圖2，貨格中的數(shù)字為該貨品從貨格經(jīng)堆垛機(jī)運(yùn)輸?shù)匠鋈霂熵浥_的單位時(shí)間。

2.3 數(shù)學(xué)模型建立

為實(shí)現(xiàn)貨位優(yōu)化，不僅要考慮堆垛機(jī)完成搬運(yùn)的行程和耗時(shí)，以節(jié)約時(shí)間和能源，還要讓優(yōu)化后的貨架重心盡量最低，以滿足貨架的穩(wěn)定性需求。A、B、C類貨品在求解目標(biāo)貨位過程中相互獨(dú)立，因此，以A類貨品為例，建立如下數(shù)學(xué)模型[10-11]：

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

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

3.1 多目標(biāo)優(yōu)化問題的Pareto遺傳算法

本文優(yōu)化的實(shí)質(zhì)為排列問題的優(yōu)化，涉及兩個(gè)無直接關(guān)聯(lián)的目標(biāo)函數(shù)，存在無法比較和沖突的現(xiàn)象，可能得不到對兩目標(biāo)函數(shù)均為最優(yōu)的解，只能求出較為均衡的解，即Pareto最優(yōu)解[12]。

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

3.2 貨位優(yōu)化的遺傳算法實(shí)現(xiàn)過程

遺傳算法中的幾個(gè)關(guān)鍵求解過程[14-15]：

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

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

（3）計(jì)算適應(yīng)度：式（2）、式（3）均為求解最小值問題，故作以下處理后作為個(gè)體適應(yīng)度，適應(yīng)度越大，目標(biāo)越優(yōu)。

其中fT、fW分別為目標(biāo)函數(shù)式（2）、式（3）的適應(yīng)度，Cmax、Zmax為兩個(gè)相對較大的數(shù)。此過程中，分別對兩目標(biāo)函數(shù)分別完成個(gè)體評價(jià)，留作后用。

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

（5）變異：隨機(jī)選擇個(gè)體中的兩個(gè)基因位進(jìn)行交換。

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

4 仿真與結(jié)果分析

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

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

圖3 A類貨品目標(biāo)函數(shù)W、T的跟蹤曲線

圖4 B類貨品目標(biāo)函數(shù)W、T的跟蹤曲線

圖5 C類貨品目標(biāo)函數(shù)W、T的跟蹤曲線

由于初始貨位是隨機(jī)產(chǎn)生的，并且染色體較長，雖然多次實(shí)驗(yàn)的結(jié)果較為滿意，但是為了對該算法的結(jié)果有較為全面的評估，用Matlab分別進(jìn)行了20次實(shí)驗(yàn)，均值的統(tǒng)計(jì)結(jié)果如表1。

表1 單目標(biāo)與多目標(biāo)函數(shù)優(yōu)化前后的對比

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

表2 貨位優(yōu)化后，輸出能力與原狀態(tài)對比

5 結(jié)語

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

該優(yōu)化方法除了適用于L形分區(qū)的分類存儲之外，對其他任何存儲策略的轉(zhuǎn)換或一般意義的倒庫均有一定的使用價(jià)值。

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

[2]馬龍，馬殷元，宋宇博，等.大型周轉(zhuǎn)型自動化倉庫的倒庫算法[J].起重運(yùn)輸機(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]劉昌祺，董良.自動化立體倉庫設(shè)計(jì)[M].北京：機(jī)械工業(yè)出版社，2004.

[9]張進(jìn).軍隊(duì)自動化立體倉庫系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].濟(jì)南：山東大學(xué)，2008.

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

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

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

[13]崔遜學(xué).多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京：國防工業(yè)出版社，2006.

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

[15]管小艷.實(shí)數(shù)編碼下遺傳算法的改進(jìn)及其應(yīng)用[D].重慶：重慶大學(xué)，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

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

分類存儲L形分區(qū)；遺傳算法；多目標(biāo)優(yōu)化；貨位再分配

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