基于“貨到人”揀選系統的動態貨位分配研究

張雪，周麗，路雪鵬，尚嬌

基于“貨到人”揀選系統的動態貨位分配研究

張雪，周麗，路雪鵬，尚嬌

（北京物資學院 信息學院，北京 101149）

為了提高“貨到人”揀選系統的訂單揀選效率，研究了電商倉庫貨位初始存儲狀態為非空情況下的商品貨位分配問題。考慮貨架上現存商品信息、倉庫空余貨位數、待補貨商品和新收入商品信息，提出基于商品關聯度的分散存儲策略，以極大化貨架上所有存儲商品的關聯度之和為目標構建商品上架與下架的動態貨位分配數學模型，并設計貪婪算法，再采用改進粒子群算法對貪婪算法得到的結果進行優化。基于商品關聯度的分散存儲策略可以減少貨架平均搬運次數29.32%左右。與隨機分配策略相比，文中提出的貨位分配策略能夠有效提升整個電商倉儲中心的揀選速度。

貨到人；貨位分配；整數規劃模型；貪婪算法；粒子群算法

在我國互聯網技術不斷發展，各大電商平臺支付安全系統不斷升級的背景下，電子商務得以迅速發展，并且由傳統的“人到貨”訂單揀選模式逐漸向基于自動引導車（Automated Guided Vehicle, AGV）的“貨到人”訂單揀選模式轉變。具有成本效益的AGV物流搬運方案實現了“貨到人”的分揀，為電商倉儲帶來了革命性變革。與“人到貨”揀選系統類似，“貨到人”揀選系統也存在一些亟須解決的問題，包括貨位分配優化、訂單處理[1-2]、AGV小車任務分配及調度[3-4]、路徑規劃[5-6]等問題。在提高倉儲配送中心揀選效率的方法中，科學的貨位分配方法是提高揀選效率的基礎，也是一種戰略上的決策，比訂單分批、優化揀選路徑等方法減少了AGV搬運貨架的次數和距離。

貨位分配是指企業依據商品的特征、需求以及其他相關變動因素，對商品存儲的位置進行動態的調整[7]。“人到貨”揀選系統有關貨位分配問題的研究成果已經相當成熟，主要是通過貨位存儲策略[8-10]、商品關聯關系分析[11-12]和商品聚類分析[13-14]等3個方面進行優化。“人到貨”揀選系統中貨架不可移動，對訂單揀選效率影響最大的是揀選工作人員，而“貨到人”揀選系統中，貨架具有可移動性，主要是利用AGV小車搬運貨架，因此“人到貨”揀選系統的相關研究成果不能直接應用于“貨到人”揀選系統。

在“貨到人”揀選系統的商品貨位分配問題中，通常需要計算商品之間的關聯度，并以此作為依據，將關聯度高的商品存儲在同一個貨架上。袁瑞萍等[15]建立了極大化每個貨架上商品之間的關聯度平均值的數學模型，并通過仿真進行求解。Kim等[16]考慮一種商品可以放在多個貨架上的情況，設計了一種優化啟發式算法求解基于商品關聯度的貨位分配問題。包菊芳等[17]采用FP–Growth算法計算商品之間的關聯度，并將相關度高的商品存儲在同一個貨架上，與隨機貨位分配策略相比，能夠有效減少貨架搬運次數。Mirzaei等[18]基于歷史訂單中的商品周轉率和關聯性，采用集成集群分配策略，并設計啟發式算法進行求解。也有的學者從其他角度出發對商品存儲位置進行優化。Onal等[19]基于爆炸存儲的商品貨位分配策略，構建了商品貨位分配的排隊論模型。Lamballais等[20]構建了單行和多行訂單的排隊網絡模型，評估不同存儲策略下的訂單最大吞吐量、平均揀選周期和機器人利用率3種指標。

學者們在研究“貨到人”揀選系統的商品貨位分配時，大部分考慮的是貨架的初始狀態是空的，即集中于研究靜態的商品貨位分配問題，但實際上電商倉儲中心貨架上是存放商品的，需要定期的對商品進行補貨或者下架某些滯銷商品，這是一個動態的貨位分配問題，并且一種商品應該存放在多個貨架上，而關于這些方面的研究較少，因此需要對一品多位的動態貨位分配問題進行展開研究。

