基于“貨到人”揀選模式的儲位分配問題研究

李珍萍， 范欣然, 吳凌云

(1.北京物資學院 信息學院,北京 101149; 2.中國科學院 數學與系統科學研究院應用數學研究所管理、決策與信息系統重點實驗室,北京 100190; 3.中國科學院大學 數學科學學院,北京 100049)

0 引言

近年來，電子商務的快速發展改變了消費者的購物習慣和企業的商業運作模式，為了快速處理多品種、小批量、多批次的碎片化訂單,“貨到人”揀選模式受到越來越多國內外電商企業的關注，早在2012年，亞馬遜以7.75億美元收購了Kiva系統并建立了基于AGV的智能倉庫，將訂單揀選效率提高了一倍。在貨到人揀選模式下，物品按照一定的規則擺放在貨架上，揀選人員站在固定的揀選臺前，當有訂單需要揀選時，搬運機器人(AGV)會將指定的貨架搬到揀選工作臺供揀選人員從貨架上揀取物品[1～3]。由于在貨到人揀選模式下，搬運機器人(AGV)需要不停地搬運貨架到揀選口，因此，儲位分配規則將直接影響訂單揀選過程中的貨架搬運次數和搬運時間(成本)，從而影響訂單揀選效率。研究貨到人揀選模式下的儲位分配問題，對于提高訂單揀選效率，降低揀選成本具有重要意義[2]。

雖然關于儲位分配問題已經有大量的研究成果，但這些研究大部分都是針對傳統人到貨揀選模式的[4～15]。由于貨到人揀選模式與人到貨揀選模式具有本質的區別，因此已有的關于人到貨揀選模式下的儲位分配方法并不能直接用于解決貨到人揀選模式下的儲位分配問題。近年來，部分學者針對貨到人揀選模式下的儲位分配問題開展了一些初步的研究工作。周方圓等以總揀選成本最小化為目標建立了基于AGV的貨到人揀選模式下的儲位分配問題數學模型，在一種物品可以同時存放在多個儲位的前提下設計了求解模型的啟發式算法[16]。Li等研究了基于AGV的貨到人揀選系統中物品儲位已知的情況下對于給定的待揀選訂單如何確定擬搬運貨架的問題，以搬運貨架總時間極小化為目標建立了混合整數規劃模型，并設計了求解模型的啟發式算法[17]。Yuan等[18,190]通過模擬實驗方法研究了貨到人揀選模式下基于工作量均衡的分區同步揀貨儲位分配問題，在一種物品只能存放到一個分區的假設下，設計了按照物品的出庫速率確定物品儲位所在分區的入庫策略，但該研究并沒有考慮物品之間的相關性。

除了基于AGV的貨到人揀選模式以外，還有一些學者從不同角度研究了基于堆垛機的自動化立體倉庫中的儲位分配問題[20～22]。雖然基于堆垛機的自動化立體倉庫采用的也是“貨到人”揀選模式，但自動化立體倉庫中的堆垛機工作原理與AGV搬運貨架的工作原理不同，自動化立體倉庫中每個托盤上只存放一種物品，堆垛機每次只能移動一個托盤，相當于每次只能揀選一種物品；基于AGV的貨到人揀選模式中，每個貨架上有多個儲位，每個儲位可以存放一種或一組綁定的物品組合(如亞馬遜智能倉庫就是把一組綁定的物品組合存放在一個儲位上[23])，因此一個貨架上可以同時存放多種物品。 AGV每次將一個貨架搬運到揀選口，工作人員可以同時揀選一個貨架上的多種物品。可見，基于AGV的貨到人揀選模式下的儲位分配問題比基于堆垛機的自動化立體倉庫中的儲位分配問題更加復雜。

本文擬對基于AGV的貨到人揀選模式下的儲位分配問題開展深入研究。以訂單揀選過程中搬運貨架的總行駛時間(成本)最小化為目標建立靜態儲位分配問題的優化模型，并設計求解模型的算法。

1 問題描述與分析

