移動(dòng)貨架倉(cāng)庫(kù)中搬運(yùn)機(jī)器人優(yōu)化調(diào)度模型與算法

楊吉威, 王 征, 王藝雪, 李延通

(大連海事大學(xué) 航運(yùn)經(jīng)濟(jì)與管理學(xué)院,遼寧 大連 116025)

1 引言

近年來(lái),基于搬運(yùn)機(jī)器人的電商倉(cāng)庫(kù)在很多大型電商物流中心得到了廣泛應(yīng)用,該類倉(cāng)庫(kù)可以靈活、準(zhǔn)確地應(yīng)對(duì)電商訂單“一單多品”的分揀特征,通過(guò)“機(jī)器換人”的方式推動(dòng)了傳統(tǒng)物流業(yè)由勞動(dòng)密集型向技術(shù)密集型轉(zhuǎn)變,促進(jìn)了物流工程領(lǐng)域現(xiàn)代化、智能化的轉(zhuǎn)型升級(jí)。該類倉(cāng)庫(kù)中,訂單、商品、貨架、揀貨臺(tái)以及機(jī)器人之間的復(fù)雜關(guān)聯(lián)關(guān)系使揀貨作業(yè)的調(diào)度非常復(fù)雜。面對(duì)大規(guī)模電商訂單和多樣化商品需求,如何調(diào)度好搬運(yùn)機(jī)器人,發(fā)揮出該類倉(cāng)庫(kù)面向電商訂單的分揀效率優(yōu)勢(shì),提升顧客滿意度,是該類倉(cāng)庫(kù)運(yùn)營(yíng)管理中亟待解決的關(guān)鍵問(wèn)題,也是電商物流企業(yè)實(shí)施物流工程管理的關(guān)鍵要素。

關(guān)于移動(dòng)貨架倉(cāng)庫(kù)中搬運(yùn)機(jī)器人優(yōu)化調(diào)度問(wèn)題,國(guó)內(nèi)外學(xué)者近年來(lái)進(jìn)行了前沿的學(xué)術(shù)研究,取得一定的研究進(jìn)展。代表性成果包括:Zou等[1]提出了基于揀貨臺(tái)處理速度的機(jī)器人分配規(guī)則,構(gòu)建了半開放排隊(duì)網(wǎng)絡(luò)并使用兩階段近似方法進(jìn)行性能評(píng)估。Roy等[2]基于多類封閉排隊(duì)網(wǎng)絡(luò)模型開發(fā)了程式化的績(jī)效評(píng)估模型。Gharehgozli和Zaerpour[3]將機(jī)器人調(diào)度問(wèn)題表述為非對(duì)稱旅行商問(wèn)題,通過(guò)添加顧客訂單優(yōu)先級(jí)約束來(lái)擴(kuò)展模型。袁瑞萍等[4]通過(guò)對(duì)電商物流配送中心訂單揀選作業(yè)流程分析,提出多揀選臺(tái)同步和異步揀選兩種作業(yè)模式,建立了兩種揀選模式下的機(jī)器人調(diào)度模型。李騰和馮珊[5]提出了在分批下發(fā)訂單任務(wù)情況下的一種隨機(jī)調(diào)度策略。Boysen等[6]針對(duì)揀貨臺(tái)訂單排序問(wèn)題建立了混合整數(shù)規(guī)劃模型,并與先到先得訂單排序規(guī)則進(jìn)行了比較。Xie等[7]針對(duì)多揀貨臺(tái)的訂單分配和貨架選擇問(wèn)題建立了數(shù)學(xué)模型。Valle和Beasley[8]針對(duì)訂單和貨架分配給揀貨員的問(wèn)題提出兩種數(shù)學(xué)方法,為揀貨臺(tái)的貨架排序問(wèn)題建立整數(shù)規(guī)劃模型。

在現(xiàn)實(shí)環(huán)境中,機(jī)器人搬運(yùn)貨架可能會(huì)在多揀貨臺(tái)間移動(dòng)后才將貨架送回,多揀貨臺(tái)會(huì)使機(jī)器人調(diào)度更加復(fù)雜,這需額外考慮揀貨臺(tái)與貨架、訂單等的匹配。有些研究雖考慮了多揀貨臺(tái)的情況,但又未將機(jī)器人調(diào)度與訂單、揀貨臺(tái)的匹配關(guān)系相結(jié)合;而電商訂單的揀貨中,訂單與揀貨臺(tái)的匹配關(guān)系決定了貨架與揀貨臺(tái)的匹配關(guān)系,進(jìn)而決定了機(jī)器人搬運(yùn)貨架所應(yīng)停留的揀貨臺(tái)位置及其調(diào)度策略。由于該問(wèn)題涉及到訂單揀貨任務(wù)分配、貨架服務(wù)順序、揀貨臺(tái)工作安排及機(jī)器人任務(wù)安排等諸多復(fù)雜環(huán)節(jié),因此該問(wèn)題的解決極具挑戰(zhàn)。為此,本文針對(duì)這一問(wèn)題,綜合考慮多個(gè)復(fù)雜環(huán)節(jié),以揀貨時(shí)間最小化為目標(biāo)建立了包含多揀貨臺(tái)的混合整數(shù)規(guī)劃模型,設(shè)計(jì)了問(wèn)題的啟發(fā)式求解算法,通過(guò)實(shí)驗(yàn)驗(yàn)證了模型和算法的有效性。

