基于动态时间窗的泊车系统路径规划研究

针对智能立体停车库中自动导引运输车(automated guided vehicle,AGV)存取车路径规划问题,采用分时利用策略,将Dijkstra算法和时间窗法有效结合,提出了一种基于动态时间窗的泊车系统路径规划方法。首先,通过引入优先级策略为接收任务的AGV设定优先级;其次,采用Dijkstra算法,按照任务优先级高低次序,依次为接受任务的AGV规划出最短可行路径;最后,在已知AGV可行路径基础上,通过对可行路径各路段的时间窗进行初始化、实时更新以及实时排布处理,实现多AGV的无冲突路径规划。为验证所提方法的可行性和有效性,以4台AGV同时工作的智能立体停车库为实例进行仿真测试。结果显示:所提出的路径规划方法不仅有效解决了目前多AGV路径规划柔性差、易出现死锁、碰撞冲突等问题,而且可在有效解决路径冲突的前提下,为接受任务的AGV规划出一条时间最短的优化路径。所提方法具有较好的鲁棒性和柔性,有效提高了智能立体停车系统整体运行效率,降低了存取车等待时间。     

考虑冲突避免的多AGV路径规划研究

目的 提高物流企业“货到人”拣选系统在实际生产中的工作效率，避免自动导引小车(AGV)间的冲突死锁，研究大规模多AGV的无冲突路径规划和协同避障问题。方法 首先考虑AGV空载、负载情况和路径扩展成本，改进A^*算法，动态调整代价函数，优化路径扩展方式。其次，提出冲突检测及避免算法，对可能产生局部冲突的路径交叉点进行避障调度，通过预约锁格，实现局部冲突的检测，制定优先级避障策略，解决AGV动态行驶路径上产生的局部冲突和死锁，进而实现全局无冲突路径规划。结果 对多组不同任务量和不同AGV规模的场景进行仿真，实验结果表明，考虑冲突避免的改进A^*算法能有效实现100个任务、90个货架单位和7个拣选站场景下的多AGV动态路径规划，相较于传统A^*算法，其平均拣选时长缩短了52.61%。结论 该方法可实现大规模场景下的多AGV动态路径规划，在付出较小转弯代价的同时有效避免局部动态冲突，该方法可为相关企业实现多AGV协同调度提供新的思路和理论依据。     

基于Dijkstra-蚁群算法的泊车系统路径规划研究

针对智能停车库中自动导引运输车(automated guided vehicle,AGV)存取车路径规划问题,提出了一种基于Dijkstra-蚁群算法(Dijkstra-ACO)的泊车系统路径规划方法.首先利用链接可视图法建立环境模型,并在此环境模型下,采用Dijkstra算法规划出AGV的初始路径;其次,通过引入节点随机选择机制、调整信息素更新方式和限定信息素阈值策略等对基本蚁群算法进行优化改进;最后,选用改进的蚁群算法对初始路径进行优化.结果显示:Dijkstra算法和混合算法均能使AGV有效避开障碍物,然后搜索到一条从起点到终点的无碰优化路径;与Dijkstra算法相比,混合算法能有效提高路径搜索效率,缩短搜索路径长度,改善搜索路径质量,表明该算法正确、可行及有效,且具有较强的全局搜索能力和较好的收敛性能,能够满足AGV存取车路径规划的要求.     

基于改进自适应遗传粒子群混合算法的多AGV路径规划研究

针对仓库中AGV的路径规划问题,该文提出了一种改进自适应遗传粒子群混合算法。首先,根据算法搜索进度修改权重和学习因子,采用一种新的非线性权重系数,两者根据迭代而动态变化。其次,动态调整交叉和变异概率参数。最后,为了避免多AGV出现路径冲突,在适应度函数中引入拥堵系数对拥堵路段进行惩罚。结果表明,与已有的改进遗传算法和改进粒子群算法相比,该文采用的改进自适应遗传粒子群混合算法搜索最优路径的长度更短、搜索范围更广。     

基于改进DQN算法的无人仓多AGV路径规划

针对无人仓中多AGV路径规划与冲突问题,以最小化总行程时间为目标,建立多AGV路径规划模型,提出一种基于动态决策的改进DQN算法。算法设计了基于单AGV静态路径规划的经验知识模型,指导AGV的学习探索方向,提前规避冲突与障碍物,加快算法收敛。同时提出基于总行程时间最短的冲突消解策略,从根本上解决多AGV路径冲突与死锁问题。最后,建立无人仓栅格地图进行仿真实验。结果表明,本文提出的模型和算法较其他DQN算法收敛速度提升13.3%,平均损失值降低26.3%。这说明该模型和算法有利于规避和化解无人仓多AGV路径规划冲突,减少多AGV总行程时间,对提高无人仓作业效率具有重要指导意义。     

路径优化算法求解集装箱码头堆场翻箱问题

