基于訂單相似度的AutoStore系統訂單分批問題研究

摘 要：作為一種高度自動化、智能化的高密度存儲系統，AutoStore系統受到電商企業廣泛關注。相較傳統倉庫，該系統能顯著提高效率、降低成本。為進一步優化其效率，針對AutoStore系統中訂單分批問題，以最大化單批訂單相似度為目標構建了混合整數線性規劃模型，并設計了基于層次聚類的啟發式算法進行求解。根據現實訂單數據設置了多個不同規模算例，通過實驗證明了算法可行性。結果表明對不同規模訂單分批問題，所提出算法均可在短時間內取得較優解。

關鍵詞：AutoStore倉儲系統；訂單分批；混合整數規劃模型；啟發式算法；聚類算法

中圖分類號：F253.9 文獻標志碼：A DOI：10.13714/j.cnki.1002-3100.2024.19.009

Abstract： In the realm of contemporary logistics， the AutoStore system， characterized by its advanced automation and intelligent high-density storage capacities， has garnered substantial attention from e-commerce enterprises. When juxtaposed with conventional warehousing systems， the AutoStore demonstrates a pronounced enhancement in operational efficiency while concurrently driving down associated costs. In an endeavor to amplify its efficacy， we addressed the intricate order batching issue inherent to the

AutoStore system. A mixed-integer linear programming model was meticulously formulated， predicated on the objective of optimizing the homogeneity within individual order batches. To achieve an effective resolution， we conceived and implemented a heuristic algorithm anchored in hierarchical clustering methodologies. Empirical validations， predicated on real-world order data across diverse scales， substantiated the algorithm's practicability. Preliminary outcomes indicate that irrespective of the order batch scale， our proffered algorithm consistently delivers superior solutions in abbreviated timeframes.

Key words： AutoStore warehousing system; order batching; mixed-integer programming model; heuristic algorithm; clustering algorithm

0 引 言

《中國制造2025》國家發展戰略中明確指出，為促使我國工業制造產能提升，需要進一步推進智能物流發展[1]。在這一戰略導向下，眾多電商企業將物聯網（IoT）和人工智能（AI）等前沿技術投入到智能物流設備和系統的研發中，以提升物流的自動化和智能化程度[2]。其中一種成果為AutoStore系統，這是一種高度自動化、智能化且儲存密度極高的系統[3]。如圖1所示，AutoStore通過縱向堆疊最多十五個規格相同的標準儲物箱來構建儲存堆垛，并將這些堆垛連接組成一個空間利用率極高的儲存系統[4]。該系統中可以通過放置隔板，將料箱內部分隔成不同的小區域，從而在同一個料箱中存儲多個種類貨品[5]。

在傳統倉庫中的訂單揀選通常會面臨一系列問題，其中首要問題是低效率[7]。傳統揀選系統通常采取“人到貨”揀貨方式，這意味著工人需要從工作臺移動到儲存區域進行揀貨，導致工人在倉庫中進行大量重復移動，產生大量的時間和勞動力浪費[8]。此外，傳統倉庫通常不能靈活應對訂單變化情況，當訂單量增加或SKU種類增多時，這些倉庫很難臨時擴展，可能需要重新設計布局及增加更多工人[3]。另外，當某個訂單需要優先處理時，傳統系統難以快速調整揀選優先級。最后，揀貨在整個倉庫運營中的成本占比相當大，通常占倉庫運營成本一半以上[9]。

對于上述問題，AutoStore系統憑借其高度自動化和緊湊的系統設計，可以提供較好的解決方案。首先，通過機器人將料箱送至工作臺的“貨到人”方式，可以顯著提高揀選效率，減少了時間和勞動力的浪費[10]。同時，由于機器人可以垂直和水平方向移動，可以隨時根據需求調度到相應的存儲貨位，結合AutoStore系統高度模塊化的特性，整個系統具有很高的靈活性，能夠根據不同的優先級和訂單需求快速調整揀貨方案[4]。最后，由于應用了大量自動揀貨機器人代替人工，該系統的揀貨成本大大低于傳統倉庫[11]。

