基于關聯網絡的機器人移動貨架系統貨位分配方法

胡祥培 丁天蓉 張源凱 莊燕玲

摘 要：作為一種新型智能訂單揀選系統，機器人移動貨架系統為解決大型網上超市面臨的一單多品訂單揀選難題提供了前所未有的機遇，而貨位分配是關系該系統運行效率最為核心的關鍵環節之一。針對該系統一品多位貨位分配問題帶來的商品關聯關系復雜、解空間巨大等難題，本文以提高貨架商品間關聯性為目標，基于縮減問題解空間的思想，提出“關聯網絡構建→關聯網絡分析→關聯網絡聚類”的三階段貨位分配方法，將聚類的商品網絡映射成貨架對應的貨位擺放來快速高效生成貨位分配方案。利用某網上超市的實際數據，將所提方法與國內外普遍應用的幾種方法進行對比，結果驗證了所提方法的高效性和實用性，可為網上超市等企業采用機器人移動貨架系統解決訂單履行難題提供理論指導和決策支持。

關鍵詞：機器人移動貨架系統;貨位分配;關聯網絡;聚類;“貨到人”揀選模式

中圖分類號：C934 文獻標識碼：A 文章編號：2097-0145（2022）01-0056-09 doi：10.11847/fj.41.1.56

Abstract：As a new intelligent order picking system， the robotic mobile fulfillment system plays an important role in solving the multi-item orders picking problem faced by online supermarkets. The efficiency of this system hinges on the storage assignment procedure. However， due to the complexity of product correlation and huge solution space， this storage assignment procedure is difficult to optimize. In order to reduce the solution space for the problem of storage assignment in robotic mobile fulfillment system， a three-stage method of “association network construction→association network analysis→association network clustering” is proposed to improve the relevance of products on the rack. This method lays the foundation for solving the storage assignment problem quickly and efficiently by mapping clusters to racks. Using the order data of an online supermarket， this paper compares the proposed method with several widely used methods. Results verify the effectiveness and practicability of the proposed method. This research provides theoretical guidance and decision support for companies who employ this system to solve order fulfillment problems.

Key words：robotic mobile fulfillment system; storage assignment; association network; clustering; parts-to-picker picking mode

1 引言

隨著互聯網的快速發展，網上購物已經成為一種新型購物方式。中國擁有全球最大的網絡零售市場，其中京東商城2020年成交總額達26125億元，訂單量仍在逐年遞增，同時每一個訂單平均包含7～8種商品[1]，傳統“人到貨”揀選模式面對訂單量的爆炸式增長以及高比例的一單多品訂單，導致倉庫運營成本激增，僅訂單揀選這一環節成本支出占倉庫運營成本65%以上[2]。揀貨員需執行高強度、遠距離的重復性揀選操作，揀選效率低下。

基于AGV（Automatic Guided Vehicle， 自動導引小車）的機器人移動貨架系統采用“貨到人”揀選模式，在提升一單多品訂單的揀選效率以及降低企業運營成本方面具有明顯優勢，已廣泛應用于各大網上超市（京東商城、亞馬遜）。然而，調研國內網上超市機器人移動貨架系統發現，該系統在實際應用中存在揀貨效率低等問題，究其原因，倉庫管理人員仍然按照傳統倉庫的貨位分配方法、并沒有根據電商具有的一單多品訂單、一貨多位特點進行貨位分配，導致機器人頻繁搬運貨架卻只能揀選很少的商品，而履行一個訂單通常又需要多個機器人搬運多個貨架，根據調研統計發現，某電商倉庫的訂單平均購買3種商品，AGV平均花費6分鐘搬運一個貨架卻僅僅揀選1.2種商品。這大大降低了該系統的運行效率。盡管電商也可以采取訂單分批[3]、機器人調度[4]等方式提高系統揀貨效率，但是由于貨位分配是該系統首要關鍵性決策，如果貨位未進行合理分配，后續再多的優化調度也是徒勞。因此，如何結合電商一單多品、一貨多位的特點，研究機器人移動貨架系統的貨位分配問題，已經成為應用機器人移動貨架系統亟需解決的關鍵難題。

