任務依賴

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

一般來說，不同任務類型存在優先級，或者相互依賴關系，例如PS區出庫托盤拆空后，需要先將空托盤搬走，否則下一個綁定在該站點的入庫任務無法執行。而疊托移庫任務需要先于空托回庫執行，否則疊托占用疊托機，導致空托回庫任務無法執行。

運力配比

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

容量限制

由于起始點、目的地或行駛區域的物理容量限制，需要對同一時間到達相應地點的AGV或搬運容器實施容量限制，例如短時間內目的站點可容納容器數、巷道可駛入AGV數等。該限制條件可根據具體業務場景靈活配置。

搬運任務分發

AGV約束

可執行任務類型限制

劃分運力組后，每個AGV只能執行特定類型任務。

AGV優先級

AGV優先級劃分常見CTU場景，例如同一巷道內的任務優先分給已被分配該巷道任務的AGV，出入庫任務優先分配正在前往相應工作站的AGV。

搬運任務分發

核心匹配算法

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

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

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

一對多：輪詢策略

多對多：MCMF；整數規劃

一對多模式

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

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

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

workcentre initiatedtask assignment problem

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

最近原則（Nearest Vehicle rule）

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

for all idle vehicles

其中是agv到當前任務點的距離

最遠原則（Farthest Vehicle rule）

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

for all idle vehicles

其中是AGV的行駛速度

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

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

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

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

Vehicle initiated task assignment problem

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

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

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

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

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

多對多模式

最小費用最大流(MCMF)

根據當前待分配任務集合及AGV集合進行建圖：

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

一個典型的網絡如下圖所示:

通過對以上網絡建圖方式及增廣路的查找方法進行改造，可以得到不同的變種MCMF模型以適應不同的業務場景。