李昆鵬, 劉騰博

(華中科技大學(xué) 管理學(xué)院,湖北 武漢 430074)

0 引言

近年來，隨著電子商務(wù)的發(fā)展以及移動(dòng)支付的普及，網(wǎng)絡(luò)購(gòu)物已經(jīng)成為人們生活中不可或缺的一部分。數(shù)據(jù)顯示，2019年“雙十一”購(gòu)物節(jié)天貓平臺(tái)24小時(shí)成交額達(dá)2684億元，訂單量也從2009年的26萬件增長(zhǎng)到了12.92億件，十年來增長(zhǎng)4970倍，巨大的訂單增長(zhǎng)量對(duì)電商企業(yè)物流系統(tǒng)提出了更高的要求。據(jù)統(tǒng)計(jì)，在傳統(tǒng)配送中心內(nèi)部，揀選作業(yè)成本占總成本的60%，訂單處理時(shí)間占比高達(dá)30%～40%。由此可見，訂單揀選已成為制約電商發(fā)展的物流瓶頸。亞馬遜在2012年斥資7.75億美元收購(gòu)Kiva Systems公司，其研發(fā)的Kiva系統(tǒng)可通過機(jī)器人搬運(yùn)貨架實(shí)現(xiàn)自動(dòng)化揀選作業(yè)，該系統(tǒng)為其節(jié)省運(yùn)營(yíng)費(fèi)用20%以上，且準(zhǔn)確率高達(dá)99.99%，這也激發(fā)了我國(guó)大型電商企業(yè)開始積極研發(fā)倉(cāng)儲(chǔ)機(jī)器人(AGV)系統(tǒng)，并將其應(yīng)用于訂單揀選作業(yè)，實(shí)現(xiàn)“由人取貨物”到“貨物送到人”的轉(zhuǎn)變。近兩年，我國(guó)AGV技術(shù)發(fā)展迅速，面對(duì)不斷趨于“多品種、小批量、高時(shí)效”的電商訂單揀選挑戰(zhàn)，如何對(duì)訂單合理分批，更好地發(fā)揮AGV在揀選效率、作業(yè)準(zhǔn)確率等方面的優(yōu)勢(shì)，已成為電商企業(yè)應(yīng)用“貨到人”系統(tǒng)進(jìn)一步提升揀選效率的新途徑。

在采用AGV的“貨到人”揀選系統(tǒng)中，主要流程如圖1中(a)所示。對(duì)于一定時(shí)間內(nèi)的訂單，首先根據(jù)商品需求和庫(kù)存確定需要搬運(yùn)的貨架，并將搬運(yùn)任務(wù)分配至AGV；然后AGV將貨架運(yùn)送至揀選站臺(tái)，由揀選人員從貨架上揀取商品并放入訂單對(duì)應(yīng)的周轉(zhuǎn)箱；最后AGV再將貨架運(yùn)回原位，該模式可極大提高揀選效率。隨著消費(fèi)者需求不斷趨于多樣化，每個(gè)訂單通常由多臺(tái)AGV搬運(yùn)多個(gè)貨架才能滿足，不僅浪費(fèi)倉(cāng)庫(kù)資源，而且AGV數(shù)量的增加還導(dǎo)致發(fā)生碰撞的可能性增大。如果能建立訂單與貨架之間的聯(lián)系，如圖1中(b)所示，將調(diào)用貨架相似度較高的訂單合并為一個(gè)批次揀選，則AGV搬運(yùn)貨架一次可供應(yīng)多個(gè)訂單需求。訂單合理分批不僅能夠提高AGV工作效率，而且貨架搬運(yùn)次數(shù)的減少可有效縮短作業(yè)完成時(shí)間?；诖?，本文以最小化AGV搬運(yùn)貨架次數(shù)為目標(biāo)，深入研究“貨到人”揀選系統(tǒng)的訂單分批問題。該問題不僅要考慮訂單的貨架選取方法，還要設(shè)計(jì)批次劃分標(biāo)準(zhǔn)，是一個(gè)十分復(fù)雜的NP-Hard問題，也是目前學(xué)術(shù)界和企業(yè)界關(guān)注較少但十分有必要優(yōu)化的環(huán)節(jié)。