假設某智能倉庫采用基于AGV的貨到人揀選模式，該倉庫擬將m種物品存儲于n個可移動貨架上。每個貨架上有h個儲位，每個儲位最多可以存放一種物品，因此每個貨架最多可以存放h種物品(其中m≤nh)。已知每個貨架的位置及AGV搬運每個貨架到揀選口的來回行走成本(時間)。根據歷史訂單信息可以統計出每種物品的歷史出庫頻率，已知未來一段時間內需要揀選的R個訂單中包含的物品種類等信息。假設每種物品至少存放在一個貨架的某個儲位上，揀選每個訂單都需要把包含訂單中某種物品的至少一個貨架搬運至揀選口。問題是如何將m種物品擺放到n個貨架上，才能使未來一段時間內揀選R個訂單的過程中AGV搬運貨架的總行駛成本(時間)最小。

由于貨到人智能倉庫主要存放的是多品種、小批量的小件物品[1～3]，顧客對這些物品的需求特點是：每個訂單中包含一種或多種物品，但每一種物品的需求量較少。因此可以假設倉庫中每種物品在一個貨位上的存放數量能夠滿足一段時間內的訂單需求，不需要考慮缺貨的情況。為了提高顧客的滿意度，大部分電商企業面對源源不斷的在線訂單都會采取實時揀選策略，實時揀選策略有兩種方式：一種是按單個訂單進行揀選，即每收到一個訂單就組織一次揀選，揀選完一個訂單再揀選下一個訂單；另一種是分批次揀選，即以很小的時間段(比如10分鐘)進行截單，對一個時間段內收到的所有訂單同時進行揀選。如果把按時間段截單得到的所有訂單看成一個合并的訂單組合(或揀選單)，則按時間分段的揀選也可以看成按照單個訂單進行揀選。本文主要考慮按訂單揀選方式。在按訂單揀選方式下，如果不考慮AGV空載行駛成本(時間)，則揀選每個訂單的成本與AGV搬運貨架的總行駛成本(時間)有關。當揀選一個訂單需要搬運多個貨架的時候，雖然多個AGV協同工作可以有效減少完成訂單揀選的時間(由于多個AGV同時搬運貨架)，但并不能減少所有AGV搬運多個貨架的總時間。由于AGV搬運貨架的成本與搬運貨架的總時間有關，因此，本文不考慮多個AGV協同工作的情況。

基于以上分析，為了簡化問題，本文做出如下假設：

(1)每個貨架的每個儲位最多存放一種物品；且每個儲位上存放的物品數量足以滿足未來一段時間揀選R個訂單的需求；

(2)每種物品至少存放在一個貨架的某個儲位上[1～3]；

(3)揀選一個訂單中的某種物品時，只需要把包含該物品的一個貨架搬運到揀選口即可[17]；

(4)訂單揀選過程中，不考慮AGV空載行駛成本(時間)和排隊等待揀選的成本(時間)，只考慮AGV頂著貨架來回行駛的成本(時間)；

(5)每個貨架在倉庫中的位置固定，即AGV每次從倉庫中搬運貨架到揀選口，完成一個訂單的揀選以后，仍然將貨架放回倉庫中原來的貨架位置。

(6)不考慮訂單合并揀選的情況，即揀選完一個訂單再揀選下一個訂單。

(7)不考慮多個AGV協同工作的情況。

2 儲位分配問題的整數非線性規劃模型

為了建立儲位分配問題的數學模型，首先定義如下符號：

m：物品種類；n：貨架個數；h：每個貨架上的儲位個數；tj：AGV搬運貨架j到揀選臺的來回行駛成本(時間)；R：待揀選的訂單個數；

定義決策變量：

以揀選訂單過程中AGV搬運貨架總行駛成本(時間)極小化為目標函數的儲位分配問題可以表示成如下整數非線性規劃模型:

