低層人工揀貨倉庫貨位優(yōu)化問題研究*

羅嫚玲，林 海，劉 威

(武漢大學國家網絡安全學院空天信息安全與可信計算教育部重點實驗室，湖北 武漢 430000)

1 引言

B2C電商企業(yè)訂單數(shù)量龐大、零散、交易時限極短，這種小批量、高頻次的出庫對其倉儲物流構成巨大成本。因此，如何合理規(guī)劃儲位成為提高空間利用率和貨物揀選效率以及降低成本的核心所在?，F(xiàn)階段國內的大部分配送中心、中小型企業(yè)等因受到資金、技術和環(huán)境等因素的限制，只能采用人工揀貨倉庫[1]。相較于自動化立體倉庫，人工揀貨倉庫貨架布局與揀選路線更加靈活，沒有太多規(guī)律，關于其貨位優(yōu)化問題的研究也很少。

當前國內外研究人員大多通過建立貨位優(yōu)化模型實現(xiàn)倉庫貨位優(yōu)化，主要優(yōu)化目標為設備或揀貨人員的行走路徑或時間，同時根據倉庫特點或倉儲需求考慮是否結合其它優(yōu)化目標[2-14]。例如，自動化立體倉庫由于貨架高、貨物重需借助堆垛機或叉車完成揀貨，此時除以設備行走時間為主要優(yōu)化目標外還需考慮貨架穩(wěn)定性、貨物周轉頻率、作業(yè)能耗等其它優(yōu)化目標或相關約束[15-17]。而低層人工揀貨倉庫由于存儲商品體積小且重量輕，此時商品之間的關聯(lián)性顯得更重要，可不考慮貨架穩(wěn)定性、貨位載重等因素[1,8,10]。在模型求解方面，由于該類問題屬于組合優(yōu)化問題，大多采用改進遺傳算法、蟻群算法、粒子群算法、模擬退火算法、貪心算法和混合粒子群等搜索算法[1,3,5-8,10,12,14,16,18,19]，少部分根據問題本身設計啟發(fā)式算法[6,11,20]。

行走路徑或時間作為貨位優(yōu)化模型的主要優(yōu)化目標，其求解復雜度直接關系到貨位優(yōu)化效率。不管是自動化立體倉庫還是基于自動導引運輸車AGV(Automated Guided Vehicle)的貨到人系統(tǒng)的普通立體倉庫[21]，每次揀選只需將指定位置的某一商品或貨架搬運到指定出口[10,16,17]，此時路徑計算時間復雜度為線性復雜度。而低層人工揀貨倉庫，由于一次揀貨需在不同貨架間行走，故行走路徑計算屬于旅行商問題的特例，而旅行商問題是非常經典的NP問題，當問題規(guī)模很大時，幾乎不可能在有限的時間內求得最優(yōu)解?，F(xiàn)有人到貨系統(tǒng)的貨位優(yōu)化研究幾乎都集中在布局規(guī)則的單深區(qū)或雙深區(qū)倉庫，該類倉庫有多條巷道，每條巷道兩邊多個貨架并排，這使得揀選某一貨架的商品時只能從該貨架所在巷道兩端進入巷道，此時可通過指定合理的啟發(fā)式路徑策略求得最短行走路徑，這使得時間復雜度大大降低[6]。但是，事實上很多中小型企業(yè)的倉庫是人到貨倉庫，一般由揀貨人員攜帶揀貨小車或其它裝載設備進行揀貨，為減少不同揀貨人員同時揀貨時的相互干擾，倉庫布局并不會采用多個貨架并排形成巷道，而是使揀貨通道寬敞且相互連接，導致揀貨路徑靈活，難以直接采用啟發(fā)式路徑策略降低時間復雜度。

由于電商企業(yè)倉庫的一次揀選都包含多種商品，故在貨位優(yōu)化問題中商品關聯(lián)性成為了研究熱點。就關聯(lián)關系分析方面，大部分研究集中在利用數(shù)據挖掘算法分析不同商品的內在關聯(lián)性，如采用Apriori算法[21-24]挖掘商品之間的關聯(lián)關系，但在電子商務環(huán)境中，對小批量、高頻次訂單數(shù)據進行商品關聯(lián)規(guī)則挖掘時，該算法計算速度緩慢，易導致貨位分配時間過長。因此，在上述條件下采用了一種不產生候選集的發(fā)現(xiàn)頻繁項集的FPGrowth算法[6,25]，其運算速度相比于Apriori算法提升幾個數(shù)量級，但相應的內存開銷也會較大。少部分研究基于矩陣或集合理論自定義啟發(fā)式算法[8,26,27]或者構建聚類模型[28]來測量不同商品之間的相似度。目前幾乎所有的商品關聯(lián)性分析都沒有考慮商品本身的熱銷程度對該商品與其它商品之間的關聯(lián)關系的影響。考慮商品關聯(lián)性進行貨位優(yōu)化時，不同的商品揀選方式對應的聚類要求也不同[23,28-30]。例如，貨到人系統(tǒng)中只有將相關性高的多個商品存放在同一個貨架才會縮短行走路徑，而人到貨系統(tǒng)將其存放在相鄰貨架同樣有效。此外，結合商品關聯(lián)性進行貨位優(yōu)化不僅可以縮短路徑，還可用于緩解擁塞和平衡工作量，如貨到人系統(tǒng)可通過分析貨品組之間的關聯(lián)度來緩解堵塞[8,31]。調研發(fā)現(xiàn)針對人到貨系統(tǒng)考慮商品關聯(lián)性進行貨位優(yōu)化以及考慮關聯(lián)度緩解堵塞的研究還很少。故本文在分配貨位時考慮了商品相關性因素，即將相關性高的商品存放到相同或相鄰貨架，此時相關性較高的不同商品可視為一個社區(qū)；然后通過社區(qū)劃分算法對不同商品及其相關性組成的網絡進行社區(qū)挖掘，使得社區(qū)內部商品節(jié)點連接緊密，不同社區(qū)商品節(jié)點之間連接稀疏。