圖1 “貨到人”揀選系統(tǒng)流程

訂單分批的概念早在1997年就由AcKerman[1]首次提出，目前在傳統(tǒng)“人到貨”揀選模式下關(guān)于訂單分批問題的研究較多。在行走距離方面，郜振華等[2]、王轉(zhuǎn)等[3]、Koch[4]等以揀選距離最短為目標(biāo)，分別采用螢火蟲分批算法、基于里程節(jié)約的方法、遺傳算法求解。在揀選時(shí)間方面，Henn等[5]以最小化總延遲時(shí)間為目標(biāo)提出變鄰域搜索算法；王旭坪等[6]考慮訂單平均服務(wù)時(shí)間最短構(gòu)建模型；Lenoble等[7]和于嵐等[8]以最小化訂單完成時(shí)間為目標(biāo)建立模型。在訂單相似度上，李詩(shī)珍等[9]提出了基于儲(chǔ)位、巷道及面積的相似系數(shù)計(jì)算方法；羅曉萌等[10]將通道重合數(shù)作為訂單相似系數(shù)。Gademann等[11]通過復(fù)雜度分析證明了訂單分批問題屬于NP-Hard問題。

近年來，隨著AGV技術(shù)的不斷成熟，國(guó)內(nèi)外學(xué)者對(duì)“貨到人”揀選系統(tǒng)的訂單分批問題開展了初步研究。范繼東[12]以貨架搬運(yùn)次數(shù)最少為目標(biāo)設(shè)計(jì)基于k-means聚類算法的訂單分批算法；李珍萍等[13]以人工揀貨成本和AGV搬運(yùn)成本之和最小為目標(biāo)建立模型。部分學(xué)者將訂單分批問題與其他問題相結(jié)合進(jìn)行探索。Xiang等[14]和李曉杰[15]結(jié)合儲(chǔ)位分配問題，前者以最大化訂單關(guān)聯(lián)度和最小化貨架訪問次數(shù)為目標(biāo)構(gòu)建模型；后者以減少AGV往返運(yùn)送貨架次數(shù)為目標(biāo)設(shè)計(jì)揀選策略。Boysen等[16]和吳穎穎等[17]考慮揀選順序，前者優(yōu)化目標(biāo)為最小化AGV搬運(yùn)貨架次數(shù)；后者為最大化單揀選站臺(tái)訂單耦合因子之和。Ardjmand[18]研究了訂單分配、訂單批處理及揀選路徑問題。

綜上所述，國(guó)內(nèi)外學(xué)者主要研究了傳統(tǒng)“人到貨”揀選模式下的訂單分批問題，而采用AGV的“貨到人”揀選系統(tǒng)與其具有本質(zhì)區(qū)別，很多研究成果和算法不能直接應(yīng)用。目前關(guān)于“貨到人”揀選系統(tǒng)訂單分批問題的研究較少，已有文獻(xiàn)多在訂單與貨架對(duì)應(yīng)關(guān)系已知的情況下構(gòu)建數(shù)學(xué)模型并設(shè)計(jì)啟發(fā)式算法求解，且多假設(shè)每種商品只能存儲(chǔ)在一個(gè)貨架上。而在實(shí)際中，電商訂單信息通常包括所需商品及數(shù)量，且商品庫(kù)存在多個(gè)貨架上均有分布，應(yīng)首先根據(jù)訂單需求選取供應(yīng)貨架。鑒于此，本文在構(gòu)造模型時(shí)考慮訂單需求與商品庫(kù)存之間的聯(lián)系，在設(shè)計(jì)算法時(shí)定義貨架相似度作為訂單選取貨架的評(píng)價(jià)指標(biāo)，最終形成一套能夠最大化減少AGV搬運(yùn)貨架次數(shù)的訂單分批方案。

