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

基于“貨到人”揀選系統(tǒng)的動(dòng)態(tài)貨位分配研究

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

（北京物資學(xué)院 信息學(xué)院，北京 101149）

為了提高“貨到人”揀選系統(tǒng)的訂單揀選效率，研究了電商倉(cāng)庫(kù)貨位初始存儲(chǔ)狀態(tài)為非空情況下的商品貨位分配問(wèn)題?？紤]貨架上現(xiàn)存商品信息、倉(cāng)庫(kù)空余貨位數(shù)、待補(bǔ)貨商品和新收入商品信息，提出基于商品關(guān)聯(lián)度的分散存儲(chǔ)策略，以極大化貨架上所有存儲(chǔ)商品的關(guān)聯(lián)度之和為目標(biāo)構(gòu)建商品上架與下架的動(dòng)態(tài)貨位分配數(shù)學(xué)模型，并設(shè)計(jì)貪婪算法，再采用改進(jìn)粒子群算法對(duì)貪婪算法得到的結(jié)果進(jìn)行優(yōu)化?；谏唐逢P(guān)聯(lián)度的分散存儲(chǔ)策略可以減少貨架平均搬運(yùn)次數(shù)29.32%左右。與隨機(jī)分配策略相比，文中提出的貨位分配策略能夠有效提升整個(gè)電商倉(cāng)儲(chǔ)中心的揀選速度。

貨到人；貨位分配；整數(shù)規(guī)劃模型；貪婪算法；粒子群算法

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

貨位分配是指企業(yè)依據(jù)商品的特征、需求以及其他相關(guān)變動(dòng)因素，對(duì)商品存儲(chǔ)的位置進(jìn)行動(dòng)態(tài)的調(diào)整[7]?！叭说截洝睊x系統(tǒng)有關(guān)貨位分配問(wèn)題的研究成果已經(jīng)相當(dāng)成熟，主要是通過(guò)貨位存儲(chǔ)策略[8-10]、商品關(guān)聯(lián)關(guān)系分析[11-12]和商品聚類分析[13-14]等3個(gè)方面進(jìn)行優(yōu)化?！叭说截洝睊x系統(tǒng)中貨架不可移動(dòng)，對(duì)訂單揀選效率影響最大的是揀選工作人員，而“貨到人”揀選系統(tǒng)中，貨架具有可移動(dòng)性，主要是利用AGV小車搬運(yùn)貨架，因此“人到貨”揀選系統(tǒng)的相關(guān)研究成果不能直接應(yīng)用于“貨到人”揀選系統(tǒng)。

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

學(xué)者們?cè)谘芯俊柏浀饺恕睊x系統(tǒng)的商品貨位分配時(shí)，大部分考慮的是貨架的初始狀態(tài)是空的，即集中于研究靜態(tài)的商品貨位分配問(wèn)題，但實(shí)際上電商倉(cāng)儲(chǔ)中心貨架上是存放商品的，需要定期的對(duì)商品進(jìn)行補(bǔ)貨或者下架某些滯銷商品，這是一個(gè)動(dòng)態(tài)的貨位分配問(wèn)題，并且一種商品應(yīng)該存放在多個(gè)貨架上，而關(guān)于這些方面的研究較少，因此需要對(duì)一品多位的動(dòng)態(tài)貨位分配問(wèn)題進(jìn)行展開(kāi)研究。

1 問(wèn)題描述

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

在“貨到人”揀選系統(tǒng)中研究商品的貨位分配問(wèn)題時(shí)，需要優(yōu)先考慮將具有關(guān)聯(lián)性的商品存儲(chǔ)在同一個(gè)貨架上，以此減少AGV小車搬運(yùn)貨架的次數(shù)。此外，在倉(cāng)庫(kù)總貨位數(shù)一定，貨架上目前存儲(chǔ)的商品信息已知情況下，需要考慮倉(cāng)庫(kù)經(jīng)過(guò)一個(gè)訂單揀選周期后，貨架上的部分商品會(huì)出現(xiàn)缺貨狀態(tài)，以及可能會(huì)有新收入的商品需要存儲(chǔ)在貨架上的情況，因此需要對(duì)貨架上缺貨的商品及新收入的商品進(jìn)行補(bǔ)貨和上架操作。

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

