采用自適應優化權重的出庫貨位優化方法研究

姜良重，雷 航，李貞昊，錢偉中，施甘圖

1.電子科技大學 信息與軟件學院，成都 610054

2.宏圖智能物流股份有限公司，成都 610051

倉庫貨位匹配作業在現代物流作業系統中占據重要的一環，貨位匹配的結果會極大影響整個物流作業的效率和企業利益。不管是人工操作的倉庫還是最近流行的自動化立體倉庫，都需要一個合理、高效的貨位匹配規劃。

為了優化貨位匹配結果，國內外學者在貨位優化方面開展了大量的研究工作。

在優化原則上，Hausman 等[1]提出基于周轉率和貨物種類的入庫貨位分配，取得了比隨機存儲更好的倉庫管理效率。黨偉超等[2]提出考慮貨架穩定性，該方案將貨架的穩定性考慮到優化策略中，降低了出入庫過程中貨架傾覆的風險。

對于貨位優化求解算法方面，當今學者大多使用啟發式算法，能夠在較短時間內，求解出一個令人滿意的貨位分配結果。Heragu 等[3]提出了使用啟發式算法來進行貨位分配；馬永杰等[4]提出基于遺傳算法的自動化倉庫貨位匹配；俞雷霖等[5]提出基于混合禁忌搜索算法的貨位分配，該算法相比傳統的遺傳算法有著更好的結果表現；陳月婷等[6]提出了改進粒子群算法的立體倉庫貨位分配優化；張思建等[7]提出了基于模擬退火算法的AVS/RS 多批貨箱入庫貨位優化；王廳長等[8]提出了采用病毒協同進化遺傳算法的自動化倉庫貨位優化方案。

另外，一些學者針對某些特殊場景下的貨位分配也進行了大量研究。寧浪等[9]針對JIT生產的零部件配送具有種類多、批次多、批量少、出入庫時間分散等特點進行貨位優化研究；侯忠等[10]針對汽車零配件倉庫特點，采用遺傳算法優化貨位分配；王雨寧等[11]針對醫療器械倉庫具有品類多，需要精準存取等特點，運用EIQBC分類法、多目標指派模型解決貨位分配問題。

總之，由于貨位分配屬于組合優化問題，隨著庫位的增多，計算量指數級增加，因此國內外學者大多采用啟發式算法來優化貨位分配，本文對于出庫貨位優化問題出于計算量考慮同樣采用啟發式算法。對于優化原則，當前大多數學者研究貨位優化問題時，主要考慮貨架的穩定性、貨物的出入庫時間、貨物相關性等局限在倉庫內部的因素，暫未發現有學者考慮到倉庫作業繁忙程度等倉庫外部因素對貨位優化的影響。在倉庫繁忙時，作業人員更愿意優先考慮出庫效率，而在倉庫作業不繁忙時，作業人員為了降低貨物積壓導致價值下降風險更愿意出庫生產日期靠前的貨物，但大多數學者對于存放在倉庫內貨物的生產日期的考慮，只是簡單地使用先進先出原則，無法滿足作業人員要求。

本文基于以上發現的不足，首先設計貨物剩余價值率和出庫代價優化模型，然后基于倉庫作業的繁忙程度，研究倉庫繁忙程度對貨物出庫代價和貨物剩余價值率之間的優化權重取值的影響，提出了基于倉庫繁忙率的自適應優化權重，并建立多目標出庫貨位優化模型，接下來，使用基于自適應算子，災變算子和精英策略的改進策略的遺傳算法對模型求解，并基于企業實際數據驗證模型和算法的合理性，最后總結本文研究成果。

1 出庫貨位分配多目標優化模型構建

1.1 貨物剩值率設計

貨物剩值率是貨物的當前實際價值與剛生產時價值的比值，影響貨物剩值率的因素主要有貨物是否有損壞，臨近保質期程度等，由于貨物倉儲中損壞概率小，故本文只考慮臨近保質期程度對貨物剩值率的影響，并定義臨期率衡量貨物臨近保質期程度。

貨物剛生產的一段時間內，價值變化不大，但到某臨界點后，價值會逐漸下降，并且下降速度會隨著時間推移而加快。因此，定義第i種貨物的第n批次的貨物的臨期率Rexpri(i,n)如式（1）：

式（1）中，Psl(i,n)是第i種的第n批次的貨物的剩余保質時長，Pl(i,n)是第i種貨物的第n批次的貨物的保質時長。