2 問(wèn)題描述及模型建立

2.1 問(wèn)題描述

移動(dòng)貨架倉(cāng)庫(kù)通常由揀貨區(qū)、存儲(chǔ)區(qū)、入庫(kù)區(qū)、出庫(kù)區(qū)等組成。倉(cāng)庫(kù)地形可柵格化處理,形成如圖1的二維平面。機(jī)器人行走方向只能為橫向或縱向,所以每個(gè)貨架、每個(gè)揀貨臺(tái)間的距離采用曼哈頓方法計(jì)算。

圖1 移動(dòng)貨架倉(cāng)庫(kù)平面示意圖

分揀系統(tǒng)中,某時(shí)段需要針對(duì)一個(gè)波次的一批訂單而揀貨。根據(jù)實(shí)際倉(cāng)庫(kù)對(duì)訂單的揀選規(guī)則,任意訂單都需要分配給唯一揀貨臺(tái)處理,以便對(duì)其商品進(jìn)行合并打包[9]。一批訂單中,每個(gè)都有不同的商品,這些商品大多分布在不同的貨架上。訂單下達(dá)后,多個(gè)機(jī)器人同時(shí)從起點(diǎn)出發(fā),將相應(yīng)貨架搬運(yùn)到揀貨臺(tái),在揀貨員按訂單指示從貨架上拾取對(duì)應(yīng)商品后,機(jī)器人將貨架運(yùn)回原位,再搬運(yùn)下一個(gè)貨架。貨架在每次搬運(yùn)過(guò)程中可能分別需要在多個(gè)揀貨臺(tái)接受服務(wù)。機(jī)器人完成所有貨架搬運(yùn)任務(wù)后,回到起點(diǎn)。本文將機(jī)器人每搬運(yùn)一個(gè)貨架并最終搬回貨架原位置稱為其執(zhí)行一次任務(wù)。

本文需確定訂單到揀貨臺(tái)的分配方案,并指定每個(gè)機(jī)器人搬運(yùn)哪些貨架及其搬運(yùn)順序,同時(shí)給出貨架在多個(gè)揀貨臺(tái)服務(wù)的先后順序,以盡量減少貨架在揀貨臺(tái)的等待時(shí)間及機(jī)器人的行走時(shí)間等,實(shí)現(xiàn)總揀貨時(shí)間的最小化。

為抽象問(wèn)題本質(zhì),將問(wèn)題進(jìn)行如下假設(shè):

(1)機(jī)器人勻速移動(dòng),其空載和重載速度一致[10]。

(2)機(jī)器人在電量充滿的情況下開始工作,在處理一批訂單的過(guò)程中電量足夠。

(3)根據(jù)實(shí)際情況,需要搬運(yùn)的貨架數(shù)遠(yuǎn)大于機(jī)器人數(shù)。

(4)機(jī)器人在倉(cāng)庫(kù)中任意兩個(gè)位置的行駛距離已知。

(5)揀貨員揀選每一單位商品(SKU)的時(shí)間恒定[9]。

2.2 模型建立

本節(jié)針對(duì)搬運(yùn)機(jī)器人調(diào)度問(wèn)題建立混合整數(shù)規(guī)劃模型,該模型涉及變量和參數(shù)分別見表1和2。

表1 變量及其說(shuō)明

表2 參數(shù)及其說(shuō)明

根據(jù)問(wèn)題定義,機(jī)器人完成所有任務(wù)的時(shí)長(zhǎng)取決于消耗時(shí)間最長(zhǎng)的機(jī)器人。所以問(wèn)題目標(biāo)為最小化所有機(jī)器人揀貨時(shí)間中的最大值。基于問(wèn)題描述和變量定義,構(gòu)建下述混合整數(shù)規(guī)劃(mixed integer programming,MIP)模型,其中M為很大的常數(shù)。

minT

(1)

s.t.T≥ril+pil+til+ti,i∈C,l∈E

(2)

(3)

(4)

(5)

(6)

(7)

ril≥si+til+(Yil-1)M,i∈C,l∈E

(8)

(9)

(10)

rjl≥ril+pil+(qijl-1)M,i,j∈C且i≠j,l∈E

(11)

rim≥ril+pil+tlm+(ylmi-1)M,i∈C,l,m∈E且l≠m

(12)

(13)

(14)

qiil=0,i∈C,l∈E

(15)

(16)

(17)

ylli=0,i∈C,l∈E

(18)

Yil+Yjl≥2(qijl+qjil),i,j∈C,i≠j,l∈E

(19)

(Yil+Yjl-2)M+1≤qijl+qjil≤1,i,j∈C,i≠j,l∈E

(20)

Yil+Yim≥2(ylmi+ymli),i∈C,l,m∈E,l≠m

(21)

(Yil+Yim-2)M+1≤ylmi+ymli≤1,i∈C,l,m∈E,l≠m

(22)

