機器人履約系統(tǒng)任務分配與貨架儲位再指派聯(lián)合優(yōu)化

李騰, 張茹蘭, 丁佩佩

(哈爾濱商業(yè)大學管理學院, 哈爾濱 150028)

移動機器人履約系統(tǒng)(robotic mobile fulfillment system,RMFS)是一種新型的“貨到人”揀選系統(tǒng),與傳統(tǒng)的人工和自動化立體倉庫系統(tǒng)AS/RS(automated storage and retrieval system)揀選相比,其在揀選效率、倉庫空間利用率等方面都存在著明顯的優(yōu)勢[1]。貨架儲位再指派問題是RMFS所特有的,其是指通過規(guī)劃貨架完成揀選任務后儲存的位置,縮短移動機器人行駛距離,降低成本,提高倉庫揀選效率的優(yōu)化問題。Krenzler等[2]是較早研究此類問題的學者,其建立了考慮貨架在揀選臺隊列位置和移動機器人數(shù)量,不考慮客戶訂單商品儲位情況和補貨問題的簡化模型,采用了二進制、最近位置、固定位置、隨機位置、迭代二進制遺傳以及俄羅斯方塊算法求解,得出在大型算例應用中俄羅斯方塊算法更為有效。Yuan等[3]基于隨機、類、周轉(zhuǎn)率原則構(gòu)建排隊模型,得出基于兩類或三類的儲位分配策略可以實現(xiàn)大多數(shù)潛在益處且益處會隨貨架周轉(zhuǎn)率的變化而變化。Weidinger等[4]進一步研究將貨架儲位再指派問題轉(zhuǎn)化成特殊的區(qū)間調(diào)度問題,提出自適應貨架儲位再指派策略。Ji等[5]將貨架儲位再指派問題分成了一次對一個貨架指派和一次對多個貨架進行指派兩類問題,建立了考慮貨架未來搬運距離的優(yōu)化模型。Rimélé等[6]提出了一種高效但計算成本較高的蒙特卡洛樹法。

隨著研究的深入,越來越多的學者在進行相關問題研究時將貨架儲位再指派作為考慮的因素。徐翔斌等[7]提出了一種考慮貨架與儲位匹配程度的貨架再指派策略。Roy等[8]在多存儲區(qū)域移動機器人分配策略問題的研究中,對隨機貨架儲位再指派策略下的移動機器人多存儲區(qū)域分配策略性能進行了研究。Li等[9]對高密度移動貨架系統(tǒng)中任務分配、路徑規(guī)劃及沖突、阻塞解決問題進行了研究。

Merschformann 等[10]在研究任務分配、貨架選擇、貨架儲位再指派問題對系統(tǒng)運行指標影響時,指出任務分配策略對系統(tǒng)吞吐量指標影響最大。因此,貨架儲位再指派策略也常常在任務分配問題研究中被考慮。Zhang[11]、Yuan等[12]和孫君陽等[13]研究了貨架返回原位置策略下的多移動機器人調(diào)度問題。Gharehgozli等[14]提出考慮訂單優(yōu)先級的任務分配問題并對存在多貨架返回位置可選情況下的貨架位置選擇問題進行了討論。Yoshitake 等[15]建立了考慮貨架和移動機器人狀態(tài)的實時調(diào)度方法,給出貨架返回距離移動機器人最近儲存位置的策略。Rimélé等[16]提出了一種實時決策形式化的隨機數(shù)學建?？蚣?研究了在隨機輸入訂單情況下,RMFS中包括訂單排序、儲位指派、貨架儲位再指派等大多數(shù)操作決策問題。Bao等[17]提出一種同時考慮任務分配和貨架儲位再指派的策略,即貨架返回到指派位置與下一任務點距離之和最小位置的策略。

在已有相關文獻中針對貨架儲位再指派問題的研究多為對貨架儲位再指派單一問題或如在任務分配、多機器人調(diào)度、儲位規(guī)劃中考慮貨架儲位再指派策略的研究,而針對貨架儲位再指派問題和RMFS其他規(guī)劃問題的聯(lián)合優(yōu)化研究文獻較少。移動機器人完成揀選任務過程中貨架返回位置是影響移動機器人行駛距離和運行時間的重要因素,不同運行狀態(tài)下能耗的差別也是影響移動機器人完成任務成本的重要因素。因此在已有研究文獻基礎上,現(xiàn)研究考慮下一任務位置的任務分配與貨架儲位再指派聯(lián)合優(yōu)化問題,將移動機器人運行成本作為主要目標,細化單位時間移動機器人重載與空載成本差異。探討RMFS實現(xiàn)移動機器人完成任務成本更優(yōu),揀選效率更高的策略,豐富相關理論,并為企業(yè)提供參考。

