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

印 美，洪榮晶，劉 林

（1.南京工業(yè)大學(xué)機(jī)械與動(dòng)力工程學(xué)院，南京 211816；2.江蘇省工業(yè)裝備數(shù)字制造及控制技術(shù)重點(diǎn)實(shí)驗(yàn)室，南京 210009）

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

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

（1.南京工業(yè)大學(xué)機(jī)械與動(dòng)力工程學(xué)院，南京 211816；2.江蘇省工業(yè)裝備數(shù)字制造及控制技術(shù)重點(diǎn)實(shí)驗(yàn)室，南京 210009）

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

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

0 引言

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

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

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

1 自動(dòng)化立體倉庫貨位問題描述

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

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

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

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

圖1 單排貨位編號(hào)

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

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

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

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

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

2 貨位優(yōu)化多目標(biāo)數(shù)學(xué)模型

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

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

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

2.2 出入庫時(shí)間分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 應(yīng)用實(shí)例

4.1 基本參數(shù)

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

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

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

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

4.2 仿真結(jié)果

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

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

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

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

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

表2 優(yōu)化前后三個(gè)目標(biāo)函數(shù)值對(duì)比

4.3 模型驗(yàn)證

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

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

5 結(jié)論

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

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

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

［3］楊朋，繆立新，戚銘堯.多載具自動(dòng)化存取系統(tǒng)貨位分配優(yōu)化［J］.計(jì)算機(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ā).自動(dòng)化立體倉庫中庫位優(yōu)化模型研究［J］.福建工程學(xué)院學(xué)報(bào)，2006，4（3）：347-350.

［7］張蹺萍，劉文煌.CIMS物流系統(tǒng)的關(guān)鍵技術(shù)［J］.計(jì)算機(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

國家自然科學(xué)基金資助項(xiàng)目（51375222）

印美（1989—），女，江蘇泰興人，南京工業(yè)大學(xué)碩士研究生，研究方向?yàn)闄C(jī)械制造及其自動(dòng)化，（E-mail）ymclara@sina.com。