綜上所述，本文針對倉庫布局不規(guī)則、商品關聯(lián)性重視程度不夠且現(xiàn)有的低層人工揀貨倉庫的儲位優(yōu)化研究非常不足等問題，在考慮商品熱銷度、相關性等因素的基礎上，提出基于社區(qū)劃分的貨位優(yōu)化算法，同時構建多個指標從不同優(yōu)化方面對多個貨位擺放方案進行評估和選擇。

2 問題描述

本文所研究的B2C電商企業(yè)低層人工揀貨倉庫布局不規(guī)則且貨架大小不一，與單深區(qū)或雙深區(qū)倉庫的巷道相比，揀貨通道更寬、更多且相互連通，使得揀選人員行走路徑更靈活。

倉庫的訂單揀選過程：揀貨員從倉庫復核打包區(qū)出發(fā)開始揀貨，當訪問完當前訂單所需訪問的所有貨架后，回到打包區(qū)。

因為行走是主要人力消耗，所以貨位優(yōu)化的主要優(yōu)化目標為縮短行走路徑或時間，其求解復雜度直接關系到優(yōu)化效率，而訂單揀選的靈活性使其難以采用啟發(fā)式路徑策略來降低求解耗時。

低層倉庫存放的商品具有體積小、重量輕的特點，不需考慮貨架承重及其穩(wěn)定性。但是，若只考慮行走路徑這一優(yōu)化目標，則很可能導致某些距離出口很近的貨架被放滿熱銷商品，造成嚴重的堵塞問題，反而降低揀貨效率，因此還需將緩解堵塞作為優(yōu)化目標。此外，本文還在仔細分析倉庫人力消耗的基礎上，提出了減少倉庫揀貨人員工作時間進而減少人員數(shù)量的優(yōu)化目標。

3 基于社區(qū)劃分的貨位優(yōu)化算法

貨位優(yōu)化算法的目標包括縮短行走路徑，緩解堵塞，減少揀貨人員數(shù)量。打包點是將復核打包區(qū)抽象為一個點，其坐標為復核打包區(qū)的位置中點。

3.1 算法描述

B2C電商企業(yè)商品多種多樣，商品之間的關系可根據訂單來衡量，一個訂單可將多種商品連接起來，而成千上萬的不同訂單各自連接不同的商品。從某種程度上講這是復雜網絡在現(xiàn)實世界中的一種表現(xiàn)形式，通過對復雜網絡進行社區(qū)挖掘，使得社區(qū)內部節(jié)點連接緊密，不同社區(qū)節(jié)點之間連接稀疏。本文正是基于這種對復雜網絡進行劃分的思路，提出了基于社區(qū)劃分的貨位優(yōu)化算法。

基于社區(qū)劃分的貨位優(yōu)化算法首先根據商品之間的關聯(lián)度，抽象出以商品為頂點的無向有權網絡，并對此復雜網絡進行社區(qū)挖掘，生成多個具有一定的內聚度的社區(qū)。然后以社區(qū)為單位進行放貨，此階段主要考慮社區(qū)熱度、貨架位置等影響因素。以社區(qū)為單位進行存放可保證同一社區(qū)的商品被存放到相鄰或同一貨架，且同一社區(qū)的商品是根據商品關聯(lián)度被劃分到同一社區(qū)，通常不會都是熱銷商品，所以本文算法在滿足縮短行走路徑的條件下還能在一定程度上緩解堵塞。

由于無法預測社區(qū)劃分算法的劃分結果，也無法直接判斷商品關聯(lián)度對貨位優(yōu)化的影響程度，故本文通過設置最大子社區(qū)閾值對社區(qū)劃分結果進行約束，以控制商品關聯(lián)度因素在貨位優(yōu)化算法中的影響。之后對不同劃分結果以社區(qū)為單位進行存放和調整可得到不同的擺放方案，最后根據指標對多個方案進行評估和選擇?；谏鐓^(qū)劃分的貨位優(yōu)化算法流程如圖1所示，詳細描述如下：

