姚文斌 朱子欣

(浙江經(jīng)濟(jì)職業(yè)技術(shù)學(xué)院 浙江 杭州 310018) 2(清華大學(xué) 廣東 深圳 518055)

0 引 言

物流業(yè)是國民經(jīng)濟(jì)的重要組成部分,現(xiàn)代物流的發(fā)展有利于跨產(chǎn)業(yè)整合資源,優(yōu)化資源配置,提高產(chǎn)品供給時(shí)效和市場響應(yīng)速度。結(jié)合人工智能、云計(jì)算、大數(shù)據(jù)、物聯(lián)網(wǎng)等信息技術(shù)的有效應(yīng)用,“互聯(lián)網(wǎng)+物流”探索愈發(fā)成熟,與其他產(chǎn)業(yè)的融合能動和資源整合效能正日漸增強(qiáng)。2014年,亞馬遜使用的Kiva系統(tǒng)作業(yè)效率較傳統(tǒng)物流作業(yè)提升2～4倍,機(jī)器人時(shí)速可達(dá)48.27 km,可抬起約340 kg重的貨物,準(zhǔn)確率達(dá)到99.99%。據(jù)報(bào)道,國內(nèi)智能倉儲機(jī)器人產(chǎn)品已經(jīng)在電商倉庫、汽車制造商倉庫等場景中應(yīng)用。但是,關(guān)于如何提高機(jī)器人在訂單揀選時(shí)的作業(yè)效率,這方面的研究還非常少,急需研究相關(guān)的算法。

本文以可移動貨架式倉庫為背景,研究該場景下基于“貨到人”揀選模式的訂單揀選排程問題。與傳統(tǒng)的“人到貨”模式相比,“貨到人”模式一方面可以把勞動力從繁重的倉庫行走、搬運(yùn)中解放出來,從而有效減少對人工的依賴,另一方面還有利于通過人工智能算法指揮調(diào)度機(jī)器人來提高工作效率。由于各待揀選訂單的處理順序和各貨架到達(dá)揀選臺的順序不同,在不同的倉庫布局、儲位分配策略下,整批全部訂單完成揀選所需要的貨架移動的次數(shù)也有差異。本文以單揀選臺為背景,設(shè)置模型的假設(shè)條件,建立訂單處理的整數(shù)規(guī)劃模型,目標(biāo)函數(shù)為最小化訂單批次完成揀選時(shí)的貨架搬運(yùn)次數(shù),用數(shù)學(xué)規(guī)劃求解器軟件CPLEX12.8求得小規(guī)模算例下的精確解。并設(shè)計(jì)了三種啟發(fā)式算法,分別是確定訂單處理次序的變鄰域搜索算法(Variable Neighborhood Search algorithm,VNS)VNS-OS、確定貨架到達(dá)次序的算法VNS-RS和交替求解訂單和貨架次序的算法AH,可求解較大規(guī)模的算例,并對計(jì)算結(jié)果進(jìn)行分析,形成結(jié)論。

1 研究背景

1.1 貨到人訂單揀選模式

相對于傳統(tǒng)人到貨模式,貨到人模式指揀貨員不動,待揀選物品存儲在托盤或箱子等存儲設(shè)備中,由自動化輸送系統(tǒng)從貯存區(qū)運(yùn)送到揀選區(qū),揀貨員根據(jù)電子標(biāo)簽的提示,從存儲設(shè)備中揀選出貨物放入訂單箱中。近年來,機(jī)器人移動履約系統(tǒng)(Robotic Mobile Fulfillment System ,RMFS)這種新型貨到人訂單揀選系統(tǒng),逐漸進(jìn)入大眾視野。它由Kiva systems、Swisslog等公司推向市場,并于2014年開始被亞馬遜應(yīng)用于倉庫,適用于需求波動明顯的多種中小件商品的電商配送中心。RMFS系統(tǒng)的前期投入費(fèi)用高昂,涉及倉儲策略復(fù)雜,且目前在商超、醫(yī)藥、化妝品、3C等應(yīng)用場景下的揀選效率提升效果不明顯,技術(shù)落地有一定難度。

