萬明重,蔣忠中+,秦緒偉,喬 雙,李銘陽
(1.東北大學(xué) 工商管理學(xué)院,遼寧 沈陽 110167;2.東北大學(xué) 行為與服務(wù)運(yùn)作管理研究所,遼寧 沈陽 110167;3.天津大學(xué) 管理與經(jīng)濟(jì)學(xué)部,天津 300072)
伴隨著電子商務(wù)的高速發(fā)展,其對(duì)客戶訂單的配送服務(wù)也提出了更高的要求。天貓超市、京東商城等購物平臺(tái)紛紛推出次日達(dá)、今日達(dá)等限時(shí)配送服務(wù)。通常地,配送服務(wù)包括客戶從下達(dá)訂單到送貨上門等流程,其中,倉庫中的訂單揀選是配送服務(wù)的重要環(huán)節(jié),屬于倉庫作業(yè)中勞動(dòng)密集度和成本最高的活動(dòng),其成本約占倉庫總運(yùn)營成本的55%以上[1]。傳統(tǒng)倉庫中,為降低人工操作的失誤,訂單揀選通常要求訂單不被拆分,即每個(gè)訂單只能分配給一名揀選員[1],但也限制了訂單揀選作業(yè)的效率。借助新興的信息技術(shù),智能倉庫可輕松地實(shí)現(xiàn)訂單任務(wù)拆分和重組,為訂單揀選作業(yè)效率的提高創(chuàng)造了有利條件。以京東智能倉庫——無人倉為例,基于3D視覺識(shí)別等技術(shù),運(yùn)用智能小車、揀貨機(jī)器人、機(jī)械手等設(shè)備代替?zhèn)鹘y(tǒng)的揀貨員和揀貨車,一方面避免了人工操作可能帶來的失誤,另一方面實(shí)現(xiàn)了倉庫的自動(dòng)揀選、智能打包等功能??梢姡鄬?duì)于傳統(tǒng)倉庫,訂單可拆分是智能倉庫揀選作業(yè)的新特征,因此如何實(shí)現(xiàn)訂單可拆分情形下的揀選作業(yè)優(yōu)化是企業(yè)實(shí)現(xiàn)智能倉庫高效運(yùn)作的重要決策問題。
近年來,訂單揀選優(yōu)化問題備受學(xué)者關(guān)注,國內(nèi)外文獻(xiàn)從訂單分批、批次分配和揀貨車路徑優(yōu)化等角度對(duì)訂單揀選問題進(jìn)行了研究。訂單分批是將不同訂單組成批次,交由揀貨車同時(shí)揀??;批次分配是將這些批次分配給不同揀貨車,并確定其揀貨順序。國外方面,SCHOLZ等[2]研究了訂單分批、批次分配問題,其目標(biāo)是使訂單總延誤時(shí)間最小;ARDJMAND等[3]研究了按波次揀選倉庫中訂單分批和批次分配問題,其目標(biāo)是最小化訂單總完工時(shí)間;THEYS等[4]和GLOCK等[5]研究了倉庫揀選的路徑優(yōu)化問題,并分別將其轉(zhuǎn)化有旅行商問題(Traveling Salesman Problem, TSP)和有容量限制的車輛路徑優(yōu)化問題(Capacitated Vehicle Routing Problem, CVRP)。國內(nèi)方面,梁旭[6]和鄒霞等[7]對(duì)傳統(tǒng)倉庫中訂單的調(diào)度問題進(jìn)行了研究。上述針對(duì)傳統(tǒng)倉庫訂單揀選問題的研究中,為降低揀貨員在作業(yè)中的失誤率,通常較少考慮訂單可拆分的情況。
隨著智能化技術(shù)的發(fā)展,倉庫逐漸開始使用自動(dòng)導(dǎo)引車(Automated Guided Vehicle, AGV)、揀貨機(jī)器人、智能揀貨車等代替?zhèn)鹘y(tǒng)的人工揀選,部分學(xué)者也開始研究訂單拆分策略下的倉庫揀選問題。訂單拆分策略下,一個(gè)訂單可被拆分成多個(gè)部分并分配給不同批次或揀貨車。ARCHETRI等[8]研究表明,訂單拆分策略有助于提高揀貨車容量的利用率,進(jìn)而提高訂單揀選的效率。CERGIBOZAN等[9]研究指出,若單個(gè)訂單較大無法由一輛揀貨車完成揀選任務(wù)時(shí),可對(duì)訂單進(jìn)行拆分,并交由多輛揀貨車進(jìn)行揀選。PARIKH等[10]研究了倉庫分區(qū)條件下的訂單分批、揀選問題,研究將單個(gè)訂單依貨品的存儲(chǔ)區(qū)域拆分給多個(gè)部分,并交由每個(gè)區(qū)域的揀貨車同時(shí)進(jìn)行揀選,其目標(biāo)是最小化揀貨車的空閑時(shí)間。BRIANT等[11]基于HappyChic公司的案例研究了考慮訂單拆分策略的訂單分配、揀貨車路由問題,其目標(biāo)是最小化揀貨車的總行走距離。
在處理限時(shí)訂單的揀選、配送問題中,確保訂單按時(shí)完成配送是最重要的目標(biāo)。但考慮訂單拆分策略的現(xiàn)有研究中,尚未對(duì)最小化訂單總延誤時(shí)間的問題進(jìn)行探討?;诖耍疚氖状卧谝宰钚』唵慰傃诱`時(shí)間為目標(biāo)的訂單揀選問題中考慮了訂單拆分策略。當(dāng)訂單允許被拆分時(shí),某個(gè)訂單可被拆分成多個(gè)部分并分配給不同批次;而只有當(dāng)該訂單需要的所有貨品都被揀選后,才能對(duì)該訂單進(jìn)行配送。此時(shí),訂單的完成時(shí)間由包含該訂單的所有批次共同決定。因此,訂單拆分策略使得以目標(biāo)為最小化訂單總延誤時(shí)間的訂單揀選問題相對(duì)傳統(tǒng)倉庫的訂單揀選問題更為復(fù)雜。
為此,本文針對(duì)智能倉庫的訂單揀選優(yōu)化問題的新特征,研究考慮拆分策略的訂單揀選優(yōu)化模型與算法,并探討拆分策略和算法設(shè)計(jì)對(duì)于訂單揀選作業(yè)效率的影響規(guī)律。首先,以訂單總延誤時(shí)間最小化為目標(biāo),構(gòu)建考慮拆分策略的訂單揀選優(yōu)化模型;其次,依據(jù)模型特點(diǎn)將該問題分解為訂單分批和批次分配兩階段,并分別提出了訂單分批算法和智能果蠅優(yōu)化算法對(duì)模型進(jìn)行求解;最后,通過數(shù)值算例計(jì)算和對(duì)比分析,驗(yàn)證了所提算法的高效性。研究結(jié)果表明,在拆分策略情形下訂單總延誤時(shí)間顯著減小,進(jìn)而大幅度提升了訂單揀選作業(yè)的效率。
訂單揀選作業(yè)流程一般包括訂單分批、批次分配和揀選路由3部分。訂單分批是將多張訂單組成不同批次;批次分配是將組成的不同批次分配給揀選員(智能小車或智能揀貨車),并確定批次的揀選順序;揀貨路由則是揀選員依據(jù)分配訂單確定揀貨路徑。在電子商務(wù)環(huán)境下,考慮智能倉庫可實(shí)現(xiàn)訂單拆分的新特征,其訂單揀選問題描述如下:倉庫將某時(shí)段接收到的多張客戶訂單,通過訂單拆分并依據(jù)其截止時(shí)間組成不同批次,再由智能揀貨車根據(jù)批次進(jìn)行揀選路由,最后將屬于同一客戶訂單的貨品整合在一起,并進(jìn)行復(fù)核和打包。如圖1所示為訂單揀選的具體流程,由于智能倉庫的自動(dòng)化水平較高,訂單拆分和分批可快速地自動(dòng)完成(花費(fèi)時(shí)間可忽略),訂單揀選花費(fèi)時(shí)間主要體現(xiàn)在智能揀貨車行走時(shí)間和取貨時(shí)間方面。行走時(shí)間是指智能揀貨車完成從倉庫起點(diǎn)開始逐個(gè)訪問訂單貨品所需揀選位置并返回倉庫起點(diǎn)的路徑所花費(fèi)的時(shí)間(假設(shè)行走速度恒定,則行走時(shí)間取決于智能揀貨車的行駛距離);取貨時(shí)間是指智能揀貨車到達(dá)指定揀選位置后取出貨品所需的時(shí)間。
研究以單區(qū)型智能倉庫為例,智能揀貨車按照包含U-turn的S型路徑揀選貨品[12],即揀貨車在完成最后一通道的貨品揀選后立即返回,而不是繼續(xù)按照S路徑走完通道。為方便機(jī)械手存取貨品,智能倉庫中揀貨車的貨框往往使用托盤或隔板劃分出若干個(gè)區(qū)域,每個(gè)區(qū)域存放至多一件貨品。因此,本文中揀貨車容量C亦指揀貨車貨框中托盤的個(gè)數(shù)(或隔板劃分的區(qū)域個(gè)數(shù))。智能揀貨車接收批次任務(wù)的時(shí)刻記為批次的開始時(shí)間,智能揀貨車完成揀選任務(wù)回到起始點(diǎn)的時(shí)刻記為批次的完成時(shí)間。當(dāng)被拆分的訂單中所需的全部貨品揀選完成時(shí),該訂單被完成;訂單的延誤時(shí)間為該訂單的完成時(shí)間減去該訂單的截止時(shí)間。基于此,問題的基本假設(shè)如下:①倉庫中存儲(chǔ)貨品的位置是固定的,且每個(gè)位置只存放一種貨品,智能揀貨車行走在巷道的中間可同時(shí)從左右兩邊揀選貨品;②智能揀貨車直至當(dāng)前任務(wù)完成后才能開始下一個(gè)任務(wù),中間不可被打斷;③每個(gè)批次中貨品的體積不得超過智能揀貨車的容量;④每個(gè)訂單至少包含一件貨品。問題的模型參數(shù)和變量包括:
(1)模型參數(shù)
I為客戶訂單集合,i∈I={1,2,…,m};
P為智能揀貨車集合,p∈P={1,2,…,n};
Q為訂單批次集合,q∈Q={1,2,…,|Q|};
K為貨品集合,k∈K={1,2,…,|K|};
C為智能揀貨車容量;
B為智能倉庫中兩相鄰?fù)ǖ篱g的距離;
L為智能倉庫中通道的長度;
(2)決策變量
xiqk為0-1變量,若批次q包含訂單i中的貨品k,則xiqk=1,否則xiqk=0;
ypqq′為0-1變量,若批次q′緊接著批次q由智能揀貨車p揀取,則ypqq′=1,否則ypqq′=0。
(3)輔助變量
τi為訂單i延誤時(shí)間;
vtravel為智能揀貨車行駛速度;
disq為完成批次q所需行走距離;
tsetup為批次的準(zhǔn)備、取貨時(shí)間;
Aq為揀選批次q中的貨品需要訪問的通道數(shù)量;
傳統(tǒng)的訂單揀選問題中,一般遵循訂單不可被拆分的原則。但由于每個(gè)訂單包含的貨品種類和數(shù)量不同,揀選每個(gè)訂單所需的揀貨車容量也不同,需要將不同訂單進(jìn)行組合來提高揀貨車容量的利用率。理想的情況是組成同一批次的訂單恰好占滿整個(gè)揀貨車且具有相同的截止時(shí)間。但在實(shí)際問題中,不同訂單的組合很難恰好占滿揀貨車,訂單的截止時(shí)間不盡相同,因此以上兩方面目標(biāo)很難同時(shí)達(dá)到最優(yōu)。
針對(duì)智能倉庫的新特征,即當(dāng)機(jī)械手和智能揀貨車代替了傳統(tǒng)的人工揀貨后,可以準(zhǔn)確執(zhí)行復(fù)雜的揀貨方案,不必再遵守訂單不可被拆分的原則;同時(shí)為進(jìn)一步提升揀貨車容量的利用率,本文在訂單分配問題中引入訂單拆分策略[8]。訂單拆分策略允許將單個(gè)訂單拆分為多個(gè)部分,并分配給不同批次進(jìn)行揀選。因此,每個(gè)批次可包含多個(gè)訂單,每個(gè)訂單也可由多個(gè)批次共同完成。由于單個(gè)訂單需要在其包含的所有貨品都完成揀選后才能配送,訂單的完成時(shí)間取決于包含該訂單批次完成時(shí)間的最大值?;谏鲜鎏匦裕瑯?gòu)建基于拆分策略的訂單揀選問題數(shù)學(xué)模型如下:
(1)
s.t.
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
xiqk∈{0,1},?i∈I,?q∈Q,?k∈K。
(10)
ypqq′∈{0,1},?q∈Q∪{0},
?q′∈Q,?p∈P。
(11)
disq=
(12)
以最小化總延誤時(shí)間為目標(biāo)的訂單揀選問題屬于NP-hard問題,當(dāng)問題規(guī)模較大時(shí)很難高效求解[13]。由于在電子商務(wù)環(huán)境下,商家需要處理大量緊急的訂單(今日達(dá)、次日達(dá)等),因而期望算法能在較短的時(shí)間內(nèi)得到高質(zhì)量的解。為實(shí)現(xiàn)這一目標(biāo),本文針對(duì)考慮拆分策略的訂單揀選問題的特點(diǎn)進(jìn)行深入分析,結(jié)果發(fā)現(xiàn),若同時(shí)處理訂單分批與批次分配問題,則每次對(duì)批次進(jìn)行分配時(shí)都需要計(jì)算完成該批次揀選任務(wù)所需時(shí)間,從而導(dǎo)致計(jì)算十分耗時(shí)。鑒于此,本文提出將問題拆分成訂單分批和批次分配兩階段的求解思路。在訂單分批階段,將訂單按需求進(jìn)行拆分,并根據(jù)訂單的截止時(shí)間重新組成批次。完成訂單分批后,每個(gè)批次的揀選時(shí)間可以直接計(jì)算得到。在批次分配階段,算法基于訂單分批的結(jié)果進(jìn)行批次分配,因此不用重復(fù)計(jì)算批次的揀選時(shí)間,只需要將以上批次分配給不同揀貨車,并確定這些批次的揀選順序。上述兩階段拆分求解思路可使得模型的計(jì)算時(shí)間顯著降低。此外,兩階段拆分求解思路實(shí)質(zhì)上只是改變了訂單揀選問題決策的順序,并不會(huì)影響模型的正確性。
訂單分批問題是將不同的訂單組成批次,其目標(biāo)是最大化智能揀貨車容量的利用率,且最小化同一批次中訂單截止時(shí)間的差值。在不考慮拆分策略的訂單分批問題中,為了提高揀貨車容量的利用率,需要將不同大小(貨品數(shù)量不同)的訂單進(jìn)行組合。由于不同訂單的截止時(shí)間不一致,無法保證組成同一批次的訂單恰好占滿揀貨車的容量,且訂單的截止時(shí)間相近。
訂單拆分策略可以較好地處理上述問題。在進(jìn)行訂單分批時(shí),按照訂單截止時(shí)間的升序逐個(gè)選取訂單并組成批次。若新加入批次的訂單大小超過智能揀貨車的剩余容量,則對(duì)該訂單進(jìn)行拆分,并將多出的部分訂單放入新的批次。該算法的詳細(xì)步驟如下:
步驟1獲取全部的訂單集合Ω,生成一個(gè)空的初始批次Bq。
步驟2選擇訂單集合Ω中截止時(shí)間最小的訂單Oi,該訂單包含貨品所需的智能揀貨車容量為Ci。令Cq表示當(dāng)前批次Bq剩余的容量,
(1)若Ci+Cq≤C,將訂單Oi放入批次Bq,并將Oi從訂單集合Ω中移除。
(2)若Ci+Cq>C,對(duì)訂單Oi進(jìn)行拆分:將訂單Oi中容量C-Cq的部分放入批次Bq,并將訂單Oi中容量Ci-(C-Cq)的部分放入新批次Bq+1;將Oi從訂單集合Ω中移除。
步驟3重復(fù)步驟2,直至訂單集合Ω為空。
通過訂單分批算法,可保證每個(gè)批次貨品恰好占滿智能揀貨車的容量。此外,只有當(dāng)新加入批次中的訂單大小超過智能揀貨車剩余容量時(shí),才對(duì)訂單進(jìn)行拆分。因此,該算法可以保證每個(gè)訂單不被過度拆分。
推論1訂單分批算法中,任意一個(gè)訂單至多被拆分成兩部分,且一個(gè)批次中至多包含兩個(gè)被拆分的訂單。
在訂單分批階段,若干個(gè)訂單組成一個(gè)批次。當(dāng)考慮訂單分配策略時(shí),部分訂單被拆分成若干部分并在不同批次進(jìn)行揀選。此時(shí),被拆分訂單的完成時(shí)間取決于它所屬批次的最大批次完成時(shí)間。為提高訂單揀選效率,在訂單的批次分配時(shí),應(yīng)考慮被拆分訂單的齊套性[14](使得同一訂單被拆分的部分盡可能同時(shí)完成)。若訂單被過度拆分,會(huì)使得批次分配階段的計(jì)算過于復(fù)雜。
FOA是模仿果蠅通過嗅覺和視覺尋找食物的算法。果蠅可以通過敏感的嗅覺發(fā)現(xiàn)遠(yuǎn)處的食物,并在接近后通過視覺找到食物的位置。通過嗅覺和視覺的指引,可以幫助果蠅快速接近食物,并準(zhǔn)確找到食物的位置。FOA通過模仿這一行為,很好地協(xié)調(diào)了算法的全局搜索能力和局部搜索能力:先通過嗅覺搜索找到較優(yōu)解,再通過視覺搜索在較優(yōu)解附近進(jìn)一步尋找更優(yōu)的解;如此循環(huán),直到收斂。ZHENG等[17]近一步改進(jìn)了FOA,并提出知識(shí)引導(dǎo)的果蠅優(yōu)化算法(Knowledge Guided FOA, KGFOA)。KGFOA通過根據(jù)果蠅的歷史經(jīng)驗(yàn),對(duì)果蠅的搜索方向進(jìn)行引導(dǎo),進(jìn)而加快算法的收斂速度。該算法主要包括以下步驟:
(1)種群編碼。將問題的可行解通過實(shí)數(shù)編碼的形式表示出來。
(2)初始化種群。隨機(jī)生成一系類初始可行解(初始果蠅)。
(3)嗅覺搜索。在每個(gè)果蠅的嗅覺范圍內(nèi)隨機(jī)生成若干個(gè)果蠅,形成子種群。
(4)視覺搜索。評(píng)價(jià)每個(gè)子種群的果蠅,并用該種群中最好的果蠅代替掉原果蠅。
(5)知識(shí)引導(dǎo)。每個(gè)果蠅根據(jù)歷史經(jīng)驗(yàn)進(jìn)行知識(shí)引導(dǎo)搜索。
FOA與KGFOA的嗅覺搜索未限制新果蠅產(chǎn)生的方式,使得該算法能結(jié)合確定性方法或啟發(fā)式規(guī)則加快FOA的收斂速度。鑒于此,本文選用KGFOA算法,并在算法的嗅覺搜索階段結(jié)合網(wǎng)絡(luò)效益重組(Net Benefit of Relocation, NBR)[18]規(guī)則對(duì)算法進(jìn)行改進(jìn),以提高算法的收斂速度。NBR規(guī)則是一類基于貪婪法近似求解單服務(wù)臺(tái)調(diào)度問題的規(guī)則。本文將NBR規(guī)則融入嗅覺搜索過程,減少了不必要的搜索空間,提高了嗅覺搜索的效率。隨后,本文基于批次分配問題的特性構(gòu)建了批次分配經(jīng)驗(yàn)概率和批次排序的經(jīng)驗(yàn)概率兩個(gè)知識(shí)庫,從而提高了知識(shí)引導(dǎo)的性能。基于此,本文通過改進(jìn)KGFOA的嗅覺搜索和知識(shí)引導(dǎo)過程,提出智能果蠅優(yōu)化算法(Smart FOA, SFOA)。相比已有的果蠅優(yōu)化算法,SFOA中果蠅不僅依靠隨機(jī)搜索的方法尋找最優(yōu)解(近優(yōu)解),還能應(yīng)用NBR規(guī)則和知識(shí)庫更智能地搜索最優(yōu)解(近優(yōu)解)。SFOA的算法流程如圖2所示。
2.2.1 種群編碼
批次分配問題的決策包括不同批次與智能揀貨車的匹配,以及智能揀貨車進(jìn)行批次揀選的順序。因此,果蠅的編碼由批次與智能揀貨車的匹配、批次的揀選順序兩方面信息組成。鑒于此,本文通過實(shí)數(shù)向量A來表示果蠅的編碼,每個(gè)果蠅的編碼可表示為:
A=[A1,A2,…,An],
2.2.2 嗅覺搜索
嗅覺搜索時(shí)給定果蠅的嗅覺范圍為(z,s),即果蠅只能在距離(z,s)內(nèi)進(jìn)行嗅覺搜索。其中距離z表示隨機(jī)生成的新果蠅A′與原果蠅A相比,至多有z個(gè)批次被指派的智能揀貨車不同;距離s表示隨機(jī)生成的新果蠅A′與原果蠅A相比,每輛智能揀貨車的揀選順序中至多有s個(gè)批次的位置發(fā)生變化。
2.2.3 視覺搜索
在視覺搜索時(shí),通過計(jì)算每個(gè)果蠅對(duì)應(yīng)揀選方案的訂單延誤時(shí)間,對(duì)果蠅進(jìn)行評(píng)價(jià)。若新生的子種群中存在果蠅對(duì)應(yīng)揀選方案的訂單延誤時(shí)間更短,則由該果蠅代替原果蠅。因而,只有當(dāng)果蠅產(chǎn)生的子種群中具有較小的訂單總延誤時(shí)間時(shí),當(dāng)前果蠅才會(huì)被其相應(yīng)的子種群中最佳的新果蠅取代。
2.2.4 知識(shí)引導(dǎo)
為加快算法的收斂速度,本文在每次迭代后對(duì)精英果蠅進(jìn)行知識(shí)引導(dǎo)。基于批次分配問題的特性,知識(shí)庫被分為精英果蠅提供的批次分配經(jīng)驗(yàn)概率和批次排序的經(jīng)驗(yàn)概率兩部分。知識(shí)引導(dǎo)搜索包含智能揀貨車分配搜索和批次排序搜索兩個(gè)過程,每個(gè)果蠅都在知識(shí)庫的引導(dǎo)下通過知識(shí)引導(dǎo)搜索實(shí)現(xiàn)訂單總延誤時(shí)間最小化的目標(biāo)。
(1)智能揀貨車分配
使用輪盤賭策略對(duì)知識(shí)庫中批次分配的經(jīng)驗(yàn)概率進(jìn)行抽樣,通過為每個(gè)批次重新分配智能揀貨車來實(shí)現(xiàn)批次分配搜索。經(jīng)驗(yàn)概率初始化如下:
其中:P是智能揀貨車的數(shù)量,Pqp(g)表示第g次迭代時(shí)將批次q分配給智能揀貨車p的概率。每一次迭代后,精英果蠅的知識(shí)庫更新公式如下:
(2)批次排序
使用輪盤賭策略對(duì)知識(shí)庫中批次排序的經(jīng)驗(yàn)概率進(jìn)行抽樣,通過為每個(gè)智能揀貨車需要揀選的批次進(jìn)行排序來實(shí)現(xiàn)批次排序搜索。經(jīng)驗(yàn)概率初始化如下:
其中:K是批次可被分配給智能揀貨車揀選位置的最大數(shù),Pqk(g)表示第g次迭代時(shí)將揀選批次q排在智能揀貨車的第k揀選位置的概率。每一次迭代后,精英果蠅的批次排序經(jīng)驗(yàn)更新概率如下:
本章將通過比較訂單可拆分與不可拆分情形下數(shù)值算例SFOA的計(jì)算結(jié)果,研究訂單拆分策略對(duì)智能倉庫的訂單揀選效率的影響規(guī)律。為進(jìn)一步驗(yàn)證訂單可拆分時(shí)SFOA算法的性能,將SFOA與最早開始時(shí)間算法(Earliest Start Date, ESD)[19]、人工魚群算法(Artificial Fish, AF)、FOA三類算法進(jìn)行對(duì)比分析。上述算法統(tǒng)一運(yùn)用Windows 10平臺(tái)的MATLAB 2016b實(shí)現(xiàn),并在CPU頻率為2.3 GHz、內(nèi)存為8 GB的計(jì)算機(jī)上運(yùn)行。
實(shí)驗(yàn)采用單區(qū)型且具有200個(gè)存儲(chǔ)位置和兩個(gè)交叉通道的倉庫,其通道分布如圖3所示。倉庫起始(I/O)點(diǎn)位于倉庫的左下角,倉庫共有10個(gè)通道,從左向右依次從1到10號(hào)編號(hào),每個(gè)通道兩側(cè)各有20個(gè)貨位。倉庫中,每個(gè)貨位存放一類貨品,其編號(hào)如圖3所示。假設(shè)每個(gè)存儲(chǔ)位置的長度為1長度單位(LU),兩個(gè)通道間的距離為5 LU。設(shè)揀選員的行走速度vtravel=10 LU/min,每個(gè)批次的準(zhǔn)備時(shí)間tsetup=5 min。
本文選擇揀貨車數(shù)量為3、訂單數(shù)量為30的小規(guī)模算例進(jìn)行驗(yàn)證。為方便求解結(jié)果展示,實(shí)例驗(yàn)證中按相同比例縮小了揀貨車容量、訂單大小和批次準(zhǔn)備時(shí)間(揀貨車容量為9、訂單內(nèi)物品數(shù)量服從均勻分布U[1,5]、批次的準(zhǔn)備時(shí)間tsetup=1 min)。算法中其余參數(shù)與數(shù)值算例中的參數(shù)設(shè)置一致。該實(shí)例的訂單詳細(xì)數(shù)據(jù)由附錄中的表1給出。訂單揀選問題首先通過訂單分批算法對(duì)訂單進(jìn)行拆分,并組成批次。訂單分批算法的結(jié)果如圖4所示,圖中:q為批次編號(hào),i為訂單編號(hào),k為貨品編號(hào)。
在問題求解的第二階段,智能果蠅優(yōu)化算法對(duì)上述批次進(jìn)行分配與排序。這些任務(wù)批次被分配給不同智能揀貨車,并按照特定順序進(jìn)行揀選。求解結(jié)果如圖5所示。圖中,批次揀選時(shí)間通過甘特圖中矩形的長度體現(xiàn),批次揀選時(shí)間越長,矩形越長;反之亦然。
基于數(shù)值算例,比較不同問題規(guī)模下訂單可拆分與不可拆分時(shí)SFOA的結(jié)果,以及SFOA算法與同類型算法的性能。表1和表2中:tar表示5次獨(dú)立重復(fù)實(shí)驗(yàn)的平均訂單總延誤時(shí)間;time表示算法平均計(jì)算時(shí)間;Gap1為訂單可拆分與訂單不可拆分條件下,SFOA算法的計(jì)算結(jié)果比較,Gap1=(tar(不可拆分)-tar(可拆分))/tar(不可拆分)×100%;Gap2為SFOA與ESD算法的計(jì)算結(jié)果比較,Gap2=(tar(ESD)-tar(SFOA))/tar(ESD)×100%;Gap3為SFOA與AF算法的計(jì)算結(jié)果比較,Gap3=(tar(AF)-tar(SFOA))/tar(AF)×100%;Gap4為SFOA與FOA算法的計(jì)算結(jié)果比較,Gap4=(tar(FOA)-tar(SFOA))/tar(FOA)×100%。
表1 訂單可拆分與不可拆分情形下SFOA
續(xù)表1
表2 訂單可拆分情形下SFOA與現(xiàn)有算法的比較分析
表1比較了訂單可拆分與不可拆分情形下,SFOA求解的總延誤時(shí)間與計(jì)算時(shí)間。計(jì)算結(jié)果顯示,訂單可拆分時(shí)SFOA的計(jì)算時(shí)間有所增加,但訂單的總延誤時(shí)間顯著降低。比較兩者的計(jì)算結(jié)果發(fā)現(xiàn),訂單拆分策略能顯著降低智能倉庫的訂單總延誤時(shí)間,其改善范圍為8.33%(n=7,m=50)~48.61%(n=5,m=200)。
如圖6所示為訂單可拆分與不可拆分情形下,通過SFOA算法求解訂單揀選問題的訂單總延誤和計(jì)算時(shí)間。結(jié)果顯示,可拆分訂單的總延誤時(shí)間普遍優(yōu)于不可拆分訂單的總延誤時(shí)間,但可拆分時(shí)算法的計(jì)算時(shí)間普遍高于不可拆分時(shí)算法的計(jì)算時(shí)間。盡管拆分策略會(huì)增加SFOA算法的求解時(shí)間,但增加的時(shí)間相對(duì)原求解時(shí)間較少,且不會(huì)隨訂單大小的變化顯著上升。
為進(jìn)一步分析SFOA算法的性能,表2比較了訂單可拆分時(shí)SFOA算法與ESD算法、AF算法、FOA算法的計(jì)算結(jié)果。表2中結(jié)果顯示,本文提出的SFOA算法性能優(yōu)于其他同類型算法,SFOA算法相對(duì)ESD算法、AF算法、FOA算法能顯著降低訂單的總延誤時(shí)間,其提升范圍分別為11.36%(n=5;m=100)~34.55%(n=5,m=50)、0%(n=3;m=50)至61.72%(n=5;m=200)、2.70%(n=5;m=50)~64.71%(n=3;m=200)。
圖7a、圖7b分別比較了訂單可拆分時(shí)ESD算法、AF算法、FOA算法和SFOA算法的訂單總延誤時(shí)間、計(jì)算時(shí)間。結(jié)果顯示,SFOA算法在不同算例中的總延誤時(shí)間、計(jì)算時(shí)間均優(yōu)于其他算法。ESD算法、FOA算法的總延誤時(shí)間大于SFOA算法的總延誤時(shí)間,但ESD算法的計(jì)算時(shí)間隨訂單數(shù)量增長較快。AF算法在訂單數(shù)為50時(shí),與SFOA的計(jì)算結(jié)果相近,但隨著訂單數(shù)量的增加,AF算法的計(jì)算結(jié)果顯著降低。
本文以電子商務(wù)環(huán)境下,智能倉庫的訂單揀選問題為背景,研究了訂單拆分策略對(duì)智能倉庫揀選效率的影響。研究以最小化訂單總延誤時(shí)間為目標(biāo),構(gòu)建了考慮拆分策略的訂單揀選優(yōu)化模型。為提高模型的求解效率,基于問題的特性將其分解為訂單分批和批次分配兩個(gè)階段。針對(duì)訂單分批問題,提出了一種訂單分批算法,以保證每個(gè)批次中的訂單能占滿智能揀貨車的容量,同時(shí)使得每個(gè)批次中訂單截止時(shí)間的差值最小。由于第二階段的批次分配問題仍屬于NP-hard問題,本文在KGFOA的基礎(chǔ)上引入了NBR規(guī)則和雙知識(shí)庫,進(jìn)而提出了SFOA算法求解該問題。數(shù)值實(shí)驗(yàn)結(jié)果表明,訂單拆分策略能有效降低訂單的總延誤時(shí)間,且提出的SFOA算法相對(duì)已有算法具備更優(yōu)的計(jì)算結(jié)果和更快的計(jì)算時(shí)間。研究結(jié)果表明,訂單拆分策略能有效減少倉庫中訂單完成的延誤時(shí)間。因此在工業(yè)應(yīng)用中,企業(yè)處理限時(shí)配送任務(wù)時(shí)可將訂單拆分后依揀貨車的容量重新組成批次,進(jìn)而提高訂單配送的效率。
本文的研究為智能倉庫中訂單揀選算法的設(shè)計(jì)提供了思路,通過對(duì)訂單進(jìn)行拆分,可以更高效地完成限時(shí)訂單的揀選任務(wù)。但該研究也存在一定局限性。本文僅研究了訂單到達(dá)信息已知情況下的訂單揀選優(yōu)化,并未涉及在線訂單達(dá)到的優(yōu)化問題,同時(shí)也未考慮貨品的擺放位置、緊急訂單或智能倉庫中機(jī)器故障等特殊情況,未來的研究可針對(duì)這些因素進(jìn)行更深入的探討。