萬(wàn)明重，蔣忠中+，秦緒偉，喬 雙,李銘陽(yáng)

(1.東北大學(xué) 工商管理學(xué)院，遼寧 沈陽(yáng) 110167；2.東北大學(xué) 行為與服務(wù)運(yùn)作管理研究所，遼寧 沈陽(yáng) 110167；3.天津大學(xué) 管理與經(jīng)濟(jì)學(xué)部，天津 300072)

0 引言

伴隨著電子商務(wù)的高速發(fā)展，其對(duì)客戶訂單的配送服務(wù)也提出了更高的要求。天貓超市、京東商城等購(gòu)物平臺(tái)紛紛推出次日達(dá)、今日達(dá)等限時(shí)配送服務(wù)。通常地，配送服務(wù)包括客戶從下達(dá)訂單到送貨上門(mén)等流程，其中，倉(cāng)庫(kù)中的訂單揀選是配送服務(wù)的重要環(huán)節(jié)，屬于倉(cāng)庫(kù)作業(yè)中勞動(dòng)密集度和成本最高的活動(dòng)，其成本約占倉(cāng)庫(kù)總運(yùn)營(yíng)成本的55%以上[1]。傳統(tǒng)倉(cāng)庫(kù)中，為降低人工操作的失誤，訂單揀選通常要求訂單不被拆分，即每個(gè)訂單只能分配給一名揀選員[1]，但也限制了訂單揀選作業(yè)的效率。借助新興的信息技術(shù)，智能倉(cāng)庫(kù)可輕松地實(shí)現(xiàn)訂單任務(wù)拆分和重組，為訂單揀選作業(yè)效率的提高創(chuàng)造了有利條件。以京東智能倉(cāng)庫(kù)——無(wú)人倉(cāng)為例，基于3D視覺(jué)識(shí)別等技術(shù)，運(yùn)用智能小車(chē)、揀貨機(jī)器人、機(jī)械手等設(shè)備代替?zhèn)鹘y(tǒng)的揀貨員和揀貨車(chē)，一方面避免了人工操作可能帶來(lái)的失誤，另一方面實(shí)現(xiàn)了倉(cāng)庫(kù)的自動(dòng)揀選、智能打包等功能?？梢?jiàn)，相對(duì)于傳統(tǒng)倉(cāng)庫(kù)，訂單可拆分是智能倉(cāng)庫(kù)揀選作業(yè)的新特征，因此如何實(shí)現(xiàn)訂單可拆分情形下的揀選作業(yè)優(yōu)化是企業(yè)實(shí)現(xiàn)智能倉(cāng)庫(kù)高效運(yùn)作的重要決策問(wèn)題。

近年來(lái)，訂單揀選優(yōu)化問(wèn)題備受學(xué)者關(guān)注，國(guó)內(nèi)外文獻(xiàn)從訂單分批、批次分配和揀貨車(chē)路徑優(yōu)化等角度對(duì)訂單揀選問(wèn)題進(jìn)行了研究。訂單分批是將不同訂單組成批次，交由揀貨車(chē)同時(shí)揀?。慌畏峙涫菍⑦@些批次分配給不同揀貨車(chē)，并確定其揀貨順序。國(guó)外方面，SCHOLZ等[2]研究了訂單分批、批次分配問(wèn)題，其目標(biāo)是使訂單總延誤時(shí)間最??；ARDJMAND等[3]研究了按波次揀選倉(cāng)庫(kù)中訂單分批和批次分配問(wèn)題，其目標(biāo)是最小化訂單總完工時(shí)間；THEYS等[4]和GLOCK等[5]研究了倉(cāng)庫(kù)揀選的路徑優(yōu)化問(wèn)題，并分別將其轉(zhuǎn)化有旅行商問(wèn)題(Traveling Salesman Problem, TSP)和有容量限制的車(chē)輛路徑優(yōu)化問(wèn)題(Capacitated Vehicle Routing Problem, CVRP)。國(guó)內(nèi)方面，梁旭[6]和鄒霞等[7]對(duì)傳統(tǒng)倉(cāng)庫(kù)中訂單的調(diào)度問(wèn)題進(jìn)行了研究。上述針對(duì)傳統(tǒng)倉(cāng)庫(kù)訂單揀選問(wèn)題的研究中，為降低揀貨員在作業(yè)中的失誤率，通常較少考慮訂單可拆分的情況。