其中(2)式為對(duì)總時(shí)間T的表示;(3)、(4)式表示所有機(jī)器人都從起點(diǎn)出發(fā),最后回到起點(diǎn);(5)～(7)式表示貨架的出入度相等且都為1;(8)式表示貨架開始移動(dòng)時(shí)間與其在揀貨臺(tái)的開始服務(wù)時(shí)間的關(guān)系;(9)式表示被同一機(jī)器人所搬運(yùn)的貨架間,后一個(gè)貨架的開始移動(dòng)時(shí)間與前一個(gè)貨架的開始服務(wù)時(shí)間的關(guān)系;(10)式表示若貨架j為起始搬運(yùn)貨架,則sj≥tj;(11)式表示若揀貨臺(tái)l服務(wù)貨架i、j,貨架i、j在該揀貨臺(tái)的開始服務(wù)時(shí)間的關(guān)系;(12)式表示貨架在需要被服務(wù)的不同揀貨臺(tái)上開始服務(wù)時(shí)間的關(guān)系;(13)式計(jì)算貨架i在揀貨臺(tái)l的服務(wù)時(shí)長(zhǎng);(14)式表示每個(gè)訂單只能在唯一的揀貨臺(tái)上處理;(15)式表示揀貨臺(tái)不能重復(fù)服務(wù)同一個(gè)貨架;(16)、(17)式表示若貨架i上有訂單h中的商品,且訂單h在揀貨臺(tái)l上處理,則Yil為1,否則為0;(18)式表示貨架不能重復(fù)在同一個(gè)揀貨臺(tái)服務(wù);(19)～(22)式給出了變量之間的關(guān)系。

若揀貨臺(tái)僅有一個(gè),且貨架被運(yùn)至揀貨臺(tái)時(shí)無(wú)需排隊(duì)即可很快完成揀選;可將貨架視為“顧客”,機(jī)器人視為“車輛”,機(jī)器人搬運(yùn)任務(wù)視為“車輛對(duì)顧客的服務(wù)”;則該問(wèn)題可簡(jiǎn)化為“多輛車從起點(diǎn)出發(fā)服務(wù)不同位置的多個(gè)顧客后再回到起點(diǎn),以最小化服務(wù)完成時(shí)間”,該問(wèn)題即轉(zhuǎn)化為車輛路徑問(wèn)題(vehicle routing problem,VRP)。由于VRP已被證明為NP-hard,因此本文問(wèn)題同樣具有NP-hard特性。

3 問(wèn)題分析

移動(dòng)貨架倉(cāng)庫(kù)搬運(yùn)機(jī)器人調(diào)度問(wèn)題包含如下待優(yōu)化子問(wèn)題:

(1)倉(cāng)庫(kù)中存在多個(gè)機(jī)器人以及多個(gè)待搬運(yùn)貨架,這就涉及到機(jī)器人與貨架的匹配,需確定哪臺(tái)機(jī)器人搬運(yùn)哪些貨架。

(2)機(jī)器人搬運(yùn)完一個(gè)貨架后,要移動(dòng)到下一個(gè)需搬運(yùn)貨架的位置。由于貨架原本位置間距離不同,搬運(yùn)貨架的先后順序會(huì)直接影響機(jī)器人行駛路徑的長(zhǎng)短,從而影響分揀效率。

(3)倉(cāng)庫(kù)通常有多個(gè)揀貨臺(tái)同時(shí)揀貨,而每個(gè)訂單的多個(gè)商品又可能分布在多個(gè)貨架上,一旦訂單分配給某個(gè)揀貨臺(tái),則該訂單相關(guān)的多個(gè)貨架都要運(yùn)送至該揀貨臺(tái)。面對(duì)多個(gè)訂單及其關(guān)聯(lián)的大量貨架,如何將訂單合理分配給揀貨臺(tái)才能均衡各個(gè)揀貨臺(tái)的任務(wù)量,從而降低揀貨時(shí)間,是需考慮的另一個(gè)子問(wèn)題。

(4)由于一個(gè)貨架在一次搬運(yùn)過(guò)程中可能需要訪問(wèn)多個(gè)揀貨臺(tái),而不同揀貨臺(tái)之間的距離也往往不同,所以貨架針對(duì)多個(gè)揀貨臺(tái)訪問(wèn)順序也將影響機(jī)器人的行駛路徑長(zhǎng)短,從而影響分揀效率。

(5)如果調(diào)度不佳,會(huì)出現(xiàn)在某個(gè)揀貨臺(tái)的前一個(gè)貨架尚未被服務(wù)完、后一個(gè)貨架就到達(dá)的情況,這就使機(jī)器人在揀貨臺(tái)處產(chǎn)生了等待,影響分揀效率。

在以最小化系統(tǒng)揀選時(shí)間為目標(biāo)的情況下,以上所有決策都相互關(guān)聯(lián)、相互影響,單獨(dú)優(yōu)化任意決策得到的結(jié)果,都不是整個(gè)問(wèn)題本身的最優(yōu)結(jié)果,需將所有決策統(tǒng)籌考慮,這就造成整個(gè)問(wèn)題十分復(fù)雜。且該問(wèn)題現(xiàn)實(shí)中的貨架數(shù)較多,單純利用模型或精確算法來(lái)求解是不現(xiàn)實(shí)的。針對(duì)這一問(wèn)題,考慮先進(jìn)行局部?jī)?yōu)化,在可行情況下對(duì)上述決策進(jìn)行分步求解,再合并計(jì)算最終結(jié)果。基于這種思路,本文設(shè)計(jì)了啟發(fā)式算法。

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

4.1 基于規(guī)則的啟發(fā)式算法 (rule-based heuristic,RBH)

