楊 瑋, 鄭傳輝, 李 然, 徐 丹

(陜西科技大學(xué) 機電工程學(xué)院, 陜西 西安 710021)

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的迅猛提升,電商行業(yè)發(fā)展愈發(fā)繁榮,訂單揀選效率備受關(guān)注,如何在緊湊的交貨期內(nèi)處理海量客戶訂單實現(xiàn)“快速交付”,不斷提高客戶滿意度,已然成為企業(yè)鞏固自身核心競爭力的關(guān)鍵所在.Bahrami B等[1]將訂單分揀(Order Picking,OP)定義為涉及從指定的儲存位置檢索產(chǎn)品以滿足客戶需求的過程,并被認為是倉庫中最勞動密集型的作業(yè),約占為倉庫作業(yè)成本的55%.此外雖人到貨揀選系統(tǒng)(Pickers-to-Goods,PTG)所需的投資相當?shù)?但缺點是揀貨人員行走時間占總訂單分揀時間的50%以上[2,3].

“貨到人”揀選系統(tǒng)(Goods-to-Pickers,GTP)是為適應(yīng)配送中心完成多品種、高頻率、小批量的海量客戶需求而提出的新模式,由儲存系統(tǒng)、輸送系統(tǒng)、揀選系統(tǒng)三部分組成.相對于傳統(tǒng)的人到貨揀選系統(tǒng)(Pickers-to-Goods,PTG),可有效避免揀貨人員行走于貨架之間的冗余時間,降低勞動強度、提高揀選效率,近些年來被廣泛應(yīng)用于電商、服裝、醫(yī)藥等行業(yè).而移動機器人履行系統(tǒng)(Robotic Mobile Fulfillment Systems,RMFS)是“貨到人”揀選系統(tǒng)的主流揀選形式.該系統(tǒng)可根據(jù)訂單波峰波谷調(diào)整移動機器人及貨架的數(shù)量,使系統(tǒng)對揀選量變化較大的配送中心能夠作出迅速的調(diào)整及重規(guī)劃,這使RMFS揀選系統(tǒng)具備柔性強、成本低等優(yōu)點,有利于提高系統(tǒng)的整體生產(chǎn)率和效率.

在GTP系統(tǒng)訂單分批研究中,已有文獻研究各種情況下的訂單揀選問題[4].李珍萍等[5]建立了訂單分批揀選聯(lián)合優(yōu)化問題的混合整數(shù)規(guī)劃模型,目標是最小化貨箱出庫總次數(shù).李珍萍等[6]以訂單分批揀選總成本極小化為目標,給出了基于商品品項信息和貨架信息的類中心的定義,提出了K-max聚類算法求解訂單分批問題.陳廣鋒等[7]以最佳貨位的最大完工時間為目標建立了數(shù)學(xué)模型,利用拉格朗日差值方法優(yōu)化了差分進化算法局部搜索的能力.胡金昌等[8]以最小化料箱出入庫數(shù)量為目標,來解決訂單排序優(yōu)化客戶分批問題,提出種子算法和遺傳算法進行求解,實驗表明不同的方法可以依據(jù)不同的規(guī)模場景提高系統(tǒng)效率.萬明重等[9]設(shè)計訂單分批算法和智能果蠅優(yōu)化算法,實驗表明考慮拆分策略能夠明顯減小訂單揀選的總延遲時間.

劉凱等[10]提出求解訂單分批問題的啟發(fā)式聚類算法,并設(shè)計了仿真實驗將所提策略與隨機分批方式進行對比.吳仁超等[11]針對訂單分批問題,提出了一種混合元啟發(fā)式算法,實驗表明,所提分批算法在求解質(zhì)量上要優(yōu)于多重變鄰域搜索、禁忌搜索等算法.Nicolas L等[12]以最小化總完成時間為目標構(gòu)建了訂單批處理模型,提出了一種元啟發(fā)式方法求解模型,并將其拓展到倉庫中具有多個分區(qū)的情況.Cav A等[13]以最小化揀貨距離為目標建立了訂單分批模型,提出了一種啟發(fā)式算法求解整數(shù)規(guī)劃模型.Chen等[14]提出了混合粒子群優(yōu)化( PSO)和ACO算法,求解以最小化行駛總距離為目標的訂單分批問題.

