張國維, 吳凌云

(1.中國科學院 數(shù)學與系統(tǒng)科學研究院 應用數(shù)學研究所,管理、決策與信息系統(tǒng)重點實驗室,北京 100190; 2.中國科學院大學 數(shù)學科學學院,北京 100049)

0 引言

近年來，隨著電子商務的快速發(fā)展，電商物流面臨的壓力越來越大[1]。傳統(tǒng)倉庫采用“人到貨”的揀選模式，揀選工人需要在倉庫中來回往返穿梭，對體能的消耗比較大，揀選效率也不高。AGV(Automated Guided Vehicle，自動導引車)智能倉庫是一種基于“貨到人”揀選模式的自動化倉庫，通過AGV將貨架搬運至揀選工作站，再由揀選工人從貨架上揀選商品來完成訂單的揀選工作[2]。這種“貨到人”揀選模式可以減少揀選過程中不必要的體能支出，提高訂單揀選效率。

圖1所示為AGV智能倉庫的示意圖[3]。當一個訂單分配給一個揀選工作站時，空閑的AGV會將滿足該訂單的貨架從儲位搬運到相應的揀選工作站，排隊等待揀選工人的揀選。當一個貨架揀選完成后，AGV會將該貨架搬運至一個空閑的儲位。當一個訂單揀選完成后，該訂單可以從揀選工作站釋放，一個新訂單可以繼續(xù)分配給該揀選工作站。一個揀選工作站往往設置多個訂單槽位，使得一個揀選工作站可以同時處理多個訂單[4]。因此，將合適的訂單集合成批次訂單同時進行處理，可以極大地降低揀選成本，提高揀選效率。

圖1 AGV智能倉庫示意圖

傳統(tǒng)倉庫訂單分批問題的研究已經(jīng)比較豐富[5～7]。但這些研究成果很難直接應用到AGV智能倉庫的訂單分批問題中。目前，針對AGV智能倉庫訂單分批問題的研究還比較少。Xiang等建立了以最小化貨架搬運次數(shù)為目標的整數(shù)規(guī)劃模型，基于最大化訂單相似性得到訂單分批問題的初始解，并利用變鄰域搜索算法對初始解進行改進[8]。李珍萍等以最小化貨架搬運成本和商品揀選成本為目標，建立了AGV智能倉庫訂單分批問題的整數(shù)規(guī)劃模型，并基于加權(quán)相似度設計了貪婪求解算法[9]。以上研究一般是基于靜態(tài)批次的假定，即一個批次包含的訂單全部釋放才能分配新的訂單。此外，也有一些學者在動態(tài)批次的假定下對訂單分批問題進行研究。Boysen等將動態(tài)分批問題建模為一個排序問題，通過交替求解訂單排序和貨架排序問題來確定訂單揀選的順序和貨架訪問揀選工作站的順序[4]。但實際應用中往往很難保證貨架按照確定的順序到達揀選工作站，因此，該模型的實用性受到很大限制。Xie等從在線優(yōu)化的角度進行建模，根據(jù)揀選工作站正在揀選的訂單和已經(jīng)搬運的貨架信息來確定將哪些訂單分配到揀選工作站[10]。但該模型是從局部對訂單分批進行優(yōu)化，缺乏對全局的把控。

此外，以上的研究中還存在兩方面的不足。首先，已有研究一般假設貨架上商品的存儲數(shù)量是充足的。但在實際應用中，貨架上商品的存儲量是有限的。其次，已有研究中一般將貨架搬運次數(shù)作為目標函數(shù)。但是揀選工人從貨架上揀選商品的成本也是很重要的一部分成本。針對已有研究中的不足，本文將研究考慮商品數(shù)量和商品揀選成本的AGV智能倉庫訂單分批問題，建立訂單分批問題的數(shù)學模型，分析訂單分批問題的結(jié)構(gòu)和特點，并提出快速高效的求解算法。

1 問題描述

已知倉庫中每個貨架上存儲的商品種類和數(shù)量，待揀選訂單中包含的商品種類和數(shù)量，揀選工作站的容量(同時揀選的訂單數(shù)量的上限)。AGV智能倉庫訂單分批問題是將給定的待揀選訂單組成不同的批次，使得每個批次包含的訂單數(shù)量不超過揀選工作站的容量，并為每個批次選擇需要搬運的貨架，使得完成訂單揀選的總成本最小。