本文首先設(shè)計(jì)一種基于規(guī)則的啟發(fā)式算法,其將決策分為兩階段進(jìn)行。由于多揀貨臺(tái)的條件極大地增加了問(wèn)題復(fù)雜性,所以在第一階段先假設(shè)只有一個(gè)揀貨臺(tái),確定機(jī)器人與貨架的關(guān)系,包括每個(gè)機(jī)器人都搬運(yùn)哪些貨架及其搬運(yùn)順序;第二階段考慮多揀貨臺(tái),通過(guò)將訂單分配給揀貨臺(tái),確定貨架與揀貨臺(tái)的關(guān)系,包括每個(gè)貨架都需經(jīng)過(guò)哪些揀貨臺(tái)及其經(jīng)過(guò)的順序。各算法關(guān)系如圖2所示。

圖2 算法關(guān)系圖

4.1.1 第一階段:機(jī)器人與貨架的關(guān)系

第一階段采用貪婪思想確定每個(gè)機(jī)器人的任務(wù)安排,具體步驟如下:

第1步初始時(shí),將K臺(tái)機(jī)器人放入閑置機(jī)器人隊(duì)列φ中。

第2步從φ首部取出一個(gè)機(jī)器人,為其分配與它距離最近的貨架,執(zhí)行第3、4步完成一次搬運(yùn)任務(wù)。若所有貨架都已搬運(yùn)完成,則所有機(jī)器人回到起點(diǎn),本算法結(jié)束。

第3步若機(jī)器人到揀貨臺(tái)時(shí),揀貨臺(tái)空閑,則立即對(duì)貨架開始服務(wù);否則等待揀貨臺(tái)空閑時(shí)再開始服務(wù)。若該貨架影響到其他貨架在揀貨臺(tái)的服務(wù)時(shí)間,則更新受影響貨架的揀貨臺(tái)服務(wù)時(shí)間。

第4步貨架在揀貨臺(tái)服務(wù)完畢后,機(jī)器人將其搬回原位,將該機(jī)器人加入φ尾部,轉(zhuǎn)入第2步。

4.1.2 第二階段:貨架與揀貨臺(tái)的關(guān)系

每個(gè)訂單的商品可能需從多個(gè)貨架中揀貨,這些貨架都應(yīng)送往一個(gè)揀貨臺(tái),以便訂單商品的打包。因此,訂單與揀貨臺(tái)的匹配關(guān)系決定了貨架與揀貨臺(tái)的匹配關(guān)系。

第二階段設(shè)計(jì)一種啟發(fā)式規(guī)則確定訂單與揀貨臺(tái)的匹配關(guān)系,基本原則是盡可能將相似的訂單分配到同一揀貨臺(tái)。根據(jù)這一原則,首先根據(jù)訂單商品所關(guān)聯(lián)的貨架,將訂單與貨架匹配,然后計(jì)算任意兩個(gè)訂單涉及的相同貨架數(shù),并倒序排序,取出前a組訂單,將每組訂單隨機(jī)分配給一個(gè)揀貨臺(tái),a的取值根據(jù)訂單數(shù)及揀貨臺(tái)數(shù)而定。這種做法在一定程度上避免了貨架過(guò)多奔波于揀貨臺(tái)之間。最后,將未分配的訂單單獨(dú)隨機(jī)分配給揀貨臺(tái),以避免將訂單“扎堆”安排給同一揀貨臺(tái)。

根據(jù)訂單與揀貨臺(tái)的匹配情況確定貨架與揀貨臺(tái)的匹配。按最近鄰原則,確定貨架經(jīng)過(guò)多個(gè)揀貨臺(tái)的順序。合并兩階段結(jié)果,得到完整調(diào)度方案。

4.2 基于模型的數(shù)學(xué)啟發(fā)式算法

數(shù)學(xué)啟發(fā)式算法基本思想是通過(guò)捕獲問(wèn)題的性質(zhì)和特征,將數(shù)學(xué)模型與啟發(fā)式方法相結(jié)合[11]。目前數(shù)學(xué)啟發(fā)式算法已成功應(yīng)用于解決復(fù)雜的大規(guī)模組合優(yōu)化問(wèn)題[12]。

4.2.1 基本形式的數(shù)學(xué)啟發(fā)式算法(matheuristic,MH)

本節(jié)算法將原問(wèn)題分解為主問(wèn)題與子問(wèn)題。主問(wèn)題優(yōu)化訂單與揀貨臺(tái)匹配、貨架經(jīng)過(guò)多個(gè)揀貨臺(tái)的順序及機(jī)器人與貨架的匹配;子問(wèn)題優(yōu)化機(jī)器人移動(dòng)貨架順序。基本思路是首先根據(jù)4.1.1節(jié)算法確定總體貨架移動(dòng)順序,存入集合U中,并設(shè)定變量wik表示貨架i與機(jī)器人k的匹配關(guān)系,這樣可以暫時(shí)不考慮2.2節(jié)模型中的復(fù)雜變量xijk。簡(jiǎn)化后的問(wèn)題構(gòu)成主問(wèn)題。將每個(gè)機(jī)器人的貨架移動(dòng)順序放在子問(wèn)題中單獨(dú)優(yōu)化。

相比于2.2節(jié)原問(wèn)題的模型,主問(wèn)題增加了表3的變量和約束(23)～(28)式。

表3 主問(wèn)題變量

