李騰, 張茹蘭, 丁佩佩

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

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

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

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

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

1 RMFS描述

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

圖1 RMFS布局圖

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

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

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

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

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

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

2.2 模型假設(shè)

為便于模型的建立,做如下假設(shè)。

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

(2)任務(wù)下發(fā)后,所有移動(dòng)機(jī)器人均在運(yùn)行狀態(tài),不考慮移動(dòng)機(jī)器人空閑成本。

(3)移動(dòng)機(jī)器人在執(zhí)行搬運(yùn)任務(wù)過程中電量始終保持充足。

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

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

(6)揀選臺(tái)有足夠的移動(dòng)機(jī)器人等待空間。

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

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

(9)揀選臺(tái)服務(wù)遵循先到先服務(wù)原則。

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

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

2.3 數(shù)學(xué)模型建立

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

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

(1)

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

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

(2)

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

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

(3)

式(3)中:dPkSl為從揀選臺(tái)Pk到貨架指派位置Sl的距離(任務(wù)Zj所在的位置變化為指派的Sl位置);(xZjSl,yZjSl)為移動(dòng)機(jī)器人搬運(yùn)的任務(wù)Zj的貨架搬回貨位Sl位置坐標(biāo);Sl為存儲(chǔ)區(qū)第l個(gè)貨架儲(chǔ)位,l={1,2,…,s};S為貨架儲(chǔ)位集合;s為貨架儲(chǔ)位總數(shù)。

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

(dZjPk+dPkSl)c2}xijl

(4)

(5)

(6)

(7)

(8)

(9)

式中:C為移動(dòng)機(jī)器人完成任務(wù)的總成本;c1為移動(dòng)機(jī)器人行駛單位距離空載成本;c2為移動(dòng)機(jī)器人行駛單位距離重載成本;xijl為決策變量,表示是否由移動(dòng)機(jī)器人i完成任務(wù)j并搬運(yùn)任務(wù)貨架返回第l個(gè)貨架儲(chǔ)位。

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

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

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

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

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

圖2 染色體編碼

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

情況1策略1貨架完成揀選后由移動(dòng)機(jī)器人將貨架搬運(yùn)至原位置。從揀選臺(tái)返回存儲(chǔ)區(qū)距離和空載距離由上一任務(wù)位置坐標(biāo)、本次執(zhí)行任務(wù)坐標(biāo)以及揀選臺(tái)位置坐標(biāo)計(jì)算得出。策略1中貨架再指派位置為原位置。

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

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

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

圖3 揀選臺(tái)排序計(jì)算規(guī)則示意圖

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

圖4 貨架返回位置與染色體關(guān)系示意圖

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

(10)

4 算例分析

4.1 算例描述

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

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

表1 移動(dòng)機(jī)器人調(diào)查參數(shù)

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

表2 實(shí)驗(yàn)參數(shù)設(shè)定

根據(jù)歷史訂單采用二八原則抽取任務(wù),即任務(wù)所需貨架80 %為中高熱度貨架,20 %為低熱度貨架。60 個(gè)任務(wù)坐標(biāo)如表3所示。隨機(jī)產(chǎn)生10 臺(tái)移動(dòng)機(jī)器人初始坐標(biāo){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)}。設(shè)定倉庫存在10 個(gè)額外空儲(chǔ)位,空儲(chǔ)位坐標(biāo)為{(31,23)、(39,29)、(22,31)、(11,34)、(19,41)、(15,13)、(39,15)、(43,22)、(11,21)、(31,34)}。

表3 任務(wù)坐標(biāo)

4.2 算例結(jié)果

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

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

圖6 3種策略下的移動(dòng)機(jī)器人完成任務(wù)成本迭代圖

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

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

圖8 4號(hào)移動(dòng)機(jī)器人三種策略下執(zhí)行任務(wù)行駛路線及貨架再指派結(jié)果

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

圖9 3種策略移動(dòng)機(jī)器人完成任務(wù)成本對比圖

4.3 結(jié)果分析

4.3.1 不同優(yōu)化目標(biāo)下的實(shí)驗(yàn)結(jié)果對比分析

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

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

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

圖10中兩種優(yōu)化目標(biāo)下,存在額外空儲(chǔ)位因素下以移動(dòng)機(jī)器人完成任務(wù)總成本最低為目標(biāo)成本優(yōu)化效果最好。3種策略移動(dòng)機(jī)器人完成任務(wù)成本優(yōu)化效果排序?yàn)椴呗?優(yōu)于策略1優(yōu)于策略2。

4.3.2 極端任務(wù)分析

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

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

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

表4 移動(dòng)機(jī)器人運(yùn)行參數(shù)

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

圖11 極端任務(wù)實(shí)驗(yàn)分組圖

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

圖12 極端任務(wù)實(shí)驗(yàn)成本對比圖

5 結(jié)論

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

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

(2)貨架儲(chǔ)存區(qū)存在開放儲(chǔ)位時(shí),移動(dòng)機(jī)器人完成任務(wù)成本更小。

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

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

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