基于以上分析，第i種貨物的第n批次的貨物剩值率Rrv(i,n)如式（2）：

為了在出庫過程中優先出庫貨物剩值度低的貨物，第一個優化目標函數如式（3）：

式（3）中，SorderSku是訂單貨物種類集合，SResult(i)是第i種貨物的貨位分配結果集，A(i,n)是第i種貨物的第n批次貨物的數量，AorderSum是訂單要求貨物數量總和。

1.2 貨物出庫代價設計

貨物出庫代價是衡量某訂單需求貨物出庫時需消耗的總時間代價。本文暫只針對立體倉庫研究，故定義編號為z的庫位，庫位中存放第i種貨物的托盤的出庫代價C(z,i)如式（4）：

式（4）中，Dh(z)是編號z的庫位到門的最短路徑距離，Vfork是叉車速度，Nl(z)是編號z的庫位所在的層數，Televator是升降機每升/降一層需要的時間。

根據上述分析，為了盡可能降低出庫代價，故建立第二個目標函數如式（5）：

式（5）中，SorderSku是訂單貨物種類集合，Sresult是貨位分配結果集，N(z,i)是編號為z的庫位中含第i種貨物的托盤數，C(z,i)是編號為z的庫位存放第i種貨物的托盤的出庫代價。

1.3 多目標優化傾向權重確定

出庫貨位優化目標有貨物出庫代價和貨物剩值率，當倉庫繁忙時，貨位優化算法應更傾向于優化出庫代價，提高作業效率，防止倉庫擁擠；當倉庫作業空閑時，貨位優化算法應更傾向于優化貨物剩值率，將貨物剩值率低的貨物出庫，降低貨物因存放過久而價值下降的風險。

基于以上分析，本文使用倉庫繁忙度衡量倉庫繁忙程度，并根據倉庫繁忙度計算各優化目標的權重。

1.3.1 倉庫繁忙度計算方法

倉庫繁忙度是指開始進行貨位優化的那一時刻的倉庫繁忙度。倉庫出庫操作主要靠叉車，叉車使用率高，則說明當前倉庫作業繁忙。因此，采用叉車使用率來衡量倉庫繁忙程度，但考慮在當前出庫作業過程中仍可能有作業到達，因此不能僅考慮某一時刻倉庫叉車使用率。

基于以上分析，某一時刻倉庫叉車使用率Rforkuse表述如式：

式（6）中，NcurFork是當前倉庫正在使用的叉車，NsumFork是倉庫中總共擁有的叉車數量。

倉庫繁忙度MwarehouseBusy表述如式（7）：

式（7）中，λ是考慮到當前出庫作業過程中倉庫繁忙度增加而設置的預留量，設置為0.2。

1.3.2 傾向權重計算方法

本文選用線性轉換得到貨物剩值率優化傾向權重w1和貨位出庫代價優化傾向權重w2，表述如式（8）：

1.4 目標函數歸一化處理

由于任務總量、貨物種類等因素會導致f1和f2的值相差較大，f2根據定義不需要進行歸一化，因此僅需對f1進行歸一化處理。

貨物的出庫代價由于出庫庫位位置和數量的不確定性，在全局上無法進行歸一化處理，因此本文根據遺傳算法特點，在每一代種群內對f1進行歸一化處理。

基于以上分析，在某一代種群內，f1和f2歸一化后的fn1和fn2表述如式（9）：

式（9）中，fmin1是當代種群中f1的最小值，fmax1是這代種群中f1的最大值。γ是常量，防止分母為零，設置為0.000 1。

1.5 出庫貨位優化模型目標函數

出庫貨位優化模型需要滿足如下幾個約束：所選庫位的貨物數量和種類必須滿足訂單要求；所選庫位的貨物能夠被允許出庫。

基于以上分析，得到優化目標函數表述如式（10）和（11）：

式（10）中，Fout是優化函數值，fn1是f1歸一化后的值，fn2是f2歸一化后的值。式（11）中，A(i,z)是編號為z的庫位上第i種貨物的數量，AorderSum(i)是訂單要求的第i種貨物的數量，F(i,z)是編號為z的庫位上第i種貨物能否出庫標志。

2 出庫貨位優化模型的算法設計

出庫貨位優化涉及出庫貨位選擇和貨位貨物出庫順序確定。因此參考文獻[12]，將貨位優化問題分為兩層進行優化：（1）貨位選擇層：選擇哪些庫位上的貨物完成貨物出庫；（2）貨位順序層：確定已選中的貨位貨物出庫順序。

