張艷菊 李群 張彭涵 李蕊

摘 要：針對訂單分揀效率低下導致商品出庫緩慢的問題，提出一種基于雙區(qū)型倉庫訂單分批與揀選的協(xié)同優(yōu)化模型，設計求解模型的CWDP-BSA（clarke-wright and dynamic programming & backtracking search algorithm）協(xié)同優(yōu)化算法。在節(jié)約算法中引入快速排序法對訂單組合的距離節(jié)約值排序，考慮AGV承載量，運用多階段決策過程最優(yōu)策略得出狀態(tài)轉移方程求解訂單分批模型，確定初始分批方案；并采取多因子選擇的回溯搜索算法求解揀選路徑模型，以此確定初始揀選方案。再以以上兩方案為基礎，建立新的基于訂單時間窗的訂單分批和揀選協(xié)同優(yōu)化模型并求解，進一步優(yōu)化訂單分批和揀選方案。最后通過對比實驗得出，平均每批次訂單的揀選距離減少了約24.56%，優(yōu)化后的揀選時間比優(yōu)化前縮短了約11.4%，在求解不同規(guī)模算例時，CWDP-BSA算法的求解結果優(yōu)于CPLEX軟件和其他算法，驗證了模型與算法的穩(wěn)定性和有效性。實驗表明，協(xié)同優(yōu)化后的訂單分批與物品揀選策略能夠有效提升訂單出庫效率。

關鍵詞：雙區(qū)型倉庫； 訂單分批揀選； 協(xié)同優(yōu)化； 節(jié)約算法； 回溯搜索優(yōu)化算法； CWDP-BSA算法

中圖分類號：F252;TP18?? 文獻標志碼：A

文章編號：1001-3695（2024）03-015-0746-10

doi：10.19734/j.issn.1001-3695.2023.07.0326

Research on collaborative optimization of order batching andpicking in two-block warehouse

Zhang Yanjua，b，c， Li Quna， Zhang Penghana， Li Ruia

（a.School of Business Administration， b.Management Science & Engineering Research Institute， c.Modern Enterprise System Innovation Research Center， Liaoning Technical University， Huludao Liaoning 125105， China）

Abstract：In response to the problem of slow delivery of goods due to low order sorting efficiency， this paper proposed a collaborative optimization model based on two-block warehouse order batching and picking，and designed a multi-stage CWDP-BSA algorithm to solve the model. In the saving algorithm， it introduced quick sorting method to sort the distance savings of order combinations. Considering the carrying capacity of AGV， under the guidance of the optimal strategy in the multi-stage decision-making process，it obtained the state transition equation to solve the order batch model and determine the initial batch plan. And it adopted a multi factor selection backtracking search algorithm to solve the picking path model， in order to determine the initial picking plan. Based on the two schemes， establishing and solving a collaborative optimization model for order batching and picking based on order time windows were to further optimize order batching and picking schemes. Finally， through comparative experiments， it can reduce the average picking distance of each batch of orders by about 24.56%， and shorten the optimized picking time by about 11.4% compared to before. When solving examples of different scales， the CWDP-BSA algorithm performs better than CPLEX software and other algorithms， which verifies the stability and effectiveness of the model and algorithm. Experiments show that the collaborative optimization of order batching and item picking strategies can effectively improve the efficiency of order delivery.

Key words：two-block warehouse; order batch picking; collaborative optimization; Clarke-Wright algorithm; backtracking search algorithm; CWDP-BSA algorithm

0 引言

近年來，在線銷售增長顯著，訂單向多品種、高頻次、多樣化的模式轉變，涌現(xiàn)出了單筆訂單規(guī)模小、訂單總體數(shù)量大、品種數(shù)目多且響應時間嚴格等特點。同時，消費者對及時配送的要求也不斷提高，加大了各電商企業(yè)的物流服務壓力。相關研究發(fā)現(xiàn)，在整體的物流倉儲系統(tǒng)中，揀選作業(yè)的勞動量占總作業(yè)量的60%［1］，而且傳統(tǒng)的揀選方式效率低、錯誤率高［2］?？梢姡枰痈咝У膾x作業(yè)方法以提升物流倉儲中心的運作效率，而分批和揀選環(huán)節(jié)所需時間占揀選作業(yè)總時間的比重最高，因此對訂單分批和揀選效率提升的研究有著重要的實踐意義。

國內外學者一般將訂單分批策略和揀選路徑規(guī)劃作為獨立的問題分別研究，均取得了較豐富的研究成果。有關訂單分批策略的研究，訂單批處理問題（OBP）的目標是將客戶訂單分組到相應批次中去，從而使通過矩形倉所有路程的總長度最小化［3］，對批次的合理排序可以最大程度地減少總作業(yè)時間。針對在線情景下的訂單批處理問題，Cristiano等人［4］提出了適用于平行及兩個或兩個以上過道的矩形網(wǎng)格存儲區(qū)的方法。Mehrdad等人［5］考慮了具有多個揀貨員的在線訂單批處理問題（OOBP），其中所有批次的最大完成時間須達到最小化。關于訂單分批的方法，Cals等人［6］提出了一種深度強化學習（DRL）方法和啟發(fā)式方法，通過分析怎樣以及何時對客戶的訂單進行分批，從而提高作業(yè)效率，使訂單準時到達。公斌［7］采用節(jié)約算法來解決城市物流配送路徑優(yōu)化問題。