(23)

si≥sik+(wik-1)M,i∈U

(24)

ril≥rilk+(wik-1)M,i∈U

(25)

sjk≥tjwik,j∈U

(26)

rilk≥sik+tilwik+(Yil-1)M,i∈U,l∈E

(27)

sjk≥rilk+pil+(til+tij)wik,j>i∈U,l∈E

(28)

主問(wèn)題模型目標(biāo)函數(shù)為(1)式,約束為(2)式、(11)～(22)式、(23)～(28)式。其中(23)式表示每個(gè)貨架只能被一個(gè)機(jī)器人搬運(yùn);(24)式描述變量sik與si之間的關(guān)系;(25)式描述變量rilk與ril之間的關(guān)系;(26)式表示被機(jī)器人k搬運(yùn)的起始貨架開始移動(dòng)時(shí)間不小于機(jī)器人從起點(diǎn)到該貨架的移動(dòng)時(shí)長(zhǎng);(27)式表示被機(jī)器人k搬運(yùn)的貨架i在揀貨臺(tái)l的開始服務(wù)時(shí)間不小于貨架i的開始移動(dòng)時(shí)間;(28)式表示在集合U的順序中,若貨架j在i后被機(jī)器人k移動(dòng),sjk與rilk應(yīng)滿足的關(guān)系。

子問(wèn)題變量及參數(shù)如表4、5所示。設(shè)集合Uk表示由機(jī)器人k搬運(yùn)的貨架集合,Uk∈U。lis表示貨架i首先經(jīng)過(guò)的揀貨臺(tái),lil表示貨架i最后經(jīng)過(guò)的揀貨臺(tái),可由主問(wèn)題求得。對(duì)于任意機(jī)器人k,有子問(wèn)題模型如下

表4 子問(wèn)題變量

表5 子問(wèn)題參數(shù)

minTk

(29)

s.t.Tk≥ri+psi+tilil+ti,i∈Uk

(30)

ri≥ti+tilis+(x0i-1)M,i∈Uk

(31)

rj≥ri+psi+tilil+tij+tjljs+(xij-1)M,i∈Uk

(32)

(33)

(34)

(35)

其中(30)式表示對(duì)機(jī)器人k揀選時(shí)間的約束;(31)式表示貨架i開始服務(wù)時(shí)間滿足的條件;(32)式表示若貨架j在貨架i后被機(jī)器人k搬運(yùn),其開始服務(wù)時(shí)間的約束;(33)～(35)式表示貨架出入度相等且為1。

基本形式的數(shù)學(xué)啟發(fā)式算法流程如下:

第1步基于求解器Gurobi,求解主問(wèn)題模型,得到在當(dāng)前的貨架順序U下的目標(biāo)函數(shù)值T1。

第2步根據(jù)主問(wèn)題求解結(jié)果,確定子問(wèn)題參數(shù)。

第3步針對(duì)每個(gè)機(jī)器人k,求解子問(wèn)題,確定變量{xij}i,j∈Uk。

第4步根據(jù)子問(wèn)題給出的所有機(jī)器人的搬運(yùn)貨架順序,計(jì)算主問(wèn)題目標(biāo)函數(shù)值T2。

第5步取T1、T2的較小值作為最終目標(biāo)值。

上述算法計(jì)算了兩個(gè)主問(wèn)題目標(biāo)函數(shù)值T1和T2,它們關(guān)于機(jī)器人移動(dòng)貨架的順序決策是不同的,T1的機(jī)器人移動(dòng)貨架順序基于參數(shù)U,T2則由子問(wèn)題求解出的貨架順序{xij}i,j∈Uk,k∈K而確定。T1和T2在訂單與揀貨臺(tái)的匹配、貨架與機(jī)器人的匹配及貨架到不同揀貨臺(tái)順序的決策都相同。一般情況下,T2小于T1,因?yàn)門2是在以機(jī)器人揀貨時(shí)間最小化為目標(biāo)的前提下,單獨(dú)優(yōu)化每個(gè)機(jī)器人移動(dòng)貨架順序后得到的目標(biāo)值;但也存在T2大于T1的情況,因?yàn)閱蝹€(gè)機(jī)器人搬運(yùn)時(shí)間減少后,機(jī)器人間的相互等待時(shí)間可能會(huì)延長(zhǎng)得更多。所以需要對(duì)這兩個(gè)目標(biāo)值比較后,返回較優(yōu)的一個(gè)。

4.2.2 改進(jìn)的數(shù)學(xué)啟發(fā)式算法(improved matheuristic,IMH)

4.2.1節(jié)主問(wèn)題基于固定的貨架移動(dòng)順序而優(yōu)化其他決策,但這個(gè)順序可能并非最優(yōu)。為此,根據(jù)子問(wèn)題結(jié)果對(duì)這個(gè)順序進(jìn)行優(yōu)化,新的順序由每個(gè)子問(wèn)題得到的貨架移動(dòng)順序拼接而成,用以更新主問(wèn)題模型中的參數(shù)U,并重新求解主問(wèn)題。按這種方式迭代多次,輸出最終解。通過(guò)不斷更新貨架移動(dòng)順序,擴(kuò)大解的搜索空間,使4.2.1節(jié)MH算法得到改進(jìn)。