隨著智能化技術(shù)的發(fā)展，倉(cāng)庫(kù)逐漸開(kāi)始使用自動(dòng)導(dǎo)引車(chē)(Automated Guided Vehicle, AGV)、揀貨機(jī)器人、智能揀貨車(chē)等代替?zhèn)鹘y(tǒng)的人工揀選，部分學(xué)者也開(kāi)始研究訂單拆分策略下的倉(cāng)庫(kù)揀選問(wèn)題。訂單拆分策略下，一個(gè)訂單可被拆分成多個(gè)部分并分配給不同批次或揀貨車(chē)。ARCHETRI等[8]研究表明，訂單拆分策略有助于提高揀貨車(chē)容量的利用率，進(jìn)而提高訂單揀選的效率。CERGIBOZAN等[9]研究指出，若單個(gè)訂單較大無(wú)法由一輛揀貨車(chē)完成揀選任務(wù)時(shí)，可對(duì)訂單進(jìn)行拆分，并交由多輛揀貨車(chē)進(jìn)行揀選。PARIKH等[10]研究了倉(cāng)庫(kù)分區(qū)條件下的訂單分批、揀選問(wèn)題，研究將單個(gè)訂單依貨品的存儲(chǔ)區(qū)域拆分給多個(gè)部分，并交由每個(gè)區(qū)域的揀貨車(chē)同時(shí)進(jìn)行揀選，其目標(biāo)是最小化揀貨車(chē)的空閑時(shí)間。BRIANT等[11]基于HappyChic公司的案例研究了考慮訂單拆分策略的訂單分配、揀貨車(chē)路由問(wèn)題，其目標(biāo)是最小化揀貨車(chē)的總行走距離。

在處理限時(shí)訂單的揀選、配送問(wèn)題中，確保訂單按時(shí)完成配送是最重要的目標(biāo)。但考慮訂單拆分策略的現(xiàn)有研究中，尚未對(duì)最小化訂單總延誤時(shí)間的問(wèn)題進(jìn)行探討。基于此，本文首次在以最小化訂單總延誤時(shí)間為目標(biāo)的訂單揀選問(wèn)題中考慮了訂單拆分策略。當(dāng)訂單允許被拆分時(shí)，某個(gè)訂單可被拆分成多個(gè)部分并分配給不同批次；而只有當(dāng)該訂單需要的所有貨品都被揀選后，才能對(duì)該訂單進(jìn)行配送。此時(shí)，訂單的完成時(shí)間由包含該訂單的所有批次共同決定。因此，訂單拆分策略使得以目標(biāo)為最小化訂單總延誤時(shí)間的訂單揀選問(wèn)題相對(duì)傳統(tǒng)倉(cāng)庫(kù)的訂單揀選問(wèn)題更為復(fù)雜。

為此，本文針對(duì)智能倉(cāng)庫(kù)的訂單揀選優(yōu)化問(wèn)題的新特征，研究考慮拆分策略的訂單揀選優(yōu)化模型與算法，并探討拆分策略和算法設(shè)計(jì)對(duì)于訂單揀選作業(yè)效率的影響規(guī)律。首先，以訂單總延誤時(shí)間最小化為目標(biāo)，構(gòu)建考慮拆分策略的訂單揀選優(yōu)化模型；其次，依據(jù)模型特點(diǎn)將該問(wèn)題分解為訂單分批和批次分配兩階段，并分別提出了訂單分批算法和智能果蠅優(yōu)化算法對(duì)模型進(jìn)行求解；最后，通過(guò)數(shù)值算例計(jì)算和對(duì)比分析，驗(yàn)證了所提算法的高效性。研究結(jié)果表明，在拆分策略情形下訂單總延誤時(shí)間顯著減小，進(jìn)而大幅度提升了訂單揀選作業(yè)的效率。

