粒計算在AGV任務(wù)分配中的應(yīng)用研究

王 杰 馬廷偉 劉 兵 孟龍

(北京物資學(xué)院信息學(xué)院 北京 101149)

一、引言

隨著智慧物流影響的逐漸擴(kuò)大，移動機(jī)器人在物流中的實際應(yīng)用已經(jīng)成為研究重點之一。在自動化立體倉庫中，AGV小車代替人類進(jìn)行揀選與搬運(yùn)。因此如何使AGV更高效地完成物流活動是十分重要的研究。本文將結(jié)合一種新的概念和計算模式——粒計算，對倉庫中的任務(wù)分配環(huán)節(jié)進(jìn)行優(yōu)化。粒計算是一種新興的概念和計算模式，更高級地模擬了人類的思維規(guī)律，對具有重要意義。針對多任務(wù)分配問題,本文運(yùn)用有關(guān)粒計算的相關(guān)理論,運(yùn)用有關(guān)信息?；母拍?提出了一種將具體任務(wù)?；姆椒ǎ⑿碌娜蝿?wù)分配模型，以提高倉庫的工作效率。

二、基于物流 AGV 的揀選作業(yè)模式描述

基于AGV移動貨架的“貨到人”自動化倉儲系統(tǒng)，倉儲區(qū)由很多可移動貨架組成，每個貨架上存儲著若干種類和數(shù)量的SKU，揀選區(qū)由多個揀選臺構(gòu)成，每個揀選臺配有一名揀選員，可以同時進(jìn)行多個訂單揀選作業(yè)。倉儲系統(tǒng)中有很多AGV，用于執(zhí)行貨架搬運(yùn)任務(wù)。對于倉儲系統(tǒng)接收到的訂單，首先根據(jù)相似度進(jìn)行分批，分批后的訂單分配到各揀選臺，調(diào)度系統(tǒng)將商品信息列表發(fā)送給揀選員，同時系統(tǒng)根據(jù)訂單任務(wù)指派執(zhí)行任務(wù)代價低、效率高的AGV搬運(yùn)貨架到揀選臺，揀選員根據(jù)商品信息列表揀選商品。

三、粒計算在AGV任務(wù)分配中的應(yīng)用

(一)粒計算的國內(nèi)外研究現(xiàn)狀

本文主要討論其在任務(wù)調(diào)度方面的研究，因資源調(diào)度與任務(wù)分配有異曲同工之妙，故有討論的意義。前人在資源調(diào)度方面已經(jīng)有了許多研究。粒計算理論應(yīng)用到網(wǎng)格調(diào)度中，提出了一種新的層次式數(shù)據(jù)網(wǎng)格資源調(diào)度算法[2]。還有一些學(xué)者將粒計算理論引入到非實體資源的調(diào)度問題上，齊平等[4]針對云資源調(diào)度中低效率問題，基于模糊商空間思想將云端虛擬機(jī)抽象成計算單元，根據(jù)用戶服務(wù)質(zhì)量特征建立基于模糊商空間的資源分配模型。張鵬[5]將電力系統(tǒng)各個機(jī)組進(jìn)行?；?，以假想最優(yōu)調(diào)度下的機(jī)組組合狀態(tài)為目標(biāo)序列，以系統(tǒng)優(yōu)化潮流計算條件下的機(jī)組組合狀態(tài)為無限接近目標(biāo)序列的函數(shù)序列，應(yīng)用粒的相似度概念進(jìn)行此函數(shù)序列與目標(biāo)序列之間粒的相似度計算，確定出在實際中最能接近給定假想最優(yōu)調(diào)度下的目標(biāo)序列所對應(yīng)的最優(yōu)發(fā)電機(jī)組組合，從而為優(yōu)化調(diào)度決策提供重要依據(jù)。鄧一平[6]運(yùn)用有關(guān)粒計算的相關(guān)理論,運(yùn)用有關(guān)信息?；母拍?提出了一種將具體任務(wù)?；姆椒?，該方法將具體任務(wù)粒化為若干個原子任務(wù)粒空間,提出了一種基于粒計算的多Agent任務(wù)模型。本文是利用粒計算的思想對倉庫中的訂單與AGV小車進(jìn)行?；?，進(jìn)而提高出庫的效率。許多學(xué)者在調(diào)度方面的研究，將資源進(jìn)行?；鉀Q問題，說明了粒計算在調(diào)度與任務(wù)分配的可操性，對本文的研究有很大的借鑒作用。