有關揀選路徑的研究，Namrata等人［8］解決了倉庫中的揀選路徑優(yōu)化問題，最大限度地減少了旅行時間和距離。由于倉儲位置和揀選路徑問題是兩個相互依賴的問題，Silva等人［9］建立了集成倉儲位置與訂單揀選問題的模型，并考慮了返回、S形、中點和最大間隙四種路由策略。針對多區(qū)型倉庫的揀貨路線優(yōu)化問題，張水旺等人［10］對多區(qū)型倉庫布局結構、揀選路徑等問題進行了明確的定義，建立了多區(qū)型倉庫下的揀貨路線優(yōu)化模型。關于路徑規(guī)劃的方法，Sebo等人［11］針對最小化揀貨距離的問題，介紹了遺傳算法的性能及其與其他路由策略（如啟發(fā)式算法和給定假設下的算法等）的比較。翟夢月等人［12］提出了一種變鄰域-禁忌搜索算法，分別通過改變商品種類的分散程度和商品種類-數(shù)量配比來規(guī)劃訂單揀選路徑。

盡管訂單分批和揀選路徑的優(yōu)化問題在學術界已有較為深刻的研究，但是考慮兩者協(xié)同優(yōu)化的研究相對較少?，F(xiàn)有研究主要從其他作業(yè)環(huán)節(jié)的協(xié)同合作出發(fā)，唐堅強等人［13］針對訂單拆分和限時配送問題進行研究，分析出了考慮多倉庫訂單拆分與異構車輛路徑的聯(lián)合優(yōu)化方法。李彤等人［14］針對不確定需求下的循環(huán)取貨問題，提出了多車型最優(yōu)路徑-裝載協(xié)同優(yōu)化的復合解決方案。通過上述研究可以發(fā)現(xiàn)，訂單分批和揀選的現(xiàn)有研究成果對本文具有重要的指導意義，但仍存在一些不足：a）對于分批策略來說，從“貨到人”和“人到貨”兩個角度出發(fā)，有學者考慮到采用節(jié)約里程法求解訂單分批策略，但節(jié)約法更加強調路程的節(jié)約，忽視了行程中的時間因素，導致分批結果效率不高；b）對于揀選路徑來說，優(yōu)化路徑的方法大多采用遺傳算法、禁忌搜索算法等，實際上這類優(yōu)化方法效率并不高且容易陷入局部最優(yōu)，需要尋找搜索能力更強的方法進行優(yōu)化；c）對于協(xié)同研究來說，現(xiàn)有研究成果主要考慮了訂單拆分和配送路徑的協(xié)同，以及貨物裝載和配送路徑的協(xié)同，關于訂單分批與揀選路徑的協(xié)同研究較少。

綜上所述，針對雙區(qū)型倉庫背景下的訂單分批與揀選路徑問題，建立訂單分批與揀選的協(xié)同優(yōu)化模型，設計CWDP-BSA多階段算法對模型進行求解。在實驗分析部分驗證了模型和算法的有效性與實用性。本文的主要創(chuàng)新點在于：a）為提升揀選作業(yè)效率，考慮訂單分批和物品揀選是連續(xù)的整體過程，提出訂單分批與物品揀選協(xié)同優(yōu)化的解決思想；b）在模型構建方面，通過對揀選作業(yè)環(huán)節(jié)中各部分的關系進行耦合分析，進而提出訂單分批和揀選路徑協(xié)同優(yōu)化的數(shù)學模型，該模型與傳統(tǒng)揀選模型的區(qū)別在于，將訂單分批和路徑規(guī)劃歸為一個整體，并構建了兩者間聯(lián)系實現(xiàn)協(xié)同優(yōu)化的思想；c）在算法求解方面，首先針對求解訂單分批和揀選路徑的優(yōu)化方案集，設計了節(jié)約動態(tài)規(guī)劃算法和回溯搜索優(yōu)化算法，其次針對求解協(xié)同優(yōu)化模型設計了多階段算法CWDP-BSA。通過實驗得出，目標值的波動處于±5%，驗證了該協(xié)同優(yōu)化算法的穩(wěn)定性。同時，在真實數(shù)據(jù)集上進行實驗分析，得出總揀選時間和揀選距離分別減少約11.4%和24.56%；利用合成數(shù)據(jù)集對分批次揀選時間和總揀選時間進行對比實驗得出，CWDP-BSA算法的性能優(yōu)于其他三種算法，驗證了該協(xié)同優(yōu)化算法的有效性。

1 問題描述及建模

1.1 問題描述

本文所研究的協(xié)同優(yōu)化問題可以描述為：以雙區(qū)型倉庫為場景，在出庫的所有流程中，對訂單分批和揀選兩個連續(xù)的工作環(huán)節(jié)進行協(xié)同優(yōu)化，給出合理的分批方案和揀選路徑方案，使某一規(guī)定時間段內n個訂單能夠完成揀選且揀選總時間最短。具體思路為：在訂單分批時重點考慮AGV載重量，并規(guī)劃距離較短的路徑為初始分批和揀選方案；根據(jù)協(xié)同優(yōu)化思想，由實際的訂單時間窗劃分最優(yōu)分批和揀選方案，再依據(jù)方案進行揀選作業(yè)。一般流程為：AGV從倉庫入口處出發(fā)，根據(jù)出庫請求與優(yōu)化后的揀選批次和揀選路線，分批次有序地進行揀選作業(yè)。具體訂單分批和揀選處理流程如圖1所示。

