粒计算在AGV任务分配中的应用研究

王 杰 马廷伟 刘 兵 孟龙

(北京物资学院信息学院 北京 101149)

随着智慧物流影响的逐渐扩大，移动机器人在物流中的实际应用已经成为研究重点之一。在自动化立体仓库中，AGV小车代替人类进行拣选与搬运。因此如何使AGV更高效地完成物流活动是十分重要的研究。本文将结合一种新的概念和计算模式——粒计算，对仓库中的任务分配环节进行优化。粒计算是一种新兴的概念和计算模式，更高级地模拟了人类的思维规律，对具有重要意义。针对多任务分配问题,本文运用有关粒计算的相关理论,运用有关信息粒化的概念,提出了一种将具体任务粒化的方法，建立新的任务分配模型，以提高仓库的工作效率。

基于AGV移动货架的“货到人”自动化仓储系统，仓储区由很多可移动货架组成，每个货架上存储着若干种类和数量的SKU，拣选区由多个拣选台构成，每个拣选台配有一名拣选员，可以同时进行多个订单拣选作业。仓储系统中有很多AGV，用于执行货架搬运任务。对于仓储系统接收到的订单，首先根据相似度进行分批，分批后的订单分配到各拣选台，调度系统将商品信息列表发送给拣选员，同时系统根据订单任务指派执行任务代价低、效率高的AGV搬运货架到拣选台，拣选员根据商品信息列表拣选商品。

(一)粒计算的国内外研究现状

本文主要讨论其在任务调度方面的研究，因资源调度与任务分配有异曲同工之妙，故有讨论的意义。前人在资源调度方面已经有了许多研究。粒计算理论应用到网格调度中，提出了一种新的层次式数据网格资源调度算法[2]。还有一些学者将粒计算理论引入到非实体资源的调度问题上，齐平等[4]针对云资源调度中低效率问题，基于模糊商空间思想将云端虚拟机抽象成计算单元，根据用户服务质量特征建立基于模糊商空间的资源分配模型。张鹏[5]将电力系统各个机组进行粒化，以假想最优调度下的机组组合状态为目标序列，以系统优化潮流计算条件下的机组组合状态为无限接近目标序列的函数序列，应用粒的相似度概念进行此函数序列与目标序列之间粒的相似度计算，确定出在实际中最能接近给定假想最优调度下的目标序列所对应的最优发电机组组合，从而为优化调度决策提供重要依据。邓一平[6]运用有关粒计算的相关理论,运用有关信息粒化的概念,提出了一种将具体任务粒化的方法，该方法将具体任务粒化为若干个原子任务粒空间,提出了一种基于粒计算的多Agent任务模型。本文是利用粒计算的思想对仓库中的订单与AGV小车进行粒化，进而提高出库的效率。许多学者在调度方面的研究，将资源进行粒化解决问题，说明了粒计算在调度与任务分配的可操性，对本文的研究有很大的借鉴作用。

(二)基于粒计算的多AGV任务分配研究

仓储拣选订单的仓库中，一般分为订单分解、合并订单、任务拆分、任务组合等作业流程，经常导致作业任务的“粒度”过大。而当前客户多处于“小批量、多批次、多品类”的订单状态，可能会造成资源利用率低、能源浪费、交货延期等问题，会对客户满意度和仓库的工作效率产生不良影响。解决这些问题的关键在于将订单转换为适合下达作业指令的任务单元，在完成订单拣选要求的前提下，根据系统特点将某些作业指令合并，尽可能减少AGV搬运货架的次数。

借助粒计算研究思想，首先将订单拆分为最小作业单元——任务粒，在考虑货架商品存储种类特点的基础上，将任务粒合并为组合任务指令，最终将订单转换为多个货架搬运任务。同时，借助物联网技术实时获取AGV的各种状态参数，如作业状态、运行状态及物理状态等，并将其实时转换为作业能力，在粒计算指导下，根据作业能力将AGV划分成适合不同作业任务的资源粒，并根据粒的合并性，将相似的资源粒进行合并。自动化仓储系统进行多AGV拣选任务分配时，针对某一类任务粒，优先选择适合该作业任务的资源粒集合中的AGV，求解时不但减小了搜索解的空间，还降低了AGV与系统的通讯次数，从而提高多AGV任务分配问题的求解质量与效率。

