一種基于物流機器人的訂單揀選排程算法設計與實現(xiàn)

姚文斌 朱子欣

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

0 引 言

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

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

1 研究背景

1.1 貨到人訂單揀選模式

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

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

1.2 訂單排序問題

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

1.3 儲位分配問題

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

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

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

1.5 變鄰域搜索算法

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

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

2 模型建立

2.1 符號說明

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

表1 符號說明

2.2 基本假設

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

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

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

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

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

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

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

3 算法設計

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

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

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

算法1VNS-OS算法

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

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

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

1.OS=OSet;

//設初始訂單排序為OSet

2.RS=GreedyOS(OS);

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

3.k=0;

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

4.whilek

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

5.flip=1;

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

6.whileflip

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

7.

//抖動階段

8.OSSolution=Shaking(OS);

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

9.OptimalRackSeq=GreedyOS(OSSolution);

//求解對應貨架排序

10.

//進入VND算法框架的局部搜索階段

11. ifflip==l

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

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

13. end

14.

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

15. ifOptimalRackSeq(1)

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

16.OS=OSSolution;

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

17.RS=OptimalRackSep;

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

18. continue

//如果在本鄰域找到更優(yōu)解,則跳回擾動鄰域Ns進行搜索

19. else

20.flip=flip+1;

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

21. end

22. end

23.k+k+1;

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

24. end

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

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

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

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

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

(11)

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

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

算法2VNS-RS算法

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

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

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

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

//設初始訂單排序為OSet

2.RSsolution=GreedyOS(OSet);

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

3.K=0;

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

4.whileK

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

5.flip=1;

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

6.whileflip

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

7.

//抖動階段

8.OptimalRackSeq=Shaking1(RSsolution);

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

9.OptimalOrderSeq=GreedyRS(OptimalRackSeq);

//求解訂單排序

10.

//進入VND算法框架的局部搜索階段

11. ifflip==l

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

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

13. end

14.

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

15.ifOptimalOrderSeq(1)

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

16.OSsolution=OptimalOrderSeq;

//更新當前訂單最優(yōu)排序為OSsolution

17.RSsolution=OptimalRackSeq;

//更新當前貨架最優(yōu)排序為RSsolution

18. continue

//如果在本鄰域找到更優(yōu)解,則跳回擾動鄰域Ns進行搜索

19. else

20.flip=flip+1;

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

21. end

22. end

23.K=K+1;

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

24. end

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

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

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

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

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

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

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

算法3AH算法

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

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

1.

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

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

2. AT=2;

//記錄當前貨架搬運次數(shù)

3.whilelength(finishedOrderID)

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

4.

//計算各訂單與當前活躍貨架的差異,取差異較小的

//訂單為活躍訂單

5. fori=1:length(pickingOrderID)

//遍歷當前活躍訂單

6. forp=1:nRack

//遍歷所有貨架

7.distance=0;

8. forj=1:nSku

//遍歷所有貨物種類

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

10.

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

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

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

12.ARSSeq(1)=AT;

//ARSSeq首列記錄當前貨架已搬運次數(shù)

13.ARSSeq(AT+1)=CurrentRackID;

//ARSSeq末列記錄當前活躍貨架

14.

//檢查當前活躍訂單是否有揀選完成的

16.pickedOrderID=pickingOrderID(rr);

//記錄本回合完成揀選的訂單標號

17.pickingOrderID=setdiff(pickingOrderID,pickedOrderID);

//更新活躍訂單ID

18.finishedOrderID=[finishedOrderID,pickedOrderID];

//更新已完成訂單ID

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

20. InActiveOrderID=setdiff(DD,pickingOrderID);

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

21.

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

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

22.

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

//訂單行標記為10 000行

23.

//本回合新補進的活躍訂單進行當前貨架的揀選

24.AT=AT+1;

//每搬運一次貨架AT增加1

25. end

4 算 例

4.1 基本參數(shù)設置

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

本文考慮了兩種儲位分配策略:隨機儲貨和按貨物間關(guān)聯(lián)規(guī)則儲貨。其中,隨機儲貨策略由函數(shù)RackSkuSet實現(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從頻繁項集中挖掘出待揀選訂單中各種貨物之間的關(guān)聯(lián)規(guī)則。頻繁項集指經(jīng)常同時出現(xiàn)的元素集合,其定義包括支持度和置信度兩個重要指標,其定義如式(12)和式(13)所示。

(12)

(13)

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

算法4Apriori算法

輸入:OSet。

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

1.minSup=0.3;

//設置最小支持度

2.minConf=0.3;

//設置最小置信度

3.nRules=1 000;

//設置最大輸出關(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.

//生成候選項集

8.

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

9.

//對每個由貨物種類組成的候選項集

10.

//檢查候選項集是否為訂單行的子集

11.

//如果是,則該候選項集計數(shù)加1

12.

//對各候選項集

13.

//若其支持度大于最小支持度,則保留該項集

14.

//返回所有頻繁項集

15.

//當集合中項的個數(shù)>0

16.

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

17.

//計算候選項集支持度,刪除非頻繁項集

18.

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

19.

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

4.2 結(jié)果分析

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

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

分析表2,在小規(guī)模算例下,可以得出:對比CPLEX耗費10分鐘求得的已知最優(yōu)解,三種算法的平均求解質(zhì)量更優(yōu),并且平均求解優(yōu)化效果排序為VNS-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ī)模算例的平均運行時間分別為26 s、72 s和1 s,均比CPLEX軟件求解時間要短。

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

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

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

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

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

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

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

4.3 敏感性分析

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

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

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

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

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

5 結(jié) 語

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

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