本文以雙區(qū)型倉庫為例，該倉庫由兩個布局相同的揀選區(qū)域和一定數(shù)量的等長巷道及貨架組成，中間的主通道（過道）把倉庫平均分為兩個區(qū)，兩邊各有一條平行于主通道的邊通道（過道和過道），相應的雙區(qū)型倉庫平面圖如圖2所示。設雙區(qū)型倉庫過道寬a=2 m，存儲貨位的長和寬分別為b=c=1 m，巷道之間的寬d=1.5 m，每一區(qū)域的巷道總數(shù)都是10條且每條巷道長度為10 m。每條巷道的兩側貨位都可以進行揀選作業(yè)，每列又都包含3個垂直貨位，即每排貨架有60個貨位，每條巷道左右兩邊的貨位數(shù)為120個。給定每一個貨物的儲位編碼方式為［區(qū)號，巷道，左右號，行號，貨位號，體積］，巷道按照從左到右的順序依次進行編碼，每條巷道兩側的貨位從前往后依次編碼，分別表示為1，2，3，…，10，得到儲位編碼［x1，x2，x3，x4，x5，x6］。例如［1，3，1，2，10，1］表示1區(qū)第三條巷道的左側第二行10貨位，該待揀選點上的貨物體積為1單位，出入口的編號是［0，0，0，0，0，0］。忽略揀選時的貨位揀選垂直移動，揀選一個品項所需的時間為3 s，自動導引車的行走速度為1 m/s?？紤]對雙區(qū)型倉庫訂單分批與揀選協(xié)同優(yōu)化問題的分析，給出相關定義如下：

定義1 揀選距離。揀選距離D為揀選所有批次商品經(jīng)過的總距離，包括行走過道的距離d1、行走巷道的距離d2以及穿越貨位的距離d3，即D=d1+d2+d3。給定［x1，x2，x3，x4，x5］和［x′1，x′2，x′3，x′4，x′5］為兩個待揀選訂單編號，則行走過道的距離d1=|x′1-x1|×a；將穿越巷道時兩排貨架的距離加入到計算中，那么行走巷道的距離d2=|x′2-x2|×（d+2b）；不考慮垂直方向的移動距離，穿越貨位的距離d3分三種情況進行如下討論：

a）當兩個需要被揀選的貨位是同一區(qū)域且同一巷道時，所要行走的距離為兩個貨位之間的距離，則d3=|x′3-x3-1|×c。

b）當兩個待揀商品的貨位在相同的區(qū)域而在不同的巷道時，行走距離的計算方法是取S形策略與混合型策略中的較小值，此時，給定d3=min{20-x′3-x3，x′3+x3-2}。

c）當兩個待揀選商品的貨位不在同一區(qū)域時，按照上述混合型策略進行求值，取值為兩者之間的最小值，此時d3=min{|x′3-x3|，40-x′3-x3}。

定義2 揀選時間。揀選時間t是完成訂單揀選動作的時間，包括尋找貨品的時間ttravel和揀取貨品的時間tpick，t=ttravel+tpick。通過降低尋找和揀取貨品的時間可以減少總揀選時間t。

定義3 倉庫網(wǎng)絡。倉庫網(wǎng)絡由一個坐標圖A（X，Y）表示，其中X為倉庫過道長度，Y為兩區(qū)域寬度。揀選過程的行走路徑，即每條長與寬的邊xr、yr都與揀選時間ttravel和tpick相關聯(lián)。

定義4 自動導引車AGV。一輛自動導引車w=〈Cn，C〉有一個揀選訂單的容量Cn和一個最大容量C（一輛AGV一次可以裝載的最大貨物體積）。W={w1，…，w|w|}代表所有的AGV。

定義5 請求。請求由r=〈sr，fr，or，pr，dr，tr，cr〉表示，其起點和終點分別為sr與fr，訂單信息為or，最優(yōu)排列批次為pr，AGV每次裝載體積為cr，根據(jù)分批結果進行揀選得到的最小揀選距離為dr，最優(yōu)揀選時間為tr。

定義6 路線。自動導引車的路線由Rw=〈l0，…，ln〉表示，l0，…，ln是Rw的起點和終點的有序序列，即li∈{sr|r∈Rw}∪{fr|r∈Rw}。如果一條路線是可行的，需滿足：a）r∈Rw，sr在路線Sw中的fr之前；b）r∈Rw，w到達fr的時間較S形揀選策略更小，揀選時間達到最優(yōu)；c）任何時候，已揀取并裝載的貨物體積（即請求的每批次大小）不超過自動導引車w的最大容量C。

示例1 為了更好地說明所研究問題，設置七個等待揀選的訂單Or進行說明。