目標函數(1)表示極小化完成R個訂單揀選需要AGV搬運貨架的總行駛成本(時間)；約束條件(2)表示每個貨架最多可以存放h種物品，該約束等價于每個貨位最多存放一種物品；約束條件(3)表示每種物品至少存放在一個貨架上；約束條件(4)表示如果第k個訂單中包含物品i, 則揀選第k個訂單中物品i時至少要將一個包含物品i的貨架搬運至揀選口；約束條件(5)(6)為變量取值約束。

貨到人揀選模式下的儲位分配問題可以表示成整數非線性規劃模型(1)～(6)，可以證明當每個貨架上的貨位數h大于2的時候，該問題屬于NP-hard問題。

定理1當h>2時，模型(1)～(6)對應的貨到人揀選模式下的儲位分配問題是NP-hard問題。

證明模型(1)～(6)對應的問題可以看成由儲位分配和貨架選擇兩個子問題構成的聯合優化問題。其中儲位分配子問題的決策變量為xij，約束條件包括(1)(2)(3)(5)；貨架選擇子問題的決策變量是ykj，約束條件包括(4)(6)，目標函數是(1)。

在儲位分配結果已知(即xij取值確定)的情況下，由式(1)(4)(6)構成的貨架選擇子問題等價于若干個獨立的賦權集合覆蓋問題[23]的和，其中每一個待揀選訂單相當于一個待覆蓋的全集，每一個貨架相當于一個子集，子集對應的權重就是搬運貨架的時間。由于當子集中包含的元素個數大于2(即一個貨架上的儲位個數大于2)的時候，賦權集合覆蓋問題是NP-hard問題[23]。因此當h>2時，貨架選擇子問題是NP-難問題。

綜上可以推出，由模型(1)～(6)定義的貨到人揀選模式下的儲位分配問題是NP-hard問題。

3 算法設計

由于貨到人揀選模式下的儲位分配問題是NP-hard問題，雖然該問題可以表示為整數非線性規劃模型，理論上當問題規模較小時，可以直接求解整數非線性規劃模型得到精確最優解。但實際中的儲位分配問題涉及到的物品、貨架、訂單等數量巨大，其對應模型中的決策變量和約束條件都很多，難以在短時間內通過求解整數非線性規劃模型得到精確最優解，因此需要設計求解模型的快速有效算法。

本文將根據物品的歷史出庫頻率、待揀選訂單中包含的物品信息等，分別設計兩種求解模型的算法：基于聚類的貪婪算法和單親進化遺傳算法。

3.1 基于聚類的貪婪算法

算法的基本思想：首先根據歷史訂單(或者待揀選訂單)中包含的物品種類等信息對物品進行聚類；再根據每個貨架上的儲位數量、每種物品的出庫頻率和各個貨架對應的搬運時間等信息，利用貪婪思想對聚類以后的物品進行分組，并確定每一組物品對應的貨架。

算法的步驟：

第1步利用K-means方法對物品進行聚類(其中類別數目由用戶自行設定)。

根據訂單物品之間的關聯關系和用戶設定的類別數目，利用歐氏距離公式，采用K-means算法對物品進行聚類。由于聚類過程中考慮了訂單與物品的關聯性，因此聚類后的同一類中的物品之間的關聯度較大，同一類物品被同時訂購的可能性也較大。

第2步對聚類后的物品進行二次分組。

根據聚類以后每類中包含的物品種類和一個貨架上的儲位數h，確定每類物品需要占用的貨架數量并將每類物品分成一組或多組，使得每組物品剛好可以存放在一個貨架上。

當某一類中的物品需要存放在多個貨架上時，可以按照該類中各種物品的歷史出庫頻次由大到小排序，根據排序對物品進行二次分組，使得每組中的物品種類均不超過h，即每組物品都可以存放在一個貨架上。

第3步計算二次分組后每一組物品對應的貨架搬運總次數，確定每一組物品對應的貨架位置。

計算二次分組后每一組物品對應的出庫頻次(即每組物品對應的貨架在訂單揀選過程中需要搬運的總次數)，按照每組物品對應貨架的搬運總次數確定每一組物品應該存放的具體貨架。盡可能將出庫頻次較高的分組放到搬運時間較短的貨架上。