整體的貨位分配操作示例見(jiàn)圖2。貨架的初始存儲(chǔ)狀態(tài)已知，數(shù)字1—9代表的是商品種類編號(hào)，數(shù)字0代表的是空貨位，其中，商品4、商品8和商品9是待補(bǔ)貨商品，根據(jù)待揀選訂單信息，先將商品7進(jìn)行下架操作，空出額外需要的貨位數(shù)，再經(jīng)過(guò)關(guān)聯(lián)度計(jì)算，分別將商品4、商品8和商品9分配在對(duì)應(yīng)的貨架上。

圖2 商品貨位分配過(guò)程

2 數(shù)學(xué)模型構(gòu)建

2.1 模型假設(shè)

在構(gòu)建商品動(dòng)態(tài)貨位分配數(shù)學(xué)模型過(guò)程中遵循以下基本假設(shè)條件。

1）在揀選過(guò)程中每個(gè)訂單單獨(dú)揀選。

2）在商品動(dòng)態(tài)貨位分配之前，下一階段的揀選訂單商品信息已知。

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

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

5）每種商品可以存儲(chǔ)在多個(gè)貨架上。

6）一個(gè)貨位只能分配一種商品。

7）不考慮貨架上現(xiàn)存商品的下架成本。

8）每個(gè)訂單中商品只訂購(gòu)一件，每個(gè)貨位上存儲(chǔ)的商品數(shù)量充足。

2.2 符號(hào)說(shuō)明

2.2.1 名詞解釋

貨架上現(xiàn)存商品表示目前存儲(chǔ)在貨架上的原有商品集合，倉(cāng)庫(kù)原有待補(bǔ)貨商品表示有補(bǔ)貨需求的原有商品集合，新收入待上架商品表示歷史訂單商品集合中沒(méi)有的商品種類。

2.2.2 參數(shù)符號(hào)說(shuō)明

2.2.3 變量符號(hào)說(shuō)明

2.3 模型構(gòu)建

2.3.1 各商品之間的關(guān)聯(lián)度計(jì)算

1）倉(cāng)庫(kù)原有待補(bǔ)貨商品之間的關(guān)聯(lián)度為：

2）新收入待上架商品與新收入待上架商品之間的關(guān)聯(lián)度為：

3）倉(cāng)庫(kù)原有待補(bǔ)貨商品與新收入待上架商品之間的關(guān)聯(lián)度為：

4）倉(cāng)庫(kù)原有待補(bǔ)貨商品與貨架上現(xiàn)存商品之間的關(guān)聯(lián)度為：

5）新收入待上架商品與貨架上現(xiàn)存商品之間的關(guān)聯(lián)度為：

2.3.2 構(gòu)建模型

在以上假設(shè)條件和參數(shù)下，建立商品動(dòng)態(tài)貨位分配模型。

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

約束條件：

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

在“貨到人”揀選系統(tǒng)中，AGV小車在接收任務(wù)后，通過(guò)舉升、導(dǎo)航和行駛等系統(tǒng)，以直線運(yùn)動(dòng)（東南西北4個(gè)方向）或原地旋轉(zhuǎn)運(yùn)動(dòng)的方式將目標(biāo)貨架搬運(yùn)至揀選臺(tái)或補(bǔ)貨臺(tái)。整個(gè)AGV小車揀選操作均由訂單信息控制系統(tǒng)進(jìn)行指令下達(dá)，并確認(rèn)貨架存儲(chǔ)區(qū)里目前所存儲(chǔ)待揀選訂單里所需商品的數(shù)量以及存儲(chǔ)的貨位，因此需要在訂單信息控制系統(tǒng)中設(shè)計(jì)一個(gè)統(tǒng)計(jì)與安排商品貨位的算法，使AGV小車能夠快速地完成貨架搬運(yùn)任務(wù)。

3 求解算法設(shè)計(jì)

3.1 貪婪算法

文中建立的商品動(dòng)態(tài)貨位分配模型是一個(gè)非線性混合整數(shù)規(guī)劃模型，當(dāng)待揀選訂單和商品種類數(shù)量較多時(shí)，在短時(shí)間內(nèi)很難直接獲得模型的精確最優(yōu)解，因此，需要針對(duì)文中提出的貨位分配問(wèn)題和模型特點(diǎn)，設(shè)計(jì)能夠快速求解該模型的啟發(fā)式算法。文中設(shè)計(jì)的啟發(fā)式算法如下所述。

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