傳統貨位分配研究主要集中于“人到貨”揀選模式，“貨到人”的機器人移動貨架系統的貨位分配作為新興研究方向，是目前研究的熱點難題[5]。由于傳統貨位分配基于貨架擺放位置制定商品存儲方案[6～9]，而機器人移動貨架系統的貨架位置不固定，因此傳統貨位分配方法的優勢很難有效發揮[10]。近年，針對機器人移動貨架系統的貨位分配的相關研究剛剛起步，按照商品存儲方式可劃分為兩種模式：一品一位[11～14]（一種商品僅存放一個貨架），一品多位[15～19]（一種商品存放于多個貨架）。

一品一位模式主要基于商品銷量、商品間關聯關系設計貨位分配方法。代表性研究有：Lamballais等[11]以最大化系統吞吐量為目標，提出基于貨架周轉率的商品分區存儲策略。Yuan等[12]考慮商品的周轉率，以最小化貨架移動次數為目標，提出一種基于銷量的貨位分配方式。Kim等[13]以最大化貨架商品間關聯度為目標，建立0-1整數規劃模型，提出了一種構造啟發式聚類算法。Li等[14]將共同購買頻率高的商品存儲在同一個貨架，以最小化貨架移動次數為目標，提出一種基于關聯分析的聚類方法。上述研究基于銷量、商品間關聯關系進行貨位分配，貨架移動次數多，揀選商品數少，揀選效率不高，很難適用于一單多品訂單的揀選。

一品多位模式可以根據商品的購買關聯性進行一品多位的貨位分配，更適用于機器人移動貨架系統，能有效降低訂單揀選時間，提高揀貨效率[15]，正被大型網上超市等企業普遍應用。針對一品多位的貨位分配問題，已有學者提出基于運籌學模型[16]和基于啟發式算法[17]進行求解。代表性研究有：Guan和Li[16]針對商品的多貨架分散存儲需求，以最大化貨架上商品間的關聯度為目標，建立了貨位分配的整數規劃模型，并使用遺傳算法求解該模型。李珍萍等[17]以搬運貨架總時間最短為目標建立了貨位分配的整數非線性規劃模型，分別設計了求解該模型的貪婪算法和單親進化遺傳算法。Xiang等[18]以最大化貨架上商品間的關聯度為目標，建立了貨位分配的混合整數規劃模型，并調用CPLEX求解器進行求解。上述研究為求解這一難題進行了有益的探索，提供了新的定量分析模型和求解算法。但分析發現，機器人移動貨架系統的貨位分配是NP-hard問題，已有研究提出的方法僅可以求解小規模貨位分配問題[17～19]，最多只能求解2000種商品，而實際企業運行的機器人移動貨架系統往往需要考慮上萬種商品的貨位分配問題，導致已有的方法很難有效應用。同時，由于一單多品訂單特點導致海量商品之間關聯關系復雜，使得一品多位的貨位分配問題更是難上加難。

本文針對機器人移動貨架系統的一品多位貨位分配問題，考慮一單多品訂單帶來的商品關聯復雜性以及一品多位帶來的解空間巨大等挑戰性，基于縮減解空間的思想，以提高貨架商品間關聯性為突破口，提出“關聯網絡構建→關聯網絡分析→關聯網絡聚類”的三階段貨位分配方法。該方法通過將商品關聯網絡映射成多個類，每個類對應一個貨架，頻繁與多種商品組合購買的高關聯度商品可被劃分至多個類，可以巧妙化解海量關聯商品的一品多位貨位分配問題。該方法彌補了現有貨位分配聚類方法僅能求解一品一位貨位分配問題的不足，通過引入加權度篩選初始聚類中心，提出一種循環迭代聚類方法，可以對分配節點和剩余關聯網絡進行實時更新，不僅縮小節點的搜索空間，還實現了一品多位的存儲需求、滿足貨架容量約束，解決大規模的一品多位貨位分配問題，具備落地應用的可行性。利用企業的實際數據，驗證本文方法的高效性和實用性，對商品存儲貨架數和貨架容納商品種類進行靈敏度分析。本文方法可為機器人移動貨架系統一品多位貨位分配方案的生成提供科學、實用的決策支持，對企業提升機器人移動貨架系統的運行效率提供切實可行的指導意見。

2 問題描述與分析

2.1 問題描述

機器人移動貨架系統是一種新型智能訂單揀選系統，該系統采用“貨到人”的揀選模式。該系統的揀選流程：AGV將存儲有訂單包含商品的貨架搬運至揀選工作站，揀貨員從貨架揀選目標商品，揀選完成的貨架再由AGV搬運至倉庫的某個空閑存儲位置。

