基于改进贪婪式算法的AMR任务分配

谢 进， 向 勇， 杨秀清， 周新志

(1.四川大学电子信息学院， 成都 610065； 2.中国民航局第二研究所， 成都 610065； 3.民航成都物流技术有限公司， 成都 610065)

1 引 言

随着全球民航业旅客流量的日益增长，机场行李处理量随之日渐攀升，据国际航空电讯集团(SITA)2020年行李IT洞察报告[1]可知，2019年全球航空业共运输了45.4亿人次旅客及行李，行李处理量在20亿件以上，2018年和2019年中国民航业分别完成旅客运输量6.1亿人次和6.6亿人次，旅客托运行李量均超过了3亿件.对机场行李进行安全、智能、高效、稳定的处理不仅对航空安全、航班准点率和旅客满意度具有举足轻重的意义，而且对我国的民航运输服务品质的提升和民航建设具有重大的促进作用.

民用机场自建成以来，国内外众多科研院所和学者针对机场行李处理技术的研究从未停止过.截至目前，虽然我国机场行李处理系统已历经了三代技术研究与更迭，历经了近40年、但是为满足未来“四型机场”建设需求、进一步提升民航运输服务品质以及旅客日益增长的个性化需求，机场行李处理技术的智能化水平应得到进一步提升，紧跟未来智能化、智慧化的发展步伐，而现有的行李处理技术的智能化程度已很难满足如上所述需求.目前，虽有与机场行李处理领域相似的快递物流和仓储领域已开研究并应用于自动导航小车AGV(Automatic Guided Vehicle)技术的包裹或仓库货运处理系统，但是AGV通常采用二维码、电磁和磁带等导航技术，按照预设规划的路径完成各个任务点之间分货物运送，这需要在行驶路线上分别预布二维码标签、金属导线和磁带，这就使得其灵活性差，智能化程度低，还会造成大量资源浪费，而且很难满足如上所述多方面需求.

因此，需要研究具备自主能力更强，智能化程度更高，面向未来机场的行李处理技术.基于AMR集群的行李处理技术具备较高的智能性、扩展性和灵活性，因为AMR通常采用激光与其他传统技术相结合的导航方式，不再需要在地面预布二维码，金属导线和磁带等地标，其自身具备强大的计算能力且能够感知周围环境并做出相应决策.所以可根据机场实时变化的行李量而实时调度不同集群规模的AMR小车，高效、智能、灵活地完成行李处理.在机场行李处理技术中，关于AMR小车的任务分配与调度是其核心问题之一，其含义主要是指在行李动态抵达和AMR小车位置持续变化的环境中，为AMR集群分配合适任务，使得行李任务处理系统的运行时间达到最小.而如何实现行李的安全、稳定、高效的处理对航空安全、航班准点率和旅客满意度具有举足轻重的重要意义.本文针对AMR集群的任务分配与调度问题提出了一种适用于机场环境的任务分配与调度策略，以缩短任务分配时间和系统运行时间.

2 相关工作

目前，针对多任务分配与调度系统的研究备受国内外学者的关注.Banziger等[2]提出了一种将仿真作为遗传算法中的适应度函数来优化机器人团队任务分配的新方法，该方法不仅可以评估任务的不同分布，也可以考虑工人和机器人在共享工作场所的交互动态.Xia等[3]提出了一种解决地面运动目标多无人机协同任务分配和航迹规划问题的系统框架.该方案不仅能有效地规划出合理的航迹而且能解决不确定性问题，得到最优的任务分配方案.El-Ashmawi 等[4]基于SSA提出了一种MSLRH算法用于解决任务分配问题，在树状结构数据集中，该算法的最小平均分配成本比遗传算法降低了62%，比PSO和JAYA降低了42%.Li 等[5]提出了一种基于改进的灰太狼优化算法(IGWO)的分布式协同任务分配策略.先将MRTA问题转化为多个旅行商问题，然后利用IGWO求解多个TSP问题的最优解.最后，对最优解空间进行积分，得到MTSP的最优解 .其实验结果表明，IGWO算法具有较快的收敛速度和较高的精度.Zhang 等[6]针多AGV系统存在着资源分配、冲突和死锁等一系列问题，采用时间窗法建立了多AGV任务分配系统，能有效地解决AGVs系统的冲突问题，具有较高的稳定性和实时性.Chen 等[7]对移动吊车与AGV集成调度问题作为一个多机器人协调调度问题进行研究，提出了一种具有两组流量平衡约束的起重机和AGV多商品网络流模型，有效地实现了AGV与起重机在自动化终端中的精确协调.Dang 等[8]提出了一种将遗传算法与禁忌搜索相结合的混合启发式算法来解决考虑完工期最小化的问题.Mousavi等[9]通过建立数学模型并和进化算法相结合，在考虑AGV电池电量的情况下，以最小化AGV的操作时间和数量为目标，对AGV的任务调度进行了优化.Tang 等[10]在传统的先来先服务调度算法上利用帕累托空间搜索，解决可预测内存层次的芯片上实时流应用程序的调度问题.Alworafi 等[11]在短作业调度算法的基础上进行改进， 极大的缩短了在云计算环境中最后一个任务的完成时间与平均响应时间，实现虚拟机之间的负载均衡.王鑫等[12]在考虑云环境下任务与虚拟机资源的特征，改进了贪婪选择策略获得了更好的执行效率和负载均衡能力.Tong等[13]提出了离线预测结合在线分配的任务分配算法POLAR-OP提升了在空间纵包领域下的任务匹配对数；桑泽磊等[14]针对传统合同网协议CNP(Contract net protocol)存在协商频繁和投标并发操作问题，提出了一种基于节拍的改进合同网协议，缩短了AGV完工时间并提升了机床、AGV利用率.严飞等[15]针对多无人机协同搜索和攻击作战中，考虑存在相互耦合的任务分配的问题，提出了一种获得最大系统效能的任务分配算法.张梦颖等[16]针对无人机群协同实时任务分配问题，在CNP的基础上，将招标者参与投标和引入并发机制对CNP做出了改进，减少了通信量、运算量和拍卖回合.