(二)基于粒計算的多AGV任務(wù)分配研究

倉儲揀選訂單的倉庫中，一般分為訂單分解、合并訂單、任務(wù)拆分、任務(wù)組合等作業(yè)流程，經(jīng)常導(dǎo)致作業(yè)任務(wù)的“粒度”過大。而當(dāng)前客戶多處于“小批量、多批次、多品類”的訂單狀態(tài)，可能會造成資源利用率低、能源浪費(fèi)、交貨延期等問題，會對客戶滿意度和倉庫的工作效率產(chǎn)生不良影響。解決這些問題的關(guān)鍵在于將訂單轉(zhuǎn)換為適合下達(dá)作業(yè)指令的任務(wù)單元，在完成訂單揀選要求的前提下，根據(jù)系統(tǒng)特點將某些作業(yè)指令合并，盡可能減少AGV搬運(yùn)貨架的次數(shù)。

借助粒計算研究思想，首先將訂單拆分為最小作業(yè)單元——任務(wù)粒，在考慮貨架商品存儲種類特點的基礎(chǔ)上，將任務(wù)粒合并為組合任務(wù)指令，最終將訂單轉(zhuǎn)換為多個貨架搬運(yùn)任務(wù)。同時，借助物聯(lián)網(wǎng)技術(shù)實時獲取AGV的各種狀態(tài)參數(shù)，如作業(yè)狀態(tài)、運(yùn)行狀態(tài)及物理狀態(tài)等，并將其實時轉(zhuǎn)換為作業(yè)能力，在粒計算指導(dǎo)下，根據(jù)作業(yè)能力將AGV劃分成適合不同作業(yè)任務(wù)的資源粒，并根據(jù)粒的合并性，將相似的資源粒進(jìn)行合并。自動化倉儲系統(tǒng)進(jìn)行多AGV揀選任務(wù)分配時，針對某一類任務(wù)粒，優(yōu)先選擇適合該作業(yè)任務(wù)的資源粒集合中的AGV，求解時不但減小了搜索解的空間，還降低了AGV與系統(tǒng)的通訊次數(shù)，從而提高多AGV任務(wù)分配問題的求解質(zhì)量與效率。

1.訂單任務(wù)粒化

對于電商倉庫的某個訂單來說，其所包含的任務(wù)只是該倉庫某區(qū)全部訂單任務(wù)的一部分。通常情況下，一個訂單內(nèi)包含多種商品，需要搬運(yùn)多個貨架到揀選臺才能完成揀選，指派AGV搬運(yùn)某個貨架到具體的揀選臺是調(diào)度系統(tǒng)所能下達(dá)的最小作業(yè)指令，是自動化倉庫訂單能夠拆分成的最小任務(wù)。對于多AGV任務(wù)分配問題來說，自動化倉儲系統(tǒng)指派AGV搬運(yùn)貨架到目標(biāo)揀選臺是系統(tǒng)所能下達(dá)的最小作業(yè)指令，是多AGV任務(wù)分配問題的基本任務(wù)單元。在考慮貨架倉儲特點的基礎(chǔ)上，通過對基本任務(wù)單元進(jìn)行合并，最終建立揀選總時間最短的多AGV任務(wù)分配及貨架排序模型。

2.AGV資源?；?/p>