(1)構建無向有權網絡：無向有權網絡由節(jié)點集合及節(jié)點之間的邊集合組成，每種商品為一個節(jié)點，網絡節(jié)點總數(shù)為歷史訂單中的商品種類數(shù)總和。任意2個節(jié)點ci和cj之間的權重wci,cj為2個商品之間的關聯(lián)度c_rci,cj，表示歷史訂單中同時包含2個商品節(jié)點的訂單總數(shù)；商品熱度c_hotci是指歷史訂單中，所有包含商品ci的訂單總數(shù)；社區(qū)熱度co_hotcoi,coj是指社區(qū)內商品的熱度總和；社區(qū)之間的關聯(lián)度co_rcoi,coj是指2個社區(qū)之間的連邊權重之和。

(2)初次劃分階段：首先利用滿足劃分要求的社區(qū)劃分算法(見3.2節(jié))對構建的無向有權網絡進行劃分，初次劃分結果為part，然后將part中的最大子社區(qū)所包含的節(jié)點總數(shù)設置為初始閾值part_T，并轉到存放階段。

(3)存放階段：目的是將劃分階段(初次劃分或再次劃分)的劃分結果以社區(qū)為單位存放到貨架，主要考慮社區(qū)熱度、社區(qū)之間的關聯(lián)度及貨架位置等因素為各個子社區(qū)尋找最佳存放貨架。

存放階段偽代碼如下所示：

1.funcationpartion_deposit_to_shelf(c_part,graph)/*社區(qū)劃分閾值part_T對應的當前社區(qū)劃分結果c_part，貨架布局graph*/

2.ininitialize(F_Allo);/*初始貨位擺放方案F_Allo*/

3.new_part=sort(c_part,co_hot);/*按社區(qū)熱度排序*/

4.forparttonew_part//存放

5.b_shelfs=find_Bshelfs(c_part,graph,F_Allo);

6.F_Allo=deposit(b_shelfs,c_part,F_Allo);

7.endfor

8.returnF_Allo;

9.endfuncation

詳細步驟如下所示：

①確定子社區(qū)的存放順序：將子社區(qū)按照社區(qū)熱度從大到小排序。

②按順序為每一個子社區(qū)尋找當前最優(yōu)貨架群并將其存放到指定貨架：

首先，為社區(qū)coj指定中心存放貨架：當j=0時，coj為第1個存放的社區(qū)，其中心存放貨架為距離打包點最近的貨架；當j>0時，評估當前所有可用貨架的存放優(yōu)劣度，從中選出最優(yōu)貨架作為中心貨架。貨架優(yōu)劣度計算如式(1)所示：

(1)

其中，shelf_rets表示當前可用貨架s存放社區(qū)coj時的貨架優(yōu)劣度，該值越大表示該貨架越可能成為社區(qū)coj的實際存放貨架；co_rcoi,coj表示社區(qū)coi和coj之間的關聯(lián)度；cs(coi)為社區(qū)coi的中心存放貨架；discs(coi),s表示社區(qū)coi的中心存放貨架與貨架s之間的距離。如果兩貨架相同時，為避免發(fā)生零除錯誤，此時將其設置為一個小于最近貨架距離的常數(shù)A。diss,sp表示當前評估貨架s與打包點sp之間的距離。

其次，計算當前倉庫中所有可用貨架與中心貨架的距離，并將可用貨架按照距離從小到大排序，得到以該中心貨架為首的可用貨架序列。

最后，將子社區(qū)商品依次存放到可用貨架序列。

③存放結束后，輸出劃分閾值part_T所對應的一個初始擺放方案F_Allo，之后轉到調整階段。

(4)調整階段：當商品種類數(shù)小于總貨位數(shù)時，初始擺放方案并不能把貨架存滿，所以調整階段在這時主要根據熱度和距離因素補齊存在空位的貨架，其偽代碼如下：

1.funcationjust_First_Placement_result(F_Allo,graph)/*初始貨位擺放方案F_Allo,貨架布局graph*/

2.forktolen(shelf)//貨架若存在空位則補齊

3.ifget_Cnum(shelf[k])

4.E_Allo=complete_shelf(shelf)

5.endif

6.endfor

7.returnE_Allo;//最終貨位擺放方案E_Allo

詳細步驟如下所示：

步驟1判斷所有貨架中是否存在貨架具有空位，若沒有則轉到步驟3。否則，轉到步驟2進行調整。

步驟2調整主要考慮熱度與距離因素，首先確定一個未存滿貨架se，然后找出沒有被存放在貨架se上的其它商品種類，并記錄其熱度與所在的貨架，之后評估哪些類型的商品適合存放在該貨架，如式(2)和式(3)所示：

(2)

(3)

