整數(shù)規(guī)劃

建立數(shù)學(xué)模型,從全局角度出發(fā),一次性為多個(gè)任務(wù)分配多輛車。以下為一種經(jīng)典的任務(wù)-運(yùn)力匹配模型:

其中 表示機(jī)器人被指派去取貨架,表示機(jī)器人距離貨架的距離，我們可以將問題中約束松弛為，求解松弛后的問題可以直接得到整數(shù)最優(yōu)解．通過求解上述多對(duì)多指派問題獲得多個(gè)機(jī)器人和任務(wù)之間的匹配關(guān)系，從全局角度進(jìn)行整體優(yōu)化，降低系統(tǒng)總搬運(yùn)成本。該模型簡化了搬運(yùn)成本，以及特定AGV執(zhí)行特定任務(wù)的成本，且不考慮業(yè)務(wù)上的復(fù)雜約束。

考慮業(yè)務(wù)約束下匹配

在多對(duì)多模式下，如果考慮跨運(yùn)力組、運(yùn)力配比或自定義約束等等，則需將相應(yīng)信息加入模型中，例如考慮運(yùn)力配比的情形，令表示第個(gè)AGV執(zhí)行第種任務(wù)，可添加約束及來限制第種任務(wù)的配比。

以上兩種模式并無絕對(duì)好壞之分,一般來說一堆多模式原理簡單,開發(fā)維護(hù)容易,計(jì)算開銷較小,但不保證全局最優(yōu);多對(duì)多模式相對(duì)復(fù)雜,且計(jì)算開銷較大,但解的最優(yōu)性更好。

搬運(yùn)任務(wù)分發(fā)

搬運(yùn)成本

一般來說,搬運(yùn)任務(wù)的起訖點(diǎn)在下發(fā)任務(wù)時(shí)就已確定,因此某個(gè)指定運(yùn)力執(zhí)行某個(gè)指定搬運(yùn)任務(wù)的成本可以明確地定義。常見的定義方式包括搬運(yùn)距離、搬運(yùn)時(shí)間。

考慮到倉內(nèi)AGV的行駛方向一般為二維平面的水平、垂直兩個(gè)正交方向,常見的距離定義方式包括歐式距離或曼哈頓距離,該定義方式較為簡單。

另一種更精確的方法為調(diào)用路徑規(guī)劃算法(等)，計(jì)算AGV→任務(wù)起點(diǎn)→任務(wù)終點(diǎn)的最短路徑的完整距離。

該方法尤其適用于路網(wǎng)中存在單向路的情形?？紤]到實(shí)時(shí)計(jì)算成本較高,可將地圖中所有完整路徑的距離存儲(chǔ)下來,直接查詢即可。在考慮路線擁堵的情況下,可根據(jù)地圖熱點(diǎn)信息為每條邊定義不同成本。搬運(yùn)距離和搬運(yùn)時(shí)間可以相互轉(zhuǎn)化,例如對(duì)于完整路徑內(nèi)的每一段直線路徑,可根據(jù)AGV的加速度信息,求出基于速度規(guī)劃的行駛時(shí)間,并為每個(gè)轉(zhuǎn)彎行為加入轉(zhuǎn)彎時(shí)間。

搬運(yùn)任務(wù)分發(fā)

任務(wù)執(zhí)行

對(duì)于以掛載任務(wù)隊(duì)列或多中轉(zhuǎn)點(diǎn)任務(wù)的情形,為使機(jī)器人可以執(zhí)行任務(wù),還需要確定任務(wù)涉及的順序問題,具體來說包括:

如果存在多個(gè)中轉(zhuǎn)點(diǎn)或者目的點(diǎn),需要確定他們之間到達(dá)服務(wù)順序；

如果采用任務(wù)隊(duì)列模式,需要確定多任務(wù)之間的執(zhí)行順序.確定執(zhí)行順序在不同場景下方式不盡相同,主要考慮因素包括距離和工作站當(dāng)時(shí)負(fù)載情況等。

下面我們通過對(duì)一些具體問題場景的討論來進(jìn)行闡述。

每個(gè)機(jī)器需要指派一個(gè)或多個(gè)搬運(yùn)任務(wù),并且需要確定每個(gè)機(jī)器人分別需要搬運(yùn)的貨架以及搬運(yùn)順序,使得所有機(jī)器人總搬運(yùn)距離最短或者使得所有任務(wù)的完成時(shí)間最短。

