一种仓储AGV路径规划最优策略方法的实现

2021-08-03王海霞

计算机与网络 2021年9期

王海霞

摘要：路径规划是自动导引车系统（ AGVS）路径管理系统的关键技术，主要用来规划智能仓储中单台或多台自动导引车（ AGV）的作业路径。研究并检验了一种基于迪杰斯特拉算法的堆优化路径规划策略方法，通过仓库多台AGV路径规划案例，表明可以实现最优的单车及多车路径规划策略，缩短了车辆在仓库中的作业时间，提高了AGV的使用效率。

关键词：自动导引车系统路径管理系统;迪杰斯特拉算法;优化策略

中图分类号：TP23 文献标志码：A 文章编号：1008-1739（ 2021）09-63-4

Application of an Optimal Strategy Method for Warehouse

AGV Path Planning

WANG Haixia

（School of Application Technology， Suzhou Universiy. Kunshan 215325， China）

Abstract： The path planning is a key technology in the path management system of Automatic Guided Vehicle System （AGVS），which is mainly used to plan the operation path of single or multiple Automatic Guided Vehicles （AGV）s in intelligent storage. A pathplanning strategy for heap optimization based on Dijkstra algorithm is studied and tested. Through a path planning case of multipleAGVs in a warehouse. it is verified that this method can achieve the optimal path planning strategy for single vehicle and multiplevehicles. shorten the operation time of the vehicle in the warehouse. and improve the use efficiency of AGVs.

Keywwds： AGVS path management system; Dijkstra algorithm; optimizing strategy

O引言

目前國内对AGV的应用需求日渐增多，因其柔性好、可靠性高、适用性强的特点，并且能实现生产搬运功能的集成和自动化，在各个行业中都得到广泛应用，其需求量正以井喷式的势头增长，如智能立体库、智能工厂、海港及码头等，随着自动化立体仓库和柔性制造系统的广泛应用，AGV作为智能物流系统连续化的重要组成部分，其精确性和高效性起着至关重要的作用[1]。

仓储AGV路径规划的最优策略方法，能够对AGV进行最优策略下的单车调度和多车调度，提高了AGV运行效率。目前这种调度方法成功用于仓储智能化物流系统，经现场证实，这种路径规划策略快速、准确、有效，比普通方法减少耗时15%以上。文中最优策略方法的实现采用了基于Dijkstra的堆优化算法，是最短路径优化算法之一，结合路径管理系统的starPlantOverview程序，能够实现AGV在智能仓储中的应用。

1仓储AGV路径管理系统的功能

仓储AGV路径管理系统有以下几个功能：监控管理、路径规划、交通调度控制、车队管理和智能交互，功能描述如表1所示，主要目的是管理、监控和调度AGV执行搬运作业任务。系统接收工厂信息管理系统（ ERPIMESIWMS）的作业任务，对AGV进行自动交通管理、监控和接收AGV的状态信息，并向工厂信息管理系统反馈任务执行情况。AGV则通过无线网络与系统通信，按照规划的路径执行作业任务。

2路径优化算法策略

路径管理系统的关键技术是路径规划，在进行路径选择时必须高效规划出一条从起始位置到目标位置的最优路径，通常采用最短路径的策略，在一个赋权图中找到一个节点到周围所有节点具有最小权的路径。这是因为在线路优化中，如果优化指标与路程的相关性较强，而与其他因素相关性较弱时，即以最短路程为准则[2]。比如仓储或车间运输线路选取时，从出发地到目的地之间有多种线路可以选取，效率指数在预测概率相等时，考虑以最短路径为准则[3]。本文路径规划使用的是在迪杰斯特拉算法基础上的优化算法。DIJ算法是求解单源最短路径问题的经典算法，常用于智能车在非结构化静态环境中进行路径规划，是一种按路径长度递增的次序产生最短路径的算法，核心思想是以遍历形式找到图中所有节点的最短路径，可求单源有权图中的最短路[4-6]。

DIJ算法时间复杂度为O（（m+n ）logn），m表示边数，n表示点数，在实际应用中速度慢、效率低。但如果使用优先队列进行堆优化，优化后每次调整的时间复杂度降为0（ elogn），其中e为顶点边数，这种优化时效}生较好。堆优化的原则是使用小根堆，用优先队列来维护这个最小的点，从而大大减少DIJ算法的时间复杂度，算法步骤如表2所示。堆优化是利用堆这种数据结构所设计的一种排序算法（此处针对小根堆），每次将堆顶提出，即为当前最小值，将堆的末端子节点放到堆首，之后与左右节点比对，与其中较小的交换，直到堆中的最小值位于根节点重新成为小根堆。

在堆中假设s为源点，t为终点，u为边界点，v为内部点。首先将源点设为边界点dis，令其为O，其余点为外部点。将所有边界点加入堆中，每次取堆顶元素（非边界点而是内部点），每个点的dis值会更新多次，每次入堆最小的dis值最先出堆，出堆时更新其周围点的dis值，并将其加入到内部点中，继续循环，直到找到终点的最短路径就可以提前退出循环，这其中一个点的dis值会被更新多次并多次入堆，直接在堆里更改它的dis值，并重排堆元素，时间复杂度仍旧是O（logn）。