基于以上分析，本文考慮在訂單需求多樣化、商品庫(kù)存多貨架分布、訂單與貨架供需關(guān)系未知等更符合實(shí)際的背景下研究訂單分批問題。首先，構(gòu)建以最小化AGV搬運(yùn)貨架次數(shù)為目標(biāo)的整數(shù)規(guī)劃模型；然后，設(shè)計(jì)兩階段訂單分批啟發(fā)式算法，并提出兩種方法創(chuàng)建新批次；最后通過實(shí)驗(yàn)驗(yàn)證本文模型和算法的有效性，分析兩種批次創(chuàng)建方法的適用性，采用靈敏度分析探討周轉(zhuǎn)箱的合理配置數(shù)量。實(shí)驗(yàn)證明本文提出的兩階段算法能夠在短時(shí)間內(nèi)得到較優(yōu)分批方案，在實(shí)際應(yīng)用中具有一定的可行性。研究成果不僅可以擴(kuò)展訂單分批問題的現(xiàn)有理論，而且能夠?yàn)槠髽I(yè)采用AGV進(jìn)一步提升揀選效率提供新的思路。

1 考慮貨架搬運(yùn)次數(shù)訂單分批模型

1.1 問題描述及假設(shè)

本文研究“貨到人”揀選系統(tǒng)的訂單分批問題，描述如下：在采用AGV的智能倉(cāng)庫(kù)中有t個(gè)揀選站臺(tái)、r個(gè)貨架，共存儲(chǔ)h種商品。每個(gè)貨架有多個(gè)儲(chǔ)位，每個(gè)儲(chǔ)位存放一種商品，每種商品存放在多個(gè)貨架上。每個(gè)揀選站臺(tái)配備d個(gè)周轉(zhuǎn)箱，每個(gè)周轉(zhuǎn)箱對(duì)應(yīng)一個(gè)訂單。某段時(shí)間內(nèi)共接收到n個(gè)需求已知的訂單揀選任務(wù)，如何對(duì)這些訂單進(jìn)行分批以實(shí)現(xiàn)批次揀選作業(yè)。在“貨到人”揀選系統(tǒng)中，作業(yè)完成時(shí)間主要取決于AGV搬運(yùn)貨架的行走時(shí)間，若能調(diào)用較少貨架滿足所有訂單的商品需求，則可最大程度減少作業(yè)完成時(shí)間?；诖耍疚囊宰钚』疉GV搬運(yùn)貨架次數(shù)為目標(biāo)，決策多訂單的批次分配及批次與貨架的服務(wù)關(guān)系，并計(jì)算批次的商品需求量及貨架的供應(yīng)量。為方便建模，考慮以下假設(shè)：

①AGV電量充足，且數(shù)量足夠多；②商品庫(kù)存量充足能夠滿足訂單集合需求；③在給定的時(shí)間段內(nèi)每個(gè)貨架只能被AGV搬運(yùn)一次；④同一訂單不能被分配至多個(gè)批次；⑤每個(gè)揀選站臺(tái)完成一個(gè)批次的揀選作業(yè)，即批次數(shù)等于揀選站臺(tái)數(shù)t，批次的最大訂單數(shù)等于周轉(zhuǎn)箱數(shù)d。

1.2 模型建立

根據(jù)問題描述，符號(hào)及變量定義如表1所示，數(shù)學(xué)模型構(gòu)建如下:

表1 模型符號(hào)變量定義

(14)

目標(biāo)函數(shù)(1)表示最小化AGV搬運(yùn)貨架次數(shù)；式(2)保證每個(gè)訂單均被分配至批次；式(3)保證每個(gè)批次均會(huì)被貨架服務(wù)；式(4)表示每個(gè)批次至少包含一個(gè)訂單；式(5)為批次的最大訂單數(shù)限制；式(6)表示每個(gè)貨架最多服務(wù)一個(gè)批次；式(7)表示批次需求等于其所包含訂單的商品需求量之和；式(8)表示批次需求可被多個(gè)貨架供應(yīng)；式(9)表示貨架的供應(yīng)量不能超過其存儲(chǔ)量；式(10)保證批次的商品需求都能被滿足；式(11)表示貨架是否被搬運(yùn)取決于其是否供應(yīng)批次商品需求；式(12)表示0-1變量；式(13)、(14)表示整數(shù)變量。