2.1 貨位選擇層算法設計

貨位選擇層優化問題是組合優化問題，采用遺傳算法進行求解。因已有研究成果表明精英策略[13]、自適應交叉率[14]和變異率和災變算子[15]明顯改善了傳統遺傳算法的缺點，因此這里基于上述改進策略并結合貨位優化問題特點設計貨位選擇層算法。

2.1.1 確定編碼方式

染色體采用二進制編碼，染色體中每個基因表示一個庫位，1代表選用該庫位貨物，0代表不選用該庫位貨物，染色體長度為貨物對應庫位數總和，并使用輔助編碼表達每個基因所對應的庫位、貨物類別、數量信息，染色體結構設計如圖1所示。

圖1 染色體結構Fig.1 Chromosome structure

2.1.2 適應度計算設計

因出庫貨位優化是最小化目標函數而適應度是求最大值，需要轉換，因此，適應度函數表述如式（12）：

式（12）中，Fadapt是適應度值，Cmax是一個相對大的數，Fout是出庫貨位優化目標函數，因Fout最大值為1，因此設Cmax=1。

2.1.3 選擇算子設計

先采用精英策略，將種群中適應度最大的個體直接復制進入下一代，對于剩余個體采用錦標賽選擇法選擇，兩種策略結合既能不丟失最優個體，又能保證適應度較大個體的基因遺傳到下一代。

2.1.4 自適應算子

自適應算子能提高遺傳算法的收斂精度和收斂速度，本文自適應算子參考文獻[16]，如式（13）：

式（13）中，k1、k2、k3和k4是常量，fmax是當前種群中個體最大適應度值，f′是要交叉的兩個個體中較大的適應度值，favg是當前種群平均適應度值，f是要變異個體的適應值，Pc是交叉概率，Pm是變異概率。

2.1.5 交叉算子設計

基于編碼特點和出庫貨位分配問題特點，交叉方式采用同類貨物基因段雙切點交叉。同類貨物基因段雙切點交叉操作過程如下：

步驟1在種群中，隨機選取父代個體PL1和父代個體PL2。

步驟2在PL1上隨機選取一段同類貨物基因段。

步驟3將PL1和PL2上相同位置的同類貨物基因段進行互換。

這樣操作的優點是兩染色體交叉后，子代染色體所表示的結果仍符合優化目標的約束。

2.1.6 變異算子設計

針對染色體編碼方式和出庫貨位分配問題特點，采用互換變異方式。首先，隨機在染色體上，選取一段同類貨物基因段，然后在該基因段上隨機選取一個值為1的基因和一個值為0的基因，最后將兩個基因值互換。

2.1.7 染色體修復策略

由于每個庫位的貨物數量不同，在進行變異操作后，可能導致染色體無法滿足出庫貨位優化目標的約束，需要進行染色體修復，修復步驟如下：

步驟1首先，判斷經過變異的第i種貨物對應染色體基因段Gi所表達的貨物數量是大于、小于還是等于訂單中第i種貨物的數量。若小于轉步驟2，若大于轉步驟4，若等于轉步驟5。

步驟2變異后導致基因段Gi所表達的貨物數量小于訂單中第i種貨物的數量，需要增加出庫庫位，從未選擇的出庫庫位中隨機選擇一個庫位SnoSelect，將基因段Gi中對應庫位SnoSelect的基因值變為1，轉到步驟3。

步驟3判斷基因段Gi所表達的貨物數量是否小于訂單中第i種貨物的數量，若大于轉步驟5，否則轉步驟2。

步驟4變異后導致基因段Gi所表達的貨物數量大于訂單中第i種貨物的數量，可能需要減少出庫庫位，將基因段Gi里基因值為1所對應的庫位按照庫位存放第i種貨物的數量從小到大排序成S1,S2,…，然后依次按順序累加庫位Si存放第i種貨物的數量，若累加的貨物數量大于訂單中第i種貨物數量，則將庫位Si后面的庫位所對應基因段Gi的基因值變為0，即不選擇后續庫位。轉步驟5。

步驟5結束染色體修復。

2.1.8 災變算子設計

災變算子的引入，模擬了自然界中生物滅絕現象，其主要作用是當算法過早收斂時，使其跳出局部搜索。災變算子主要由災變條件和災變方式構成，本文設計如下：

（1）災變條件：首先設置一個災變倒計時數C，每當新一代個體中最好的個體的適應度相比上一代沒有進化，則C值減1；然后當C=0，發生災變，根據災變方式重新生成種群。