機器人移動貨架系統特別適合大型網上超市中體積小重量輕的小件商品的揀選，在電商倉庫目前常采用的分品類存儲模式下[20，21]，同一個機器人移動貨架系統中通常只存放一個大類且體積較小的商品。由于訂單揀選時，AGV會將整個貨架搬運至揀選站，通過提升貨架上商品間的關聯性可以提高從每個貨架可獲取的目標商品數，從而有效提升揀選效率。機器人移動貨架系統貨位分配問題的決策一般是基于一段較長時間內的訂單數據來分析商品間的關聯性，這主要是由于短時間內的訂單受促銷等因素的影響，某些商品被人為增加了與其他商品購買的頻率，產生噪聲數據，與此同時，若根據一個季度的數據進行貨位分配，可以有效進行季節性調整貨位分配方案以適應顧客購買偏好的季節性變化。因此，基于一段較長時間（例如一個季度）的訂單數據來挖掘穩定的商品購買關聯關系，并將其應用于貨位分配決策是增加貨位分配結果魯棒性、提升系統揀選效率的有效途徑。

貨位分配就是對貨架上存儲的商品種類進行優化，將商品存放在合適的貨架以提升系統的揀選效率。假設倉庫有N種商品，R個可移動貨架，單個貨架最多可存儲M種商品，移動貨架系統的貨位分配需要決策各商品的存儲貨架，即把這N種商品擺放到R個貨架上，且每個貨架存儲的商品種類數不超過M。在一品多位存儲模式下，單種商品可在多個貨架分散存儲。顧客常同時購買多種商品，利用歷史訂單中商品組合購買的關聯關系，可將顧客組合購買頻率高的商品放在同一貨架進行存儲，通過增加貨架上商品間的關聯性，使得移動單個貨架可揀選多種商品，從而減少總移動貨架次數。故問題界定為如何將這N種商品擺放到R個貨架上，使得貨架的商品關聯度總和最大。

基于多個機器人移動貨架倉庫的實地調研和文獻梳理，提出如下假設：

（1）一個貨架可以存儲多種商品，單個貨架可存儲商品種類不超過最大種類數約束。

（2）一種商品可存放于多個貨架。

（3）不考慮商品缺貨的情況。

（4）基于一段較長時間（通常是一個季度）的歷史訂單進行貨位分配決策。

為了便于后文表述，文中使用的變量符號及其代表的意義說明如下：

索引：

i， j表示商品的索引，i，j=1，2，3，…，N;

k表示訂單的索引，k=1，2，3，…，K;

r表示貨架的索引，r=1，2，3，…，R。

參數：

N表示商品種類數量;

K表示客戶訂單數量;

R表示貨架數量;

M表示貨架最大可存儲商品種類數。

2.2 復雜性分析

通過對機器人移動貨架系統貨位分配問題的分析，發現該問題具有NP-hard特性，求解空間隨問題規模增加而爆炸式增長，出現組合爆炸的情況，現證明如下：

定理1 “一品多位”存儲模式下的機器人移動貨架系統貨位分配問題是NP-hard問題。

證明 當商品存儲的貨架數量設置為1時，“一品多位”存儲模式下的機器人移動貨架系統貨位分配問題即變成“一品一位”存儲環境下的機器人移動貨架系統貨位分配問題，該問題已被Mirzaei等[22]證明是NP-hard問題，因此，本文研究的“一品多位”存儲模式下的機器人移動貨架系統貨位分配問題也是NP-hard問題。“一品多位”存儲模式下的機器人移動貨架系統貨位分配問題的可行解比“一品一位”存儲模式的解空間更大，求解更為復雜。對于一品一位和一品多位兩種不同的貨位分配模式，對比解空間大小是反映兩者求解復雜性差異的有效手段。假定商品種類數目為N，單個貨架最多允許存儲M種商品，且N>M>1，不考慮貨架空置，進行復雜性分析。

一品一位貨位分配模式下，其中Z表示貨架數量，Ω指所有可行解的集合，|Ω|表示解空間的元素數量，解空間內元素越多求解最優解的難度也越大。