其中，c_retc表示商品c的存放價值，該值越大，則說明商品c越適合被添加到當前有空位的貨架se；c_hotc表示商品c的商品熱度；c_hotmax表示所有商品中的最高熱度值，做歸一化處理；se表示當前未存滿貨架，sc表示存放商品c的所有貨架中距離se最近的貨架；dis(se,sc)表示貨架se與sc之間的距離；dismax表示當前倉庫中不同貨架之間的最大距離，做歸一化處理；dis(se,shc)表示貨架se與貨架shc之間的距離；Shc表示存放商品c的所有貨架集合。

步驟3根據評估值對商品從大到小排序，將前e種商品添加到當前有空位貨架se,e為空貨位個數(shù)。

步驟4貨架遍歷調整結束后得到閾值part_T對應的最終擺放方案，之后轉到再次劃分階段。

(5)再次劃分階段：本階段通過設置不同的閾值part_T可得到不同的劃分結果，作為存放階段的輸入，最終可以得到多個不同的貨位擺放方案。再次劃分階段的輸入為初次劃分結果及其劃分閾值part_T，該值大小為初次劃分結果中最大子社區(qū)所包含的節(jié)點總數(shù)。本階段通過不斷減小part_T以獲得不同的社區(qū)劃分結果，直到part_T減小到1時再次劃分階段結束。每一個閾值獲得的再次劃分結果除了進入存放階段和調整階段獲得最終的貨位擺放方案外，也是下一輪的再次劃分輸入。再次劃分階段偽代碼如下所示：

1.funcationagain_part(part_T,c_part)/*初次劃分結果c_part對應的劃分閾值part_T*/

2.whilepart_T≠1//貨架若存在空位則補齊

3.part_T-=1;

4.Whileexist_big_part(c_part)

5.forparttoc_part

6.iflen(part)>part_T

7.part_g=build_g(part);

8.spart=again_part(part_g);

9.iflen(spart)>part_T

10.spart=rand_part(part,part_T);

11.endif

12.update(c_part,spart);

13.endif

14.endfor

15.endwhile

16.a_parts=update_apart_result(T,c_part)

17.endwhile

18.returna_parts/*不同劃分閾值及其對應的再次劃分結果*/

19.endfuncation

詳細步驟如下所示：

步驟1判斷當前part_T是否為1，若是，則轉到評估選擇階段；否則設置當前社區(qū)劃分結果c_part為閾值part_T時的劃分結果，part_T-=1，part_Flag=False。

步驟2判斷c_part是否存在子社區(qū)所包含的節(jié)點數(shù)大于part_T，若不存在則轉到步驟3，否則轉到步驟5。

步驟3如果part_Flag為False，轉到步驟4，否則轉到存放階段。

步驟4設置最大子社區(qū)閾值為part_T的最終貨位擺放方案與閾值part_T+1的最終貨位擺放方案相同，然后轉到步驟1。

(6)評估選擇階段：根據評估指標從多個貨位擺放方案中選出最優(yōu)方案。

3.2 社區(qū)劃分算法選擇

基于社區(qū)劃分的貨位優(yōu)化算法中的劃分步驟由社區(qū)劃分算法完成，而劃分算法的好壞會影響貨位優(yōu)化算法的效率。

3.2.1 社區(qū)劃分算法要求

社區(qū)劃分算法具有以下幾個特點：(1)電商企業(yè)商品種類較多，訂單數(shù)量龐大且零散，這使得無向有權網絡規(guī)模較大，復雜度高且往往是多分量而非單分量；(2)本文提出的貨位優(yōu)化算法采用最大子社區(qū)閾值來控制關聯(lián)度的影響程度，需多次劃分，故劃分速度會影響貨位優(yōu)化算法的運行效率；(3)劃分質量的好壞直接關系到劃分次數(shù)的多少以及最終貨位擺放方案的質量。綜上可知，社區(qū)劃分算法需滿足在劃分規(guī)模較大且復雜的網絡時運算速度快且劃分質量高。

3.2.2 FU算法

根據劃分算法需求，本文對多種經典社區(qū)劃分算法進行了理論與實驗分析，發(fā)現(xiàn)FU(Fast Unfolding)算法最適用于無向有權稠密網絡。因此，本文提出的基于社區(qū)劃分的貨位優(yōu)化算法中的劃分步驟將由FU算法來完成，后文將其稱為基于社區(qū)劃分FU的貨位優(yōu)化算法。

需要說明的是,無論是速度合適、劃分質量高的非重疊算法，還是在處理有權稠密網絡時運算速度快、劃分性能好且可控制重疊點數(shù)量少于或等于多余貨位數(shù)的重疊算法都可直接替換本文選定的社區(qū)劃分算法。

FU算法，又稱Louvain算法[32],可以分為2個階段反復迭代計算。首先將網絡中每個節(jié)點看成一個單獨的社區(qū)，并對社區(qū)進行編號;然后，對每個節(jié)點i，計算其加入鄰居節(jié)點j所在社區(qū)后模塊度增量ΔQ的變化，如果ΔQ>0，則將其放到對應模塊度變量變化最大的鄰居節(jié)點，否則，節(jié)點停留在原社區(qū)。將節(jié)點i放入社區(qū)C后，對應的模塊度增量計算公式如式(4)所示：

