“RMFS”揀選系統的訂單分批優化

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

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

0 引言

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

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

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

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

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

1 RMFS揀選系統

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

圖2 RMFS系統中的揀選臺

圖3 RMFS系統訂單揀選流程

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

2 訂單分批優化模型

2.1 條件與假設

本文所有假設如下:

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

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

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

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

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

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

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

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

2.2 模型建立

假設系統某一時刻的訂單池中,共有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.同時設置移動機器人搬運一次貨架的時間t1及揀貨員揀選一次SKU的時間t2.其次考慮到電商行業訂單需要快速響應,從而保障訂單及時到達客戶這一現狀,本文定義了訂單i的延遲時間為訂單結束時間與截止時間差,如式(1)所示:

(1)

(2)

(3)

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

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

目標函數(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的服務時間的和;式(9)表示批次j的開始時間,為該批次內訂單i的最早到達時間;式(10)表示批次j的服務時間,為移動機器人搬運貨架的時間與揀貨員的揀貨時間和;式(11)至式(13)表示決策變量取值約束.

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

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

3.1 移除算子

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

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

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

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

3.2 插入算子

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

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

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

3.3 LNS_DE算法步驟

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

圖4 LNS_DE算法流程圖

(14)

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

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

(4)經過步驟(3)后進入迭代循環,當迭代循環小于次數genmax,執行如下操作:

①變異

針對每個個體向量,執行差分變異操作會產生變異向量.在DE中共有常用的5種變異策略產生變異個體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是種群中適應度最好的個體;縮放因子F是[0,2]中的一個實常數因數,起到對控制偏差變量的放大作用.

②交叉

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

(16)

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

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

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

⑤計算原解與新解的適應度;

⑥選擇適應度更優的個體,轉至步驟①進入下一次迭代循環.

(5)當迭代次數等于genmax時,迭代停止,并輸出最終的全局最優值.

4 數值算例

4.1 參數校準

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

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

表1 參數校準初始實驗區域

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

表2 正交表及方差分析

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

表3 參數校準結果

4.2 實驗結果

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

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

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

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

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

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

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

5 結論

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

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

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

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

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