摘 要：基于自動導(dǎo)引車（AGV）的“貨到人”揀選系統(tǒng)，各品類商品可以拆零存放在不同貨架上，同一貨架也可以存儲多種商品，貨架的位置也是隨機移動的。面對待揀選的訂單，選擇哪些貨架移動到揀選臺，以滿足訂單的品類和數(shù)量要求，并最小化選取移動貨架個數(shù)，是此類型倉庫需要解決的關(guān)鍵問題。針對該問題，文章提出基于訂單相似度進行訂單分批，再通過線性遞減權(quán)重的粒子群算法來優(yōu)化移動貨架選擇解。由于移動貨架的優(yōu)化問題是NP-hard問題，線性規(guī)劃求解器難以求解，實驗結(jié)果表明，與線性規(guī)劃求解器Lingo相比，文本的兩階段移動貨架選擇方法是有效的，可以在短時間得出求解方案，大大提升了求解效率。敏感性分析進一步揭示了批次數(shù)量、品類數(shù)量、貨架數(shù)量以及訂單數(shù)量，對搬運貨架次數(shù)的影響，為管理者提供了決策依據(jù)。

關(guān)鍵詞：“貨到人”揀選；自動導(dǎo)引車（AGV）；移動貨架；訂單相似度；粒子群算法

中圖分類號：F252；U492 文獻標志碼：A DOI：10.13714/j.cnki.1002-3100.2024.18.007

Abstract： In automated guided vehicle（AGV） "parts-to-picker" picking system， each kind of products can be disassembled and stored in a number of movable racks. A rack can also store multiple products， and the positions of the racks are also randomly moved. For a batch of orders to be picked， it is a key problem that needs to be solved in the application of this new warehousing system to determine which racks should be moved to the picking platform to meet the picking requirements of product types and quantities and minimize the number of the racks to be moved. This paper proposes an order similarity measure method for order batching， and then optimizes the mobile rack selection solution through particle swarm optimization algorithm with linear decreasing weights. Because the optimization problem of the mobile rack is an NP hard problem， it is difficult for linear programming solvers to solve. The experimental results show that， compared with the linear programming solver Lingo， the two-stage mobile rack selection method proposed in this paper is effective and can obtain a solution in a short time， greatly improving the efficiency of the solution. Sensitivity analyses further reveal the influence of batch quantity， category quantity， rack quantity， and order quantity on number of times of rack handling， and provide the important basis of decision for managers.

Key words： "parts-to-picker" picking; automated guided vehicle（AGV）; mobile rack; similarity of orders; particle swarm optimization algorithm

電子商務(wù)的發(fā)展省去了很多中間環(huán)節(jié)，很多制造企業(yè)將產(chǎn)品庫存交由協(xié)同發(fā)展的第三方物流企業(yè)托管，面對高頻次、小批量和多品種特征的客戶訂單，第三方物流企業(yè)傾向于通過一個集倉儲管理、訂單處理、分揀派送于一體的物流配送中心，來適應(yīng)制造企業(yè)的出貨要求，實現(xiàn)與制造業(yè)在銷售環(huán)節(jié)的聯(lián)動發(fā)展。訂單分揀是一個配送中心的核心，直接影響著整個倉庫的效率，揀選作業(yè)成本占總運營成本的55%以上[1]，選擇一種合理有效的揀選策略，在優(yōu)化分揀作業(yè)流程、減少作業(yè)處理時間上起到關(guān)鍵作用。

揀選場景一般分為“人到貨”揀選和“貨到人”揀選。傳統(tǒng)“人到貨”揀選策略研究比較成熟，構(gòu)建的模型通常以揀選人員的行走距離或行走時間為優(yōu)化目標[2-6]，主要將不同的訂單相似準則作為約束考慮，例如相同的通道數(shù)[7-8]、商品存儲位置相近[9]等?！柏浀饺恕睊x根據(jù)不同的揀選設(shè)備，則有miniload“貨到人”系統(tǒng)、穿梭車“貨到人”系統(tǒng)、AGV“貨到人”系統(tǒng)，本文在AGV機器人系統(tǒng)的環(huán)境下考慮這一過程，該系統(tǒng)由Jünemann[10]提出概念，亞馬遜首先將其著名的KIVA系統(tǒng)付諸實踐[11]。如今，越來越多的類似機器人系統(tǒng)被用于支持現(xiàn)代倉庫，例如Swisslog公司的CarryPick? [12]。