在處理限時訂單的揀選﹑配送問題中,保障訂單及時到達客戶,提高客戶滿意度這一目標對于處理限時客戶訂單是至關(guān)重要的因素.只有少數(shù)學(xué)者將總延遲時間作為優(yōu)化目標融入至訂單分批問題中.趙金龍等[15]建立以最小化總延遲時間的整數(shù)規(guī)劃模型,利用改進的智能果蠅優(yōu)化算法確定訂單分配和排序決策;Chen等[16]在考慮客戶訂單總延遲最小的情況下,提出了混合遺傳和蟻群優(yōu)化算法,提出的混合算法在求解質(zhì)量上優(yōu)于多遺傳算法和到期日期優(yōu)先算法.此外在上述研究中[6,7,9-14],強調(diào)了對融入啟發(fā)式搜索的混合算法的性能和改進效果;因此本文結(jié)合RMFS系統(tǒng)的特點,提出一種融合大鄰域搜索的改進差分進化算法,引入大鄰域搜索的破壞、修復(fù)思想與一批基于隨機、基于最大代價貢獻和基于集中批次的移除算子以及新的插入算子組件,以最小化訂單總延遲時間為目標對不同規(guī)模的限時客戶訂單分配高質(zhì)量批次,提高揀選效率.

1 RMFS揀選系統(tǒng)

RMFS揀選系統(tǒng)由調(diào)度系統(tǒng)、移動機器人、揀選臺、揀貨員、可移動貨架、巷道和充電站組成,整體布局如圖1所示.RMFS揀選系統(tǒng)訂單揀選作業(yè)流程如下:(1)系統(tǒng)依據(jù)庫存信息以及任務(wù)信息對已接收的訂單分配給目標貨架及揀選臺;(2)系統(tǒng)確定需要執(zhí)行的機器人,并判斷機器人自身電量是否有足夠的時間移動至目標貨架,若有則由該機器人執(zhí)行揀貨任務(wù),若無則需前往充電區(qū)域充電,直至電量達到20%后繼續(xù)完成任務(wù);(3)移動機器人按照規(guī)劃好的最優(yōu)揀選路徑移動至目標貨架;(4)到達目標貨架后,移動機器人頂升、抬起可移動貨架并將其運送至目標揀選臺;(5)到達揀選臺后,按照如圖2所示進行排隊揀選,直至揀貨員開始執(zhí)行該任務(wù);(6)待揀貨員揀貨完成后向系統(tǒng)進行反饋,系統(tǒng)規(guī)劃好移動機器人的路徑,命令其將貨架放回存儲區(qū);(7)移動機器人將貨架放回存儲區(qū),即完成當前任務(wù)的揀選,系統(tǒng)將釋放移動機器人并命令其返回待命位置;(8)若移動機器人任務(wù)密集時,則需就地待命,若否,移動機器人需返回停車區(qū).揀選流程如圖3所示.

圖2 RMFS系統(tǒng)中的揀選臺

圖3 RMFS系統(tǒng)訂單揀選流程

在RMFS揀選系統(tǒng)中,往往同一批次的訂單需要移動機器人多次搬運以及揀貨員在可移動貨架上多次揀選才能完成.而傳統(tǒng)的訂單分批方法比如隨機分批或低質(zhì)量的訂單分配批次會使得移動機器人和揀貨員頻繁操作,從而增加設(shè)備及人力損耗,同時也會使移動機器人進行多次運輸作業(yè)增加訂單揀選時間、降低揀選效率.為解決這一難題,本文首先針對RMFS揀選系統(tǒng),建立以最小化訂單總延遲時間為目標的訂單分批優(yōu)化模型,提出了融合大鄰域搜索的改進差分進化算法,引入移除、插入算子組件,優(yōu)化客戶訂單分配,構(gòu)造高質(zhì)量批次,避免設(shè)備損耗,減少訂單揀選時間及資源閑置,從而提高客戶滿意度及倉庫揀選效率.

2 訂單分批優(yōu)化模型

2.1 條件與假設(shè)

本文所有假設(shè)如下:

(1)同一訂單的SKU不能拆分為不同批次.

(2)任何單個存儲位置都有足夠的SKU用于批量訂單,不會出現(xiàn)缺貨現(xiàn)象.

