印 美，洪榮晶，劉 林

（1.南京工業(yè)大學機械與動力工程學院，南京 211816；2.江蘇省工業(yè)裝備數(shù)字制造及控制技術(shù)重點實驗室，南京 210009）

基于非支配遺傳算法的自動化倉庫動態(tài)貨位優(yōu)化*

印 美1，洪榮晶1，劉 林2

（1.南京工業(yè)大學機械與動力工程學院，南京 211816；2.江蘇省工業(yè)裝備數(shù)字制造及控制技術(shù)重點實驗室，南京 210009）

針對存有隨機數(shù)量貨物的機床零部件自動化立體倉庫（AS/RS）中存在的貨位規(guī)劃難題，提出了一種基于動態(tài)的倉儲模式與Pareto遺傳算法的AS/RS貨位優(yōu)化方法。該方法以能耗最低和效率最高為基本原則規(guī)劃庫區(qū)和優(yōu)化分配貨架，完成貨位編號和貨品編號；以堆垛機行駛時間和貨架穩(wěn)定性為優(yōu)化目標，建立貨位多目標優(yōu)化的數(shù)學模型；采用第二代非支配排序遺傳算法得到動態(tài)貨位優(yōu)化的Pareto最優(yōu)解。仿真實例計算結(jié)果表明，該方法使貨物的出入庫能量消耗、出入庫效率以及貨架的穩(wěn)定性等指標得到較大改善。

自動化立體倉庫；貨位動態(tài)分配；多目標優(yōu)化；遺傳算法

0 引言

自動化立體倉庫（AS/RS，Automated Storage&Retrieval System）是指人工不直接進行處理的自動存儲和取出貨物的系統(tǒng)，它具有占地面積少、貨位處理速度快、準確率高、降低庫存積壓等優(yōu)點［1］，對現(xiàn)代物流系統(tǒng)的作業(yè)效率和系統(tǒng)性能具有重要影響，在機床零部件的自動化管理系統(tǒng)中得到了廣泛應(yīng)用。

貨位分配是影響自動化立體倉庫作業(yè)效率和系統(tǒng)性能的重要因素，為了進一步提升自動化立體倉庫性能，相關(guān)學者在自動化立體倉庫貨位分配優(yōu)化方面進行了大量研究。羅鍵等［2］根據(jù)出入庫點到貨位小車的時間進行貨位分區(qū)并進行了貨位優(yōu)化。楊鵬等［3］針對多載具自動化存取系統(tǒng)的貨位分配優(yōu)化問題進行了研究。MoonG等［4］研究了存儲量變化時分類隨機存儲策略和貨物再次分類策略對存儲效率的影響，根據(jù)存儲量變化的大小選擇相應(yīng)的貨物存儲策略。Ediz等［5］以貨位分配、貨位檢索和貨位存儲保持最小化為目的建立數(shù)學模型，并基于最優(yōu)訂貨策略采用遺傳退火算法進行求解。

上述研究是在倉庫空倉情況下的靜態(tài)貨位優(yōu)化，通常情況下倉庫存儲著一定量的貨物，同時存在出入庫，需要隨時給入庫貨物分配貨位。此外，考慮到節(jié)能環(huán)保，本文將降低能耗對存儲成本的影響作為優(yōu)化目標之一。因此，綜合考慮貨位優(yōu)化過程中能耗的影響、倉庫的運行效率和貨架的穩(wěn)定性，建立多目標約束的優(yōu)化模型，提出了一種基于第二代非支配排序遺傳算法的動態(tài)貨位優(yōu)化分配方法，為出入庫貨物選擇最佳貨位。

1 自動化立體倉庫貨位問題描述