集装箱翻箱问题(CRP)可描述为在集装箱堆场现有堆垛状态和提箱序列确定情况下,以最少的翻箱数量提取出堆场箱区内所有集装箱;CRP是一个NP-hard问题。为此构建双层目标规划模型,提出嵌套翻箱规则的路径规划算法(POA),以期减少解空间大小,从而在更短的CPU运行时间内得到CRP的最优解。数值实验结果表明,POA在翻箱数量及运行时间上均优于多数算法,有效提高集装箱码头堆场作业效率,更适用于求解集装箱码头翻箱作业优化问题。     

一种新型包装码垛机器人路径规划方法

目的为了提高码垛机器人的工作效率,减小能量损耗,优化机器人末端抓手的工作轨迹。方法建立机器人路径规划的数学模型,在此基础上对传统的蚁群算法进行改进,将环境中局部的机器人路径信息引入蚁群信息素的初始化和路径选择概率中,提高蚁群算法的收敛速度,并防止算法早熟,避免算法陷入局部最优。结果仿真结果表明,改进后的蚁群算法收敛速度更快,能够在较短时间内规划出最佳路径。结论所提方法能够明显提高码垛机器人最佳路径搜索能力,对于提升机器人运行效率具有重要指导意义。     

自动化集装箱码头运输系统配置的仿真优化

以新型自动化集装箱码头中间运输系统为研究对象,建立了自动化集装箱码头中间运输系统的仿真优化模型,并利用仿真优化方法搜索优化调度方案,最小化船舶靠岸后装卸作业的总时间和最大化各种设备的操作效率,优化模块使用遗传算法,整个程序使用C#语言编制.通过仿真计算表明能够非枚举地从所有可能的动态调度方案中搜到最佳方案:运输系统的设备利用率、系统作业时间,都得到了相应改善.     

智能电能表自动化检定的省级协同调度探讨

为实现国网范围内智能电能表自动化检定能力共享、适应智能电能表差异化、波动性的需求特点,本文探讨了智能电能表自动化检定的省级协同调度策略。首先,提出了层次动态任务调度机制,以实现自动化检定车间系统及设备运行状态的实时管控;基于模块化思想设计自动化检定车间的生产调度系统;设计了基于时间窗的自动导引车(Automated Guided Vehicle,AGV)路径冲突规避算法,以提高AGV的传送效率;其次,提出了基于自适应混合作业协同域的生产调度柔性管理策略;其研究成果已得以应用,取得了初步成效,满足了智能电能表的用表需求。     

时变环境下基于AGV运动学模型的无碰撞路径规划研究

自动导引小车(AGV,Automated Guided Vehicle)由于采用无人驾驶,高度自动化、高度智能化的优点被广泛应用于柔性制造系统和工厂物流自动化领域,使得生产效率以及自动化程度大大提高.目前AGV的运动,无论是磁条导航、二维码导航、或是激光导航,都是沿着预先设定的路径进行运动的,并不具有自主导航功能.本文针对工厂、医院、商场、博览会等存在运动障碍物的环境下,在考虑AGV运动学模型及运动约束的前提下,进行时变环境下AGV自动避障、自主导航研究,并提出相应的实时路径规划算法.所提出的算法在Matlab上进行了仿真实验,验证了算法的有效性和可行性.     

Deadlock prevention for automated guided vehicles in automated container terminals

Automated guided vehicles (AGVs) are an important component for automating container terminals. When utilizing AGVs to transport containers from one position to another in a container terminal, deadlocks are a serious problem that must be solved before real operations can take place. This study assumes that the traveling area for AGVs is divided into a large number of grid-blocks, and, as a method of traffic control, grid-blocks are reserved in advance when AGVs are running. The first purpose of the reservation is to make room between AGVs and to prevent deadlocks. The objective of this study is to develop an efficient deadlock prediction and prevention algorithm for AGV systems in automated container terminals. Because the size of an AGV is much larger than the size of a grid-block on a guide path, this study assumes that an AGV may occupy more than one grid-block at a time. This study proposes a method for reserving grid-blocks in advance to prevent deadlocks. A graphical representation method is suggested for a reservation schedule and a priority table is suggested to maintain priority consistency among grid-blocks. It is shown that the priority consistency guarantees deadlock-free reservation schedules for AGVs to cross the same area at the same time. The proposed method was tested in a simulation study.     

考虑有限物流运输能力的智能车间AGV调度算法研究

以大批量生产模式智能车间为背景,针对单环布局下多自动导航小车 （AGV） 的调度问题进行研究。首先,对典型智能车间特点进行了分析,利用Plant Simulation仿真平台建立了基于实际生产场景的仿真模型;其次,提出了基于软时间窗的AGV调度规则和基于备选调度规则集的6个运行机制;最后,通过设计仿真实验对上述7个调度规则进行了分析和比较。实验结果表明,基于软时间窗AGV调度方法总体上表现更好。这为企业配置和调度AGV小车提供了决策支持。     

Scheduling and routing algorithms for AGVs: A survey