尽管目前还未有将 AMR小车应用于机场行李处理领域相关的研究报道，但是在上述文献中针对多任务分配与调度 系统的研究对AMR小车的任务分配与调度研究具有重要借鉴意义.

3 问题描述

3.1 场景模型

机场的行李处理系统中，AMR集群可应用于机场值机岛、开包间和分拣等局部场景，也可应用于机场行李处理整体场景.本文以值机岛场景应用AMR集群为例，在值机岛场景中，旅客行李从值机柜台进入，由AMR小车托运至集中安检区进行安检，然后再将安全行李运输至行李分拣口，为了方便描述，可将AMR值机岛场景描述为图1所示模型.

图1 场景模型Fig.1 The scene model

图1所示模型主要由值机柜台区，AMR停放区，行李分拣口区及值机柜台区和行李分拣口区之间的运行区组成，图1中菱形代表AMR小车，方形代表值机柜台，圆形代表行李分拣口区.当行李到达值机柜台后，在停放区的AMR运行到达值机柜台接上行李之后，需要根据行李的目标位置将其安全运送至行李分拣口之一，然后该AMR再根据值机柜台的行李任务情况选择返回停放区还是直接返回值机柜台继续接取新的行李.

3.2 相关定义

本节对3.1节的行李任务和AMR小车做出相关定义，设ti为任务集合T中的任务，ti∈T，对单个任务ti的定义为

ti=〈taskId,ts,ls,le〉

其中,taskId代表该任务的编号；ts代表任务到达值机柜台的时间；ls代表任务开始的位置，即任务在某个值机柜台的位置；le代表任务结束的位置，即任务在最终到达行李分拣口的某个位置.

设wi为AMR集合W中一台AMR，wi∈W，对单个AMR的定义为

wi=〈workId,lc,Cf,Ca〉

其中,workId代表该小车的编号；lc=〈x，y〉，代表该AMR 当前的位置；x和y分别代表横纵坐标；Ct代表该AMR接取新任务的距离代价；Ca代表该AMR执行完自身当前任务的代价，如果AMR没有在执行行李运输任务，则Ca=0.每轮分配任务时需要更新计算Ct和Ca的值.

3.3 任务匹配

在机场环境中，任务集合T中的任务并不是所有任务一起到达值机柜台，而是在不同的时间点到达.所以任务分配需要在每轮任务到达后执行，这是一个多轮的任务分配问题，直到任务集合中的最后的任务都到达值机柜台，完成任务分配.用WT表示总任务分配集合，假设任务集合Ti是T的子集合，即表示第i轮任务分配的任务数量，设WTi表示第i轮的任务分配集合，那么每个分配可表示为WTi=〈wj,tk〉，，其中，wj∈T，tk∈Ti；wj代表j个AMR；tk代表第k个任务，在每轮任务分配中，每个AMR允许分配得到Ti中的多个任务，任务分配一旦完成，就不会发生改变，由AMR完成自身任务.

4 任务分配

AMR 集群系统可视为一个随机服务系统，行李处理任务的到达流可用泊松流[17]描述，其到达时间间隔服从参数为λ的负指数分布，而服务时间服从参数为μ的负指数分布.本文提出一种基于改进贪婪式的AMR小车任务分配与调度策略.当任务到达值机柜台之后，首先考虑到机场环境中存在障碍物和AMR小车位置动态发生变化的问题，采用A*算法计算AMR小车接取任务的代价并且根据任务动态更新.其次考虑到任务到达规律和AMR小车规模对任务分配和调度的影响，对AMR小车进行类型划分和使用预先出发的策略.