表1為訂單信息，表2為根據(jù)揀選請求r得到的訂單優(yōu)化前后的分批結果、揀貨路徑。揀選請求r為：自動導引車w從Sr出發(fā)，根據(jù)訂單信息O1～O7，在滿足w=〈Cr，C〉的條件下求解最優(yōu)排列批次pr，同時求出每批次最小揀選距離dr所在的揀選路線Rw，履行每批次揀選路線Rw，最終得出最優(yōu)揀選時間tr，在完成訂單分批與揀選后回到fr。

假設將訂單以常用的順序分批方法進行分批，在滿足體積約束的條件下得到批次劃分后，以S形行走策略為例對物品揀選的路徑進行計算。圖2的黑色部分為第一批次的商品儲位，圖中路線為第一批次的行走路線Rw1，灰色部分和陰影部分分別為第二、三批次的商品儲位，那么，優(yōu)化前分批次揀選路線如圖3（a）～（c）所示，計算出優(yōu)化前第一批次的總時間t1，即ttravel+tpick=139 s，第二、三批次的行走方式與第一批次相同，計算得出第二、三批次的總時間t2、t3分別為245 s、210? s。

而這種訂單分批和揀選策略的效率并不高，依據(jù)揀選請求r，考慮將訂單進行連接，把經(jīng)過但沒有出現(xiàn)在路線Rw上的訂單按照次序插入到揀選路線中，直到全部的訂單都被安排完揀選路線時結束。例如，將批次2中訂單4編碼［1，2，1，2，7，10］的貨物插入至批次1中訂單2編碼［1，2，1，1，6，9］的貨物后，不斷插入直至每一批次揀選貨物飽和，形成優(yōu)化后的訂單分批方案，如表2所示。根據(jù)新的分批方案，協(xié)同優(yōu)化待揀選商品間的總距離，根據(jù)最短距離劃定揀選路線，形成訂單分批和揀選協(xié)同優(yōu)化后的解決方案，如圖3（d）～（f）所示。計算出優(yōu)化后第一批次耗費的總時間t1=ttravel+tpick=149 s，第二、三批次的總時間t2、t3分別為146 s、95 s。可以看出，協(xié)同優(yōu)化后的分揀總時間明顯少于優(yōu)化前所需要的總時間。由上述訂單分批與揀選路徑協(xié)同優(yōu)化后所求得的結果可知，優(yōu)化策略明顯提高了作業(yè)效率。可以想象，隨著訂單規(guī)模的擴大，優(yōu)化分批和揀選策略將會節(jié)省更多時間，說明傳統(tǒng)分批方式與物品揀選策略存在弊端，本文提出的協(xié)同優(yōu)化策略具有一定的可行性。

1.2 問題假設

為了減少非必要因素對分批和揀選問題的影響，使模型更具有針對性與實用性，同時起到簡化模型構建與降低問題計算復雜程度的作用，對模型進行如下假設：a）每種商品僅有一個存儲的位置；b）每個訂單中的商品僅屬于一個批次，不被分割到兩個批次中；c）不將貨物在貨架上的垂直移動納入揀選距離的計算中，垂直移動距離不會對揀選人員的揀選距離產生影響；d）所有的AGV從入口統(tǒng)一出發(fā)，揀選完成后返回入口，整個過程形成一個閉合回路；e）不考慮緊急插單的情況；f）訂單中揀選的商品不會出現(xiàn)缺貨的情況。

1.3 模型的參數(shù)與變量

本文模型使用到的集合含義、參數(shù)說明分別如表3、4所示，決策變量如下：

3 實驗結果與分析

3.1 實驗介紹

本文CWDP-BSA協(xié)同優(yōu)化算法使用MATLAB R2022b編程，采用CPLEX作為模型求解器，所有實驗環(huán)境均在Intel CoreTM i7-6 500U CPU 64位計算機上運行。為了更好地對比較結果進行分析，本文基于某電商企業(yè)訂單高峰期內記錄的訂單數(shù)據(jù)的實際情況，生成100個訂單作為測試算例，商品數(shù)量總計576件，參數(shù)設置已在1.1節(jié)中詳細闡述，提取部分訂單數(shù)據(jù)如表5所示。

3.2 訂單分批和揀選協(xié)同優(yōu)化結果對比分析

根據(jù)本文的模型和算法，分別對雙區(qū)型倉庫中的原始分揀策略和協(xié)同優(yōu)化策略進行比較分析：按照順序分批的方式將100個訂單進行分批，共分成37個批次，由于受AGV容量限制，每批次包含1～5個訂單不等；按訂單順序進行劃分，得到優(yōu)化前的訂單分批結果；在相同的情景與訂單數(shù)量中，用本文算法再進行求解。優(yōu)化前后的部分訂單分批結果與優(yōu)化后每批次訂單的揀選路徑如表6所示。