注實際使用該算法時有可能出現某些分組包含物品種類較少的情況，為了提高儲位利用率，可以在第2步中將物品種類較少的分組合并。

3.2 單親進化遺傳算法

在基于聚類的貪婪算法中，如果不同類別的物品不允許擺放在同一個貨架上，則物品需要占用較多的貨架。而且當同一類中物品種類較多時，直接按照物品的出庫頻次進行二次分組，并不能很好的體現物品之間的關聯關系。為了提高儲位利用率并降低揀選成本，本節將設計基于精英保留的單親進化遺傳算法直接求解儲位分配模型。

3.2.1 單親進化遺傳算法操作規則

(1)染色體編碼

采用0,1矩陣編碼方式表示m種物品在n個貨架上的儲位分配方案。具體編碼方法如下：矩陣共有m行n列，每一行對應一種物品，每一列對應一個貨架。由于每一種物品至少擺放在一個儲位上，每一個貨架最多有h個儲位，因此矩陣中每一行至少有一個1，每一列最多有h個1。如：

表示5種物品在3個貨架上的儲位分配結果，其中第1種和第3種物品擺放在第一個貨架上，第2種和第5種物品擺放在第2個貨架上，第4種物品同時擺放在第1和第3個貨架上。本文只考慮物品和貨架之間的對應關系，至于擺放在同一個貨架上的多種物品，可以隨機分配儲位。編碼矩陣中的元素等于整數非線性規劃模型中的決策變量xij。

(2)種群初始化

根據染色體編碼方式，隨機產生若干個m行n列的0,1矩陣，矩陣的每行至少一個1，每列中1的個數不超過h個。

(3)適應度

對于每個個體解碼后得到的儲位分配方案，首先根據每個待揀選訂單中包含的物品是否在某個貨架上出現確定揀選訂單過程中是否需要搬運該貨架(如果待揀選訂單中的一種或多種物品出現在某個貨架上，則需要搬運該貨架，即ykj=1；否則該貨架不需要搬運，即ykj=0)；然后計算出揀選每個訂單需要搬運貨架的總時間，進一步求出揀選所有訂單需要搬運貨架的總時間，即整數規劃模型的目標函數值。

其中tj表示AGV搬運貨架j到揀選臺的來回行走時間；ykj為決策變量，揀選第k個訂單需要搬運貨架j時為1，不需要搬運時為0。

由于整數規劃模型的目標函數為極小化的，本文定義適用度函數為目標函數的倒數，即fitness=1/z。

(4)交叉操作

采用單親染色體多點基因倒位算子實現交叉操作。具體交叉操作規則是：從個體編碼矩陣中隨機選擇連續的若干行，將選中的行倒序排列得到交叉后的染色體編碼矩陣。

如交叉前的染色體編碼矩陣為：

如果選中第2，3，4行，則交叉后的染色體編碼矩陣為：

采用這種交叉操作，交叉后的個體仍然對應可行解。

(5)變異操作

根據儲位分配問題的約束條件和染色體編碼規則，本文采用單點突變變異算子進行變異操作。即從染色體編碼矩陣中隨機選擇兩行，交換兩行的位置。如：

變異前的染色體編碼矩陣為：

如果選擇了第2、3兩行，則變異后的染色體為：

(6)精英保留策略

本文采用精英保留策略，將每一代中適用度最大的前10%的個體直接保留至下一代，下一代中的其余90%的個體則是從變異后的個體中選擇的適用度最大的前90%。

(7)終止規則

本文設定的最大迭代次數作為終止條件，當迭代次數到達最大值時，終止運行并將最后一代中適用度最大的個體對應的解作為最優解。

3.2.2 單親進化遺傳算法的計算步驟

初始化：設置種群規模、最大迭代次數、交叉概率、變異概率等參數；

第1步隨機產生初始種群，計算每個個體對應的適用度值；令迭代次數t=0；