RMFS系統(tǒng)的整體優(yōu)化目標(biāo)是最小化人力費(fèi)用和設(shè)備支出,涉及儲物貨架選擇、貨架儲位分配、訂單分配、補(bǔ)貨分配和機(jī)器人分配等問題。Yuan等[1]建立開放排隊(duì)模型,研究RMFS系統(tǒng)的性能。Boysen等[2]提出集束搜索啟發(fā)式算法,優(yōu)化小規(guī)模訂單和待揀選貨架的排序,以減少所需機(jī)器人數(shù)量。Yuan等[3]構(gòu)建排隊(duì)網(wǎng)絡(luò)模型,通過數(shù)值分析計(jì)算訂單揀選時(shí)間來評估系統(tǒng)性能,得到機(jī)器人的最佳數(shù)量和速度。Lamballais等[4]建立單隊(duì)和多隊(duì)訂單的排隊(duì)網(wǎng)絡(luò)模型,評估RMFS系統(tǒng)下不同的倉庫布局和機(jī)器人分區(qū)策略。Zou等[5]研究RMFS系統(tǒng)的電池管理問題,建立半開放排隊(duì)網(wǎng)絡(luò)(SOQN)來評估系統(tǒng)性能。Kumar等[6]研究RMFS系統(tǒng)的路徑規(guī)劃問題,設(shè)計(jì)多種倉庫布局下無碰撞路徑的算法。Roy等[7]基于多級封閉排隊(duì)網(wǎng)絡(luò)模型,研究RMFS系統(tǒng)的存儲區(qū)域的揀貨和補(bǔ)貨流程。Lamballais等[8]引入排隊(duì)模型,設(shè)計(jì)優(yōu)化每個存儲單位對應(yīng)的貨架數(shù)、揀選站與補(bǔ)貨點(diǎn)數(shù)量比和各貨架的補(bǔ)貨點(diǎn)的算法?，F(xiàn)有關(guān)于貨到人訂單揀選的研究大多是從倉庫布局設(shè)計(jì)或者局部運(yùn)作策略的角度對揀選系統(tǒng)的效率進(jìn)行評估,但是這些研究不能給出操作層面的訂單揀選計(jì)劃,即訂單作業(yè)順序和貨架的供應(yīng)順序。雖然文獻(xiàn)[2]研究了作業(yè)層的訂單揀選計(jì)劃問題,但是其采用的是集束搜索啟發(fā)式算法,這種算法受集束寬度參數(shù)的影響較大,而本文則提出一種可變鄰域搜索算法,這種元啟發(fā)式算法已在很多倉庫作業(yè)問題研究中被證明有效。

1.2 訂單排序問題

目前,國內(nèi)外圍繞優(yōu)化訂單排序的研究較少,多數(shù)基于傳統(tǒng)人到貨揀選模式,且多與訂單分批、路徑規(guī)劃等策略同時(shí)進(jìn)行研究。Zhang等[9]圍繞在線訂單批處理和排序問題,以最小化周轉(zhuǎn)時(shí)間為目標(biāo),討論揀貨員數(shù)量對系統(tǒng)揀選效率的影響。Boysen等[10]研究移動貨架倉庫系統(tǒng)的訂單揀選排序問題,討論開放過道數(shù)量對揀選作業(yè)的影響,目標(biāo)是提高空間利用率和減少揀選人力消耗。Scholz等[11]考慮訂單到期日,提出變鄰域下降算法,以最小化系統(tǒng)總延遲為目標(biāo),求解訂單分批、批次分配及排序、路徑規(guī)劃的整合優(yōu)化策略。Boysen等[12]研究電商倉庫的自動分揀問題,提出兩階段基于動態(tài)規(guī)劃的訂單處理算法,目標(biāo)是最小化釋放順序中的訂單分布。Chen等[13]研究考慮客戶訂單延遲的訂單組批、排序和路徑規(guī)劃問題,建立非線性混合整數(shù)規(guī)劃模型,提出了混合編碼遺傳算法和蟻群優(yōu)化相結(jié)合的算法。

1.3 儲位分配問題

儲位分配問題研究如何將入庫貨物分配到倉儲區(qū)的貨位上,優(yōu)化儲位分配可以有效縮短揀貨作業(yè)時(shí)長,降低物料搬運(yùn)成本,提高空間利用率。目前,基于人到貨揀選模式的儲位分配問題的研究成果較多,但不能直接應(yīng)用于貨到人模式下。Pan等[14]研究多揀選員pick-and-pass系統(tǒng)的儲位分配問題,提出以減少缺貨和平衡各揀選區(qū)工作量為目標(biāo)的啟發(fā)式算法。Guo等[15]研究在考慮儲貨區(qū)空間消耗的單位裝載倉庫下,對比叉車在單指令模式下隨機(jī)、全周轉(zhuǎn)率和基于類的三種存儲策略對揀貨走行距離的影響。

1.4 任務(wù)調(diào)度問題

倉庫管理中的任務(wù)調(diào)度問題主要包括機(jī)器人任務(wù)分配、訂單任務(wù)分配、補(bǔ)貨任務(wù)分配等,目的是提高系統(tǒng)揀選效率,平衡任務(wù)負(fù)載。Elango 等[16]旨在解決RMFS系統(tǒng)的多機(jī)器人任務(wù)分配問題,用k-means算法實(shí)現(xiàn)將任務(wù)聚類、計(jì)算機(jī)器人走行成本和機(jī)器人分配,實(shí)現(xiàn)最小化多機(jī)器人走行距離和均衡工作負(fù)荷的目標(biāo)。Zhou等[17]針對智能倉庫的多機(jī)器人任務(wù)分配問題,提出以最小化走行距離和平衡工作負(fù)載為目標(biāo)的平衡啟發(fā)式機(jī)制。

1.5 變鄰域搜索算法

變鄰域搜索算法(VNS)是一種求解組合優(yōu)化和全局優(yōu)化問題的元啟發(fā)式算法,基本思想是在下降階段系統(tǒng)地改變鄰域以找到局部最優(yōu)解,在擾動階段跳出相應(yīng)谷[18]。目前,應(yīng)用VNS算法求解倉儲管理問題的文獻(xiàn)數(shù)量不多,且主要基于人到貨的揀選場景。Menendez等[19]討論人到貨揀選模式下訂單的批處理及排序問題,提出變鄰域搜索算法,目標(biāo)是最小化訂單的延誤懲罰成本。Yang 等[20]研究共享存儲策略下多載具自動化存取系統(tǒng)的儲位分配和存儲檢索調(diào)度的聯(lián)合優(yōu)化問題,允許檢索操作產(chǎn)生的空位重用,提出求解大規(guī)模算例的變鄰域搜索算法。Menendez等[21]圍繞人到貨揀選模式下最小-最大訂單批處理問題,提出并行變鄰域搜索算法,目標(biāo)是最小化所有訂單批次的最大揀選時(shí)間。