2 基于貨架相似度的兩階段訂單分批算法

訂單分批是將訂單集合劃分為包含一個(gè)或多個(gè)訂單的批次進(jìn)行揀選，本文提出了基于貨架相似度的兩階段訂單分批算法SSTOBA(Shelf Similarity based Two-phase Order Batching Algorithm)，如圖2所示。第一階段，包括新批次創(chuàng)建和訂單加入批次兩個(gè)步驟：(1)采用兩種方法創(chuàng)建新批次。法一：計(jì)算兩兩訂單的貨架相似度并將相似度最大的合并作為新批次，若最大相似度為0，則將訂單各自作為揀選批次；法二：計(jì)算每個(gè)訂單的所需貨架數(shù)并將數(shù)值最大的作為新批次。(2)訂單加入批次。計(jì)算訂單與當(dāng)前批次的貨架相似度并將相似度最大的訂單加入，直至訂單數(shù)達(dá)到周轉(zhuǎn)箱數(shù)，在此過程中若最大相似度為0，則將當(dāng)前批次作為揀選批次。通過以上兩個(gè)步驟將所有訂單分配至批次。然后，遍歷每個(gè)訂單作為第一個(gè)初始批次得到各自分批方案，將較優(yōu)方案作為初始解。第二階段，設(shè)計(jì)局部搜索算法改進(jìn)初始解，通過兩種移除算子和修復(fù)算子不斷更新當(dāng)前解，得到最優(yōu)解或近似最優(yōu)解。

圖2 求解框架

為建立訂單與貨架之間的供需匹配關(guān)系，在算法中考慮兩種規(guī)則為訂單選取貨架，然后定義貨架相似度函數(shù)作為評(píng)價(jià)指標(biāo)。本節(jié)先對(duì)貨架選取規(guī)則和相似度函數(shù)進(jìn)行說明，在此基礎(chǔ)上介紹算法兩個(gè)階段的具體步驟。

2.1 兩種訂單選取貨架規(guī)則

電商訂單所需商品通常來自多個(gè)貨架，同種商品在多個(gè)貨架存儲(chǔ)，因此每個(gè)訂單對(duì)應(yīng)多種貨架組合。在實(shí)際中訂單與貨架的匹配關(guān)系未知，需首先對(duì)貨架量化作為選取依據(jù)。本文結(jié)合訂單需求量和商品庫(kù)存量的關(guān)系提出兩種貨架量化標(biāo)準(zhǔn)。其中，Om表示訂單需求商品m的數(shù)量，Skm表示貨架存儲(chǔ)商品m的數(shù)量，具體描述如下。兩種標(biāo)準(zhǔn)為貨架存k儲(chǔ)或可滿足訂單需求商品的類型數(shù)，分別表示為Mk和Nk。當(dāng)訂單對(duì)商品m有需求，若貨架k存儲(chǔ)商品m，即Om>0,Skm>0，則Mk值加一；若貨架存儲(chǔ)商品且?guī)齑媪繚M足需求量，即Om>0,Skm>Dm，則Nk值加一，檢測(cè)所有商品需求得到貨架k的Mk值和Nk值。

為得到較優(yōu)組合，在對(duì)貨架量化基礎(chǔ)上，提出兩種貨架選取規(guī)則，區(qū)別在于Mk和Nk的計(jì)算次序不同，如圖3所示。對(duì)于貨架集合S={1,…,r}。首先，根據(jù)訂單需求Om，計(jì)算每個(gè)貨架的Mk值(Nk值)并選擇最大值貨架。若存在h個(gè)貨架具有最大值，則比較貨架的Nk值(Mk值)并選擇最大值貨架。若仍存在t個(gè)貨架兩數(shù)值均最大，則從中隨機(jī)選擇貨架。然后，使該貨架盡可能滿足訂單需求，更新Om和Skm。最后，按照兩種規(guī)則不斷選擇供應(yīng)貨架，直至訂單的所有商品需求均被滿足，由此得到訂單的兩種供應(yīng)貨架組合。

