基于NSGA-II的維修器材倉庫多目標貨位分配規(guī)劃

于戰(zhàn)果，鄧 威，張 堯，楊冰峰

(1.軍事交通學院后勤裝備勤務(wù)保障中心，天津300161;2.軍事交通學院 研究生管理大隊，天津300161)

存儲是倉庫的一項主要功能，縮短出入庫的 搬運距離，提高作業(yè)效率，提升器材保管水平的關(guān)鍵就在于科學合理的貨位管理，也就是將各種器材依據(jù)一定的原則安排在貨架的指定位置，以實現(xiàn)器材搬運的低成本、高效率［1－2］。

1 多目標貨位分配模型

1.1 問題描述

在一個包含a排b列c層的貨架存儲區(qū)，存儲區(qū)貨架布置如圖1所示，共有n個貨位，需要存儲m種器材，每種器材需要Ni個貨位，其中

圖1 貨架區(qū)簡單立體示意

現(xiàn)在需要按照一定的原則將這m種器材合理地存放到貨架上。最靠近出口的排為第一排，最靠近出口的列為第一列，最低層為第一層。位于i排 j列 k 層的貨位坐標為(xijk，yijk，zijk)，坐標(0，0，0)為該存儲區(qū)的出口，記為I/O口，貨位的長、寬、高分別為貨位沿X、Y、Z軸的長度。根據(jù)問題的實際進行如下限定:存儲區(qū)只有一個出入口，每個貨格只存放一種器材，器材的尺寸能夠放入貨位。

1.2 目標分析

根據(jù)維修器材的管理要求和倉庫的實際情況，針對器材存儲規(guī)劃時能夠進行量化分析的原則，在進行存儲貨位分配規(guī)劃時主要考慮以下3個目標。

(1)目標一:搬運距離最短。就是器材存儲到貨架上后，在分揀搬運出庫時減少作業(yè)人員行走的總路程。解決此目標的基本思想是將出庫數(shù)量大且出庫次數(shù)多的器材放在離出入口較近的貨位上。定義Ki為順序編號為i的器材的年平均出庫量，則Ki越高i器材所存貨位離出入庫距離越小。定義Fi為順序編號為i的器材的年平均出庫頻次，即指i器材一年的平均出庫次數(shù)，F(xiàn)i越高i器材所存貨位離出入庫距離也應(yīng)該越小。

若要使總的搬運距離最小，得到目標函數(shù):

式中:n為需要存放在貨架上的器材種類數(shù)，若一種器材需要多個貨位，則看成是多種器材;l為貨架區(qū)貨位數(shù)量，一般有n≤l，即保證每種器材都有位置進行存放;dj為編號為j的貨位到出入口的距離;Xij=0或1，Xij=1為i種器材存放在編號為j的貨位上，反之Xij=0。

(2)目標二:貨架總質(zhì)心最低。若將較重器材放在貨架的上層，而相對較輕的器材放在貨架的下層，上重下輕的結(jié)構(gòu)會導(dǎo)致貨架發(fā)生傾覆的可能性，而且在人工揀選系統(tǒng)中，較重器材存放位置較高也不便于從貨架上取出，因此降低貨架總質(zhì)心，器材存放上輕下重也是必須考慮的目標。假設(shè)有 n 種器材，質(zhì)量分別為 m1，m2，…，mn，且分別位于h1，h2，…，hn高度，則此n種器材的總質(zhì)心 h可以使用如下公式計算:

貨位 j的位置坐標為(xj，yj，zj)，則貨架的總質(zhì)心為

式中:mi為第i種器材的質(zhì)量，若同種器材只需要一個貨位，則為器材的入庫質(zhì)量，若需求多個貨位，則為該種器材單個貨位最大存儲質(zhì)量。由于這里的目標是提高貨架的穩(wěn)定性，器材存放上輕下重，因此只需考慮豎直方向上的中心坐標最小，水平方向上無需考慮。