綜上所述,現(xiàn)有的訂單排序、儲位分配、任務(wù)調(diào)度等方面的研究,雖然與本文有一定的重疊,但并不是針對“貨到人”這一應(yīng)用場景的,因而問題區(qū)別較大;同時(shí),針對“貨到人”場景,缺乏適用于操作層的訂單揀選算法,因此,本文對這一問題開展研究。

2 模型建立

2.1 符號說明

模型的符號說明如表1所示。

表1 符號說明

2.2 基本假設(shè)

本文研究的揀選臺訂單處理問題,將基于以下基本假設(shè)展開求解:

(1) 假設(shè)倉儲區(qū)采取共享存儲策略,即一種貨物可分散存儲在多個貨架上。

(2) 假設(shè)貨架上貨物數(shù)量充足,不考慮缺貨情況。

(3) 不考慮機(jī)器人行走過程中的堵塞。

(4) 不考慮揀選臺之間的相互影響。

(5) 假設(shè)訂單的活躍狀態(tài)轉(zhuǎn)換發(fā)生在貨架改變之前,即當(dāng)本回合有活躍可揀選訂單完成揀選后,下一回合補(bǔ)入的新活躍訂單可利用本回合活躍貨架揀選貨物。

2.3 整數(shù)規(guī)劃模型建立

建立基于貨到人系統(tǒng)的揀選臺訂單處理的整數(shù)規(guī)劃模型如下:

(1)

s.t.

(2)

(3)

yj,t+yj,t+d≤yj,t+1+1

?t=1,2,…,T,d=2,3,…,T-t,?j=1,2,…,N

(4)

(5)

?i=1,2,…,M,?j=1,2,…,N,?t=1,2,…,T

(6)

(7)

xrt∈{0,1} ?r=1,2,…,R,?t=1,2,…,T

(8)

yjt∈{0,1} ?j=1,2,…,N,?t=1,2,…,T

(9)

zijt∈{0,1} ?i=1,2,…,M,?j=1,2,…,N,
?t=1,2,…,T

(10)

式(1)是最小化完成所有訂單揀選時(shí)貨架的總搬運(yùn)次數(shù),其中Φt由式(7)定義,表示到達(dá)揀選臺的貨架的改變次數(shù)。式(2)限制揀選臺可同時(shí)揀選貨架的最大數(shù)量。式(3)限制揀貨員最多可同時(shí)處理B個待揀選訂單。式(4)確保每個訂單必須在連續(xù)的回合期間被揀選。式(5)確保全部訂單的所有貨物必須都被揀選完成。式(6)表示當(dāng)且僅當(dāng)現(xiàn)回合下訂單是活躍可揀選狀態(tài),且所需貨物也儲存在當(dāng)前活躍貨架中時(shí),該待揀選貨物才能被揀出。式(8)、式(9)和式(10)定義xrt、yjt和zijt為0-1變量,其中xrt記錄了各回合中活躍狀態(tài)訂單包含的待揀選貨物種類的揀選情況,由xrt可得出貨架排序RS為所有回合中首次取1時(shí)對應(yīng)的貨架編號r的順序排列集合,由yjt可得出訂單處理排序OS為所有回合中yjt首次取1時(shí)對應(yīng)的訂單編號j的順序排列集合。

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

隨著算例規(guī)模的增大,精確算法求解數(shù)學(xué)模型所需時(shí)長遠(yuǎn)超出可行范圍,因此本文設(shè)計(jì)了三種算法來求解更大規(guī)模算例,分別為確定訂單處理次序的算法VNS-OS、確定貨架到達(dá)次序的算法VNS-RS和交替求解訂單和貨架次序的算法AH。

3.1 確定訂單排序的訂單處理問題

算法VNS-OS的思路是先確定待揀選訂單處理排序,再根據(jù)給定的訂單排序求得對應(yīng)貨架搬運(yùn)總次數(shù)最少的貨架排序。其中,待揀選訂單處理排序通過算子Shaking、opt1、opt2和opt3進(jìn)行變換,通過函數(shù)GreedyOS求解出對應(yīng)的最優(yōu)貨架排序,VNS-OS算法如算法1所示。

算法1VNS-OS算法

輸入:抖動鄰域Ns,VND鄰域集合Nl=1,2,3,設(shè)置MaxVNDIteration和MaxIteration。

輸出:RS記錄當(dāng)前最優(yōu)貨架排序,首列記錄最少貨架搬運(yùn)次數(shù),OS記錄當(dāng)前最優(yōu)訂單排序。

生成初始解:由初始OSet和函數(shù)GreedyOS求得初始貨架排充RS。

1.OS=OSet;

//設(shè)初始訂單排序?yàn)镺Set

2.RS=GreedyOS(OS);

//由函數(shù)GreedyOS求得初始貨架排序RS

3.k=0;

//設(shè)VND算法框架的初始迭代次數(shù)為0