(4)

其中，Σin和∑tot分別表示社區(qū)C內部邊權重之和以及所有與社區(qū)C內節(jié)點相連的邊權重之和；ki表示指向節(jié)點i的連邊權值之和，ki,in表示節(jié)點i與社區(qū)C內節(jié)點之間連邊的權重之和,E表示網絡中邊的數(shù)量。

重復上述過程直到所有節(jié)點所屬社區(qū)不再發(fā)生變化，第1階段結束。第2階段是利用其在第1階段發(fā)現(xiàn)的社區(qū)構建新的網絡，節(jié)點即為上一階段發(fā)現(xiàn)的社區(qū)，此時對社區(qū)內的節(jié)點進行壓縮，社區(qū)內節(jié)點之間的權重轉化為新的節(jié)點環(huán)的權重，社區(qū)間的邊權重轉化為新節(jié)點間的邊權重，當新的網絡建立完成后，重復第1階段的過程直到得到局部模塊度最大的社區(qū)為止。

4 評估指標及優(yōu)化模型

基于社區(qū)劃分的貨位優(yōu)化算法最后一步是評估和選出最優(yōu)的方案，故本節(jié)主要針對不同優(yōu)化目標構建評估指標。

4.1 評估假設及變量說明

貨位優(yōu)化目的是提高訂單揀選效率，故通過模擬與分析工作人員的揀選流程，構建評估指標對優(yōu)化方案進行效果評估。為便于模擬揀選流程，需對其做出如下合理假設：

假設1倉庫揀貨人員數(shù)目大于1，所有人以相同行走速度共同負責倉庫揀選。

假設2每個揀貨人員每次揀選一個訂單，根據下單時間順序進行揀選，揀選一個訂單的行走路徑為當前可走路徑中的最短路徑，另外不考慮小車載重問題。

假設3每個貨位只存放一種商品，任意貨位的商品數(shù)量能夠滿足任意一個訂單所需該種商品的數(shù)量要求，即不考慮商品數(shù)量與缺貨問題。

本文中使用的變量說明如表1所示。

Table 1 Variable description

4.2 評估指標

本文提出了3個單一評估指標和1個綜合指標用于評估貨位擺放方案的優(yōu)劣，3個單一指標對應3個優(yōu)化目標，包括縮短行走路徑、緩解堵塞及減少揀貨人員數(shù)量。

4.2.1 縮短行走路徑

由于行走時間占整個配送中心總作業(yè)時間的60%，所以從縮短揀貨人員的行走路徑為主要優(yōu)化目標。由假設可知揀貨人員以訂單為單位進行揀選，故需累加揀選所有訂單的行走路徑。由于低層人工揀貨倉庫布局不規(guī)則，無法指定啟發(fā)式行走策略來降低計算復雜度，故為了滿足時間復雜度要求，本文選擇了2種算法求解各訂單的行走路徑:動態(tài)規(guī)劃算法與貪心算法。當單次訪問貨架節(jié)點很少時，采用動態(tài)規(guī)劃求解精確最短路徑，否則采用貪心算法求解近似最短路經，以減少計算耗時。

第1個評估指標為揀選所有訂單的行走路徑總和Zdis，后文簡稱行走總路程，其計算如式(5)和式(6)所示：

(5)

(6)

其中,Zk表示揀選訂單k的最短行走路徑；MDk表示揀選訂單k的所有可能的取貨方案。取貨方案是指完成該訂單所需訪問的貨架點集合及打包點，由于不同的貨架可能存放相同的商品，而在取貨時一個訂單對應的某種商品只需訪問其中一個貨架即可，故單個訂單可能存在多個取貨方案；SDk表示訂單k的任意一個取貨方案；len(SDk)表示取貨方案SDk所包含的訪問點個數(shù)。雖然訂單具有小批量、高頻次的特點，但難免存在包含訪問節(jié)點數(shù)過多的大訂單，若繼續(xù)采用動態(tài)規(guī)劃計算行走路徑會耗時過多。故為提高算法效率，通過設置揀選單個訂單訪問節(jié)點個數(shù)閾值len_k來決定采用何種方式計算行走路徑，如果當前揀選訂單需訪問節(jié)點個數(shù)超過該閾值，則采用貪心算法，否則采用動態(tài)規(guī)劃算法。

(7)

(8)

(9)

s.t.xij∈{0,1},xii=0,i,j∈SDk

(10)

(11)

(12)

(13)

4.2.2 緩解堵塞

