基于改進遺傳算法的震后應(yīng)急物資儲位優(yōu)化研究

王 婧，禹宏斌（武漢科技大學(xué) 管理學(xué)院，湖北 武漢 430065）

0 引 言

2023年土耳其地震期間，大量國際救援物資涌入災(zāi)區(qū)。然而，急需的救援物資未能全部及時送到受災(zāi)群眾手中。除了災(zāi)中運輸網(wǎng)絡(luò)受損和物資緊缺等因素外，應(yīng)急倉庫物資儲位分配不合理也是一個重要原因。地震期間，應(yīng)急物資的需求激增，供應(yīng)管理變得困難，儲位分配不合理會導(dǎo)致物資的揀選和出庫出現(xiàn)延遲，不利于有效開展災(zāi)后救援。及時有效地供應(yīng)應(yīng)急物資對災(zāi)中救援至關(guān)重要。因此，對應(yīng)急物資儲備工作進行合理系統(tǒng)的規(guī)劃非常重要。同時，加強此類研究有助于不斷完善我國的應(yīng)急物流體系。

1 應(yīng)急物資儲備系統(tǒng)研究綜述

應(yīng)急物資儲備倉庫是我國應(yīng)急物資儲備的主體，承擔(dān)著救災(zāi)物資的收集和調(diào)度等任務(wù)。在發(fā)生重大突發(fā)公共衛(wèi)生事件后，它能快速響應(yīng)并為其提供必要的支持，在保障人民的生命安全和基本生活需求方面具有重要作用，應(yīng)予以充分重視和投入。

學(xué)者們非常關(guān)注應(yīng)急物資儲備庫的選址問題。文獻[1]為確定應(yīng)急物資儲備庫的最優(yōu)選址，考慮了需求和運輸時間不確定的問題，建立了模型，用混合蛙跳算法求解。文獻[2]提出借助圓心定位法進行應(yīng)急物資儲備庫選址，創(chuàng)立全面協(xié)同的應(yīng)急物資儲備系統(tǒng)。文獻[3]借助系統(tǒng)動力學(xué)法，通過仿真模擬案例，求解應(yīng)急物資的合理儲備量。文獻[4]探討了立體倉儲系統(tǒng)下防疫物資儲位分配的優(yōu)化問題，并采用枚舉法求解。文獻[5]利用了加入精英保留策略的遺傳算法，對儲位分配模型進行求解，并與標準遺傳算法比較，驗證了前者的優(yōu)越性。因此，本文將利用精英保留遺傳算法來研究應(yīng)急物資的儲位優(yōu)化問題。

2 應(yīng)急物資儲備現(xiàn)狀

由于地震災(zāi)害的突發(fā)性和破壞性，強震后往往急需大量應(yīng)急救援物資，以確保人們的生命安全，滿足其基本生活需求。應(yīng)急物資將在災(zāi)后迅速籌措，集中運送到應(yīng)急物資儲備庫，由救援人員或志愿者進行倉庫管理和物資調(diào)度。

我國的應(yīng)急物資儲備庫存在硬件設(shè)施不完善，倉儲管理存在缺陷等問題。目前大多數(shù)應(yīng)急物資儲備庫缺乏必要的倉儲設(shè)備和設(shè)施，通常需要依賴救援人員或志愿者進行人工作業(yè)，這會拖慢物資的裝卸和出庫速度，不利于震后救援工作的有效開展。而且，物資往往只是根據(jù)儲位的空閑情況隨意擺放，這無疑會對出庫效率造成不良影響。災(zāi)后，由于應(yīng)急物資的需求量急劇增加，不合理的儲位分配會導(dǎo)致應(yīng)急物資儲備庫供貨效率嚴重滯后和供貨不足。

合理的儲位分配對提高物資出庫效率、應(yīng)急救援工作的效率和效果非常重要。為此，本研究建立了數(shù)學(xué)模型，用于優(yōu)化應(yīng)急物資儲備庫中物資儲位的分配情況，并采用改進遺傳算法求解。

3 儲位優(yōu)化模型建立

3.1 模型條件假設(shè)

為了明確研究目的，針對應(yīng)急物資的特點，提出了以下一系列假設(shè)條件，用于描述應(yīng)急物資儲備系統(tǒng)。