1 問(wèn)題描述與模型建立

1.1 問(wèn)題描述和符號(hào)定義

訂單揀選作業(yè)流程一般包括訂單分批、批次分配和揀選路由3部分。訂單分批是將多張訂單組成不同批次；批次分配是將組成的不同批次分配給揀選員(智能小車(chē)或智能揀貨車(chē))，并確定批次的揀選順序；揀貨路由則是揀選員依據(jù)分配訂單確定揀貨路徑。在電子商務(wù)環(huán)境下，考慮智能倉(cāng)庫(kù)可實(shí)現(xiàn)訂單拆分的新特征，其訂單揀選問(wèn)題描述如下：倉(cāng)庫(kù)將某時(shí)段接收到的多張客戶訂單，通過(guò)訂單拆分并依據(jù)其截止時(shí)間組成不同批次，再由智能揀貨車(chē)根據(jù)批次進(jìn)行揀選路由，最后將屬于同一客戶訂單的貨品整合在一起，并進(jìn)行復(fù)核和打包。如圖1所示為訂單揀選的具體流程，由于智能倉(cāng)庫(kù)的自動(dòng)化水平較高，訂單拆分和分批可快速地自動(dòng)完成(花費(fèi)時(shí)間可忽略)，訂單揀選花費(fèi)時(shí)間主要體現(xiàn)在智能揀貨車(chē)行走時(shí)間和取貨時(shí)間方面。行走時(shí)間是指智能揀貨車(chē)完成從倉(cāng)庫(kù)起點(diǎn)開(kāi)始逐個(gè)訪問(wèn)訂單貨品所需揀選位置并返回倉(cāng)庫(kù)起點(diǎn)的路徑所花費(fèi)的時(shí)間(假設(shè)行走速度恒定，則行走時(shí)間取決于智能揀貨車(chē)的行駛距離)；取貨時(shí)間是指智能揀貨車(chē)到達(dá)指定揀選位置后取出貨品所需的時(shí)間。

研究以單區(qū)型智能倉(cāng)庫(kù)為例，智能揀貨車(chē)按照包含U-turn的S型路徑揀選貨品[12]，即揀貨車(chē)在完成最后一通道的貨品揀選后立即返回，而不是繼續(xù)按照S路徑走完通道。為方便機(jī)械手存取貨品，智能倉(cāng)庫(kù)中揀貨車(chē)的貨框往往使用托盤(pán)或隔板劃分出若干個(gè)區(qū)域，每個(gè)區(qū)域存放至多一件貨品。因此，本文中揀貨車(chē)容量C亦指揀貨車(chē)貨框中托盤(pán)的個(gè)數(shù)(或隔板劃分的區(qū)域個(gè)數(shù))。智能揀貨車(chē)接收批次任務(wù)的時(shí)刻記為批次的開(kāi)始時(shí)間，智能揀貨車(chē)完成揀選任務(wù)回到起始點(diǎn)的時(shí)刻記為批次的完成時(shí)間。當(dāng)被拆分的訂單中所需的全部貨品揀選完成時(shí)，該訂單被完成；訂單的延誤時(shí)間為該訂單的完成時(shí)間減去該訂單的截止時(shí)間?；诖耍瑔?wèn)題的基本假設(shè)如下：①倉(cāng)庫(kù)中存儲(chǔ)貨品的位置是固定的，且每個(gè)位置只存放一種貨品，智能揀貨車(chē)行走在巷道的中間可同時(shí)從左右兩邊揀選貨品;②智能揀貨車(chē)直至當(dāng)前任務(wù)完成后才能開(kāi)始下一個(gè)任務(wù)，中間不可被打斷;③每個(gè)批次中貨品的體積不得超過(guò)智能揀貨車(chē)的容量;④每個(gè)訂單至少包含一件貨品。問(wèn)題的模型參數(shù)和變量包括：

(1)模型參數(shù)

I為客戶訂單集合，i∈I={1,2,…,m}；

P為智能揀貨車(chē)集合，p∈P={1,2,…,n}；