(3)同一批次中不同訂單的同一SKU是從同一可移動貨架上揀選的.

(4)可移動貨架上的存儲SKU的貨位固定、貨架位置固定.

(5)若兩個訂單中包含同一SKU,將其合并揀選能減少揀貨員揀選操作一次的時間.

(6)若兩個訂單中包含的SKU位于同一貨架,將其合并揀選可以減少一次移動機器人搬運的時間.

(7)已知移動機器人每搬運一次貨架的時間簡化為t1及揀貨員揀選一次SKU的時間為t2.

(8)同一移動機器人,單周期內(nèi)僅需處理某一批次訂單,且必須完成當前周期的當前批次所有揀選任務(wù)后,方可開啟下一周期內(nèi)某一批次的揀選任務(wù).

2.2 模型建立

假設(shè)系統(tǒng)某一時刻的訂單池中,共有N張具有不同截止時間的訂單O1,O2,O3,…,Oi等待處理,每條訂單有M種SKU且貨位信息已知,用aim=1表示訂單i中包含商品m,否則aim=0,此外每個可移動貨架s1,s2,s3,…se上可擺放5種SKU,用bme=1表示商品m在貨架e上,否則bme=0.同時設(shè)置移動機器人搬運一次貨架的時間t1及揀貨員揀選一次SKU的時間t2.其次考慮到電商行業(yè)訂單需要快速響應(yīng),從而保障訂單及時到達客戶這一現(xiàn)狀,本文定義了訂單i的延遲時間為訂單結(jié)束時間與截止時間差,如式(1)所示:

(1)

(2)

(3)

綜合考慮以上的訂單延遲時間、揀選時間和批次容量約束,可建立以最小化訂單總延遲時間為目標的訂單分批優(yōu)化模型.

(4)

s.t.

(5)

(6)

(7)

(8)

(9)

(10)

xij∈{0,1},?i∈I,j∈J

(11)

yje∈{0,1},?j∈J,e∈E

(12)

zjm∈{0,1},?j∈J,m∈M

(13)

目標函數(shù)(4)表示以最小化訂單總延遲時間;式(5)表示每個訂單只能被分到一個批次;式(6)表示批次j中任意訂單i中包含商品m,則批次j包含商品m;式(7)表示如果批次j中包含商品m,則移動機器人需要搬運商品m所在的貨架e,其中yje為0-1變量,若揀選批次j需要搬運貨架e,則yje=1,否則yje=0;式(8)表示批次j的完成揀選的時間,為批次j開始揀選的時間與批次j的服務(wù)時間的和;式(9)表示批次j的開始時間,為該批次內(nèi)訂單i的最早到達時間;式(10)表示批次j的服務(wù)時間,為移動機器人搬運貨架的時間與揀貨員的揀貨時間和;式(11)至式(13)表示決策變量取值約束.

3 一種融合大鄰域搜索的改進差分進化算法設(shè)計

差分進化算法(Differential Evolution,DE)是從仿生智能計算(Bionic Intelligent Computing,BIC)出現(xiàn)以來,優(yōu)化算法結(jié)構(gòu)中的又一大進步,其保留了一對一的競爭策略和基于種群的搜索方式[17].由于該算法具有優(yōu)越的全局收斂能力,求解過程和方法較為簡單等優(yōu)點,因此DE算法更適用于求解較為復(fù)雜的大規(guī)模全局問題.但是傳統(tǒng)DE算法因其單一的變異策略、固定不變的鄰域值和緩慢的靜態(tài)鄰域拓撲交換速率,導(dǎo)致其全局與局部之間的搜索能力無法達到均衡等問題.而大鄰域搜索算法(Large Neighborhood Search,LNS)可通過一組移除和插入算子進行動態(tài)鄰域搜索,使算法具備了良好的適應(yīng)能力[18].同時移除算子和插入算子能夠針對問題特性靈活設(shè)計,可擴展度高.本文在傳統(tǒng)DE算法的基礎(chǔ)上融入大鄰域搜索算法(Large Neighborhood Search,LNS),設(shè)計了3個移除算子和2個插入算子,提出了應(yīng)用于RMFS系統(tǒng)離散型訂單分批問題的融合大鄰域搜索的改進差分進化算法.

3.1 移除算子

