任務(wù)依賴

不同任務(wù)可能存在任務(wù)依賴，例如PS人工區(qū)出庫，當前工作站需要在上一個任務(wù)完成并移走托盤后，才能執(zhí)行下一個出庫搬運任務(wù)。因此出庫搬運任務(wù)依賴于對應(yīng)工作站的托盤回庫或空托回收任務(wù)。因此對于已根據(jù)優(yōu)先級生成的任務(wù)隊列，對于每一個存在依賴的任務(wù)，需要在該任務(wù)前插相應(yīng)依賴任務(wù)。

一般來說，不同任務(wù)類型存在優(yōu)先級，或者相互依賴關(guān)系，例如PS區(qū)出庫托盤拆空后，需要先將空托盤搬走，否則下一個綁定在該站點的入庫任務(wù)無法執(zhí)行。而疊托移庫任務(wù)需要先于空托回庫執(zhí)行，否則疊托占用疊托機，導(dǎo)致空托回庫任務(wù)無法執(zhí)行。

運力配比

以PS區(qū)為例，雖然出庫任務(wù)優(yōu)先級更高，但如果出庫任務(wù)較多，可能導(dǎo)致所有AGV全部執(zhí)行出庫搬運任務(wù)，造成入庫托盤在接駁點積壓，因此需預(yù)留一定配比的AGV運力只為或優(yōu)先為入庫任務(wù)服務(wù)。

容量限制

由于起始點、目的地或行駛區(qū)域的物理容量限制，需要對同一時間到達相應(yīng)地點的AGV或搬運容器實施容量限制，例如短時間內(nèi)目的站點可容納容器數(shù)、巷道可駛?cè)階GV數(shù)等。該限制條件可根據(jù)具體業(yè)務(wù)場景靈活配置。

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

AGV約束

可執(zhí)行任務(wù)類型限制

劃分運力組后，每個AGV只能執(zhí)行特定類型任務(wù)。

AGV優(yōu)先級

AGV優(yōu)先級劃分常見CTU場景，例如同一巷道內(nèi)的任務(wù)優(yōu)先分給已被分配該巷道任務(wù)的AGV，出入庫任務(wù)優(yōu)先分配正在前往相應(yīng)工作站的AGV。

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

核心匹配算法

對于核心匹配算法，已經(jīng)有一套行之有效的實踐。本文涉及的所有匹配問題，其主體均為任務(wù)和AGV兩個部分。

一般來說，根據(jù)某一時刻機器人可掛載的最多任務(wù)數(shù)量是否為一，又可以分為兩種模式：單一任務(wù)模式和任務(wù)隊列模式。其中，在單一任務(wù)模式下，機器人一次只能領(lǐng)取一個任務(wù)，在完成當前任務(wù)后才可以領(lǐng)取執(zhí)行下一任務(wù)；對于任務(wù)隊列模式，機器人可以一次分配多個任務(wù)，根據(jù)場景不同可以按照一定順序或者同時執(zhí)行。

根據(jù)單輪指派問題中的兩方(即AGV和搬運任務(wù)) 數(shù)量的多少，又可以分為一對多和多對多模式。

一對多：輪詢策略

多對多：MCMF；整數(shù)規(guī)劃

一對多模式

一對多模式主要分為以下兩種情況:

1.workcentre initiated：在新任務(wù)生成時從多個可選機器人中選擇最為合適的一個執(zhí)行任務(wù)

2.Vehicle initiated：當一個機器人空閑后，從多個等待任務(wù)中選擇一個給該機器人執(zhí)行

workcentre initiatedtask assignment problem

在該模式下，如何從可選機器人中選擇最合適的那一個，是整個策略的核心。一般來說，有如下原則：

最近原則（Nearest Vehicle rule）

選擇滿足以下條件的第個AGV ：

for all idle vehicles

其中是agv到當前任務(wù)點的距離

最遠原則（Farthest Vehicle rule）

選擇滿足以下條件的第個AGV ：

for all idle vehicles

其中是AGV的行駛速度

最長閑置原則（Longest Idle Vehicle rule）

選擇滿足以下條件的第個AGV ：

其中，代表當前時間，代表到當前時間為止，第個AGV的空閑時間

對于當前待執(zhí)行任務(wù)池（任務(wù)間無優(yōu)先級），依次對每個任務(wù)執(zhí)行以上選取原則，為每個任務(wù)匹配一個最優(yōu)AGV，然后按照成本從低到高選取個數(shù)不超過AGV數(shù)量與任務(wù)數(shù)量最大者的配對，作為分配結(jié)果。

Vehicle initiated task assignment problem

在該模式下,每次為當前空閑的車選擇一個最合適的任務(wù)執(zhí)行

最少空駛時間/距離原則( Shortest Travel Time/Distance rule)

選擇對當前AGV來說空駛時間最短或距離最短的任務(wù)其他原則包括最大出庫隊列原則、FCFS原則等

對于當前可用AGV資源池,依次對每個AGV執(zhí)行以上選取原則,為每個AGV匹配一個最優(yōu)任務(wù),然后按照成本從低到高選取個數(shù)不超過可用AGV數(shù)量與任務(wù)數(shù)量最大者的配對,作為分配結(jié)果。

基于任務(wù)選車或基于車選任務(wù),是兩種不同的方式。一般來說,某個任務(wù)長期無法執(zhí)行比某輛AGV長期閑置更加嚴重,因此基于任務(wù)選車是一種更合適的方式。

多對多模式

最小費用最大流(MCMF)

根據(jù)當前待分配任務(wù)集合及AGV集合進行建圖：

考慮一個典型的場景,每輛AGV僅可同時執(zhí)行一個任務(wù),那么每輛AGV到源點的容量均為1. 任務(wù)到匯點的各條邊容量顯然均為1. 如果某個任務(wù)能被某個AGV執(zhí)行,則有從該AGV到該任務(wù)的有向邊,其容量為1。每條邊的成本綜合一下幾點得出:(1)任務(wù)優(yōu)先級分數(shù)(2)AGV優(yōu)先級分數(shù) (3)搬運成本。

一個典型的網(wǎng)絡(luò)如下圖所示:

通過對以上網(wǎng)絡(luò)建圖方式及增廣路的查找方法進行改造，可以得到不同的變種MCMF模型以適應(yīng)不同的業(yè)務(wù)場景。