第2步將種群中的個體按照適用度值由大到小排序；判斷迭代次數是否達到預先設定的最大迭代次數, 若是則結束計算，將適用度最大的個體對應的解作為近似最優解輸出；否則轉第3步；

第3步根據精英保留策略，選擇適用度最高的10%的個體，直接保留進入下一代；令當前代個體全部進入交配池；

第4步按照交叉概率從交配池中選擇部分個體進行交叉操作；

第5步按照變異概率從交配池中選擇部分個體進行變異操作；

第6步計算變異后交配池中個體的適應度，從中選擇適應度最高的前90%的個體進入下一代；與第3步保留下來的10%的個體合并在一起，構成下一代種群；令迭代次數t=t+1，返回第2步；

輸出：最優的儲位分配方案及對應的目標函數值。

3.3 算法復雜性分析

定理2基于聚類的貪婪算法的時間復雜度為O(Rmn2)，單親進化遺傳算法時間復雜度為O(TPmn)。

證明在基于聚類的貪婪算法中，第1步K-means聚類的計算量不超過O(tkmn),其中t為K-means聚類的迭代次數，k為聚類個數，這里k最大可以取值為R；第2步二次分組的計算次數不超過O(m)，第3步確定每個訂單揀選過程中需要搬運的貨架,計算量不超過O(Rmn2)[17],綜上，基于聚類的貪婪算法時間復雜度為max{O(tRmn),O(Rmn2)}。當K-means聚類的迭代次數t不超過貨架個數n的時候，算法的時間復雜度為O(Rmn2)。

對于單親進化遺傳算法，假設種群規模為P,最大迭代次數為T，則每一次迭代中，第1步計算適用度函數的復雜度為O(Pmn)，第2步按照適用度函數值排序的復雜度為O(PlogP)，第3～5步的復雜度為O(Pmn)，第6步的復雜度為O(Pmn)。假設且logP≤mn，則整個算法的時間復雜度為O(TPmn)。

由以上分析可以看出，當倉庫中的貨架個數n>TP時，基于聚類的貪婪算法復雜度大于單親進化遺傳算法，當單親進化遺傳算法的迭代次數T或種群規模P較大時，其計算復雜度將超過基于聚類的貪婪算法。

4 模擬計算與分析

4.1 小規模算例的分析

為了分析兩種算法的求解效果，本文利用不同參數(物品種類、貨架數目、待揀選訂單數目等)模擬產生了幾個小規模算例。首先利用Lingo軟件編程求解整數非線性規劃模型得到各個問題的全局最優解。然后分別利用本文設計的基于聚類的貪婪算法和單親進化遺傳算法求解，兩種算法均使用Matlab編程在i3-2367M CPU@ 1.40GHz筆記本電腦上運行，其中遺傳算法設置種群規模為50，最大迭代次數為1000次。表1記錄了兩種算法10次運算求得的最優目標函數值和10次運算中得到全局最優解的次數，表2記錄了各個算法10次運算對應的平均運行時間。

表1 兩種算法求解小規模算例得到的目標函數值分析

表2 各種算法求解小規模算例的平均運行時間

從表1可以看出，對于小規模問題，遺傳算法和貪婪算法均能以很大的概率得到問題的全局最優解，遺傳算法得到全局最優解的概率明顯高于貪婪算法。從表2可以看出，隨著問題規模的增大，遺傳算法和貪婪算法的計算時間增加不明顯。利用Lingo軟件直接求解整數規劃模型的計算時間隨著問題規模的增加呈指數增長，對于包含30種物品、5個貨架、100個訂單的問題，利用Lingo軟件求解整數規劃模型的運算時間已經超過12小時，但遺傳算法和貪婪算法的計算時間均不足10秒鐘。當問題規模增大到50種物品、10個貨架、100個訂單時，利用Lingo軟件求解整數規劃模型運算24小時仍然未得到問題的最優解，遺傳算法迭代1000次的計算時間為4.08秒，貪婪算法的運算時間為14.39秒。由此可見，隨著問題規模的增大，本文設計的兩種算法的計算速度優勢非常明顯。

4.2 不同規模算例的模擬計算與分析

