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

徐澤宇，楊 雙

（暨南大學(xué) 管理學(xué)院，廣東 廣州 510000）

0 引言

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

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

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

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

1 儲銷混合貨位優(yōu)化模型

1.1 問題描述

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

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

1.2 假設(shè)條件

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

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

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

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

（5）每個(gè)存儲貨位和銷售貨位都只能存放一種貨物的一個(gè)庫存量單位，一個(gè)庫存量單位也只能放在一個(gè)貨位上，且?guī)齑媪繂挝皇亲钚〉拇娣艈挝?，不可拆分?/p>

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

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

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

（9）貨物到達(dá)貨位中心即視為貨物放置完成，不考慮貨物放置后的調(diào)整時(shí)間。

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

1.3 符號說明

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

表1 符號定義

1.4 目標(biāo)函數(shù)

建立貨位優(yōu)化模型的目標(biāo)函數(shù)，需要遵守以下幾個(gè)原則：

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

（2）產(chǎn)品相關(guān)性原則。為了便于存儲貨架上貨物的管理和保存，使存儲貨架上的貨物排列整齊有序，每種貨物在存放時(shí)應(yīng)當(dāng)盡可能的集中布置[7]。

由此做出如下定義：

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

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

按照產(chǎn)品關(guān)聯(lián)規(guī)則，將相關(guān)性最強(qiáng)的貨物盡可能擺在靠近的位置，以每一類的類內(nèi)產(chǎn)品距離最小、類間產(chǎn)品距離最大為目標(biāo)函數(shù)F2。

1.5 約束條件

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

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

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

圖2 儲-銷貨架俯視圖

圖3 改進(jìn)自適應(yīng)交叉變異的遺傳算法流程圖

1.6 建立模型

綜上所述，可以建立如下所示的貨位優(yōu)化模型

s.t.

其中，F(xiàn)1表示補(bǔ)貨效率最優(yōu)，F(xiàn)2表示同種貨物集中布置、不同種貨物分散布置，D和di的具體計(jì)算見式（3）和式（5）。第一個(gè)約束條件表示一個(gè)貨位只能放置一個(gè)貨物，第二個(gè)約束條件表示貨架重心控制在一定高度以下，第三個(gè)約束條件表示貨物擺放在貨位中心上。

2 改進(jìn)自適應(yīng)交叉變異的遺傳算法

2.1 改進(jìn)自適應(yīng)交叉變異的遺傳算法流程

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

改進(jìn)自適應(yīng)交叉變異GA的具體步驟如下：

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

（2）初始化種群：采用實(shí)數(shù)編碼產(chǎn)生個(gè)體數(shù)量為Popsize的隨機(jī)初始種群。

（3）計(jì)算每個(gè)個(gè)體的適應(yīng)度：根據(jù)前文公式計(jì)算每個(gè)個(gè)體的目標(biāo)函數(shù)值。

（4）選擇操作：采用二元錦標(biāo)賽選擇法，隨機(jī)選取兩個(gè)個(gè)體，將目標(biāo)函數(shù)值較小的個(gè)體放入子代種群中。

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

圖4 自適應(yīng)交叉操作示意圖

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

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

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

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

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

圖6 精英保留策略示意圖

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

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

圖7 編碼示意圖

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

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

圖8 貨位編號示意圖

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

圖9 重心調(diào)整操作算法流程圖

3 實(shí)例驗(yàn)證及分析

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

3.1 數(shù)據(jù)產(chǎn)生

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

表2 實(shí)驗(yàn)參數(shù)表

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

不同規(guī)模的貨物種類產(chǎn)生方式為：通過產(chǎn)生n個(gè)隨機(jī)正整數(shù)，且其和為U，每個(gè)隨機(jī)正整數(shù)表示每類貨物所包含的庫存量單位個(gè)數(shù)。

3.2 算法性能評估

為了證明改進(jìn)自適應(yīng)交叉變異遺傳算法的優(yōu)越性，本文引入一般的貪婪算法進(jìn)行對比。貪婪算法的具體規(guī)則如下：

步驟1：對所有存儲貨位進(jìn)行編號。

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

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

為了更準(zhǔn)確地評估經(jīng)典GA算法和改進(jìn)自適應(yīng)交叉變異GA算法的性能?，F(xiàn)做出如下定義：

其中，GAPBefore(i),GAPAfter(i)分別表示經(jīng)典遺傳算法的優(yōu)化率和改進(jìn)遺傳算法的優(yōu)化率。ZGreedy(i)表示第i個(gè)算例中貪婪算法的目標(biāo)函數(shù)值；ZBefore(i)表示第i個(gè)算例中經(jīng)典遺傳算法的目標(biāo)函數(shù)值；ZAfter(i)表示第i個(gè)算例中改進(jìn)遺傳算法的目標(biāo)函數(shù)值。

每個(gè)算例進(jìn)行五次實(shí)驗(yàn)并計(jì)算五次實(shí)驗(yàn)結(jié)果的平均值作為該算法的最終結(jié)果。最終實(shí)驗(yàn)結(jié)果見表3。

表3 算法結(jié)果表

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

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

圖10 算法迭代圖

3.3 關(guān)鍵參數(shù)對目標(biāo)函數(shù)的影響

將表3的目標(biāo)函數(shù)值繪制成如圖11所示的折線圖。可以看出，在同一問題規(guī)模下，存儲貨架的層數(shù)越低，目標(biāo)函數(shù)值越小。所以管理者在布置存儲貨位時(shí)，應(yīng)盡可能地降低貨架總層數(shù)。

圖11 不同算例下算法結(jié)果對比圖

4 結(jié)語

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