1.订单任务粒化

对于电商仓库的某个订单来说，其所包含的任务只是该仓库某区全部订单任务的一部分。通常情况下，一个订单内包含多种商品，需要搬运多个货架到拣选台才能完成拣选，指派AGV搬运某个货架到具体的拣选台是调度系统所能下达的最小作业指令，是自动化仓库订单能够拆分成的最小任务。对于多AGV任务分配问题来说，自动化仓储系统指派AGV搬运货架到目标拣选台是系统所能下达的最小作业指令，是多AGV任务分配问题的基本任务单元。在考虑货架仓储特点的基础上，通过对基本任务单元进行合并，最终建立拣选总时间最短的多AGV任务分配及货架排序模型。

2.AGV资源粒化

仓储作业是动态连续的作业过程，调度系统的任务队列中不断增加新的作业任务，作业环境也在不断变化，调度中心根据任务作业需求向仓储系统中的作业设备下达作业指令。在自动化仓库的拣选系统中，除传送带外，其他作业设备，如堆垛机、叉车、AGV、货架等自身状态、作业状态、作业进程、当前位置、当前载货量以及续航时间等随时间不规则变化。对于AGV来说，对于某一确定任务，货架位置固定，拣选台位置固定，不同AGV由于各种状态的不同，执行任务的时间成本以及能耗不同。调度系统的目的是在保证任务高质量、快速完成的前提下，实现AGV的高效、合理调用，实时获取AGV的各项状态参数并计算转化为实时作业能力，是调度系统实现智能调度的基础。

(三)基于粒计算的多AGV任务分配模型构建

本文通过粒计算制定的任务粒化和资源粒化方法，建立多AGV任务分配模型，以实现全部订单拣选总时间最短的任务分配目标。设定每个组合任务指令都对应着一个货架搬运，因此每个拣选台的拣选任务也就是AGV将拣选台订单需求的若干货架搬运至拣选台并完成商品拣选的过程，由基于物联网的资源粒信息可实时计算出各AGV执行各拣选台组合任务耗时及能耗。最后，以拣选时间最短为目标，建立多AGV任务分配模型并进行求解，最终得到各拣选台订单任务分配结果。

Qu：为s拣选台对q货架商品的需求量

pnsq：表示AGVrn被分配到s拣选台对q货架搬运。

将组合作业指令与AGV资源粒进行组合，建立一段时间内全部订单拣选耗时最短的多AGV任务分配模型：

(1)

其中，目标函数(1)表示最小化订单拣选的总耗时；
约束(2)表示一台AGV资源粒只能分配给一个拣选台上的一个任务粒；
约束(3)为变量取值约束；
约束(4)表示资源粒当前作业能力能满足任务粒需求。

随着智慧物流的到来，物流逐渐向个性化、小批量、多批次方向发展。而粒计算模仿了人类看待事物多角度、多层次的思维模式，成为处理不确定的大量信息的有效方法。并且粒计算最根本的思想是通过合适粒度的选择,来寻找问题的一种较好的、近似的解决方案,从而降低问题求解的复杂度。针对这一问题，本文分三阶段构建以搬运时间最少的模型。第一阶段：对订单进行合并或分解，形成大小合适的任务粒，将最小的任务粒组合成新的拣选订单。第二阶段:对机器人从性能及电量方面评估，根据粒计算构造AGV资源粒并组合。第三阶段：构建基于粒计算的多机器人模型。本文通过粒计算的理论和方法对物流复杂问题的解决提供了新思路。如何更精确将粒计算运用到物流作业中是一个值得思考的问题。