本文研究自動導(dǎo)引車（AGV）“貨到人”系統(tǒng)的揀選策略問題，它的優(yōu)化目標及約束因素與傳統(tǒng)“人到貨”揀選問題有本質(zhì)區(qū)別，目前基于AGV的“貨到人”揀選研究明顯少于其在實踐中的應(yīng)用[13]，部分學(xué)者對此展開了初步探索。Xiang等[14]研究了基于KIVA系統(tǒng)的存儲分配問題，旨在決定將哪個產(chǎn)品放入哪個移動貨架，以最大限度地提高產(chǎn)品相似性。Roy等[15]研究了存儲區(qū)域的AGV機器人分配策略。Yang等[16]研究了基于AGV的揀選系統(tǒng)中訂單排序和貨架調(diào)度的聯(lián)合優(yōu)化問題，建立了一個混合整數(shù)線性規(guī)劃模型，并提出了一個兩階段求解過程。Boysen等[17]研究了分揀訂單分批和排序，以及被拖到分揀站點的貨架排序問題。秦馨等[18]以總搬運貨物次數(shù)最少為目標，建立了訂單分批數(shù)學(xué)模型，并用遺傳算法求解。李珍萍等[19]分析了影響訂單揀選成本和效率的兩種主要因素，建立了以訂單分批揀選總部極小化為目標的整數(shù)規(guī)劃模型，設(shè)計了K-MAX聚類算法求解。張國維等[20]以極小化貨架搬運成本和商品揀選成本為目標，建立了AGV智能倉庫訂單分批整數(shù)規(guī)劃模型，并提出了一種基于訂單和貨架交替選擇的貪婪求解算法。李昆鵬等[21]以人工揀選成本和AGV搬運成本之和最小為目標函數(shù)構(gòu)建數(shù)學(xué)模型，并設(shè)計改進自適應(yīng)遺傳算法求解。這些文獻提及了貨架選擇的重要性，但是側(cè)重點是針對訂單分批問題建立模型和求解方法，并未給出具體貨架的選擇方法。

綜上研究，本文認為求解AGV“貨到人”系統(tǒng)的AGV搬運次數(shù)最小化問題，需要解決兩個問題，一是決定哪些訂單形成同一個批次，二是每一個批次需要搬動哪些貨架。本文第一階段使用訂單相似度來進行訂單分批，第二階段使用線性遞減權(quán)重粒子群算法來改進貨架搬運次數(shù)解，以探索AGV“貨到人”揀選系統(tǒng)移動貨架的選擇方法。

1 問題描述與模型構(gòu)建

1.1 問題描述

以AGV為搬運工具的分揀倉中，有貨架個，每個揀選臺可以容納個周轉(zhuǎn)箱，整個倉庫一共存儲個品類的商品，在單位時間內(nèi)有個訂單待揀選，如何將這些訂單進行分批揀選。由于此類揀選倉的貨架存放位置不是固定的，可以將貨物的搬運距離與貨物的搬運次數(shù)近似看作線性相關(guān)，所以只要貨架被搬運的次數(shù)越少，搬運的總距離或總成本就越低，揀選臺的工作效率就越高?；诖耍疚囊宰钚』疉GV搬運貨架次數(shù)為目標，決策訂單的分配批次以及貨架對于訂單的服務(wù)關(guān)系，最終得到合理的訂單分批和貨架調(diào)度方案。

為了方便建立模型，考慮如下假設(shè)：所有訂單揀選信息在分批前已知；所有貨架上的存儲商品信息在分批前已知；每個貨架有多個貨格，每個貨格只能存放一個商品，但同一個商品可以在不同的貨架中存放；貨架上的貨物數(shù)量大于訂單需要的商品數(shù)量；訂單不允許被分割，每個訂單只能被劃分到一個批次中；揀選人員揀選不同商品的成本相同；1個周轉(zhuǎn)箱對應(yīng)1個訂單，批次的最大訂單數(shù)小于等于周轉(zhuǎn)箱數(shù)。

1.1aLPOUmda9N0itgLWaXugw==2 模型建立