（2）災變方式：首先保留當代最優個體，然后隨機生成其他個體，最后將這些個體組成新一代種群。

2.2 貨位順序層優化

貨位順序層優化是基于貨位選擇層優化結果進行優化，確定貨位上貨物出庫順序。

2.2.1 貨位順序層問題描述

由于訂單要求貨物數量不一定恰好等于所選庫位上存放的貨物數量，導致最后一個出庫的庫位上貨物只有部分貨物出庫，若隨機確定順序，可能導致出庫貨位優化結果不佳，因此需要確定貨位出庫順序。

2.2.2 貨位順序層優化算法設計

首先確定存放貨物需全部出庫的庫位，然后對剩余的每個庫位計算每個庫位的出庫優化目標值，最后根據每個庫位的出庫優化目標值從小到大依次選擇庫位。基于以上思想，設計如下步驟來求解貨位順序優化問題：

步驟1按照庫位上存放第i種貨物存放數量從大到小排序得庫位序列(S1,S2,…,Sn)，依次累加庫位上第i種貨物的數量，直到總和滿足訂單中第i種貨物數量，剩余沒有被累加的庫位序列(Sm,Sm+1,…,Sn)為貨物全部出庫的庫位，庫位序列(S1,S2,…,Sm-1)則為需要比較的優化目標大小的庫位。轉到步驟2。

步驟2針對庫位序列(S1,S2,…,Sm-1)，計算每個庫位的出庫優化目標值。轉到步驟3。

步驟3步驟2 中計算的庫位出庫優化目標值最大的庫位為最后出庫庫位，(Sm,Sm+1,...,Sn)庫位序列根據庫位存放第i種貨物的數量由小到大順序出庫。

2.3 出庫貨位優化模型求解算法流程

出庫貨位優化模型求解算法需要經過貨位選擇層算法優化和貨位順序層算法優化，流程如圖2所示。

圖2 出庫貨位優化模型求解算法流程圖Fig.2 Flowchart of algorithm for solving outbound storage location optimization model

3 實例驗證和結果分析

3.1 實驗環境

本文使用Java 語言實現出庫貨位優化算法并基于實際生產數據進行算法驗證。

參考遺傳算法常用參數設置，設置出庫貨位優化算法參數如表1所示。

表1 出庫貨位優化算法參數表Table 1 Parameter table of outbound storage location optimization algorithm

3.2 實例數據

本文數據來源于宏圖智能物流股份有限公司的物流倉庫數據庫中的貨物存儲數據，數據格式見表2。

表2 庫存信息格式Table 2 Inventory information format

數據庫中信息含有8 165 個庫位信息，19 588 個不同貨物種類不同批次的貨物庫存信息，總庫存貨物數量為11 222 825件。

3.3 實驗結果分析

3.3.1 驗證算法性能

本文基于自適應算子、精英策略和災變策略的改進出庫貨位優化算法（IOSAA）是對采用標準遺傳算法的傳統出庫貨位優化算法（TOSAA）的改進，現基于實際訂單運用IOSAA 和TOSAA 分別對貨物出庫貨位分配模型進行求解，并比較目標函數值的結果來驗證IOSAA是否比TOSAA有更好的優化結果。由于出庫代價無法在算法外部進行歸一化，因此，將出庫代價傾向優化權重設為1，比較兩者優化出庫代價的結果，實驗采用的訂單詳情如表3所示。

表3 測試實例中訂單詳情表Table 3 Order details table in test case

算法優化過程對比結果如圖3所示。從圖3可以看出，TOSAA由于采用傳統遺傳算法作為主要優化手段，導致無法保存每一代最優結果，因此優化過程不平穩，并且容易過早收斂，無法繼續優化；而IOSAA由于采用了精英策略、自適應算子和災變算子改進手段，可以彌補傳統遺傳算法的不足，優化過程更平穩、快速，并且可以避免過早收斂，盡可能到達到最優值。

圖3 IOSAA和TOSAA優化過程比較Fig.3 Comparison of IOSAA and TOSAA optimization process

下面采用了10個不同的企業實際出庫訂單再次對比IOSAA和TOSAA算法效果，出庫代價傾向優化權重設為1，結果如圖4所示。

圖4 不同訂單下IOSAA和TOSAA出庫代價優化結果對比Fig.4 Comparison of IOSAA and TOSAA outbound cost optimization results under different orders