1 問題描述

如圖1所示，“貨到人”揀選系統按倉庫區域的功能可分為商品補貨區、貨架存儲區、商品揀貨區、AGV充電區和AGV等待區。在接到訂單揀選指令后，由AGV小車和工作人員合作完成訂單的揀選工作。

在“貨到人”揀選系統中研究商品的貨位分配問題時，需要優先考慮將具有關聯性的商品存儲在同一個貨架上，以此減少AGV小車搬運貨架的次數。此外，在倉庫總貨位數一定，貨架上目前存儲的商品信息已知情況下，需要考慮倉庫經過一個訂單揀選周期后，貨架上的部分商品會出現缺貨狀態，以及可能會有新收入的商品需要存儲在貨架上的情況，因此需要對貨架上缺貨的商品及新收入的商品進行補貨和上架操作。

根據電商訂單呈小批量多批次的特點，提出了基于商品關聯度的分散存儲策略，即首先采用商品分散存儲策略，即同一種商品可以存儲在多個貨架上，但不能存儲在同一個貨架上的策略，使同一個貨架上存儲的商品種類達到最多，從而增加商品不同揀選的可能性。其次，通過極大化同一貨架上商品間的關聯度之和，獲取商品在貨架上的最佳存儲位置，達到有效減少貨架搬運次數，提高訂單揀選效率的目的。

整體的貨位分配操作示例見圖2。貨架的初始存儲狀態已知，數字1—9代表的是商品種類編號，數字0代表的是空貨位，其中，商品4、商品8和商品9是待補貨商品，根據待揀選訂單信息，先將商品7進行下架操作，空出額外需要的貨位數，再經過關聯度計算，分別將商品4、商品8和商品9分配在對應的貨架上。

圖2 商品貨位分配過程

2 數學模型構建

2.1 模型假設

在構建商品動態貨位分配數學模型過程中遵循以下基本假設條件。

1）在揀選過程中每個訂單單獨揀選。

2）在商品動態貨位分配之前，下一階段的揀選訂單商品信息已知。

3）每個訂單中包含一種或多種不同的商品。

4）不考慮商品的體積以及大小，即一個貨位可以容納任意一種商品。

5）每種商品可以存儲在多個貨架上。

6）一個貨位只能分配一種商品。

7）不考慮貨架上現存商品的下架成本。

8）每個訂單中商品只訂購一件，每個貨位上存儲的商品數量充足。

2.2 符號說明

2.2.1 名詞解釋

貨架上現存商品表示目前存儲在貨架上的原有商品集合，倉庫原有待補貨商品表示有補貨需求的原有商品集合，新收入待上架商品表示歷史訂單商品集合中沒有的商品種類。

2.2.2 參數符號說明

2.2.3 變量符號說明

2.3 模型構建

2.3.1 各商品之間的關聯度計算

1）倉庫原有待補貨商品之間的關聯度為：

2）新收入待上架商品與新收入待上架商品之間的關聯度為：

3）倉庫原有待補貨商品與新收入待上架商品之間的關聯度為：

4）倉庫原有待補貨商品與貨架上現存商品之間的關聯度為：

5）新收入待上架商品與貨架上現存商品之間的關聯度為：

2.3.2 構建模型

在以上假設條件和參數下，建立商品動態貨位分配模型。

目標函數：

約束條件：

上述模型中，目標函數表示極大化貨架上所有存放商品的關聯度之和；約束條件（1）表示一個貨架上存放的待補貨商品和新收入待上架商品的種類數之和不超過這個貨架上的空余貨位數；約束條件（2）表示一個貨架上待補貨商品和新收入待上架商品的實際分配貨位數之和不超過這個貨架上的空余貨位數；約束條件（3）表示待補貨商品和新收入待上架商品在所有貨架上的實際分配貨位個數之和等于待補貨商品和新收入待上架需要的貨位分配個數之和；約束條件（4）表示當待補貨商品被分配到一個貨架上時，該貨架要給該商品分配貨位；約束條件（5）表示當新收入待上架商品被分配到一個貨架上時，該貨架要給該商品分配貨位；約束條件（6）表示貨架上現存商品中需要下架的總貨位數不少于待補貨商品與新收入待上架商品實際分配的貨位數之和減去倉庫的總空余貨位數；約束條件（7）表示減去下架商品貨位數后的貨架上現存商品的貨位數與待補貨商品和新收入待上架商品的實際分配貨位數之和等于倉庫的總貨位數；約束條件（8）和約束條件（9）為變量取值約束。