輸入：歷史訂單數(shù)據(jù)，倉(cāng)庫(kù)內(nèi)待補(bǔ)貨商品的種類數(shù)及對(duì)應(yīng)的貨位數(shù)，新收入待上架商品的種類數(shù)及對(duì)應(yīng)的貨位數(shù)，貨架上現(xiàn)存商品初始的貨位存儲(chǔ)狀態(tài)。

1）統(tǒng)計(jì)所有貨架上現(xiàn)存商品的種類及其所占的貨位數(shù)，歷史訂單數(shù)據(jù)中包含的貨架上現(xiàn)存商品的種類信息，將訂單中不包含的貨架上現(xiàn)存商品種類視為滯銷商品，下架對(duì)應(yīng)貨位數(shù)。

2）找出全部有空位的貨架，將每個(gè)貨架上現(xiàn)存商品視為一個(gè)集合，根據(jù)歷史訂單信息和關(guān)聯(lián)性計(jì)算公式，求解所有待補(bǔ)貨商品與每個(gè)貨架上現(xiàn)存商品集合的關(guān)聯(lián)度之和，所有新收入待上架商品與每個(gè)貨架上現(xiàn)存商品集合的關(guān)聯(lián)度之和，并將所有的關(guān)聯(lián)度和進(jìn)行降序排列。

3）從降序排列中找到與貨架上現(xiàn)存商品集合關(guān)聯(lián)度和最大的商品，判斷該貨架上是否只有一個(gè)空貨位，如果只有一個(gè)空貨位，則進(jìn)入步驟4，否則進(jìn)入步驟5。

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

5）如果該貨架上有2個(gè)及以上的貨位，判斷該貨架上是否有商品存儲(chǔ)，如果有商品存儲(chǔ)，找到與貨架上現(xiàn)存商品集合關(guān)聯(lián)度和最大的商品存放在該貨架上，進(jìn)入步驟4，否則進(jìn)入步驟6。

6）如果該貨架上5層貨位均為空，計(jì)算所有剩余未被分配的倉(cāng)庫(kù)原有待補(bǔ)貨商品和新收入商品之間的關(guān)聯(lián)度值，將關(guān)聯(lián)度高的5種商品分配在該貨架上，更新待分配的商品集合和貨架上現(xiàn)存商品集合，判斷倉(cāng)庫(kù)內(nèi)所有待上架商品是否全部分配完成，如果全部完成，則結(jié)束計(jì)算，否則進(jìn)入步驟2。

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

3.2 粒子群算法

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

粒子根據(jù)以式（10）來(lái)更新自身的速度和位置。

為了使粒子在不同的進(jìn)化階段擁有不同的搜索能力，文中引入了動(dòng)態(tài)慣性權(quán)重。為設(shè)定一個(gè)變化區(qū)間，即在算法開(kāi)始時(shí)，賦予慣性權(quán)重一個(gè)較大的正值，在算法結(jié)束時(shí)，賦予慣性權(quán)重一個(gè)較小的正值。

動(dòng)態(tài)慣性權(quán)重值目前采用最多的是線性遞減慣性權(quán)重：

式（14）是一種經(jīng)驗(yàn)做法，文中在后期對(duì)模型進(jìn)行求解時(shí)首先與其他2種慣性群眾選擇方法進(jìn)行對(duì)比，從而選擇最優(yōu)的慣性權(quán)重：

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

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

1）根據(jù)第1階段的貨位分配結(jié)果初始化粒子群，設(shè)定種群規(guī)模、最大迭代次數(shù)、每個(gè)粒子的速度和位置等。

2）計(jì)算每個(gè)粒子的適應(yīng)度值。

5）計(jì)算動(dòng)態(tài)慣性權(quán)重值，更新迭代每個(gè)粒子的位置和速度。

6）判斷是否完成迭代次數(shù)，如果完成則結(jié)束計(jì)算，輸出最優(yōu)的可行解，否則返回步驟2繼續(xù)計(jì)算。

輸出：優(yōu)化后的商品貨位分配結(jié)果。

文中商品動(dòng)態(tài)貨位分配算法總流程見(jiàn)圖3。

圖3 商品動(dòng)態(tài)貨位分配算法總流程

4 模擬計(jì)算與分析