根據(jù)問題描述，符號及變量定義如表1所示。

目標函數(shù)（1）表示最小化AGV搬運貨架的次數(shù)；式（2）表示每個訂單只能被分配到一個批次中；式（3）表示一個批次所有訂單數(shù)量之和小于等于周轉(zhuǎn)箱數(shù)；式（4）表示同一批次訂單的商品數(shù)量之和小于貨架上同種類商品數(shù)量之和；式（5）和式（6）表示0—1變量。

2 基于訂單相似度的訂單分批

訂單一般包含了物品品類、物品數(shù)量、交貨地址及日期等諸多信息，訂單相似度就是指訂單包含的物品品類、交貨期等方面具有相似性[22]，通過計算訂單相似度，可以減少重復(fù)揀選的次數(shù)，縮短揀選時間，實現(xiàn)相似度高的訂單批量揀選。本文綜合考慮訂單品類相似度和訂單交貨期相似度來構(gòu)建訂單相似度，并據(jù)此形成初始訂單分批方案。品類相似度如下。

表示任意兩個訂單和之間的品類相似度，其中是訂單包含的品類編號，是訂單包含的品類編號，是訂單和訂單具有的相同品類數(shù)量，是訂單和訂單合并后所有品類數(shù)量。交貨期相似度如下。

表示任意兩個訂單和之間的交貨期相似度，其中是訂單的交貨期，是訂單的交貨期，越小，說明兩個訂單的交貨期越接近， 相似度越大，表示訂單集D 中兩個訂單交貨期之差的最大絕對值，用于進行歸一化處理。最終訂單相似度定義如下。

以分別表示品類相似度和交貨期相似度的權(quán)重。若說明揀選單的構(gòu)成更注重揀選效率，通過相同品類來減少AGV搬運次數(shù)。若，說明揀選單的構(gòu)成更注重減少訂單延遲時間。通過將品類相似度和交貨期相似度相結(jié)合并賦予不同的權(quán)重系數(shù)來構(gòu)建訂單相似度進行訂單分批，可以達到效率和客戶服務(wù)水平的平衡，并與最終貨架選擇結(jié)果緊密相關(guān)。

3 基于線性遞減權(quán)重的粒子群貨架求解算法

面向批次訂單，究竟選擇哪些貨架移動到揀選臺，以滿足訂單商品品類及數(shù)量要求，并最小化貨架個數(shù)，同樣是NP-hard難題，本文設(shè)計線性遞減權(quán)重粒子群算法來求解貨架組合，算法步驟如下。

步驟1：根據(jù)貨架品類和揀選單品類的包含關(guān)系，隨機初始化貨架種群中每個粒子的位置和速度。

步驟2：計算每個粒子的搬運貨架次數(shù)的適應(yīng)度值，將粒子的位置和適應(yīng)度值存儲在粒子的個體極值中，將所有個體極值中最優(yōu)適應(yīng)度值的個體位置和適應(yīng)度值保存在全局極值中。

步驟3：更新粒子的位移和速度。代表更新前的貨架解粒子，代表更新后的貨架解粒子，代表更新前的速度，代表更新后的速度，為慣性權(quán)重，c1、c2代表加速度數(shù)，r1、r2代表在[0，1]之間隨機產(chǎn)生的加速度權(quán)重系數(shù)。

步驟4：線性遞減權(quán)重，表示慣性權(quán)重最大值，示慣性權(quán)重最小值，表示當前迭代步數(shù)。

步驟5：對每個粒子，用它的適應(yīng)度值和個體極值進行比較，如果，則用替換掉。

步驟6：對每個粒子，用它的適應(yīng)度值和全局極值，比較，如果，則用替換掉。

步驟7：滿足最大循環(huán)次數(shù)，則退出，否則返回步驟3。

4 仿真實驗與算法有效性

通過設(shè)計仿真實驗，利用MATLAB編制程序，對本文提出的基于線性遞減權(quán)重的粒子群移動貨架選擇優(yōu)化算法進行分析，仿真環(huán)境為MATLAB 2016a、Window10操作系統(tǒng)、Intel i5-5200U CPU 2.20GHz、16G RAM。本文考慮訂單需求多樣化、商品庫存多貨架分布的特點隨機生成數(shù)據(jù)，對6組不同規(guī)模的算例進行測試，其中每個貨架有4個貨格，周轉(zhuǎn)箱數(shù)量為3。結(jié)果如表2所示，以AGV搬運貨架次數(shù)為衡量指標。