1 RMFS描述

RMFS主要由揀選臺、可移動貨架、通道以及移動機器人組成,其布局如圖1所示。在“貨到人”揀選模式下,當倉庫管理系統(tǒng)接收到訂單后,按照訂單波次,系統(tǒng)使用一定的調(diào)度規(guī)則對任務進行一次性分配。在進行任務分配前,移動機器人的狀態(tài)是不明確的,任務可以分配給任意移動機器人完成。如果任務所分配的移動機器人處于忙碌狀態(tài),則需要等待該機器人完成任務后,再對分配任務進行搬運。移動機器人開始執(zhí)行任務(如圖1中空載標記位置)后,將按照任務序列對任務貨架進行依次搬運。在移動機器人任務執(zhí)行過程中,移動機器人首先會從初始位置移動到被分配任務所需要的貨架位置(如圖1中實線指向標號為1的貨架),再將貨架搬運至任務指定揀選臺(如圖1中實線指向揀選臺5),由揀選人員根據(jù)任務訂單商品信息對貨架上的商品進行揀選、完成掃描和打包。當系統(tǒng)中指定揀選臺被占用時,移動機器人會在指定的揀選臺進行排隊等待,直到被揀選完畢。移動機器人將貨架搬回存儲區(qū),在存儲區(qū)中選擇某一位置放回貨架(如圖1中星形標記位置),遵循不同貨架儲位再指派策略,移動機器人會將貨架放在不同空位上并在貨架下等待執(zhí)行下一任務的命令。

圖1 RMFS布局圖

2 RMFS任務分配與貨架儲位再指派聯(lián)合優(yōu)化的數(shù)學模型

2.1 聯(lián)合優(yōu)化問題描述

移動機器人運行時,根據(jù)移動機器人狀態(tài)不同可以分為重載(如圖1中重載標記)和空載(如圖1中空載標記)兩種狀態(tài)。不難發(fā)現(xiàn),移動機器人在完成揀選任務的過程中,重載與空載狀態(tài)是交替進行的,其中移動機器人行駛的重載距離包括移動機器人搬運貨架到揀選臺和從揀選臺返回到儲存區(qū)的兩段距離,空載距離為移動機器人接收到任務后,從所在地點前往所需搬運任務貨架地點之間的距離。移動機器人重載狀態(tài)需要托載沉重的貨架,因此重載與空載行駛能耗不同,為進一步減小移動機器人完成任務總成本,應細化移動機器人重載和空載成本差距。

在空載運行中,移動機器人行駛距離由移動機器人初始位置和任務位置決定;在重載運行中,移動機器人行駛距離由任務位置、揀選臺位置和返回存儲區(qū)位置決定。其中任務位置和揀選臺位置與訂單相關由管理信息系統(tǒng)指定,相對固定。而移動機器人初始位置與返回存儲區(qū)位置,由于在移動機器人即將完成當前任務列表時,新的任務列表會提前發(fā)放給移動機器人等待執(zhí)行,即除第一輪任務執(zhí)行開始外,移動機器人執(zhí)行不同輪次任務中的初始位置等于該移動機器人上一任務貨架返回位置,因此移動機器人初始位置和返回存儲區(qū)位置主要由貨架儲位再指派策略決定。

實際中常用的貨架儲位再指派策略主要有兩種,返回原位置策略和返回距離揀選臺最近位置策略,其中返回原位置策略(如圖1中藍色虛線所示,下文統(tǒng)一策略1表示),其是指將揀選完成后的貨架由移動機器人搬運至存儲貨架的原位置。返回距離揀選臺最近策略(如圖1中橙色虛線所示,下文統(tǒng)一用策略2表示),它是指將揀選完成的貨架由移動機器人搬運至距離揀選臺最近的空儲位上。本文研究提出了一種考慮任務分配的貨架儲位再指派策略(如圖1中紅色虛線所示,下文統(tǒng)一用策略3表示),當貨架完成揀選后,移動機器人根據(jù)其執(zhí)行的任務列表,將貨架放置在返回儲存區(qū)指派位置與到達任務列表中下一任務位置聯(lián)合距離最小的空儲位上。