訂單揀選效率的提高是現代物流和供應鏈管理中的關鍵問題，為進一步提高訂單揀選效率，通常可以采用訂單分批的策略。它的核心理念是將含有相同種類貨物的多個訂單集中在同一個波次中進行處理。現階段，國內外許多學者針對不同智能倉儲系統對該問題進行過深入研究。Petersen et al.[12]的研究表明，在人工揀選系統中，對于小批量訂單進行訂單分批能顯著節省總成本。這為訂單分批的實際應用提供了可靠的數據支持，證明了該策略的有效性。Henn et al.[13]則通過設計啟發式算法來進行訂單的分批和排序，進一步減少訂單的延遲時間。此外，王旭坪等[14]提出了一種旨在最小化訂單處理時間的非線性揀選與配送聯合調度模型，通過數值實驗模擬結果分析，發現這一模型對問題的處理能力更加全面，可以應對更加復雜的揀貨場景。王轉[15]針對電商配送中心的實際情況，更深入地探討了訂單分批在現實場景中的應用，綜合考慮揀貨工具和貨品包裝的體積，構建了以最大化節約搬運里程為目標的訂單分批求解模型。

盡管上述研究為訂單分批問題提供了多種有價值的研究方法，但對于AutoStore系統，這些傳統方法可能并不完全適用，仍有必要針對其特殊的儲存方式和揀貨方式進一步設計訂單排序方法。由于該系統內單個料箱可以存儲多個種類的貨物，且料箱通常按照共享存儲的方式緊密堆疊[16]。因此，如何有效地將多個訂單組合起來，使得對同種貨物有需求的訂單可以盡量集中在同一個訂單批次中，這對減少揀貨任務分配的數量和機器人揀選料箱的次數至關重要。在現有針對AutoStore系統內貨物存儲問題的研究中，楊瑋等[17]通過結合關聯規則挖掘算法與混沌種子優化算法，提出貨物合箱的存儲優化方法，該方法的核心是結合關聯規則挖掘算法與混沌種子優化算法。通過從機器人翻箱操作、料箱的分配規則、系統布局三方面進行分析，并結合AutoStore的運作規律，建立了以機器人揀貨行走距離最短為目標的數學模型，實現了更高效的貨物存儲和揀貨過程。吳瑩瑩[10]基于關聯規則提出一種合箱策略，并根據FP-growth算法設計了混合種子算法進行求解。這些研究進一步豐富了針對AutoStore系統的研究內容，為研究該系統中的訂單揀選策略提供了更多的可行策略選擇。

然而，針對具體的AutoStore系統訂單分批問題，現有文獻尚未進行過系統性的方法設計。基于上述研究背景，本文以最大化單個批次內的訂單相似度為目標，構建了混合整數線性規劃模型求解最優訂單分批策略，同時，由于訂單分批問題已被證明是NP-hard問題，因此本文設計了基于層次聚類的啟發式算法對大規模問題進行求解。針對不同問題規模設置了多組算例對算法進行計算實驗，實驗結果證明本文所提出的算法對不同規模的問題都能在短時間內求得較優可行解，證明了本文所提算法的可行性和有效性。

1 問題描述

本文的問題描述為：在存有多種貨物的AutoStore系統中，每個料箱中存儲有m個種類貨物，每個種類貨物存儲量為n。現需要對一批訂單進行揀貨，共包含O個小訂單，每個訂單共包含G個貨物種類，每個種類需求q個貨物。現在需要將這一批訂單分為多個波次安排揀貨指令，每個波次的分批依據為訂單相似度R，即不同訂單包含的相同種類貨品數量；以訂單i， j為例，q代表訂單種類k的貨物數量，那么訂單間的相似度為：

式（1）說明了相似度的計算公式，即對兩個訂單中同時包含的貨物種類而言，總需求數量較小的即為這兩組訂單間的相似度。本文目標是使具有高相似度的訂單被分配在相同波次內，即最大化同一訂單波次內相同種類貨物的數量，從而將盡可能少地檢索相同種類貨物，提高系統揀貨效率。

2 組合優化模型

2.1 問題假設。為構建模型作如下假設：（1）所有訂單都具有相同的重要性，不考慮優先處理某些訂單；（2）同一訂單不能拆分；（3）已知各料箱中的貨品信息，包括貨物種類和各種類存貨數量；（4）倉庫里貨品數量充足，不考慮補貨。

2.2 模型構建。本文模型中的符號和含義如表1所示，以W為目標函數值，旨在最大化同一訂單波次內相同種類貨物的數量，據此建立如下混合整數線性規劃模型：

式（3）表示每個訂單只能被分配一次；式（4）表示每個波次訂單數不超過最大訂單數量；式（5）規定了變量的取值范圍。

3 算法設計