4.1 代价计算

本文中AMR小车的接取任务的代价Ct使用A*算法计算，这是考虑到在场景中存在障碍物的问题，如果采用常规的距离计算法如曼哈顿距离，欧氏距离计算，将会对任务分配的准确性有着较大的影响.如图2所示，图中黑色条形为障碍物，不可通过.当任务出现在位置A(0，10)的时候，在位置B(22，16)和位置C(17，3)分别有一辆AMR小车参与该任务的分配，此时如果采用欧氏距离公式计算如下式.

(1)

根据式(1)可计算位置B(22，16)与A位置(0，10)的欧式距离dAB=22.8，位置C与A的欧式距离dAC=18.4.显然如果按照欧氏距离来计算代价，那么将由位置C处的小车获得该任务，但是由于图中存在障碍物，小车是不可通过路径AC的.而采用A*算法估算路径时，路径长度计算如下式.

(2)

式中,n1代表A*算法斜向步数;n2代表横向或纵向步数.根据式(2)，AB路径长度为dAB=24.5，AC的路径长度dAC=29.9，显然应当由B处的小车获取该任务.因此在实际情况中，采用A*算法估计代价更加符合实际需求.

图2 代价计算Fig.2 The cost calculation

4.2 任务分配算法

贪婪算法在任务分配与调度问题中是一种常见的策略.贪婪算法总是做出在当前看来最好的选择，算法的关键是贪婪策略的选择.算法应用在本文中，即每当任务到来时，贪婪算法总是从所有AMR中选择接取任务代价最小的AMR，直至所有的任务分配完毕.但每次任务到来时，总是从所有AMR中选择会使得计算量较大.因此在改进策略中，根据AMR不同运行状态的特点，对AMR进行类型划分，第一种是空闲的AMR小车即停放在AMR停放区的小车，用flag=0来标识；第二种是执行完当前任务正在返回AMR停放区的小车，用flag=1来标识；第三种是正在执行任务的AMR小车用flag=2来标识.在计算代价Ct，可以直观地知道在三种类型的小车中，第一种小车的代价Ct小于另外两种类型的小车的Ct，第二种小车的代价Ct小于第三种代价的小车.当任务到来的时候，不需要所有小车全部参与分配而是分批次考虑参与该轮任务的分配，优先考虑flag=0的小车参与分配，接着考虑flag=1的小车参与分配，最后才考虑flag=2的参与分配.采取这样分批次参与分配的方案可以有效减少无用小车的代价估算，降低计算量.此外，由于AMR 集群系统中行李处理任务的到达流为泊松流，到达时间间隔服从参数为λ的负指数分布，而服务时间服从参数μ为负指数分布.因此任务的到达是可预估的.由于可以预估到下一轮任务的到达，如果系统存在空闲的小车就可以提前出发到值机柜台接取任务，对于flag=1的小车可以不用返回停放区直接前往服务区接取任务，这种模式甚至有可能做到车等任务的效果，能够有效减少系统运行时间.

因此，本文在基于任务泊松流到达的基础上，对AMR小车的代价估算使用更加符合实际应用场景的A*算法计算，并且采用分批次AMR小车的任务分配和AMR小车提前出发的策略，能够有效缩短任务分配时间和系统运行时间.算法如图3所示.

图3中list0，list1，list2分别对应存放flag=0，flag=1，flag=2类型的小车，当新任务到来.先判断list0中是否为空，如果不为空就直接为list0中的AMR小车分配任务并执行任务；list0如果为空就判断list1是否为空，list1不为空就为list1中的AMR小车分配任务并执行；如果list1仍然为空，那么就从list2中分配任务并执行.新的一轮任务到来之前，空闲的AMR小车可预先出发前往值机柜台区等待，没有空闲的AMR小车那就不做处理.当没有新任务到来后，算法结束.

图3 算法流程Fig.3 The algorithm flow

5 仿真实验

为了验证本文所提算法的有效性，使用任务分配时间和系统运行时间作为评价指标，通过与SimpleGreedy，节拍合同网协议[14]和GR分配算法[18]进行对比实验研究.SimpleGreedy采取的策略是当任务到达值机柜台之后，所有AMR小车参与该轮的任务分配.GR采取的策略是任务到达之后不会立即分配，而是设定一个时间片，收集该时间片的任务数量之后再进行任务分配.本文进行了两组实验，第一组仿真实验对比分析不同算法获得的任务分配时间；第二组仿真实验对比分析不同算法获取的系统运行时间.本文仿真环境基于Python3.7.4，在处理器为3.2 GHz Inter(R) Core(TM) i5-4460，内存为16 G的计算机上运行.

5.1 任务分配时间实验