結(jié)果表明，在不同算例規(guī)模下，基于訂單相似度的貨架選擇粒子群算法最優(yōu)解與LINGO計算的最優(yōu)解沒有差別，說明算法的合理性和有效性。在求解時間上，隨著訂單數(shù)和貨架數(shù)不斷增加時，LINGO求解時間耗時較長，而AGV智能倉庫對揀選時間要求很高，而本文算法能夠在短時間內(nèi)獲得AGV搬運貨架次數(shù)較少的訂單分批方案，具有實用性。

5 敏感性分析

在不同的時間段，顧客訂單數(shù)量及其訂單的商品結(jié)構(gòu)會有很大的不同，例如在電商大促日，顧客的訂單數(shù)量會激增，每個訂單所包含品類也會增多，不同的訂單數(shù)量、訂單品類結(jié)構(gòu)如何影響貨架搬運次數(shù)，物流倉儲方應(yīng)該如何調(diào)整貨架數(shù)量以及揀選批次，都是需要考慮的問題。本節(jié)主要分析批次數(shù)量、品類數(shù)量、貨架數(shù)量以及訂單數(shù)量，對搬運貨架次數(shù)的影響，旨在給倉儲管理者提供相應(yīng)的管理啟示。

5.1 批次數(shù)量敏感性分析

算例規(guī)模設(shè)置訂單數(shù)為100，貨架數(shù)為30，每個貨架有4個貨位，品類數(shù)為70，批次數(shù)為1、2、4、5、10、20、25、50、100的情況下，測試不同批次數(shù)量對AGV搬運貨架次數(shù)的影響，測試數(shù)據(jù)隨機產(chǎn)生，測試結(jié)果取每次測試運行十次中的最小值，再取十次測試的平均值，數(shù)據(jù)如表3所示。

實驗結(jié)果表明，在同樣的訂單數(shù)量、貨架數(shù)量和品類數(shù)量的情況下，批次數(shù)量對AGV搬運貨架次數(shù)的影響顯著，分批越多，AGV搬運貨架的次數(shù)也呈等倍數(shù)的增長，說明應(yīng)盡可能減少批次數(shù)量，如圖1所示。

5.2 品類數(shù)量敏感性分析

算例規(guī)模設(shè)置訂單數(shù)為100，貨架數(shù)為30，每個貨架有4個貨位，批次數(shù)為5，在品類數(shù)為10、20、30、40、50、60、70、80、90、100、110、120的情況下，測試不同品類數(shù)量對AGV搬運貨架次數(shù)的影響，測試數(shù)據(jù)隨機產(chǎn)生，測試結(jié)果取每次測試運行十次中的最小值，再取十次測試的平均值，數(shù)據(jù)如表4所示。

實驗結(jié)果表明，在同樣的訂單數(shù)量、貨架數(shù)量和批次數(shù)量的情況下，隨著品類數(shù)量的增加，對AGV搬運貨架次數(shù)的影響逐漸趨于平緩，在當前規(guī)模下，當品類數(shù)在70～120時，AGV搬運貨架的次數(shù)基本沒有差別，說明品類數(shù)量的增加，不會必然導(dǎo)致AGV搬運貨架次數(shù)的增加，如圖2所示。

5.3 貨架數(shù)量敏感性分析

算例規(guī)模設(shè)置訂單數(shù)為100，每個貨架有4個貨位，品類數(shù)為70，批次數(shù)為5的情況下，在貨架數(shù)為20、30、40、50、60、70、80、90、100、110的情況下，測試不同貨架數(shù)量對AGV搬運貨架次數(shù)的影響，測試數(shù)據(jù)隨機產(chǎn)生，測試結(jié)果取每次測試運行十次中的最小值，再取十次測試的平均值，數(shù)據(jù)如表5所示。