訂單揀選的成本主要包括兩方面： AGV搬運貨架的成本和揀選工人從貨架上揀選商品的成本。由于AGV智能倉庫中貨架的位置是實時變動的，貨架的移動距離不能夠準確地衡量[11,12]。為了簡化問題，我們假設每個貨架搬運一次的成本是固定的，因此，我們利用線性模型來建模貨架搬運成本。揀選工人從一個貨架上揀選兩件相同的商品比揀選兩件不同的商品的效率更高(揀選工人揀選商品的成本存在規(guī)模經(jīng)濟)，因此，我們利用固定成本和變動成本來建模揀選工人從貨架上揀選商品的成本。

2 模型構(gòu)建

為了建立AGV智能倉庫訂單分批問題的數(shù)學模型，我們定義如下符號。

(1)索引

i：商品索引,i∈I;p：貨架索引,p∈P;o：訂單索引,o∈O;b：批次索引,b∈B。

(2)參數(shù)

c1：搬運一次貨架的成本;c2：從貨架上揀選一種商品的固定成本;c3：從貨架上揀選一件商品的變動成本;C：揀選工作站的容量;Dio：訂單o中商品i的需求量;Sip：貨架p中商品i的存儲量。

(3)決策變量

wob：0-1變量，訂單o是否被分配到批次b;xpb：0-1變量，批次b是否需要搬運貨架p;yipb：0-1變量，批次b是否需要從貨架p上揀選商品i;zipb：批次b需要從貨架p上揀選商品i的數(shù)量。

根據(jù)以上符號，可以將訂單分批問題表示為一個整數(shù)規(guī)劃模型。

(1)

(11)

目標函數(shù)(1)表示極小化訂單揀選的總成本，其中第一項表示貨架搬運成本，第二項表示商品揀選的固定成本，第三項表示商品揀選的變動成本；約束條件(2)表示每個訂單恰好被分配到一個批次中；約束條件(3)表示分配到每個批次的訂單數(shù)量不超過揀選工作站的容量；約束條件(4)和(5)表示每個批次只能從選中的貨架上揀選商品；約束條件(6)表示每個批次中每種商品的揀選量恰好等于該批次所有訂單中該商品的需求總量；約束條件(7)表示每個貨架上每種商品的揀選量不超過該貨架上該商品的存儲量；約束條件(8)～(11)表示決策變量的取值范圍。

(12)

在下文中，我們使用目標函數(shù)(12)作為訂單分批模型的目標函數(shù)。

3 求解算法

求解AGV智能倉庫訂單分批問題需要解決兩個相互關聯(lián)的決策問題：決定每個批次包含哪些訂單(批次組合問題)，決定每個批次需要搬運哪些貨架(貨架選擇問題)。已有的研究中通常將這兩個決策問題分開求解：先求解批次組合問題，再求解貨架選擇問題[8,9]。已有文獻一般通過訂單的相似性作為組合批次的指標，但是，訂單相似性并不能直接反映揀選該批次需要的揀選成本。而在求解貨架選擇問題時，由于批次已經(jīng)確定，批次使用的貨架信息并不能反饋到批次組合問題來做出更好的決策。

本文針對訂單分批問題的特點，提出了一種基于訂單和貨架交替選擇的貪婪求解算法。通過交替確定每個批次中包含的訂單和需要使用的貨架，貨架選擇的信息可以及時得到反饋，從而在當前批次后續(xù)訂單選擇中做出更好的決策。

該算法的具體步驟如下：

Step1初始化當前批次b=1，已分批訂單數(shù)量n=0。

Step2如果n=|O|，轉(zhuǎn)到Step 10。如果n<|O|，從未分批的訂單中選擇一個包含商品種類最多的訂單加入到當前批次，記錄當前批次剩余空間k=C-1，令n=n+1。

Step3選出可以滿足當前批次中未滿足商品種類最多的貨架。如果可選的貨架數(shù)量大于一個，則從中隨機選出一個包含未分批訂單中商品種類最多的貨架。將選擇的貨架加入到當前批次，并更新貨架上商品的剩余數(shù)量和當前批次中未滿足的商品數(shù)量。

Step4重復Step 3直到當前批次中的商品全部被滿足。

Step5從未分批的訂單中選出所有能夠由當前批次已選擇的貨架滿足的訂單。如果可選訂單數(shù)量為零，轉(zhuǎn)到Step 7。 如果可選的訂單數(shù)量大于一個，則從中選出包含商品種類最多的訂單。如果可選的訂單數(shù)量還大于一個，則從中選出隨機選出一個與已加入當前批次的訂單包含相同商品種類最多的訂單。將選擇的訂單加入到當前批次，并更新貨架上商品的剩余數(shù)量，令k=k-1，n=n+1。

Step6重復Step 5直到?jīng)]有未分批的訂單能夠由當前批次已選擇的貨架滿足或當前批次包含的訂單數(shù)量等于揀選工作站的容量C。