在“貨到人”揀選系統中，AGV小車在接收任務后，通過舉升、導航和行駛等系統，以直線運動（東南西北4個方向）或原地旋轉運動的方式將目標貨架搬運至揀選臺或補貨臺。整個AGV小車揀選操作均由訂單信息控制系統進行指令下達，并確認貨架存儲區里目前所存儲待揀選訂單里所需商品的數量以及存儲的貨位，因此需要在訂單信息控制系統中設計一個統計與安排商品貨位的算法，使AGV小車能夠快速地完成貨架搬運任務。

3 求解算法設計

3.1 貪婪算法

文中建立的商品動態貨位分配模型是一個非線性混合整數規劃模型，當待揀選訂單和商品種類數量較多時，在短時間內很難直接獲得模型的精確最優解，因此，需要針對文中提出的貨位分配問題和模型特點，設計能夠快速求解該模型的啟發式算法。文中設計的啟發式算法如下所述。

第1階段主要采用貪婪算法得到初始的商品貨位分配結果。

輸入：歷史訂單數據，倉庫內待補貨商品的種類數及對應的貨位數，新收入待上架商品的種類數及對應的貨位數，貨架上現存商品初始的貨位存儲狀態。

1）統計所有貨架上現存商品的種類及其所占的貨位數，歷史訂單數據中包含的貨架上現存商品的種類信息，將訂單中不包含的貨架上現存商品種類視為滯銷商品，下架對應貨位數。

2）找出全部有空位的貨架，將每個貨架上現存商品視為一個集合，根據歷史訂單信息和關聯性計算公式，求解所有待補貨商品與每個貨架上現存商品集合的關聯度之和，所有新收入待上架商品與每個貨架上現存商品集合的關聯度之和，并將所有的關聯度和進行降序排列。

3）從降序排列中找到與貨架上現存商品集合關聯度和最大的商品，判斷該貨架上是否只有一個空貨位，如果只有一個空貨位，則進入步驟4，否則進入步驟5。

4）判斷該商品是否只需要分配一個貨位，如果只需要分配一個貨位，則將該商品分配在對應的貨架上，更新待分配的商品集合；如果需要分配2個及以上的貨位，則先存放1個貨位在對應貨架上，并將該商品視作貨架上現存商品，更新待分配的商品集合和貨架上現存商品集合，進入步驟2。

5）如果該貨架上有2個及以上的貨位，判斷該貨架上是否有商品存儲，如果有商品存儲，找到與貨架上現存商品集合關聯度和最大的商品存放在該貨架上，進入步驟4，否則進入步驟6。

6）如果該貨架上5層貨位均為空，計算所有剩余未被分配的倉庫原有待補貨商品和新收入商品之間的關聯度值，將關聯度高的5種商品分配在該貨架上，更新待分配的商品集合和貨架上現存商品集合，判斷倉庫內所有待上架商品是否全部分配完成，如果全部完成，則結束計算，否則進入步驟2。

輸出：商品補貨以及新收入商品上架后的貨架上存放的商品信息。

3.2 粒子群算法

第2階段主要是采用粒子群算法對第1階段貪婪算法得到的貨位分配結果進行優化。該算法不需要像其他優化算法那樣，例如遺傳算法，需要對個體進行選擇操作、交叉操作和變異操作等，因此減少了復雜的遺傳操作。

粒子根據以式（10）來更新自身的速度和位置。

為了使粒子在不同的進化階段擁有不同的搜索能力，文中引入了動態慣性權重。為設定一個變化區間，即在算法開始時，賦予慣性權重一個較大的正值，在算法結束時，賦予慣性權重一個較小的正值。

動態慣性權重值目前采用最多的是線性遞減慣性權重：

式（14）是一種經驗做法，文中在后期對模型進行求解時首先與其他2種慣性群眾選擇方法進行對比，從而選擇最優的慣性權重：

該階段算法的具體步驟如下。