MH和IMH算法基于模型而設(shè)計(jì),使用通用整數(shù)規(guī)劃求解器,一旦問(wèn)題規(guī)模增大,求解器運(yùn)行時(shí)間會(huì)很長(zhǎng),影響求解效果。而元啟發(fā)式算法可以較好地平衡求解效果和時(shí)間。為此,4.3節(jié)設(shè)計(jì)了一種元啟發(fā)式算法,以便在有限時(shí)間內(nèi)得到一個(gè)較好解。

4.3 兩階段自適應(yīng)大鄰域搜索算法(Two-stage ALNS)

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

自適應(yīng)大鄰域搜索(adaptive large neighborhood search,ALNS)是Ropke和Pisinger[13]提出的一種元啟發(fā)式算法,其在鄰域搜索的基礎(chǔ)上增加對(duì)算子作用效果的衡量,使算法能夠自動(dòng)選擇好的算子對(duì)解進(jìn)行破壞與修復(fù),以便得到更優(yōu)解。由于問(wèn)題決策的復(fù)雜性,本節(jié)設(shè)計(jì)兩階段ALNS算法,每階段內(nèi)部都利用ALNS優(yōu)化。第一階段仍然假設(shè)只有一個(gè)揀貨臺(tái),將4.1.1節(jié)作為初始解的生成方法,并只針對(duì)機(jī)器人與貨架的匹配及搬運(yùn)貨架的順序進(jìn)行優(yōu)化。第二階段考慮多揀貨臺(tái),在第一階段結(jié)果的基礎(chǔ)上,對(duì)訂單分配給揀貨臺(tái)的決策進(jìn)行優(yōu)化,并在此后對(duì)貨架在不同揀貨臺(tái)的服務(wù)順序進(jìn)行優(yōu)化。初始解利用4.1.2節(jié)得到。此階段加入模擬退火機(jī)制[14],以避免陷入局部最優(yōu)解。

由于第一階段相比原問(wèn)題增加了特定條件,所以第一階段結(jié)果并不一定是原問(wèn)題最優(yōu)解的一部分,直接傳遞到第二階段很可能會(huì)跳過(guò)全局最優(yōu)解。所以在第一階段優(yōu)化后收集結(jié)果較好的Q個(gè)解作為第二階段參數(shù)來(lái)增加搜索空間,分別進(jìn)行第二階段優(yōu)化,最終比較選出最優(yōu)結(jié)果。

在反饋機(jī)制上,將第二階段結(jié)束后當(dāng)前整體最優(yōu)解的機(jī)器人與貨架匹配和貨架移動(dòng)順序部分重新傳回第一階段,作為初始解繼續(xù)進(jìn)行第一階段內(nèi)部?jī)?yōu)化。另外,若當(dāng)前整體最優(yōu)解比前一次外層循環(huán)整體結(jié)果更優(yōu),則在返回第一階段時(shí)不再內(nèi)部迭代,直接將當(dāng)前結(jié)果復(fù)制為Q個(gè)參數(shù)傳到下一次第二階段的迭代,這樣不僅可以在一定程度上避免迭代不充分而跳過(guò)全局最優(yōu)解的情況出現(xiàn),也可以節(jié)約求解時(shí)間。算法步驟如下:

第1步生成第一階段初始解。

第2步進(jìn)行破壞與修復(fù),生成新解。

第3步更新第一階段當(dāng)前最優(yōu)解和破壞、修復(fù)操作方法權(quán)重。

第4步是否滿足第一階段最大迭代次數(shù)。若否,轉(zhuǎn)到第2步,否則轉(zhuǎn)到第5步。

第5步收集第一階段結(jié)果較好的Q個(gè)解,作為參數(shù)生成Q個(gè)第二階段初始解。對(duì)第一個(gè)初始解進(jìn)行第6～9步的操作。

第6步進(jìn)行破壞與修復(fù),生成新解。

第7步判斷是否更優(yōu)。若是則更新第二階段當(dāng)前最優(yōu)解;否則根據(jù)模擬退火原理判斷是否更新當(dāng)前最優(yōu)解,并更新破壞與修復(fù)操作方法權(quán)重。

第8步降溫,判斷溫度是否低于最低溫度。若否,轉(zhuǎn)到第6步;若是,將溫度調(diào)整為初始溫度,轉(zhuǎn)到第9步。

第9步是否滿足第二階段最大迭代次數(shù)。若否,轉(zhuǎn)到第6步;否則轉(zhuǎn)到第10步。

第10步是否將Q個(gè)初始解分別迭代完成。若是,轉(zhuǎn)到第11步;否則取下一初始解,轉(zhuǎn)到第6步。

第11步在Q個(gè)迭代結(jié)果中選最優(yōu),按反饋機(jī)制更新第一階段初始解。判斷是否滿足外層循環(huán)最大迭代次數(shù)。若否,轉(zhuǎn)到第2步;否則輸出最優(yōu)解,結(jié)束算法。

4.3.2 破壞與修復(fù)算子

(1)第一階段破壞算子

隨機(jī)移除:在任務(wù)數(shù)大于1的機(jī)器人中,隨機(jī)選擇一個(gè)并移除其中一個(gè)搬運(yùn)任務(wù)。

最差移除:選擇返回起點(diǎn)最晚的機(jī)器人,移除其中一個(gè)搬運(yùn)任務(wù)。

(2)第一階段修復(fù)算子

