动态优先级策略下快递分拨中心多AGV路径规划

动态优先级策略下快递分拨中心多AGV路径规划

田帅辉 樊略
重庆邮电大学现代邮政学院

随着电子商务迅猛发展,快递包裹业务量不断扩大,2021 年全国快递包裹超过 1083 亿件。随着快递包裹数量的逐年递增以及消费者对快递时效性需求的增加,传统快递分拨中心使用人工进行分拣作业已经无法满足现实要求。在此背景下,兼备柔性、效率和成本优势的无人搬运车 (Automated GuidedVehicle,AGV)快递分拣系统应运而生。AGV 优势明显,一台 AGV 工作量可抵 8-12 个人工劳动力,自动化快递分拨中心可以实现 24 小时作业,不仅大幅降低人工成本,还能提高作业效率。合理规划路径并解决路径冲突问题、缩短 AGV的总运行时间是提高 AGV 作业效率的关键,也是当前的研究热点之一。

基于快递分拨中心环境,为 AGV 规划无冲突路径,能减少 AGV 运行时间,提高 AGV系统作业效率。本文研究的是多 AGV 在运行过程中寻找最优路径并解决路径冲突的问题。

多 AGV 间的协同路径规划和冲突处理是实现基于多 AGV 的自动化快递分拨中心的关键。目前,国内外有许多学者对 AGV 路径规划问题进行了研究,在单 AGV 路径规划方面,相关学者重点对 A算法[1-2]、Dijkstra 算法[3-4]、蚁群算法[5-6]、遗传算法[7-8]等智能算法进行优化和改进,以得到更优的初始路径,对每台AGV 进行初始路径规划的效果将极大程度上影响该系统的运行效率。而对于多 AGV 系统,在进行路径规划的同时需要解决路径冲突问题,情况更为复杂。刘国栋[9]提出一种两阶段动态路径规划策略,离线阶段生成各节点之间备选路径库,在线阶段优化路径,但其离线阶段生成路径过于理想化,由于路径复杂度的问题,随着节点数增多会带来实时性的问题。李昆鹏[10]针对路径规划与调度问题提出两阶段优化算法,第一阶段根据规则生成初始路径,第二阶段检测潜在碰撞点并解决碰撞,但其仅考虑货架优先级未考虑行驶过程中 AGV 优先级的变化。Ma[11]采用结合全局优先级的 A算法与局部协调控制搜索各 AGV 路径,但其未处理冲突问题。Desaulniers G[12]等人使用改进贪心算法为少量 AGV 进行路径规划,但无法解 决 拥 堵 问题 。 针 对 冲突 和 死 锁 问题 ,Smolic-Rocak N[13]等采用时间窗模型将 AGV间的冲突转化为道路资源的竞争,但该方法着重于碰撞的预测,无法直接解决冲突,需要结合其他方法实现 AGV 的冲突解决。多 AGV路径规划常使用优先级策略解决冲突问题,实践已证明其有效性。Umar[14]等通过遗传算法对 AGV 系统进行路径规划,通过设立优先级的方式解决路径冲突问题。张新艳[15]等分析节点到达时间并以电量与路径性能为指标为AGV 分配优先级,但优先级固定无法动态调节;张中伟[16]等首先划分冲突类型并使用时间窗进行检测,然后将等待时间、行驶距离、任务紧急程度作为量化动态优先级的指标,最后根据动态优先级选择冲突消减的方法,但其在进行优先级评价时未考虑 AGV 电量因素。

传统两阶段路径规划方法采用离线生成候选路径数据库,再根据候选路径进行总体路径规划。离线阶段生成不同点之间的理想路径,在线阶段再根据地图信息进行局部路径调整。该方法在离线路径规划阶段由于没有考虑AGV 对地图占用,选出的初始路径之间容易产生冲突。借鉴该思路,本文采用先静态后动态的两阶段路径规划方法。在静态路径规划阶段,将其他 AGV 视为环境障碍物,规划出每辆 AGV 的初始路径;在动态路径规划阶段,对初始路径进行调整实现多 AGV 的无冲突路径规划。相较于传统两阶段路径规划方法,该方法能提前考虑 AGV 对道路的占用,有效减少 AGV 冲突。

两阶段路径规划方法可以降低 AGV 之间的冲突概率,但随着数量的增加无法完全避免冲突,因此需要制定解决 AGV 冲突问题的方案。现阶段解决多 AGV 冲突问题通常采用固定优先级策略,即在执行任务之前就确定每一辆 AGV 的优先级。该方法无法考虑任务的相对重要性,因此不能及时完成时效性要求高的任务;并且低优先级 AGV 可能长时间处于等待、避让状态造成路网节点堵塞,也导致长时间不能完成任务。因此,本文针对快递分拨中心多 AGV 无碰撞路径规划问题,对该场景常见碰撞类型进行分类并设计避碰规则;综合考虑 AGV 电量、包裹时效性要求以及路径代价等因素设计动态优先级评价策略,即在 AGV执行任务发生冲突时,根据各 AGV 在当前节点的实时优先级决定通过节点的顺序。此外,针对传统 A算法规划路径存在无意义转向的不足,对 A算法进行改进引入“转向惩罚”减少寻路过程中的无效转向,从而构建一个安全、稳定、灵活的自动化快递分拨中心系统。

