粒計算在AGV任務分配中的應用研究

王 杰 馬廷偉 劉 兵 孟龍

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

一、引言

隨著智慧物流影響的逐漸擴大，移動機器人在物流中的實際應用已經成為研究重點之一。在自動化立體倉庫中，AGV小車代替人類進行揀選與搬運。因此如何使AGV更高效地完成物流活動是十分重要的研究。本文將結合一種新的概念和計算模式——粒計算，對倉庫中的任務分配環節進行優化。粒計算是一種新興的概念和計算模式，更高級地模擬了人類的思維規律，對具有重要意義。針對多任務分配問題,本文運用有關粒計算的相關理論,運用有關信息粒化的概念,提出了一種將具體任務粒化的方法，建立新的任務分配模型，以提高倉庫的工作效率。

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

基于AGV移動貨架的“貨到人”自動化倉儲系統，倉儲區由很多可移動貨架組成，每個貨架上存儲著若干種類和數量的SKU，揀選區由多個揀選臺構成，每個揀選臺配有一名揀選員，可以同時進行多個訂單揀選作業。倉儲系統中有很多AGV，用于執行貨架搬運任務。對于倉儲系統接收到的訂單，首先根據相似度進行分批，分批后的訂單分配到各揀選臺，調度系統將商品信息列表發送給揀選員，同時系統根據訂單任務指派執行任務代價低、效率高的AGV搬運貨架到揀選臺，揀選員根據商品信息列表揀選商品。

三、粒計算在AGV任務分配中的應用

(一)粒計算的國內外研究現狀

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

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

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

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

1.訂單任務粒化

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

2.AGV資源粒化

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

(三)基于粒計算的多AGV任務分配模型構建

本文通過粒計算制定的任務粒化和資源粒化方法，建立多AGV任務分配模型，以實現全部訂單揀選總時間最短的任務分配目標。設定每個組合任務指令都對應著一個貨架搬運，因此每個揀選臺的揀選任務也就是AGV將揀選臺訂單需求的若干貨架搬運至揀選臺并完成商品揀選的過程，由基于物聯網的資源粒信息可實時計算出各AGV執行各揀選臺組合任務耗時及能耗。最后，以揀選時間最短為目標，建立多AGV任務分配模型并進行求解，最終得到各揀選臺訂單任務分配結果。

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

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

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

(1)

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

四、總結

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