輸入：第1階段貪婪算法得到的初始貨位分配結果，即每個貨架上存放的具體商品信息。

1）根據第1階段的貨位分配結果初始化粒子群，設定種群規模、最大迭代次數、每個粒子的速度和位置等。

2）計算每個粒子的適應度值。

5）計算動態慣性權重值，更新迭代每個粒子的位置和速度。

6）判斷是否完成迭代次數，如果完成則結束計算，輸出最優的可行解，否則返回步驟2繼續計算。

輸出：優化后的商品貨位分配結果。

文中商品動態貨位分配算法總流程見圖3。

圖3 商品動態貨位分配算法總流程

4 模擬計算與分析

4.1 算例描述

某個電商倉庫中包含30個貨架，每個貨架分成5層，共存儲55種商品，在倉庫運行一段時間后，倉庫某些貨位為空狀態，即貨位上沒有商品存儲。現倉庫接到300個訂單需要揀選，每個訂單里包含的商品種類不超過10種，待揀選訂單見表1，其中包括10種（商品編號為56—65）之前進行預售的商品。根據待揀選訂單，發現倉庫現有存儲的55種商品中有商品需要進行補貨，以及新收入的商品需要存儲到貨架上，待補貨商品和新收入的商品的種類和所需要的貨位數見表2。目前倉庫的空余貨位不足以存儲全部的待補貨商品和新收入商品，在考慮每個訂單單獨揀選的情況下，需要將全部待補貨商品和新收入商品分配在貨架上，并且要達到訂單總揀選效率最高。

表1 300個待揀選訂單信息

Tab.1 Information of 300 orders to be picked

表2 待補貨商品及新收入商品所需貨位數

Tab.2 Number of allocations for goods to be replenished and new incoming goods

4.2 結果分析

根據前文的描述以及文中設計的貨位分配策略和算法，在Intel(R) Core(TM) i3–4160 CPU @ 3.60 GHz 3.60 GHz處理器，Matlab R2019(a)編程環境下得到貨位法分配結果。其中，對式（14）、式（15）、式（16）不同的慣性權重選擇進行了研究，最終選擇式（15）作為文中的慣性權重計算公式。

首先根據歷史訂單計算55種倉庫現有商品之間的關聯度，同時根據待揀選訂單計算所有商品之間的關聯度，并將此關聯度矩陣累計加入到歷史訂單關聯度矩陣中，最終的商品關聯度計算結果見表3。

經過算法的不斷迭代與更新，得到各分配策略的貨位分配結果。貪婪算法經過0.219 s得到的初始貨位分配結果見表4。粒子群算法對初始貨位分配結果進行優化后得到的貨位分配結果見表5，其算法收斂曲線見圖4。將全部待補貨商品和新收入商品隨機的分配在貨架上，得到的貨位分配結果見表6。

表3 商品關聯度計算結果

Tab.3 Goods relevance calculation result

表4 貪婪算法得到的初始貨位分配結果

Tab.4 Initial goods allocation obtained by the greedy algorithm

注：（）里表示的是貨架的初始存儲狀態，包含下架的商品種類。

表5 粒子群算法優化后得到的貨位分配結果

Tab.5 Goods allocation obtained after optimization by particle swarm algorithm

注：（）里表示的是貨架的初始存儲狀態，包含下架的商品種類。

圖4 粒子群算法收斂曲線

在完成同一批300個訂單揀選時，文中提出的基于商品關聯度的分散存儲策略和隨機存儲策略的結果對比見表7。基于商品關聯度的分散存儲策略需要搬運貨架1 166次，隨機分配策略需要搬運貨架1 651次，將2種貨位分配策略進行對比，文中的貨位分配策略可有效地將貨架的搬運次數降低29.38%。同時，文中貨位分配策略得到的所有貨架上商品的關聯度之和比隨機分配策略得到的所有貨架上商品的關聯度之和提高了37.94%。

為了證明文中提出的算法在求解貨位分配模型結果時的穩定性，在訂單數為300和每個貨架的貨位數固定（5）的情況下，設計不同數量的補貨商品總數、新收入商品總數和不同規模的貨架數。文中策略與隨機分配策略的貨架搬運次數進行了對比，對比結果見表8。

表6 隨機分配得到的貨位分配結果