在這一場景下任務(wù)的指派和順序的確定是通過求解一個(gè)變種車輛路徑問題(VRP) 同時(shí)確定的。而對(duì)于上一節(jié)介紹的揀選支持機(jī)器人系統(tǒng),確定機(jī)器人對(duì)揀選點(diǎn)(也就是多個(gè)中轉(zhuǎn)點(diǎn)) 的前往順序可以抽象為一個(gè)在倉儲(chǔ)路網(wǎng)結(jié)構(gòu)下的經(jīng)典旅行商問題(Traveling Salesman Problem,TSP) 或其變種問題,通過最小化行駛路徑長度確定各個(gè)揀選點(diǎn)的到達(dá)順序。

在搬運(yùn)機(jī)器人場景下,可能多個(gè)工作站都需求同一個(gè)貨架上的物品,也就是一條搬運(yùn)任務(wù)有多個(gè)目的地的情況。雖然可以通過TSP類方法確定各個(gè)工作站的到達(dá)順序從而最小化整體搬運(yùn)距離,但同時(shí)還需要根據(jù)工作站當(dāng)時(shí)的任務(wù)負(fù)載情況進(jìn)行調(diào)整,可以優(yōu)先前往相對(duì)需求急迫或者當(dāng)前較空閑的工作站,減少工作站的等待,雖然會(huì)增加一部分搬運(yùn)成本但是可以提高整體系統(tǒng)作業(yè)效率。

搬運(yùn)任務(wù)分發(fā)

評(píng)價(jià)及靈敏度分析

任務(wù)分配和執(zhí)行的策略會(huì)依據(jù)不同場景不同需求而有所不同,而在同一場景下面對(duì)同樣的業(yè)務(wù)需求,通常也會(huì)有多種不同的調(diào)度策略可供選擇,即便同一種策略也會(huì)因?yàn)椴煌膬?nèi)置參數(shù)選擇而產(chǎn)生不同表現(xiàn),現(xiàn)實(shí)中通常很難完全確定某一單一環(huán)節(jié)如何影響整體系統(tǒng)生產(chǎn)效率。

盡管如此,通過對(duì)一些特定統(tǒng)計(jì)量的分析,我們也可以大致了解策略對(duì)系統(tǒng)性能的影響。對(duì)于本節(jié)所介紹的搬運(yùn)任務(wù)分配和執(zhí)行,在訂單揀選場景例如揀選和揀選支持機(jī)器人系統(tǒng),可用若干用于評(píng)價(jià)調(diào)度策略性能的統(tǒng)計(jì)量,其中包括:

1. 訂單生產(chǎn)效率:一定時(shí)間內(nèi)生產(chǎn)完成訂單數(shù)量與接受訂單數(shù)量的比例

2. 響應(yīng)時(shí)間:任務(wù)等待機(jī)器人執(zhí)行的時(shí)間與機(jī)器人空駛時(shí)間之和

3. 生產(chǎn)時(shí)間:訂單在系統(tǒng)中生產(chǎn)的時(shí)間

4. 機(jī)器人平均利用率:機(jī)器人執(zhí)行任務(wù)的時(shí)間(包括空駛和滿載時(shí)間與總時(shí)間的比值)

現(xiàn)實(shí)生產(chǎn)系統(tǒng)中還會(huì)計(jì)算和監(jiān)控更多統(tǒng)計(jì)量用于后續(xù)性能分析,其中包括工作站揀選等待時(shí)間、機(jī)器人平均搬運(yùn)距離以及搬運(yùn)任務(wù)平均耗時(shí)等。對(duì)于分揀場景,則會(huì)統(tǒng)計(jì)包裹投遞效率等。

除去上面提及的系統(tǒng)性能表現(xiàn)以外,另一方面我們還需要關(guān)注算法策略本身屬性。具體來說,隨著機(jī)器人技術(shù)的不斷普及和業(yè)務(wù)場景的不斷擴(kuò)大,系統(tǒng)中機(jī)器人數(shù)量和待處理的任務(wù)量會(huì)進(jìn)一步提升,這會(huì)使得調(diào)度問題規(guī)模變得很大,而同時(shí)業(yè)務(wù)對(duì)于系統(tǒng)的響應(yīng)可能要求很高,在這種場景下,需要算法策略有很好的計(jì)算性能。

機(jī)器人系統(tǒng)不可避免會(huì)出現(xiàn)異常故障,算法策略也需要有足夠的魯棒性可以進(jìn)行快速調(diào)整。另外,對(duì)不同時(shí)間段內(nèi)可能的不同調(diào)度目標(biāo),調(diào)度策略也需要有足夠的柔性可以滿足不同要求。總體而言,需要通過對(duì)運(yùn)營效率、計(jì)算性能、魯棒性和柔性等方面綜合對(duì)所考慮的任務(wù)調(diào)度策略進(jìn)行評(píng)價(jià)。