(1)基于隨機的移除算子:從當前解中隨機移除批次Bj中的ni筆訂單.

(2)基于最大代價貢獻的移除算子:優(yōu)先移除延遲時間代價貢獻最大的批次Bj中的訂單Oi.某個訂單Oi的代價貢獻由式(2)計算,采用輪盤賭的方式,從當前解中選擇ni筆訂單進行移除操作,定義訂單Oi的權(quán)重Qi=τi.

(3)基于集中批次的移除算子:集中移除一個批次上的訂單.從當前解中找到某個代價最大的批次,隨機移除該批次上的所有訂單.若無符合條件的批次,則退化為隨機移除算子.

隨機移除算子為純隨機算子,具有隨機性強、跳出局部最優(yōu)的能力較強的優(yōu)點,但也容易移除在正確位置上的訂單,從而產(chǎn)生無效操作;最大代價貢獻移除算子會將延遲時間貢獻最大的訂單優(yōu)先考慮,而這些訂單往往正是需要優(yōu)化的訂單,缺點是容易陷入局部最優(yōu);集中批次移除算子會集中移除一個批次上的所有訂單,策略簡單且具有良好的局部收斂能力,這兩種移除算子均需要遍歷一遍當前解中各個訂單的屬性,故以上三種移除算子的時間復(fù)雜度分別為O(1)、O(n)、O(n).

3.2 插入算子

(1)貪婪順序插入算子:每個訂單i由貪婪策略得到插入位置,也就是選擇使本次插入增加的總延遲時間最小的位置插入,將待插入訂單隨機亂序后依次貪婪插入.

(2)遍歷插入算子:隨機選擇兩個移除的訂單,將其它訂單順序打亂后依次以貪婪法插入,然后選擇兩個訂單中的第一個訂單,分別固定到使延遲時間增加最小的前[ky×n]個批次中.對另一訂單遍歷所有批次即位置,以概率p直接選擇其中最優(yōu)的鄰域解,但仍有1-p的概率以賭盤方式選擇一個鄰域解,每個鄰域解的權(quán)重為其適應(yīng)值.其中ky為(0,1)之間的常數(shù).

根據(jù)待插入訂單需要嘗試的批次數(shù)和,貪婪順序插入算子與遍歷插入算子的時間復(fù)雜度均為O(n),是算法的主要耗時部分之一.因移除算子的時間復(fù)雜度均小于O(n2),故每次選擇一個移除算子和一個插入算子執(zhí)行的時間復(fù)雜度仍為O(n2).此外貪婪順序插入算子存在易陷入局部最優(yōu)的缺點,而遍歷插入算子在很大程度上彌補了這種局限.

3.3 LNS_DE算法步驟

本文提出的LNS_DE算法進行優(yōu)化的步驟如下,算法流程圖如圖4所示.

圖4 LNS_DE算法流程圖

(14)

并設(shè)定算法相關(guān)參數(shù),包括種群數(shù)量NP、縮放因子F、交叉概率CR、最大迭代次數(shù)genmax等參數(shù).

(3)記錄當前個體最優(yōu)值以及全局最優(yōu)值.

(4)經(jīng)過步驟(3)后進入迭代循環(huán),當?shù)h(huán)小于次數(shù)genmax,執(zhí)行如下操作:

①變異

針對每個個體向量,執(zhí)行差分變異操作會產(chǎn)生變異向量.在DE中共有常用的5種變異策略產(chǎn)生變異個體Vi,G,以DE/best/1策略進行變異操作,如下所示:

Vi,G=xbest,G+F(xr1,G-xr2,G)

(15)

式(15)中:xrm,G是m=[1,2,3,…,M]中隨機選擇的不同的個體,與目標個體xi,G不相同;xbest,G是種群中適應(yīng)度最好的個體;縮放因子F是[0,2]中的一個實常數(shù)因數(shù),起到對控制偏差變量的放大作用.

②交叉

在變異操作后,需將目標向量xi,G與變異向量Vi,G進行二項式交叉生成最終的試驗向量Ui,G=[Ui1,G,Ui2,G,…,UiM,G],依下式進行交叉操作,以增加干擾參數(shù)向量的多樣性:

(16)