由于N遠大于M、x，解空間的元素數量主要受N影響，可固定M、x，分析N與解空間規模的關系。令x取最小值2，分析企業數據得知M最小為5，Z、Z′由（1）、（3）式計算得到。當N為6時，一品多位模式下的可行解數量是一品一位模式的15.3倍，而當N增長到23時，該數值已經達到了驚人的3.5×1019倍。更不用說，實際倉庫的可移動貨架數量可達上千、存儲的商品種類在數萬以上，在一品多位存儲模式下，其可行解的數量十分龐大，難以用精確算法求解。因此，本文基于縮減解空間的思想，利用訂單內商品的關聯關系，提出基于商品關聯網絡的貨位分配方法。

3 基于關聯網絡的三階段貨位分配方法

3.1 三階段貨位分配方法的求解原理

機器人移動貨架系統一品多位貨位分配問題面臨兩大難點：（1）問題可行解空間隨商品種類數急劇膨脹。（2）一品多位貨位分配引發的“商品-商品”與“商品-貨架”關聯關系復雜。針對這些難點，本文提出“關聯網絡構建→關聯網絡分析→關聯網絡聚類”的三階段貨位分配方法，該方法基于縮減問題解空間的思想，以提高貨架商品間關聯性為突破口，利用商品關聯網絡構建訂單中商品的關聯關系，通過分析關聯網絡中商品的加權度進一步對關聯網絡進行聚類，由于該方法可以將商品關聯網絡映射成多個類，每個類對應一個貨架，從而巧妙化解海量關聯商品的一品多位貨位分配問題。

三階段貨位分配方法的核心內容如下：

（1）第一階段為商品關聯網絡構建。針對海量多品訂單的商品關聯關系挖掘問題，將商品抽象成網絡的節點，商品間兩兩組合購買的頻次抽象成網絡的邊，這樣構建的商品關聯網絡既能呈現商品間是否存在關聯，又能表示其關聯關系的強弱，從而將百萬級訂單信息壓縮至數萬種商品的關聯，可以有效解決數量龐大、結構多樣、一單多品訂單給商品關聯分析帶來的時間和空間復雜度問題。

（2）第二階段為商品關聯網絡分析。從整體拓撲結構、節點重要性、連邊權重等維度對網絡進行分析，利用網絡呈現的高內聚、低耦合、無標度特性，將貨位分配問題轉化為聚類問題進行求解。同時，從網絡節點加權度的角度，依據網絡特性設計聚類求解方法，可大大縮減貨位分配方案的解空間，有利于快速生成較優的貨位分配方案。

（3）第三階段為關聯網絡聚類。一品多位存儲和貨架容量有限的特點，使得用聚類求解貨位分配時面臨著單個節點出現在多個類、單個類節點總數約束等挑戰。本文提出的關聯網絡聚類通過一種循環迭代聚類方式，可以對分配節點和剩余關聯網絡進行實時更新，不僅可以縮小節點的搜索空間，還可以實現一品多位的存儲需求、滿足貨架容量約束。與此同時，該聚類方法引入加權度[23]篩選初始聚類中心，基于貪婪規則將關聯性最強的節點歸于一類，可以最大化同類節點的關聯性。

3.2 階段一：商品關聯網絡的構建

訂單是挖掘商品關聯性的重要依據，從訂單內部結構來看，同一訂單購買的商品種類、數量具有差異性，訂單與訂單之間由于購買相同的商品也會產生關聯關系。數量龐大、結構多樣、一單多品訂單給商品關聯分析帶來時間和空間的復雜性。訂單內部、訂單間錯綜交叉的結構復雜性，本質是商品之間的關聯關系，將訂單中商品抽象成網絡的節點，商品間兩兩組合購買的頻次抽象成網絡的邊，這樣構建的商品關聯網絡既能呈現商品之間是否存在關聯關系，又能表示其關聯關系的強弱，從而實現百萬級訂單信息壓縮至數萬種商品關聯的轉化，解決關聯分析面臨的時間和空間復雜性難題。商品關聯網絡的計算步驟如下：

表1是一個客戶訂單的示例，以表中訂單為例，介紹商品關聯網絡的構建流程。

圖2是將訂單信息轉換成商品關聯網絡的圖示，訂單涉及的6種商品A到F分別被抽象成節點v1到v6。基于（8）式定義，根據圖2（a）與表1一致的訂單信息得到圖2（b）的訂單-商品關系矩陣P。根據（9）式，由訂單-商品關系矩陣P計算可得商品關聯矩陣S，相對應的商品關聯網絡如圖2（d）所示。

3.3 階段二：商品關聯網絡的分析

