（陸軍勤務(wù)學(xué)院 重慶 401331）

1 引言

被裝是軍隊(duì)裝備的常服、禮服、作訓(xùn)防護(hù)服、標(biāo)志服飾、臥具、裝具的總稱，是軍人作戰(zhàn)、訓(xùn)練、生活的重要物質(zhì)基礎(chǔ)[1]。貨位優(yōu)化是指給儲存的各種物資分配合適的貨位，使總體儲存效益達(dá)到最優(yōu)[2]。被裝物資的貨位分配問題影響著揀選效率和出入庫效率，與被裝保障水平緊密聯(lián)系。貨位優(yōu)化以提升倉儲作業(yè)效率和空間利用率、降低成本、增加貨架穩(wěn)定性為目標(biāo)。因此，貨位優(yōu)化問題通常是多目標(biāo)優(yōu)化問題，需要通過建立數(shù)學(xué)模型，并運(yùn)用算法求得最優(yōu)解。本文將建立被裝物資貨位優(yōu)化的模型，并使用遺傳算法求解模型，得到最優(yōu)的貨位分配方案。

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

2.1 問題描述與條件假設(shè)

分配貨位要遵循兩條重要的原則[3～4]：1）周轉(zhuǎn)率原則，將周轉(zhuǎn)率高的物資安排在離出口較近的貨位上。2）重心原則，考慮貨架在垂直和水平方向上的穩(wěn)定性，將重量大的物資儲存在低層，在水平方向上的擺放也要盡量均勻。根據(jù)這兩條原則，將優(yōu)化目標(biāo)定為縮短物資出庫時(shí)間和增加貨架穩(wěn)定性，模型假設(shè)以自動(dòng)化立體庫為背景，但對于采用貨架儲存物資的普通倉庫也有借鑒作用[5]。

現(xiàn)假設(shè)某座庫房中有n排貨架，每個(gè)貨架有m列貨格和l層，那么這座庫房總的貨位數(shù)為nml個(gè) 。 用 x，y，z（x∈[1 ，n]，y∈[1 ，m]，z∈[1 ，l]，x，y，z∈Z）分別表示貨位所在的排、列、層，每個(gè)貨位的坐標(biāo)可以表示為（x，y，z），比如（2，5，6）就表示第2排第5列第6層的貨位。此外，假設(shè)每個(gè)貨位只存放一個(gè)托盤，每個(gè)托盤上只儲存一箱物資。同時(shí)，為方便計(jì)算，忽略堆垛機(jī)在取貨時(shí)伸縮機(jī)械臂所耗費(fèi)的時(shí)間，且在每排貨架的同一側(cè)作業(yè)。一些涉及到計(jì)算的其他參數(shù)的假設(shè)情況如表1所示。

表1 各參數(shù)的值

2.2 建立模型

第一個(gè)優(yōu)化目標(biāo)是減少出庫時(shí)間，在堆垛機(jī)運(yùn)行速度一定的情況下，要減少出庫時(shí)間就要縮短所有物資出庫移動(dòng)距離之和[6]。為了簡化計(jì)算，假設(shè)只有一臺堆垛機(jī)。堆垛機(jī)從原點(diǎn)（0，0，0）出發(fā)，先沿x軸方向水平運(yùn)行，到達(dá)目標(biāo)貨位所在排時(shí)，進(jìn)入巷道內(nèi)沿y軸水平運(yùn)行，到達(dá)目標(biāo)貨位所在列時(shí)，再沿z軸垂直運(yùn)行，最終到達(dá)目標(biāo)貨位（x，y，z）。堆垛機(jī)在x軸方向運(yùn)行時(shí)，要經(jīng)過（x-1）個(gè)貨格，同時(shí)考慮到每兩排貨架間的距離，即巷道的寬度為S0，假設(shè)堆垛機(jī)運(yùn)行到巷道口中心位置再進(jìn)入，則所經(jīng)過的巷道數(shù)為（x-1-1/2）個(gè)。堆垛機(jī)進(jìn)入巷道后，首先運(yùn)行到目標(biāo)貨位所在列的第一層貨格的底部中心位置，然后再開始上升。因此，在前往目標(biāo)貨位所在列的過程中，堆垛機(jī)要經(jīng)過的貨格數(shù)為（y-1/2）個(gè)。到達(dá)目標(biāo)貨位所在列后，堆垛機(jī)在上升過程中要經(jīng)過的貨格數(shù)為（z-1）個(gè)。堆垛機(jī)在水平方向和垂直方向上的運(yùn)行速度分別為Vh和VV，因此貨位坐標(biāo)為（x，y，z）的物資從貨位到出口的移動(dòng)時(shí)間ti為