實驗結(jié)果表明，在同樣的訂單數(shù)量、品類數(shù)量和批次數(shù)情況下，隨著貨架數(shù)量的增加，AGV搬運貨架的次數(shù)越來越多，說明在貨架能夠滿足商品存儲數(shù)量的情況下，貨架數(shù)越少越好，貨架越多會造成商品在貨架上的分布越來越分散，從而導(dǎo)致搬運次數(shù)增加，如圖3所示。

5.4 訂單數(shù)量敏感性分析

算例規(guī)模設(shè)置貨架數(shù)為30，每個貨架有4個貨位，品類數(shù)為70，批次數(shù)為5，在訂單規(guī)模100、200、300、400、500、600、700、800、900、1 000的情況下，測試不同訂單數(shù)量對AGV搬運貨架次數(shù)的影響，測試數(shù)據(jù)隨機產(chǎn)生，測試結(jié)果取每次測試運行十次中的最小值，再取十次測試的平均值，數(shù)據(jù)如表6所示。

實驗結(jié)果表明，在同樣的貨架數(shù)量、品類數(shù)量和批次數(shù)情況下，隨著訂單數(shù)量的增加，AGV搬運貨架的次數(shù)只在一個很小范圍內(nèi)波動，說明批次訂單數(shù)量對AGV搬運貨架次數(shù)的影響很小，如圖4所示。

5.5 總體均值的區(qū)間估計

在現(xiàn)實生活中，搬運貨架次數(shù)分布服從正態(tài)分布或者近似地用正態(tài)分布刻畫，上述敏感性分析中，僅使用了樣本均值來估計總體均值，即點估計法。使用點估計對總體的未知參數(shù)進行估計時，難免有一些誤差，究竟估計量的值與真值相差多少，需要進一步尋找總體均值的范圍，并應(yīng)該具有一定的可靠程度，在此使用區(qū)間估計法，進一步根據(jù)樣本數(shù)字特征推斷總體的數(shù)字特征，基本步驟如下。

步驟1：計算樣本均值。

步驟2：計算樣本方差。

步驟3：使用T統(tǒng)計量對總體均值進行區(qū)間估計，其中為樣本容量，T統(tǒng)計量服從自由度為的分布。

步驟4：取檢驗水平=0.05，則區(qū)間[]稱為的95%的置信區(qū)間，分別稱為置信下限和置信上限。

根據(jù)計算，可以得到批次數(shù)量、品類數(shù)量、貨架數(shù)量、訂單數(shù)量分別對搬運次數(shù)的總體均值的95%的置信區(qū)間，如表7—10所示。

6 結(jié) 論

移動貨架倉庫中的貨架選擇問題是針對一批訂單的揀選需求，構(gòu)建滿足訂單揀選需求、所需要貨架數(shù)量最小化的數(shù)學(xué)優(yōu)化問題，本文通過設(shè)計基于訂單相似度的訂單分批算法和線性遞減權(quán)重的粒子群貨架選擇算法，來求解該問題。最后實驗結(jié)果表明，本文設(shè)計的算法在算例測試中有較好的表現(xiàn)，算法可以得到較優(yōu)的解決方案，且耗時相較于Lingo更少。通過敏感性分析，發(fā)現(xiàn)批次數(shù)量對AGV搬運貨架次數(shù)的影響顯著，分批越多，AGV搬運貨架的次數(shù)也呈等倍數(shù)增長；品類數(shù)量的增加，對AGV搬運貨架次數(shù)的影響逐漸趨于平緩；在滿足商品儲存數(shù)量情況下，貨架數(shù)量的增加，會導(dǎo)致AGV搬運貨架的次數(shù)變多；對同一揀選倉庫來說，訂單數(shù)量的增加，訂單數(shù)量對AGV搬運貨架次數(shù)的影響很小。最后為探究點估計對總體均值估計帶來的誤差，進一步尋找了置信度為95%的總體均值的置信區(qū)間，提升了這些發(fā)現(xiàn)的可靠性。

參考文獻：

[1] DE KOSTER R，LE-DUC T，ROODBERGEN K J. Design and control of warehouse order picking：A literature review[J].European Journal of Operational Research，2007，182（2）：481-501.

[2] KOCH S，W?SCHER G. A grouping genetic algorithm for the Order Batching Problem in distribution warehouses[J]. Journal ofBusiness Economics，2016，86（1）：131-153.

