自動(dòng)化立體倉(cāng)中堆垛機(jī)存取貨路徑優(yōu)化問(wèn)題研究

王玉聰，何杰明，廖云飛，馮 浩

（1.天津大學(xué)管理與經(jīng)濟(jì)學(xué)部，天津 300072；2.廣東煙草惠州市有限責(zé)任公司，廣東惠州 516000；3.中國(guó)煙草總公司廣東省公司，廣東廣州 510610）

0 引言

隨著物流運(yùn)輸業(yè)的飛速發(fā)展，物流中轉(zhuǎn)、配送需求不斷增多，為了更好地滿足運(yùn)輸需求，越來(lái)越多的物流中心選擇使用先進(jìn)的機(jī)械設(shè)備來(lái)代替人力勞動(dòng)，既降低了成本，又提高了運(yùn)作效率。自動(dòng)化立體倉(cāng)是現(xiàn)代物流技術(shù)領(lǐng)域出現(xiàn)的一種新型倉(cāng)儲(chǔ)方式，其主體由貨架、巷道式堆垛起重機(jī)、出入庫(kù)工作臺(tái)和自動(dòng)運(yùn)進(jìn)運(yùn)出及操作控制系統(tǒng)組成，利用立體倉(cāng)庫(kù)設(shè)備企業(yè)實(shí)現(xiàn)了倉(cāng)庫(kù)貨位合理化、存取自動(dòng)化、操作簡(jiǎn)便化。在自動(dòng)化立體倉(cāng)庫(kù)這整個(gè)系統(tǒng)中，堆垛機(jī)的調(diào)度優(yōu)化是提高倉(cāng)庫(kù)作業(yè)效率的關(guān)鍵，因而研究自動(dòng)化立體倉(cāng)庫(kù)堆垛機(jī)的調(diào)度問(wèn)題具有重要的理論價(jià)值和現(xiàn)實(shí)意義。

1 問(wèn)題及模型

1.1 問(wèn)題描述

本文研究一個(gè)自動(dòng)化立體倉(cāng)的堆垛機(jī)路徑規(guī)劃問(wèn)題。已知某物流配送中心擁有一個(gè)2排m列n層（共m×n×2個(gè)貨位）的高層立體貨架，貨位的長(zhǎng)度為L(zhǎng)、高度為H，每個(gè)貨位可存放一個(gè)托盤(pán)，出入庫(kù)平臺(tái)設(shè)在高層立體貨架一側(cè)的底層（第0層）。該貨架的所有出入庫(kù)任務(wù)由一臺(tái)巷道堆垛機(jī)完成，其在水平方向和豎直方向的移動(dòng)速率分別為vx和vy，堆垛機(jī)每次只能搬運(yùn)一個(gè)托盤(pán)。現(xiàn)有一批待入庫(kù)和待出庫(kù)的任務(wù)單，出入庫(kù)的貨位無(wú)先后順序要求，且已知每個(gè)任務(wù)對(duì)應(yīng)的貨位坐標(biāo)。該問(wèn)題的目標(biāo)是，合理規(guī)劃堆垛機(jī)的移動(dòng)路線（即規(guī)劃所有任務(wù)的完成順序），使得堆垛機(jī)完成所有任務(wù)的總耗時(shí)最短。

1.2 模型假設(shè)

為簡(jiǎn)化模型，本文結(jié)合實(shí)際情況做出如下假設(shè)：

（1）不考慮貨架上的實(shí)際存貨情況，即默認(rèn)入庫(kù)任務(wù)所對(duì)應(yīng)的貨位為空貨位，出庫(kù)任務(wù)所對(duì)應(yīng)的貨位存有貨物。

（2）堆垛機(jī)水平和豎直方向的移動(dòng)相互獨(dú)立且均為勻速運(yùn)動(dòng)，堆垛機(jī)在兩貨位間的移動(dòng)時(shí)間取其水平和豎直方向中較長(zhǎng)的時(shí)間。

（3）不考慮堆垛機(jī)的啟動(dòng)和制動(dòng)過(guò)程，忽略裝卸貨時(shí)間。

（4）不考慮托盤(pán)（貨物）的實(shí)際大小，貨位間距即為堆垛機(jī)的移動(dòng)距離。

（5）堆垛機(jī)在同一位置，對(duì)巷道左右兩排貨位均可操作，不考慮兩排貨位間距離。

1.3 模型建立

模型建立所用符號(hào)說(shuō)明見(jiàn)表1。

表1 模型建立所用符號(hào)及說(shuō)明

模型分為單一作業(yè)模式和復(fù)合作業(yè)模式兩種。

（1）單一作業(yè)模式。單一作業(yè)模式下，堆垛機(jī)需要不斷往返于出入庫(kù)平臺(tái)與任務(wù)相對(duì)應(yīng)的貨位之間，其完成全部任務(wù)是時(shí)間隨著具體任務(wù)的確定而定，與任務(wù)的順序無(wú)關(guān)，也不存在路徑優(yōu)化問(wèn)題。堆垛機(jī)在單一作業(yè)模式下完成全部任務(wù)的總耗時(shí)為：

（2）復(fù)合作業(yè)模式。復(fù)合作業(yè)下，堆垛機(jī)可選擇依照已有的出入庫(kù)順序逐一完成任務(wù)，或?qū)θ蝿?wù)進(jìn)行重新排列，達(dá)到路徑優(yōu)化的效果。復(fù)合作業(yè)模式下的優(yōu)化模型如下：

其中，式（2）為目標(biāo)函數(shù)，表示最小化完成全部任務(wù)的總時(shí)間；式（3）、式（4）限制每個(gè)任務(wù)所對(duì)應(yīng)的貨位被訪問(wèn)一次，且出入度相等；式（5）給出了堆垛機(jī)從任務(wù)i的貨位移動(dòng)到任務(wù)j的貨位所需要的時(shí)間表達(dá)式；式（6）為決策變量的取值范圍。