a.應(yīng)急物資儲備倉庫為自動化立體倉庫，屬于單元貨格式存儲形式；

b.該自動化立體倉庫只有一個出庫口；

c.倉庫中的巷道寬度（排距）及貨架單元格的長、寬和高均為固定值；

d.在自動化立體倉庫中，有a排貨架，每排貨架有b列和c層。第一排貨架是最靠近出庫口的排，第一列是最靠近出庫口的列，第一層是貨架的底層；

e.該倉庫有多種應(yīng)急物資，物資存放采用隨機存儲策略，可以使用任何儲位。同一組貨架上不同品種的貨物尺寸相同，重量不同；

f.已知每種貨物的重量和出庫率。

3.2 模型建立（見表1）

3.2.1 出庫效率分析

在堆垛機勻速運行的情況下，減少作業(yè)移動路程即可縮短出庫作業(yè)時間，從而提高出庫效率。為提高出庫效率，現(xiàn)考慮采取就近存放原則，使貨物盡量臨近出庫口存放。儲位坐標（xij，yij，zij）表示第i類物資的第j個貨品的X軸、Y軸和Z軸坐標，出庫口坐標為O（0，0，0）。堆垛機沿著X軸、Y軸和Z軸分別以vx、vy和vz的速度勻速運動，貨物出庫率為Sij。

堆垛機在X，Y，Z方向的運行時間分別為：

貨物單次出庫移動的最短距離為：

出庫效率目標函數(shù)如下：

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

為保持貨架的穩(wěn)定性，采取以下策略：將較重的物資放置在貨架的下層，較輕的物資放置在貨架的上層，貨架底層記為第1層。假設(shè)儲位（xij，yij，zij）存放的第i類物資第j個貨品重量為Mij，所在的層為Zij。為使貨架保持穩(wěn)定，要最小化所有貨品的所在層與其重量的乘積之和，由此得到如下目標函數(shù)：

3.2.3 物資關(guān)聯(lián)分析

在考慮貨品相關(guān)性原則的前提下，將貨品分類存放，并確保將其按類別分類擺放，實現(xiàn)均勻分布。出庫時，優(yōu)先選擇先入庫的同種貨品。這意味著要把同類貨物盡可能擺放在一起，并盡量縮短同類貨物之間的距離。

d為所有i類別貨品內(nèi)離散距離和，類內(nèi)貨物盡量緊湊，同類貨物盡量靠近，d越小類內(nèi)貨物越緊湊，越符合關(guān)聯(lián)原則。D為所有貨物均值坐標到出庫口的距離和，D越小越接近出庫口。目標函數(shù)如下：

其中，貨品內(nèi)離散距離和d表示所有第i類別貨物的離散距離和（i=1，2，3，...，n），即第i類別貨物到gi（x，y，z）的距離之和，gi（x，y，z）為第i類貨物的坐標均值。

全部貨物的均值坐標為：

D表示所有貨物均值坐標到出庫口的距離之和：

3.2.4 約束條件

根據(jù)儲位優(yōu)化原則及自動立體倉庫的實際情況，設(shè)置應(yīng)急物資儲備庫儲位優(yōu)化模型的參數(shù)范圍為：

為避免多目標模型求解時各目標相互影響，用經(jīng)典的權(quán)重系數(shù)法將多目標模型轉(zhuǎn)換成單目標優(yōu)化模型，即：

根據(jù)應(yīng)急物資的特性可知，在三個目標中，最重要的是出庫效率。為此，出庫效率的權(quán)重應(yīng)該是三個目標中最大的。

用層次分析法（AHP）求得權(quán)重為：w1=0.625，w2=0.238 5，w3=0.136 5。最終的優(yōu)化模型為：

4 算法設(shè)計

在解決簡單問題時，標準遺傳算法表現(xiàn)良好，但對于復(fù)雜的多峰值問題，它可能無法保留群體中的最優(yōu)個體。研究顯示，帶有精英保留策略的遺傳算法在復(fù)雜多峰值函數(shù)的優(yōu)化中能找到全局最佳解。對于倉庫儲位分配問題這類復(fù)雜多峰值函數(shù)的優(yōu)化問題，我們引入了精英保留策略以實現(xiàn)遺傳算法的全局收斂（見圖1）。該策略在進行選擇、交叉和變異操作之前，會保存種群中的最優(yōu)個體。在下一輪迭代中，如果發(fā)現(xiàn)更好的個體，會用新的優(yōu)秀個體替代之前保存的最優(yōu)個體。這樣可以確保最優(yōu)解得以保留，并提高算法的效率。