可以發(fā)現(xiàn)，采用CWDP-BSA協(xié)同優(yōu)化算法得出的結果與采用順序分揀策略所得結果有顯著不同。在CWDP-BSA協(xié)同優(yōu)化算法中，將一個時間段看作時間窗，在該時間窗內到達的訂單不是按照訂單到達的時間順序進行批次劃分，而是綜合考慮這一段時間內的所有訂單，把訂單中所包含商品的體積作為考慮因素，并將同一訂單中的商品作為一個整體來進行相應的批次劃分，得出優(yōu)化后的訂單分批結果，再根據(jù)協(xié)同優(yōu)化思想使每一批次訂單在一條最優(yōu)最短的路徑上完成揀選工作，從而使所有批次訂單揀選總距離最小，同時花費更低的揀選時間。本節(jié)針對揀選距離和揀選時間，將100個訂單的算例分別采用CWDP-BSA協(xié)同優(yōu)化方法和不涉及協(xié)同優(yōu)化的順序揀選策略進行對比實驗。選取前10個批次的訂單進行揀選距離對比分析，如表7所示。以批次5為例，優(yōu)化前批次內訂單包含18件商品，以S形揀選策略揀選商品的順序分別為［1，6，2，2，1，4］→［2，5，1，3，4，6］→［2，6，2，1，8，4］→［1，7，2，1，1，4］→［2，7，1，2，3，3］→［2，7，2，3，2，7］→［2，2，1，3，1，6］→［1，4，2，2，1，10］→［2，4，2，1，6，7］→［2，3，2，1，1，10］→［2，7，1，2，2，7］→［2，4，1，3，2，6］→［1，5，1，3，6，10］→［2，3，1，2，6，7］→［2，4，2，1，4，7］→［2，7，1，1，5，6］→［2，3，1，2，9，4］→［2，1，1，1，6，1］，根據(jù)定義1中對揀選距離計算方程式的定義d=|x′1-x1|×a+|x′2-x2|×（d+2b）+|x′3-x3-1|×c，得出優(yōu)化前批次5的揀選距離為248 m；使用CWDP-BSA算法優(yōu)化后批次內所含訂單的揀選順序為［1，1，1，3，2，6］→［2，1，1，1，6，1］→［2，1，2，2，2，9］→［2，2，2，3，5，4］→［2，3，1，2，6，7］→［2，3，1，2，9，4］→［2，3，1，3，5，8］→［2，4，2，1，4，7］→［2，4，2，1，4，8］→［2，4，1，3，9，5］→［2，4，1，3，8，1］→［2，5，2，1，5，7］→［2，5，2，1，6，9］→［2，7，2，3，4，6］→［2，7，2，1，3，3］→［2，7，1，1，5，6］→［1，5，2，1，3，7］→［1，7，2，2，1，1］→［1，7，2，2，5，8］→［1，6，1，1，6，5］→［1，5，1，3，7，7］→［1，5，2，2，4，6］→［1，5，2，2，5，8］，經(jīng)協(xié)同優(yōu)化后，批次5中23件商品的揀選距離為191 m。與優(yōu)化前的結果相比，雖然優(yōu)化后批次內增加了5件商品，但商品的揀選距離卻縮短了約22.98%，且10個批次訂單揀選距離的平均優(yōu)化百分比為24.56%，說明協(xié)同優(yōu)化算法能夠很好地縮短揀選距離，對降低揀選時間有較大的幫助。

為了清晰地看出揀選作業(yè)縮短的時間，先求出初始未經(jīng)過改進的分批與揀選路徑所需時間，再求協(xié)同優(yōu)化后每批次所需要的最短揀選時間，最后將每批次的最短揀選時間相加得到目標函數(shù)值，即揀選的最小總時間，對比結果如圖7所示。

根據(jù)對比結果可以發(fā)現(xiàn)，在分批揀選時間上，協(xié)同優(yōu)化后的每一個批次揀選時間都小于優(yōu)化前，除了個別批次的時間優(yōu)化百分比較低以外，剩余批次時間優(yōu)化百分比均在10%～20%，具有明顯的優(yōu)化效果。在總揀選時間上，協(xié)同優(yōu)化也呈現(xiàn)出了較好的優(yōu)化效果，如表8所示的計算結果，在使用順序分批和S形揀選策略的情況下，所計算的揀選總時間為6 267 s；經(jīng)過訂單分批和揀選路徑協(xié)同優(yōu)化后，所求得的最小揀選時間為5 551 s。由此可以計算出優(yōu)化后的揀選時間比優(yōu)化前縮短了716 s，也就是說，協(xié)同優(yōu)化方法較初始分揀策略縮短了約11.4%的揀選作業(yè)時間，說明所提出的協(xié)同優(yōu)化思路行之有效，能夠得到合理的分批和揀選結果。

3.3 算法有效性分析

為驗證不確定環(huán)境下的協(xié)同優(yōu)化模型和CWDP-BSA算法的有效性，通過調整訂單規(guī)模（Q）、訂單商品種類（K）、AGV數(shù)量（W）三個參數(shù)，分別進行小規(guī)模仿真實驗和大規(guī)模仿真實驗。相關參數(shù)設置如表9所示。

3.3.1 小規(guī)模仿真實驗

本節(jié)考慮訂單商品種類多樣化、AGV自動導引車數(shù)量不定的特點生成隨機數(shù)據(jù)，對10組訂單規(guī)模為10的小算例進行測試。其中，Q為訂單規(guī)模，K為商品種類，W為AGV數(shù)量，PT表示揀選總時間，RT表示運行時間，GAP表示CWDP-BSA算法求解結果與CPLEX求解結果的偏差，求解方法為（PT（CWDP-BSA）-PT（CPLEX））/PT（CPLEX）×100%。由于模型的約束條件和參數(shù)過多，在有限時間內，CPLEX求解器不能全部精確求解，部分算例也無法得到最優(yōu)解，所以，本文設置CPLEX的最大運行時間限制為3 600 s，CPLEX和CWDP-BSA的小規(guī)模算例求解結果如表10所示。