2 實(shí)驗(yàn)結(jié)果

對(duì)堆垛機(jī)的作業(yè)進(jìn)行實(shí)驗(yàn)計(jì)算，使用JAVA編程，計(jì)算堆垛機(jī)單一作業(yè)模式下的總作業(yè)時(shí)間，并使用求解器求解復(fù)合作業(yè)模式下的路徑優(yōu)化模型，得到符合作業(yè)模式下的總作業(yè)時(shí)間。調(diào)用的求解器為IBM ILOG CPLEX 12.8，運(yùn)行環(huán)境為Intel（R）Core（TM）i5-6200U CPU@2.30 GHz 2.40 GHz處理器和4 GB內(nèi)存計(jì)算機(jī)。

2.1 算例及參數(shù)

根據(jù)實(shí)際情況，設(shè)貨架共包含2排42列10層的貨位，每個(gè)貨位長(zhǎng)1.5 m、高2 m，堆垛機(jī)水平方向的移動(dòng)速率為1.5 m/s，豎直方向的移動(dòng)速率為0.5 m/s。

隨機(jī)生成一批出入庫(kù)混合任務(wù)及其對(duì)應(yīng)的貨位坐標(biāo)。按照算例中出入庫(kù)任務(wù)的數(shù)量多少分為：I類(lèi)，即以入庫(kù)任務(wù)為主（入庫(kù)任務(wù)數(shù)量約為出庫(kù)任務(wù)數(shù)量的2倍）；O類(lèi)，即以出庫(kù)任務(wù)為主（出庫(kù)任務(wù)數(shù)量約為入庫(kù)任務(wù)數(shù)量的2倍）；IO類(lèi)，即均衡任務(wù)（出入庫(kù)任務(wù)數(shù)量大致相等）。算例共包含小、中、大6種規(guī)模，任務(wù)總數(shù)分別為30、100、200、300、400和500個(gè)，每種規(guī)模下包含3類(lèi)算例各10個(gè)。

2.2 實(shí)驗(yàn)結(jié)果

表2為堆垛機(jī)單一作業(yè)和復(fù)合作業(yè)兩種模式下的完成每種規(guī)模的算例任務(wù)的平均總耗時(shí)。其中，最后一列表示復(fù)合作業(yè)與單一作業(yè)相比，堆垛機(jī)耗時(shí)的減少的百分比，其計(jì)算公式為

表2 算例計(jì)算結(jié)果

圖1展示了堆垛機(jī)完算例任務(wù)總耗時(shí)，以折線圖的形式展示了復(fù)合作業(yè)較單一作業(yè)的完成任務(wù)總耗時(shí)減少百分比隨算例規(guī)模的變化趨勢(shì)。

圖1 算例計(jì)算結(jié)果

從表2和圖1可以看出，對(duì)于所有算例，堆垛機(jī)在復(fù)合作業(yè)模式下的完成任務(wù)總耗時(shí)小于單一作業(yè)模式。復(fù)合作業(yè)模式下出入庫(kù)作業(yè)的結(jié)合在很大程度上減少了堆垛機(jī)的空載移動(dòng)，有效提高了堆垛機(jī)作業(yè)效率。此外，耗時(shí)減少百分比隨算例規(guī)模的增加而增加。因此，企業(yè)應(yīng)當(dāng)盡量將出入庫(kù)任務(wù)配合起來(lái)，充分利用堆垛機(jī)的每一次移動(dòng)，尤其是當(dāng)出入庫(kù)任務(wù)量非常大時(shí)，采用優(yōu)化的復(fù)合作業(yè)模式是有必要的。

3 結(jié)論

本文研究了自動(dòng)化立體倉(cāng)中堆垛機(jī)路徑優(yōu)化的問(wèn)題，堆垛機(jī)的出入庫(kù)作業(yè)可分為單一作業(yè)和復(fù)合作業(yè)兩種模式：在單一作業(yè)模式下，對(duì)于給定的出入庫(kù)任務(wù)，堆垛機(jī)完成任務(wù)的總耗時(shí)確定值；在復(fù)合作業(yè)模式下，堆垛機(jī)可按給定的任務(wù)順序依次完成出入庫(kù)作業(yè)，或?qū)θ蝿?wù)進(jìn)行重新排列，進(jìn)而優(yōu)化移動(dòng)路徑，提高作業(yè)效率。針對(duì)兩種作業(yè)方式，本文分別給出了堆垛機(jī)完成任務(wù)的總耗時(shí)的計(jì)算方法，并針對(duì)復(fù)合作業(yè)建立了相應(yīng)的數(shù)學(xué)優(yōu)化模型，以求解最優(yōu)的路徑及對(duì)應(yīng)的總耗時(shí)。

本文隨機(jī)生成了6種規(guī)模的實(shí)驗(yàn)算例，分別對(duì)兩種作業(yè)方式下的完成任務(wù)總耗時(shí)進(jìn)行計(jì)算。計(jì)算結(jié)果表明，復(fù)合作業(yè)較單一作業(yè)而言耗時(shí)較少，復(fù)合作業(yè)帶來(lái)的耗時(shí)減少百分比隨著算例規(guī)模的增加而增加。因此，企業(yè)采用堆垛機(jī)的復(fù)合作業(yè)模式是有意義的，應(yīng)盡量將出入庫(kù)的作業(yè)配合完成，充分利用堆垛機(jī)的每一次移動(dòng)，尤其是當(dāng)出入庫(kù)任務(wù)量非常大時(shí)，這種優(yōu)化顯得尤為重要。