為了進一步對比分析兩種算法的計算效果，我們模擬產生了一批不同規模(物品種類、貨架數目)的算例，假設各個算例對應的每個貨架上貨位數均為10，每個貨架對應的搬運時間服從[15,25]秒之間的均勻分布。對于每個算例分別用貪婪算法和遺傳算法確定儲位分配方案，其中遺傳算法設置種群規模為50，最大迭代次數為1000次。每個算例重復運行10次，表3中列出了10次模擬計算的最短運行時間、平均運行時間。根據兩種算法10次運算得到的最優儲位分配方案，分別計算了揀選100個訂單對應的搬運貨架總次數、搬運貨架總成本(時間)，見表4。

表3 兩種算法求解不同規模算例的運行時間表(單位：秒)

表4 兩種算法得到的最優儲位分配結果對應于100個訂單的揀選成本

從表3中可以看出，對于大規模問題，兩種算法均可以在較短的時間內得到問題的解，隨著問題規模的增大，兩種算法的運行時間均有所增長，且遺傳算法的運行時間均小于貪婪算法的運行時間。從表4中可以看出，對于各種規模的問題，遺傳算法得到的儲位分配結果對應于揀選100個訂單的貨架搬運次數和貨架搬運總時間均小于貪婪算法。

4.3 實際案例分析

某小型電子商務公司采用基于AGV的貨到人揀選模式，該公司倉庫中共有22個貨架，每個貨架上有10個儲位，每個儲位最多可以擺放一種物品。根據貨架在倉庫中的位置以及AGV搬運貨架時的行走速度等可以計算出AGV搬運每個貨架到揀選口的來回行走時間，見表5。

表5 各個貨架對應的來回搬運時間(單位：秒)

該公司主要經銷140種日用品和食品飲料等，目前公司采取的儲位分配策略是：直接根據歷史訂單統計物品的出庫頻率，依次將出庫頻率較大的物品擺放在離揀選口較近的貨架上，140種物品全部擺放在倉庫中的1～14號貨架上。

接下來我們將利用該公司2017/2/17和2017/2/18兩天共100個訂單的數據，分別使用貪婪算法和遺傳算法對該公司倉庫中的儲位進行優化，并分析優化前后的訂單揀選過程中需要搬運貨架的次數和搬運時間等。

(1)利用貪婪算法優化儲位

由于100個訂單中包含了該公司經銷的全部140種物品，首先根據每個訂單中包含的物品詳細信息，利用K-means聚類方法將140種物品聚為13類；再根據每類中包含的不同物品種類數，按照每個貨架上最多可以擺放10種物品計算出每類物品需要占用的貨架個數。每類包含的物品種類、需要占用貨架個數等信息如表6所示。

表6 140種物品的聚類結果統計表

對于需要占用多個貨架的類別(如第1類)進行二次分組。將同一類中各種物品在100個訂單中出現的次數(即物品的出庫頻次)從大到小排序，把出現頻次最高的10種物品分為一組，出庫頻次排序在11～20的物品分為第二組，依次類推，直到所有物品分組完畢為止。二次分組后每一組物品均可以擺放在一個貨架上，根據以上方法可以將表2中的13類物品分為22組，見表7。

由于每一組物品可以擺放在一個貨架上，當進行訂單揀選時，每次搬運一組物品對應的貨架時都可以同時揀選到貨架上的所有物品，因此該組物品對應的貨架搬運次數并不等于物品的出庫頻次之和。為此，需要根據每個訂單中包含的物品種類計算揀選每個訂單時各組物品對應的貨架搬運次數，進一步計算出揀選100個訂單的過程中，每組物品對應的貨架總搬運次數，結果見表7。

表7 各組物品對應的總出庫頻次及對應貨架的總搬運次數