3.1 算法思想。訂單排序問題已被證明為NP-hard問題，為了對該問題進行快速求解，本文基于層次聚類算法，以最大化單個批次內的訂單相似度為目標設計了啟發式算法HC，旨在縮小搜索空間并更快地求得近似最優解。

層次聚類是一種無需預先指定聚類數量的聚類算法，它通過將數據點逐步合并成聚類簇來生成層次化的聚類結構。該算法的基本運行方式為：在算法開始時，每個數據點都被視為一個單獨的簇。隨后基于某種相似度度量，將最相似的兩個簇合并為一個簇。這個過程會一直重復，直到所有數據點最終合并為一個簇或滿足某些其他的終止條件。

3.2 算法規則

3.2.1 解的編碼方式。本文使用字典對每個訂單編碼，包括訂單編號、貨物種類數、每個種類的貨品數量，例如一個編號為2，包含兩個貨物種類的訂單為：

'ID'：3， 'items'： 2：1， 5：3 （6）

式（6）表示了一個編號為“3”，包含1個種類“2”貨物、3個種類“5”貨物的訂單。

在目標解中將所有訂單構成一個訂單列表，包含所有訂單的編號，例如：

0，1，3， 2，4 （7）

式（7）中描述了一組將五個訂單分為兩個波次的解，其中：編號為0，1，3的三個訂單為一個波次，編號為2，4的兩個訂單為另一個波次。

3.2.2 算法流程。算法的完整求解過程如下：

Step1：初始化數據。初始化訂單數據，生成一批包含G個貨物種類的初始訂單，包括O個訂單，每個訂單有g個貨物種類，每個種類需求q個貨物。初始化簇。

Step2：計算關聯矩陣。根據訂單之間的相似度，計算出一個關聯矩陣R。其中R表示第i個訂單和第j個訂單之間的相似度。

Step3：計算距離矩陣。根據關聯矩陣R計算距離矩陣D，D中的每個元素表示簇之間的距離。距離矩陣初始化為最大關聯值減去關聯矩陣R，并將對角線元素設置為正無窮。

Step4：迭代合并簇。找到距離矩陣D中距離最近的兩個簇，然后將它們合并成一個簇。刪除被合并的第二個簇。更新距離矩陣D，刪除對應的行和列。重復以上步驟，不斷減少簇的數量，如果某次合并操作會導致某個聚類的大小超過P，則該次合并會被跳過，直到達到停止條件，即總的簇數量不大于最大波次數K，且每個波次中訂單數量不超過最大訂單數P。

Step5：輸出結果。輸出合并后的簇列表，這些簇即為分批后的各批次所包含訂單。

4 數值實驗

為了測試模型對不同規模大小訂單的性能表現，本文利用Python3.10調用Gurobi求解器對模型進行求解，在Windows11的環境中運行，計算機配置Intel Core i7-12700H@2.30GHz，RAM16.0GB。

4.1 實驗示例。如圖2所示，以一組共包含5個種類的10個訂單為例。其中每個訂單包含g個種類貨物，符合均值為2的幾何分布；每個種類需求q個貨物，q為1到10間的隨機值，共分為兩個訂單批次。圖3繪制了該問題的聚類譜系圖。

4.2 實驗結果。對不同規模的算例求解結果如表2所示。標題中O表示總訂單數量，G表示總貨物種類數，K表示訂單波次數，W表示單個訂單波次內相同種類貨物數量平均所占總貨物數量的比值，T表示CPU計算時間（單位：秒）。

實驗結果顯示，對于所有參數組合，HC均能在短時間內求出可行解。對于同等規模訂單算例而言，針對不同訂單分批數，訂單分批數越多，每個訂單波次內相同種類貨物數量平均所占總貨物數量的比值W越低，但CPU計算時間也能得到明顯降低。對于相同分批次數而言，W值并不單純隨著訂單數量增大和包含貨物種類數量增多而產生明顯變化，僅僅與總貨物種類數和訂單總數的比值有關。觀察數據可知，當訂單所分批次和訂單數量一定時，隨著總貨物種類數和訂單總數的比值增加，W值不斷降低，CPU計算時間不斷增加。

因此，從最大化單個批次內訂單相似度的角度而言，為了最大化同一訂單波次內相同種類貨物的數量，將訂單進行較少的分批是更好的決策。但是，在分批數較多的情況下，每個訂單波次也能有至少70%的訂單相似度，且求解時間大大降低，對于更大規模的訂單綜合考慮，將訂單進行較多的分批也是一種可行策略。