4.whilek

//MaxVNDIteration為VND算法框架最大迭代次數(shù)

5.flip=1;

//從VND內(nèi)鄰域Nl開始局部搜索

6.whileflip

//依次在鄰域N1、N2、N3進(jìn)行局部搜索后跳出VND

7.

//抖動階段

8.OSSolution=Shaking(OS);

//執(zhí)行算子Shaking,生成Ns(OS)隨機(jī)鄰域解

9.OptimalRackSeq=GreedyOS(OSSolution);

//求解對應(yīng)貨架排序

10.

//進(jìn)入VND算法框架的局部搜索階段

11. ifflip==l

//flip指示進(jìn)入VND框架內(nèi)對應(yīng)鄰域Nl進(jìn)行局部搜索

12. [OSSolution,OptimalRackSeq]=optl(OSSolution,OptimalRackSeq);

13. end

14.

//更新最優(yōu)解:

15. ifOptimalRackSeq(1)

//當(dāng)經(jīng)歷VND所得解優(yōu)于當(dāng)前最優(yōu)解時(shí)

16.OS=OSSolution;

//更新OSSolution為當(dāng)前訂單最優(yōu)排序OS

17.RS=OptimalRackSep;

//更新OptimalRackSeq為當(dāng)前貨架最優(yōu)排序RS

18. continue

//如果在本鄰域找到更優(yōu)解,則跳回?cái)_動鄰域Ns進(jìn)行搜索

19. else

20.flip=flip+1;

//若在本鄰域未找到更優(yōu)解,跳到下個鄰域Nl繼續(xù)搜索

21. end

22. end

23.k+k+1;

//記錄VND算法框架的迭代次數(shù)

24. end

按初始訂單處理排序排列的訂單集合為OSet,通過鄰域變換生成新的訂單排序,包括擾動階段和局部搜索階段。擾動階段有算子Shaking,實(shí)現(xiàn)在N個訂單標(biāo)號排序中任意選擇2個訂單行調(diào)換揀選次序的變換。圖1展示了N=6時(shí)訂單排序經(jīng)歷算子Shaking前后的變換過程,其中箭頭標(biāo)識所選插入點(diǎn)。

圖1 算法VNS-OS擾動階段鄰域算子Shaking變換示例

局部搜索階段有opt1、opt2和opt3三個算子,其中算子opt1實(shí)現(xiàn)在N個訂單標(biāo)號中取隨機(jī)選擇的2個插入點(diǎn)間進(jìn)行區(qū)間反轉(zhuǎn)的變換,算子opt2實(shí)現(xiàn)在N個訂單標(biāo)號中取隨機(jī)選擇的2個插入點(diǎn)塞入新序列頭部,其余標(biāo)號按原序列依次排列,算子opt3實(shí)現(xiàn)在N個訂單標(biāo)號中取隨機(jī)選擇的2個相鄰插入點(diǎn),將數(shù)字大的插入點(diǎn)后面的訂單標(biāo)號插入兩點(diǎn)之間。圖2展示了N=6時(shí)訂單排序分別經(jīng)歷算子opt1、opt2和opt3前后的變換過程。

圖2 算法VNS-OS局部搜索階段鄰域算子變換示例

函數(shù)GreedyOS用于求解當(dāng)前待揀選訂單處理排序下的使所有訂單揀選完成的貨架搬運(yùn)總次數(shù)最小的貨架排序。它的基本思路是,為了使全部訂單揀選完成時(shí)的貨架搬運(yùn)總次數(shù)最小,即要使每回合從當(dāng)前活躍貨架上揀出的貨物最多,在每回合選擇與當(dāng)前活躍訂單總差異最小的為活躍貨架。其衡量標(biāo)準(zhǔn)為貨架內(nèi)貨物種類組合與當(dāng)前活躍訂單行的差異,如式(11)所示,由于兩者均為用邏輯語言表達(dá)貨物種類包含關(guān)系的0-1行向量,故兩者的差異用附帶條件的曼哈頓距離公式表示。

(11)

3.2 確定貨架排序的訂單處理問題

算法VNS-RS的思路是先確定到達(dá)揀選臺的貨架排序,再根據(jù)當(dāng)前活躍貨架內(nèi)的貨物種類組合決定本回合的活躍訂單,以各待揀選訂單依次轉(zhuǎn)變?yōu)榛钴S狀態(tài)的順序,作為使貨架搬運(yùn)總次數(shù)最少的待揀選訂單處理排序。其中,貨架到達(dá)揀選臺的排序通過算子Shaking1、opt1S、opt2S和opt3S進(jìn)行變換,通過函數(shù)GreedyRS求解出對應(yīng)的最優(yōu)訂單排序,VNS-RS算法如算法2所示。

算法2VNS-RS算法

輸入:N,R,OSet,抖動領(lǐng)域Nk,k=1,VND鄰域集合Nl,l=1,2,3,設(shè)置MaxVNDIteration和MaxIteration。

輸出:RSsolution記錄最優(yōu)貨架排序,OSsolution記錄最優(yōu)訂單排序,首列為最少貨架搬運(yùn)次數(shù)。

生成初始解:初始訂單排序?yàn)镺Set,由函數(shù)GreedyOS求得初始貨架排序InitialRS,記此時(shí)貨架搬運(yùn)次數(shù)為InitialScore,再加上n個{1:R}構(gòu)成RSsolution。