根據每組物品對應貨架的總搬運次數，由大到小對分組進行排序，再根據倉庫中每個貨架對應的搬運時間由小到大對貨架進行排序，依次確定每個分組對應的貨架位置。如第一組物品對應的貨架總搬運次數最高，因此第一組物品應該擺放在搬運時間最短的1號貨架上，依次類推，第12組物品對應的貨架搬運次數最少，因此第12組物品擺放在搬運時間最長的22號貨架上。按照這種儲位分配結果，揀選100個訂單需要搬運貨架的總次數為326次，總搬運時間為6697秒。

由于以上算法對應的有些分組中的物品數量較少，為了提高倉庫中的貨位利用率，減少遠距離貨架的使用。可以考慮把包含物品種類較少的分組合并在一起。如本例中可以把第5、7、22組合并；6、8、9組合并；13、14、16組合并；17、18組合并；12、21組合并。合并后的變成14組，每組均包含10種物品。分別計算合并后每組物品對應貨架的出庫頻次，按照出庫頻次從大到小為每組物品安排貨架得到貨位分配方案，此時140種物品可以全部存放在搬運時間較短的1～14號貨架上。該方案對應的揀選100個訂單的貨架搬運次數仍然為326次，總搬運時間為6599秒。由于分組合并以后減少了遠距離貨架的使用，因此總的貨架搬運時間有所降低。

(2)利用單親進化遺傳算法優化儲位

利用單親進化遺傳算法直接對140種物品進行儲位分配時，設置參數為：種群規模為50，最大迭代次數為1000，交叉概率0.5，變異概率為0.1。利用Matlab編寫遺傳算法實現程序，在i3-2367M CPU@ 1.40GHz處理器、32位操作系統配置的電腦上運行5.59秒，得到近似最優的儲位分配方案。140種物品全部存放在1～14號貨架上。按照該儲位分配方案揀選100個訂單需要搬運貨架的次數為273次，總搬運時間為5656秒。

(3)結果分析

表8分別記錄了兩種算法得到的儲位分配方案對應的揀選100個訂單過程中需要搬運貨架的總次數、搬運貨架的總時間、以及算法運行總時間，表8中最后一行是按照該公司目前的基于出庫頻率的儲位分配方案揀選100個訂單的貨架搬運總次數、貨架搬運總時間等。

表8 計算結果分析

從表8中可以看出，無論是使用遺傳算法還是貪婪算法得到的儲位分配方案都比該公司目前采用的基于出庫頻率的儲位分配方案好。與該公司目前采用的基于出庫頻率的儲位分配方案相比，兩種算法得到的儲位分配結果對應揀選100個訂單時需要搬運貨架的總次數分別減少了19%和3.26%。揀選100個訂單的貨架搬運總時間分別降低了16.8%、3%(采取分組合并策略)和2%(未采取分組合并策略)。這說明了考慮物品之間的關聯性在基于AGV的貨到人揀選模式下的儲位分配問題中確實能大幅提高揀選的效率。使用貪婪算法時，如果采取二次分組合并策略，可以減少貨架的使用數量，提高貨架利用率，同時也能降低貨架總搬運時間，可見在貪婪算法中加入二次分組合并策略可以有效改善解的質量。從計算時間來看，加入分組合并策略以后貪婪算法的計算時間會有所增加，二次分組合并問題本身也是一個組合優化問題，隨著問題規模的增大，計算時間可能增加比較明顯。綜合考慮各項指標可以發現，遺傳算法無論是計算速度還是計算效果都明顯優于貪婪算法。

對于本節的實際問題，我們也嘗試利用優化軟件Lingo和GLPK分別編程直接求解整數規劃模型，兩個程序連續運行700多個小時都沒有得到最終計算結果，因此該問題不適合使用優化軟件直接求解整數規劃模型。

4.4 算法優劣分析

