浙江工业大学研招网(浙江工业大学研招网官网)
浙江工业大学研招网，浙江工业大学研招网官网
广告 | 点击查看
近期，浙江工业大学鲁建厦教授团队在Computers & Industrial Engineering（IF:7.18）上发表了题为An automated guided vehicle conflict-free scheduling approach considering assignment rules in a robotic mobile fulfillment system（《一种在RMFS中考虑分配规则的AGV无冲突调度方法》）的论文。
本文共 3179 字，预计阅读需要15分钟
论文摘要 Abstract
AGV作为一种物料搬运设备已在各行业广泛应用，在制造业的自动化仓库中尤甚。仓库的工作效率与订单的拣选环节息息相关，在特定时间内，随着AGV拣选任务量增加，多台AGV发生冲突和死锁的频率也随之增加，进而对整体效率产生负面影响。
本文提出了一种考虑分配规则的多台AGV调度方法(MASA)，并设计了一种在仓库中有多工作站的情况下，多台AGV生成无冲突工作路线的方法。与以往研究的多工作站随机分配规则不同，本文提出了基于拥挤的分配规则(CAR)和基于开放时间的分配规则(OTAR)来调整AGV的工作路线的方法，可以缓解AGV在工作站堵塞的情况。
本文建立了基于时空网络的AGV总完成时间最小化调度模型，设计了解决AGV无冲突调度问题的协同优化算法，数值实验验证了该算法的有效性和稳定性。在相同的工作负载下，CAR和OTAR比传统随机分配规则的总完成时间分别减少了5.55%和9.56%；基于分类存储模式下，完成时间分别减少了8.01%和12.13%。当仓库有大量的拣选任务和多工作站时，MASA有很大潜力能有效提高仓库系统的效率。
01
“货到人”的下半场
2012年，亚马逊耗资7.75亿美元收购Kiva systems，在自家仓库中大规模布置Kiva机器人，将货架从仓库搬运至人工拣选站，开启了“货到人”拣选的智能时代。如今，移动机器人履约系统（RMFS）已被仓储物流、制造业等领域广泛应用。
RMFS是由大量AGV代替人工拣选的系统。AGV的速度随着技术发展逐渐变快，同时企业要求订单响应时间更短，提高效率迫在眉睫。许多中型、大型仓库普遍配备多个工作站以提高仓库整体效率，但单纯增加数量，并不能彻底解决这一问题。由于存储区的货架到各工作站的距离不同，AGV将待拣选货架运送到工作站的行程时间也不同。将货架分配到距离最近工作站的分配规则看似可以减少AGV的行驶时间，实则会导致工作站之间的工作负载不平衡。此外，运输待拣选货架的AGV在工作站排队等候时，会造成工作站堵塞，甚至严重延误订单拣选环节的进程。
配有多个工作站的RMFS如何避免浪费时间，提高系统效率呢？答案是：更好地解决AGV路径规划问题。作为RMFS领域研究的热点问题，AGV路径规划的相关研究很多，有基于AGV充电时间、AGV转弯时间、AGV速度、AGV冲突和死锁等不同研究方向。其中，AGV冲突和死锁领域是多AGV路径规划的核心问题之一。诸多学者提出了诸如基于两层控制架构的AGV无冲突路径生成集成算法；基于当前AGV占用时间窗的贪婪最优先搜索和选择冲突避免策略的A*算法；基于动态规划和时间窗的算法等等研究成果。
多台AGV同时工作时，考虑AGV与工作站之间的交互作用，通过拣选任务的优先级来合理调度货架搬运顺序具有十分重要的意义。目前，研究者对AGV路径规划与调度问题的协同优化研究较少。无论是路径规划问题，还是调度问题，大多数研究都只关注了拣选任务与AGV之间的分配问题，而忽略了AGV与工作站的交互。AGV的完整工作过程通常被建模为排队网络模型，该模型不能准确描述AGV运行过程中的冲突和死锁。此外，大多数研究也并未考虑工作站运行时间对AGV工作路线和系统效率的影响。
02
“狭路相逢勇者胜”
想要解决上述问题，我们还得从RMFS的基础配置情况和AGV的基本冲突类型说起。
一个典型的RMFS系统包括一个AGV停车区，一个存储区，货架存储在矩形块中，仓库西侧配有多个工作站。AGV在工作站和存储区之间运送货架。一台AGV一次只能携带一个货架。闲置AGV可以穿过货架底部，但当AGV携带货架时，它只能沿着巷道行驶。此外，每个工作站都配有一个缓冲区，AGV在工作站和缓冲区沿指定方向行驶，携带货架的多台AGV在缓冲区等待排队。
在RMFS中，多台AGV在窄巷道或交叉巷道中执行订单任务时，发生冲突是不可避免的。路只有一条，但AGV没有“狭路相逢勇者胜”这么一说。想要化解冲突提高效率，先要了解冲突有哪些类型。一般来说，AGV冲突主要有三类：
相对冲突：两台AGV在窄巷道相遇
等待冲突：正在等待中的AGV挡住了另一台AGV的行进路线
相遇冲突：两台优先级不同的AGV在转角处相遇
每个AGV的当前工作状态可以反映其拣选任务的执行情况，因此工作状态在AGV路径规划和优先级分类中起着重要作用。AGV的工作状态具体分为以下四步:
1.AGV移动到待拣选货架的存放位置
2.AGV将货架运送至工作站
3.AGV将货架返回储存区
4.AGV完成所有任务，返回停车区
03
AGV如何回避冲突？
传统RMFS的AGV调度方法倾向于将工作站视为一个拣选区，或倾向于将工作站随机分配给AGV。若在此基础上优化AGV与待拣选货架的分配问题及货架的运输顺序，可以减少货架移动次数，进而缩短作业时间。不过路径规划问题的复杂程度和AGV数量与工作站复杂程度正相关，多台AGV在多工作站的RMFS中工作时，AGV冲突的概率和AGV在多个工作站的等待时间很可能会增加，从而延迟AGV的后续运行和系统完成时间。
分配规则会影响AGV的后续行驶路线，因此有必要将其纳入RMFS调度问题的考量范围。针对这一问题，鲁建厦教授团队通过设计新的分配规则来优化AGV的工作效率，同时缓解AGV之间的冲突。冲突回避的具体过程如图所示。团队考虑时间成本和系统效率，以AGV编号、工作状态和接受任务先后顺序来确定AGV的优先级，并将订单周期性地动态分配给AGV。具体步骤如下:
步骤1:根据AGV前一阶段结束时间对AGV优先级进行排序，结束时间较早的AGV优先级越高。如果有多个AGV具有相同的结束时间，则转到步骤2，否则转到步骤3。
步骤2:以AGV当前搬运状态作为评价指标，携带货架的AGV优先级高于空闲AGV。
步骤3:根据AGV编号确定剩余AGV的优先级。AGV编号越小，其优先级越高。
04
模型假设&算法提出
时空网络模型分别以时间和空间为轴，将一维物理网络扩展为二维时空网络，可以有效地利用空间和时间的信息。在网络流问题中，AGV之间的冲突和AGV在工作站等待时长可以看作是时间窗口约束。时空网络可以更直观地表示AGV的状态，减少了时间和空间之间的关系约束。因此，鲁建厦教授团队决定应用时空网络理论来解决拥有多工作站的RMFS中的AGV调度和AGV路径冲突问题。
模拟退火算法具有受初始解的影响小、全局搜索能力强等特点，其采用多邻域结构交替搜索和Metropolis准则，是解决组合优化问题最常用的算法之一，在调度问题上有广泛应用。鲁建厦教授团队设计了一种考虑任务分配和路径规划的启发式算法来解决多台AGV调度问题，算法流程图如下。
05
实验结论与局限
考虑到分配规则对AGV后续行驶路线和系统完成时间的影响，鲁建厦教授团队基于拥挤的分配规则(CAR)和基于开放时间的分配规则(OTAR)，提出了一种考虑分配规则的多台AGV调度方法(MASA)，针对RMFS中AGV与工作站之间的分配问题和AGV无冲突路由问题，生成了一种有效的AGV调度方案。
该方法通过实现无冲突路由和分配规则的协同优化，提高了RMFS的工作效率。此外，该篇论文建立了RMFS中AGV调度的时空网络模型，提出了一种获取工作路径的协同优化算法。论文通过一系列数值实验，对比了新提出算法与TS和SA-I算法的结果，通过数据证明了新提出的算法具有更好的有效性和稳定性。此外，论文对三种分配规则的实验结果进行了比较，CAR和OTAR可以实现比传统RAR更好的效果。不过文章并没有详细讨论RMFS中AGV、工作站和其他配套设备的瓶颈问题，以及多AGV在大型仓库、多种仓库布局下的调度问题。
物流企业除了通过“简单粗暴”地增加工作站和AGV的数量来提高仓库运行效率外，还可以通过合理匹配工作站、AGV和拣选任务三者来提高系统效率，降本增效，在注重时效性的前提下实现内部物流运营精细化。本文所提出的分配规则和AGV调度算法可以帮助从业者将工作站分配给有拣选任务的AGV，并生成无冲突的AGV工作路线，可以在节约成本的前提下提高RMFS的潜在系统效率。
此外，这一AGV调度算法也可扩展到其他AGV物料搬运的应用场景，如转运、作业车间等。
06
编译、排版：罗丹
广告宣传
浙江工业大学研招网(浙江工业大学研招网官网)