1.OSsolution=[InitialScore,1:nOrder];

//設(shè)初始訂單排序?yàn)镺Set

2.RSsolution=GreedyOS(OSet);

//通過函數(shù)GreedyOS求貨架初始排序RSsolution

3.K=0;

//設(shè)VND算法框架的初始迭代次數(shù)為0

4.whileK

//MaxVNDIteration為VND算法框架最大迭代次數(shù)

5.flip=1;

//從VND框架內(nèi)鄰域Nl開始局部搜索

6.whileflip

//依次在鄰域N1,,N2,N3進(jìn)行局部搜索后跳出VND

7.

//抖動階段

8.OptimalRackSeq=Shaking1(RSsolution);

//生成Ns(RSsolution)隨機(jī)鄰域解

9.OptimalOrderSeq=GreedyRS(OptimalRackSeq);

//求解訂單排序

10.

//進(jìn)入VND算法框架的局部搜索階段

11. ifflip==l

//flip指示進(jìn)入VND框架內(nèi)對應(yīng)鄰域Nl進(jìn)行局部搜索

12. [OptimalRackSeq,OptimalOrderSeq]=optl(OptimalRackSeq,OptimalOrderSeq);

13. end

14.

//更新最優(yōu)解:

15.ifOptimalOrderSeq(1)

//若VND所得解優(yōu)于當(dāng)前最優(yōu)解

16.OSsolution=OptimalOrderSeq;

//更新當(dāng)前訂單最優(yōu)排序?yàn)镺Ssolution

17.RSsolution=OptimalRackSeq;

//更新當(dāng)前貨架最優(yōu)排序?yàn)镽Ssolution

18. continue

//如果在本鄰域找到更優(yōu)解,則跳回?cái)_動鄰域Ns進(jìn)行搜索

19. else

20.flip=flip+1;

//若在本鄰域未找到最優(yōu)解,跳到下個鄰域Nl繼續(xù)搜索

21. end

22. end

23.K=K+1;

//記錄VND算法框架的迭代次數(shù)

24. end

通過函數(shù)GreedyOS求解訂單處理排序?yàn)镺Set時(shí)的貨架排序InitialRS,之后通過擾動階段和局部搜索階段的鄰域變換生成新的貨架排序,當(dāng)變換后貨架排序中出現(xiàn)相同的相鄰貨架標(biāo)號,則刪去重復(fù)標(biāo)號。擾動階段有算子Shaking1,實(shí)現(xiàn)在當(dāng)前貨架排序中任意選擇2個貨架標(biāo)號調(diào)換次序。圖3展示了初始貨架排序?yàn)閧3,2,1,4}(R=4,插入點(diǎn)在排位1-7范圍內(nèi)選取)時(shí)貨架排序經(jīng)歷算子Shaking1前后的變換過程。

圖3 算法VNS-RS擾動階段鄰域算子Shaking1變換示例

局部搜索階段包括算子opt1S、opt2S和opt3S,其中算子opt1S實(shí)現(xiàn)在當(dāng)前貨架排序中取隨機(jī)選擇的2個插入點(diǎn)間進(jìn)行區(qū)間反轉(zhuǎn),算子opt2S實(shí)現(xiàn)在當(dāng)前貨架排序中取隨機(jī)選擇的2個插入點(diǎn)塞入新序列頭部,其余貨架標(biāo)號按原序列依次排列,算子opt3S實(shí)現(xiàn)在當(dāng)前貨架排序中取隨機(jī)選擇的2個相鄰插入點(diǎn),將排位靠后插入點(diǎn)后面的貨架標(biāo)號插入兩點(diǎn)之間。圖4展示了初始貨架排序?yàn)閧3,2,1,4}(R=4,插入點(diǎn)在排位1至7范圍內(nèi)選取)時(shí)貨架排序分別經(jīng)歷算子opt1S、opt2S和opt3S前后的變換過程。

圖4 算法VNS-RS局部搜索階段鄰域算子變換示例

函數(shù)GreedyRS用于求解當(dāng)前到達(dá)揀選臺的貨架排序下的確保全部訂單完成揀選的貨架搬運(yùn)總次數(shù)最小的訂單處理排序。其基本思路與函數(shù)GreedyOS類似,在每回合選擇與當(dāng)前活躍貨架的差異最小的訂單轉(zhuǎn)為活躍狀態(tài)。

3.3 交替確定訂單和貨架排序的訂單處理問題

基于對上述兩個子問題的思考,設(shè)計(jì)交替確定訂單和貨架排序的算法AH。算法AH的基本思路為先計(jì)算各貨架與當(dāng)前活躍訂單的差異,取總差異最小的為本回合活躍貨架,再取與當(dāng)前活躍貨架差異較小的訂單為活躍訂單,交替來確定訂單和貨架排序。最終得到R組解訂單排序AOSSeqSet和對應(yīng)貨架排序ARSSeqSet,取R組解中完成所有訂單揀選時(shí)所需貨架搬運(yùn)次數(shù)最少的為最優(yōu)訂單排序AOSSeq和最優(yōu)貨架排序ARSSeq,AH算法如算法3所示。

算法3AH算法

輸入:N,M,R,B,OSet,RSet。