以某機電企業(yè)的立體倉庫為例，每一巷道有左右兩排貨架。假設(shè)立體倉庫每一列貨位數(shù)量一致，貨格大小相同，有n排p列q層，其貨位的長度、高度分別為l、h，并將最接近入庫臺的一排記為第一排，最接近巷道口的一列記為第1列，最底下一層記為第1層，位于第x排y列z層的貨位記為（x，y，z）（x=1，2，…，n；y=1，2，…，p；z=1，2，…，q）。針對上述倉庫布局模式，下面采用分類隨機存儲策略結(jié)合貨架受力均勻和穩(wěn)定性原則、效率原則、分散存放原則進行自動化倉庫的動態(tài)貨位分配，具體分配策略內(nèi)容如下：

（1）貨位編號。為了形成貨位的優(yōu)先級順序，需要對倉庫貨位的單位能耗進行排序，文獻［6］中給出了一種貨位單位能耗因子d（h，L）

式中，g為重力加速度/m·s-2；h為貨格的高度/m；L為貨物所在貨位到出入庫臺的水平距離/m；f為軌道與輸送小車的摩擦系數(shù)。

根據(jù)公式（1），按d（h，L）由小到大的原則對倉庫的貨位進行排序并編號。貨位編號的大小對應(yīng)于貨物存入該貨位時所消耗能量的大小，當立體倉庫的構(gòu)造和布局確定時，可以得到相應(yīng)的貨位單位質(zhì)量的能耗值，排序后單排貨位編號如圖1所示。

圖1 單排貨位編號

（2）貨位聯(lián)合編號。為了滿足相同貨品的分散存放和堆垛機運行的平衡，綜合各巷道貨架貨位進行統(tǒng)一編號。將每排貨架對應(yīng)貨位從左到右進行順序編號，形成穿梭于各巷道之間的貨位鏈，如圖2所示是聯(lián)合編號完成后貨位排序。

圖2 聯(lián)合編號示意圖

（3）貨品編號。為了使每個貨品與合理的貨位形成一一映射關(guān)系，依據(jù)貨位-貨品耦合原理［7］，需要對貨品的立方體索引號值（Cube-per-Order，COI）進行計算。由Heskett［8］給出的立方體索引號規(guī)則，并考慮到能耗的影響，將貨品的COI值計算公式修改為：

式中，Ik表示某種貨物k的COI值；Ck表示貨物k存儲總量所需的庫存容量；fk表示貨物k的出庫頻率；mk表示貨物k的質(zhì)量。

貨品鏈的形成根據(jù)公式（2），由貨品的COI值從小到大對貨品進行排序，其順序反映了貨品的出入庫頻率和質(zhì)量，然后將COI值低的貨物與貨位編號小的貨位相對應(yīng)，即將出入庫頻率高且質(zhì)量大的貨物放置在距離出入口近并且單位能耗低的貨位上，這樣既能提高出入庫的效率又能降低倉庫的運行成本。

2 貨位優(yōu)化多目標數(shù)學模型

根據(jù)貨架穩(wěn)定性原則和效率原則，以倉庫運行能耗最低、出入庫時間最小化和重心最穩(wěn)作為優(yōu)化目標，以倉庫的實際運行狀況為約束條件，建立貨位優(yōu)化的多目標數(shù)學模型。

2.1 貨位區(qū)優(yōu)化

設(shè)有s種貨品，貨位分區(qū)的目的是讓貨品的COI值Ik（k=1，2，…，s）較小的貨品放置在單位能耗低的貨位上，即使Ik與貨位編號D的乘積Q最小，數(shù)學描述為：

2.2 出入庫時間分析

假設(shè)堆垛機在X方向、Y方向和Z方向均以勻速運動的，速度分別為vx、vy、vz，不考慮制動、啟動堆垛機的耗時及伸入貨格進行操作的時間，則出入庫效率優(yōu)化的數(shù)學描述為：

式中，txyz=（x+（x/2））d/vx+max（l×y/vy，h×（z-1）/vz），表示將貨物送到分配的貨位運行時間最小。axyz=0或1，為0時表示（x，y，z）貨格沒有貨物，為1時表示（x，y，z）貨格有貨物。

2.3 貨架穩(wěn)定性分析

