竇 洽

(武昌職業(yè)學(xué)院,湖北 武漢 430200)

1 多搬運(yùn)機(jī)器人研究現(xiàn)狀

搬運(yùn)機(jī)器人是工業(yè)機(jī)器人的一種,能夠?qū)ψ鳂I(yè)做自動(dòng)化搬運(yùn)。 當(dāng)這種搬運(yùn)機(jī)器人里面擁有多種末端執(zhí)行器的時(shí)候,它不拘泥于某種形態(tài)對(duì)物品進(jìn)行各種作業(yè),不僅能減少大量的人力,也可以讓搬運(yùn)的效率得到提升[1]。 當(dāng)前倉(cāng)庫(kù)里面開(kāi)始出現(xiàn)各種類型的搬運(yùn)機(jī)器人,這大大提升了工作效率。

搬運(yùn)機(jī)器人已經(jīng)發(fā)展了一段時(shí)間,不少過(guò)去單個(gè)搬運(yùn)機(jī)器人所存在的問(wèn)題都已經(jīng)被解決。 當(dāng)運(yùn)用單個(gè)搬運(yùn)機(jī)器人進(jìn)行工作時(shí),通常只要對(duì)應(yīng)位置坐標(biāo),故規(guī)劃路徑較簡(jiǎn)單。 近些年來(lái),物流業(yè)務(wù)量一年比一年增加,倉(cāng)庫(kù)系統(tǒng)也擁有更多的面積,僅僅依靠單個(gè)機(jī)器人沒(méi)有辦法滿足當(dāng)下的需求。 因此,要想提升工作效率,讓工作能夠盡快完成,則需要運(yùn)用多個(gè)搬運(yùn)機(jī)器人一起運(yùn)作。 多搬運(yùn)機(jī)器人在運(yùn)作時(shí),由于有更多因素需要考慮,所以問(wèn)題也會(huì)更加復(fù)雜[1]。 搬運(yùn)機(jī)器人在運(yùn)行過(guò)程中會(huì)用到很多技術(shù),需要對(duì)任務(wù)進(jìn)行分配、規(guī)劃相應(yīng)的路徑等。 假如倉(cāng)庫(kù)里運(yùn)行的搬運(yùn)機(jī)器人不止1 個(gè)時(shí),常常會(huì)出現(xiàn)分配任務(wù)不夠均衡、路徑規(guī)劃不清晰導(dǎo)致?lián)矶碌惹闆r[2]。 故當(dāng)運(yùn)用多搬運(yùn)機(jī)器人協(xié)作的時(shí)候,最關(guān)鍵的點(diǎn)是分析與解決任務(wù)調(diào)度的問(wèn)題,只有將這一點(diǎn)解決了,才能真正實(shí)現(xiàn)協(xié)作的可能。

2 多搬運(yùn)機(jī)器人工作模式

多搬運(yùn)機(jī)器人除了擁有極強(qiáng)的收納能力,可收納較大的貨物,還擁有對(duì)貨物進(jìn)行抓取的執(zhí)行末端,能夠?qū)崿F(xiàn)揀選操作。 當(dāng)這類機(jī)器人被正式使用后,倉(cāng)儲(chǔ)的自動(dòng)化將再次得到提升[3]。 類機(jī)器人可以將不同的物料箱在同一時(shí)間段內(nèi)進(jìn)行存儲(chǔ),當(dāng)需要取貨的時(shí)候通常會(huì)選擇“夾抱式”。 通常多搬運(yùn)機(jī)器人在運(yùn)行過(guò)程中流程如下:(1)將需要機(jī)器人執(zhí)行的任務(wù)隊(duì)列進(jìn)行分配。 (2)每個(gè)機(jī)器人獲取相應(yīng)的任務(wù),然后自行移動(dòng)到該任務(wù)需要進(jìn)行的貨架旁。 (3)依據(jù)任務(wù)的不同,機(jī)器人將貨物放入儲(chǔ)物格或者是貨架中。(4)假如任務(wù)隊(duì)列依舊還有,則直接再次循環(huán)步驟2。(5)機(jī)器人移動(dòng)到分理處位置,然后對(duì)貨物進(jìn)行裝貨或者是卸貨。