對3種策略下移動機器人搬運貨架行駛距離進行算例討論,如圖1所示,對地圖進行柵格化處理后,將每一單位小格設置為1 個單位距離。移動機器人從初始位置搬運任務1到達揀選臺需要移動距離為21 個單位距離(如圖1中黑色實線行走距離),使用策略1下移動機器人從揀選臺到任務1返回位置再到達任務2需要移動33 個單位距離(如圖1中藍色虛線行走距離);使用策略2下移動機器人需要移動47 個單位距離(如圖1中橙色虛線行走距離),而使用策略3,機器人移動31 個單位距離(如圖1中紅色虛線行走距離),相較于前兩種策略,策略3有效地縮小了移動機器人的行駛距離,算例結(jié)果表明策略3對完成任務移動機器人行駛距離優(yōu)化效果最好。為驗證算例的通用性,建立以移動機器人完成任務總成本最小為目標,考慮移動機器人重載與空載成本差異,同時對任務分配及貨架儲位再分配位置進行決策的數(shù)學模型,對比3種策略的實驗結(jié)果。

2.2 模型假設

為便于模型的建立,做如下假設。

(1)第一次揀選任務下發(fā)之前移動機器人均處于空閑狀態(tài),并且隨機分布在系統(tǒng)中。

(2)任務下發(fā)后,所有移動機器人均在運行狀態(tài),不考慮移動機器人空閑成本。

(3)移動機器人在執(zhí)行搬運任務過程中電量始終保持充足。

(4)存儲區(qū)貨架儲位數(shù)多于貨架數(shù),即存在空余儲位。

(5)倉庫中的貨架規(guī)格相同。

(6)揀選臺有足夠的移動機器人等待空間。

(7)移動機器人的速度是恒定的,忽略移動機器人加速/減速。

(8)不考慮移動機器人起升貨架成本與轉(zhuǎn)彎成本。

(9)揀選臺服務遵循先到先服務原則。

(10)貨架商品數(shù)量滿足訂單揀選需求,不考慮缺貨情況。

(11)忽略移動機器人因避障等問題出現(xiàn)的距離增加情況。

2.3 數(shù)學模型建立

柵格化地圖后,距離計算適用于使用曼哈頓距離為

dRiZj=|xRi-xZj|+|yRi-yZj|

(1)

式(1)中:dRiZj為Ri移動機器人從初始位置到Zj任務貨架存儲點的距離;(xRi,yRi)為系統(tǒng)中Ri移動機器人的起始位置坐標;(xZj,yZj)為系統(tǒng)中Zj任務的位置坐標;R為移動機器人集;n為揀選系統(tǒng)移動機器人數(shù)量;Ri為揀選系統(tǒng)中第i個移動機器人,i={1,2,…,n};Z為任務集;m為揀選系統(tǒng)中任務的數(shù)量;Zj任務中的第j個任務,j={1,2,…,m}。

dZjPk=|xZj-xPk|+|yZj-yPk|

(2)

式(2)中:dZjPk為從Zj任務貨架存儲點到Pk揀選臺的距離;(xPk,yPk)為系統(tǒng)中Pk揀選工作臺的位置坐標;P為揀選臺集;p為揀選臺的數(shù)量;Pk為揀選系統(tǒng)中的第k個揀選臺,k={1,2,…,p}。

dPkSl=|xPk-xZjSl|+|yPk-yZjSl|

(3)

式(3)中:dPkSl為從揀選臺Pk到貨架指派位置Sl的距離(任務Zj所在的位置變化為指派的Sl位置);(xZjSl,yZjSl)為移動機器人搬運的任務Zj的貨架搬回貨位Sl位置坐標;Sl為存儲區(qū)第l個貨架儲位,l={1,2,…,s};S為貨架儲位集合;s為貨架儲位總數(shù)。

考慮機器人重空載差異的任務分配與貨架儲位再指派聯(lián)合優(yōu)化問題,機器人完成任務成本由兩部分組成:移動機器人空載成本和重載成本,因此,目標函數(shù)為

(dZjPk+dPkSl)c2}xijl

(4)

(5)

(6)

(7)

(8)

(9)

