儲銷一體倉儲式超市中的存儲貨位指派優化問題研究

徐澤宇，楊 雙

（暨南大學 管理學院，廣東 廣州 510000）

0 引言

隨著經濟發展和居民消費水平的提高，以儲銷一體、批零兼營為主要特征的倉儲式超市迅速興起。這類會員制倉儲超市憑借著倉儲式的陳列降低了中間存放和二次運輸成本，產品的大包裝和高周轉可以覆蓋采購成本和品質損耗。

但相應地，產品的大包裝和高周轉率可能引起更繁重的搬運工作，而且由于場地限制，超市內部不適合安裝大型搬運設備，所以對倉儲式超市進行貨位分配優化以減少搬運工作量十分必要。另一方面，以往的貨位優化問題中，貨架僅有一個I/O，即貨物由不同起點搬運至共同的終點。但在倉儲式超市中，貨物需要從存儲貨架搬運至對應的銷售貨架，即貨物由不同的起點搬運至不同的終點。

針對貨位優化問題，諸多學者在算法方面進行了創新。張延華，等[1]借鑒模擬退火算法思想，設計了改進模擬退火遺傳算法，雖然優化效果顯著，但研究對象為僅有一個I/O點的自動化立式倉庫，問題并不復雜。羅煥，等[2]建立了多目標貨位優化模型，并采用變鄰域NSGA-2算法進行優化，雖然優化效果顯著，但研究對象也為僅有一個I/O點的自動化立式倉庫。王鐵錚，等[3]采用強化學習的方式解決優化問題，雖然方式新穎，但缺少與啟發式算法的優化效果對比，且尋優效率較低。姜良重，等[4]從貨物價值剩余率的角度建立貨位優化模型并利用自適應遺傳算法進行求解，雖然建模角度新穎但沒有考慮貨架重心約束。劉旺盛，等[5]研究了多出入口的倉庫貨位優化，相比單一出入口的自動化立體倉庫，雖然出入口數量增加，但增加數量有限。

綜合現有的研究成果，大多數學者聚焦于單一出入口的立體倉庫進行研究，即使存在多出入口倉庫的研究，出入口數也只增加少數幾個，不能從根本上改變問題的復雜度。而目前倉儲式超市的貨位優化問題，貨物搬運的起終點隨貨物種類的增加而增加，是現有研究尚未觸及的。因此，有必要針對儲銷一體的倉儲式超市的貨位優化問題建立合適的數學模型，設計改進自適應交叉變異的遺傳算法進行求解，并與貪婪算法、傳統遺傳算法的求解結果進行對比，對相關參數進行靈敏度分析并得出相應的管理啟示，以此驗證模型的可靠性和算法求解的有效性。

1 儲銷混合貨位優化模型

1.1 問題描述

如圖1所示，某大型超市存儲銷售一體的立體倉庫由銷售貨架和存儲貨架組成。最底層貨架為銷售貨架，擺放待銷售的貨物，每個銷售貨位固定擺放一種貨物，銷售貨架的貨物擺放情況由超市決定。第二層及以上貨架為存儲貨架，每個存儲貨位只能擺放一個庫存量單位（Stock Keeping Unit）的貨物。當銷售貨位上的貨物被售出時會立即從存儲貨架上搬運同種貨物的一個庫存量單位以完成補貨。具體優化問題可以描述為：已知貨物的種類數、每種貨物的庫存量單位數和每種貨物每個庫存量單位的重量。按照一定的指派規則，將所有貨物的庫存量分配到存儲貨位中，在保證貨架重心不超過一定高度的條件下，同種貨物盡可能集中擺放，以使全部貨物搬運到對應銷售貨位所需時間最少。

圖1 銷售-存儲倉庫示意圖

1.2 假設條件

（1）每個存儲貨位及銷售貨位形狀大小相同，沿x，y，z軸方向分別長為?x，寬為?y，高為?z。

（2）銷售貨位：沿x，y軸方向分別有a行b列，共有a×b個銷售貨位，均在第1層（最底層），每個銷售貨位擺放固定種類的貨物。

（3）存儲貨位：沿x，y，z軸方向分別有a行c列t層（c＜b），共有a×c×t個存儲貨位位于第2層至第t+1層。

（4）巷道：所有巷道寬度相同，存在多條x軸向巷道但僅存在一條y軸向巷道位于第c列到第c+1列之間。