圖1 HAI ROBOTICS 多搬運(yùn)機(jī)器人

當(dāng)多搬運(yùn)機(jī)器人進(jìn)行取貨的時(shí)候,它首先會(huì)移動(dòng)到分理處,并從這里出發(fā),隨后所有排隊(duì)等候的機(jī)器人領(lǐng)取各自的任務(wù)。 但這些任務(wù)的數(shù)量以及機(jī)器人的數(shù)量都是有限制的,因?yàn)楫?dāng)這兩者的數(shù)量到達(dá)某個(gè)規(guī)模時(shí),任務(wù)調(diào)度會(huì)出現(xiàn)很多問(wèn)題,以至于算法沒(méi)有辦法迅速求解。

3 多搬運(yùn)機(jī)器人任務(wù)調(diào)度建模

事實(shí)上,多搬運(yùn)機(jī)器人的任務(wù)調(diào)度問(wèn)題能夠被建模為CTSP 問(wèn)題,即把搬運(yùn)機(jī)器人當(dāng)成是CTSP 問(wèn)題里面的旅行商,而不同規(guī)格的搬運(yùn)機(jī)器人對(duì)應(yīng)不同的顏色[4]。 在當(dāng)前的科技中,CTSP 已經(jīng)能夠擁有最優(yōu)的算法。 把這種任務(wù)調(diào)度問(wèn)題之間轉(zhuǎn)換為CTSP 問(wèn)題,就可以在時(shí)間盡量短的情況下獲得更好的分配任務(wù)的方案,工作效率也能得到一定的提升。 對(duì)多搬運(yùn)系統(tǒng)機(jī)器人來(lái)說(shuō),合理、科學(xué)的任務(wù)調(diào)度不僅可以讓需要運(yùn)行的作業(yè)得到優(yōu)化,也可以降低協(xié)作的難度。

不管在哪種電商倉(cāng)庫(kù)內(nèi)都擁有各種各樣且數(shù)量多的貨物,這些貨物并沒(méi)有相同的規(guī)格、體積和形狀。不同的揀選機(jī)器人只能對(duì)應(yīng)其規(guī)格的貨物,所以要想將倉(cāng)庫(kù)里面不同規(guī)格的商品都存取完畢自然要用到很多規(guī)格的揀選機(jī)器人。 由于不同規(guī)格的貨物在進(jìn)行存取的時(shí)候需要用到不同規(guī)格的揀選機(jī)器人,因此這種任務(wù)調(diào)度也被稱作是多任務(wù)調(diào)度。

事實(shí)上,搬運(yùn)機(jī)器人所行走的路徑與任務(wù)和工作臺(tái)之間的距離是沒(méi)有任何聯(lián)系的,搬運(yùn)機(jī)器人行蹤的總路徑只與其被分配的任務(wù)序列有聯(lián)系。 如果是很多個(gè)任務(wù)被同一個(gè)搬運(yùn)機(jī)器人運(yùn)行操作時(shí),要想順利解決這些任務(wù)的分配問(wèn)題,可以通過(guò)建立模型,將其變成旅行商的問(wèn)題,再解決問(wèn)題。 在電商倉(cāng)庫(kù)中,多搬運(yùn)機(jī)器人最重要的任務(wù)調(diào)度問(wèn)題就是怎樣讓多輛搬運(yùn)機(jī)器人獲得更多的搬運(yùn)任務(wù),最終這些調(diào)度的結(jié)果應(yīng)當(dāng)是:所有的搬運(yùn)機(jī)器人都可以獲得分配,而且擁有詳細(xì)的任務(wù)序列[5]。 不過(guò),如果搬運(yùn)機(jī)器人有太多的數(shù)量,或者任務(wù)數(shù)量有很多的時(shí)候,要想盡快將這些任務(wù)進(jìn)行分配就不會(huì)很簡(jiǎn)單。 在此類情況下,可以將這種調(diào)度問(wèn)題變成全色CTSP 問(wèn)題。 以圖2 為例,能夠直觀地看出搬運(yùn)機(jī)器人的數(shù)量是3 輛,而需要分配的任務(wù)一共有8 個(gè)。 對(duì)于不同的搬運(yùn)機(jī)器人,可以給予不同的顏色,在每個(gè)任務(wù)上分配3 種顏色,即這8 個(gè)任務(wù)都能夠被搬運(yùn)機(jī)器人所接受,這3 個(gè)搬運(yùn)機(jī)器人里面的每一個(gè)機(jī)器人都可以將所有的任務(wù)全部搬運(yùn)完成。

