基于關(guān)聯(lián)網(wǎng)絡(luò)的機(jī)器人移動貨架系統(tǒng)貨位分配方法

胡祥培 丁天蓉 張?jiān)磩P 莊燕玲

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

關(guān)鍵詞：機(jī)器人移動貨架系統(tǒng);貨位分配;關(guān)聯(lián)網(wǎng)絡(luò);聚類;“貨到人”揀選模式

中圖分類號：C934 文獻(xiàn)標(biāo)識碼：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 引言

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

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

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

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

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

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

2 問題描述與分析

2.1 問題描述

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

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

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

基于多個機(jī)器人移動貨架倉庫的實(shí)地調(diào)研和文獻(xiàn)梳理，提出如下假設(shè)：

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

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

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

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

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

索引：

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

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

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

參數(shù)：

N表示商品種類數(shù)量;

K表示客戶訂單數(shù)量;

R表示貨架數(shù)量;

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

2.2 復(fù)雜性分析

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

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

證明 當(dāng)商品存儲的貨架數(shù)量設(shè)置為1時，“一品多位”存儲模式下的機(jī)器人移動貨架系統(tǒng)貨位分配問題即變成“一品一位”存儲環(huán)境下的機(jī)器人移動貨架系統(tǒng)貨位分配問題，該問題已被Mirzaei等[22]證明是NP-hard問題，因此，本文研究的“一品多位”存儲模式下的機(jī)器人移動貨架系統(tǒng)貨位分配問題也是NP-hard問題?！耙黄范辔弧贝鎯δＪ较碌臋C(jī)器人移動貨架系統(tǒng)貨位分配問題的可行解比“一品一位”存儲模式的解空間更大，求解更為復(fù)雜。對于一品一位和一品多位兩種不同的貨位分配模式，對比解空間大小是反映兩者求解復(fù)雜性差異的有效手段。假定商品種類數(shù)目為N，單個貨架最多允許存儲M種商品，且N>M>1，不考慮貨架空置，進(jìn)行復(fù)雜性分析。

一品一位貨位分配模式下，其中Z表示貨架數(shù)量，Ω指所有可行解的集合，|Ω|表示解空間的元素?cái)?shù)量，解空間內(nèi)元素越多求解最優(yōu)解的難度也越大。

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

3 基于關(guān)聯(lián)網(wǎng)絡(luò)的三階段貨位分配方法

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

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

三階段貨位分配方法的核心內(nèi)容如下：

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

（2）第二階段為商品關(guān)聯(lián)網(wǎng)絡(luò)分析。從整體拓?fù)浣Y(jié)構(gòu)、節(jié)點(diǎn)重要性、連邊權(quán)重等維度對網(wǎng)絡(luò)進(jìn)行分析，利用網(wǎng)絡(luò)呈現(xiàn)的高內(nèi)聚、低耦合、無標(biāo)度特性，將貨位分配問題轉(zhuǎn)化為聚類問題進(jìn)行求解。同時，從網(wǎng)絡(luò)節(jié)點(diǎn)加權(quán)度的角度，依據(jù)網(wǎng)絡(luò)特性設(shè)計(jì)聚類求解方法，可大大縮減貨位分配方案的解空間，有利于快速生成較優(yōu)的貨位分配方案。

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

3.2 階段一：商品關(guān)聯(lián)網(wǎng)絡(luò)的構(gòu)建

訂單是挖掘商品關(guān)聯(lián)性的重要依據(jù)，從訂單內(nèi)部結(jié)構(gòu)來看，同一訂單購買的商品種類、數(shù)量具有差異性，訂單與訂單之間由于購買相同的商品也會產(chǎn)生關(guān)聯(lián)關(guān)系。數(shù)量龐大、結(jié)構(gòu)多樣、一單多品訂單給商品關(guān)聯(lián)分析帶來時間和空間的復(fù)雜性。訂單內(nèi)部、訂單間錯綜交叉的結(jié)構(gòu)復(fù)雜性，本質(zhì)是商品之間的關(guān)聯(lián)關(guān)系，將訂單中商品抽象成網(wǎng)絡(luò)的節(jié)點(diǎn)，商品間兩兩組合購買的頻次抽象成網(wǎng)絡(luò)的邊，這樣構(gòu)建的商品關(guān)聯(lián)網(wǎng)絡(luò)既能呈現(xiàn)商品之間是否存在關(guān)聯(lián)關(guān)系，又能表示其關(guān)聯(lián)關(guān)系的強(qiáng)弱，從而實(shí)現(xiàn)百萬級訂單信息壓縮至數(shù)萬種商品關(guān)聯(lián)的轉(zhuǎn)化，解決關(guān)聯(lián)分析面臨的時間和空間復(fù)雜性難題。商品關(guān)聯(lián)網(wǎng)絡(luò)的計(jì)算步驟如下：