Tab.6 Goods allocation obtained by random distribution

注：（）里表示的是貨架的初始存儲狀態，包含下架的商品種類。

表7 2種貨位分配策略結果對比

Tab.7 Comparison of 2 goods allocation strategies

表8 不同規模搬運貨架次數結果對比

Tab.8 Comparison of handling number of shelves of different scales

由表8可知，與隨機分配策略相比，文中提出的基于商品關聯度的分散存儲策略的貨架搬運次數平均降低了29.32%，由此證明了文中提出的分配策略及算法具有穩定性和可行性。

5 結語

近年來，隨著電商的快速發展，電商企業為了提高訂單的揀選作業和配送作業效率，已經開始逐漸采用“貨到人”揀選系統。文中對所有商品之間的關聯度進行計算，根據一種商品可以存儲在多個貨架上、倉庫內原有待補貨商品所需要的貨位數、新收入待上架商品所需要的貨位數等約束條件構建數學模型，設計貪婪算法和粒子群算法進行求解，并通過仿真進行算例驗證，結果表明，文中提出的貨位分配策略可以明顯減少貨架平均搬運次數。

在研究“貨到人”揀選系統貨位分配問題時，文中以滯銷商品下架的貨位總數超過待補貨商品和新收入商品所需額外貨位數之和為約束條件，即存在某些商品種類不在待揀選訂單中的情況，但從實際角度出發，可能會存在待揀選訂單中包含全部商品的情況，同時，文中沒有考慮倉庫滯銷商品的下架成本，因此，在下一步的研究中將著重考慮這2種情況。

[1] YANG X, HUA G, HU L, et al. Joint Optimization of Order Sequencing and Rack Scheduling in the Robotic Mobile Fulfilment System[J]. Computers & Operations Research, 2021, 135: 105467.

[2] BOYSEN N, BRISKORN D, EMDE S. Parts-to-Picker Based 0rder Processing In a Rack-Moving Mobile Robots Environment[J]. European Journal of Operational Research, 2017, 262(2): 550-562.

[3] ROY D, NIGAM S, DE KOSTER R, et al. Robot-Storage Zone Assignment Strategies in Mobile Fulfillment Systems[J]. Transportation Research Part E Logistics and Transportation Review, 2019, 122: 119-142.

[4] SHARMA K, DORIYA R. Coordination of Multi-Robot Path Planning for Warehouse Application Using Smart Approach for Identifying Destinations[J].Intelligent Service Robotics, 2021, 14(2): 313-325.

[5] PAIKRAY H K, DAS P K, PANDA S. Optimal Multi-Robot Path Planning Using Particle Swarm Optimization Algorithm Improved by Sine and Cosine Algorithms[J]. Arabian Journal for Science and Engineering, 2021, 46(4): 3357-3381.

[6] 雷斌, 王菀瑩, 趙佳欣. 貨位分配優化研究綜述[J]. 計算機工程與應用, 2021, 57(1): 48-55.

LEI Bin, WANG Wan-ying, ZHAO Jia-xin. Review of Research on Location Allocation Optimization[J]. Computer Engineering and Applications, 2021, 57(1): 48-55.

[7] BORTOLINI M, FACCIO M, FERRARI E, et al. Design of Diagonal Cross-Aisle Warehouses with Class-Based Storage Assignment Strategy[J]. The International Journal of Advanced Manufacturing Technology, 2019, 100(9): 2521-2536.

[8] ZHOU Li, SUN Li-li, LI Zhao-chan, et al. Study on a Storage Location Strategy Based on Clustering and Association Algorithms[J]. Soft Computing, 2020, 24(8): 5499-5516.

[9] 李陽, 唐磊, 胡俊. 基于遺傳算法的航天零件倉庫貨位優化研究[J]. 制造業自動化, 2020, 42(8): 68-73.

LI Yang, TANG Lei, HU Jun. The Research on Space Parts Warehouse Location Optimization Based on Genetic Slgorithms[J]. Manufacturing Automation, 2020, 42(8): 68-73.

[10] PANG K W, CHAN H L. Data Mining-Based Algorithm for Storage Location Assignment in a Randomised Warehouse[J]. International Journal of Production Research, 2017, 55(14): 4035-4052.