圖1 精英保留遺傳算法流程圖

4.1 編碼設(shè)計

本文采用整數(shù)排列法進行編碼。操作如下：每個染色體表示一個儲位，包括排數(shù)、列數(shù)和層數(shù)等信息。初始種群的數(shù)量（染色體個數(shù)）已確定。基因取值為整數(shù)，表示儲位的坐標。例如，6（5，3，3）表示物資6存放在排數(shù)為5、列數(shù)為3、層數(shù)為3的儲位上。

4.2 初始種群確定

初始種群代表了倉庫物資儲位分配的可能結(jié)果集。種群規(guī)模過大會耗費過多計算時間，而規(guī)模過小則可能導(dǎo)致其過早收斂。染色體上的基因位已確定，具體的儲位信息將在案例分析中提供，每個染色體都對應(yīng)一種解決方案。在初始化種群時，可能會出現(xiàn)將不同貨品分配到同一儲位的情況。為了確保儲位的唯一性，需要逐一遍歷儲位。如果存在相同的儲位，則可通過隨機生成其他儲位坐標來替換重復(fù)的坐標，以確保每個貨品都被分配到獨立的儲位上。

4.3 適應(yīng)度函數(shù)確定

本文中的所有目標函數(shù)都是求最小值，轉(zhuǎn)換為適應(yīng)度函數(shù)時需使用目標函數(shù)的倒數(shù)進行計算。適應(yīng)度值越大，被遺傳到下一代的概率就越大，對應(yīng)的目標函數(shù)值就越小。

適應(yīng)度函數(shù)表示如下：

4.4 選擇操作

通過結(jié)合輪盤賭和精英保留策略選擇個體，我們能在選擇個體時實現(xiàn)優(yōu)化。這種方法允許我們從父代中選擇最佳個體，并將其直接保留到下一代，這樣可以避免失去父代的最優(yōu)個體。同時，這也能確保適應(yīng)度較高的個體更有可能在下一代中被保留，從而大幅提高算法的收斂速度。

4.5 交叉操作

交叉運算是算法中種群生成新個體的一種關(guān)鍵方式。我們所采用的方法是順序交叉法，其中交叉概率設(shè)定為0.8。下面是交叉運算的步驟：首先，根據(jù)概率確定需要進行交叉操作的父代個體。然后，將這些父代個體，分為兩個一組，并在特定規(guī)則下交換染色體的某個基因位，這樣就能夠生成兩個全新的個體。以由儲位組成的染色體為例，假設(shè)我們選擇了兩個染色體：9號儲位（6，5，6）和12號儲位（3，2，3）。接下來，我們要在相同位置上互換兩個基因位。最終，我們得到了兩個新的個體：（6，2，6）和（3，5，3）。

4.6 變異操作

使用交換變異方法進行變異運算，將變異概率設(shè)置為0.01。每個染色體都包含儲位的排、列和層信息。例如，根據(jù)儲位的變異概率，在染色體中選擇8號儲位（2，3，1），選定的基因變異位為染色體的“2”和“1”，通過交換它們，生成新的個體（1，3，2）。

根據(jù)設(shè)定概率對個體進行交叉、變異操作，評估這些個體的適應(yīng)度，選擇適應(yīng)度較高的個體進行下一代的交叉和變異。循環(huán)執(zhí)行這個過程，直到達到設(shè)定的最大迭代次數(shù)。當(dāng)達到設(shè)定的最大迭代次數(shù)時，算法將結(jié)束運行。算法的目標是通過交叉和變異操作，逐步改進個體的適應(yīng)度，并在每一代中選擇最優(yōu)個體進行繁衍，最終得到更優(yōu)解。

5 應(yīng)急物資儲位優(yōu)化仿真實現(xiàn)（見表2）

表2 仿真基本參數(shù)設(shè)定