為了達到貨架穩(wěn)定目標，即重心最穩(wěn)，將貨物在貨架上的分布視作質(zhì)點系，其數(shù)學描述為：

式中，Gz、Gy和Gxyz分別表示貨架的垂直重心、水平重心和貨架（x，y，z）貨位處的貨物重量，式（5）為了使貨架的垂直重心接近貨架的底層，使貨架穩(wěn)定；式（6）是為了使貨架的水平重心接近貨架水平方向的中心軸線。

因此，貨架穩(wěn)定性目標的數(shù)學描述為：

由于貨架水平穩(wěn)定性和垂直穩(wěn)定性同樣重要，貨架任何一邊不穩(wěn)定都會造成嚴重后果，所以在水平和垂直方向上設(shè)置相同的系數(shù)，均為0.5。

2.4 貨位優(yōu)化數(shù)學模型

綜上所述，貨位優(yōu)化的多目標數(shù)學模型可以描述為：

貨架一共有n排p列q層，x、y、z均為正整數(shù)，分別表示貨架的排、列、層，且1＜x＜n，1＜y＜p，1＜z＜q。

3 基于遺傳算法的貨位優(yōu)化設(shè)計

由上述分析，貨位動態(tài)分配優(yōu)化模型是一個多目標優(yōu)化問題，對于多目標優(yōu)化問題，各個目標是相互沖突的，求解的關(guān)鍵是獲得由Pareto最優(yōu)解組成的集合，用遺傳算法求解多目標問題的方法主要有SPEA2、NPGA2、SPGA、NSGA、NSGA-Ⅱ等，而第二代非支配排序遺傳算法（NSGA-Ⅱ）較其他算法具良好的穩(wěn)定性、收斂性以及所求得的Pareto最優(yōu)解集分布均勻［9-10］，本文采用該算法對貨位動態(tài)分配的多目標問題進行優(yōu)化，并且在個體生成時進行約束處理，使其滿足約束條件，從而保證每個個體都是可行解。

基于NSGA-Ⅱ算法求解貨位分配優(yōu)化模型的步驟：

（1）獲取當前的庫存狀態(tài)（包括貨品與貨位的信息）；

（2）輸入當前的任務(wù)信息（包括出入庫、貨品的任務(wù)數(shù)等）；

（3）初始化并編碼。設(shè)置最大迭代次數(shù)Kmax、種群數(shù)目pop、交叉概率pc、變異概率pm。采用實數(shù)編碼，初始化群體，并計算個體適應(yīng)度值；

（4）將群體個體進行非支配分層，設(shè)置虛擬適應(yīng)度，計算個體擁擠度算子，修改虛擬適應(yīng)度，按照輪賽制選擇算子，進行選擇，形成新種群；

（5）執(zhí)行交叉、變異操作，在此對產(chǎn)生的個體進行約束處理，避免非法產(chǎn)生非法個體；

（6）精英保留策略，將父代種群Pt與子代種群Qt合并為臨時種群Rt，進行非支配分層，并計算每個個體局部擁擠距離，依據(jù)輪賽制選取pop個個體，形成新的父代種群；

（7）在此基礎(chǔ)上進行選擇、交叉、變異，形成新的子代種群。如果迭代次數(shù)大于最大次數(shù)Kmax，則迭代終止；

（8）得到優(yōu)化后的貨位坐標，進行模擬仿真驗證，根據(jù)優(yōu)化結(jié)果，對貨位重新排序。

如圖3所示，為求解貨位分配優(yōu)化的算法流程圖。

圖3 求解貨位分配優(yōu)化的算法流程圖

4 應(yīng)用實例

4.1 基本參數(shù)

某自動化立體倉庫有4排，每排8列4層，貨位的長度d=120cm，寬度l=120cm，貨位的高度h=80cm，堆垛機的水平運行速度vx=1 m/s、vy=1 m/s，垂直運行速度vz=0.5 m/s。貨物的參數(shù)如表1所示，第一列表示貨物1的質(zhì)量是20 kg，作業(yè)概率為30%，需要的貨位個數(shù)是50個，分配在B區(qū)，以此類推，已知每類貨物的質(zhì)量，作業(yè)概率和所需要的貨位數(shù)。