機器人移動貨架系統一品多位貨位分配問題面臨可行解空間隨商品種類數急劇膨脹的難點，通過對商品關聯網絡的多維度分析，利用拓撲結構、節點、連邊的分析結果指導貨位分配問題求解，可使得貨位分配結果匹配商品購買規律，大大縮減貨位分配方案的解空間。基于國內某大型網上超市倉庫的商品關聯網絡圖，對網絡結構、節點、連邊的特征進行分析。

（1）拓撲結構分析

如圖1（階段二的子圖）所示，從整體拓撲結構分析，商品關聯網絡具有高內聚、低耦合特征，聚類求解方式非常符合網絡中商品節點聚集成團的特點，因此可以將貨位分配問題轉化成聚類問題進行求解，將節點聚成類，類對應貨架，求解關聯商品的貨位分配問題。

（2）節點、連邊分析

如圖1（階段二的子圖）所示，從節點維度分析，網絡的小部分節點與多個節點有連邊關聯，大部分節點僅連接少數節點，根據連邊數量可知，節點具有差異性。從連邊權重維度分析，權重取值也具有顯著差異，部分連邊權重僅為個位數，少部分連邊的權重高于一千，連邊權重代表商品一起購買的頻次，不適合將不同權重的邊視作同等重要。由節點重要性、連邊權重分析可知，商品關聯網絡具有無標度特性，因此，通過優化關鍵核心商品的決策，可更高效地生成貨位分配方案。

（3）節點加權度分析

結合節點重要性、連邊權重的分析，加權度[23]適合用于度量商品關聯網絡節點的重要性，它是一種兼顧連邊數量和連邊權重差異的節點重要性度量方式，可篩選出頻繁與多種商品一同購買的核心商品。計算步驟如下：

（1）計算布爾矩陣。為了計算各節點的加權度，先根據商品關聯矩陣S計算布爾矩陣B，定義布爾矩陣

以圖2的商品關聯網絡為例，圖3展示了節點加權度的計算過程。第一步根據（10）式由商品關聯矩陣S計算布爾矩陣B，結果如圖3（b）所示。第二步根據（11）式計算各節點的度，結果如圖3（c）所示。第三步計算各節點的加權度，先根據商品關聯矩陣S計算節點的連邊權重和，結果如圖3（d）所示，再根據（12）式計算節點的加權度，結果如圖3（e）所示。計算結果顯示，加權度考慮連邊權重差異，節點劃分更加精確。例如，圖3中節點v1、v2、v3、v4的度相等，但加權度將上述節點細分為三類，分別是加權度最大的v1，其次是v4，最后為v2、v3。

3.4 階段三：基于關聯網絡的聚類算法

聚類將商品關聯網絡映射成多個類，每個類對應一個貨架，一個節點可被聚到多個類，從而可以巧妙化解海量關聯商品的一品多位貨位分配問題，階段二也詳細闡述了聚類方式求解貨位分配問題的有效性。傳統聚類方法形成類的節點數量差異很大[25]，對應到倉庫實際運營中，部分類不滿足貨架容量約束，貨架存儲空間的利用率差異很大，不具備可行性。現有機器人移動貨架系統貨位分配的聚類方法只能將節點聚到一個類，僅適用于一品一位貨位分配問題的求解[13，14]。因此，本文提出基于關聯網絡的聚類算法，通過一種循環迭代聚類方式，可以對分配節點和剩余關聯網絡進行實時更新，不僅可以縮小節點的搜索空間，還可以實現一品多位的存儲需求、滿足貨架容量約束。與此同時，該聚類方法引入加權度篩選初始聚類中心，基于貪婪規則將關聯性最強的節點歸于一類，可以最大化同類節點的關聯性。算法偽代碼如表2所示。

目前文獻中效率最高的機器人移動貨架系統貨位分配聚類算法的時間復雜度為o（N4log N）[13]，本文算法的時間復雜度遠低于已知最優算法，說明本文算法更加高效。

4 實例驗證

實例驗證分為兩部分來度量提出算法的有效性，第一部分通過與不同算法的比較來分析算法計算結果，第二部分是對相應的參數進行靈敏度分析。基于沈陽某網上超市機器人移動貨架系統的倉庫配置，設定商品種類數為10005，單貨架最多存儲29種商品，揀選工作站5個，AGV為15臺。本文構建了與該倉庫對應的Flexsim仿真模型，通過Python 3.6編程實現貨位分配算法，然后輸入仿真模型對揀選效率進行對比。實驗均在Intel Core I5-8265CPU， 1.80GHz， 8 GB RAM的計算機上求解。