將熱銷商品聚集到離打包點近的貨架可使行走路徑大大縮短，但很可能引起堵塞。是否發(fā)生堵塞與訂單到來時間、訂單包含的商品種類數(shù)、訂單被揀選的開始時間、訂單實際揀選路徑、人員數(shù)量、行走速度等因素有關。難以通過模擬揀選來記錄不同工作人員在倉庫中的時間與位置，進而計算堵塞的頻率和累積耗時。故本文通過統(tǒng)計某一段時間內各個貨架的取貨頻次標準差，來表征該時間段內可能的堵塞情況。某貨架的取貨頻次是指揀選人員在該貨架的取貨次數(shù)。取貨1次是指任意1個工作人員在揀選任意1個訂單的過程中，只要在某個貨架處停下揀貨，則為1次取貨，那么該貨架的取貨頻次加1。

因為訂單處理存在揀選時限，不同處理時間段的訂單揀選不會相互影響，所以直接對很長一段時間內的訂單統(tǒng)計取貨頻次計算標準差來表征堵塞程度并不是很合理。因此，本文首先對訂單分批，不同批次的訂單揀選不會發(fā)生堵塞，然后計算各個批次對應的取貨頻次標準差，最后累加求和，以此表征堵塞程度。訂單分批主要按時間窗口處理，通過考慮揀貨人員的工作時間段，商家指定的訂單揀選時限或當天發(fā)貨截止時間，在滿足不出現(xiàn)超時訂單影響顧客購物體驗的條件下為各個訂單指定處理時間段。

在本文算例中,上海某電商物流企業(yè)指定每天t點前下單可當天發(fā)貨,訂單發(fā)貨時限tf為24 h，故可知當天t點后到第2天t點前之間的所有訂單須在第2天工作時間段內發(fā)出，分批時間窗為當天t點至第2天t點，在此時間段內到來的所有訂單為一個批次，最終得到多個批次。

雖然標準差越大發(fā)生堵塞的可能性越大，但也不是越小越好。因為優(yōu)化的最終目的是減少揀選時間，而它不僅和堵塞耗時有關，還和行走耗時有關。由于不同貨架距離打包點的位置不同，行走耗時也不同，故允許不同貨架的取貨頻次不同。本文考慮距離得到表征不同貨架之間的允許取貨頻次差異的變量F，然后在此基礎上計算取貨頻次標準差。Fi表示在貨架si揀貨1次相當于在距離sp最近的貨架處等待揀貨Fi-1次后取貨1次，即允許在距離打包點最近的貨架取貨頻次是在貨架si取貨頻的Fi倍，F(xiàn)i計算如式(14)所示：

(14)

其中,dissi表示貨架si到打包點sp的距離；dismin表示所有貨架中距離打包點最近的貨架與sp的距離。tq表示揀選單個訂單的過程中在某個貨架處揀貨1次需要花費的平均時間，也表示堵塞1次需要等待的平均時間，其計算如式(15)所示：

(15)

其中,s_m表示平均1個訂單包含的商品數(shù)。

通過Fi可確定不同貨架的最佳取貨頻次，只要各個貨架實際取貨頻次滿足此條件，則認為達到了最佳取貨頻次狀態(tài)，此時衡量堵塞程度的標準差應為0。本文利用Fi與貨架si實際取貨頻次計算在考慮貨架差異情況下的取貨頻次標準差之和Zstd，后文簡稱堵塞指標,其計算如式(16)所示：

(16)

其中,M表示批次數(shù)；ZK表示揀選完批次K的所有訂單后各個貨架的取貨頻次的方差，其計算如式(17)所示：

(17)

其中,N表示當前倉庫的總貨架數(shù)；fi表示貨架i的實際取貨次數(shù)；fmean表示對各個貨架的實際取貨頻次乘以對應Fi后的平均取貨頻次，其計算如式(18)所示：

(18)

4.2.3 減少人員數(shù)量

揀貨人員的工作時間主要花費在行走、揀取商品和打包3個方面。行走時間與行走速度、距離有關；揀選商品時間與揀取1次的平均時間、揀取頻次有關；打包時間與打包速度、訂單數(shù)量有關。所有影響揀選時間的因素中無論是行走速度、打包速度還是訂單數(shù)量都無法通過合理的貨位擺放得到優(yōu)化，只有行走路徑和揀取頻次能夠優(yōu)化。通過計算工作總耗時便可計算出所需揀貨人員的數(shù)量。首先，將行走速度、打包速度簡化為平均速度定值，撿取1次商品的平均時間tq根據式(15)求得;然后,通過貨位優(yōu)化縮短行走路徑和降低揀貨頻次，進而減少揀選總時間和所需揀貨人員的數(shù)量。由前文分析可知，為防止訂單超時，揀選人員須按時處理完各個批次的所有訂單，即人員數(shù)量需滿足花費時間最多的批次不能出現(xiàn)超時訂單。故此優(yōu)化目標需分別計算各個批次所需花費的總時間，包括行走時間、揀取時間和打包時間，從中找出花費總時間最多的批次，并記錄該批次的行走路徑與揀取總頻次，即2個評估指標。而行走路徑已作為第1個指標被單獨提出，所以只需評估耗時最多的批次對應的揀貨總頻次之和即可。綜上可知，為花費時間最多的批次j對應的取貨總頻次Zq,后文簡稱取貨總頻次，其計算如式(19)～式(24)所示：