圖3 兩種貨架選取規(guī)則

2.2 貨架相似度函數(shù)

(15)

(16)

(17)

2.3 兩階段算法步驟

2.3.1 第一階段生成初始解

本文算法基于訂單選取貨架規(guī)則和貨架相似度函數(shù)，在第一階段，根據(jù)批次中是否已有訂單進(jìn)行新批次創(chuàng)建及訂單加入批次，提出兩種方法創(chuàng)建新批次，①兩訂單貨架相似度最大；②單訂單所需貨架數(shù)最多，分別表述為法一和法二。為擴(kuò)大搜索空間，遍歷訂單集合，各訂單依次作為第一個(gè)批次，得到基于每個(gè)訂單的分批方案。由于訂單在兩種規(guī)則下選取貨架對(duì)應(yīng)兩種貨架組合，最終得到2n種分批方案。鑒于每個(gè)方案均建立在第一個(gè)批次已有訂單的基礎(chǔ)上，為更清楚展現(xiàn)算法邏輯，描述順序?yàn)橛唵渭尤肱魏托屡蝿?chuàng)建，主要流程如圖4所示，具體步驟如下。

(1)訂單加入批次

Step2若批次中訂單數(shù)小于周轉(zhuǎn)箱數(shù)，返回Step1，繼續(xù)加入訂單；若已達(dá)到周轉(zhuǎn)箱數(shù)，則當(dāng)前批次為揀選批次，刪除其供應(yīng)貨架，執(zhí)行Step3。

Step3若集合中訂單數(shù)大于1，則生成新的空批次，執(zhí)行Step4采用兩種方法創(chuàng)建新批次；若訂單數(shù)為1，則該訂單為揀選批次，終止算法。

(2)新批次創(chuàng)建

Step4(法二) 當(dāng)批次為空，按所需貨架數(shù)對(duì)集合中訂單排序，將所需貨架數(shù)最多的訂單作為新批次，并將其從集合中刪除，返回Step1。

同理得到O={1,…,n}中每個(gè)訂單的兩種貨架組合分別作為第一個(gè)批次的分批方案，共得到2n種訂單分批方案，計(jì)算每個(gè)方案中AGV完成所有訂單揀選任務(wù)的搬運(yùn)貨架次數(shù)，將搬運(yùn)次數(shù)最少的作為第一階段初始解s0。

2.3.2 第二階段局部搜索算法改進(jìn)初始解

基于第一階段所得初始解，為提高算法尋優(yōu)能力以獲得高質(zhì)量的解，在第二階段加入局部搜索算法，包括破環(huán)與修復(fù)兩個(gè)步驟，通過兩種移除算子和修復(fù)算子改進(jìn)當(dāng)前解，主要步驟如下。

兩種移除算子：①移除批次訂單。在當(dāng)前解中，隨機(jī)選擇20%的批次，從每個(gè)批次中隨機(jī)移除一個(gè)訂單，得到破壞解sd。將移除的訂單存入未分批集合R，對(duì)應(yīng)貨架存入可用貨架集合S；②移除訂單貨架。在當(dāng)前解中，隨機(jī)選擇30%的貨架移除，存入可用貨架集合S，同時(shí)將對(duì)應(yīng)訂單刪除，存入未分批集合R，得到破環(huán)解sd。

修復(fù)算子：基于貨架集合S，對(duì)訂單集合R，計(jì)算各訂單與破壞解sd中所有未飽和批次的貨架相似度(訂單數(shù)未達(dá)到周轉(zhuǎn)箱數(shù))，將相似度最大的訂單插入，并將其從集合R中刪除，同時(shí)將其所需貨架從集合S中刪除。繼續(xù)執(zhí)行插入，直到集合R中的訂單均分配至批次，得到修復(fù)解se。

