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

(大連海事大學 航運經(jīng)濟與管理學院,遼寧 大連 116025)

1 引言

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

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

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

2 問題描述及模型建立

2.1 問題描述

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

圖1 移動貨架倉庫平面示意圖

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

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

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

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

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

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

(4)機器人在倉庫中任意兩個位置的行駛距離已知。

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

2.2 模型建立

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

表1 變量及其說明

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

根據(jù)問題定義,機器人完成所有任務的時長取決于消耗時間最長的機器人。所以問題目標為最小化所有機器人揀貨時間中的最大值。基于問題描述和變量定義,構建下述混合整數(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)式為對總時間T的表示;(3)、(4)式表示所有機器人都從起點出發(fā),最后回到起點;(5)～(7)式表示貨架的出入度相等且都為1;(8)式表示貨架開始移動時間與其在揀貨臺的開始服務時間的關系;(9)式表示被同一機器人所搬運的貨架間,后一個貨架的開始移動時間與前一個貨架的開始服務時間的關系;(10)式表示若貨架j為起始搬運貨架,則sj≥tj;(11)式表示若揀貨臺l服務貨架i、j,貨架i、j在該揀貨臺的開始服務時間的關系;(12)式表示貨架在需要被服務的不同揀貨臺上開始服務時間的關系;(13)式計算貨架i在揀貨臺l的服務時長;(14)式表示每個訂單只能在唯一的揀貨臺上處理;(15)式表示揀貨臺不能重復服務同一個貨架;(16)、(17)式表示若貨架i上有訂單h中的商品,且訂單h在揀貨臺l上處理,則Yil為1,否則為0;(18)式表示貨架不能重復在同一個揀貨臺服務;(19)～(22)式給出了變量之間的關系。

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

3 問題分析

移動貨架倉庫搬運機器人調(diào)度問題包含如下待優(yōu)化子問題:

(1)倉庫中存在多個機器人以及多個待搬運貨架,這就涉及到機器人與貨架的匹配,需確定哪臺機器人搬運哪些貨架。

(2)機器人搬運完一個貨架后,要移動到下一個需搬運貨架的位置。由于貨架原本位置間距離不同,搬運貨架的先后順序會直接影響機器人行駛路徑的長短,從而影響分揀效率。

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

(4)由于一個貨架在一次搬運過程中可能需要訪問多個揀貨臺,而不同揀貨臺之間的距離也往往不同,所以貨架針對多個揀貨臺訪問順序也將影響機器人的行駛路徑長短,從而影響分揀效率。

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

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

4 算法設計

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

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

圖2 算法關系圖

4.1.1 第一階段:機器人與貨架的關系

第一階段采用貪婪思想確定每個機器人的任務安排,具體步驟如下:

第1步初始時,將K臺機器人放入閑置機器人隊列φ中。

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

第3步若機器人到揀貨臺時,揀貨臺空閑,則立即對貨架開始服務;否則等待揀貨臺空閑時再開始服務。若該貨架影響到其他貨架在揀貨臺的服務時間,則更新受影響貨架的揀貨臺服務時間。

第4步貨架在揀貨臺服務完畢后,機器人將其搬回原位,將該機器人加入φ尾部,轉入第2步。

4.1.2 第二階段:貨架與揀貨臺的關系

每個訂單的商品可能需從多個貨架中揀貨,這些貨架都應送往一個揀貨臺,以便訂單商品的打包。因此,訂單與揀貨臺的匹配關系決定了貨架與揀貨臺的匹配關系。

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

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

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

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

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

本節(jié)算法將原問題分解為主問題與子問題。主問題優(yōu)化訂單與揀貨臺匹配、貨架經(jīng)過多個揀貨臺的順序及機器人與貨架的匹配;子問題優(yōu)化機器人移動貨架順序?；舅悸肥鞘紫雀鶕?jù)4.1.1節(jié)算法確定總體貨架移動順序,存入集合U中,并設定變量wik表示貨架i與機器人k的匹配關系,這樣可以暫時不考慮2.2節(jié)模型中的復雜變量xijk。簡化后的問題構成主問題。將每個機器人的貨架移動順序放在子問題中單獨優(yōu)化。

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

表3 主問題變量

(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)

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

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

表4 子問題變量

表5 子問題參數(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)式表示對機器人k揀選時間的約束;(31)式表示貨架i開始服務時間滿足的條件;(32)式表示若貨架j在貨架i后被機器人k搬運,其開始服務時間的約束;(33)～(35)式表示貨架出入度相等且為1。

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

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

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

第3步針對每個機器人k,求解子問題,確定變量{xij}i,j∈Uk。

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

第5步取T1、T2的較小值作為最終目標值。

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

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

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

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

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

4.3.1 算法設計

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

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

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

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

第2步進行破壞與修復,生成新解。

第3步更新第一階段當前最優(yōu)解和破壞、修復操作方法權重。

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

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

第6步進行破壞與修復,生成新解。

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

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

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

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

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

4.3.2 破壞與修復算子

(1)第一階段破壞算子

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

最差移除:選擇返回起點最晚的機器人,移除其中一個搬運任務。

(2)第一階段修復算子

隨機修復:隨機選擇一個機器人,將移除的貨架作為其最后一個任務。

最近鄰修復:計算所有機器人需移動的最后一個貨架與移除貨架之間的距離,選擇最短的機器人,將移除貨架添加為其最后一個任務。

(3)第二階段破壞算子

隨機移除:隨機選擇一個訂單,將該訂單與揀貨臺的匹配關系移除。

最差移除:訂單分配不均會導致同一時間有的揀貨臺繁忙,有的空閑,造成資源浪費,也會導致揀選時間增加。最差移除將安排訂單最多揀貨臺中的某一個訂單移除。

(4)第二階段修復算子

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

末尾修復:在破壞的解最后隨機補充匹配一個揀貨臺。對位修復可在原解的附近進行搜索,以向最優(yōu)解逼近;而末尾修復則加大擾動,使算法有機會跳出局部最優(yōu)。

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

5 數(shù)值實驗

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

表6 算法參數(shù)

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

5.1 小規(guī)模算例實驗

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

表7 小規(guī)模算例實驗結果(v=1)

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

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

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

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

圖5 揀貨臺數(shù)對求解時間的影響

圖6 機器人數(shù)對求解時間的影響

5.2 大規(guī)模算例實驗

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

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

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

6 結論與啟示

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

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

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