任务依赖

不同任务可能存在任务依赖，例如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模型以适应不同的业务场景。