表1 倉庫貨物基本參數(shù)

根據(jù)貨位區(qū)分配結(jié)果，質(zhì)量越大、作業(yè)效率越大的貨物放在距離出入口越近貨位區(qū)的可能性越大，即1類貨物放在B區(qū)，2類貨物放在C區(qū)，3類貨物放在A區(qū)，倉庫貨物基本參數(shù)見表1。

仿真計算實例中，假設(shè)共有2個貨物需要入庫，其中1類貨物、2類貨物各1個。共有2個貨物要出庫，為3類貨物。貨位進行優(yōu)化前，倉庫的布局情況見圖6a，當前庫存為15個，分別是1類貨物5個，2類貨物4個，3類貨物6個。

4.2 仿真結(jié)果

仿真結(jié)果分析：按照上述NSGA-Ⅱ?qū)Χ嗄繕藘?yōu)化問題的求解方法，設(shè)置算法種群規(guī)模為200，交叉概率為0.9，變異概率為0.1，進化最大代數(shù)為100。編程并對其進行數(shù)值模擬計算，運行結(jié)果如圖4所示。

圖4 種群均值和解的追蹤曲線

圖5 目標函數(shù)解的分布

圖4 為種群均值和解追蹤曲線，圖5為目標函數(shù)解的分布圖，由圖4、圖5可見，種群進化到70代時已基本收斂，當種群進化到100代時，Pareto最優(yōu)解具有良好的多樣性，NSGA-Ⅱ的搜索結(jié)果是令人滿意的。

選取其中的三組具有代表性的Pareto最優(yōu)解作為貨位優(yōu)化方案，對比貨位優(yōu)化前后的三個目標函數(shù)值，如表2所示，較之優(yōu)化前，其貨物存儲能耗fQ、出入庫時間fE和貨架重心fG平均值分別降低了39.20%、61.84%和47.62%，在Pareto最優(yōu)解集中，三個目標之間是競爭關(guān)系，當其中一個減小時，必然會導致其他兩個目標值相應(yīng)增大。

表2 優(yōu)化前后三個目標函數(shù)值對比

4.3 模型驗證

如圖6所示，是采用數(shù)值模擬計算出的優(yōu)化前后貨位分配狀態(tài)的三維示意圖。對比優(yōu)化前后貨位分配狀態(tài)表明，優(yōu)化前的貨位布局不合理，倉庫的綜合性能比較差，貨位優(yōu)化后，貨位分配布局合理，滿足出入庫效率和貨架穩(wěn)定性要求且能耗最低。同類貨物的貨區(qū)有相應(yīng)的空缺貨位，是因為再次入庫時可以直接存放貨物到對應(yīng)貨位區(qū)，無需再進行倒庫操作。再次出庫時，僅需取出相應(yīng)貨位區(qū)的貨物即可。此外，由仿真結(jié)果知，并非所有Ik較小的貨物都放在編號較小的貨位上，這是因為貨位優(yōu)化是一個多目標的問題，多個目標相互矛盾，在求解的過程中，為了滿足多目標最優(yōu)，部分優(yōu)化目標有妥協(xié)的趨勢。

圖6 優(yōu)化前后貨位分配狀態(tài)對比

5 結(jié)論

本文提出了一種基于NSGA-Ⅱ算法的自動化立體倉庫動態(tài)貨位優(yōu)化方法，該方法在綜合考慮堆垛機運行時間最短和貨架重心最穩(wěn)的前提下，兼顧了倉庫運行能耗最低為優(yōu)化目標，通過對生成個體進行了約束處理有效地避免非法個體的產(chǎn)生，較好地解決了貨位優(yōu)化多目標之間相互沖突的妥協(xié)求解問題。仿真實例表明，所建立的模型能較好的兼顧貨位分配時的能耗、效率和貨架穩(wěn)定性要求，得到的Pareto最優(yōu)解為出入庫貨物分配了合理貨位，該優(yōu)化算法可滿足工程應(yīng)用實際需求。