4.1 結果分析

使用上述倉庫2019年7月至9月的148015個訂單，274875行購買記錄，按比例劃分訓練集和測試集，訓練集用于對貨位分配方案進行訓練，測試集可對訓練得到的貨位分配方案的優劣進行評估。整個季度的客戶訂單按照下單日期進行排序，日期早的客戶訂單排在前面、日期晚的排在后方，將時間占比80%的前74天的訂單數據作為訓練集，剩下20%的后18天的訂單數據作為測試集。

針對機器人移動貨架系統的貨位分配問題，現有文獻中方法有基于規則的分配方法[12]、啟發式聚類算法[13]、遺傳算法[16]、貪婪算法[17]，其中遺傳算法和貪婪算法的問題求解規模受限，不進行比較，因此，本文主要是和構造啟發式聚類算法、隨機分配方法、按銷量分配方法進行對比，其中構造啟發式聚類算法是目前解決機器人移動貨架系統貨位分配最優的方法，該方法考慮商品的銷量和商品間的購買關聯關系提出了一種啟發式聚類方法，以求解機器人移動貨架系統的貨位分配問題;隨機分配方法作為基準算法，通過將商品隨機放置于貨架上來形成貨位分配方案;按銷量分配方法是當前倉庫實踐常用的方法，通過對商品按銷量進行排序，將具有相同銷量的商品放置于同一貨架上。本文目標是最大化貨架商品關聯度總和，表3比較了各方法的貨架商品關聯度總和，以及仿真模型的運行結果。Imp%表示其他方法相對隨機分配方法提升的百分比。

從表3可知，基于關聯網絡的貨位分配方法顯著提高了各貨架商品間的關聯度，比構造啟發式聚類的結果高43.38%，比隨機分配方法、按銷量分配方法高21901.16%、922.54%，表明設計方法效果較好。本文方法在總搬運貨架數、仿真揀選耗時、AGV行駛距離方面優勢明顯，均取得最小值，在AGV狀態占比部分，本文算法的AGV空駛、空閑狀態占比最低，載重狀態占比最高，表明工作狀態時間占比大，AGV利用率更高。總之，本文設計方法的仿真運行結果最好，其次是構造啟發式聚類算法，再是按銷量分配方法，隨機分配方法的表現最差，各方法的表現結果與貨架商品關聯度總和的結果一致。其中與隨機分配方法相比，本文所提方法能夠降低約33%的總搬運貨架數和36%的AGV行駛距離。相比于目前表現最好的構造啟發式聚類算法而言，本文所提方法依然可減少約10%的總搬運貨架數和12%的AGV行駛距離。仿真結果進一步驗證了本文方法的有效性，結果表明旨在增強各貨架商品間關聯性的貨位分配是提高機器人移動貨架系統揀選效率的有效方式。

4.2 靈敏度分析

4.2.1 商品存儲貨架數的分析

實踐經驗顯示調整小部分商品存儲的貨架數量可大幅提高系統的揀選效率，本節用加權度來篩選這一部分商品，測試商品存儲于不同數量的貨架下揀選效率的變化。根據商品關聯網絡中節點的加權度，采用實踐中常用的二八定律對商品分組，將商品劃分為加權度值高的A類商品和加權度值低的B類商品（A類商品占比20%，B類商品占比80%）。貨位分配采用基于關聯網絡的貨位分配方法，分別修改A、B類商品存儲的貨架數量，圖4展示了該組實驗的結果。數據統計發現該倉庫95%的商品存放的貨架數量不多于5個，故至多允許5個貨架存儲同種商品，需要的貨架數是滿足當前貨架數量配置所需的貨架總數。

從圖4可知，分別為A類、B類商品分配相同的存儲貨架數時，A類商品需投入的貨架資源更少，但可實現更高的貨架商品關聯度總和，隨著分配貨位數的增加，A類商品在提升貨架商品關聯度方面的優勢愈加明顯。在仿真揀選耗時方面，前期B類商品投入1.5倍于A類商品的貨架資源，通過增加貨架成本，短暫取得揀選耗時的優勢，后期即使為B類商品投入2倍以上于A類商品的貨架資源，揀選耗時卻明顯處于劣勢。分析發現，加權度值低的B類商品數量占比大，且不常與多種其他商品一起購買，為B類商品增加貨架數時，貨架商品關聯度的增長慢，但需要面積更大的倉庫和更多的貨架，AGV必須行駛更遠的距離以搬運貨架，反而增加了揀選耗時。

