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

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

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

1 多目標(biāo)貨位分配模型

1.1 問題描述

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

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

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

1.2 目標(biāo)分析

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

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

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

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

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

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

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

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

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

1.3 模型建立

針對(duì)以上貨位分配規(guī)劃的3個(gè)目標(biāo)，建立如下多目標(biāo)數(shù)學(xué)規(guī)劃模型:

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

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

2 算法設(shè)計(jì)

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

2.1 NSGA-II進(jìn)化算法

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

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

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

3 算例分析

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

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

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

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

3.2 求解結(jié)果

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

圖2 順序編碼示意

表2 編碼示例

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

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

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

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

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

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

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

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

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

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

表5 目標(biāo)函數(shù)值對(duì)比

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

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

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

4 結(jié)語

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

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

［2］ 程書強(qiáng).論配送中心的儲(chǔ)位規(guī)劃管理［J］.中國儲(chǔ)運(yùn)，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］.杭州:浙江大學(xué)，2006.

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

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