本节对比分析4种算法获得的任务分配时间.图4表示AMR数量变化时，4种算法的所耗去的任务分配时间.从图4中可以看出，随着AMR数量的增加，SimpleGreedy，GR和节拍合同网协议(CNP)的任务分配时间都持续增大，这是由于每轮分配任务过程中，所有AMR都参与了分配，而随着任务数量增加，每轮任务分配时有更多的AMR需要计算接取代价，从而增加了分配时间.值得注意的是，当AMR数量增加时，本文所提的算法任务分配时间变化不大，任务分配时间较另外3种算法都更小.这是由于在算法中将AMR类型进行分类，每次进行任务分配时是根据AMR的自身情况决定是否参与分配任务的，如果有空闲的AMR，空闲的AMR会参与任务分配，而其他的AMR不会，此时由参与任务分配的AMR决定分配时间.

图5表示当任务数量变化时，4种不同算法的分配时间对比情况. 从图5中可以看出，随着任务数量增加，4种算法的任务分配时间都继续增加，这是显而易见的.但是可以观察到本文所提的算法与另外3种算法的分配时间在逐渐接近.这是由于任务到达时间长度固定为6 min，随着任务数量增加，任务到达的密集程度必然增加，AMR处理任务的速度无法跟上，那么累积在flag=2类型的AMR较多，在分配任务时则会导致参与任务分配的AMR数量增加，从而任务分配时间增大.

图5 任务数量变化的任务分配时间对比Fig.5 The comparison of task allocation time with the change of tasks number

图6表示时间变化时，任务分配时间的对比.类似的情况，由于AMR数量和任务数量固定，对于SimpleGreedy和GR和节拍合同网协议(CNP)来说，任务分配时间变化不大，但是本文所提的算法分配时间先减小，然后又增大.刚开始任务到达密集程度高，累积在flag=2类型的AMR较多，而最后任务到达密集程度低，累积在flag=0类型的AMR较多，所以参与任务分配的AMR数量是一个由大变小，再由小变大的过程.

5.2 系统运行时间实验

本节对比分析4种算法的获取的系统运行时间.图7表示AMR数量变化时4种算法的系统运行时间.从图7中可以看出，随着AMR数量增加，4种算法的系统运行时间都持续减小.当AMR数量大于等于10个后，本文所提出的算法的运行时间明显要小得多，如表1所示较之于节拍合同网协议最差有7.6%的提升.这是由于当AMR数量小于10个时，任务到来比较密集，较多AMR会处于一个比较繁忙的状态，在值机柜台与分拣口之间来回运输行李.这点从系统运行时间上也可以看出，行李任务是在5 min之内到达的，但AMR数量为8个时，系统处理完任务最快的Improve差不多也要750 s.

图6 时间变化的任务分配时间对比Fig.6 The comparison of task allocation time with time change

图7 AMR数量变化时的运行时间对比Fig.7 The comparison of system running time with the change of AMRs number

表1 AMR数量变化的运行时间提升量

图8表示任务数量变化时4种不同算法的系统运行时间.从图8中可以看出，随着任务数量增加，任务到达的密集程度必然增加，系统运行时间必然增加，但本文提出的算法任务数量大致在55～100之间系统运行时间能够获得较大提升，如表2所示，本文所提算法较之于节拍合同网协议(CNP)运行时间最差有8.4%的提升.

图8 任务数量变化时的运行时间对比Fig.8 The comparison of system running time with the change of tasks number

图9 时间变化时的运行时间对比

表2 任务数量变化的运行时间提升量

图9表示当任务到达时间长度变化时，4种不同算法的系统运行时间对比.从图9中可以看出，随着任务到达时间长度增加，4种算法的系统运行时间持续增大，但最后系统运行时间会呈现接近趋势.这是由于总体任务个数为100，刚开始SimpleGreedy，GR算法和节拍合同网协议(CNP)处理任务速度没有本文所提算法快，但随着任务到达时间长度增大，任务到达的密集程度降低，另外三种算法也能较快的处理任务.如表3所示，在10.3～14.1 min之间，本文所提算法与CNP相比，系统运行时间至少能有11.6%的提升.

表3 时间变化的运行时间提升量

6 结 论

本文研究了机场环境行李动态抵达情况下实时分配AMR小车的任务分配问题，在贪婪式分配算法的基础上，根据实时行李的规模和AMR集群状态，提出一种基于改进贪婪式的AMR任务分配与调度策略.本文算法与SimpleGreedy、GR算法和节拍合同网协议相比，行李量大致在55～100之间系统运行时间至少能够获得8.4%的提升；在本文所设定的值机岛场景下AMR数量在10～14之间系统运行时间至少能有7.6%的提升；任务在10.3～14.1 min之间抵达时系统运行时间至少能有11.6%的提升.