式中:C為移動機器人完成任務的總成本;c1為移動機器人行駛單位距離空載成本;c2為移動機器人行駛單位距離重載成本;xijl為決策變量,表示是否由移動機器人i完成任務j并搬運任務貨架返回第l個貨架儲位。

式(4)表示移動機器人完成所有任務花費的總成本最小;式(5)表示每個任務只能由一個移動機器人執(zhí)行;式(6)表示倉庫內(nèi)貨架儲位數(shù)量大于可移動貨架數(shù)量;式(7)表示每個移動機器人一次只能執(zhí)行一個任務;式(8)表示每個貨架只能被指派到一個儲位上;式(9)為決策變量取值約束。

通過求解上述規(guī)劃模型,不僅可以得到移動機器人任務分配結(jié)果,而且可以得到移動機器人返回儲位區(qū)的貨架再指派位置。

3 算法設計

任務分配與貨架儲位再指派聯(lián)合優(yōu)化問題是一個非確定性多項式完全問題(non-deterministic polynomial complete problem,NPC),并且涉及的數(shù)據(jù)量較大,很難在短時間內(nèi)通過直接求解方式得到問題的最優(yōu)解,本文研究根據(jù)此聯(lián)合優(yōu)化問題的特點,借助遺傳算法效率高、通用性和穩(wěn)定性好等優(yōu)點,設計求解算法。算法的具體求解過程如下。

步驟1采用實數(shù)編碼產(chǎn)生染色體如圖2所示,其中染色體上的基因位表示任務編號,長度為任務總數(shù);基因表示移動機器人編號。同時設定初始種群數(shù)量、交叉概率、變異概率和最大迭代次數(shù),確定使用移動機器人數(shù)量、完成任務數(shù)量。

圖2 染色體編碼

步驟2移動機器人完成任務總成本及貨架再指派位置計算。分別計算移動機器人行駛空載、重載距離、貨架再指派位置。重載距離中移動機器人搬運任務貨架到揀選臺的距離,利用任務坐標與揀選臺坐標可計算兩者之間的曼哈頓距離,而另一段重載距離即搬運貨架返回存儲區(qū)距離、空載距離和貨架再指派位置主要由不同貨架儲位再指派策略決定。

情況1策略1貨架完成揀選后由移動機器人將貨架搬運至原位置。從揀選臺返回存儲區(qū)距離和空載距離由上一任務位置坐標、本次執(zhí)行任務坐標以及揀選臺位置坐標計算得出。策略1中貨架再指派位置為原位置。

情況2策略2貨架完成任務后將返回至計算所有可選空儲位距離揀選臺最近的空儲位;策略3返回至計算所有可選空儲位中移動機器人搬運貨架返回選中空儲位與從該空儲位前往移動機器人任務列表中下一任務位置距離和最小的空儲位。在執(zhí)行任務和對應揀選臺由管理信息系統(tǒng)指定的情況下,移動機器人搬運貨架回儲存區(qū)距離和空載距離的大小均主要取決于選擇放回的貨架最優(yōu)儲位。兩段距離均由上一任務選中空位坐標、揀選臺位置坐標、本次執(zhí)行任務坐標、本次執(zhí)行任務選中空位坐標計算得出。

在情況2中,貨架最優(yōu)儲位的選擇是尤為重要的,移動機器人可選擇的貨架空儲位范圍需受移動機器人從揀選臺搬運貨架返回儲存區(qū)順序影響。因此移動機器人從揀選臺返回存儲區(qū)的順序即移動機器人在揀選臺等待揀選的隊列順序?qū)σ苿訖C器人返回儲存區(qū)行駛距離有重要作用。移動機器人返回順序計算規(guī)則設計如下。