基于DIJ堆优化算法程序流程如图1所示，其特点在于：

①不必扫描1-n，只需遍历由pos顶点可以到达的顶点即可，使用vector存储图，或者使用链式前向星;

②每次找出一个距离源点最短的顶点，然后把这些点存起来，按照距离关键字进行查找;

③内部实现为小根堆，满足动态的插入，在0（1）的时间内直接取出最小点并结合①，使得总时间复杂度从O（nX2）降到O（Vlogn+VE），對稀疏图很有效果。

3基于堆优化策略的项目应用

本路径管理系统优化策略在多个项目中使用，在管理软件中运行starPlantOverview程序，完成项目路径制作，系统对接工厂制造执行计划系统ERP和智能化仓储系统WMS，按照存储要求，实现生产原料和成品的自动出入库。以系统在智能化仓储系统项目中的具体应用来说明堆优化实际应用，该仓库由新旧2间立体库组成，总建筑面积650 1112，如图2所示。其物流系统主要采用AGV方式和人工入库方式相结合，项目使用了3台激光导向AGV系统，货架通道设置为2.8 m，行驶通道设为3m。

当路径管理系统接收到ERP/MES/WMS的有效任务指令后，系统按照DIJ堆优化原则选择AGV最优路径，分配作业任务给空闲AGV，同时生成有效路径图，如图3所示，AGV按照系统路径指令执行任务，任务流程如图4所示。当3台AGV同时工作时，按照入货口分开原则并遵循特定的路径规划策略，以确保AGV不会发生碰撞，规划策略主要有速率调整法、交通规则法和优先级法。

主要流程如下：

①当两车在十字路口相遇时，根据时间优先法进行车辆选择，先申请占用点位的车辆通过路口，后申请车辆采用速率调整法在原点位等待，当前车通过后，隔离区解除再行通过。

②当两车占用一条路线时，通过枚举重叠进行相同方向和交叉路口构建重叠路线的交通规则来进行避撞。

③按照入货口产品和原料的状态要求，为每台AGV制定优先级。当优先级低的AGV遇到优先级高的AGV时，低者给高者让路并在重叠路径最近点位进行等待。

④同时在启动任务中设置充电和停靠任务并绑定所有车辆，根据三段式电量百分比指标对车辆进行充电指示;当车辆完成装卸且无新住务后，按照就近停靠原则停泊。

在该项目中假设源点为s点并将它设为边界点，dis[s]-0，其余点为外部点，将所有边界点加入堆中，建立2个数组dis和VIS，dis[i]表示从源点出发到编号为i点的距离，即DP1一{v}，DP（n）包含除s外的其他DP点，DP（n）的dis值为无穷大，如果找到一条s到达点j的更短路径，dis[J]将更新为这条更短路径的距离，vis[j]表示j点的dis[j]，vis[j]=true表示j点的dis值已经确定是最小值，初始时所有点的VIS值都为false。每次取堆顶元素，最小的那个dis值最先出堆，出堆时更新其周围点的dis值，并将其加入到内部点中，只要找到终点的最短路径则提前退出，如果没有继续用递归算法使根节点为最小值，重复以上步骤，直至所有点的VIS值都为true。

项目实施过程中，分别采用了Dijkstra算法路径规划和基于Dijkstra的堆优化算法路径规划进行AGV作业测试，调度分2种情况：

①规划20个DP点：堆优化算法耗时比DIJ算法的调度系统少（m一2）[（ L1/S1）+（ L2/S2）]。

②规划20个DP点、5个转弯，堆优化算法耗时比DIJ算法的调度系统少（m一2）[（L1/S1）]+（ L2/S2 ）l+Tt。其中，L1为减速距离;S1为减速度;L2为加速距离;S2为加速度;T1为可能产生的多余转弯耗时。

根据现场统计，在相同DP点个数情况下，该算法可以节约时间4 sl点;在相同个数DP点情况下和相同转弯个数情况下，该算法可以节约时间4 sl点+5 s（多余转弯耗时）。

4结束语

针对智能立体库AGV路径规划问题，介绍了一种AGV路径规划最优策略方法在实际项目中的应用。以堆优化算法弥补了DIJ算法耗时长效率低的缺点，并通过某仓储智能物流路径规划在车辆调度中的实际应用，验证了优化算法时间复杂度的降低，提高了AGV的执行效率。

参考文献

[1]李炜文.自动化立体仓库AGV路径规划研究[D].长春：吉林大学，2020.

[2]余娜娜，李铁克，王柏琳，等.自动化分拣仓库中多AGV调度与路径规划算法[J].计算机集成制造系统，2020，26（1）：171-180.

[3]吴家琴.基于迪克斯特洛模型的物流运输最短路径选择[J].物流技术，2013，32（21）：193-195.

[4]李全勇，李波，张瑞，等.基于改进Dijkstra算法的AGV路径规划研究[J].机械工程与自动化，2021（1）：23-25.

[5]郭亚铭，武照云，张中伟，等.柔性制造车间单AGV节能路径规划研究[J]组合机床与自动化加工技术，2020（10）：181-184.