整数规划

建立数学模型,从全局角度出发,一次性为多个任务分配多辆车。以下为一种经典的任务-运力匹配模型:

其中 表示机器人被指派去取货架,表示机器人距离货架的距离，我们可以将问题中约束松弛为，求解松弛后的问题可以直接得到整数最优解．通过求解上述多对多指派问题获得多个机器人和任务之间的匹配关系，从全局角度进行整体优化，降低系统总搬运成本。该模型简化了搬运成本，以及特定AGV执行特定任务的成本，且不考虑业务上的复杂约束。

考虑业务约束下匹配

在多对多模式下，如果考虑跨运力组、运力配比或自定义约束等等，则需将相应信息加入模型中，例如考虑运力配比的情形，令表示第个AGV执行第种任务，可添加约束及来限制第种任务的配比。

以上两种模式并无绝对好坏之分,一般来说一堆多模式原理简单,开发维护容易,计算开销较小,但不保证全局最优;多对多模式相对复杂,且计算开销较大,但解的最优性更好。

搬运任务分发

搬运成本

一般来说,搬运任务的起讫点在下发任务时就已确定,因此某个指定运力执行某个指定搬运任务的成本可以明确地定义。常见的定义方式包括搬运距离、搬运时间。

考虑到仓内AGV的行驶方向一般为二维平面的水平、垂直两个正交方向,常见的距离定义方式包括欧式距离或曼哈顿距离,该定义方式较为简单。

另一种更精确的方法为调用路径规划算法(等)，计算AGV→任务起点→任务终点的最短路径的完整距离。

该方法尤其适用于路网中存在单向路的情形。考虑到实时计算成本较高,可将地图中所有完整路径的距离存储下来,直接查询即可。在考虑路线拥堵的情况下,可根据地图热点信息为每条边定义不同成本。搬运距离和搬运时间可以相互转化,例如对于完整路径内的每一段直线路径,可根据AGV的加速度信息,求出基于速度规划的行驶时间,并为每个转弯行为加入转弯时间。

搬运任务分发

任务执行

对于以挂载任务队列或多中转点任务的情形,为使机器人可以执行任务,还需要确定任务涉及的顺序问题,具体来说包括:

如果存在多个中转点或者目的点,需要确定他们之间到达服务顺序；

如果采用任务队列模式,需要确定多任务之间的执行顺序.确定执行顺序在不同场景下方式不尽相同,主要考虑因素包括距离和工作站当时负载情况等。

下面我们通过对一些具体问题场景的讨论来进行阐述。

每个机器需要指派一个或多个搬运任务,并且需要确定每个机器人分别需要搬运的货架以及搬运顺序,使得所有机器人总搬运距离最短或者使得所有任务的完成时间最短。

在这一场景下任务的指派和顺序的确定是通过求解一个变种车辆路径问题(VRP) 同时确定的。而对于上一节介绍的拣选支持机器人系统,确定机器人对拣选点(也就是多个中转点) 的前往顺序可以抽象为一个在仓储路网结构下的经典旅行商问题(Traveling Salesman Problem,TSP) 或其变种问题,通过最小化行驶路径长度确定各个拣选点的到达顺序。

在搬运机器人场景下,可能多个工作站都需求同一个货架上的物品,也就是一条搬运任务有多个目的地的情况。虽然可以通过TSP类方法确定各个工作站的到达顺序从而最小化整体搬运距离,但同时还需要根据工作站当时的任务负载情况进行调整,可以优先前往相对需求急迫或者当前较空闲的工作站,减少工作站的等待,虽然会增加一部分搬运成本但是可以提高整体系统作业效率。

搬运任务分发

评价及灵敏度分析

任务分配和执行的策略会依据不同场景不同需求而有所不同,而在同一场景下面对同样的业务需求,通常也会有多种不同的调度策略可供选择,即便同一种策略也会因为不同的内置参数选择而产生不同表现,现实中通常很难完全确定某一单一环节如何影响整体系统生产效率。

尽管如此,通过对一些特定统计量的分析,我们也可以大致了解策略对系统性能的影响。对于本节所介绍的搬运任务分配和执行,在订单拣选场景例如拣选和拣选支持机器人系统,可用若干用于评价调度策略性能的统计量,其中包括:

1. 订单生产效率:一定时间内生产完成订单数量与接受订单数量的比例

2. 响应时间:任务等待机器人执行的时间与机器人空驶时间之和

3. 生产时间:订单在系统中生产的时间

4. 机器人平均利用率:机器人执行任务的时间(包括空驶和满载时间与总时间的比值)

现实生产系统中还会计算和监控更多统计量用于后续性能分析,其中包括工作站拣选等待时间、机器人平均搬运距离以及搬运任务平均耗时等。对于分拣场景,则会统计包裹投递效率等。

除去上面提及的系统性能表现以外,另一方面我们还需要关注算法策略本身属性。具体来说,随着机器人技术的不断普及和业务场景的不断扩大,系统中机器人数量和待处理的任务量会进一步提升,这会使得调度问题规模变得很大,而同时业务对于系统的响应可能要求很高,在这种场景下,需要算法策略有很好的计算性能。

机器人系统不可避免会出现异常故障,算法策略也需要有足够的鲁棒性可以进行快速调整。另外,对不同时间段内可能的不同调度目标,调度策略也需要有足够的柔性可以满足不同要求。总体而言,需要通过对运营效率、计算性能、鲁棒性和柔性等方面综合对所考虑的任务调度策略进行评价。