4.2.2 貨架存儲商品種類數的分析

在生產實踐中，企業十分關注單個貨架應存放多少種商品。為了比較貨架存儲商品種類對揀選效率的影響，在不同的貨架最多存儲商品種類數下，采用基于關聯網絡的貨位分配方法生成貨位分配方案，分析了需要的貨架數、貨架商品關聯度總和、仿真揀選耗時的變化，圖5是實驗結果。

由圖5可知，隨著貨架最大存儲商品種類數的增加，需要的貨架數、仿真揀選耗時先快速下降，后緩慢減少，貨架商品關聯度總和也是先快速增長再緩慢增加。上述變化趨勢顯示，隨著貨架存儲商品種類數的增加，揀選效率的增長速率下降，可以為企業根據揀選效率變化規律確定貨架存儲商品種類數提供決策支持。

4.2.3 管理啟示

基于上述分析結果，從企業實踐應用的角度出發，總結兩點管理啟示如下：

（1）根據實踐中常用的二八定律，將加權度排名前20%的商品分散存放在一個以上的貨架上，可以極大地提升系統揀選效率。加權度是度量商品重要性的有效方式，增加高加權度商品存儲的貨架數，揀選效率明顯上升。網上超市在售商品種類多達數百萬，單倉存儲商品種類數萬種，從企業經濟成本和庫存管理出發，不適宜為所有商品都分配多個貨架。因此，企業可依據加權度進行貨架資源分配，優先增加高加權度商品存儲的貨架數，最大幅度提高揀選效率。

（2）將貨架商品關聯度隨貨架存儲商品種類數變化曲線的變化速率趨于穩定的點設置為貨架最大存儲商品種類數，可均衡揀選效率、補貨成本和能源耗用。理論上講，貨架存儲的商品越豐富，移動一個貨架獲得訂單商品的概率越大。但是，貨架存儲商品種類越多，單種商品存放的量越少，導致頻繁補貨的問題，同時，貨架存放過多商品使得AGV托舉貨架耗費的能源也越高，設置合理的貨架存儲商品種類數有利于系統高效地運行。分析揀選效率隨貨架存儲商品種類數變化的變化趨勢發現，增加貨架存儲商品種類數，揀選效率提升效果遞減。因此，企業可參考該規律設置貨架存儲的商品種類數，實現揀選、補貨和能耗的均衡。

5 結論與啟示

針對機器人移動貨架系統的一品多位貨位分配難題，基于縮減解空間的思想，以提高貨架商品間關聯性為突破口，本文提出“關聯網絡構建→關聯網絡分析→關聯網絡聚類”的三階段貨位分配方法，第一階段從訂單中抽取商品關聯關系構建商品關聯網絡，第二階段分析網絡結構后轉化為聚類問題求解，第三階段基于商品的加權度提出基于關聯網絡的聚類算法。研究成果為機器人移動貨架系統貨位分配的優化決策提供了一種新的求解思路，有助于豐富機器人移動貨架系統的貨位分配和啟發式復雜網絡聚類的成果。在實踐上，理論成果為企業貨位分配方案的生成提供借鑒。

本研究主要的貢獻如下：（1）提出三階段貨位分配方法，利用網絡高內聚、低耦合特征應用聚類方式求解，引入加權度提升聚類階段質量，縮減問題的解空間，為貨位分配方案的高效生成提供有效方法。（2）利用控制變量法分析商品存儲貨架數、貨架存儲商品種類數對揀選效率的影響，給出了管理啟示，為企業劃定貨架容納商品種類數、依據加權度的商品存儲貨架數分配提供了決策依據。

參 考 文 獻：

[1] Zhang Y， Huang M， Hu X， et al.. Package consolidation approach to the split-order fulfillment problem of online supermarkets[J]. Journal of the Operational Research Society， 2017， 69（1）： 127-141.

[2] 李英德.波次分區揀貨時裝箱與貨位指派問題協同優化的模型與算法[J].系統工程理論與實踐，2013，33（5）：1269-1276.

[3] Boysen N， Briskorn D， Emde S. Parts-to-picker based order processing in a rack-moving mobile robots environment[J]. European Journal of Operational Research， 2017， 262（2）： 550-562.