表1是一個客戶訂單的示例，以表中訂單為例，介紹商品關(guān)聯(lián)網(wǎng)絡(luò)的構(gòu)建流程。

圖2是將訂單信息轉(zhuǎn)換成商品關(guān)聯(lián)網(wǎng)絡(luò)的圖示，訂單涉及的6種商品A到F分別被抽象成節(jié)點(diǎn)v1到v6?；冢?）式定義，根據(jù)圖2（a）與表1一致的訂單信息得到圖2（b）的訂單-商品關(guān)系矩陣P。根據(jù)（9）式，由訂單-商品關(guān)系矩陣P計(jì)算可得商品關(guān)聯(lián)矩陣S，相對應(yīng)的商品關(guān)聯(lián)網(wǎng)絡(luò)如圖2（d）所示。

3.3 階段二：商品關(guān)聯(lián)網(wǎng)絡(luò)的分析

機(jī)器人移動貨架系統(tǒng)一品多位貨位分配問題面臨可行解空間隨商品種類數(shù)急劇膨脹的難點(diǎn)，通過對商品關(guān)聯(lián)網(wǎng)絡(luò)的多維度分析，利用拓?fù)浣Y(jié)構(gòu)、節(jié)點(diǎn)、連邊的分析結(jié)果指導(dǎo)貨位分配問題求解，可使得貨位分配結(jié)果匹配商品購買規(guī)律，大大縮減貨位分配方案的解空間?；趪鴥?nèi)某大型網(wǎng)上超市倉庫的商品關(guān)聯(lián)網(wǎng)絡(luò)圖，對網(wǎng)絡(luò)結(jié)構(gòu)、節(jié)點(diǎn)、連邊的特征進(jìn)行分析。

（1）拓?fù)浣Y(jié)構(gòu)分析

如圖1（階段二的子圖）所示，從整體拓?fù)浣Y(jié)構(gòu)分析，商品關(guān)聯(lián)網(wǎng)絡(luò)具有高內(nèi)聚、低耦合特征，聚類求解方式非常符合網(wǎng)絡(luò)中商品節(jié)點(diǎn)聚集成團(tuán)的特點(diǎn)，因此可以將貨位分配問題轉(zhuǎn)化成聚類問題進(jìn)行求解，將節(jié)點(diǎn)聚成類，類對應(yīng)貨架，求解關(guān)聯(lián)商品的貨位分配問題。

（2）節(jié)點(diǎn)、連邊分析

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

（3）節(jié)點(diǎn)加權(quán)度分析

結(jié)合節(jié)點(diǎn)重要性、連邊權(quán)重的分析，加權(quán)度[23]適合用于度量商品關(guān)聯(lián)網(wǎng)絡(luò)節(jié)點(diǎn)的重要性，它是一種兼顧連邊數(shù)量和連邊權(quán)重差異的節(jié)點(diǎn)重要性度量方式，可篩選出頻繁與多種商品一同購買的核心商品。計(jì)算步驟如下：

（1）計(jì)算布爾矩陣。為了計(jì)算各節(jié)點(diǎn)的加權(quán)度，先根據(jù)商品關(guān)聯(lián)矩陣S計(jì)算布爾矩陣B，定義布爾矩陣

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

3.4 階段三：基于關(guān)聯(lián)網(wǎng)絡(luò)的聚類算法

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

目前文獻(xiàn)中效率最高的機(jī)器人移動貨架系統(tǒng)貨位分配聚類算法的時間復(fù)雜度為o（N4log N）[13]，本文算法的時間復(fù)雜度遠(yuǎn)低于已知最優(yōu)算法，說明本文算法更加高效。

4 實(shí)例驗(yàn)證

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

4.1 結(jié)果分析

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

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