本文設計的基于聚類的貪婪算法結合了聚類和貪婪算法的優點，通過聚類將經常出現于同一訂單并且類型相近的物品劃分為一類，體現了訂單與物品、物品與物品之間的關聯關系，另一方面將二次分組以后的物品，按照對應的貨架搬運次數由大到小依次安排儲位，有利于提高訂單揀選效率，但是使用該方法時如果不采取二次分組合并策略，就會出現某些貨架上物品種類很少的情況，導致占用較多的貨架，在一定程度上會造成儲位資源的浪費。如果在貪婪算法中加入二次分組合并策略，則可以將包含物品種類較少的分組合并在一起，從而有效減少貨架的使用數量，提高儲位利用率，同時也能減少訂單揀選過程中的貨架搬運總時間。因此加入分組合并策略的貪婪算法優于不加入分組合并策略的貪婪算法。

本文設計的基于精英保留的單親進化遺傳算法直接求解儲位分配模型，不僅可以使關聯度較大的物品盡可能擺放在相同的貨架上，以減少訂單揀選過程中搬運貨架的總次數，降低搬運貨架的總時間，而且還能有效避免出現空缺的貨位，減少貨架的使用數量，提高倉庫中的儲位利用率。由于該算法計算速度快，效果好，因此可以作為智能倉庫管理信息系統的核心算法。

本文研究的問題中需要根據歷史訂單的信息進行儲位分配，再根據待揀選訂單信息對儲位分配結果進行評價，實際問題中歷史訂單和待揀選訂單的數量往往都很多，即便是小規模的問題，其整數非線性規劃模型的決策變量和約束條件也很多。由于儲位分配問題屬于NP難問題，對于中等以上規模的問題不適合直接利用整數非線性規劃模型求解。利用本文設計的兩種算法均可以在短時間內得到大規模問題的近似最優解。

5 結論

本文研究了基于AGV的貨到人揀選模式下的靜態儲位分配問題，建立了以揀選訂單過程中搬運貨架總時間最短為目標的整數非線性規劃模型，設計了求解模型的貪婪算法和單親進化遺傳算法。分別利用模擬數據和電商企業的真實數據進行了計算，并分析了各個算法的計算效果。

基于AGV的智能倉庫自出現以來受到國內外大型電商企業的高度關注，亞馬遜等大型企業已經將基于AGV的貨到人智能倉庫系統成功應用于倉儲管理中，并大大提高了訂單揀選效率。現階段某些智能倉庫系統中采用的是綁定貨品組合的隨機儲位分配策略，即根據歷史訂單信息，首先將訂單與物品綁定形成固定的貨品組合，然后以固定的貨品組合為存儲單元在有空閑儲位的貨架中隨機為其分配儲位[24]。由于歷史訂單種類繁多(且很多歷史訂單出庫頻率較低)，因此訂單與物品綁定以后形成的貨品組合種類繁多，由于每一類貨品組合都至少需要占用一個儲位，所以以歷史訂單綁定形成的貨品組合為存儲單元的存儲方式必然需要占用大量的貨架(儲位)。本文給出的儲位分配策略是以物品為存儲單元的，由于物品的種類遠遠小于物品組合的種類，因此按照本文的儲位分配策略可以大大減少貨架的使用數量，另外，本文在分配儲位的時候考慮了物品之間的關聯關系，將關聯度較大的物品盡可能存放在一個貨架上，因此可以有效減少訂單揀選過程中搬運貨架的次數，降低揀選成本、提高揀選效率。

本文研究中假設一個儲位上的物品數量足夠滿足一段時間內的訂單揀選需求。實際中，由于不同物品出庫頻率相差較大，一個儲位上的存儲空間有限，對于出庫頻率較高的物品，一個儲位上的存儲量可能無法滿足一段時間內的訂單揀選需求，此時需要搬運多個包含該物品的貨架到揀選口，這種情況下，可以結合文獻[17]中的貨架選擇方法，確定揀選訂單時需要搬運的多個貨架的最佳組合。

本文研究的問題是在倉庫中所有的儲位上均為空閑儲位情況下的靜態儲位分配問題，接下來我們將研究倉庫中同時存在空閑儲位、需要補貨的儲位和不需要補貨的儲位等多種情況下，如何進行動態儲位分配的問題。我們還將研究較長時間內訂單揀選過程中的在線儲位分配問題，為解決智能物流倉儲系統設計問題提供理論依據和算法支持。