雙區(qū)型倉庫訂單分批與揀選協(xié)同優(yōu)化研究

張艷菊 李群 張彭涵 李蕊

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

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

中圖分類號(hào)：F252;TP18?? 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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 引言

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

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

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

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

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

1 問題描述及建模

1.1 問題描述

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

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

定義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］為兩個(gè)待揀選訂單編號(hào)，則行走過道的距離d1=|x′1-x1|×a；將穿越巷道時(shí)兩排貨架的距離加入到計(jì)算中，那么行走巷道的距離d2=|x′2-x2|×（d+2b）；不考慮垂直方向的移動(dòng)距離，穿越貨位的距離d3分三種情況進(jìn)行如下討論：

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

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

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

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

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

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

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

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

示例1 為了更好地說明所研究問題，設(shè)置七個(gè)等待揀選的訂單Or進(jìn)行說明。

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

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

而這種訂單分批和揀選策略的效率并不高，依據(jù)揀選請求r，考慮將訂單進(jìn)行連接，把經(jīng)過但沒有出現(xiàn)在路線Rw上的訂單按照次序插入到揀選路線中，直到全部的訂單都被安排完揀選路線時(shí)結(jié)束。例如，將批次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）所示。計(jì)算出優(yōu)化后第一批次耗費(fèi)的總時(shí)間t1=ttravel+tpick=149 s，第二、三批次的總時(shí)間t2、t3分別為146 s、95 s?？梢钥闯?，協(xié)同優(yōu)化后的分揀總時(shí)間明顯少于優(yōu)化前所需要的總時(shí)間。由上述訂單分批與揀選路徑協(xié)同優(yōu)化后所求得的結(jié)果可知，優(yōu)化策略明顯提高了作業(yè)效率?？梢韵胂?，隨著訂單規(guī)模的擴(kuò)大，優(yōu)化分批和揀選策略將會(huì)節(jié)省更多時(shí)間，說明傳統(tǒng)分批方式與物品揀選策略存在弊端，本文提出的協(xié)同優(yōu)化策略具有一定的可行性。

1.2 問題假設(shè)

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)介紹

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

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

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

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

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

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

3.3 算法有效性分析

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

3.3.1 小規(guī)模仿真實(shí)驗(yàn)

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

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

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

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

3.3.2 大規(guī)模仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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

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

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

參考文獻(xiàn)：

［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)化設(shè)計(jì)［J］. 統(tǒng)計(jì)與決策， 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)科學(xué)與數(shù)學(xué)， 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］翟夢月， 王征， 李延通， 等. 可移動(dòng)貨架倉儲(chǔ)系統(tǒng)中商品儲(chǔ)位分配問題研究［J］. 中國管理科學(xué)， 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］唐堅(jiān)強(qiáng)， 祁超， 王紅衛(wèi). 帶時(shí)間窗的多倉庫訂單拆分與異構(gòu)車輛路徑聯(lián)合優(yōu)化方法［J］. 系統(tǒng)工程理論與實(shí)踐， 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)工程理論與實(shí)踐， 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］李曉春， 鐘雪靈， 王雄志， 等. 雙旋轉(zhuǎn)貨架揀貨作業(yè)優(yōu)化設(shè)計(jì)［J］. 管理工程學(xué)報(bào)， 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］莊燕玲， 孫玉姣， 朱濤， 等. 移動(dòng)貨架系統(tǒng)多機(jī)器人“存-取貨架”調(diào)度優(yōu)化方法［J］. 系統(tǒng)工程理論與實(shí)踐， 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áng)， 劉超， 等. 基于回溯搜索優(yōu)化算法求解帶時(shí)間窗和同時(shí)送取貨的車輛路徑問題［J］. 計(jì)算機(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è)車間調(diào)度［J］. 運(yùn)籌與管理， 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］胡中波， 王旭鵬. 求解測試用例自動(dòng)生成問題的多因子回溯搜索優(yōu)化算法［J］. 計(jì)算機(jī)應(yīng)用， 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］. 計(jì)算機(jī)應(yīng)用， 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.）