輸出:AOSSeqSet,ARSSeqSet,生成R組解。

1.

//首回合依次取各貨架為首個活躍貨架,分別再取當(dāng)前貨架

//差異較小的為首批活躍訂單,生成R組解

2. AT=2;

//記錄當(dāng)前貨架搬運(yùn)次數(shù)

3.whilelength(finishedOrderID)

//循環(huán)終止條件為全部訂單都完成揀選

4.

//計(jì)算各訂單與當(dāng)前活躍貨架的差異,取差異較小的

//訂單為活躍訂單

5. fori=1:length(pickingOrderID)

//遍歷當(dāng)前活躍訂單

6. forp=1:nRack

//遍歷所有貨架

7.distance=0;

8. forj=1:nSku

//遍歷所有貨物種類

9. ifCurrentOrderSet(pickingOrderID(i),j)>0

10.

//用帶條件的曼哈頓距離公式來計(jì)算貨架與訂單行的差異

11. [～,CurrentRackID]=min(pickingDis);

//取總差異最小的為活躍貨架

12.ARSSeq(1)=AT;

//ARSSeq首列記錄當(dāng)前貨架已搬運(yùn)次數(shù)

13.ARSSeq(AT+1)=CurrentRackID;

//ARSSeq末列記錄當(dāng)前活躍貨架

14.

//檢查當(dāng)前活躍訂單是否有揀選完成的

16.pickedOrderID=pickingOrderID(rr);

//記錄本回合完成揀選的訂單標(biāo)號

17.pickingOrderID=setdiff(pickingOrderID,pickedOrderID);

//更新活躍訂單ID

18.finishedOrderID=[finishedOrderID,pickedOrderID];

//更新已完成訂單ID

19.DD=setdiff(1:nOrder,finishedOrderID);

20. InActiveOrderID=setdiff(DD,pickingOrderID);

//更新剩余未揀選訂單ID

21.

//如有,按當(dāng)前訂單處理排序補(bǔ)足至min(B,剩余待揀選

//訂單數(shù))個活躍訂單

22.

//計(jì)算本回合揀選過后的CurrentOrderSet,將揀選完成

//訂單行標(biāo)記為10 000行

23.

//本回合新補(bǔ)進(jìn)的活躍訂單進(jìn)行當(dāng)前貨架的揀選

24.AT=AT+1;

//每搬運(yùn)一次貨架AT增加1

25. end

4 算 例

4.1 基本參數(shù)設(shè)置

與本文研究的問題最直接相關(guān)的是文獻(xiàn)[2],但該文未提供具體的算例數(shù)據(jù),無法直接對比本文算法與該文提出的集束搜索算法,但該文指出了算例中參數(shù)的取值范圍,并討論了其合理性。本文根據(jù)文獻(xiàn)[2],分別隨機(jī)產(chǎn)生了一組小規(guī)模、一組中規(guī)模和一組大規(guī)模算例。其中小規(guī)模算例可以直接用整數(shù)規(guī)劃求解器CPLEX利用問題的數(shù)學(xué)模型(見2.3節(jié))進(jìn)行求解,得到問題的最優(yōu)解或者近似最優(yōu)解,從而為評價(jià)本文提出的VNS算法提供依據(jù)。中等規(guī)模和大規(guī)模是指逐步加大訂單數(shù)、貨架數(shù)和SKU數(shù)等,以進(jìn)一步加大搜索空間和計(jì)算強(qiáng)度,通過與算法初始解的對比來進(jìn)一步測試VNS算法的有效性。首先介紹其中的訂單集和貨物集的生成方法。訂單集合OSet由函數(shù)OrderSet生成,輸入?yún)?shù)為待揀選訂單總數(shù)N和貨物種類數(shù)M。假設(shè)各種貨物在所有訂單中出現(xiàn)的次數(shù)服從均值為λi的泊松分布,i值取1到M的正整數(shù)。各貨物對應(yīng)的λi之間相對大小排序隨機(jī)產(chǎn)生,限制所有取值服從[0.2N,0.8N]的均勻分布,確保OSet中無空訂單行的出現(xiàn)。

本文考慮了兩種儲位分配策略:隨機(jī)儲貨和按貨物間關(guān)聯(lián)規(guī)則儲貨。其中,隨機(jī)儲貨策略由函數(shù)RackSkuSet實(shí)現(xiàn),輸入?yún)?shù)為貨物種類數(shù)M、貨架種類數(shù)R和x,其中M-x限制所有貨架中允許出現(xiàn)的最多貨物種類數(shù)。所有種類的貨物一定儲存在至少一個貨架內(nèi),確保各貨架內(nèi)貨物種類組合之間不存在包含關(guān)系,且互不相同。

而按貨物間關(guān)聯(lián)規(guī)則的儲位分配策略,本文通過引入智能算法Apriori從頻繁項(xiàng)集中挖掘出待揀選訂單中各種貨物之間的關(guān)聯(lián)規(guī)則。頻繁項(xiàng)集指經(jīng)常同時(shí)出現(xiàn)的元素集合,其定義包括支持度和置信度兩個重要指標(biāo),其定義如式(12)和式(13)所示。

(12)

(13)

