基于訂單相似度的AutoStore系統(tǒng)訂單分批問題研究

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

關(guān)鍵詞：AutoStore倉儲(chǔ)系統(tǒng)；訂單分批；混合整數(shù)規(guī)劃模型；啟發(fā)式算法；聚類算法

中圖分類號：F253.9 文獻(xiàn)標(biāo)志碼：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》國家發(fā)展戰(zhàn)略中明確指出，為促使我國工業(yè)制造產(chǎn)能提升，需要進(jìn)一步推進(jìn)智能物流發(fā)展[1]。在這一戰(zhàn)略導(dǎo)向下，眾多電商企業(yè)將物聯(lián)網(wǎng)（IoT）和人工智能（AI）等前沿技術(shù)投入到智能物流設(shè)備和系統(tǒng)的研發(fā)中，以提升物流的自動(dòng)化和智能化程度[2]。其中一種成果為AutoStore系統(tǒng)，這是一種高度自動(dòng)化、智能化且儲(chǔ)存密度極高的系統(tǒng)[3]。如圖1所示，AutoStore通過縱向堆疊最多十五個(gè)規(guī)格相同的標(biāo)準(zhǔn)儲(chǔ)物箱來構(gòu)建儲(chǔ)存堆垛，并將這些堆垛連接組成一個(gè)空間利用率極高的儲(chǔ)存系統(tǒng)[4]。該系統(tǒng)中可以通過放置隔板，將料箱內(nèi)部分隔成不同的小區(qū)域，從而在同一個(gè)料箱中存儲(chǔ)多個(gè)種類貨品[5]。

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

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

訂單揀選效率的提高是現(xiàn)代物流和供應(yīng)鏈管理中的關(guān)鍵問題，為進(jìn)一步提高訂單揀選效率，通?？梢圆捎糜唵畏峙牟呗浴Ｋ暮诵睦砟钍菍⒑邢嗤N類貨物的多個(gè)訂單集中在同一個(gè)波次中進(jìn)行處理?，F(xiàn)階段，國內(nèi)外許多學(xué)者針對不同智能倉儲(chǔ)系統(tǒng)對該問題進(jìn)行過深入研究。Petersen et al.[12]的研究表明，在人工揀選系統(tǒng)中，對于小批量訂單進(jìn)行訂單分批能顯著節(jié)省總成本。這為訂單分批的實(shí)際應(yīng)用提供了可靠的數(shù)據(jù)支持，證明了該策略的有效性。Henn et al.[13]則通過設(shè)計(jì)啟發(fā)式算法來進(jìn)行訂單的分批和排序，進(jìn)一步減少訂單的延遲時(shí)間。此外，王旭坪等[14]提出了一種旨在最小化訂單處理時(shí)間的非線性揀選與配送聯(lián)合調(diào)度模型，通過數(shù)值實(shí)驗(yàn)?zāi)M結(jié)果分析，發(fā)現(xiàn)這一模型對問題的處理能力更加全面，可以應(yīng)對更加復(fù)雜的揀貨場景。王轉(zhuǎn)[15]針對電商配送中心的實(shí)際情況，更深入地探討了訂單分批在現(xiàn)實(shí)場景中的應(yīng)用，綜合考慮揀貨工具和貨品包裝的體積，構(gòu)建了以最大化節(jié)約搬運(yùn)里程為目標(biāo)的訂單分批求解模型。

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

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

1 問題描述

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

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

2 組合優(yōu)化模型

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

2.2 模型構(gòu)建。本文模型中的符號和含義如表1所示，以W為目標(biāo)函數(shù)值，旨在最大化同一訂單波次內(nèi)相同種類貨物的數(shù)量，據(jù)此建立如下混合整數(shù)線性規(guī)劃模型：

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

3 算法設(shè)計(jì)

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

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

3.2 算法規(guī)則

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

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

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

在目標(biāo)解中將所有訂單構(gòu)成一個(gè)訂單列表，包含所有訂單的編號，例如：

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

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

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

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

Step2：計(jì)算關(guān)聯(lián)矩陣。根據(jù)訂單之間的相似度，計(jì)算出一個(gè)關(guān)聯(lián)矩陣R。其中R表示第i個(gè)訂單和第j個(gè)訂單之間的相似度。

Step3：計(jì)算距離矩陣。根據(jù)關(guān)聯(lián)矩陣R計(jì)算距離矩陣D，D中的每個(gè)元素表示簇之間的距離。距離矩陣初始化為最大關(guān)聯(lián)值減去關(guān)聯(lián)矩陣R，并將對角線元素設(shè)置為正無窮。

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

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

4 數(shù)值實(shí)驗(yàn)

為了測試模型對不同規(guī)模大小訂單的性能表現(xiàn)，本文利用Python3.10調(diào)用Gurobi求解器對模型進(jìn)行求解，在Windows11的環(huán)境中運(yùn)行，計(jì)算機(jī)配置Intel Core i7-12700H@2.30GHz，RAM16.0GB。

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

4.2 實(shí)驗(yàn)結(jié)果。對不同規(guī)模的算例求解結(jié)果如表2所示。標(biāo)題中O表示總訂單數(shù)量，G表示總貨物種類數(shù)，K表示訂單波次數(shù)，W表示單個(gè)訂單波次內(nèi)相同種類貨物數(shù)量平均所占總貨物數(shù)量的比值，T表示CPU計(jì)算時(shí)間（單位：秒）。

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

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

5 結(jié) 論

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

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

參考文獻(xiàn)：

[1] 周濟(jì). 智能制造——“中國制造2025”的主攻方向[J]. 中國機(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系統(tǒng)優(yōu)化調(diào)度研究[D]. 西安：陜西科技大學(xué)，2021.

[11] SWISSLOG. 瑞仕格AutoStore落戶上海為智慧用水打造物流之樞[J]. 現(xiàn)代制造，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電子商務(wù)環(huán)境下訂單揀選與配送聯(lián)合調(diào)度優(yōu)化[J]. 中國管理科學(xué)，2016，24（7）：101-109.

[15] 王轉(zhuǎn)，裴澤平. 啟發(fā)式路徑下節(jié)約里程的訂單分批算法[J]. 計(jì)算機(jī)工程與應(yīng)用，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.