將貨架上所儲存的物資搬運(yùn)到出口所耗費(fèi)的總時(shí)間還與各種物資的周轉(zhuǎn)率Pi有關(guān)，即，因此，物資出庫效率優(yōu)化的目標(biāo)函數(shù)可表示為

第二個(gè)優(yōu)化目標(biāo)是提高貨架穩(wěn)定性。貨架的穩(wěn)定性由其垂直重心和水平重心決定，假設(shè)質(zhì)量為G1、G2……Gn的物資被分別存放在高度為H1、H2……Hn的貨位上，那么此貨架的垂直重心位置為

一個(gè)貨格的重心通常在其幾何中心，要使整個(gè)貨架在水平方向上的穩(wěn)定性達(dá)到最佳，就要盡量讓其水平重心靠近水平方向的中心位置，即mL0/2（貨架長度的1/2）處。因此，貨架水平重心位置Gy可表示為

為了優(yōu)化貨架整體穩(wěn)定性，要使Gz和Gy之加權(quán)和取最小值，假設(shè)兩者的權(quán)重c1和c2均為0.5。綜上，貨架穩(wěn)定性優(yōu)化的目標(biāo)函數(shù)可表示為

綜上，建立貨位優(yōu)化的多目標(biāo)模型如下：

其中，1≤x≤n，1≤y≤m，1≤z≤l，且均為整數(shù)。

3 運(yùn)用遺傳算法求解模型

根據(jù)多目標(biāo)優(yōu)化問題的本質(zhì)，各個(gè)目標(biāo)函數(shù)之間是存在相互沖突的關(guān)系的，不存在使所有目標(biāo)函數(shù)都達(dá)到最優(yōu)狀態(tài)的解，因此只能取得一組折中解，即帕累托最優(yōu)解[7]。在解決多目標(biāo)優(yōu)化問題上，遺傳算法具有獨(dú)特的優(yōu)勢：1）可廣泛地對可行解進(jìn)行表示，直接對問題的結(jié)構(gòu)對象進(jìn)行操作。2）群體搜索。不同于許多傳統(tǒng)的算法，遺傳算法可以同時(shí)處理多個(gè)個(gè)體并對解進(jìn)行評估。3）限制條件較少。遺傳操作的基礎(chǔ)是適應(yīng)度函數(shù)值，不受函數(shù)連續(xù)性的約束。4）不易陷入局部最優(yōu)，找到全局最優(yōu)解的能力較強(qiáng)。因此，遺傳算法適用于解決被裝物資貨位優(yōu)化問題。

3.1 遺傳算法基本原理

遺傳算法（Genetic Algorithm，GA）是一種模擬生物的遺傳和進(jìn)化機(jī)制的自適應(yīng)概率優(yōu)化技術(shù)，這個(gè)概念最早在1967年由美國密歇根大學(xué)的學(xué)生Bagley首次提出，Bagley的老師Holland教授在1975年提出了遺傳算法的系統(tǒng)論述。生物通過染色體的交叉和變異完成進(jìn)化，遺傳算法通過特定的編碼方法產(chǎn)生“染色體”，并對“染色體”上的基因進(jìn)行選擇、交叉、變異，通過對個(gè)體進(jìn)行評價(jià)篩選，最后找到最好的“染色體”。它從一個(gè)隨機(jī)的初始種群出發(fā)，對其中的個(gè)體進(jìn)行選擇、交叉、變異，形成新一代種群。通過數(shù)次迭代，種群不斷進(jìn)化，最后收斂得到適應(yīng)能力最強(qiáng)的種群，即得到問題的最優(yōu)解[8]。遺傳算法的主要運(yùn)行步驟如下。