從圖4 可以看出，IOSAA 的優化結果明顯優于TOSAA，在各個訂單中都表現穩定，出庫代價最低，并且隨著訂單規模增加，出庫代價增大，差距也越明顯。

下面結合自適應優化權重，對比IOSAA和TOSAA，設置倉庫繁忙度為0.6，出庫代價和剩值率結果如表4所示。

表4 基于自適應優化權重，IOSAA和TOSAA結果對比Table 4 Based on adaptive optimization weights，IOSAA and TOSAA results comparison

為了明顯看出兩者的差距，定義對比綜合值如式（14）：

式（14）中，Fcompare1是算法1 的對比綜合值，Fcompare2是算法2的對比綜合值，fout1是算法1結果中的出庫代價，fout2是算法2結果中的出庫代價，frv1是算法1結果中的貨物剩值率，frv2是算法2結果中的貨物剩值率。

因此，表4 中IOSAA 和TOSAA 所對應的對比綜合值，如表5所示。

表5 表4中IOSAA和TOSAA所對應的對比綜合值Table 5 Value of comparison of IOSAA and TOSAA in Table 4

從表5 可以看出，IOSAA 的對比綜合值明顯小于TOSAA，優化結果表現更優。

由于貨物出庫過程中作業人員無法忍受算法耗費過長時間，因此接下來比較兩者運行時間，通過運行100次，TOSAA和IOSAA平均運行時間對比如圖5所示。

圖5 IOSAA和TOSAA運行時間對比Fig.5 IOSAA and TOSAA running time comparison

如圖5 所示，TOSAA 算法運行速度要快于IOSAA算法，但是對于實際應用來說，100多毫秒的延遲相比于優化結果的提升幅度，是完全可以接受的。

基于上述分析，表明改進后的出庫貨位優化算法能夠有效解決出庫貨位優化問題，并且優化結果相比使用標準遺傳算法的出庫貨位優化算法有所提高。

3.3.2 驗證自適應優化權重作用

為驗證基于倉庫繁忙度的自適應優化權重是否有效，本文首先選取同一個訂單，采用不同的倉庫繁忙度，分別使用自適應優化權重和不適用優化權重算法進行對比，仿真結果如圖6所示。

圖6 同一訂單不同倉庫繁忙度下，仿真對比結果Fig.6 Simulation comparison results under the same order with different warehouse busyness

接下來選取一系列訂單，采用同一個倉庫繁忙度（這里設置倉庫繁忙度為0.6），分別使用自適應優化權重和不適用優化權重算法進行對比，仿真結果如圖7所示。

圖7 不同訂單同一倉庫繁忙度下，仿真對比結果Fig.7 Simulation comparison results under the same warehouse busyness for different orders

由圖6、圖7的結果可知，使用了自適應優化權重的出庫貨位優化算法對于貨物剩值率的優化優于不使用自適應優化權重的算法，這是由于不使用自適應優化權重的算法只考慮優化出庫代價，這導致某些生產日期靠前的貨物無法出庫，造成貨物積壓，給企業造成損失，而使用了自適應優化權重的出庫貨位優化算法根據倉庫繁忙度來調整優化權重，并且在倉庫繁忙時，傾向于降低出庫代價，提高出庫代價；在倉庫比較空閑時，傾向于出庫貨物剩值率低的貨物。因此，基于倉庫繁忙度的自適應優化權重可以有效幫助倉庫降低生產日期靠前的貨物積壓風險，同時可以在倉庫繁忙時優先考慮出庫效率。

4 結語

本文研究了倉庫出庫貨位優化問題，建立了以出庫代價和貨物剩值率為原則的出庫貨位優化模型，并利用改進遺傳算法結合基于倉庫繁忙率的自適應優化權重對模型進行求解，通過企業實際生產數據驗證了模型和算法的可行性和合理性，對于出庫貨位優化，采用精英策略、自適應算子和災變算子的遺傳算法的優化結果優于標準的遺傳算法，并且其收斂速度更快，能夠避免過早收斂；同時使用基于倉庫繁忙率的自適應優化權重，能夠較好地避免貨物因在倉庫內存放過久而貨物價值降低的風險同時又能在倉庫繁忙時優先考慮出庫效率。

本文在研究中對于臨期率和貨物剩值率的設計過于主觀，并且沒有考慮到跨倉庫出庫的情形。因此，在今后的研究中，需要進一步研究，建立更加客觀的臨期率和貨物剩值率模型，并研究跨倉庫出庫的場景下的出庫貨位優化。