AGV“貨到人”揀選系統的移動貨架選擇方法

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

關鍵詞：“貨到人”揀選；自動導引車（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

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

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

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

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

1 問題描述與模型構建

1.1 問題描述

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

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

1.1aLPOUmda9N0itgLWaXugw==2 模型建立

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

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

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

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

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

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

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

3 基于線性遞減權重的粒子群貨架求解算法

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

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

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

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

步驟4：線性遞減權重，表示慣性權重最大值，示慣性權重最小值，表示當前迭代步數。

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

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

步驟7：滿足最大循環次數，則退出，否則返回步驟3。

4 仿真實驗與算法有效性

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

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

5 敏感性分析

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

5.1 批次數量敏感性分析

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

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

5.2 品類數量敏感性分析

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

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

5.3 貨架數量敏感性分析

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

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

5.4 訂單數量敏感性分析

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

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

5.5 總體均值的區間估計

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

步驟1：計算樣本均值。

步驟2：計算樣本方差。

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

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

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

6 結 論

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

參考文獻：

[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] 王轉，裴澤平. 啟發式路徑下節約里程的訂單分批算法 [J]. 計算機工程與應用，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 電子商務環境下訂單揀選與配送聯合調度優化[J]. 中國管理科學，2016，24（7）： 101-109.

[8] 羅曉萌，夏雪垠，李建斌.快消品電子商務倉儲訂單批次問題研究[J]. 系統科學與數學，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ü?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]. 制造業自動化，2021，43（5）：108-112.

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

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

[21] 李昆鵬，劉騰博，李文莉.改進自適應遺傳算法求解“貨到人”揀選系統訂單分批問題[J]. 機械工程學報，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.