圖2 搬運(yùn)個(gè)體與對(duì)象的CTSP 顏色表示

4 基于VNS 算法的多搬運(yùn)機(jī)器人調(diào)度求解

4.1 VNS 算法簡(jiǎn)介

VNS 是一種智能啟發(fā)算法,這種算法由國(guó)外學(xué)者提出,該算法并不需要種群進(jìn)行迭代進(jìn)化[6]。 VNS 擁有不少優(yōu)點(diǎn),例如:便于進(jìn)行操作、擁有簡(jiǎn)單的結(jié)構(gòu),而且在生產(chǎn)調(diào)度問(wèn)題以及旅行商問(wèn)題上能順利運(yùn)用。

4.2 基于VNS 算法的求解

4.2.1 貪婪初始化

VNS 算法只是對(duì)某個(gè)個(gè)體進(jìn)行初始化處理,而初始化個(gè)體的好壞能夠影響算法的性能。 在本研究中,為了得到初始解,通常會(huì)選用貪婪初始化的方式去生成。 貪婪初始化的步驟主要如下:(1)某個(gè)商人能夠隨機(jī)得到城市,且這個(gè)城市擁有多樣的顏色,而每個(gè)商人都順利到達(dá)所有需要訪問(wèn)的城市。 (2)起始城市會(huì)被商人當(dāng)成是當(dāng)前城市,而下一個(gè)城市則在剩下需要訪問(wèn)的城市里面選擇,需要遵循的原則是,下一個(gè)城市與當(dāng)前城市擁有最短的路徑,得到不同商人的貪婪城市序列。 (3)當(dāng)商人的城市序列全部完成之后,再把起始城市加到這個(gè)系列末端之后。 具體如圖3 所示,當(dāng)一個(gè)商人貪婪初始化5 個(gè)城市時(shí),其城市序列應(yīng)該為1-4-3-5-2-1。

圖3 貪婪初始化

4.2.2 抖動(dòng)操作

當(dāng)運(yùn)用VNS 算法時(shí),為了獲得更新的鄰域解,應(yīng)當(dāng)運(yùn)用抖動(dòng)的方式來(lái)持續(xù)搜索當(dāng)前領(lǐng)域的情況。 本研究為了順利進(jìn)行抖動(dòng),會(huì)選擇以下這些操作方式:貪婪重插入操作、多色城市的貪婪重插入操作等。 當(dāng)使用最后一種操作方法的時(shí)候,可以在當(dāng)前解周邊的小范圍鄰域進(jìn)行搜索。 如圖4 所示,就是運(yùn)用了多色城市的貪婪重定位操作方式,這里的商人一共有2個(gè),城市有10 個(gè)。

圖4 貪婪重定位操作

4.2.3 局部搜索操作

要想得到更加優(yōu)質(zhì)的解,對(duì)經(jīng)過(guò)抖動(dòng)而生成的新鄰域解進(jìn)行局部搜索操作就能夠得到。 如圖5 所示,就是運(yùn)用了局部搜索操作方式,這里的商人一共是2個(gè),城市是10 個(gè)。

圖5 局部搜索操作

4.2.4 2-OPT 操作

當(dāng)進(jìn)行上一步操作以后,城市序列就會(huì)有所變化。 為了優(yōu)化商人的城市序列,這篇文章選擇的操作方式是2-OPT,如圖6 所示,就是運(yùn)用了2-OPT 的操作方式,這里的城市是10 個(gè)。

圖6 2-OPT 操作示例

4.3 基于VNS 算法的求解流程

VNS 的具體流程如圖7 所示。

圖7 VNS 流程

5 算例分析