以PT和RT為衡量指標，“*”表示兩求解方法對比下更優(yōu)的運行結果，GAP值表示CWDP-BSA算法的求解效果優(yōu)于CPLEX。從結果來看，有6個算例的CWDP-BSA結果比CPLEX結果更優(yōu)，揀選時間結果相差最大達7.08%；有4個算例的CWDP-BSA結果與CPLEX結果相同。從求解時間來看，CWDP-BSA的運行時間均小于或等于CPLEX。而CPLEX對于6個請求在

3 600 s內已經(jīng)很難得到最優(yōu)解，CWDP-BSA卻可以在5 s內得到可接受的有效解，說明本文協(xié)同優(yōu)化模型及CWDP-BSA算法行之有效。

為了驗證算法的穩(wěn)定性，使用CWDP-BSA協(xié)同優(yōu)化算法和CPLEX求解器進行了10次運算。目標函數(shù)值波動情況如圖8所示。該結果表明，在多次運算中兩求解方法的目標值波動都處于±5%，但CWDP-BSA相較于CPLEX，求解波動更小，由此可以看出，本文方法的穩(wěn)定性更好。

3.3.2 大規(guī)模仿真實驗

在10次獨立運算程序后，本節(jié)將實驗求解所用的最大訂單規(guī)模擴大到100個。為進一步驗證算法的有效性，共進行兩項實驗，一是對CWDP-BSA和不同算法之間的效果進行比較，二是將本文協(xié)同優(yōu)化算法和單獨優(yōu)化方法進行比較研究。

假設訂單規(guī)模分別為10、30、50、70、100，其他參數(shù)相同的情況下，將CWDP-BSA算法與遺傳算法（GA）、嵌套遺傳算法（FNGA）進行對比實驗。遺傳算法是解決訂單分批和揀選問題中最常用的方法，嵌套遺傳算法在遺傳算法的基礎上進行改進，其收斂速度更快，文獻［27］運用嵌套遺傳算法進行運算，驗證了其良好的收斂性和穩(wěn)定性。在此基礎上，本文將以上算法進行對比分析，如圖9所示，結果發(fā)現(xiàn)CWDP-BSA算法和嵌套遺傳算法比普通遺傳算法效果更優(yōu)，盡管嵌套遺傳算法也能大大降低分批和揀選作業(yè)的時間，但所求得的揀選時間仍在任意訂單規(guī)模中高于CWDP-BSA算法，該實驗證明了CWDP-BSA算法的有效性。

為了驗證協(xié)同優(yōu)化研究的優(yōu)越性，本文將CWDP-BSA算法與以下三種單獨求解算法進行比較。所有對比算法均采用相同運行參數(shù)和環(huán)境，不同之處在于：算法A采用順序分批和S形揀選策略，是倉庫內常用的揀貨方式；算法B采用CWDP節(jié)約與動態(tài)規(guī)劃算法優(yōu)化訂單分批，采用S形揀選策略進行揀選作業(yè)；算法C采用BSA回溯搜索算法優(yōu)化揀選路徑，采用順序分批的方式進行訂單分批。三種算法均不涉及訂單分批和揀選的協(xié)同優(yōu)化。而算法CWDP-BSA采用CWDP算法優(yōu)化分批方案，并采用BSA算法優(yōu)化每一批次的揀選路徑，使雙區(qū)型倉庫內的分揀作業(yè)得到協(xié)同優(yōu)化。對各項算例取平均值作為實驗結果，對比結果如圖10所示。

通過對比實驗結果可以發(fā)現(xiàn)，本文CWDP-BSA算法在分批次揀選時間和總揀選時間上都有較好的表現(xiàn)。用順序分批和S形揀選策略且不涉及訂單分批和揀選協(xié)同優(yōu)化的算法A得到的分批次揀選時間和總揀選時間用時最長；單獨優(yōu)化分批方案的CWDP算法和單獨優(yōu)化揀選路徑的BSA算法求解得出的揀選時間效果相似，CWDP比BSA算法性能好一些；采取訂單分批和揀選協(xié)同優(yōu)化的CWDP-BSA算法求解的分批次揀選時間和總揀選時間在四種算法中最短，并且表現(xiàn)出了良好的性能特征。具體實驗結果如圖10所示。

a）訂單規(guī)模Q的作用。在AGV數(shù)量固定的情況下，隨著訂單規(guī)模的不斷擴大，四種算法的分批次揀選時間和總揀選時間總趨勢都在不斷增加且總揀選時間的增幅較大，其中算法A所花費的揀選時間大于其余三種算法，算法C所得的揀選時間僅次于算法B，算法CWDP-BSA表現(xiàn)出更好的性能，在分批次揀選時間和總揀選時間上都低于其他算法。

b）商品種類K的作用。在訂單規(guī)模固定的情況下，商品種類的增多會使訂單中商品儲位變多，從而使商品間位置更加復雜、揀選距離增加。然而，算法CWDP-BSA在商品種類不斷增多時，分批次揀選時間和總揀選時間都低于其他三種算法，在總揀選時間上，CWDP-BSA算法節(jié)省的時間呈現(xiàn)出越來越多的趨勢。