第一步，編碼。確定所要解決的問題的變量及相關(guān)參數(shù)后，變量x即可作為個(gè)體的“表現(xiàn)型”，用特定的編碼方式對x進(jìn)行處理后得到的字符串即為它的“基因型”，編碼就是表現(xiàn)型與基因型之間的映射，它是遺傳算法識別個(gè)體的基礎(chǔ)。例如，采用二進(jìn)制編碼方法時(shí)，將十進(jìn)制數(shù)1850轉(zhuǎn)化為二進(jìn)制數(shù)11100111010的過程就是編碼，十進(jìn)制數(shù)是表現(xiàn)型，二進(jìn)制數(shù)是基因型。

第二步，產(chǎn)生初始種群。隨機(jī)生成n個(gè)初始個(gè)體，即特定的結(jié)構(gòu)數(shù)據(jù)，可以是二進(jìn)制串，也可以是實(shí)數(shù)結(jié)構(gòu)，由這些個(gè)體構(gòu)成初始種群。遺傳算法以初始種群為起點(diǎn)進(jìn)行迭代，迭代次數(shù)根據(jù)問題復(fù)雜程度確定，對于比較簡單的問題，通常經(jīng)過50至200次迭代就可找到最優(yōu)解；對于一些很復(fù)雜的問題，迭代次數(shù)可達(dá)到數(shù)千次甚至上萬次。

第三步，計(jì)算個(gè)體的適應(yīng)度。適應(yīng)度值表明個(gè)體的優(yōu)劣程度[9]。將個(gè)體代入到目標(biāo)函數(shù)中進(jìn)行計(jì)算，得到目標(biāo)函數(shù)值。通常目標(biāo)函數(shù)是求得最小解，若優(yōu)化問題的目標(biāo)是求最小解，則無需轉(zhuǎn)化。若優(yōu)化問題的目標(biāo)是求最大解，則需對目標(biāo)函數(shù)值進(jìn)行轉(zhuǎn)化，獲得個(gè)體的適應(yīng)度值。

第四步，選擇。根據(jù)個(gè)體的適應(yīng)度值，通過特定的方法從當(dāng)前種群中選擇適應(yīng)度值較高的個(gè)體，這些個(gè)體將成為父代參與產(chǎn)生子代個(gè)體。適應(yīng)能力強(qiáng)的個(gè)體為下一代提供優(yōu)良基因的概率更大，體現(xiàn)出了達(dá)爾文進(jìn)化學(xué)說中適者生存的思想。

第五步，交叉。以設(shè)定好的交叉概率Pc對不同父代個(gè)體的染色體片段進(jìn)行交換，這樣子代個(gè)體將擁有父代個(gè)體的組合特性。交叉操作是將父代優(yōu)良基因遺傳給子代的關(guān)鍵，能提高種群的適應(yīng)能力。

第六步，變異。以設(shè)定好的變異概率Pm對隨機(jī)選中的個(gè)體的結(jié)構(gòu)數(shù)據(jù)進(jìn)行隨機(jī)的改變，即對某個(gè)體染色體上隨機(jī)位置的基因值進(jìn)行改變，例如將二進(jìn)制串11100111010中第3位上的1變異為0，其對應(yīng)的表現(xiàn)型就由十進(jìn)制數(shù)1850變成了1594。自然界中變異概率很低，但變異能增加種群基因的多樣性。

經(jīng)過上述操作后得到的群體進(jìn)入下一次迭代，當(dāng)?shù)螖?shù)達(dá)到設(shè)定的上限值時(shí)，遺傳算法終止，輸出最適應(yīng)的個(gè)體，得到最優(yōu)解[10]。

3.2 貨位優(yōu)化的相關(guān)數(shù)據(jù)

以自動(dòng)化立體庫為例，選取其中一個(gè)區(qū)域的貨架作為優(yōu)化樣本，在這個(gè)區(qū)域中有3排貨架，每排貨架有5列、6層。同時(shí)，選取10種品名的被裝作為儲存在這一區(qū)域貨架上的物資，這10種被裝物資的初始貨位分配情況如表2所示。在這10種被裝物資中，囊括了軍服、軍鞋、裝具等多個(gè)品種，在周轉(zhuǎn)率、重量方面跨度較大，具有很好的代表性，適于作為貨位優(yōu)化的樣本。這些被裝物資的初始貨位是隨機(jī)分配的。

表2 被裝物資初始貨位分配情況

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