(3)目標三:同種裝備維修器材距離近。同一裝備的多種周轉(zhuǎn)維修器材經(jīng)常會同時出庫，存儲于相鄰貨位能夠方便揀選。假設(shè)某一專業(yè)共有k種裝備，第i種裝備共有Ni種周轉(zhuǎn)維修器材，每種維修器材貨位的空間位置坐標為(x，y，z)，則Ni種維修器材的位置組合向量為

定義rj為第j種器材和該類器材中心的偏離距離，則

1.3 模型建立

針對以上貨位分配規(guī)劃的3個目標，建立如下多目標數(shù)學規(guī)劃模型:

式中Rg為第g種裝備維修器材的總偏離距離。

以上通過建立一個多目標數(shù)學規(guī)劃模型對貨位分配規(guī)劃的優(yōu)劣性進行數(shù)學描述，此數(shù)學模型能夠有效地反映出貨位分配的3個指標要求，實現(xiàn)從“現(xiàn)實問題”向“抽象數(shù)學空間”的轉(zhuǎn)變。

2 算法設(shè)計

本文建立的是一個多目標規(guī)劃問題，求解多目標問題主要有兩種基本思路:一是先決策再優(yōu)化，最為代表的是權(quán)重系數(shù)法;二是先優(yōu)化再決策，常用的是多目標進化算法。由于先決策的方法需要掌握問題的先驗信息，而通常獲得這些信息是比較困難的，這里采用先優(yōu)化再決策的方法。算法分為兩個階段:第一階段通過NSGA－II進化算法得到多目標問題的Pareto解集，即得到多個貨位分配方案;第二階段運用Topsis方法對多個方案進行優(yōu)選。

2.1 NSGA-II進化算法

目前多目標進化算法有很多，Kalyanmoy Deb的帶精英策略的快速非支配排序遺傳算法［3］(nondominated sorting genetic algorithm II，NSGAII)是應(yīng)用最廣泛、求解效果最好的一種。NSGA-II是一種求解多目標問題的遺傳算法，由Deb等人在2002年在對NSGA算法改進的基礎(chǔ)上提出。NSGA-II算法采用個體的非支配層次作為適應(yīng)度，適應(yīng)度是通過快速非支配排序得到的。在維護種群的多樣性方面，NSGA-II首次引入了擁擠距離的方法，還使用了(μ+λ)的精英保留策略。NSGA-II中兩個最重要的函數(shù)是快速非支配排序函數(shù)和擁擠距離計算函數(shù)，具體計算方法可參見文獻［4］。

2.2 基于Topsis的方案優(yōu)選

Topsis法是 C.L.Hwang和 K.Yoon于1981 年提出，是依據(jù)各方案到理想解的距離進行排序選優(yōu)的方法，適用于解決多屬性決策問題。在本文中，多目標進化算法求得的非劣解集作為待決策方案，3個目標作為各方案的屬性，目標值是各屬性的取值，屬性權(quán)值是決策者的偏好信息，因此運用Topsis方法是可行的。具體計算方法可參見文獻［5］。

3 算例分析

3.1 基礎(chǔ)數(shù)據(jù)

應(yīng)用上述建立的模型和求解方法對某裝備維修器材倉庫倉儲區(qū)初始貨位分配進行規(guī)劃。每排貨架為10列5層，單個貨格的長寬高均為一個單位，巷道寬度為兩個單位。這里以兩排貨架共100個貨位入庫100種器材為例進行規(guī)劃。各種器材的基礎(chǔ)信息見表1。

表1 器材基礎(chǔ)信息

為便于使用遺傳算法求解，對貨位采用如下方式的順序編碼，以b列c層為例，若有多排，順序號依次順延(如圖2所示)。

3.2 求解結(jié)果

編碼是建立問題空間和模型空間聯(lián)系的樞紐，針對問題特點，本文采用符號編碼方式。器材編碼順序不變，通過變換貨位編碼的不同順序，可以得到不同的染色體(編碼示例見表2，遺傳算法控制參數(shù)見表3)。

