邱亭秀　倪欣园　于露　窦万峰

摘  要：本文结合最优路径算法、时间窗、冲突处理策略，提出一种基于结点时间窗修改初始路径的多AGV（Automated Guided Vehicle）调度的方法。该方法适用于路径选择少，对备用路径选择依赖性小的情况。本文首先运用A*算法进行静态初始路径规划，结合时间窗进行冲突预判，在结点采用“时间点+固定时间片”进行路径结点时间窗更改，提高了路径使用效率;然后，在初始路径上依据冲突类型修改或添加结点及时间窗。最后，通过仿真实验，验证了本文提出的方法可以减少实时运算的负担且提高了长路段的利用效率。

关键词：时间窗;调度策略;路径规划;结点时间点;初始路径修改

中图分类号：TP391.7     文献标识码：A

A Novel Scheduling Method of Modifying the Initial Path based on Node Time Window

QIU Tingxiu， NI Xinyuan， YU Lu， DOU Wanfeng

（School of Computer Science and Technology， Nanjing Normal University， Nanjing 210023， China）

1430273936@qq.com; 821787886@qq.com; 897741680@qq.com; douwanfeng@njnu.edu.cn

Abstract： Based on optimal path algorithm， time window and conflict elimination strategy， this paper proposes a multi-AGV （Automated Guided Vehicle） scheduling method which modifies the initial path based on node time window. This method is suitable for the case of less path selection and less dependence on alternative path selection. Firstly an algorithm， namely A*， is used to gain a static initial path for a task combined with time window for conflict prediction， and "time point +

fixed time slice" is used to change time window of the node with time conflicts. Then， on the initial path， nodes and time windows are added or altered according to conflicting types. Finally， the simulation results show that this scheduling method can reduce the burden of real-time operation and improve the utilization efficiency of long road sections.

Keywords： time window; scheduling strategy; path planning; node time; initial path modification

1   引言（Introduction）

AGV（Automated Guided Vehicles）是一种典型的用于无人工厂进行重复性的运输任务作业的无人驾驶的移动机器人[1，2]。

AGV小车是智能车间重要的物流运输资源，能否將物料按时送达加工单元将影响系统生产资源的利用率。因此，如何快捷高效地调度有限的AGV小车，使得车间的生产效率最高是智能车间生产的重要环节盘[3]。国内外对AGV的调度研究主要集中在AGV的路径规划、AGV的数量配置以及AGV的任务分配三个方面[4]。在物料配送模式中，最重要的是确定AGV的行驶路线，即AGV的路径规划问题，其本质上是VRP（Vehicle Routing Problem）问题[5]。AGV的路径规划不当会使得AGV相互冲突，此时不但无法提高车间的运作效率，反而阻碍车间顺畅运作。因此，AGV路径规划是亟待解决的问题[6]。

国内外学者对AGV路径规划问题作了不少研究[7-10]。……