Q為訂單批次集合，q∈Q={1,2,…,|Q|}；

K為貨品集合，k∈K={1,2,…,|K|}；

C為智能揀貨車(chē)容量；

B為智能倉(cāng)庫(kù)中兩相鄰?fù)ǖ篱g的距離；

L為智能倉(cāng)庫(kù)中通道的長(zhǎng)度；

(2)決策變量

xiqk為0-1變量，若批次q包含訂單i中的貨品k，則xiqk=1，否則xiqk=0；

ypqq′為0-1變量，若批次q′緊接著批次q由智能揀貨車(chē)p揀取，則ypqq′=1，否則ypqq′=0。

(3)輔助變量

τi為訂單i延誤時(shí)間；

vtravel為智能揀貨車(chē)行駛速度；

disq為完成批次q所需行走距離；

tsetup為批次的準(zhǔn)備、取貨時(shí)間；

Aq為揀選批次q中的貨品需要訪問(wèn)的通道數(shù)量；

1.2 拆分策略和優(yōu)化模型

傳統(tǒng)的訂單揀選問(wèn)題中，一般遵循訂單不可被拆分的原則。但由于每個(gè)訂單包含的貨品種類和數(shù)量不同，揀選每個(gè)訂單所需的揀貨車(chē)容量也不同，需要將不同訂單進(jìn)行組合來(lái)提高揀貨車(chē)容量的利用率。理想的情況是組成同一批次的訂單恰好占滿整個(gè)揀貨車(chē)且具有相同的截止時(shí)間。但在實(shí)際問(wèn)題中，不同訂單的組合很難恰好占滿揀貨車(chē)，訂單的截止時(shí)間不盡相同，因此以上兩方面目標(biāo)很難同時(shí)達(dá)到最優(yōu)。

針對(duì)智能倉(cāng)庫(kù)的新特征，即當(dāng)機(jī)械手和智能揀貨車(chē)代替了傳統(tǒng)的人工揀貨后，可以準(zhǔn)確執(zhí)行復(fù)雜的揀貨方案，不必再遵守訂單不可被拆分的原則；同時(shí)為進(jìn)一步提升揀貨車(chē)容量的利用率，本文在訂單分配問(wèn)題中引入訂單拆分策略[8]。訂單拆分策略允許將單個(gè)訂單拆分為多個(gè)部分，并分配給不同批次進(jìn)行揀選。因此，每個(gè)批次可包含多個(gè)訂單，每個(gè)訂單也可由多個(gè)批次共同完成。由于單個(gè)訂單需要在其包含的所有貨品都完成揀選后才能配送，訂單的完成時(shí)間取決于包含該訂單批次完成時(shí)間的最大值?；谏鲜鎏匦?，構(gòu)建基于拆分策略的訂單揀選問(wèn)題數(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)

2 模型的求解算法

以最小化總延誤時(shí)間為目標(biāo)的訂單揀選問(wèn)題屬于NP-hard問(wèn)題，當(dāng)問(wèn)題規(guī)模較大時(shí)很難高效求解[13]。由于在電子商務(wù)環(huán)境下，商家需要處理大量緊急的訂單(今日達(dá)、次日達(dá)等)，因而期望算法能在較短的時(shí)間內(nèi)得到高質(zhì)量的解。為實(shí)現(xiàn)這一目標(biāo)，本文針對(duì)考慮拆分策略的訂單揀選問(wèn)題的特點(diǎn)進(jìn)行深入分析，結(jié)果發(fā)現(xiàn)，若同時(shí)處理訂單分批與批次分配問(wèn)題，則每次對(duì)批次進(jìn)行分配時(shí)都需要計(jì)算完成該批次揀選任務(wù)所需時(shí)間，從而導(dǎo)致計(jì)算十分耗時(shí)。鑒于此，本文提出將問(wèn)題拆分成訂單分批和批次分配兩階段的求解思路。在訂單分批階段，將訂單按需求進(jìn)行拆分，并根據(jù)訂單的截止時(shí)間重新組成批次。完成訂單分批后，每個(gè)批次的揀選時(shí)間可以直接計(jì)算得到。在批次分配階段，算法基于訂單分批的結(jié)果進(jìn)行批次分配，因此不用重復(fù)計(jì)算批次的揀選時(shí)間，只需要將以上批次分配給不同揀貨車(chē)，并確定這些批次的揀選順序。上述兩階段拆分求解思路可使得模型的計(jì)算時(shí)間顯著降低。此外，兩階段拆分求解思路實(shí)質(zhì)上只是改變了訂單揀選問(wèn)題決策的順序，并不會(huì)影響模型的正確性。