［1］中國倉儲協(xié)會倉儲設(shè)施與技術(shù)應(yīng)用委員會.自動化立體倉庫應(yīng)用及發(fā)展展望［J］.物流技術(shù)與應(yīng)用，2013（4）：106-108.

［2］羅鍵，鐘壽桂，吳長慶.基于離散粒子群算法的A VS/R S貨位優(yōu)化［J］.廈門大學學報，2009，48（2）：212-215.

［3］楊朋，繆立新，戚銘堯.多載具自動化存取系統(tǒng)貨位分配優(yōu)化［J］.計算機集成制造系統(tǒng)，2011，17（5）：1050-1055.

［4］Moon G，Kim GP.Effects of relocation to AS/RS storage location policy with production quantity varition［J］.Computer and Industrial Engineering，2001，l（4）：1-13.

［5］Atmaca Ediz，Ozturk Ayla.Defining order picking policy：A storage assignment model and a simulated annealing solution in AS/RS systems［J］.Applied Mathematical Modeling，2012，37（7）：5069-5079.

［6］銀光球，何福英，盛冬發(fā).自動化立體倉庫中庫位優(yōu)化模型研究［J］.福建工程學院學報，2006，4（3）：347-350.

［7］張蹺萍，劉文煌.CIMS物流系統(tǒng)的關(guān)鍵技術(shù)［J］.計算機集成制造系統(tǒng)，1997，3（1）：22-24.

［8］Heskett J L.Cube-per-order index-a key to warehouse stock location［J］.Transportation and Distribution Management，1963，3（4）：27-31.

［9］Zitzler E，Thiele L.Multi-objective evolutionary algorithms：a comparative case study and the strength Pareto approach［J］.Evolutionary Computation，IEEE Transactions on，1999，3（4）：257-271.

［10］Kalyanmoy Deb，Amrit Pratap，Sameer Agarwa.A fast and elitist multiobjective genetic algorithm：NSGA-II［J］.IEEE Transaction on Evolutionary Computation，2002，6（2）：182-197.

（編輯 李秀敏）

Optimization for Dynamic Location Assignment of AS/RS Based on Non-dominated Sorting Genetic Algorithm

YIN Mei1，HONG Rong-jing1，LIU Lin2
（1.School of Mechanical and Power Engineering，Nanjing Tech University，Nanjing 211816，China；2.Jiangsu Key Laboratory of Digital Manufacturing for Industrial Equipment and Control Technology，Nanjing210009，China）

To solve the slotting optimization of AS/RS，in which random spaces were occupied，an optimization method based on the dynamic storage strategy and non-dominated sorting genetic algorithm II（NSGA-II）was proposed.In this method，low energy consumption and high efficiency were taken into consideration for the section assignment and the locations and goods were numbered.Then，the optimization model was established for location assignment by defining the optimal objectives as the travel time of Storage/Retrieval machines and the stability of the whole warehouse.Finally，the optimal Pareto solution of dynamic location assignment was obtained using the NSGA-II.A numerical example demonstrated the feasibility of the proposed method，which not only reduced the energy and time consumption of storage and retrieval cycle，but also improved the stability of the whole warehouse.

automated storage/retrieval system；dynamic location assignment；multi-objectives optimization；non-dominated sorting genetic algorithm

TH246；TG65

A

1001-2265（2015）03-0031-04 DOI：10.13462/j.cnki.mmtamt.2015.03.009

2014-05-30；

2014-06-03

國家自然科學基金資助項目（51375222）

印美（1989—），女，江蘇泰興人，南京工業(yè)大學碩士研究生，研究方向為機械制造及其自動化，（E-mail）ymclara@sina.com。