隨機(jī)修復(fù):隨機(jī)選擇一個(gè)機(jī)器人,將移除的貨架作為其最后一個(gè)任務(wù)。

最近鄰修復(fù):計(jì)算所有機(jī)器人需移動(dòng)的最后一個(gè)貨架與移除貨架之間的距離,選擇最短的機(jī)器人,將移除貨架添加為其最后一個(gè)任務(wù)。

(3)第二階段破壞算子

隨機(jī)移除:隨機(jī)選擇一個(gè)訂單,將該訂單與揀貨臺(tái)的匹配關(guān)系移除。

最差移除:訂單分配不均會(huì)導(dǎo)致同一時(shí)間有的揀貨臺(tái)繁忙,有的空閑,造成資源浪費(fèi),也會(huì)導(dǎo)致揀選時(shí)間增加。最差移除將安排訂單最多揀貨臺(tái)中的某一個(gè)訂單移除。

(4)第二階段修復(fù)算子

對(duì)位修復(fù):將移除的訂單隨機(jī)補(bǔ)充匹配一個(gè)與原解不同的揀貨臺(tái)。計(jì)算每個(gè)貨架需要經(jīng)過(guò)的揀貨臺(tái),迭代優(yōu)化貨架在多個(gè)揀貨臺(tái)的服務(wù)順序,形成完整的解。

末尾修復(fù):在破壞的解最后隨機(jī)補(bǔ)充匹配一個(gè)揀貨臺(tái)。對(duì)位修復(fù)可在原解的附近進(jìn)行搜索,以向最優(yōu)解逼近;而末尾修復(fù)則加大擾動(dòng),使算法有機(jī)會(huì)跳出局部最優(yōu)。

每階段的破壞修復(fù)算子分別有2個(gè),所以在迭代時(shí)會(huì)得到24種不同的鄰域搜索組合方法,對(duì)算法搜索能力有一定幫助。當(dāng)求解大規(guī)模問(wèn)題時(shí),只破壞一處對(duì)原解的擾動(dòng)較小,所以在第一階段選擇三個(gè)機(jī)器人進(jìn)行破壞。

5 數(shù)值實(shí)驗(yàn)

本文模型和算法利用Python 3.8編寫,使用Gurobi 9.1.1求解模型。計(jì)算機(jī)配置Intel(R) Core(TM) i5-8400 CPU 2.80GHz、8GB RAM、Windows10操作系統(tǒng)。算例通過(guò)某電商平臺(tái)分揀中心真實(shí)數(shù)據(jù)經(jīng)過(guò)處理得到。設(shè)置單位SKU在揀貨臺(tái)處理時(shí)間為α=10s,機(jī)器人移速v=0.5m/s。算法參數(shù)設(shè)置如表6所示。根據(jù)實(shí)際需要,將所有算法針對(duì)小規(guī)模算例求解時(shí)間限制在1800s,大規(guī)模算例求解時(shí)間限制在4800s,若超過(guò)該時(shí)間,則強(qiáng)行停止算法,輸出當(dāng)前最優(yōu)解。同樣地,也將數(shù)學(xué)啟發(fā)式算法對(duì)應(yīng)的模型設(shè)置最大的求解時(shí)間限制。

表6 算法參數(shù)

根據(jù)相關(guān)文獻(xiàn)[15-17],設(shè)計(jì)一種在機(jī)器人調(diào)度中應(yīng)用較為常見的遺傳算法(GA)作為對(duì)比算法。該算法對(duì)所有決策同步優(yōu)化,并與本文算法進(jìn)行對(duì)比分析。

5.1 小規(guī)模算例實(shí)驗(yàn)

本文在小規(guī)模問(wèn)題上進(jìn)行了如表7所示的多組實(shí)驗(yàn),包括本文模型、算法以及對(duì)比算法的求解結(jié)果。其中n、H、N、K分別代表貨架數(shù)、訂單數(shù)、揀貨臺(tái)數(shù)、機(jī)器人數(shù)。由于小規(guī)模算例中機(jī)器人數(shù)較少,交通更通暢,所以在合理的情況下,將機(jī)器人移速提高為1m/s。表中各算法的GAP為其結(jié)果與MIP求解結(jié)果的差距,公式為GAPi=(Ti-T0)/T0,其中Ti為算法i求解的目標(biāo)值,T0為MIP求解的目標(biāo)值。

表7 小規(guī)模算例實(shí)驗(yàn)結(jié)果(v=1)

ALNS算法在求解效果上要優(yōu)于兩種數(shù)學(xué)啟發(fā)式算法及GA,其結(jié)果與MIP的GAP達(dá)到0%的數(shù)量最多,甚至對(duì)于MIP無(wú)法完整求解的算例4,GAP小于0。GA與Two-stage ALNS在求解效果上的差距,也體現(xiàn)出兩階段數(shù)學(xué)啟發(fā)式算法相比于單階段的優(yōu)越性。針對(duì)算例11～15進(jìn)行敏感性分析,固定其他參數(shù)而只增加揀貨臺(tái)數(shù),揀選時(shí)間隨之減小,但其減小速度是遞減的。當(dāng)揀貨臺(tái)數(shù)增至4個(gè)時(shí),繼續(xù)增加揀貨臺(tái)將不會(huì)使系統(tǒng)揀選效率繼續(xù)提升。