2.1 訂單分批算法

訂單分批問(wèn)題是將不同的訂單組成批次，其目標(biāo)是最大化智能揀貨車(chē)容量的利用率，且最小化同一批次中訂單截止時(shí)間的差值。在不考慮拆分策略的訂單分批問(wèn)題中，為了提高揀貨車(chē)容量的利用率，需要將不同大小(貨品數(shù)量不同)的訂單進(jìn)行組合。由于不同訂單的截止時(shí)間不一致，無(wú)法保證組成同一批次的訂單恰好占滿揀貨車(chē)的容量，且訂單的截止時(shí)間相近。

訂單拆分策略可以較好地處理上述問(wèn)題。在進(jìn)行訂單分批時(shí)，按照訂單截止時(shí)間的升序逐個(gè)選取訂單并組成批次。若新加入批次的訂單大小超過(guò)智能揀貨車(chē)的剩余容量，則對(duì)該訂單進(jìn)行拆分，并將多出的部分訂單放入新的批次。該算法的詳細(xì)步驟如下：

步驟1獲取全部的訂單集合Ω，生成一個(gè)空的初始批次Bq。

步驟2選擇訂單集合Ω中截止時(shí)間最小的訂單Oi，該訂單包含貨品所需的智能揀貨車(chē)容量為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，直至訂單集合Ω為空。

通過(guò)訂單分批算法，可保證每個(gè)批次貨品恰好占滿智能揀貨車(chē)的容量。此外，只有當(dāng)新加入批次中的訂單大小超過(guò)智能揀貨車(chē)剩余容量時(shí)，才對(duì)訂單進(jìn)行拆分。因此，該算法可以保證每個(gè)訂單不被過(guò)度拆分。

推論1訂單分批算法中，任意一個(gè)訂單至多被拆分成兩部分，且一個(gè)批次中至多包含兩個(gè)被拆分的訂單。

在訂單分批階段，若干個(gè)訂單組成一個(gè)批次。當(dāng)考慮訂單分配策略時(shí)，部分訂單被拆分成若干部分并在不同批次進(jìn)行揀選。此時(shí)，被拆分訂單的完成時(shí)間取決于它所屬批次的最大批次完成時(shí)間。為提高訂單揀選效率，在訂單的批次分配時(shí)，應(yīng)考慮被拆分訂單的齊套性[14](使得同一訂單被拆分的部分盡可能同時(shí)完成)。若訂單被過(guò)度拆分，會(huì)使得批次分配階段的計(jì)算過(guò)于復(fù)雜。

2.2 智能果蠅優(yōu)化算法

FOA是模仿果蠅通過(guò)嗅覺(jué)和視覺(jué)尋找食物的算法。果蠅可以通過(guò)敏感的嗅覺(jué)發(fā)現(xiàn)遠(yuǎn)處的食物，并在接近后通過(guò)視覺(jué)找到食物的位置。通過(guò)嗅覺(jué)和視覺(jué)的指引，可以幫助果蠅快速接近食物，并準(zhǔn)確找到食物的位置。FOA通過(guò)模仿這一行為，很好地協(xié)調(diào)了算法的全局搜索能力和局部搜索能力：先通過(guò)嗅覺(jué)搜索找到較優(yōu)解，再通過(guò)視覺(jué)搜索在較優(yōu)解附近進(jìn)一步尋找更優(yōu)的解；如此循環(huán)，直到收斂。ZHENG等[17]近一步改進(jìn)了FOA，并提出知識(shí)引導(dǎo)的果蠅優(yōu)化算法(Knowledge Guided FOA, KGFOA)。KGFOA通過(guò)根據(jù)果蠅的歷史經(jīng)驗(yàn)，對(duì)果蠅的搜索方向進(jìn)行引導(dǎo)，進(jìn)而加快算法的收斂速度。該算法主要包括以下步驟：