c）AGV數(shù)量W的作用。在訂單規(guī)模固定的情況下，AGV數(shù)量的增多會直接對總揀選時間有明顯的影響。由圖10的實驗結果可以發(fā)現(xiàn)，AGV數(shù)量增多使總揀選時間不斷下降。算法A揀選時間最長，其次是算法B和C，算法CWDP-BSA的總揀選時間最短。由于每個批次只能由一輛AGV進行揀選，所以AGV總數(shù)量的變化不會對分批次揀選時間產生影響，但在此情況下，由CWDP-BSA算法求解的分批次揀選時間仍然低于其余三種算法，說明在該數(shù)據(jù)集中CWDP-BSA協(xié)同優(yōu)化算法的求解效果優(yōu)勢明顯。

4 結束語

本文針對倉庫傳統(tǒng)訂單分揀作業(yè)效率低、成本高且訂單量不斷激增的現(xiàn)狀，以揀選距離和揀選時間最小化為目標，建立協(xié)同優(yōu)化模型并設計CWDP-BSA算法求解，最后通過實驗驗證了模型與算法的有效性，可得出以下結論：

a）考慮現(xiàn)有的訂單履約流程，建立了針對訂單分批與揀選的協(xié)同優(yōu)化模型，所得出的訂單分批和揀選方案能夠有效提高揀選作業(yè)效率，降低雙區(qū)型倉庫的運營成本。

b）在所設計的CWDP-BSA協(xié)同優(yōu)化算法中，將快速排序法與節(jié)約動態(tài)規(guī)劃思想相結合，并采用多因子選擇的回溯搜索優(yōu)化算法得到訂單批次和路徑的初始解，基于訂單時間窗約束得到分批和揀選方案的近似最優(yōu)解。該方法有效增強了算法的尋優(yōu)能力，提高了求解質量。

c）通過協(xié)同優(yōu)化算法和單獨優(yōu)化算法的對比實驗及不同規(guī)模下的算例實驗，驗證了CWDP-BSA協(xié)同優(yōu)化算法的有效性和穩(wěn)定性，為求解倉庫訂單分批和路徑協(xié)同優(yōu)化問題提供了新的有效算法。

本文考慮了固定訂單情景下的訂單分批與揀選路徑協(xié)同優(yōu)化的問題，而隨著訂單需求個性化的發(fā)展，未來研究可以將發(fā)生缺貨、訂單拆分或緊急插入等情況納入考慮范圍，以此進一步提高優(yōu)化決策的科學性。

參考文獻：

［1］Tompkines J A， White J A， Bozer Y A， et al. Facilities planning［M］. New Jersey： Wiley， 2003.

［2］Wang Yanyan， Wu Yaohua， Liu Peng. Sorting task optimization of automatic sorting system［J］. Journal of Mechanical Engineering， 2011，47（20）：10-17.

［3］Ivan ， Sergej K， Michael S. A hybrid of adaptive large neighborhood search and tabu search for the order-batching problem［J］. European Journal of Operational Research， 2018，264（2）： 653-664.

［4］Cristiano A V， John E B. Order batching using an approximation for the distance travelled by pickers［J］. European Journal of Operational Research， 2020，284（2）： 460-484.

［5］Mehrdad A， Yahia Z M， Ali M. A rule-based heuristic algorithm for online order batching and scheduling in an order picking warehouse with multiple pickers［J］. RAIRO-Operations Research， 2020，54（1）： 101-107.

［6］Cals B， Zhang Yingqian， Dijkman R， et al. Solving the online ba-tching problem using deep reinforcement learning［J］. Computers & Industrial Engineering， 2021，156： 107221.

［7］公斌. 城市物流配送系統(tǒng)改造更新的優(yōu)化設計［J］. 統(tǒng)計與決策， 2009（3）： 60-63. （Gong Bin. Optimization design of urban logistics distribution system transformation and renewal［J］. Statistics and Decision， 2009（3）： 60-63.）

［8］Namrata S， Bhawesh S， Sung H C. Route optimization for warehouse order picking operations via vehicle routing and simulation［J］. SN Applied Sciences， 2020，2（2）： 311-329.

［9］Silva A， Coelho L C， Darvish M， et al. Integrating storage location and order picking problems in warehouse planning［J］. Transportation Research Part E， 2020，140： 102003.

［10］張水旺， 謝浩， 付林萍， 等. 考慮車載容量的多區(qū)型倉庫揀貨路徑優(yōu)化研究［J］. 系統(tǒng)科學與數(shù)學， 2021，41（1）： 238-253. （Zhang Shuiwang， Xie Hao， Fu Linping， et al. Research on optimization of picking path for multi zone warehouse considering vehicle capacity［J］. System Science and Mathematics， 2021，41（1）： 238-253.）

［11］Sebo J， Busa J J. Comparison of advanced methods for picking path optimization： case study of dual-zone warehouse［J］. International Journal of Simulation Modeling， 2020，19（3）： 410-421.