1）編碼。本文采用實(shí)數(shù)編碼，一條染色體表示一種貨位分配結(jié)果，從左至右依次包含一個(gè)貨位的坐標(biāo)、儲存在該貨位上的物資的周轉(zhuǎn)率、物資的質(zhì)量，其結(jié)構(gòu)為xyzpiGi。例如，染色體1 2 1 0.2 18就是一個(gè)解，表示周轉(zhuǎn)率為0.2，質(zhì)量為18kg的被裝品種被分配到坐標(biāo)為（1，2，1）的貨位上進(jìn)行儲存。

2）生成初始種群。確定編碼方法就得到了個(gè)體的表示方法。染色體1 2 1 0.2 18代表一種貨位分配結(jié)果，10條染色體組成一個(gè)個(gè)體，即一個(gè)包含全部10種被裝物資貨位分配結(jié)果的方案，初始種群就是由若干個(gè)個(gè)體組成的[11]。初始種群大小設(shè)定為50個(gè)，即隨機(jī)產(chǎn)生50個(gè)貨位分配方案。將x、y、z進(jìn)行排列組合，產(chǎn)生n*m*l（n=3，m=5，l=6）種貨位坐標(biāo)，即90種貨位坐標(biāo)，將其儲存在一個(gè)90×3的矩陣A中。然后，生成[1，90]之間的隨機(jī)整數(shù)，取前10個(gè)數(shù)作為矩陣A的行向量序號，例如前10個(gè)數(shù)為 8，2，10，7，4，3，6，9，5，1，就取矩陣A的第8，2，10，7，4，3，6，9，5，1行為10種被裝物資的貨位坐標(biāo)，與它們的周轉(zhuǎn)率和質(zhì)量結(jié)合起來，成為一個(gè)10×5的矩陣，每一個(gè)行向量代表一個(gè)貨位分配結(jié)果，整個(gè)矩陣表示一個(gè)個(gè)體，這樣就生成了一個(gè)初始個(gè)體：

將這個(gè)方法循環(huán)運(yùn)行50次，就得到了含有50個(gè)個(gè)體的初始種群。

3）計(jì)算目標(biāo)函數(shù)。前文已建立了被裝物資貨位優(yōu)化模型，可直接將個(gè)體代入模型進(jìn)行計(jì)算，得到該個(gè)體的目標(biāo)函數(shù)值。個(gè)體的目標(biāo)函數(shù)值越小，則表示該個(gè)體適應(yīng)度越大，即貨位分配結(jié)果更優(yōu)。

4）遺傳操作。（1）選擇：先使用RANKING函數(shù)對個(gè)體進(jìn)行適應(yīng)度值的分配，然后用根據(jù)適應(yīng)度值大小FitnVi進(jìn)行選擇。若總共有u個(gè)個(gè)體，一個(gè)個(gè)體被選擇的概率為

適應(yīng)度值較大的個(gè)體可能被多次選擇。（2）交叉：對當(dāng)前種群中的個(gè)體進(jìn)行重組，每個(gè)矩陣中奇數(shù)行和偶數(shù)行進(jìn)行配對重組，得到新的個(gè)體。由于本文要解決的問題是組合優(yōu)化問題，被裝物資的周轉(zhuǎn)率和質(zhì)量是一一對應(yīng)的，不能改變，因此只有它們的貨位坐標(biāo)進(jìn)行交叉，本文把交叉概率pc設(shè)定為0.6。（3）變異：先將貨位坐標(biāo)轉(zhuǎn)化為二進(jìn)制數(shù)，再使用變異函數(shù)對其進(jìn)行變異。變異完成后，再將二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)，獲得變異后的貨位坐標(biāo)。

5）迭代。設(shè)定迭代次數(shù)為50，當(dāng)上述操作完成一次后，進(jìn)入下一次迭代，直到迭代次數(shù)滿50次為止。在迭代過程中，目標(biāo)函數(shù)會逐漸收斂，最后得到最優(yōu)解。

4 使用Matlab運(yùn)行遺傳算法