[11] LEE C. A GA-Based Optimisation Model for Big Data Analytics Supporting Anticipatory Shipping in Retail 4.0[J]. International Journal of Production Research, 2016, 55(2): 593-605.

[12] 周亞云, 項前, 余崇貴, 等. 考慮物料需求關聯與周轉率的倉儲貨位優化方法[J]. 東華大學學報(自然科學版), 2020, 46(3): 414-420.

ZHOU Ya-yun, XIANG Qian, YU Chong-gui, et al. A Method for Storage Location Optimization Considering Material Demand Correlations and Turnover[J]. Journal of Donghua University (Natural Science), 2020, 46(3): 414-420.

[13] HOLY V, SOKOL O, ?ERNY M. Clustering Retail Products Based on Customer Behaviour[J]. Applied Soft Computing Journal, 2017, 60: 752-762.

[14] NIU J. Intelligent Evaluation Model of E-Commerce Transaction Volume Based on the Combination of K-Means and SOM Algorithms[J]. International Journal of Information and Communication Technology, 2021, 18(2): 189.

[15] 袁瑞萍, 王慧玲, 李俊韜, 等. 基于移動機器人的訂單揀選系統貨位優化模型和算法研究[J]. 系統科學與數學, 2020, 40(6): 1050-1060.

YUAN Rui-ping, WANG Hui-ling, LI Jun-tao, et al. The Slotting Optimization Model and Algorithm in Robotic Mobile Fulfillment Systems[J]. Journal of Systems Science and Mathematical Sciences, 2020, 40(6): 1050-1060.

[16] 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.

[17] 包菊芳, 王麗. 基于SKU關聯度的儲位優化問題研究[J]. 數學的實踐與認識, 2021, 51(14): 31-40.

[18] BAO Ju-fang, WANG Li. Research on Optimization of Storage Location Based on SKU Correlation[J]. Mathematics in Practice and Theory, 2021, 51(14): 31-40.

[19] MASOUD M, NIMA Z, RENé D K. The Impact of Integrated Cluster-Based Storage Allocation on Parts-to-Picker Warehouse Performance[J]. Transportation Research Part E, 2021, 146: 102207.

[20] ONAL S, ZHANG Jing-ran, DAS S. Modelling and Performance Evaluation of Explosive Storage Policies in Internet Fulfilment Warehouses[J]. International Journal of Production Research, 2017, 55(20): 5902-5915.

[21] LAMBALLAIS T, ROY D, DE KOSTER M. Estimating Performance in a Robotic Mobile Fulfillment System[J]. European Journal of Operational Research, 2017, 256(3): 976-990.

Dynamic Allocation Based on “Goods-to-person” Picking System

ZHANG Xue, ZHOU Li, LU Xue-peng, SHANG Jiao

(School of Information, Beijing Wuzi University, Beijing 101149, China)

The work aims to study the goods allocation when the initial storage status of the e-commerce warehouse is not empty, so as to improve the order picking efficiency of the “goods-to-person” picking system. Considering the information of the existing goods on the shelf, the number of vacant goods allocation in the warehouse, the goods to be replenished and the information of the new incoming goods, a decentralized storage strategy based on the degree of goods relevance was proposed to maximize the sum of the relevance of all stored goods on the shelf, thus constructing the mathematical model of dynamic allocation of goods on and off the shelves. Then, a greedy algorithm was designed, and the particle swarm algorithm was improved to optimize the results obtained by the greedy algorithm. The decentralized storage strategy based on the degree of goods relevance could reduce the average number of shelf handling by about 29.32%. Compared with the random allocation strategy, the proposed allocation strategy can effectively improve the picking speed of the entire e-commerce storage center.

“goods-to-person”; goods allocation; integer programming model; greedy algorithm; particle swarm algorithm

F274

A

1001-3563(2022)15-0247-11

10.19554/j.cnki.1001-3563.2022.15.029

2021–11–26

國家自然科學基金（71501015）；北京社科基金重點項目（18GLA009）；北京市長城學者項目（CIT&TCD20170317）

張雪（1994—），女，北京物資學院碩士生，主攻智能物流系統。

周麗（1978—），女，博士，北京物資學院教授，主要研究方向為智能物流系統。

責任編輯：曾鈺嬋