倉儲作業(yè)是動態(tài)連續(xù)的作業(yè)過程，調(diào)度系統(tǒng)的任務(wù)隊列中不斷增加新的作業(yè)任務(wù)，作業(yè)環(huán)境也在不斷變化，調(diào)度中心根據(jù)任務(wù)作業(yè)需求向倉儲系統(tǒng)中的作業(yè)設(shè)備下達(dá)作業(yè)指令。在自動化倉庫的揀選系統(tǒng)中，除傳送帶外，其他作業(yè)設(shè)備，如堆垛機(jī)、叉車、AGV、貨架等自身狀態(tài)、作業(yè)狀態(tài)、作業(yè)進(jìn)程、當(dāng)前位置、當(dāng)前載貨量以及續(xù)航時間等隨時間不規(guī)則變化。對于AGV來說，對于某一確定任務(wù)，貨架位置固定，揀選臺位置固定，不同AGV由于各種狀態(tài)的不同，執(zhí)行任務(wù)的時間成本以及能耗不同。調(diào)度系統(tǒng)的目的是在保證任務(wù)高質(zhì)量、快速完成的前提下，實現(xiàn)AGV的高效、合理調(diào)用，實時獲取AGV的各項狀態(tài)參數(shù)并計算轉(zhuǎn)化為實時作業(yè)能力，是調(diào)度系統(tǒng)實現(xiàn)智能調(diào)度的基礎(chǔ)。

(三)基于粒計算的多AGV任務(wù)分配模型構(gòu)建

本文通過粒計算制定的任務(wù)粒化和資源?；椒?，建立多AGV任務(wù)分配模型，以實現(xiàn)全部訂單揀選總時間最短的任務(wù)分配目標(biāo)。設(shè)定每個組合任務(wù)指令都對應(yīng)著一個貨架搬運(yùn)，因此每個揀選臺的揀選任務(wù)也就是AGV將揀選臺訂單需求的若干貨架搬運(yùn)至揀選臺并完成商品揀選的過程，由基于物聯(lián)網(wǎng)的資源粒信息可實時計算出各AGV執(zhí)行各揀選臺組合任務(wù)耗時及能耗。最后，以揀選時間最短為目標(biāo)，建立多AGV任務(wù)分配模型并進(jìn)行求解，最終得到各揀選臺訂單任務(wù)分配結(jié)果。

Qu：為s揀選臺對q貨架商品的需求量

pnsq：表示AGVrn被分配到s揀選臺對q貨架搬運(yùn)。

將組合作業(yè)指令與AGV資源粒進(jìn)行組合，建立一段時間內(nèi)全部訂單揀選耗時最短的多AGV任務(wù)分配模型：

(1)

其中，目標(biāo)函數(shù)(1)表示最小化訂單揀選的總耗時；約束(2)表示一臺AGV資源粒只能分配給一個揀選臺上的一個任務(wù)粒；約束(3)為變量取值約束；約束(4)表示資源粒當(dāng)前作業(yè)能力能滿足任務(wù)粒需求。

四、總結(jié)

隨著智慧物流的到來，物流逐漸向個性化、小批量、多批次方向發(fā)展。而粒計算模仿了人類看待事物多角度、多層次的思維模式，成為處理不確定的大量信息的有效方法。并且粒計算最根本的思想是通過合適粒度的選擇,來尋找問題的一種較好的、近似的解決方案,從而降低問題求解的復(fù)雜度。針對這一問題，本文分三階段構(gòu)建以搬運(yùn)時間最少的模型。第一階段：對訂單進(jìn)行合并或分解，形成大小合適的任務(wù)粒，將最小的任務(wù)粒組合成新的揀選訂單。第二階段:對機(jī)器人從性能及電量方面評估，根據(jù)粒計算構(gòu)造AGV資源粒并組合。第三階段：構(gòu)建基于粒計算的多機(jī)器人模型。本文通過粒計算的理論和方法對物流復(fù)雜問題的解決提供了新思路。如何更精確將粒計算運(yùn)用到物流作業(yè)中是一個值得思考的問題。