(1)種群編碼。將問(wèn)題的可行解通過(guò)實(shí)數(shù)編碼的形式表示出來(lái)。

(2)初始化種群。隨機(jī)生成一系類初始可行解(初始果蠅)。

(3)嗅覺(jué)搜索。在每個(gè)果蠅的嗅覺(jué)范圍內(nèi)隨機(jī)生成若干個(gè)果蠅，形成子種群。

(4)視覺(jué)搜索。評(píng)價(jià)每個(gè)子種群的果蠅，并用該種群中最好的果蠅代替掉原果蠅。

(5)知識(shí)引導(dǎo)。每個(gè)果蠅根據(jù)歷史經(jīng)驗(yàn)進(jìn)行知識(shí)引導(dǎo)搜索。

FOA與KGFOA的嗅覺(jué)搜索未限制新果蠅產(chǎn)生的方式，使得該算法能結(jié)合確定性方法或啟發(fā)式規(guī)則加快FOA的收斂速度。鑒于此，本文選用KGFOA算法，并在算法的嗅覺(jué)搜索階段結(jié)合網(wǎng)絡(luò)效益重組(Net Benefit of Relocation, NBR)[18]規(guī)則對(duì)算法進(jìn)行改進(jìn)，以提高算法的收斂速度。NBR規(guī)則是一類基于貪婪法近似求解單服務(wù)臺(tái)調(diào)度問(wèn)題的規(guī)則。本文將NBR規(guī)則融入嗅覺(jué)搜索過(guò)程，減少了不必要的搜索空間，提高了嗅覺(jué)搜索的效率。隨后，本文基于批次分配問(wèn)題的特性構(gòu)建了批次分配經(jīng)驗(yàn)概率和批次排序的經(jīng)驗(yàn)概率兩個(gè)知識(shí)庫(kù)，從而提高了知識(shí)引導(dǎo)的性能?；诖?，本文通過(guò)改進(jìn)KGFOA的嗅覺(jué)搜索和知識(shí)引導(dǎo)過(guò)程，提出智能果蠅優(yōu)化算法(Smart FOA, SFOA)。相比已有的果蠅優(yōu)化算法，SFOA中果蠅不僅依靠隨機(jī)搜索的方法尋找最優(yōu)解(近優(yōu)解)，還能應(yīng)用NBR規(guī)則和知識(shí)庫(kù)更智能地搜索最優(yōu)解(近優(yōu)解)。SFOA的算法流程如圖2所示。

2.2.1 種群編碼

批次分配問(wèn)題的決策包括不同批次與智能揀貨車(chē)的匹配，以及智能揀貨車(chē)進(jìn)行批次揀選的順序。因此，果蠅的編碼由批次與智能揀貨車(chē)的匹配、批次的揀選順序兩方面信息組成。鑒于此，本文通過(guò)實(shí)數(shù)向量A來(lái)表示果蠅的編碼，每個(gè)果蠅的編碼可表示為：

A=[A1,A2,…,An],

2.2.2 嗅覺(jué)搜索

嗅覺(jué)搜索時(shí)給定果蠅的嗅覺(jué)范圍為(z,s)，即果蠅只能在距離(z,s)內(nèi)進(jìn)行嗅覺(jué)搜索。其中距離z表示隨機(jī)生成的新果蠅A′與原果蠅A相比，至多有z個(gè)批次被指派的智能揀貨車(chē)不同；距離s表示隨機(jī)生成的新果蠅A′與原果蠅A相比，每輛智能揀貨車(chē)的揀選順序中至多有s個(gè)批次的位置發(fā)生變化。

2.2.3 視覺(jué)搜索

