基于VNS 智能算法的多搬运机器人任务调度方法研究

窦 洽

(武昌职业学院,湖北 武汉 430200)

1 多搬运机器人研究现状

搬运机器人是工业机器人的一种,能够对作业做自动化搬运。 当这种搬运机器人里面拥有多种末端执行器的时候,它不拘泥于某种形态对物品进行各种作业,不仅能减少大量的人力,也可以让搬运的效率得到提升[1]。 当前仓库里面开始出现各种类型的搬运机器人,这大大提升了工作效率。

搬运机器人已经发展了一段时间,不少过去单个搬运机器人所存在的问题都已经被解决。 当运用单个搬运机器人进行工作时,通常只要对应位置坐标,故规划路径较简单。 近些年来,物流业务量一年比一年增加,仓库系统也拥有更多的面积,仅仅依靠单个机器人没有办法满足当下的需求。 因此,要想提升工作效率,让工作能够尽快完成,则需要运用多个搬运机器人一起运作。 多搬运机器人在运作时,由于有更多因素需要考虑,所以问题也会更加复杂[1]。 搬运机器人在运行过程中会用到很多技术,需要对任务进行分配、规划相应的路径等。 假如仓库里运行的搬运机器人不止1 个时,常常会出现分配任务不够均衡、路径规划不清晰导致拥堵等情况[2]。 故当运用多搬运机器人协作的时候,最关键的点是分析与解决任务调度的问题,只有将这一点解决了,才能真正实现协作的可能。

2 多搬运机器人工作模式

多搬运机器人除了拥有极强的收纳能力,可收纳较大的货物,还拥有对货物进行抓取的执行末端,能够实现拣选操作。 当这类机器人被正式使用后,仓储的自动化将再次得到提升[3]。 类机器人可以将不同的物料箱在同一时间段内进行存储,当需要取货的时候通常会选择“夹抱式”。 通常多搬运机器人在运行过程中流程如下:(1)将需要机器人执行的任务队列进行分配。 (2)每个机器人获取相应的任务,然后自行移动到该任务需要进行的货架旁。 (3)依据任务的不同,机器人将货物放入储物格或者是货架中。(4)假如任务队列依旧还有,则直接再次循环步骤2。(5)机器人移动到分理处位置,然后对货物进行装货或者是卸货。

图1 HAI ROBOTICS 多搬运机器人

当多搬运机器人进行取货的时候,它首先会移动到分理处,并从这里出发,随后所有排队等候的机器人领取各自的任务。 但这些任务的数量以及机器人的数量都是有限制的,因为当这两者的数量到达某个规模时,任务调度会出现很多问题,以至于算法没有办法迅速求解。

3 多搬运机器人任务调度建模

事实上,多搬运机器人的任务调度问题能够被建模为CTSP 问题,即把搬运机器人当成是CTSP 问题里面的旅行商,而不同规格的搬运机器人对应不同的颜色[4]。 在当前的科技中,CTSP 已经能够拥有最优的算法。 把这种任务调度问题之间转换为CTSP 问题,就可以在时间尽量短的情况下获得更好的分配任务的方案,工作效率也能得到一定的提升。 对多搬运系统机器人来说,合理、科学的任务调度不仅可以让需要运行的作业得到优化,也可以降低协作的难度。

不管在哪种电商仓库内都拥有各种各样且数量多的货物,这些货物并没有相同的规格、体积和形状。不同的拣选机器人只能对应其规格的货物,所以要想将仓库里面不同规格的商品都存取完毕自然要用到很多规格的拣选机器人。 由于不同规格的货物在进行存取的时候需要用到不同规格的拣选机器人,因此这种任务调度也被称作是多任务调度。

事实上,搬运机器人所行走的路径与任务和工作台之间的距离是没有任何联系的,搬运机器人行踪的总路径只与其被分配的任务序列有联系。 如果是很多个任务被同一个搬运机器人运行操作时,要想顺利解决这些任务的分配问题,可以通过建立模型,将其变成旅行商的问题,再解决问题。 在电商仓库中,多搬运机器人最重要的任务调度问题就是怎样让多辆搬运机器人获得更多的搬运任务,最终这些调度的结果应当是:所有的搬运机器人都可以获得分配,而且拥有详细的任务序列[5]。 不过,如果搬运机器人有太多的数量,或者任务数量有很多的时候,要想尽快将这些任务进行分配就不会很简单。 在此类情况下,可以将这种调度问题变成全色CTSP 问题。 以图2 为例,能够直观地看出搬运机器人的数量是3 辆,而需要分配的任务一共有8 个。 对于不同的搬运机器人,可以给予不同的颜色,在每个任务上分配3 种颜色,即这8 个任务都能够被搬运机器人所接受,这3 个搬运机器人里面的每一个机器人都可以将所有的任务全部搬运完成。