（5）每個存儲貨位和銷售貨位都只能存放一種貨物的一個庫存量單位，一個庫存量單位也只能放在一個貨位上，且庫存量單位是最小的存放單位，不可拆分。

（6）共有n個貨物種類，其中第i類貨物有ki個庫存量單位。滿足，即庫存量單位總數不得超過存儲貨位數。

（7）每個貨物的每個庫存量單位重量已知，其中第i 類貨物的第j 個庫存量單位重量為mij(i≤n，j≤ki)。

（8）貨物由存儲貨位轉運到銷售貨位時是按照直線運動的，且每次僅能沿x軸、y軸、z軸中的一個方向運動，運輸路線不能從貨架內部穿過。

（9）貨物到達貨位中心即視為貨物放置完成，不考慮貨物放置后的調整時間。

（10）在單位銷售周期內，存儲貨架上的所有貨物最終均會轉移到銷售貨架上并售出。

1.3 符號說明

為了建立合適的儲存-銷售貨位優化模型，現規定具體符號及其定義見表1。其中，決策變量僅為xij、yij、zij。而表示第i類貨物所在的銷售貨位坐標，由超市決定。

表1 符號定義

1.4 目標函數

建立貨位優化模型的目標函數，需要遵守以下幾個原則：

（1）補貨效率最大化原則。補貨效率最大化是指在單位銷售周期內存儲貨架上的所有貨物搬運到銷售貨架上對應貨位的時間最短[6]。為便于描述，規定(xij,yij,zij)表示第i類第j個庫存量單位在存儲貨架上的坐標，表示第i 類貨物的銷售貨位坐標。由此所有產品的搬運時間見式（1）。其中，Distx(i,j)，Disty(i,j)，Distz(i,j)分別表示將第i類第j個庫存量單位從存儲貨位搬運至對應的銷售貨位的x軸向距離，y軸向距離和z軸向距離。

（2）產品相關性原則。為了便于存儲貨架上貨物的管理和保存，使存儲貨架上的貨物排列整齊有序，每種貨物在存放時應當盡可能的集中布置[7]。

由此做出如下定義：

②類內分散度。定義di為第i類貨物的類內分散度。其計算方法為第i類貨物中每個貨物到中心位置的距離之和。具體見式（3）。

④類間分散度。定義D為類間分散度，計算方法為各類貨物中心位置與所有貨物中心位置距離之和。

按照產品關聯規則，將相關性最強的貨物盡可能擺在靠近的位置，以每一類的類內產品距離最小、類間產品距離最大為目標函數F2。

1.5 約束條件

（1）一位一物。每個貨位只擺放一個庫存量單位的貨物，每個庫存量單位的貨物可以擺放在任意一個存儲貨位中[8]。具體函數形式見式（7），即任意兩個庫存量單位的貨物至少存在一個維度的坐標不相等。

（2）貨架穩定。貨架穩定約束是指貨架在使用過程中保持穩定，避免傾斜倒塌[9]。即貨物的分布應使存儲貨架的重心在一定高度以下。具體函數形式見式（8），其中α(α＞1)表示寬放系數，zmin表示當前貨物重量配置下貨架重心所能下達的最低高度。具體計算方法是將所有貨物按從重到輕進行排序，按此順序從低層至高層填充貨架。

（3）貨位中心擺放。貨物的位置擺放在儲位中心上，具體如圖2所示。其中?x表示存儲貨位沿x軸向的長度，l表示巷道寬度，a表示所有貨架行數。?y表示存儲貨位沿y軸向的長度，c表示存儲貨架列數。?z表示存儲貨位沿z軸向的長度，t表示存儲貨架層數。由此則可得到貨物坐標，見式（9）。

圖2 儲-銷貨架俯視圖

圖3 改進自適應交叉變異的遺傳算法流程圖

1.6 建立模型

綜上所述，可以建立如下所示的貨位優化模型

s.t.

其中，F1表示補貨效率最優，F2表示同種貨物集中布置、不同種貨物分散布置，D和di的具體計算見式（3）和式（5）。第一個約束條件表示一個貨位只能放置一個貨物，第二個約束條件表示貨架重心控制在一定高度以下，第三個約束條件表示貨物擺放在貨位中心上。

2 改進自適應交叉變異的遺傳算法

2.1 改進自適應交叉變異的遺傳算法流程