忽略揀選人員揀選時間且使用移動機器人到達揀選臺行駛總距離升序作為移動機器人從揀選臺搬運貨架回儲存區(qū)的順序,所以可能出現(xiàn)距離相等、排序相同的情況。此時若所有移動機器人為第一次到達揀選臺(移動機器人到達揀選臺的距離設置為移動機器人從初始位置到任務位置再到揀選臺距離的總和),同樣距離的移動機器人可以隨機選擇進入揀選臺隊列順序,但當移動機器人第二次到達時(移動機器人到達揀選臺的距離設置為移動機器人上一次離開揀選臺到再次到達揀選臺之間的距離),若移動機器人到達揀選臺距離相同,移動機器人進入隊列的順序應受第一次從揀選臺返回順序的影響,此時同樣距離下,應該先執(zhí)行上一任務放回隊列中順序在前的移動機器人。因此為保證貨架空儲位選擇的有序進行,設置參數(shù)a,a∈[1,2,…,n],將移動機器人計算第二次達到揀選臺順序的未排序前行駛距離依次加上參數(shù)a,如圖3所示。(當移動機器人位于第一次到達揀選臺返回隊列首位,第一個計算再次到達揀選臺距離時,a=1;返回隊列中第二位移動機器人,a=2,依次類推),此時計算的移動機器人行駛距離將僅作為貨架放回存儲區(qū)順序使用;當計算移動機器人行駛總成本時使用未加和參數(shù)a的值進行計算。移動機器人按照上述計算所得順序有序進行空位選擇。

圖3 揀選臺排序計算規(guī)則示意圖

空儲位選擇規(guī)則如下:假設存在n臺移動機器人共同執(zhí)行任務,任務執(zhí)行最初,空位集合應為n臺移動機器人執(zhí)行任務空位加上開放儲位。根據(jù)上文得到的任務執(zhí)行過程中貨架在揀選臺的隊列,當位于揀選臺隊列首位移動機器人從揀選臺返回儲位區(qū)時,根據(jù)策略2、策略3的貨架返回空儲位的要求對空位進行選擇并存入選中空儲位集合。已知揀選臺位置、空位位置、移動機器人任務列表,能計算出揀選臺隊列中移動機器人搬運貨架存放的新空儲位。當移動機器人得到貨架儲位再指派策略下任務貨架應存放位置后,將在空位集合中扣除計算所得位置。新任務被搬運時,將添加新任務位置至空位集合。因此不難發(fā)現(xiàn)兩種貨架儲位再指派策略下的任務貨架新儲位集合順序與移動機器人的揀選臺隊列順序相對應。具體任務貨架新儲位、染色體、揀選臺隊列間的對應關系如圖4所示。

圖4 貨架返回位置與染色體關系示意圖

染色體的適應度值為移動機器人完成所有任務行駛總成本的倒數(shù),即步驟3遺傳操作。采用精英保留策略選擇一定數(shù)量適應度值高的優(yōu)良個體作為父代。為保證種群的多樣性,按照交叉概率進行交叉操作,選擇兩個父代個體,使兩條染色體上隨機一段基因進行交叉從而生成新的個體。按照變異概率對選擇個體進行變異操作;隨機選擇染色體上任意一位替換為所采用移動機器人任意序號。生成新種群,為了保證倉庫中移動機器人均參與任務執(zhí)行,將對選擇、交叉、變異后產(chǎn)生的群體進行篩選,將其中因變異產(chǎn)生的移動機器人缺失的極少數(shù)情況去除。設置最大迭代次數(shù),若程序執(zhí)行已達到最大迭代數(shù)則停止迭代,輸出最終結(jié)果,形成染色體與任務返回位置對應關系。若未達到迭代次數(shù)則返回步驟2繼續(xù)執(zhí)行。

(10)

4 算例分析

4.1 算例描述

為了驗證本文模型的有效性,設典型倉庫揀選區(qū)域面積為50 m×50 m,將區(qū)域地圖進行柵格化處理并建立直角坐標系,取單位距離為1 m,標記左下角第一個位置坐標設置為(0,0),其中第一個數(shù)值為其所在列,第二個數(shù)值為其所在行。揀選臺坐標設定為(24,5)。柵格化揀選區(qū)域布局如圖1所示。

通過調(diào)研方式得到6 組目前應用較廣泛的移動機器人數(shù)據(jù)如表1所示。

表1 移動機器人調(diào)查參數(shù)

參考表2中行業(yè)數(shù)據(jù),選取典型移動機器人參數(shù):固定成本98 000 元,功率1 000 w,移動機器人充電時間3 h,空載續(xù)航12 h,重載續(xù)航8 h,空載使用年限12 a,重載使用年限10 a。電費為每千瓦時0.86 元計算,由移動機器人充電時間、功率、重空載續(xù)航時間、可知系統(tǒng)中每臺移動機器人每秒空載耗電為0.000 06 元,每秒重載耗電為0.000 09 元。從移動機器人固定成本與重空載使用年限可知系統(tǒng)中每臺移動機器人空載年折損為8 167 元,重載年折損為9 800 元,每秒空載折損為0.000 26 元,每秒重載折損為0.000 31 元,移動機器人行駛速度為1 m/s,由此可得,移動機器人空載單位總成本c1為0.000 32 元,重載單位總成本c2為0.000 40 元,如表2所示。