[3] HONG S. Order batch formations for less picker blocking in a narrow-aisle picking system[J]. Industrial Engineering andManagement Systems，2015，14（3）：289-298.

[4] 王轉(zhuǎn)，裴澤平. 啟發(fā)式路徑下節(jié)約里程的訂單分批算法 [J]. 計算機工程與應(yīng)用，2018，54（23）：203-209.

[5] ARDJMAND E，SHAKERI H，SINGH M，et al. Minimizing order picking makespan with multiple pickers in a wave pickingwarehouse[J]. International Journal of Production Economics，2018，206：169-183.

[6] JIANG Zhongzhong，WAN Mingzhong，PEI Zhi，et al. Spatial and temporal optimization for smart warehouses with fast turnover[J/OL]. Computers & Operations Research，2021，125，105091.[2024-02-20]. https：//doi.org/10.1016/j.cor.2020.105091.

[7] 王旭坪，張珺，易彩玉. B2C 電子商務(wù)環(huán)境下訂單揀選與配送聯(lián)合調(diào)度優(yōu)化[J]. 中國管理科學(xué)，2016，24（7）： 101-109.

[8] 羅曉萌，夏雪垠，李建斌.快消品電子商務(wù)倉儲訂單批次問題研究[J]. 系統(tǒng)科學(xué)與數(shù)學(xué)，2016，36（6）：847-859.

[9] MENéNDEZ S，PARDO E G，ALONSO-AYUSO A，et al. Variable neighborhood search strategies for the order batchingproblem[J]. Computers & Operations Research，2017，78（2）：500-512.

[10] JüNEMANN R. Materialflu? und logistik—Systematische grundlagen mit praxisbeispielen[M]. Berlin：Aufl.，1989：18.

[11] ENRIGHT J J，WURMAN P R. Optimization and coordinated autonomy in mobile fulfillment systems[C]//AAAIWS'11-09：Proceedings of the 9th AAAI Conference on Automated Action Planning for Autonomous Mobile Robots，2011：33-38.

[12] BOYAEN N，DE KOSTER R，F(xiàn)ü?LER D. The forgotten sons：Warehousing systems for brick-and-mortar retail chains[J].European Journal of Operational Research，2021，288（2）：361-381.

[13] AZADEH K，DE KOSTER R，ROY D. Robotized and automated warehouse systems：Review and recent developments[J].Transportation Science，2019，53（4）：917-945.

[14] XIANG Xi，LIU Changchun，MIAO Lixin. Storage assignment and order batching problem in Kiva mobile fulfilment system[J].Engineering Optimization，2018，50（11）：1941-1962.

[15] ROY D，NIGAM S，DE KOSTER R，et al. Robot-storage zone assignment strategies in mobile fulfillment systems[J].Transportation Research Part E：Logistics and Transportation Review，2019，122：119-142.

[16] YANG Xiying，HUA Guowei，HU Linyuan，et al. Joint optimization of order sequencing and rack scheduling in therobotic mobile fulfilment system[J/OL].Computers&Operations Research，2021，135：105467.[2024-02-25].https：//doi.org/10.1016/j.cor.2021.105467.

[17] BOYSEN N，BRISKORN D，EMDE S. Parts-to-picker based order processing in a rack moving mobile robots environment[J].European Journal of Operational Research，2017，262（2）：550-562.

[18] 秦馨，趙劍道，任楠，等.基于遺傳算法的訂單分批策略研究[J]. 制造業(yè)自動化，2021，43（5）：108-112.

[19] 李珍萍，田宇璇，卜曉奇，等.無人倉系統(tǒng)訂單分批問題及K-max聚類算法[J].計算機集成制造系，2021，27（5）：1506-1517.

[20] 張國維，吳凌云.考慮商品數(shù)量和商品揀選成本的AGV智能倉庫訂單分批問題研究[J].運籌與管理，2022，31（12）： 9-15.

[21] 李昆鵬，劉騰博，李文莉.改進自適應(yīng)遺傳算法求解“貨到人”揀選系統(tǒng)訂單分批問題[J]. 機械工程學(xué)報，2023，59（4）： 308-317.

[22] LI Jianbin，HUANG Rihuan，DAI J B. Joint optimization of order batching and picker routing in the online retailer's warehousein China[J]. International Journal of Production Research，2017，55（2）：447-461.