4.1 算例描述

某個(gè)電商倉(cāng)庫(kù)中包含30個(gè)貨架，每個(gè)貨架分成5層，共存儲(chǔ)55種商品，在倉(cāng)庫(kù)運(yùn)行一段時(shí)間后，倉(cāng)庫(kù)某些貨位為空狀態(tài)，即貨位上沒(méi)有商品存儲(chǔ)?，F(xiàn)倉(cāng)庫(kù)接到300個(gè)訂單需要揀選，每個(gè)訂單里包含的商品種類不超過(guò)10種，待揀選訂單見(jiàn)表1，其中包括10種（商品編號(hào)為56—65）之前進(jìn)行預(yù)售的商品。根據(jù)待揀選訂單，發(fā)現(xiàn)倉(cāng)庫(kù)現(xiàn)有存儲(chǔ)的55種商品中有商品需要進(jìn)行補(bǔ)貨，以及新收入的商品需要存儲(chǔ)到貨架上，待補(bǔ)貨商品和新收入的商品的種類和所需要的貨位數(shù)見(jiàn)表2。目前倉(cāng)庫(kù)的空余貨位不足以存儲(chǔ)全部的待補(bǔ)貨商品和新收入商品，在考慮每個(gè)訂單單獨(dú)揀選的情況下，需要將全部待補(bǔ)貨商品和新收入商品分配在貨架上，并且要達(dá)到訂單總揀選效率最高。

表1 300個(gè)待揀選訂單信息

Tab.1 Information of 300 orders to be picked

表2 待補(bǔ)貨商品及新收入商品所需貨位數(shù)

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

4.2 結(jié)果分析

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

首先根據(jù)歷史訂單計(jì)算55種倉(cāng)庫(kù)現(xiàn)有商品之間的關(guān)聯(lián)度，同時(shí)根據(jù)待揀選訂單計(jì)算所有商品之間的關(guān)聯(lián)度，并將此關(guān)聯(lián)度矩陣?yán)塾?jì)加入到歷史訂單關(guān)聯(lián)度矩陣中，最終的商品關(guān)聯(lián)度計(jì)算結(jié)果見(jiàn)表3。

經(jīng)過(guò)算法的不斷迭代與更新，得到各分配策略的貨位分配結(jié)果。貪婪算法經(jīng)過(guò)0.219 s得到的初始貨位分配結(jié)果見(jiàn)表4。粒子群算法對(duì)初始貨位分配結(jié)果進(jìn)行優(yōu)化后得到的貨位分配結(jié)果見(jiàn)表5，其算法收斂曲線見(jiàn)圖4。將全部待補(bǔ)貨商品和新收入商品隨機(jī)的分配在貨架上，得到的貨位分配結(jié)果見(jiàn)表6。

表3 商品關(guān)聯(lián)度計(jì)算結(jié)果

Tab.3 Goods relevance calculation result

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

Tab.4 Initial goods allocation obtained by the greedy algorithm

注：（）里表示的是貨架的初始存儲(chǔ)狀態(tài)，包含下架的商品種類。

表5 粒子群算法優(yōu)化后得到的貨位分配結(jié)果

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

注：（）里表示的是貨架的初始存儲(chǔ)狀態(tài)，包含下架的商品種類。

圖4 粒子群算法收斂曲線

在完成同一批300個(gè)訂單揀選時(shí)，文中提出的基于商品關(guān)聯(lián)度的分散存儲(chǔ)策略和隨機(jī)存儲(chǔ)策略的結(jié)果對(duì)比見(jiàn)表7。基于商品關(guān)聯(lián)度的分散存儲(chǔ)策略需要搬運(yùn)貨架1 166次，隨機(jī)分配策略需要搬運(yùn)貨架1 651次，將2種貨位分配策略進(jìn)行對(duì)比，文中的貨位分配策略可有效地將貨架的搬運(yùn)次數(shù)降低29.38%。同時(shí)，文中貨位分配策略得到的所有貨架上商品的關(guān)聯(lián)度之和比隨機(jī)分配策略得到的所有貨架上商品的關(guān)聯(lián)度之和提高了37.94%。