Apriori原理的核心理論為,如果一個元素是非頻繁項(xiàng),那么它的超集也是非頻繁項(xiàng)集。這樣,Apriori算法可以避免項(xiàng)集數(shù)量的指數(shù)增長,進(jìn)而在合理時(shí)間范圍內(nèi)尋找到頻繁項(xiàng)集。Apriori算法如算法4所示。

算法4Apriori算法

輸入:OSet。

輸出:關(guān)聯(lián)規(guī)則文檔rules.txt。

1.minSup=0.3;

//設(shè)置最小支持度

2.minConf=0.3;

//設(shè)置最小置信度

3.nRules=1 000;

//設(shè)置最大輸出關(guān)聯(lián)規(guī)則數(shù)量

4.sortFlag=1;

//按照支持度從大到小的排序依次輸出關(guān)聯(lián)規(guī)則

5.

//調(diào)用Apriori算法尋找待揀選訂單內(nèi)貨物種類間的關(guān)聯(lián)規(guī)則

6. [Rules,FreqItemsets]=findRules(OSet,minSup,minConf,nRules,sortFlag,code,rulefile);

7.

//生成候選項(xiàng)集

8.

//對待揀選訂單集合的每個訂單行

9.

//對每個由貨物種類組成的候選項(xiàng)集

10.

//檢查候選項(xiàng)集是否為訂單行的子集

11.

//如果是,則該候選項(xiàng)集計(jì)數(shù)加1

12.

//對各候選項(xiàng)集

13.

//若其支持度大于最小支持度,則保留該項(xiàng)集

14.

//返回所有頻繁項(xiàng)集

15.

//當(dāng)集合中項(xiàng)的個數(shù)>0

16.

//構(gòu)建候選項(xiàng)集列表,初始n=1

17.

//計(jì)算候選項(xiàng)集支持度,刪除非頻繁項(xiàng)集

18.

//構(gòu)建由n+1項(xiàng)組成的候選項(xiàng)集的列表

19.

//從頻繁項(xiàng)集中挖掘關(guān)聯(lián)規(guī)則

4.2 結(jié)果分析

在小規(guī)模算例下,通過對比CPLEX在10分鐘內(nèi)求得的整數(shù)規(guī)劃模型的解,驗(yàn)證算法VNS-OS、VNS-RS和AH的有效性。參數(shù)設(shè)置為N=20、M=5、R=10、B=3,采用隨機(jī)儲貨策略,共10個貨架儲存不同的兩兩貨物種類組合。表2列出了各算法求得的搬運(yùn)次數(shù),其中第一列是用CPLEX求得的搬運(yùn)次數(shù),第2、4、6列中α分別表示用VNS-OS、VNS-RS、AH算法求得的搬運(yùn)次數(shù)的改進(jìn)百分比(正值表示降低),第3、5列β表示與初始解的搬運(yùn)次數(shù)改進(jìn)百分比(正值表示降低)。

表2 小規(guī)模算例計(jì)算結(jié)果

分析表2,在小規(guī)模算例下,可以得出:對比CPLEX耗費(fèi)10分鐘求得的已知最優(yōu)解,三種算法的平均求解質(zhì)量更優(yōu),并且平均求解優(yōu)化效果排序?yàn)閂NS-RS>VNS-OS>AH,平均優(yōu)化程度分別為17.9%、12.5%和6.7%,從而證明了三種算法的有效性。對于算法VNS-OS和VNS-RS,最終解對比其初始解的平均優(yōu)化程度分別為23.3%和27.1%,證明VNS算法對于訂單處理排序和貨架排序的優(yōu)化效果明顯。VNS-RS、VNS-OS和AH求解小規(guī)模算例的平均運(yùn)行時(shí)間分別為26 s、72 s和1 s,均比CPLEX軟件求解時(shí)間要短。

在中等規(guī)模算例下,參數(shù)設(shè)置為N=50,M=8,R=28,B在3～20之間取值。采用隨機(jī)儲貨策略,共28個貨架儲存不同的兩兩貨物種類組合。

分析表3,在中等規(guī)模算例下可以得出:對比三種算法求得的最優(yōu)解,平均求解優(yōu)化效果排序?yàn)閂NS-OS>VNS-RS>AH,平均優(yōu)化程度分別為13.1%、5.1%和2.3%,同時(shí)算法AH在B取值較小時(shí)求解質(zhì)量較優(yōu),算法VNS-RS在B取值較大時(shí)求解質(zhì)量較優(yōu)。算法VNS-OS和VNS-RS的最終解對比其初始解的平均優(yōu)化程度分別為21.0%和13.9%,證明VNS算法對訂單處理排序和貨架排序的優(yōu)化效果明顯。VNS-RS、VNS-OS和AH求解中等規(guī)模算例的平均時(shí)間分別為89 s、155 s和2 s,耗時(shí)較短。

表3 中等規(guī)模算例計(jì)算結(jié)果

在大規(guī)模算例下,參數(shù)設(shè)置N=100,M=15,R=105,B在10～30之間取值。分別采用隨機(jī)和按關(guān)聯(lián)規(guī)則的儲位分配策略,隨機(jī)儲貨策略為共105個貨架儲存不同的兩兩貨物種類組合,按Apriori算法計(jì)算出的置信度最高的14條關(guān)聯(lián)規(guī)則將貨物存儲在14個不同貨架中。

