考慮商品數(shù)量和商品揀選成本的AGV智能倉(cāng)庫(kù)訂單分批問(wèn)題研究

張國(guó)維, 吳凌云

(1.中國(guó)科學(xué)院 數(shù)學(xué)與系統(tǒng)科學(xué)研究院 應(yīng)用數(shù)學(xué)研究所,管理、決策與信息系統(tǒng)重點(diǎn)實(shí)驗(yàn)室,北京 100190; 2.中國(guó)科學(xué)院大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,北京 100049)

0 引言

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

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

圖1 AGV智能倉(cāng)庫(kù)示意圖

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

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

1 問(wèn)題描述

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

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

2 模型構(gòu)建

為了建立AGV智能倉(cāng)庫(kù)訂單分批問(wèn)題的數(shù)學(xué)模型，我們定義如下符號(hào)。

(1)索引

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

(2)參數(shù)

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

(3)決策變量

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

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

(1)

(11)

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

(12)

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

3 求解算法

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

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

該算法的具體步驟如下：

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

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

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

Step4重復(fù)Step 3直到當(dāng)前批次中的商品全部被滿(mǎn)足。

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

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

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

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

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

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

4 算例分析

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

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

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

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

4.2 算例結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

在實(shí)際應(yīng)用中，AGV智能倉(cāng)庫(kù)包含多個(gè)不同的揀選工作站，如何有效地將這些批次分配到不同的揀選工作站，有待未來(lái)進(jìn)一步的研究。此外，如何確定批次的揀選順序，也是未來(lái)的一個(gè)重要研究方向。