圖3～6分別為改變貨架數(shù)、訂單數(shù)、揀貨臺(tái)數(shù)、機(jī)器人數(shù)對(duì)算法求解時(shí)間的影響。綜合來(lái)看,Two-stage ALNS、GA、MH求解時(shí)間較短且較穩(wěn)定。MIP、IMH求解時(shí)間隨參數(shù)變化明顯,MIP在算例4、5、15甚至已超出求解時(shí)間限制。

圖3 貨架數(shù)對(duì)求解時(shí)間的影響

圖4 訂單數(shù)對(duì)求解時(shí)間的影響

圖5 揀貨臺(tái)數(shù)對(duì)求解時(shí)間的影響

圖6 機(jī)器人數(shù)對(duì)求解時(shí)間的影響

5.2 大規(guī)模算例實(shí)驗(yàn)

表8為大規(guī)模算例各算法求解結(jié)果。除算例1外,MIP在一定時(shí)間內(nèi)都無(wú)法找到可行解。RBH可在極短的時(shí)間內(nèi)找到可行解,但目標(biāo)值較大。MH與IMH之間各有優(yōu)劣,而GA求解效果則僅優(yōu)于RBH。從Two-stage ALNS求解結(jié)果來(lái)看,對(duì)于算例1,要比MIP的可行解更優(yōu);算例1～3中,Two-stage ALNS求解效果相比于MH略差,但差距較小;對(duì)于其他算例,Two-stage ALNS的結(jié)果優(yōu)于其他算法,且較為穩(wěn)定。圖7為各算法求解結(jié)果對(duì)比圖,可以更直觀突出Two-stage ALNS在大規(guī)模問(wèn)題求解上相較于其他算法的優(yōu)勢(shì)。

表8 大規(guī)模算例求解結(jié)果(v=0.5 )

圖7 大規(guī)模算例求解效果對(duì)比

6 結(jié)論與啟示

移動(dòng)貨架倉(cāng)庫(kù)中搬運(yùn)機(jī)器人調(diào)度是倉(cāng)儲(chǔ)管理領(lǐng)域具有代表性的需多問(wèn)題協(xié)同考慮的組合優(yōu)化難題。由于現(xiàn)實(shí)倉(cāng)庫(kù)中該問(wèn)題具有一定規(guī)模,且求解時(shí)間十分有限,該問(wèn)題的解決極具挑戰(zhàn)。為此,本文綜合考慮了訂單揀貨任務(wù)分配、貨架服務(wù)順序、揀貨臺(tái)工作安排及機(jī)器人調(diào)度等諸多相互關(guān)聯(lián)、相互影響的復(fù)雜環(huán)節(jié),以揀貨時(shí)間最小化為目標(biāo)建立了考慮多揀貨臺(tái)的混合整數(shù)規(guī)劃模型,證明了問(wèn)題的NP-Hard特性。為求解現(xiàn)實(shí)中大規(guī)模問(wèn)題,本文一方面將數(shù)學(xué)規(guī)劃模型與啟發(fā)式方法結(jié)合,設(shè)計(jì)了基于模型的數(shù)學(xué)啟發(fā)式算法;另一方面設(shè)計(jì)了一種基于模擬退火和特殊反饋機(jī)制的兩階段ALNS算法。通過(guò)電商物流企業(yè)真實(shí)數(shù)據(jù)驗(yàn)證了模型和算法的科學(xué)性和有效性。實(shí)驗(yàn)結(jié)果表明,本文的ALNS算法針對(duì)各種規(guī)模算例都表現(xiàn)出較強(qiáng)競(jìng)爭(zhēng)優(yōu)勢(shì),基于模型的數(shù)學(xué)啟發(fā)式算法在保證一定求解質(zhì)量的前提下,針對(duì)部分算例的求解效果優(yōu)于ALNS算法,這兩種算法相比于文獻(xiàn)中的代表性算法都更具競(jìng)爭(zhēng)力。

實(shí)驗(yàn)發(fā)現(xiàn),倉(cāng)庫(kù)揀貨臺(tái)數(shù)量的增加未必總會(huì)減少揀貨時(shí)間、提高揀貨效率。由于移動(dòng)貨架倉(cāng)庫(kù)的揀貨操作是一項(xiàng)人機(jī)協(xié)同工作,在機(jī)器人數(shù)量給定情況下,當(dāng)揀貨臺(tái)和相應(yīng)揀貨員在一定范圍內(nèi)增加時(shí),訂單揀選效率可得到有效提高。但當(dāng)超出該范圍,揀選效率將不再提升。而揀貨臺(tái)和揀貨員的最優(yōu)數(shù)量可由本文算法針對(duì)現(xiàn)實(shí)倉(cāng)庫(kù)案例給出,這就為一類需要人機(jī)協(xié)同工作的倉(cāng)儲(chǔ)企業(yè)的硬件和人力配置決策提供了參考。

本文研究是基于機(jī)器人電量足夠情況下而進(jìn)行的機(jī)器人調(diào)度。當(dāng)訂單量很大,機(jī)器人滿電情況下無(wú)法完成揀貨任務(wù)時(shí),需將機(jī)器人充電任務(wù)與其揀貨任務(wù)一起調(diào)度。充電與揀貨任務(wù)的聯(lián)合調(diào)度是未來(lái)該領(lǐng)域的一個(gè)重要研究方向。