(19)

(20)

(21)

(22)

(23)

(24)

4.2.4 綜合評估指標

采用不同的評估指標從不同優(yōu)化角度來衡量貨位擺放方案的優(yōu)劣時，目標函數(shù)可能朝不同的方向收斂，故無法利用多個指標同時評估以選出最優(yōu)擺放方案。因此，本文采用簡單加權方法將多個指標值加權成綜合指標進行評估，各個單指標如下所示：

(1)平均每批次行走總時間Ztd如式(25)所示:

Ztd=Zdis/(M×v)

(25)

(2)取貨頻次標準差之和Zstd見式(16);

(3)耗時最多批次所對應的取貨時間Ztq如式(26)所示：

Ztq=Zq×tq

(26)

最后利用簡單加權法將3個指標組合為如式(27)和式(28)所示的綜合評估指標Z：

Z=αZtd+βZstd+λZtq

(27)

s.t.α+β+γ=1

(28)

5 實驗結果及分析

本文基于上海某電商物流企業(yè)的多個實際訂單數(shù)據和4種貨位優(yōu)化對比算法，驗證了本文提出的基于社區(qū)劃分FU的貨位優(yōu)化算法的有效性。

5.1 對比算法

(1)基于隨機的貨位優(yōu)化算法：首先隨機生成多個貨位擺放方案，再利用評估指標從中選出較優(yōu)方案。

(2)基于社區(qū)劃分Infomap的貨位優(yōu)化算法：該算法是指本文提出的基于社區(qū)劃分的貨位優(yōu)化算法中的劃分步驟由Infomap劃分算法完成，設置該算法的目的是探究不同劃分算法對本文所提算法的影響。

(3)基于貪心算法的貨位優(yōu)化算法：該算法的思想是將最好的商品及其部分關聯(lián)商品擺放到最優(yōu)貨架。最好的商品是指熱度最高的商品，部分關聯(lián)商品是指與該商品的密切度高于指定閾值的所有商品。某商品與其它商品的密切度為兩者的關聯(lián)度除以該商品與所有商品的關聯(lián)度之和。最優(yōu)貨架通過評估值找出，貨架ex_si的評估值計算如式(29)所示：

(29)

其中，c表示常數(shù)；J表示所有貨架集合；freespace(sj)表示貨架sj的剩余空位;dis(si,sj)表示貨架si與sj之間的距離,如果si=sj，則dis(si,sj)為常數(shù)A；dis(si,sp)表示貨架si與打包點sp之間的距離。

(4)基于遺傳算法的貨位優(yōu)化算法：主要根據4.2.4節(jié)中的綜合指標建立貨位優(yōu)化模型，之后采用改進的遺傳算法進行求解。首先，生成一定數(shù)量的隨機貨位擺放方案，單個擺放方案可指定任意貨架上的任意貨位存放何種商品，即為一條染色體；然后，進行大規(guī)模的隨機探索求得最優(yōu)方案。隨機探索過程包括交叉、變異、調整修復和適應度計算。

5.2 實驗數(shù)據及變量設置

本文實驗數(shù)據來自上海某電商物流企業(yè)2019年某月的訂單，總共25 397個訂單，包括560個商品種類，商品體積小且重量輕。該企業(yè)倉庫的部分實際布局如圖2所示，共48個貨架且每個貨架都有固定取貨點，包括2種貨架類型：類型1(虛線框)有14個且每個貨架有22個儲位，類型2(實線框)有34個且每個貨架有9個儲位。

為計算揀選路徑，設置了2個假設：(1)揀貨人員揀選時靠近貨架邊緣；(2)揀貨人員走矩形路線而不進行斜線移動?；诩僭O抽象出用于路徑計算的無向有權圖如圖2所示，任意2點之間的連線權重為2點之間的距離。

實驗中使用的評估指標中的變量值如表2所示。本文考慮以行走路徑為主要優(yōu)化目標，綜合評估指標和評估模型中的權重系數(shù)設置為α=0.8,β=0.15,γ=0.05。

Table 2 Variable settings

5.3 結果分析

本文評估指標包括3個單一指標和1個綜合指標，其中單一指標包括行走總路徑、堵塞指標和取貨總頻次。本節(jié)先分析本文基于社區(qū)劃分的貨位優(yōu)化算法結果，然后對比不同方案的平均解和最優(yōu)解。

基于社區(qū)劃分的貨位優(yōu)化算法的多個貨位擺放方案的各項評估指標值隨著最大子社區(qū)閾值增大的變化情況如圖3所示。從圖3可以看到，基于社會劃分FU的貨位優(yōu)化算法的綜合指標值與單一指標值最優(yōu)解都優(yōu)于基于社區(qū)劃分Infomap的貨位優(yōu)化算法的。此外，虛線一直存在波動，說明需要評估的方案較多；實線存在多個直線段，說明需要評估的方案較少。故基于社區(qū)劃分FU的貨位優(yōu)化算法不論在方案質量還是評估時間上都優(yōu)于基于社區(qū)劃分Infomap的貨位優(yōu)化算法。這表明選擇符合劃分要求的社區(qū)劃分算法對于改進本文所提貨位優(yōu)化算法非常重要。