Automated guided vehicles (AGVs) are now becoming popular in automated materials handling systems, flexible manufacturing systems and even container handling applications. In the past few decades, much research has been devoted to the technology of AGV systems and rapid progress has been witnessed. As one of the enabling technologies, scheduling and routing of AGVs have attracted considerable attention. Many algorithms for the scheduling and routing of AGVs have been proposed. However, most of the existing results are applicable to systems with a small number of AGVs, offering a low degree of concurrency. With a drastically increased number of AGVs in recent applications (e.g. in the order of a hundred in a container handling system), efficient algorithms are needed to resolve the increased contention of resources (e.g. path, loading and unloading buffers) among AGVs. This survey paper first gives an account of the emergence of the problem of AGV scheduling and routing. It then differentiates it from several related problems and classifies major existing algorithms for the problem. Finally, the paper points out fertile areas for future study of AGV scheduling and routing.     

A bi-directional path layout for conflict-free routing of AGVs

Automated Guided Vehicles (or AGVs for short) are now widely used in automated material handling systems. Much research has been done on developing path layout and algorithms for the optimal routing and scheduling of AGVs. However, with the drastically increased number of AGVs in some recent applications (e.g. in the order of a hundred in container terminals), algorithms that can achieve a high degree of concurrency of AGV moves are urgently needed. This paper presents a bi-directional path layout and an algorithm for routing AGVs. To route the vehicles without conflicts and to minimize the space requirement of the layout, critical conditions for certain key parameters of the path and vehicle are derived. We further show theoretically that a high degree of concurrency of AGV moves can be achieved, although the routing decision takes only a constant amount of time for each vehicle. The routing efficiency is analysed in terms of the distance traversed and the time requirement for AGVs to complete all pickup and drop-off (or P/D for short) jobs. Results of this study could form a basis for more complicated path layouts and routing algorithms.     

Dispatching multi-load AGVs in highly automated seaport container terminals

This paper is concerned with AGV dispatching in seaport container terminals. Special attention is given to multi-load vehicles which can carry more than one container at a time. The characteristics of this complex application environment and the impact on the AGV dispatching problem are analyzed and various solution techniques considered. For practical application within an online logistics control system, a flexible priority rule based approach is developed, making use of an extended concept of the availability of vehicles. For evaluation reasons, this approach is complemented by an alternative MILP formulation. Finally, the performance of the priority rule based approach and the MILP model are analysed for different scenarios with respect to total lateness of the AGVs. The main focus of the numerical investigation is on evaluating the priority rule based approach for single and dual-load vehicles as well as comparing its performance against the MILP modelling approach.     

Strategies for dispatching AGVs at automated seaport container terminals

Control of logistics operations at container terminals is an extremely complex task, especially if automated guided vehicles (AGVs) are employed. In AGV dispatching, the stochastic nature of the handling systems must be taken into account. For instance, handling times of quay and stacking cranes as well as release times of transportation orders are not exactly known in advance. We present a simulation study of AGV dispatching strategies in a seaport container terminal, where AGVs can be used in single or dual-carrier mode. The latter allows transporting two small-sized (20 ft) or one large-sized (40 ft) container at a time, while in single-mode only one container is loaded onto the AGV irrespective of the size of the container. In our investigation, a typical on-line dispatching strategy adopted from flexible manufacturing systems is compared with a more sophisticated, pattern-based off-line heuristic. The performance of the dispatching strategies is evaluated using a scalable simulation model. The design of the experimental study reflects conditions which are typical of a real automated terminal environment. Major experimental factors are the size of the terminal and the degree of stochastic variations. Results of the simulation study reveal that the pattern-based off-line heuristic proposed by the authors clearly outperforms its on-line counterpart. For the most realistic scenario investigated, a deviation from a lower bound of less than 5% is achieved when the dual-load capability of the AGVs is utilized.     

Inventory-based dispatching of automated guided vehicles on container terminals

This paper deals with automated guided vehicles (AGVs) which transport containers between the quay and the stack on automated container terminals. The focus is on the assignment of transportation jobs to AGVs within a terminal control system operating in real time. First, we describe a rather common problem formulation based on due times for the jobs and solve this problem both with a greedy priority rule based heuristic and with an exact algorithm. Subsequently, we present an alternative formulation of the assignment problem, which does not include due times. This formulation is based on a rough analogy to inventory management and is solved using an exact algorithm. The idea behind this alternative formulation is to avoid estimates of driving times, completion times, due times, and tardiness because such estimates are often highly unreliable in practice and do not allow for accurate planning. By means of simulation, we then analyze the different approaches. We show that the inventory-based model leads to better productivity on the terminal than the due-time-based formulation.     

A neural algorithm for finding the shortest flow path for an automated guided vehicle system

The automated guided vehicle (AGV)system is emerging as the dominant technology to maximize the flexibility of material handling, while increasing the overall productivity of manufacturing operations. This paper presents a new way of finding the shortest flow path for an AGV system on a specific routing structure. An optimal solution of the system is determined by using an approach based on the Hopfield neural network with the simulated annealing (SA) procedure. In other words, the proposed approach reduces the total cost of an AGV delivery path from one workstation to another on the shop floor. By changing the temperature of the two-stage SA, a solution can be found that avoids potential collisions between AGVs. Both the flow path and the potential collision, which are major problems in AGV systems, may be solved simultaneously by the proposed neural network approach. Other advantages offered by the proposed method are its simplicity compared with operations research (OR)methods and a decreased number of needed AGVs. The performance of the approach is also investigated.