图2 搬运个体与对象的CTSP 颜色表示

4 基于VNS 算法的多搬运机器人调度求解

4.1 VNS 算法简介

VNS 是一种智能启发算法,这种算法由国外学者提出,该算法并不需要种群进行迭代进化[6]。 VNS 拥有不少优点,例如:便于进行操作、拥有简单的结构,而且在生产调度问题以及旅行商问题上能顺利运用。

4.2 基于VNS 算法的求解

4.2.1 贪婪初始化

VNS 算法只是对某个个体进行初始化处理,而初始化个体的好坏能够影响算法的性能。 在本研究中,为了得到初始解,通常会选用贪婪初始化的方式去生成。 贪婪初始化的步骤主要如下:(1)某个商人能够随机得到城市,且这个城市拥有多样的颜色,而每个商人都顺利到达所有需要访问的城市。 (2)起始城市会被商人当成是当前城市,而下一个城市则在剩下需要访问的城市里面选择,需要遵循的原则是,下一个城市与当前城市拥有最短的路径,得到不同商人的贪婪城市序列。 (3)当商人的城市序列全部完成之后,再把起始城市加到这个系列末端之后。 具体如图3 所示,当一个商人贪婪初始化5 个城市时,其城市序列应该为1-4-3-5-2-1。

图3 贪婪初始化

4.2.2 抖动操作

当运用VNS 算法时,为了获得更新的邻域解,应当运用抖动的方式来持续搜索当前领域的情况。 本研究为了顺利进行抖动,会选择以下这些操作方式:贪婪重插入操作、多色城市的贪婪重插入操作等。 当使用最后一种操作方法的时候,可以在当前解周边的小范围邻域进行搜索。 如图4 所示,就是运用了多色城市的贪婪重定位操作方式,这里的商人一共有2个,城市有10 个。

图4 贪婪重定位操作

4.2.3 局部搜索操作

要想得到更加优质的解,对经过抖动而生成的新邻域解进行局部搜索操作就能够得到。 如图5 所示,就是运用了局部搜索操作方式,这里的商人一共是2个,城市是10 个。

图5 局部搜索操作

4.2.4 2-OPT 操作

当进行上一步操作以后,城市序列就会有所变化。 为了优化商人的城市序列,这篇文章选择的操作方式是2-OPT,如图6 所示,就是运用了2-OPT 的操作方式,这里的城市是10 个。

图6 2-OPT 操作示例

4.3 基于VNS 算法的求解流程

VNS 的具体流程如图7 所示。

图7 VNS 流程

5 算例分析

当运用就近原则时,虽然电商仓库能够更快完成目前的任务,可是总耗时是没有考虑在内的。 虽然当前已经有很多CTSP 求解案例,但如果旅行商数目过多时,通常是达到几百的情况,求解将会变得很复杂,因此想要在较短的时间内高效、科学地求解就变得比较困难[7]。 如图8 所示,这里运用到的搬运机器人一共是500 个,而搬运任务有15 000 个,所体现的调度过程图是选择了大规模旅行商的全色CTSP 模型。在此任务中,任务一共进行了3 次分配,每次都是500辆搬运机器人分5 000 个任务。 当算力处于有限情况时,任务执行时间会小于任务调度时间,这就会让搬运机器人在完成任务之后出现等待的情况,大大降低了工作效率。 如果搬运机器人数量过多,在达到几百的时候,多搬运机器人以及拣选机器人的任务调度都不适用建模成大规模CTSP 的方法。

图8 采用大规模CTSP 模型调度

6 结语

当大规模搬运机器人在进行任务调度时,常常会出现求解困难的情形,为了有效、科学、合理地解决这个问题,本研究选择运用CTSP 模型与分组并行策略结合在一起的方式去解决。 所谓分组并行策略,其实就是把大规模搬运机器人转变成小规模搬运机器人,然后对这些分组后的机器人做并行调度[8]。 运用此策略的过程如图9 所示,在这个过程图中共用到15 000 个搬运任务及500 辆搬运机器人。 其运用分组并行策略的步骤如下:第一,把这500 辆搬运机器人平分为5 个集群,每个集群都由50 辆搬运机器人组成,同样将15 000 个任务平分为30 个任务集,而每个任务集都由500 个任务所组成。 第二,将这些任务进行分配,例如:1—50 号搬运机器人将会按照顺序得到1—50 号任务,在得到任务后,搬运机器人就会对得到的任务进行执行,而同时501—1 000 号的任务已经被分到这50 号搬运机器人身上,就这样依次往后面分配8 次任务。 因为每个批次的搬运机器人数量以及任务数都较少,所以在进行任务调度时可以较快完成任务。 当不同批次的调度被完成后,因为搬运机器人集群都在完成自己被分配到的任务,所以搬运机器人对任务进行等待的情况并不会出现。

图9 采用分组并行策略调度