表2 實驗參數(shù)設定

根據(jù)歷史訂單采用二八原則抽取任務,即任務所需貨架80 %為中高熱度貨架,20 %為低熱度貨架。60 個任務坐標如表3所示。隨機產(chǎn)生10 臺移動機器人初始坐標{1(10,13)、2(26,13)、3(39,27)、4(3,34)、5(2,28)、6(3,45)、7(23,41)、8(14,24)、9(6,20)、10(26,27)}。設定倉庫存在10 個額外空儲位,空儲位坐標為{(31,23)、(39,29)、(22,31)、(11,34)、(19,41)、(15,13)、(39,15)、(43,22)、(11,21)、(31,34)}。

表3 任務坐標

4.2 算例結(jié)果

在MATLAB R2017a環(huán)境下實現(xiàn)本文提出的啟發(fā)式算法的仿真程序,在WIN1064Bit操作系統(tǒng)下進行實驗,設置初始種群個數(shù)600 個,交叉概率與變異概率分別為0.9和0.8。設置最大迭代次數(shù)800 次。運行10 次選取最優(yōu)實驗結(jié)果如圖5所示。其實驗結(jié)果迭代圖如圖6 (c)所示。

貨架內(nèi)的編號表示任務編號;紅色編號表示任務執(zhí)行后指派位置為原位置;黑色編號表示任務執(zhí)行后新的指派位置

圖6 3種策略下的移動機器人完成任務成本迭代圖

基于實際數(shù)據(jù)進行3種策略下移動機器人完成任務成本對比實驗。3種策略下均進行10 次運行,取其實驗結(jié)果中最小值作為最終結(jié)果。實驗結(jié)果迭代圖和移動機器人調(diào)度結(jié)果如圖6和圖7所示。為進一步對比結(jié)果,以4 號移動機器人為例描繪3種策略下移動機器人行駛路徑和貨架儲位再指派結(jié)果,如圖8所示。從圖7和圖8中可以看出采用不同的貨架再指派策略將會得到不同的任務分配結(jié)果和貨架返回位置。

圖7 三種策略下移動機器人調(diào)度結(jié)果

圖8 4號移動機器人三種策略下執(zhí)行任務行駛路線及貨架再指派結(jié)果

策略3下移動機器人完成任務成本為1.679 3 元,策略2下移動機器人完成任務成本為1.794 4 元,而策略1下移動機器人完成任務成本為1.792 3 元(圖6)。策略3優(yōu)于另兩種策略。為進一步驗證本文所提聯(lián)合優(yōu)化策略的優(yōu)越性,再次生成10 批60 個任務,分別得到3種策略下移動機器人運行成本,對結(jié)果進行降序排序,得出如圖9所示的運行成本對比圖。從圖9中看出,本文所提策略3總成本最低,結(jié)果最優(yōu)。

圖9 3種策略移動機器人完成任務成本對比圖

4.3 結(jié)果分析

4.3.1 不同優(yōu)化目標下的實驗結(jié)果對比分析

在移動機器人調(diào)度與貨架儲位再指派問題研究中,數(shù)學模型多為以移動機器人完成任務行駛距離最小為目標和以移動機器人完成任務成本最小為目標兩種,其中以成本最小為目標計算多使用距離乘統(tǒng)一的單位行駛距離成本得到,但實際在移動機器人完成任務過程中,移動機器人有兩種運行狀態(tài):空載和重載,其兩者間能耗存在差距,移動機器人完成任務成本的計算應該考慮移動機器人能耗差距帶來的單位成本變化。因此,本文構(gòu)建考慮移動機器人重空載成本差距因素的以移動機器人完成任務成本最小為目標的數(shù)學模型,同時設計實驗與以移動機器人完成任務行駛距離最小為目標下移動機器人完成任務成本情況進行對比,實驗設計了考慮貨架儲位再指派策略和額外空儲位因素的如下5種情況,情況1:有額外空儲位采用策略3;情況2:策略1;情況3:有額外空儲位采用策略2;情況4:無額外空儲位采用策略3;情況5:無額外空儲位采用策略2。

