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

王 杰 馬廷偉 劉 兵 孟龍

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

一、引言

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

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

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

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

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

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

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

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

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

1.訂單任務(wù)?；?/p>

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

2.AGV資源?；?/p>

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

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

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

Qu：為s揀選臺(tái)對(duì)q貨架商品的需求量

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

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

(1)

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

四、總結(jié)

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