式(16)中:jrand是集合{1,2,…,M}內(nèi)隨機選擇的一個整數(shù),以保證變異向量至少有一維信息被保留下來;交叉概率CR是區(qū)間[0,1]之間的常數(shù).

③判斷當前解是否為較優(yōu)解,若是,則在較優(yōu)解的移除算子集中以輪盤賭的方式選擇一個算子;若不是,則在非較優(yōu)解的移除算子集中以輪盤賭的方式選擇一個算子;

④對當前解應(yīng)用選擇的移除算子,得到移除的訂單集和其待插入的位置,以輪盤賭的方式選擇插入算子,并計算鄰域解;

⑤計算原解與新解的適應(yīng)度;

⑥選擇適應(yīng)度更優(yōu)的個體,轉(zhuǎn)至步驟①進入下一次迭代循環(huán).

(5)當?shù)螖?shù)等于genmax時,迭代停止,并輸出最終的全局最優(yōu)值.

4 數(shù)值算例

4.1 參數(shù)校準

該算法框架主要有3個參數(shù),為每種算例類型尋找最佳參數(shù)設(shè)置非常耗時.相反,更希望在廣泛的算例類型上提供良好結(jié)果的參數(shù)設(shè)置.因此,必須校準所涉及的3個參數(shù).本研究基于Coy等[19]中提出的系統(tǒng)參數(shù)校準過程,為這些問題算例查找高質(zhì)量的參數(shù)設(shè)置.因此整個參數(shù)設(shè)計實驗包括四個步驟:選擇問題子集,確定每個參數(shù)變化的設(shè)計中心和范圍,組合參數(shù)設(shè)置并進行算例驗證,最后確定每個問題集良好的參數(shù)設(shè)置.

在參數(shù)校準中,選擇代表整個問題集特征的3個不同算例作為實驗子集.確定實驗子集后,依據(jù)各參數(shù)本身的性質(zhì)設(shè)置設(shè)計中心和變化區(qū)域,如表1所示.最小值和最大值代表實驗區(qū)域的外邊緣,根據(jù)步長可計算參數(shù)的不同水平值.

表1 參數(shù)校準初始實驗區(qū)域

由于必須校準3個參數(shù),利用田口方法論為3個因子和4個水平進行析因設(shè)計,以確定實驗結(jié)果穩(wěn)定、波動性小的參數(shù)組合[20,21].如表2所示,從正交表中選擇L16正交陣列,對于16種配置中的每種配置,在算例類型為50個訂單、10個貨架上執(zhí)行5次運行以獲得算法最優(yōu)解平均值A(chǔ)bs_Obj.并通過方差分析法可以找到重要參數(shù),從表2可以看出,對于算例1來說因子F(縮放因子)對算法的影響最大,其次是因子NP(種群規(guī)模),因子CR(交叉概率)對算法的影響最小.算例1中每個因子的最佳水平為NP3、F4和CR4.

表2 正交表及方差分析

接下來,為每個算例選擇最優(yōu)解平均值最低的參數(shù)設(shè)置.結(jié)果設(shè)置如表3所示,通過取實驗子集的參數(shù)設(shè)置的平均值,可以獲得最終參數(shù)設(shè)置,該參數(shù)設(shè)置將用于進一步的實驗,并在廣泛的問題類型上可提供高質(zhì)量的解決方案,以顯示所提出的算法框架的計算性能.

表3 參數(shù)校準結(jié)果

4.2 實驗結(jié)果

上述研究的參數(shù)設(shè)置用于下面討論的所有實驗.第一部分實驗在基于每個算例類型上比較使用DE算法、LNS_DE算法,每組實驗分別重復(fù)10次,累計2x6x10=120組試驗.并統(tǒng)計了兩種訂單分批算法的最優(yōu)解平均值A(chǔ)bs_Obj、平均偏差值Dev、平均目標值優(yōu)化比例MPI及平均運行時間T.其中Dev表示在一類算例中,當前算法最優(yōu)解平均值A(chǔ)bs_Obj與已知最優(yōu)解之間的平均百分比偏差值,已知最優(yōu)解是DE、LNS_DE中發(fā)現(xiàn)的最優(yōu)解的平均值;MPI表示LNS_DE求解結(jié)果對比DE的改進程度.