Step1參數(shù)初始化。輸入第一階段初始解s0，初始目標(biāo)函數(shù)值為AGV搬運(yùn)貨架次數(shù)r0；初始化當(dāng)前解rc和當(dāng)前目標(biāo)函數(shù)值sc，使sc=s0，rc=r0；設(shè)置l=0，L=0，當(dāng)前解最大未改善次數(shù)lmax，算法最大迭代次數(shù)Lmax。

Step2若L

Step3若l

Step4通過移除算子得到破環(huán)解sd，然后采用修復(fù)算子得到修復(fù)解se。計(jì)算修復(fù)解se的貨架搬運(yùn)次數(shù)，作為其目標(biāo)函數(shù)值re，如果re

Step5輸出近似最優(yōu)解s*=sc，近似最優(yōu)目標(biāo)函數(shù)值r*=rc。

3 仿真實(shí)驗(yàn)及數(shù)據(jù)測(cè)試

本文所有測(cè)試在Intel Core i5 2.2GHz CPU with 4GB RAM的計(jì)算機(jī)上運(yùn)行，采用CPLEX作為模型求解器，啟發(fā)式算法采用C++編碼，實(shí)驗(yàn)部分設(shè)置最大迭代次數(shù)為100。

3.1 小規(guī)模仿真實(shí)驗(yàn)

為驗(yàn)證本文數(shù)學(xué)模型和算法中兩種批次創(chuàng)建方法的有效性，采用小規(guī)模算例對(duì)比分析CPLEX與算法求解結(jié)果。為使算法所得批次數(shù)等于揀選站臺(tái)數(shù)，以不影響貨架搬運(yùn)次數(shù)為前提改進(jìn)算法所得方案，在符合周轉(zhuǎn)箱數(shù)范圍內(nèi)將包含訂單數(shù)較少的批次合并。本文考慮訂單需求多樣化、商品庫(kù)存多貨架分布的特點(diǎn)隨機(jī)生成數(shù)據(jù)，對(duì)5組不同規(guī)模的算例測(cè)試。其中，總商品類型數(shù)為8，揀選站臺(tái)數(shù)為5，周轉(zhuǎn)箱數(shù)為4。

結(jié)果如表2所示，以AGV搬運(yùn)貨架次數(shù)(Out)為衡量指標(biāo)。M1、M2分別表示第一階段新批次創(chuàng)建的法一和法二；CS1、CS2分別表示最優(yōu)解與法一、法二求解所得百分差，等于“(SSTOBA-CPLEX)/SSTOBA*100%”；time1、time2、time3分別表示CPLEX、法一、法二的求解時(shí)間。

表2 小規(guī)模實(shí)驗(yàn)結(jié)果

圖5 三種方式下貨架搬運(yùn)次數(shù)對(duì)比圖

結(jié)果表明，(1)對(duì)于貨架搬運(yùn)次數(shù)，如圖5所示，在不同算例規(guī)模下，CPLEX求解模型可最大程度減少搬運(yùn)次數(shù)。在兩階段算法中，采用不同方法創(chuàng)建新批次對(duì)求解結(jié)果有所影響，法一比法二能夠獲得更少的搬運(yùn)次數(shù)。此外，對(duì)于表現(xiàn)較好的法一，搬運(yùn)次數(shù)與最優(yōu)解僅相差1～2次，平均相差7.4%，且在有些情況下能夠獲得最優(yōu)解，說明算法具有合理性和有效性。(2)在求解時(shí)間上，如圖6所示，當(dāng)訂單數(shù)由14、貨架數(shù)由40不斷增加時(shí)，模型求解時(shí)間呈指數(shù)型增長(zhǎng)，由于電商配送中心對(duì)時(shí)間要求極高，CPLEX在求解大規(guī)模問題時(shí)耗時(shí)較長(zhǎng)，因此很有必要探索高效的啟發(fā)式算法，而本文算法能夠在短時(shí)間內(nèi)獲得AGV搬運(yùn)貨架次數(shù)較少的訂單分批方案，具有很好的實(shí)用性。由此可見，本文建立的數(shù)學(xué)模型是正確且有效的，兩階段算法中的法一能在短時(shí)間內(nèi)獲得最優(yōu)解或近似最優(yōu)解。