為了驗證模型和算法的有效性，我們使用Matlab 2022a進行算法改進的運行程序。在該程序中，我們從應(yīng)急物資中選取了26個不同的貨物，以進行模擬仿真優(yōu)化。我們的目標是找到目標函數(shù)的最小值，同時確定其與該最小值對應(yīng)的儲位分配坐標。

假定應(yīng)急物資儲備庫內(nèi)部存放四類共計26種應(yīng)急物資，依次用數(shù)字1—26表示。

第一類是食品和飲用水，具體的貨品編號為1，2，5，8，14，24，25。地震發(fā)生后，食品和飲用水可能會被污染或中斷供應(yīng)。因此，需要儲備足夠的罐頭、方便面、面包、餅干、能量棒、瓶裝飲用水、桶裝飲用水以滿足人們的基本需求。

第二類是醫(yī)療用品，具體的貨品編號為4，6，7，15，17，18，22。地震可能會造成人員傷亡，因此需要儲備醫(yī)療用品，如急救藥品、止血帶、繃帶、注射器、消毒液、消毒棉球、折疊擔(dān)架等，必要時可以提供醫(yī)療救助。

第三類是防護用品，具體的貨品編號為3，9，12，13，20，21，23。地震可能會產(chǎn)生瓦礫、玻璃碎片等危險物品，因此需要儲備防護用品，如呼吸器、氧氣面罩、口罩、護目鏡、防護鞋、安全帽、防護服等，以保護人們的安全。

第四類是床上用品，具體的貨品編號為10，11，16，19，26。地震發(fā)生后，人們可能需要在臨時避難所或帳篷中住宿。因此，需儲備足夠的床上用品，如睡袋、被子、枕頭、毛毯、折疊帳篷等。

應(yīng)急物資的相關(guān)屬性及初始儲位安排如表3所示，初始應(yīng)急物資儲位分配情況如圖2所示。

圖2 初始應(yīng)急物資儲位分配

表3 應(yīng)急物資的相關(guān)屬性以及初始儲位安排

優(yōu)化后應(yīng)急物資的相關(guān)屬性及儲位安排如表4所示，優(yōu)化后應(yīng)急物資的儲位分配情況如圖3所示。

圖3 優(yōu)化后應(yīng)急物資儲位分配

表4 優(yōu)化后的應(yīng)急物資儲位分配表

由以上圖表可以看出：

優(yōu)化之前，隨機存儲策略導(dǎo)致應(yīng)急物資的儲位分配雜亂無章。但經(jīng)過圖3中的層次分析法計算權(quán)重并賦予不同目標函數(shù)權(quán)重后，優(yōu)化后的應(yīng)急物資儲位變得更加集中了。出庫率高的物資靠近出庫口，出庫率低的物資離出庫口較遠，大幅提高了應(yīng)急物資的出庫效率。此外，優(yōu)化后重量較大的物資主要集中在貨架底層，增加了貨架的穩(wěn)定性。同類物資的儲位距離較近，符合儲位分配的相關(guān)性原則。

從圖4可以看出，在第125代時目標函數(shù)已達到最優(yōu)解，證明算法的收斂速度快；用不同方法對目標函數(shù)進行計算，優(yōu)化前的總目標函數(shù)值為901.712 4，而優(yōu)化后的總目標函數(shù)值為140.140 4，優(yōu)化效率約為84%（見表5）。可以明顯看出，優(yōu)化后的目標函數(shù)值比優(yōu)化前有了明顯的改進。

圖4 算法收斂過程

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

總而言之，優(yōu)化后的儲位分配原則取得了明顯的效果，物資揀選和出庫效率顯著提高。

6 結(jié)論和展望

強烈的地震會對人民生活和生命安全造成巨大的負面影響。為確保生命安全、有效救援，迅速供應(yīng)救援物資至關(guān)重要。以自動化立體倉庫為研究對象，考慮了不同儲位的分配原則，給各目標函數(shù)分配合適的權(quán)重，建立儲位優(yōu)化模型，用改進的遺傳算法求解，結(jié)果驗證了模型、算法的可行性。這項研究對提高應(yīng)急物資儲備庫的運作效率，及更好地支持搶險救災(zāi)工作具有重要意義。然而，在研究應(yīng)急物資儲位的優(yōu)化時，未考慮物資保質(zhì)期等特點，在后續(xù)研究中可針對此點加以改進。