應用表3任務數(shù)據(jù)進行10 次實驗,選擇實驗結(jié)果中最小值。實驗結(jié)果顯示,5種情況下,情況5移動機器人完成任務成本最大,為1.884 5 元?；诖似溆?種情況成本降低百分比和成本值對比圖,如圖10所示。

圖10 不同優(yōu)化目標下成本值及基于情況5成本下降百分比對比圖

圖10中兩種優(yōu)化目標下,存在額外空儲位因素下以移動機器人完成任務總成本最低為目標成本優(yōu)化效果最好。3種策略移動機器人完成任務成本優(yōu)化效果排序為策略3優(yōu)于策略1優(yōu)于策略2。

4.3.2 極端任務分析

實際倉庫運作過程中,揀選訂單因銷售策略、市場客戶需求的多變性而具有不確定性,可能出現(xiàn)訂單任務所在貨架位置相對集中的情況。因此設計任務貨架集中分布情況下,幾種貨架儲位再指派策略對比實驗。

根據(jù)倉庫實際運行情況,貨架可能出現(xiàn)的集中情況歸納為兩類:倉庫布局適宜當前市場需求變化時任務貨架集中靠近揀選臺一側(cè),和倉庫布局與當前市場需求變化情況存在偏差,倉庫即將根據(jù)季節(jié)、需求變動進行倉庫重新布局時,任務貨架集中遠離揀選臺一側(cè)兩類。

在極端任務情況下,同時考慮不同移動機器人運行極端參數(shù),根據(jù)實際調(diào)研的移動機器人運行參數(shù),歸納為3 種:重空載成本差距極大L、重空載成本差距一般M和重空載成本差距極小S,具體參數(shù)如表4所示。

表4 移動機器人運行參數(shù)

對移動機器人不同重空載單位成本、極端任務分布和應用的貨架儲位再指派策略組合設計實驗,產(chǎn)生了12 組對比情況,如圖11所示。

圖11 極端任務實驗分組圖

對圖11中12 組情況設置10 組任務進行實驗,將結(jié)果降序排列后,結(jié)果如圖12所示。由圖12得到本文提出的聯(lián)合優(yōu)化策略,在3種重空載成本差距情況下,任務貨架集中遠離揀選臺分布與任務貨架集中靠近揀選臺分布,優(yōu)化效果均優(yōu)于另兩種策略。對比圖12中另外兩種策略,在M、S成本差距情況下,無關任務貨架分布情況,返回原位置策略優(yōu)于返回距離揀選臺最近位置策略,移動機器人完成任務成本更低。但當成本差距情況為L時,任務貨架集中遠離揀選臺分布時,返回距離揀選臺最近策略與返回原位置策略移動機器人使用成本相差較小。

圖12 極端任務實驗成本對比圖

5 結(jié)論

研究了RMFS下考慮移動機器人重空載成本差距的任務分配與貨架儲位再指派的聯(lián)合優(yōu)化問題,建立了以移動機器人完成任務總成本最小為目標的數(shù)學模型,設計了求解模型的啟發(fā)式算法,并與傳統(tǒng)的返回原位置和返回距離揀選臺最近位置策略進行了實驗對比,得到以下結(jié)論。

(1)本文提出的任務分配與貨架儲位再指派聯(lián)合優(yōu)化策略移動機器人完成任務成本更低,效率更高。

(2)貨架儲存區(qū)存在開放儲位時,移動機器人完成任務成本更小。

(3)無關任務分布和移動機器人重空載成本差距大小情況,聯(lián)合優(yōu)化策略均具有完成任務總成本最低特征。

在大部分情況下,返回原位置策略移動機器人完成任務總成本均低于返回距離揀選臺最近策略。該結(jié)果對不同貨架布局和移動機器人規(guī)格下的貨架儲位再指派策略選擇具有一定的指導作用。

由于RMFS優(yōu)化問題影響因素的復雜性,后續(xù)將考慮貨架周轉(zhuǎn)率變化對貨架位置的影響,周轉(zhuǎn)率高的貨架存放在距離揀選臺較遠的位置將會造成移動機器人行駛距離增大,進而增加移動機器人運行總成本。結(jié)合實際,在聯(lián)合優(yōu)化問題中考慮貨架周轉(zhuǎn)率,進一步提高揀選效率。