經典遺傳算法（Genetic Algorithm）的基本思想是對種群不斷進行選擇、交叉、變異操作，以此來實現“優勝劣汰”[10]。但經典遺傳算法在迭代初期容易陷入局部最優解，迭代后期又難以收斂。故其求解效果有時并不理想。本文提出改進自適應交叉變異的遺傳算法。不僅對交叉和變異操作進行改進，而且還引入精英保留策略。此外，本文增加降低重心高度的操作，通過降重算法對經過交叉、變異后重心高度過高的個體進行調整，以保證最后迭代產生的個體均滿足重心約束。

改進自適應交叉變異GA的具體步驟如下：

（1）設置初始參數：設置種群規模Popsize，交叉概率Pc，變異概率Pm，最大迭代次數Genmax。

（2）初始化種群：采用實數編碼產生個體數量為Popsize的隨機初始種群。

（3）計算每個個體的適應度：根據前文公式計算每個個體的目標函數值。

（4）選擇操作：采用二元錦標賽選擇法，隨機選取兩個個體，將目標函數值較小的個體放入子代種群中。

（5）自適應交叉操作：對基于位置的交叉操作（Position-based Crossover）進行改進。傳統的基于位置的交叉操作分為兩個階段，第一階段是從兩個父代染色體上隨機選擇若干位置，這些位置的基因復制保留到子代相同位置，第二階段是在父代染色體2上尋找子代染色體1缺少的基因并將這些基因以在父代染色體2中的順序填入，另一個子代以相同的方式產生，具體如圖4所示。

圖4 自適應交叉操作示意圖

為了保證迭代過程中解的多樣性，本文針對第一階段復制保留的基因數量采取自適應操作。即復制保留的基因數量與當前迭代次數相關，具體見式（10）。

其中，n表示第一階段被保留的基因個數，dim表示染色體上的基因總數，tmax表示最大迭代次數，t表示當前迭代次數，rand(-1,1)表示在(-1,1)之間的隨機數。

（6）變鄰域變異操作：經典遺傳算法在求解離散問題時往往采用互換變異方式，然而單一的變異方式不足以進行深入的搜索，所以本文采用三種變異方式，并從中選擇最優的個體作為最終的變異個體，具體如圖5所示。

圖5 變鄰域變異操作示意圖

（7）精英保留策略：將初始隨機種群P0和經過選擇、交叉、變異的種群Q0進行合并，形成個體數量為2×Popsize的種群R0。計算所有個體的適應度，將適應度較高的個體保留到下一代中，從而形成新一代種群P1[11]。具體如圖6所示。

圖6 精英保留策略示意圖

2.2 算法設計

2.2.1 編碼方式。本文采用的編碼方式是基于順序庫存量單位對貨位進行編碼。即產生一個[1,a×b]的隨機序列作為初始個體。具體如圖7所示。

圖7 編碼示意圖

圖7表示第1類第1個庫存量放置在第7號存儲貨位，第1類第2個庫存量放置在第9號存儲貨位，以此類推，第n類貨物的第kn個庫存量放置在第6號存儲貨位。

存儲貨位的編號方式如下：距離原點最近的存儲貨位編號為1，沿y軸正方向延伸的存儲貨位編號依次增加。當該行存儲貨位全部編號完成后，再對更高一層進行編號，每層編號規則均為沿y軸正方向延伸的存儲貨位編號依次增加，當該排貨架全部編號完成后，再對沿x正方向的貨架排進行編號。即編號的順序遵循先對y軸正方向，再對z軸正方向，最后是x軸正方向。具體如圖8所示。

圖8 貨位編號示意圖

2.2.2 重心調整操作。如果個體的重心高度超過給定高度，則對其進行調整。具體調整操作為：首先隨機選取兩個貨物，其次比較兩者的重量和重心高度。如果重量較大者位置也較高則兩者互換位置，否則不操作。再次計算當前擺放情況的重心高度，若滿足約束則結束操作，若不滿足則繼續隨機選取兩個貨物，重復上述操作直至滿足重心約束或者達到最大操作次數。算法流程圖如圖9所示。

圖9 重心調整操作算法流程圖

3 實例驗證及分析

在本節中，首先描述測試問題的生成過程。其次基于不同規模的算例對本文提出的改進自適應交叉變異遺傳算法進行評估，并將其與貪婪算法和經典遺傳算法進行比較。最后通過實驗結果說明幾個關鍵因素對貨物搬運效率和品類集中度的影響。