3.2 大規(guī)模仿真實(shí)驗(yàn)

為分析本文在第一階段提出的兩種批次創(chuàng)建方法的適用性，以及局部搜索算法對(duì)初始解的改進(jìn)效果，本節(jié)采用兩階段算法對(duì)更大規(guī)模算例測(cè)試。在衡量分批效果上，選取AGV搬運(yùn)貨架次數(shù)(Out)和分批后的批次數(shù)(Batch)兩個(gè)指標(biāo)評(píng)價(jià)。實(shí)驗(yàn)結(jié)果如表3所示，其中，P1、P2分別表示第一階段和第二階段；P1O、P2O分別表示在第一階段和第二階段法一與法二在搬運(yùn)次數(shù)上的差異，計(jì)算分別為“(P1 M1-P1 M2)/P1 M2*100%”和“(P2 M1-P2 M2)/P2 M2*100%”，負(fù)號(hào)表示相對(duì)減少；M1O、M2O表示法一和法二在兩個(gè)階段結(jié)果的百分差，計(jì)算分別為“(P1 M1-P2 M1)/P2 M1*100%”和“(P1 M2-P2 M2)/P2 M2*100%”；BGap表示法一與法二在批次數(shù)上的差異，等于“(M1-M2)/M2*100%”。

表3 大規(guī)模實(shí)驗(yàn)結(jié)果

由結(jié)果可知，(1)對(duì)于貨架搬運(yùn)次數(shù)，如圖7所示，由P1O、P2O可知，法一與法二的搬運(yùn)次數(shù)相差較大，在第一階段法一比法二平均減少40.3%，在第二階段平均減少38.5%；由M1O、M2O可知，采用局部搜索算法能在一定程度上改善初始解，與第一階段相比，法一與法二分別平均節(jié)約搬運(yùn)次數(shù)23.4%和32.4%。法二改進(jìn)后的解仍比法一初始解的搬運(yùn)次數(shù)多，主要原因是，在第一階段，法一將貨架相似度最大的兩個(gè)訂單合并作為新批次，更能節(jié)約搬運(yùn)次數(shù)，初始解與近似最優(yōu)解差距較小。(2)對(duì)于批次數(shù)，如圖8所示，法一得到的批次數(shù)較多，由BGap可知法一比法二平均增加42.9%，最大差距為66.7%。主要原因是，法一考慮當(dāng)不存在兩訂單所需貨架相同時(shí)將訂單各自作為揀選批次，故出現(xiàn)批次中僅包含一個(gè)訂單的情況較多導(dǎo)致批次數(shù)增加。綜上，采用法一的兩階段算法能夠獲得更少的搬運(yùn)次數(shù)，從而有效縮短AGV搬運(yùn)貨架行走時(shí)間。

圖7 兩種方法不同階段貨架搬運(yùn)次數(shù)差異圖

圖8 兩種方法批次數(shù)差異圖

3.3 周轉(zhuǎn)箱數(shù)量靈敏度分析

在采用“貨到人”揀選模式的倉(cāng)庫(kù)中，每個(gè)揀選站臺(tái)配備一定數(shù)量周轉(zhuǎn)箱，分別對(duì)應(yīng)一個(gè)訂單。周轉(zhuǎn)箱作為物流容器，數(shù)量過多將會(huì)占用空間且增加采購(gòu)成本，因此，本節(jié)基于兩階段算法探討周轉(zhuǎn)箱的合理配置數(shù)量。隨機(jī)生成一組中等規(guī)模算例：總商品類型數(shù)為20、訂單數(shù)為30、貨架數(shù)為60。結(jié)果如表4所示，其中，time1、time2分別表示法一和法二的求解時(shí)間；P2O、BGap分別表示法一與法二在貨架搬運(yùn)次數(shù)、批次數(shù)上的差異，負(fù)號(hào)表示相對(duì)減少。計(jì)算分別為“(P2 M1-P2 M2)/P2 M2*100%”和“(M1- M2)/M2*100%”。