表4比較了在6個算例類型中,DE算法、LNS_DE算法的性能.在求解質(zhì)量上,LNS_DE算法在所有算例類型上均優(yōu)于DE算法.具體表現(xiàn)為,所有算例上,LNS_DE算法解的平均值優(yōu)化比例隨著訂單數(shù)量的增大而增大,優(yōu)勢在不斷擴大,平均縮短了22.05%的延遲時間,在N/E/M=300/50/250時最大可減少71.6%的延遲時間.此外LNS_DE算法平均偏差值Dev小于DE算法,這表示在每個算例類型中,LNS_DE算法都發(fā)現(xiàn)了最多的已知最優(yōu)解,尤其在N=75后平均偏差值Dev均為0,說明每次實驗已知最優(yōu)解全部來源于LNS_DE算法;在求解時間上,LNS_DE算法并未優(yōu)于DE算法,但計算時間差率大小控制在合理范圍內(nèi):2%～7%,這是由于任何混合算法性能的提高都是以犧牲算法搜索時間為代價;且隨著客戶訂單數(shù)量增大時,兩種算法執(zhí)行時間均呈一定幅度下降.

表4 兩種分批算法在不同算例中的計算結(jié)果

企業(yè)促銷活動時,客戶反映表現(xiàn)為兩方面,一方面是購買訂單增加帶來的訂單行增加,另一方面是客戶一起購買的商品增加,即訂單長度增加.因此第二部分實驗探究訂單長度對分批效果的影響.基于算例類型N/E/M=100/20/100,在不同的訂單長度({1,4}、{1,6}、{1,8})上統(tǒng)計了LNS_DE算法和DE算法的訂單總延遲時間,累計2×3×10=60組試驗.

圖5呈現(xiàn)了DE算法、LNS_DE算法在3種訂單長度下的訂單總延遲時間數(shù)值.雖然隨著單個訂單所包含的的商品種類擴增時,兩種算法所求解的訂單延遲時間均進一步延長,但延遲時間也在合理范圍之內(nèi).另外LNS_DE算法分批效果明顯優(yōu)于DE,且在訂單行長度為{1,8}時,優(yōu)化效果達到最大,說明在訂單分批流程時,管理者可選擇LNS_DE算法緩解延遲時間所帶來的經(jīng)濟損失,得出的方案對企業(yè)面臨大型促銷活動時,可實現(xiàn)快速響應(yīng)客戶這一點.

圖5 兩種算法在不同訂單長度下的總延遲時間

圖6記錄了DE算法、LNS_DE算法在不同規(guī)模算例下的計算迭代過程.可以發(fā)現(xiàn)DE算法的收斂速度較快,但易陷入局部最優(yōu),而本文所提出的LNS_DE算法通過擴大鄰域搜索范圍,能夠有效提高算法精度;同樣LNS_DE算法得到的最優(yōu)解適應(yīng)度值均優(yōu)于DE算法,且隨著訂單規(guī)模的增大,適應(yīng)度值的優(yōu)化效果愈加明顯.

5 結(jié)論

(1)以最小化訂單總延遲時間為目標,建立基于“RMFS”揀選系統(tǒng)的訂單分批優(yōu)化模型.

(2)引入大鄰域搜索的破壞與修復(fù)思想及一批基于隨機、基于最大代價貢獻和基于集中批次的移除算子以及新的插入算子組件,設(shè)計出融合大鄰域搜索的改進差分進化算法對模型進行求解.

(3)對于不同規(guī)模的限時客戶訂單結(jié)構(gòu),LNS_DE算法通過擴大鄰域搜索范圍,能夠有效提高算法精度,平均縮短22.05%的延遲時間,與差分進化算法(DE)相比,求解質(zhì)量更優(yōu)、性能更穩(wěn)定、收斂速度更快.

(4)面對大型促銷活動所帶來的訂單長度增加、高訂單數(shù)量時,本文算法解的優(yōu)化比例不斷擴大,主要體現(xiàn)在LNS_DE算法平均偏差值Dev均小于DE算法,且在N=75后均為0,說明每次實驗已知最優(yōu)解全部來源于LNS_DE算法,故該方法所求解高質(zhì)量的訂單批次可有效縮短揀選時間,提高揀選效率.

(5)此外,LNS_DE算法與DE算法計算時間差率大小始終保持在合理范圍內(nèi):2%～7%.