在視覺(jué)搜索時(shí)，通過(guò)計(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)?；谂畏峙鋯?wèn)題的特性，知識(shí)庫(kù)被分為精英果蠅提供的批次分配經(jīng)驗(yàn)概率和批次排序的經(jīng)驗(yàn)概率兩部分。知識(shí)引導(dǎo)搜索包含智能揀貨車(chē)分配搜索和批次排序搜索兩個(gè)過(guò)程，每個(gè)果蠅都在知識(shí)庫(kù)的引導(dǎo)下通過(guò)知識(shí)引導(dǎo)搜索實(shí)現(xiàn)訂單總延誤時(shí)間最小化的目標(biāo)。

(1)智能揀貨車(chē)分配

使用輪盤(pán)賭策略對(duì)知識(shí)庫(kù)中批次分配的經(jīng)驗(yàn)概率進(jìn)行抽樣，通過(guò)為每個(gè)批次重新分配智能揀貨車(chē)來(lái)實(shí)現(xiàn)批次分配搜索。經(jīng)驗(yàn)概率初始化如下：

其中：P是智能揀貨車(chē)的數(shù)量，Pqp(g)表示第g次迭代時(shí)將批次q分配給智能揀貨車(chē)p的概率。每一次迭代后，精英果蠅的知識(shí)庫(kù)更新公式如下：

(2)批次排序

使用輪盤(pán)賭策略對(duì)知識(shí)庫(kù)中批次排序的經(jīng)驗(yàn)概率進(jìn)行抽樣，通過(guò)為每個(gè)智能揀貨車(chē)需要揀選的批次進(jìn)行排序來(lái)實(shí)現(xiàn)批次排序搜索。經(jīng)驗(yàn)概率初始化如下：

其中：K是批次可被分配給智能揀貨車(chē)揀選位置的最大數(shù)，Pqk(g)表示第g次迭代時(shí)將揀選批次q排在智能揀貨車(chē)的第k揀選位置的概率。每一次迭代后，精英果蠅的批次排序經(jīng)驗(yàn)更新概率如下：

3 數(shù)值算例與結(jié)果分析

本章將通過(guò)比較訂單可拆分與不可拆分情形下數(shù)值算例SFOA的計(jì)算結(jié)果，研究訂單拆分策略對(duì)智能倉(cāng)庫(kù)的訂單揀選效率的影響規(guī)律。為進(jìn)一步驗(yàn)證訂單可拆分時(shí)SFOA算法的性能，將SFOA與最早開(kāi)始時(shí)間算法(Earliest Start Date, ESD)[19]、人工魚(yú)群算法(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)行。

3.1 數(shù)值算例

實(shí)驗(yàn)采用單區(qū)型且具有200個(gè)存儲(chǔ)位置和兩個(gè)交叉通道的倉(cāng)庫(kù)，其通道分布如圖3所示。倉(cāng)庫(kù)起始(I/O)點(diǎn)位于倉(cāng)庫(kù)的左下角，倉(cāng)庫(kù)共有10個(gè)通道，從左向右依次從1到10號(hào)編號(hào)，每個(gè)通道兩側(cè)各有20個(gè)貨位。倉(cāng)庫(kù)中，每個(gè)貨位存放一類貨品，其編號(hào)如圖3所示。假設(shè)每個(gè)存儲(chǔ)位置的長(zhǎng)度為1長(zhǎng)度單位(LU)，兩個(gè)通道間的距離為5 LU。設(shè)揀選員的行走速度vtravel=10 LU/min，每個(gè)批次的準(zhǔn)備時(shí)間tsetup=5 min。

3.2 實(shí)例驗(yàn)證

本文選擇揀貨車(chē)數(shù)量為3、訂單數(shù)量為30的小規(guī)模算例進(jìn)行驗(yàn)證。為方便求解結(jié)果展示，實(shí)例驗(yàn)證中按相同比例縮小了揀貨車(chē)容量、訂單大小和批次準(zhǔn)備時(shí)間(揀貨車(chē)容量為9、訂單內(nèi)物品數(shù)量服從均勻分布U[1,5]、批次的準(zhǔn)備時(shí)間tsetup=1 min)。算法中其余參數(shù)與數(shù)值算例中的參數(shù)設(shè)置一致。該實(shí)例的訂單詳細(xì)數(shù)據(jù)由附錄中的表1給出。訂單揀選問(wèn)題首先通過(guò)訂單分批算法對(duì)訂單進(jìn)行拆分，并組成批次。訂單分批算法的結(jié)果如圖4所示，圖中：q為批次編號(hào)，i為訂單編號(hào)，k為貨品編號(hào)。