1 问题描述及建模

1.1 问题描述

该问题可描述为:快递分拨中心中存在大批量包裹投递任务、多个 AGV 小车,在 AGV领取包裹后,需要为每辆 AGV 规划路径,AGV 在执行任务时成为彼此的动态障碍物,会产生路径冲突,因此需要解决 AGV 的路径规划以及冲突解决问题,即每辆 AGV 什么时间通过哪条路径的问题。在一定的约束条件下,为 AGV 选择最优行驶路径,并在发生冲突时根据各包裹的优先级解决冲突。本文主要解决AGV 路径规划以及运行过程中的动态避碰的问题,属于组合优化问题。

快递分拨中心中多 AGV 路径规划需要规划出较优路径且避免 AGV 间碰撞达到协同作业,主要由单个 AGV 路径规划和多 AGV 冲突解决两层构成。其中,第 1 层是路径规划层,忽略快递分拨中心中其他 AGV 的影响,使各AGV 在各自的起点与终点间寻找到可通行空间内的最优路径。第 2 层是冲突解决层,采用避碰规则解决快递分拨中心 AGV 间的冲突问题,寻找最优路径组合,保证快递分拨中心多AGV 能够顺利完成包裹投递任务。

1.2 环境建模

本文以菜鸟与圆通共建的“超级机器人”分拨中心为基础构建环境模型,该模型能充分利用快递分拨中心空间,并提供一个规则且利于 AGV 作业的环境,如图 1 所示。图中用栅格地图表示快递分拨中心环境,栅格地图由以下部分组成:①分拣台:位于地图边缘,AGV在此领取包裹;②道路:用于 AGV 行驶;③包裹投递区:根据包裹的收货地址,在地图上散布多个投递区;④AGV:在地图中行驶并搬运包裹;⑤包裹目的地:包裹目的地对应包裹投递区,AGV 需行驶至包裹目的地对应包裹投递区进行投递;⑥障碍物:占据空间导致AGV 无法经过的区域;⑦停靠区:用于空闲AGV 的停靠及充电,当前电量低于阈值或完成所有任务时返回停靠区进行充电。

图片[1]-动态优先级策略下快递分拨中心多AGV路径规划
图 1 快递分拨中心示意图

栅格法具有简化地形环境,且易于实现的优点,能保证所构建环境的有效性,基于此,本文选用栅格法对快递分拨中心环境进行简化建模。将快递分拨中心实际作业环境简化为二维平面图形,称该平面图形为栅格地图。地图中存在若干单位大小的栅格,将所有栅格分为障碍栅格(不可通行)和可行栅格(可自由通行),分别用黑色和白色表示。快递分拨中心示意如图 2 所示,其中左侧栅格代表分拣台,即 AGV 领取包裹任务的地点,不可通行;中间黑色栅格代表投递区,即 AGV 投递包裹的地点;右侧黑色栅格代表停靠区,即 AGV 停放与充电的区域,不可通行;白色栅格代表道路,即 AGV 作业的自由可行空间。

图片[2]-动态优先级策略下快递分拨中心多AGV路径规划
图 2 栅格地图

基于快递分拨中心场景提出以下假设:

1) 所有 AGV 型号相同;
2) 地图中每一个栅格为长度为2m的正方形;
3) 栅格图中道路为单通道双向行驶;
4) AGV 有前进,左、右垂直转向三种运动方式;
5) AGV 运动时保持匀速行驶,为 1m/s,不考虑加减速,考虑转弯时间,设转弯时间为
6) 每一栅格仅可容纳一辆 AGV;
7) AGV 每次执行一个包裹任务,完成任务后到下一包裹所在分拣台;
8) AGV 电量低于阈值时,优先完成当前任务随后前往停靠区进行充电。

2 静态路径规划

目前常用的路径规划算法主要有 A算法、Dijkstra 算法、蚁群算法和遗传算法等。A算法拥有计算速度快、路径短等优点,是目前处理有障碍物的智能寻路最常用的方法,因此本文采用 A*算法解决静态路径规划问题。

2.1 传统 A*算法的不足

传统的 A算法在实际应用中会产生过多非必要转向,而快递分拨中心中 AGV 过多的转向不仅会增加额外的运行时间,降低系统运行效率,还会因为惯性产生包裹掉落的风险。因此,本文在传统 A算法的基础上引入转向惩罚以减少转弯次数。

采用传统 A*算法进行 AGV 路径规划虽然能获得一条安全无碰撞的路径,但在快递分拨中心场景中容易出现非必要转向,使得AGV 在实际应用中将消耗更多的能量和时间。如图 3 所示,图中黑色方格为障碍物,从起点S 寻找至终点 D 的最短路径,图中两条路径的长度相同。

动态优先级策略下快递分拨中心多AGV路径规划-AGV吧
动态优先级策略下快递分拨中心多AGV路径规划
此内容为免费资源,请登录后查看
积分
免费资源
© 版权声明
THE END
喜欢就支持一下吧
点赞5 分享
评论 抢沙发

请登录后发表评论

    暂无评论内容