當(dāng)運(yùn)用就近原則時(shí),雖然電商倉(cāng)庫(kù)能夠更快完成目前的任務(wù),可是總耗時(shí)是沒(méi)有考慮在內(nèi)的。 雖然當(dāng)前已經(jīng)有很多CTSP 求解案例,但如果旅行商數(shù)目過(guò)多時(shí),通常是達(dá)到幾百的情況,求解將會(huì)變得很復(fù)雜,因此想要在較短的時(shí)間內(nèi)高效、科學(xué)地求解就變得比較困難[7]。 如圖8 所示,這里運(yùn)用到的搬運(yùn)機(jī)器人一共是500 個(gè),而搬運(yùn)任務(wù)有15 000 個(gè),所體現(xiàn)的調(diào)度過(guò)程圖是選擇了大規(guī)模旅行商的全色CTSP 模型。在此任務(wù)中,任務(wù)一共進(jìn)行了3 次分配,每次都是500輛搬運(yùn)機(jī)器人分5 000 個(gè)任務(wù)。 當(dāng)算力處于有限情況時(shí),任務(wù)執(zhí)行時(shí)間會(huì)小于任務(wù)調(diào)度時(shí)間,這就會(huì)讓搬運(yùn)機(jī)器人在完成任務(wù)之后出現(xiàn)等待的情況,大大降低了工作效率。 如果搬運(yùn)機(jī)器人數(shù)量過(guò)多,在達(dá)到幾百的時(shí)候,多搬運(yùn)機(jī)器人以及揀選機(jī)器人的任務(wù)調(diào)度都不適用建模成大規(guī)模CTSP 的方法。

圖8 采用大規(guī)模CTSP 模型調(diào)度

6 結(jié)語(yǔ)

當(dāng)大規(guī)模搬運(yùn)機(jī)器人在進(jìn)行任務(wù)調(diào)度時(shí),常常會(huì)出現(xiàn)求解困難的情形,為了有效、科學(xué)、合理地解決這個(gè)問(wèn)題,本研究選擇運(yùn)用CTSP 模型與分組并行策略結(jié)合在一起的方式去解決。 所謂分組并行策略,其實(shí)就是把大規(guī)模搬運(yùn)機(jī)器人轉(zhuǎn)變成小規(guī)模搬運(yùn)機(jī)器人,然后對(duì)這些分組后的機(jī)器人做并行調(diào)度[8]。 運(yùn)用此策略的過(guò)程如圖9 所示,在這個(gè)過(guò)程圖中共用到15 000 個(gè)搬運(yùn)任務(wù)及500 輛搬運(yùn)機(jī)器人。 其運(yùn)用分組并行策略的步驟如下:第一,把這500 輛搬運(yùn)機(jī)器人平分為5 個(gè)集群,每個(gè)集群都由50 輛搬運(yùn)機(jī)器人組成,同樣將15 000 個(gè)任務(wù)平分為30 個(gè)任務(wù)集,而每個(gè)任務(wù)集都由500 個(gè)任務(wù)所組成。 第二,將這些任務(wù)進(jìn)行分配,例如:1—50 號(hào)搬運(yùn)機(jī)器人將會(huì)按照順序得到1—50 號(hào)任務(wù),在得到任務(wù)后,搬運(yùn)機(jī)器人就會(huì)對(duì)得到的任務(wù)進(jìn)行執(zhí)行,而同時(shí)501—1 000 號(hào)的任務(wù)已經(jīng)被分到這50 號(hào)搬運(yùn)機(jī)器人身上,就這樣依次往后面分配8 次任務(wù)。 因?yàn)槊總€(gè)批次的搬運(yùn)機(jī)器人數(shù)量以及任務(wù)數(shù)都較少,所以在進(jìn)行任務(wù)調(diào)度時(shí)可以較快完成任務(wù)。 當(dāng)不同批次的調(diào)度被完成后,因?yàn)榘徇\(yùn)機(jī)器人集群都在完成自己被分配到的任務(wù),所以搬運(yùn)機(jī)器人對(duì)任務(wù)進(jìn)行等待的情況并不會(huì)出現(xiàn)。

圖9 采用分組并行策略調(diào)度