Step7以概率(1-e-k)判定是否繼續(xù)向當前批次加入新訂單。如果繼續(xù)加入新訂單，則轉(zhuǎn)到Step 8；否則，轉(zhuǎn)到Step 9。

Step8從未分批的訂單中選出所有能夠由已選擇的貨架滿足至少一種商品的訂單。如果可選的訂單數(shù)量為零，轉(zhuǎn)到Step 9。 如果可選的訂單數(shù)量大于一個，則從中選出可以由已選擇的貨架滿足商品種類最多的訂單。如果可選的訂單數(shù)量還大于一個，則從中選出隨機選出一個與已加入當前批次的訂單包含相同商品種類最多的訂單。令k=k-1，n=n+1，轉(zhuǎn)到Step 3。

Step9結(jié)束當前批次，并記錄當前批次包含的訂單，需要搬運的貨架及從每個貨架上揀選商品的種類和數(shù)量，令b=b+1，轉(zhuǎn)到Step 2。

Step10結(jié)束計算，輸出每一個批次包含的訂單，需要搬運的貨架及從每個貨架上揀選商品的種類和數(shù)量。

4 算例分析

4.1 算例模擬和參數(shù)設置

算例模擬主要包含兩個步驟：貨架模擬和訂單模擬。貨架模擬確定每個貨架上存儲的商品種類和數(shù)量，訂單模擬確定每個訂單包含的商品種類和數(shù)量[3,10]。貨架模擬：每個貨架包含8個貨位，每個貨位可以存儲一種商品。每種商品在一個貨架上的存儲量為區(qū)間[1,20]的一個隨機整數(shù)。每個貨架上存儲的商品從所有商品中隨機選擇。訂單模擬：商品的需求頻率服從參數(shù)為2/|I|的幾何分布。包含一種，兩種，三種商品的訂單的概率分別為0.5，0.25和0.25。訂單中每一種商品的需求量為1或2，概率分別為0.9和0.1。

根據(jù)商品種類數(shù)量，貨架數(shù)量和訂單數(shù)量的不同，我們將模擬算例設置為小規(guī)模，中規(guī)模和大規(guī)模三種不同規(guī)模。不同規(guī)模算例的參數(shù)設置如表1所示。

表1 不同規(guī)模算例的參數(shù)設置

4.2 算例結(jié)果

為了驗證本文提出的貪婪算法的有效性，分別將該算法與CPLEX求解器和文獻[9]中提出的基于相似性的分批算法進行對比，分析其求解質(zhì)量和求解速度。文獻[9]中的訂單分批模型中并未考慮商品數(shù)量，因此，我們利用本文提出的貪婪算法的Step 3和Step 4為每個批次選擇相應的貨架。此外，根據(jù)文獻[9]的結(jié)論，我們將基于商品的訂單相似度的權(quán)重設置為c2/(c1+c2)，將基于貨架的訂單相似度的權(quán)重設置為c1/(c1+c2)。

本文的算法是利用Python進行編程，在AMD R5-3600處理器的Windows電腦上運行的。本文使用CPLEX V12.10，設置最大運行時間設置為600秒。本文提出的貪婪算法和基于相似性的分批算法分別運行100次，取100次中得到的最好的解，以下結(jié)果展示中均為算法運行100次的總時間。

對于小規(guī)模算例，我們分別采用CPLEX求解器、基于相似性的分批算法和本文提出的貪婪算法進行求解。求解結(jié)果如表2所示。對于CPLEX求解器，我們展示了求解結(jié)果和運算時間；對于基于相似性的分批算法，我們還展示了該算法求解結(jié)果相對于CPLEX求解結(jié)果的誤差百分比；對于本文提出的貪婪算法，我們也展示了該算法相對于基于相似性的分批算法的求解結(jié)果下降百分比。

表2 小規(guī)模算例的求解結(jié)果

根據(jù)表2可知，對于小規(guī)模算例，當訂單數(shù)量為30的時候，CPLEX可以得到精確最優(yōu)解，而當訂單數(shù)量為60的時候，CPLEX在設置的最大運行時間內(nèi)無法得到精確最優(yōu)解。相對于CPLEX的求解時間，基于相似性的分批算法和本文提出的貪婪算法具有明顯的優(yōu)勢：基于相似性的分批算法的平均運算時間為3.14秒，本文提出的貪婪算法的平均運算時間為1.35秒。由于基于相似性的貪婪算法需要計算任意兩個訂單之間的相似性，因此，該算法的計算復雜度較高，運算時間也比本文提出的貪婪算法要長。相對于CPLEX的求解結(jié)果，基于相似性的分批算法的誤差百分比基本都在10%以上，平均誤差百分比為19.8%；而本文提出的貪婪算法的誤差百分比均不超過10%，平均誤差百分比為5.38%。相對于基于相似性的分批算法，本文提出的貪婪算法的平均下降百分比約為11.84%。