為了證明文中提出的算法在求解貨位分配模型結(jié)果時(shí)的穩(wěn)定性，在訂單數(shù)為300和每個(gè)貨架的貨位數(shù)固定（5）的情況下，設(shè)計(jì)不同數(shù)量的補(bǔ)貨商品總數(shù)、新收入商品總數(shù)和不同規(guī)模的貨架數(shù)。文中策略與隨機(jī)分配策略的貨架搬運(yùn)次數(shù)進(jìn)行了對(duì)比，對(duì)比結(jié)果見(jiàn)表8。

表6 隨機(jī)分配得到的貨位分配結(jié)果

Tab.6 Goods allocation obtained by random distribution

注：（）里表示的是貨架的初始存儲(chǔ)狀態(tài)，包含下架的商品種類。

表7 2種貨位分配策略結(jié)果對(duì)比

Tab.7 Comparison of 2 goods allocation strategies

表8 不同規(guī)模搬運(yùn)貨架次數(shù)結(jié)果對(duì)比

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

由表8可知，與隨機(jī)分配策略相比，文中提出的基于商品關(guān)聯(lián)度的分散存儲(chǔ)策略的貨架搬運(yùn)次數(shù)平均降低了29.32%，由此證明了文中提出的分配策略及算法具有穩(wěn)定性和可行性。

5 結(jié)語(yǔ)

近年來(lái)，隨著電商的快速發(fā)展，電商企業(yè)為了提高訂單的揀選作業(yè)和配送作業(yè)效率，已經(jīng)開(kāi)始逐漸采用“貨到人”揀選系統(tǒng)。文中對(duì)所有商品之間的關(guān)聯(lián)度進(jìn)行計(jì)算，根據(jù)一種商品可以存儲(chǔ)在多個(gè)貨架上、倉(cāng)庫(kù)內(nèi)原有待補(bǔ)貨商品所需要的貨位數(shù)、新收入待上架商品所需要的貨位數(shù)等約束條件構(gòu)建數(shù)學(xué)模型，設(shè)計(jì)貪婪算法和粒子群算法進(jìn)行求解，并通過(guò)仿真進(jìn)行算例驗(yàn)證，結(jié)果表明，文中提出的貨位分配策略可以明顯減少貨架平均搬運(yùn)次數(shù)。

在研究“貨到人”揀選系統(tǒng)貨位分配問(wèn)題時(shí)，文中以滯銷商品下架的貨位總數(shù)超過(guò)待補(bǔ)貨商品和新收入商品所需額外貨位數(shù)之和為約束條件，即存在某些商品種類不在待揀選訂單中的情況，但從實(shí)際角度出發(fā)，可能會(huì)存在待揀選訂單中包含全部商品的情況，同時(shí)，文中沒(méi)有考慮倉(cāng)庫(kù)滯銷商品的下架成本，因此，在下一步的研究中將著重考慮這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] 雷斌, 王菀瑩, 趙佳欣. 貨位分配優(yōu)化研究綜述[J]. 計(jì)算機(jī)工程與應(yīng)用, 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] 李陽(yáng), 唐磊, 胡俊. 基于遺傳算法的航天零件倉(cāng)庫(kù)貨位優(yōu)化研究[J]. 制造業(yè)自動(dòng)化, 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] 周亞云, 項(xiàng)前, 余崇貴, 等. 考慮物料需求關(guān)聯(lián)與周轉(zhuǎn)率的倉(cāng)儲(chǔ)貨位優(yōu)化方法[J]. 東華大學(xué)學(xué)報(bào)(自然科學(xué)版), 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] 袁瑞萍, 王慧玲, 李俊韜, 等. 基于移動(dòng)機(jī)器人的訂單揀選系統(tǒng)貨位優(yōu)化模型和算法研究[J]. 系統(tǒng)科學(xué)與數(shù)學(xué), 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關(guān)聯(lián)度的儲(chǔ)位優(yōu)化問(wèn)題研究[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí), 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

國(guó)家自然科學(xué)基金（71501015）；北京社科基金重點(diǎn)項(xiàng)目（18GLA009）；北京市長(zhǎng)城學(xué)者項(xiàng)目（CIT&TCD20170317）

張雪（1994—），女，北京物資學(xué)院碩士生，主攻智能物流系統(tǒng)。

周麗（1978—），女，博士，北京物資學(xué)院教授，主要研究方向?yàn)橹悄芪锪飨到y(tǒng)。

責(zé)任編輯：曾鈺嬋