[4] Gharehgozli A， Zaerpour N. Robot scheduling for pod retrieval in a robotic mobile fulfillment system[J]. Transportation Research Part E： Logistics and Transportation Review， 2020， 142： 102087.

[5] Azadeh K， De Koster R， Roy D. Robotized and automated warehouse systems： review and recent developments[J]. Transportation Science， 2019， 53（4）： 917-945.

[6] Heskett J L. Cube-per-order index-a key to warehouse stock location[J]. Transportation and Distribution Management， 1963， 3（1）： 27-31.

[7] Hausman W H， Schwarz L B， Graves S C. Optimal storage assignment in automatic warehousing systems[J]. Management Science， 1976， 22（6）： 629-638.

[8] 寧浪，張宏斌，張斌.面向JIT制造的零部件配送中心貨位優化研究[J].管理科學學報，2014，17（11）：10-19.

[9] 田歆，羅春林，汪壽陽，等.零售物流中心運作優化的一種T型補貨策略[J].中國管理科學，2018，26（4）：78-87.

[10] Weidinger F， Boysen N， Briskorn D. Storage assignment with rack-moving mobile robots in KIVA warehouses[J]. Transportation Science， 2018， 52（6）： 1479-1495.

[11] Lamballais T， Roy D， De Koster M B M. Estimating performance in a robotic mobile fulfillment system[J]. European Journal of Operational Research， 2017， 256（3）： 976-990.

[12] Yuan R， Graves S C， Cezik T. Velocity-based storage assignment in semi-automated storage systems[J]. Production and Operations Management， 2019， 28（2）： 354-373.

[13] Kim H J， Pais C， Shen Z J M. Item assignment problem in a robotic mobile fulfillment system[J]. IEEE Transactions on Automation Science and Engineering， 2020， 17（4）： 1854-1867.

[14] Li X， Hua G， Huang A， et al.. Storage assignment policy with awareness of energy consumption in the kiva mobile fulfilment system[J]. Transportation Research Part E： Logistics and Transportation Review， 2020， 144： 102158.

[15] Lamballais T， Roy D， De Koster R B M. Inventory allocation in robotic mobile fulfillment systems[J]. IISE Transactions， 2020， 52（1）： 1-17.

[16] Guan M， Li Z. Genetic Algorithm for scattered storage assignment in kiva mobile fulfillment system[J]. American Journal of Operations Research， 2018， 8（6）： 474-485.

[17] 李珍萍，范欣然，吳凌云.基于“貨到人”揀選模式的儲位分配問題研究[J].運籌與管理，2020，29（2）：1-11.

[18] Xiang X， Liu C， Miao L. Storage assignment and order batching problem in kiva mobile fulfilment system[J]. Engineering Optimization， 2018， 50（11）： 1941-1962.

[19] Chen L， Langevin A， Riopel D. The storage location assignment and interleaving problem in an automated storage/retrieval system with shared storage[J]. International Journal of Production Research， 2010， 48（4）： 991-1011.

[20] Zhang Y， Lin W H， Huang M， et al.. Multi-warehouse package consolidation for split orders in online retailing[J]. European Journal of Operational Research， 2021， 289（3）： 1040-1055.

[21] Zhu S， Hu X， Huang K， et al.. Optimization of product category allocation in multiple warehouses to minimize splitting of online supermarket customer orders[J]. European Journal of Operational Research， 2021， 290（2）： 556-571.

[22] Mirzaei M， Zaerpour N， de Koster R. The impact of integrated cluster-based storage allocation on parts-to-picker warehouse performance[J]. Transportation Research Part E： Logistics and Transportation Review， 2021， 146： 102207.

[23] Garas A， Schweitzer F， Havlin S. A k-shell decomposition method for weighted networks[J]. New Journal of Physics， 2012， 14（8）： 083030.

[24] Ding Z， Chen X， Dong Y， et al.. Consensus reaching in social network DeGroot model： the roles of the Self-confidence and node degree[J]. Information Sciences， 2019， 486： 62-72.

[25] Mangiameli P， Chen S K， West D. A comparison of SOM neural network and hierarchical clustering methods[J]. European Journal of Operational Research， 1996， 93（2）： 402-417.

[26] Kolen J F， Hutcheson T. Reducing the time complexity of the fuzzy c-means algorithm[J]. IEEE Transactions on Fuzzy Systems， 2002， 10（2）： 263-267.

3413500338239