分析表4,在大規(guī)模算例下,可以得出:相比于三種算法求得的最優(yōu)解,平均求解優(yōu)化效果排序?yàn)閂NS-OS>VNS-RS>AH,平均優(yōu)化程度分別為9.3%、5.7%和1.4%,同時(shí)算法AH在B取值較小時(shí)求解質(zhì)量較優(yōu),算法VNS-RS在B取值較大時(shí)求解質(zhì)量較優(yōu)。對于算法VNS-OS和VNS-RS,最終解相比于其初始解的平均優(yōu)化程度分別為14.0%和10.6%,證明VNS算法對訂單處理排序和貨架排序的優(yōu)化效果明顯。VNS-RS、VNS-OS和AH求解大規(guī)模算例的平均時(shí)間分別為135 s、141 s和13 s,耗時(shí)適中。

表4 大規(guī)模算例計(jì)算結(jié)果

綜合不同規(guī)模算例的計(jì)算結(jié)果,總結(jié)出三種算法求解質(zhì)量較好的條件,即當(dāng)算例規(guī)模較小或算例規(guī)模較大且B取值較大時(shí),選擇算法VNS-RS求解質(zhì)量較高;當(dāng)算例規(guī)模較大且B取值較小時(shí),選擇算法AH求解質(zhì)量較高且耗時(shí)短;算法VNS-OS整體的求解質(zhì)量穩(wěn)定,性能最優(yōu)。

4.3 敏感性分析

基于對不同規(guī)模算例的求解結(jié)果,研究全部訂單完成揀選時(shí)貨架總搬運(yùn)次數(shù)和貨架利用率受單揀選臺可同時(shí)處理最大訂單數(shù)和不同儲位分配策略的影響。

分析表5,可以得出:在隨機(jī)儲位分配策略下,三種算法中,算法VNS-OS求得的平均貨架利用率最小(37.2%)。該策略下,貨架平均利用率較低,僅利用到近四成貨架,并且貨架利用率隨揀選臺可同時(shí)處理的最大訂單數(shù)B值增加而降低。貨架搬運(yùn)次數(shù)隨B值增加而減少,但下降幅度逐漸變小,說明B取值不是越大越好。隨著可同時(shí)處理的最大訂單數(shù)增加,所需貨架搬運(yùn)次數(shù)減少的收益增幅逐漸降低,但同時(shí)人力和設(shè)備成本卻在增加,因此,應(yīng)當(dāng)取合適大小的訂單處理批量實(shí)現(xiàn)系統(tǒng)整體效率的優(yōu)化。

表5 貨架搬運(yùn)次數(shù)和貨架利用率隨B值變化情況

按照隨機(jī)和關(guān)聯(lián)規(guī)則的存儲策略分別對相同算例求解。如表6所示,首列標(biāo)注了各組算例采取的儲位分配策略,可以得出:對比隨機(jī)儲貨策略,按關(guān)聯(lián)規(guī)則儲貨的平均貨架利用率約為隨機(jī)儲貨的2.4倍,所需貨架搬運(yùn)總次數(shù)平均減少12.7%,說明按關(guān)聯(lián)規(guī)則儲貨可以節(jié)省大量貨架,在減少貨架搬運(yùn)次數(shù)的同時(shí)提高貨架利用率,優(yōu)于隨機(jī)儲位分配策略。

表6 貨架搬運(yùn)次數(shù)和貨架利用率隨B值變化情況

5 結(jié) 語

本文關(guān)注智能物流背景下的貨到人揀貨系統(tǒng),研究基于物流機(jī)器人的訂單揀選排程算法及其實(shí)現(xiàn),是“貨到人”揀選模式的理論研究和應(yīng)用。本文在考慮單揀選臺可同時(shí)處理的最大訂單數(shù)和貨架內(nèi)貨物組合規(guī)則的前提下,建立了求解揀選臺訂單處理的整數(shù)規(guī)劃模型。接著分別從先確定訂單處理次序和貨架到達(dá)次序兩個角度,設(shè)計(jì)了VNS-OS算法和VNS-RS算法,進(jìn)一步設(shè)計(jì)了交替求解訂單和貨架排序的AH算法,證明了算法的有效性和準(zhǔn)確性。最后結(jié)合算例計(jì)算結(jié)果,在完成所有訂單揀選和所需貨架搬運(yùn)總次數(shù)最少的前提下,分析單揀選臺可同時(shí)處理的最大訂單數(shù)、儲位分配策略(隨機(jī)分配、按貨物間關(guān)聯(lián)規(guī)則分配)對揀選效率和貨架利用率的影響,為可移動貨架式倉庫的實(shí)際運(yùn)營者提供有利于提升系統(tǒng)揀選效率的倉庫管理建議。

隨著近年來可移動式貨架倉庫在電商、快消品、藥品等多類場景下的應(yīng)用和發(fā)展,RMFS系統(tǒng)的實(shí)際運(yùn)行還有很多值得深入研究和綜合考慮的問題。未來可以考慮貨架內(nèi)貨物經(jīng)揀選后出現(xiàn)缺貨的情況,研究合適的補(bǔ)貨策略,還可以考慮多個揀選臺共同處理待揀選訂單的情況。未來可以綜合考慮結(jié)合倉庫布局、路徑規(guī)劃、機(jī)器人小車電池管理等問題,提升倉庫的揀選效率,減少系統(tǒng)總支出。