對于中規(guī)模和大規(guī)模算例，我們采用基于相似性的分批算法和本文提出的貪婪算法進行求解。求解結(jié)果如表3和表4所示。

表3 中規(guī)模算例的求解結(jié)果

表4 大規(guī)模算例的求解結(jié)果

根據(jù)表3和表4可知，隨著問題規(guī)模的增加，基于相似性的分批算法和本文提出的貪婪算法的運算時間有所增加，尤其是基于相似性的分批算法，求解大規(guī)模算例的運算時間都超過了100秒。相比于基于相似性的分批算法，本文提出的貪婪算法在運算時間上仍然有較大的優(yōu)勢。在本文中，兩個算法的運算時間為運行100次的時間，但是在實際應用中，可以調(diào)整算法運行的次數(shù)來平衡算法的運算時間和求解質(zhì)量。此外，本文提出的貪婪算法可以在不同的CPU核心、不同的機器上并行運算，因此，算法的運行次數(shù)可以更加靈活地進行調(diào)整。

對于中規(guī)模和大規(guī)模算例，本文提出的貪婪算法的求解結(jié)果相對于基于相似性的分批算法下降的百分比的平均值分別為8.97%和4.07%，與小規(guī)模算例的結(jié)果相比有所下降。我們認為產(chǎn)生這種現(xiàn)象的主要原因是隨著商品種類的增加，算例模擬時可以產(chǎn)生的訂單商品組合呈指數(shù)級增長，而算例模擬的訂單數(shù)量并沒有大幅度增加，因此，訂單之間的差異較大，通過訂單分批來提高揀選效率的能力降低。在實際應用中，雖然倉庫中的商品種類很多，但實際的訂單種類是遠遠小于商品種類的組合數(shù)，因此，本文提出的貪婪算法在實際應用中的效果會更好。

此外，我們還發(fā)現(xiàn)，當c2取值較小時，下降百分比相對較大；而當c2取值較大時，下降百分比相對較小。產(chǎn)生這種情況的主要原因是隨著c2取值的增加，商品揀選成本在總成本中的比重增加。本文提出的貪婪算法認為減少貨架搬運次數(shù)的優(yōu)先級高于減少商品揀選次數(shù)的優(yōu)先級，不會因為c2取值的不同而改變；而基于相似性的貪婪算法中的訂單相似度會根據(jù)取值的不同而改變，能夠在一定程度上對貨架搬運成本和商品揀選成本進行權(quán)衡。因此，在c2取值較大時，本文提出的貪婪算法的優(yōu)勢會相對降低。但是在實際應用中，c2往往是遠大于c1的，因此，本文提出的貪婪算法在實際應用中會有更好的效果。

4.3 考慮商品揀選成本的有效性

表5 不同商品揀選固定成本下小規(guī)模算例的模型求解結(jié)果和實際揀選成本

5 結(jié)論

訂單分批問題是基于“貨到人”揀選模式的AGV智能倉庫訂單揀選過程中一個關鍵的決策問題，對訂單揀選效率有極大的影響。本文研究了考慮商品數(shù)量和商品揀選成本的AGV智能倉庫訂單分批問題，建立了以極小化貨架搬運成本和商品揀選成本為目標的整數(shù)規(guī)劃模型，并設計了快速高效的貪婪求解算法。本文提出的模型考慮了商品數(shù)量和商品揀選成本，相比于已有研究中的訂單分批模型更符合實際情況，增加了模型的實用性。針對訂單分批問題的結(jié)構(gòu)和特點，本文提出了一種基于訂單和貨架交替選擇的貪婪求解算法。通過訂單和貨架的交替選擇，可以做出更合理的決策，從而達到更好的求解效果。通過不同規(guī)模的算例對本文提出的貪婪算法進行了分析，結(jié)果表明，相對于CPLEX求解器，本文提出的貪婪算法求解結(jié)果的誤差百分比約為5.38%，相對于基于相似性的分批算法，本文提出的貪婪算法在運算時間和解的質(zhì)量上都有明顯的優(yōu)勢。對比不考慮商品揀選成本的訂單分批模型，本文提出的模型可以大幅度降低商品的揀選次數(shù)。此外，即使實際中商品揀選的固定成本相對于貨架搬運成本小很多時，仍然不能忽略商品揀選成本。

在實際應用中，AGV智能倉庫包含多個不同的揀選工作站，如何有效地將這些批次分配到不同的揀選工作站，有待未來進一步的研究。此外，如何確定批次的揀選順序，也是未來的一個重要研究方向。