以Matlab7.1作為實(shí)現(xiàn)遺傳算法的軟件，加載由英國謝菲爾德大學(xué)開發(fā)的遺傳算法工具箱GAT?BX，這個(gè)工具箱中包含了實(shí)現(xiàn)遺傳算法所需的多種函數(shù)，能夠很好地解決多目標(biāo)優(yōu)化問題。將表1中的參數(shù)寫入到一個(gè)M文件中[12]，編寫被裝物資貨位優(yōu)化問題的遺傳算法程序，然后運(yùn)行程序，得到貨位優(yōu)化結(jié)果并進(jìn)行分析。

4.1 貨位優(yōu)化結(jié)果

運(yùn)行Matlab程序，可獲得模型的求解結(jié)果，包括各目標(biāo)函數(shù)的最小值、模型的帕累托最優(yōu)解、目標(biāo)函數(shù)圖像等。最優(yōu)解如表3所示，其中的貨位坐標(biāo)是優(yōu)化后的結(jié)果。效率優(yōu)化目標(biāo)函數(shù)在50次迭代過程中的圖像如圖1所示，其中，位于上方的曲線表示解的平均值的變化過程，下方的曲線表示最優(yōu)解的變化過程。貨架穩(wěn)定性優(yōu)化目標(biāo)函數(shù)的圖像如圖2所示。

表3 優(yōu)化后的貨位分配情況

4.2 結(jié)果分析

由圖1可以看出，迭代開始時(shí)，效率優(yōu)化目標(biāo)函數(shù)值最高處于22左右的水平。在運(yùn)行到第1代和第10代之間時(shí)，函數(shù)值在19～22之間浮動(dòng)。此后，函數(shù)值基本穩(wěn)定在19左右，其平均值也呈明顯下降趨勢。從圖2可以看出，目標(biāo)函數(shù)值經(jīng)過15次迭代，由17.9左右下降到17.4左右，此后基本收斂在17.4，其平均值也在18.1左右收斂。表4中列舉了優(yōu)化前后的貨位分配方案的目標(biāo)函數(shù)值，可以看出，效率優(yōu)化目標(biāo)函數(shù)值下降了29.9%，物資出庫效率得到顯著提升。同時(shí)，貨架穩(wěn)定性優(yōu)化目標(biāo)函數(shù)值下降了6.0%，兩目標(biāo)函數(shù)之和下降了20.1%，說明模型整體優(yōu)化效果較好。

圖1 效率優(yōu)化目標(biāo)函數(shù)迭代過程

圖2 貨架穩(wěn)定性優(yōu)化目標(biāo)函數(shù)迭代過程

表4 優(yōu)化前后效果比較

綜上所述，遺傳算法全局搜索、并行運(yùn)算的特點(diǎn)使它能高效地求解多目標(biāo)優(yōu)化問題，并且能直觀地展現(xiàn)出優(yōu)化過程，具有很強(qiáng)的實(shí)用性。本文建立的被裝物資貨位優(yōu)化模型基本達(dá)到了預(yù)期目標(biāo)，在物資出庫效率和貨架穩(wěn)定性兩個(gè)方面取得了較好的優(yōu)化效果。由此可見，根據(jù)貨位分配原則設(shè)定明確的貨位優(yōu)化目標(biāo)，建立相應(yīng)的數(shù)學(xué)模型，然后運(yùn)用適當(dāng)?shù)墓ぞ哌M(jìn)行求解，根據(jù)實(shí)際情況將得到的優(yōu)化結(jié)果進(jìn)行調(diào)整和應(yīng)用，就能取得儲存規(guī)劃的優(yōu)化效果，提高被裝倉儲作業(yè)的效率。

5 結(jié)語

通過運(yùn)用遺傳算法在MATLAB中模擬被裝物資貨位優(yōu)化，驗(yàn)證了這個(gè)多目標(biāo)組合優(yōu)化問題的一種有效解決方案，同時(shí)也為解決類似問題提供參考。物流行業(yè)正處在上升期，軍事物流建設(shè)還有很長的路要走。要保障打贏未來戰(zhàn)爭以及保障非戰(zhàn)爭軍事任務(wù)，軍事物流信息化建設(shè)有至關(guān)重要的作用。互聯(lián)網(wǎng)技術(shù)和人工智能發(fā)展迅猛，軍事物流信息化建設(shè)也充滿機(jī)遇。通過理念創(chuàng)新與技術(shù)融合，讓軍事物流信息化的進(jìn)步為強(qiáng)軍事業(yè)提供全方位的有力保障。