從表3可知，基于關(guān)聯(lián)網(wǎng)絡(luò)的貨位分配方法顯著提高了各貨架商品間的關(guān)聯(lián)度，比構(gòu)造啟發(fā)式聚類的結(jié)果高43.38%，比隨機(jī)分配方法、按銷量分配方法高21901.16%、922.54%，表明設(shè)計(jì)方法效果較好。本文方法在總搬運(yùn)貨架數(shù)、仿真揀選耗時、AGV行駛距離方面優(yōu)勢明顯，均取得最小值，在AGV狀態(tài)占比部分，本文算法的AGV空駛、空閑狀態(tài)占比最低，載重狀態(tài)占比最高，表明工作狀態(tài)時間占比大，AGV利用率更高?？傊疚脑O(shè)計(jì)方法的仿真運(yùn)行結(jié)果最好，其次是構(gòu)造啟發(fā)式聚類算法，再是按銷量分配方法，隨機(jī)分配方法的表現(xiàn)最差，各方法的表現(xiàn)結(jié)果與貨架商品關(guān)聯(lián)度總和的結(jié)果一致。其中與隨機(jī)分配方法相比，本文所提方法能夠降低約33%的總搬運(yùn)貨架數(shù)和36%的AGV行駛距離。相比于目前表現(xiàn)最好的構(gòu)造啟發(fā)式聚類算法而言，本文所提方法依然可減少約10%的總搬運(yùn)貨架數(shù)和12%的AGV行駛距離。仿真結(jié)果進(jìn)一步驗(yàn)證了本文方法的有效性，結(jié)果表明旨在增強(qiáng)各貨架商品間關(guān)聯(lián)性的貨位分配是提高機(jī)器人移動貨架系統(tǒng)揀選效率的有效方式。

4.2 靈敏度分析

4.2.1 商品存儲貨架數(shù)的分析

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

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

4.2.2 貨架存儲商品種類數(shù)的分析

在生產(chǎn)實(shí)踐中，企業(yè)十分關(guān)注單個貨架應(yīng)存放多少種商品。為了比較貨架存儲商品種類對揀選效率的影響，在不同的貨架最多存儲商品種類數(shù)下，采用基于關(guān)聯(lián)網(wǎng)絡(luò)的貨位分配方法生成貨位分配方案，分析了需要的貨架數(shù)、貨架商品關(guān)聯(lián)度總和、仿真揀選耗時的變化，圖5是實(shí)驗(yàn)結(jié)果。

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

4.2.3 管理啟示

基于上述分析結(jié)果，從企業(yè)實(shí)踐應(yīng)用的角度出發(fā)，總結(jié)兩點(diǎn)管理啟示如下：

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

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

5 結(jié)論與啟示

針對機(jī)器人移動貨架系統(tǒng)的一品多位貨位分配難題，基于縮減解空間的思想，以提高貨架商品間關(guān)聯(lián)性為突破口，本文提出“關(guān)聯(lián)網(wǎng)絡(luò)構(gòu)建→關(guān)聯(lián)網(wǎng)絡(luò)分析→關(guān)聯(lián)網(wǎng)絡(luò)聚類”的三階段貨位分配方法，第一階段從訂單中抽取商品關(guān)聯(lián)關(guān)系構(gòu)建商品關(guān)聯(lián)網(wǎng)絡(luò)，第二階段分析網(wǎng)絡(luò)結(jié)構(gòu)后轉(zhuǎn)化為聚類問題求解，第三階段基于商品的加權(quán)度提出基于關(guān)聯(lián)網(wǎng)絡(luò)的聚類算法。研究成果為機(jī)器人移動貨架系統(tǒng)貨位分配的優(yōu)化決策提供了一種新的求解思路，有助于豐富機(jī)器人移動貨架系統(tǒng)的貨位分配和啟發(fā)式復(fù)雜網(wǎng)絡(luò)聚類的成果。在實(shí)踐上，理論成果為企業(yè)貨位分配方案的生成提供借鑒。

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

參 考 文 獻(xiàn)：

[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] 李英德.波次分區(qū)揀貨時裝箱與貨位指派問題協(xié)同優(yōu)化的模型與算法[J].系統(tǒng)工程理論與實(shí)踐，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制造的零部件配送中心貨位優(yōu)化研究[J].管理科學(xué)學(xué)報(bào)，2014，17（11）：10-19.

[9] 田歆，羅春林，汪壽陽，等.零售物流中心運(yùn)作優(yōu)化的一種T型補(bǔ)貨策略[J].中國管理科學(xué)，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].運(yùn)籌與管理，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