在問(wèn)題求解的第二階段，智能果蠅優(yōu)化算法對(duì)上述批次進(jìn)行分配與排序。這些任務(wù)批次被分配給不同智能揀貨車(chē)，并按照特定順序進(jìn)行揀選。求解結(jié)果如圖5所示。圖中，批次揀選時(shí)間通過(guò)甘特圖中矩形的長(zhǎng)度體現(xiàn)，批次揀選時(shí)間越長(zhǎng)，矩形越長(zhǎng)；反之亦然。

3.3 結(jié)果分析

基于數(shù)值算例，比較不同問(wèn)題規(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)，訂單拆分策略能顯著降低智能倉(cāng)庫(kù)的訂單總延誤時(shí)間，其改善范圍為8.33%(n=7,m=50)～48.61%(n=5,m=200)。

如圖6所示為訂單可拆分與不可拆分情形下，通過(guò)SFOA算法求解訂單揀選問(wèn)題的訂單總延誤和計(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ù)量增長(zhǎng)較快。AF算法在訂單數(shù)為50時(shí)，與SFOA的計(jì)算結(jié)果相近，但隨著訂單數(shù)量的增加，AF算法的計(jì)算結(jié)果顯著降低。

4 結(jié)束語(yǔ)

本文以電子商務(wù)環(huán)境下，智能倉(cāng)庫(kù)的訂單揀選問(wèn)題為背景，研究了訂單拆分策略對(duì)智能倉(cāng)庫(kù)揀選效率的影響。研究以最小化訂單總延誤時(shí)間為目標(biāo)，構(gòu)建了考慮拆分策略的訂單揀選優(yōu)化模型。為提高模型的求解效率，基于問(wèn)題的特性將其分解為訂單分批和批次分配兩個(gè)階段。針對(duì)訂單分批問(wèn)題，提出了一種訂單分批算法，以保證每個(gè)批次中的訂單能占滿智能揀貨車(chē)的容量，同時(shí)使得每個(gè)批次中訂單截止時(shí)間的差值最小。由于第二階段的批次分配問(wèn)題仍屬于NP-hard問(wèn)題，本文在KGFOA的基礎(chǔ)上引入了NBR規(guī)則和雙知識(shí)庫(kù)，進(jìn)而提出了SFOA算法求解該問(wèn)題。數(shù)值實(shí)驗(yàn)結(jié)果表明，訂單拆分策略能有效降低訂單的總延誤時(shí)間，且提出的SFOA算法相對(duì)已有算法具備更優(yōu)的計(jì)算結(jié)果和更快的計(jì)算時(shí)間。研究結(jié)果表明，訂單拆分策略能有效減少倉(cāng)庫(kù)中訂單完成的延誤時(shí)間。因此在工業(yè)應(yīng)用中，企業(yè)處理限時(shí)配送任務(wù)時(shí)可將訂單拆分后依揀貨車(chē)的容量重新組成批次，進(jìn)而提高訂單配送的效率。

本文的研究為智能倉(cāng)庫(kù)中訂單揀選算法的設(shè)計(jì)提供了思路，通過(guò)對(duì)訂單進(jìn)行拆分，可以更高效地完成限時(shí)訂單的揀選任務(wù)。但該研究也存在一定局限性。本文僅研究了訂單到達(dá)信息已知情況下的訂單揀選優(yōu)化，并未涉及在線訂單達(dá)到的優(yōu)化問(wèn)題，同時(shí)也未考慮貨品的擺放位置、緊急訂單或智能倉(cāng)庫(kù)中機(jī)器故障等特殊情況，未來(lái)的研究可針對(duì)這些因素進(jìn)行更深入的探討。