考慮拆分策略的智能倉庫訂單揀選優(yōu)化問題

萬明重，蔣忠中+，秦緒偉，喬 雙,李銘陽

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

0 引言

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

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

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

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

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

1 問題描述與模型建立

1.1 問題描述和符號定義

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

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

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延誤時間；

vtravel為智能揀貨車行駛速度；

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

tsetup為批次的準備、取貨時間；

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

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

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

針對智能倉庫的新特征，即當機械手和智能揀貨車代替了傳統(tǒng)的人工揀貨后，可以準確執(zhí)行復雜的揀貨方案，不必再遵守訂單不可被拆分的原則；同時為進一步提升揀貨車容量的利用率，本文在訂單分配問題中引入訂單拆分策略[8]。訂單拆分策略允許將單個訂單拆分為多個部分，并分配給不同批次進行揀選。因此，每個批次可包含多個訂單，每個訂單也可由多個批次共同完成。由于單個訂單需要在其包含的所有貨品都完成揀選后才能配送，訂單的完成時間取決于包含該訂單批次完成時間的最大值。基于上述特性，構建基于拆分策略的訂單揀選問題數(shù)學模型如下：

(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 模型的求解算法

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

2.1 訂單分批算法

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

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

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

步驟2選擇訂單集合Ω中截止時間最小的訂單Oi，該訂單包含貨品所需的智能揀貨車容量為Ci。令Cq表示當前批次Bq剩余的容量，

(1)若Ci+Cq≤C，將訂單Oi放入批次Bq，并將Oi從訂單集合Ω中移除。

(2)若Ci+Cq>C，對訂單Oi進行拆分：將訂單Oi中容量C-Cq的部分放入批次Bq，并將訂單Oi中容量Ci-(C-Cq)的部分放入新批次Bq+1；將Oi從訂單集合Ω中移除。

步驟3重復步驟2，直至訂單集合Ω為空。

通過訂單分批算法，可保證每個批次貨品恰好占滿智能揀貨車的容量。此外，只有當新加入批次中的訂單大小超過智能揀貨車剩余容量時，才對訂單進行拆分。因此，該算法可以保證每個訂單不被過度拆分。

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

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

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

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

(1)種群編碼。將問題的可行解通過實數(shù)編碼的形式表示出來。

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

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

(4)視覺搜索。評價每個子種群的果蠅，并用該種群中最好的果蠅代替掉原果蠅。

(5)知識引導。每個果蠅根據(jù)歷史經(jīng)驗進行知識引導搜索。

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

2.2.1 種群編碼

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

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

2.2.2 嗅覺搜索

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

2.2.3 視覺搜索

在視覺搜索時，通過計算每個果蠅對應揀選方案的訂單延誤時間，對果蠅進行評價。若新生的子種群中存在果蠅對應揀選方案的訂單延誤時間更短，則由該果蠅代替原果蠅。因而，只有當果蠅產(chǎn)生的子種群中具有較小的訂單總延誤時間時，當前果蠅才會被其相應的子種群中最佳的新果蠅取代。

2.2.4 知識引導

為加快算法的收斂速度，本文在每次迭代后對精英果蠅進行知識引導?；谂畏峙鋯栴}的特性，知識庫被分為精英果蠅提供的批次分配經(jīng)驗概率和批次排序的經(jīng)驗概率兩部分。知識引導搜索包含智能揀貨車分配搜索和批次排序搜索兩個過程，每個果蠅都在知識庫的引導下通過知識引導搜索實現(xiàn)訂單總延誤時間最小化的目標。

(1)智能揀貨車分配

使用輪盤賭策略對知識庫中批次分配的經(jīng)驗概率進行抽樣，通過為每個批次重新分配智能揀貨車來實現(xiàn)批次分配搜索。經(jīng)驗概率初始化如下：

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

(2)批次排序

使用輪盤賭策略對知識庫中批次排序的經(jīng)驗概率進行抽樣，通過為每個智能揀貨車需要揀選的批次進行排序來實現(xiàn)批次排序搜索。經(jīng)驗概率初始化如下：

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

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

本章將通過比較訂單可拆分與不可拆分情形下數(shù)值算例SFOA的計算結果，研究訂單拆分策略對智能倉庫的訂單揀選效率的影響規(guī)律。為進一步驗證訂單可拆分時SFOA算法的性能，將SFOA與最早開始時間算法(Earliest Start Date, ESD)[19]、人工魚群算法(Artificial Fish, AF)、FOA三類算法進行對比分析。上述算法統(tǒng)一運用Windows 10平臺的MATLAB 2016b實現(xiàn)，并在CPU頻率為2.3 GHz、內(nèi)存為8 GB的計算機上運行。

3.1 數(shù)值算例

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

3.2 實例驗證

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

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

3.3 結果分析

基于數(shù)值算例，比較不同問題規(guī)模下訂單可拆分與不可拆分時SFOA的結果，以及SFOA算法與同類型算法的性能。表1和表2中：tar表示5次獨立重復實驗的平均訂單總延誤時間;time表示算法平均計算時間；Gap1為訂單可拆分與訂單不可拆分條件下，SFOA算法的計算結果比較，Gap1=(tar(不可拆分)-tar(可拆分))/tar(不可拆分)×100%；Gap2為SFOA與ESD算法的計算結果比較，Gap2=(tar(ESD)-tar(SFOA))/tar(ESD)×100%；Gap3為SFOA與AF算法的計算結果比較，Gap3=(tar(AF)-tar(SFOA))/tar(AF)×100%；Gap4為SFOA與FOA算法的計算結果比較，Gap4=(tar(FOA)-tar(SFOA))/tar(FOA)×100%。

表1 訂單可拆分與不可拆分情形下SFOA

續(xù)表1

表2 訂單可拆分情形下SFOA與現(xiàn)有算法的比較分析

表1比較了訂單可拆分與不可拆分情形下，SFOA求解的總延誤時間與計算時間。計算結果顯示，訂單可拆分時SFOA的計算時間有所增加，但訂單的總延誤時間顯著降低。比較兩者的計算結果發(fā)現(xiàn)，訂單拆分策略能顯著降低智能倉庫的訂單總延誤時間，其改善范圍為8.33%(n=7,m=50)～48.61%(n=5,m=200)。

如圖6所示為訂單可拆分與不可拆分情形下，通過SFOA算法求解訂單揀選問題的訂單總延誤和計算時間。結果顯示，可拆分訂單的總延誤時間普遍優(yōu)于不可拆分訂單的總延誤時間，但可拆分時算法的計算時間普遍高于不可拆分時算法的計算時間。盡管拆分策略會增加SFOA算法的求解時間，但增加的時間相對原求解時間較少，且不會隨訂單大小的變化顯著上升。

為進一步分析SFOA算法的性能，表2比較了訂單可拆分時SFOA算法與ESD算法、AF算法、FOA算法的計算結果。表2中結果顯示，本文提出的SFOA算法性能優(yōu)于其他同類型算法，SFOA算法相對ESD算法、AF算法、FOA算法能顯著降低訂單的總延誤時間，其提升范圍分別為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分別比較了訂單可拆分時ESD算法、AF算法、FOA算法和SFOA算法的訂單總延誤時間、計算時間。結果顯示，SFOA算法在不同算例中的總延誤時間、計算時間均優(yōu)于其他算法。ESD算法、FOA算法的總延誤時間大于SFOA算法的總延誤時間，但ESD算法的計算時間隨訂單數(shù)量增長較快。AF算法在訂單數(shù)為50時，與SFOA的計算結果相近，但隨著訂單數(shù)量的增加，AF算法的計算結果顯著降低。

4 結束語

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

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