圖2 順序編碼示意

表2 編碼示例

表3 遺傳算法控制參數(shù)

通過在Matlab 7.5平臺上編寫程序?qū)崿F(xiàn)上述算法。其中選擇、交叉、變異等遺傳操作同基本遺傳算法，具體可參見文獻［6］。結(jié)果如圖3—6所示。

圖3 第一目標函數(shù)性能迭代

通過3個目標函數(shù)的性能迭代圖可以發(fā)現(xiàn)，隨著迭代次數(shù)的增加，3個目標值均出現(xiàn)了明顯的下降，到1 000代之后逐漸趨于穩(wěn)定，相對于初始隨機生成的貨位分配方案，最終方案的目標值顯然較好，說明本文方法具有較好的優(yōu)化效果。

通過上文的計算，得到的Pareto最優(yōu)解集以Excel的形式輸出。由于問題的規(guī)模較大，得到的最優(yōu)解集中解的數(shù)量較多，考慮到本文3個目標中更傾向于使第一目標達到最優(yōu)，通過對第一目標函數(shù)值進行升序排列，從中選取前30個，每個解都對應(yīng)一種貨位分配方案(見表4)。

圖4 第二目標函數(shù)性能迭代

圖5 第三目標函數(shù)性能迭代

根據(jù)2.2節(jié)中的Topsis方法，把求解到的30個解作為決策方案，把3個目標作為方案的屬性，屬性權(quán)值為［0.5，0.3，0.2］，通過編程分析，得到最佳協(xié)調(diào)解為序號20。

通過表5對比可以看出，在多目標模型作用下，最優(yōu)結(jié)果中3個目標函數(shù)值相對于初始貨位分配方案均明顯降低，證明了本文求解方法的可行性。

表4 最優(yōu)方案目標函數(shù)值

表5 目標函數(shù)值對比

對貨位分配最優(yōu)結(jié)果對應(yīng)染色體進行解碼，得到貨位分配方案如圖7、圖8所示。

圖7 第一排貨架器材位置分布

圖8 第二排貨架器材位置分布

4 結(jié)語

本文通過對某器材倉庫貨位管理中的多個要求進行量化分析，建立了貨位分配的多目標規(guī)劃模型。運用NSGA-II算法得到多目標問題的Pareto解集，即多個貨位分配方案，可供決策者選擇。根據(jù)決策者偏好信息應(yīng)用Topsis方法得到帶附加條件的最優(yōu)解。經(jīng)驗證本方法能夠較好的解決多目標貨位分配問題。本文中遺傳算法的控制參數(shù)是依據(jù)經(jīng)驗設(shè)定的，可能產(chǎn)生早熟情況，并不能保證收斂于最優(yōu)Pareto前端。通過設(shè)置不同的參數(shù)進行求解結(jié)果的對比來確定最佳的參數(shù)將是下一步研究的方向。

［1］ 鄭凌鶯.醫(yī)藥物流中心倉庫貨位優(yōu)化系統(tǒng)的研究［D］.上海:上海交通大學，2005.

［2］ 程書強.論配送中心的儲位規(guī)劃管理［J］.中國儲運，2003(3):50-53.

［3］ Deb K，Pratap A，Agawal S，et al.A fast and elitist multiobjective genetic algorithm NSGA － II［J］.IEEE Transaction on Evolutionary Computation，2002，6(2):182-197.

［4］ 高媛.非支配排序遺傳算法(NSGA)的研究與應(yīng)用［D］.杭州:浙江大學，2006.

［5］ 石黎明，張雄，李少華.基于熵權(quán)的TOPSIS法在艦載飛機搶修決策中的運用［J］.系統(tǒng)仿真技術(shù)，2013，9(4):350-354.

［6］ 雷英杰.MATLAB遺傳算法工具箱及其應(yīng)用［M］.西安:西安電子科技大學出版社，2005:62-94.