3.1 數據產生

首先生成三組不同規模測試算例（小規模、中規模、大規模）。根據實地觀察，無論存儲貨位和銷售貨位的數量如何變化，始終保持兩條巷道的布局，即一條巷道沿x軸方向，一條巷道沿y軸方向，巷道寬度l也固定為2m。每個存儲貨位和銷售貨位的長、寬、高也保持不變，即?x=1,?y=1.2,?z=1.4。機械臂的移動速度也保持不變，即vx=0.5,vy=1,vz=0.2。而問題規模不同，存儲貨位和銷售貨位的數量也不同，相應地存儲貨位和銷售貨位的陳列方式也不同。另外，由于兩個目標函數值量綱相差較大，為了平衡量綱，將權重設置為0.001。其他參數具體設置見表2。

表2 實驗參數表

遺傳算法的相關參數設置如下：種群大小Popsize=100，最大迭代次數Genmax=400，交叉概率Pc=0.7，變異概率Pm=0.3。

不同規模的貨物種類產生方式為：通過產生n個隨機正整數，且其和為U，每個隨機正整數表示每類貨物所包含的庫存量單位個數。

3.2 算法性能評估

為了證明改進自適應交叉變異遺傳算法的優越性，本文引入一般的貪婪算法進行對比。貪婪算法的具體規則如下：

步驟1：對所有存儲貨位進行編號。

步驟2：將各類貨物按平均重量由大到小排序，不妨設第1 類貨物的平均重量最大，第2 類次之，……，第n類貨物平均重量最小。對同類貨物內部也按重量由大到小排序，比如第i類貨品的第1個貨物最重，第2個貨物次之，…，第ki個貨物最輕。令Oi,j表示第i類貨物中第j個貨物，并令Vi,j(s) 為第s個存儲貨位到Oi,j的銷售貨位的F1目標函數值。

步驟3:fori=1,2,…,n,j=1,2,…,ki，do:令S為當前高度最低的所有空閑存儲貨位的集合，并對任意s∈S，計算Vi,j(s)；選出S中Vi,j(s) 值最小的存儲貨位，比如；指派貨物Oi,j到存儲貨位。

為了更準確地評估經典GA算法和改進自適應交叉變異GA算法的性能?，F做出如下定義：

其中，GAPBefore(i),GAPAfter(i)分別表示經典遺傳算法的優化率和改進遺傳算法的優化率。ZGreedy(i)表示第i個算例中貪婪算法的目標函數值；ZBefore(i)表示第i個算例中經典遺傳算法的目標函數值；ZAfter(i)表示第i個算例中改進遺傳算法的目標函數值。

每個算例進行五次實驗并計算五次實驗結果的平均值作為該算法的最終結果。最終實驗結果見表3。

表3 算法結果表

由表3可以看出，無論是小、中、大規模，改進自適應交叉變異遺傳算法的優化效果明顯優于經典遺傳算法和貪婪算法。其在貪婪算法結果的基礎上最小者優化了5.31%，最大者優化了31.13%。與經典遺傳算法相比，改進自適應交叉變異遺傳算法平均優化效果提升了6.78%。

實驗的迭代曲線如圖10所示?？梢钥闯龈倪M后的遺傳算法比經典遺傳算法能夠更快速地收斂，而且目標函數值也更低，能有效地防止算法陷入局部最優解。由此可得改進后的遺傳算法無論是在求解效率還是求解效果上均優于經典遺傳算法。

圖10 算法迭代圖

3.3 關鍵參數對目標函數的影響

將表3的目標函數值繪制成如圖11所示的折線圖?？梢钥闯?，在同一問題規模下，存儲貨架的層數越低，目標函數值越小。所以管理者在布置存儲貨位時，應盡可能地降低貨架總層數。

圖11 不同算例下算法結果對比圖

4 結語

本文針對儲銷一體化的貨位優化問題建立了多目標優化的數學模型，采用自適應交叉變異的遺傳算法，即對遺傳算法中的交叉和變異操作進行針對性優化并引入經營策略以增強算法的全局搜索能力。通過多次仿真實驗驗證了改進算法相對于貪婪算法的優越性，算法結果可以獲得更短的搬運時間和更集中的貨物擺放。此外，根據算法結果也總結出相應的管理啟示，在布置存儲貨位時，應當盡可能降低貨架總層數。