5 結 論

本文旨在研究AutoStore系統中的訂單分批問題，以最大化單個批次內的訂單相似度為目標，設計了混合整數線性規劃模型，并設計了基于層次聚類算法的啟發式算法HC。為驗證算法的實用性和有效性，本文設計了一系列不同規模的算例針對所提出的算法進行實驗。實驗結果表明，無論是小規模還是大規模的問題，算法HC總能在短時間內求得較優可行解。結果發現在分批數一定時，訂單相似度并不單純與訂單規模大小有關，主要與貨物種類的總數與貨物數量之間的比率有關。當訂單規模固定時，選擇較小的分批數量可以進一步提高訂單之間的相似度。

綜上所述，本文為AutoStore系統的訂單分批問題提出了一種新的訂單分批策略，并設計了一種能在短時間內求得較優解的啟發式算法，該算法在各種規模的問題上都有出色的表現，為現實場景中的訂單調度提供了新的參考方案。然而，本文仍有一定的局限性，由于在研究問題時為方便求解對問題做出了一定的簡化，忽略了一些實際操作中可能存在的約束，例如訂單的優先級和完成時間限制。未來的研究可以在本文研究基礎上加入這些限制條件，使問題更加接近實際的操作場景，從而進一步提高算法在現實應用中的適應性和準確性。

參考文獻：

[1] 周濟. 智能制造——“中國制造2025”的主攻方向[J]. 中國機械工程，2015，26（17）：12.

[2] XU L D， XU E L， LI L. Industry 4.0： State of the art and future trends[J]. International Journal of Production Research， 2018，56（8）：2941-2962.

[3] BOYSEN N， DE KOSTER R， WEIDINGER F. Warehousing in the e-commerce era： A survey[J]. European Journal of Operational Research， 2019，277（2）：396-411.

[4] M W PVL. An in-depth review of automated split case picking technology for distribution centers[EB/OL]. （2019）[2023-09-05]. https：//mwpvl.com/html/swisslong autostore veview.html.

[5] BECKSCH?FER M， MALBERG S， TIERNEY K， et al. Simulating storage policies for an automated grid-based warehouse system[C] // Computational Logistics： 8th International Conference， ICCL 2017， Southampton， UK， October 18-20， 2017， Proceedings 8， 2017：468-482.

[6] SWISSLOG. AutoStore： Space saving storage and order picking system for small parts[EB/OL]. （2021）[2023-09-05]. https：

//www.swisslog.com/en-us/products-systems-solutions/asrs-automated-storage-retrieval-systems/autostore-integrator.

[7] WINKELHAUS S， ZHANG M， GROSSE E H. Hybrid order picking： A simulation model of a joint manual and autonomous order picking system[J]. Computers Industrial Engineering， 2022，167：107981.

[8] 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.

[9] XIE L， THIEME N， KRENZLER R， et al. Introducing split orders and optimizing operational policies in robotic mobile fulfillment systems[J]. European Journal of Operational Research， 2021，288（1）：80-97.

[10] 吳瑩瑩. AutoStore系統優化調度研究[D]. 西安：陜西科技大學，2021.

[11] SWISSLOG. 瑞仕格AutoStore落戶上海為智慧用水打造物流之樞[J]. 現代制造，2021（11）：2.

[12] PETERSEN C G， AASE G J I J O P E. A comparison of picking， storage， and routing policies in manual order picking[J]. Production Economics， 2004，92（1）：11-19.

[13] HENN S， SCHMID V J C， ENGINEERING I. Metaheuristics for order batching and sequencing in manual order picking systems[J]. Computers & Industrial Engineering， 2013，66（2）：338-351.

[14] 王旭坪，張珺，易彩玉. B2C電子商務環境下訂單揀選與配送聯合調度優化[J]. 中國管理科學，2016，24（7）：101-109.

[15] 王轉，裴澤平. 啟發式路徑下節約里程的訂單分批算法[J]. 計算機工程與應用，2018，54（8）：203-209.

[16] ZOU B P， DE KOSTER R， XU X H. Operating policies in robotic compact storage and retrieval systems[J]. Transportation Science， 2018，52（4）：788-811.

[17] 楊瑋，張子涵，張曉楠，等. 新型無人倉AutoStore的貨物合箱方法研究[J]. 包裝工程，2022，43（17）：174-183.