表3是不同算法最終多個貨位擺放方案的整體質量情況。由于各個算法的時間主要耗費在指標評估階段，評估時間與評估方案個數(shù)呈正比，表3最后一列統(tǒng)計了每種算法需評估的方案個數(shù)。從表3可以看出，基于社區(qū)劃分FU的貨位優(yōu)化算法僅需評估44個貨位擺放方案，時間耗費上小于其余算法，僅占基于遺傳算法評估時間的0.55%，占基于社區(qū)劃分Infomap的12.43%，占基于隨機方案的44%，占基于貪心方案的62.86%?；谏鐓^(qū)劃分FU的44個方案的行走總路徑均值比隨機100個方案的高31.98%，比基于貪心算法的高11.28%，比基于社區(qū)劃分Infomap的高10.22%，比基于遺傳算法迭代400輪后的最優(yōu)20個方案的高9.54%。在主要優(yōu)化目標為行走總路程時，基于社區(qū)劃分FU的貨位優(yōu)化算法與其它算法相比能更快剔除大量的劣質擺放方案，找出優(yōu)秀方案。

表4是5種優(yōu)化算法的最優(yōu)方案各項指標對比情況。基于社區(qū)劃分FU的貨位優(yōu)化算法最優(yōu)解的綜合指標優(yōu)于基于隨機最優(yōu)解28.61%，優(yōu)于基于遺傳算法最優(yōu)解14.55%，優(yōu)于基于社區(qū)劃分Infomap最優(yōu)解5.83%，優(yōu)于基于貪心算法最優(yōu)解5.06%；就行走總路徑而言，基于社區(qū)劃分FU的貨位優(yōu)化算法優(yōu)于基于隨機最優(yōu)解29.67%，優(yōu)于基于遺傳算法最優(yōu)解12.72%，優(yōu)于基于貪心算法最優(yōu)解9.34%，略高于基于社區(qū)劃分Infomap最優(yōu)解1.51%；基于社區(qū)劃分FU最優(yōu)解的堵塞指標優(yōu)于基于隨機最優(yōu)解和基于社區(qū)劃分Infomap的最優(yōu)解，但高于基于遺傳算法最優(yōu)解與基于貪心算法最優(yōu)解。顯然這是行走總路程與堵塞指標朝不同方向收斂導致的結果，只需調整綜合指標中相應的權重系數(shù)即可使得堵塞指標更小。

Table 3 Evaluation of the average solutions of different slotting optimization algorithms

Table 4 Evaluation of the optimal solutions of different slotting optimization algorithms

綜上，本文提出的基于社區(qū)劃分FU的貨位優(yōu)化算法與隨機貨位優(yōu)化算法、基于遺傳算法的貨位優(yōu)化算法及基于社區(qū)劃分Infomap的貨位優(yōu)化算法相比，其方案質量更好，評估時間也占據優(yōu)勢；與基于貪心算法的貨位優(yōu)化算法相比，不僅在速度與方案質量上有一定優(yōu)勢，還在控制關聯(lián)度的影響程度上有優(yōu)勢。因為基于貪心算法的貨位優(yōu)化算法根據密切度閾值控制熱銷商品周圍應該存放的關聯(lián)商品數(shù)，這使得它只能通過測試找出最優(yōu)解可能出現(xiàn)的密切度閾值區(qū)間，然后再以更細粒度搜尋最優(yōu)方案。與其相比，基于社區(qū)劃分FU的貨位優(yōu)化算法在主要目標為行走路徑，次要目標為緩解堵塞、減少工作人員數(shù)量時能夠更快地剔除大量劣質擺放方案，直接獲得多個優(yōu)秀方案。

6 結束語

倉儲優(yōu)化一直是倉儲發(fā)展的重要方向之一。本文根據實際問題需求，提出了基于社區(qū)劃分的貨位優(yōu)化算法以及多個評估指標，并通過實驗驗證了該算法可有效提高倉儲揀選效率，降低成本。

在后續(xù)工作中，可在以下方面繼續(xù)展開研究：(1)基于社區(qū)劃分的貨位優(yōu)化算法中的劃分步驟可由不同的劃分算法來完成，是否還有其它更高效的已有劃分算法以及能否根據問題背景設計更加高效的劃分算法還有待進一步研究；(2)本文貨位優(yōu)化算法主要針對人到貨系統(tǒng)，也可通過改進算法的某些步驟使其適用于基于AGV的貨到人智能倉儲系統(tǒng)，例如劃分閾值的上限、評估指標中的路徑計算等，具體改進方法及適用效果還需進一步研究。