［12］翟夢月， 王征， 李延通， 等. 可移動貨架倉儲系統(tǒng)中商品儲位分配問題研究［J］. 中國管理科學， 2023，31（3）： 167-176. （Zhai Mengyue， Wang Zheng， Li Yantong， et al. Research on the allocation of commodity storage space in mobile shelf storage systems［J］. Chinese Journal of Management Science， 2023，31（3）： 167-176.）

［13］唐堅強， 祁超， 王紅衛(wèi). 帶時間窗的多倉庫訂單拆分與異構車輛路徑聯(lián)合優(yōu)化方法［J］. 系統(tǒng)工程理論與實踐， 2023，43（5）： 1446-1464. （Tang Jianqiang， Qi Chao， Wang Hongwei. A joint optimization method for multi warehouse order splitting and heteroge-neous vehicle paths with time windows［J］. Systems Engineering-Theory & Practice， 2023，43（5）： 1446-1464.）

［14］李彤， 崔晶. 不確定需求環(huán)境下的路徑-裝載協(xié)同優(yōu)化研究［J］. 系統(tǒng)工程理論與實踐， 2021，41（10）： 2561-2580. （Li Tong， Cui Jing. Research on path loading collaborative optimization in uncertain demand environments［J］. Systems Engineering-Theory & Practice， 2021，41（10）： 2561-2580.）

［15］李曉春， 鐘雪靈， 王雄志， 等. 雙旋轉貨架揀貨作業(yè)優(yōu)化設計［J］. 管理工程學報， 2012，26（3）： 114-121. （Li Xiaochun， Zhong Xueling， Wang Xiongzhi， et al. Optimization design of picking operation for double rotating shelves［J］. Journal of Management Engineering， 2012，26（3）： 114-121.）

［16］Merve C T. A fuzzy multi-criteria approach based on Clarke and Wright savings algorithm for vehicle routing problem in humanitarian aid distribution［J］. Journal of Intelligent Manufacturing. 2023，34（5）： 2241-2261.

［17］Stuart D. Richard Bellman on the birth of dynamic programming［J］. Operations Research， 2002， 50（1）： 48-51.

［18］莊燕玲， 孫玉姣， 朱濤， 等. 移動貨架系統(tǒng)多機器人“存-取貨架”調度優(yōu)化方法［J］. 系統(tǒng)工程理論與實踐， 2023，43（2）： 488-508. （Zhuang Yanling， Sun Yujiao， Zhu Tao， et al. Optimization method for multi robot “storage retrieval” scheduling in mobile shelf system［J］. Systems Engineering-Theory & Practice， 2023，43（2）： 488-508.）

［19］Martin A， Martin D， Clemens H， et al. Dual-pivot quicksort： optimality， analysis and zeros of associated lattice paths［J］. Combina-torics Probability and Computing， 2019，28（4）： 485-518.

［20］Civicioglu P. Backtracking search optimization algorithm for numerical optimization problems［J］. Applied Mathematics and Computation， 2013， 219（15）： 8121-8144.

［21］王超， 高揚， 劉超， 等. 基于回溯搜索優(yōu)化算法求解帶時間窗和同時送取貨的車輛路徑問題［J］. 計算機集成制造系統(tǒng)， 2019， 25（9）： 2237-2247. （Wang Chao， Gao Yang， Liu Chao， et al. Solving vehicle routing problem with time window and simultaneous deli-very and pickup based on backtracking search optimization algorithm［J］. Computer Integrated Manufacturing System， 2019，25（9）： 2237-2247.）

［22］Song Xianhai， Zhang Xueqiang， Zhao Sutao， et al. Backtracking search algorithm for effective and efficient surface wave analysis［J］. Journal of Applied Geophysics， 2015，114： 19-31.

［23］El-Fergany A. Optimal allocation of multitype distributed generators using backtracking search optimization algorithm［J］. International Journal of Electrical Power & Energy Systems， 2015，64（64）： 1197-1205.

［24］Modiri-delshad M， Rahim N A. Solving non-convex economic dispatch problem via backtracking search algorithm［J］. Energy， 2014， 77： 372-381.

［25］董海， 徐曉鵬. 離散回溯搜索算法求解多柔性作業(yè)車間調度［J］. 運籌與管理， 2022，31（1）： 87-91. （Dong Hai， Xu Xiaopeng. Discrete backtracking search algorithm for multi flexible job shop scheduling［J］. Operations Research and Management， 2022，31（1）： 87-91.）

［26］胡中波， 王旭鵬. 求解測試用例自動生成問題的多因子回溯搜索優(yōu)化算法［J］. 計算機應用， 2023， 43（4）： 1214-1219. （Hu Zhongbo， Wang Xupeng. A multifactor backtracking search optimization algorithm for solving the problem of automatic test case generations［J］. Journal of Computer Applications， 2023，43（4）： 1214-1219.）

［27］孫軍艷， 陳智瑞， 牛亞儒， 等. 基于嵌套遺傳算法的揀貨作業(yè)聯(lián)合優(yōu)化［J］. 計算機應用， 2020，40（12）： 3687-3694. （Sun Junyan， Chen Zhirui， Niu Yaru， et al. Joint optimization of picking operations based on nested genetic algorithm［J］. Journal of Computer Applications， 2020，40（12）： 3687-3694.）