表4 周轉(zhuǎn)箱數(shù)量靈敏度分析

由結(jié)果可知，隨著周轉(zhuǎn)箱數(shù)的增加，兩種方法在貨架搬運(yùn)次數(shù)和批次數(shù)上基本呈現(xiàn)由下降到平穩(wěn)波動(dòng)的變化趨勢(shì)，如圖9和圖10所示。主要原因是，訂單加入批次的停止條件包括兩個(gè)，訂單與批次不存在所需貨架相同以及批次訂單數(shù)達(dá)到周轉(zhuǎn)箱數(shù)。(1)當(dāng)周轉(zhuǎn)箱數(shù)較少時(shí)，即使存在訂單與批次的所需貨架相同，由于最大訂單數(shù)限制可能無法繼續(xù)加入批次。(2)當(dāng)周轉(zhuǎn)箱數(shù)由4增加至10時(shí)，批次可包含訂單增多，將相似度最大的訂單加入批次能有效減少搬運(yùn)次數(shù)，同時(shí)，批次中訂單數(shù)的增多導(dǎo)致總批次數(shù)減少。(3)當(dāng)由10逐步增加時(shí)，批次最大訂單數(shù)的限制作用不明顯，訂單停止加入批次主要是由于不存在所需貨架相同，此時(shí)周轉(zhuǎn)箱數(shù)的增加對(duì)搬運(yùn)次數(shù)和批次數(shù)的影響很小。由此可知，在中等規(guī)模下合適的周轉(zhuǎn)箱數(shù)為9～10個(gè)，此時(shí)貨架搬運(yùn)次數(shù)較少且周轉(zhuǎn)箱利用率較高。綜上，通過對(duì)周轉(zhuǎn)箱數(shù)量進(jìn)行靈敏度分析，可為不同倉(cāng)庫(kù)規(guī)模的周轉(zhuǎn)箱數(shù)量配置提供參考，達(dá)到合理利用倉(cāng)庫(kù)資源、提高企業(yè)經(jīng)濟(jì)效益的目的。

圖9 不同周轉(zhuǎn)箱規(guī)模下貨架搬運(yùn)次數(shù)變化圖

圖10 不同周轉(zhuǎn)箱規(guī)模下批次數(shù)變化圖

4 結(jié)論

本文研究了“貨到人”揀選系統(tǒng)的電商訂單分批問題，考慮訂單需求多樣化、商品庫(kù)存多貨架存儲(chǔ)以及訂單與貨架匹配關(guān)系未知等實(shí)際因素，以最小化AGV搬運(yùn)貨架次數(shù)為目標(biāo)構(gòu)建數(shù)學(xué)模型，并設(shè)計(jì)基于貨架相似度的訂單分批算法求解。最后通過實(shí)驗(yàn)驗(yàn)證了本文模型和算法的有效性和實(shí)用性，實(shí)驗(yàn)結(jié)果表明，(1)采用法一基于兩訂單貨架相似度最大的兩階段算法能獲得更少的搬運(yùn)次數(shù)，在有些情況下能夠獲得最優(yōu)解。(2)本文算法能夠在具有110個(gè)貨架、28種商品的倉(cāng)庫(kù)中對(duì)55個(gè)訂單分批處理，在第二階段，法一和法二比初始解分別平均減少搬運(yùn)次數(shù)23.4%和32.4%。(3)在中等倉(cāng)庫(kù)規(guī)模下周轉(zhuǎn)箱合理配置數(shù)量為9～10個(gè)。綜上，本研究不僅擴(kuò)展了“貨到人”揀選系統(tǒng)中訂單分批問題的相關(guān)理論，而且可為企業(yè)通過訂單分批進(jìn)一步提高AGV揀選效率提供參考。此外，考慮多種實(shí)際因素對(duì)智能倉(cāng)庫(kù)建設(shè)具有重要理論價(jià)值和現(xiàn)實(shí)意義。未來的研究中，可以考慮將AGV路徑規(guī)劃與訂單分批相結(jié)合進(jìn)行深入探討，此外，還會(huì)考慮在線訂單分批問題。