时间窗约束下的AGV动态路径规划

张峥炜，陈波，陈卫东

时间窗约束下的AGV动态路径规划

张峥炜，陈波，陈卫东

针对自动化码头的多自动导引车系统（Automated Guided Vehicle，AGV）的路径规划问题，提出了一种基于时间窗的改进Dijkstra动态路径规划算法。算法按照任务优先级和地图中的先验信息顺序规划各AGV的行驶路径，在已规划路径的基础上，通过更新地图中的时间窗信息，继续规划后续路径，实现各AGV的无冲突且行驶时间最短的动态路径规划。结合实例及对比实验表明该算法能够有效减少多AGV之间的路径冲突，降低AGV的路径行驶时间，提高自动化码头运行效率。

自动导引车；时间窗；动态路径规划；Dijkstra算法；自动化码头

0 引言

自动导引车（Automated Guided Vehicle，AGV）系统是一种实现物料搬运的无人运输系统，在仓储物流、汽车装配、烟草、电力等行业都有着广泛应用。近年来随着集装箱自动化码头在国内的兴起，AGV作为主要的水平运输工具承担重要任务，主要包括从岸桥到堆场的集装箱卸船运输、堆场到岸桥的装船运输以及堆场内的转场运输等。AGV水平运输系统被业界公认为整个自动化码头的效率瓶颈，而 AGV路径规划问题又是AGV系统设计的核心，因此研究多AGV系统的高效无冲突、无死锁路径问题，对于提高整个自动化码头的装卸效率具有重要意义。

世界上第一个集装箱自动化码头荷兰鹿特丹港ECT码头于1993年投入商业运营，此后德国汉堡港CTA码头、鹿特丹港Euromax等自动化码头相继建成，国外学者围绕自动化码头做了大量的研究工作，针对AGV的路径问题的研究主要集中于在途AGV的相互间冲突[1,2]，死锁的预防、检测与控制[3-5]等方面，而针对AGV路径搜索相关方面的研究相对较少。Klimm等[6]提出一种无冲突的静态路径规划方法，首先以最小负载为目标规划路径，然后进行死锁的预防与检测。该方法仅适用于地图中潜在死锁数量较少的情况，随着AGV数量的增加，地图中潜在的死锁数量增多，该方法无法获得较优的结果。Jeon等[7]提出一种基于Q学习的路径规划算法，通过估计AGV在行驶中因冲突而产生的等待时间，为AGV规划一条行驶时间最短的路径，但是该算法求解耗时长，且无法避免死锁的产生。

国内自动化码头起步相对较晚，针对自动化码头的AGV路径规划问题研究较少，且研究主要面向制造系统。刘国栋等[8]针对多AGV调度系统，提出两阶段动态路径规划方法，第一阶段先离线生成任意两点之间的候选路径集，第二阶段采用启发式方法为所有任务分配各自的最优路径。贺丽娜等[9]针对制造系统中的多AGV调度，提出一种基于先验决策的无碰撞路径规划方法，该方法先根据Dijkstra算法对每个 AGV规划出最短路径，再结合时间窗原理进行AGV的无碰撞路径规划。胡彬等[10]提出一种基于时间窗的动态路径规划方法，该方法通过求出备选路径，再在备选路

径上排出理想情况下的时间窗，然后对有时间窗重叠部分的路径进行计算与更新。乔岩等[11]提出通过实时改变自动导引车通过节点的优先级来调整自动导引车在相应节点的通过顺序，从而实现多自动导引车动态环境下的路径规划。

上述文献提出的AGV动态路径规划算法，均采用先为已分配任务的AGV规划最短行驶路径，再根据时间窗为各AGV调整路径通过次序及时间，某种程度上避免了相互冲突，但由于路径的规划是以行驶距离最短为目标，规划过程并未考虑行驶时间，无法充分利用路段的时间资源，因此AGV运行效率有限。基于以上原因，本文提出了一种适用于自动化码头的AGV动态路径规划方法，基于时间窗理论实现行驶时间最短的无冲突路径。

1 问题描述

1.1 地图描述

自动化码头的布局主要有两种方式，循环式布局和交叉式布局，Duinkerken等[12]对两种布局方式进行了对比，得出在岸桥装卸船效率相同的情况下，交叉式布局需求的 AGV数量更少，即交叉式布局方式下AGV的运行效率更高。目前国内已建成的或在建的自动化码头，均采用交叉式布局，因此本文研究亦采用该方式。

在自动化码头中，AGV沿着铺在地面上的导引磁钉行驶，磁钉及AGV在磁钉之间的运动方向构成地图，如图1所示：

图1 自动化码头中部分地图布局

布局中所有的磁钉抽象为图论中的点，根据点在地图中的不同位置以及AGV在点之间的运动方向构成图论中的有向边。所有的点以及点与点之间的线路抽象为一个有向强连通图 。其中为点的集合，为边的集合，为边上权重的集合。

动态路径规划算法的目标是搜索出一条能连通、无冲突的且行驶时间最短的路径，所以有向边的权重定义为 AGV通过该边的行驶时间。AGV在边上的权重为边的长度与边上行驶速度的比值为式（1）：

式（1）中为边的物理长度，为AGV在边上的平均行驶速度。

1.2 模型描述

本文模型描述如下：在一个强连通图中，给定一个任务，其中表示任务编号，表示任务的起点，表示任务的终点，表示任务的开始时间，规划一条从任务起点到任务终点能够连通、无冲突的且行驶时间最短的路径。

一个简化的地图模型如图2所示：

图2 简化的地图模型

与其相对应的时间窗如图3所示：

图3 对应的时间窗

为简化模型，本文在建模时做如下规定：

（1）对于有k个任务需要规划路径，按照任务优先级依次对k个任务进行路径规划，任务优先级在任务下发时给出。

（2）在所有运行区域，AGV的行驶速度设定为常值。

（3）为保障AGV行车安全，本文定义一个安全时间：

（4）为便于研究，本文假设所有任务均统一下发，对于实际工程中可能出现的分批下发情况，本文暂不做讨论。

2 时间窗约束下的路径规划算法

2.1 算法实现步骤

针对动态路径规划算法的求解，本文采用类似求解Dijkstra算法的以点为基础的标号法，Dijkstra算法解决的是带权重的有向图上单源最短路径问题[13]，该算法要求所有边的权重均为非负值。在本文研究中，边的权重为时间，均为非负值满足算法要求。算法的实现分为以下几个步骤：

2.2 时间窗的计算（1）计算AGV通过点的时间如图4所示：

图4 AGV通行示意图

（2）计算最早达到时间及占用时间窗

在执行带时间窗约束的路径搜索时，如图5所示：

图5 相邻点

如1.2节所示的模型，运用上述算法规划AGV的行驶路径，主要计算过程及结果如图6所示：

图6 路径规划结果

3 算法仿真验证

本文使用MATLAB R2012a软件进行时间窗约束下的动态路径规划仿真验证。选取国内某自动化码头水平运输区部分区域，长287米，宽94米，包含45个堆场作业车道，40个岸桥缓冲区车道以及6个高速车道。AGV行驶速度设定为3m/s。本文设计了两组对比实验，一组是任务数量相同时的路径规划，另一组是任务数量逐渐递增时的路径规划，从两个维度对比本文提出的算法与先路径规划后进行无冲突的时间窗排布算法[8-11]（后文简称对比算法）的结果差异。其中每个任务定义为一辆AGV从岸桥缓冲区车道运输集装箱到堆场作业车道，或者从堆场作业车道运输集装箱到岸桥缓冲区车道，AGV数量等于任务数量。

（1）任务数量相同

实验设定一批任务包含40个子任务，即需要规划40辆AGV分别从不同的堆场作业车道生成路径至不同的岸桥缓冲区车道。随机生成500万批任务，根据每批任务中40个子任务的起点和终点位置计算路线的潜在冲突次数，采用聚类方法将每批任务的潜在冲突次数分成3类，得到的潜在冲突次数分类如表1所示：

表1 每批任务潜在冲突次数分类

根据表1中所述的潜在冲突次数的分类，每个类别分别取样200批任务，计算每批任务中40个子任务的平均完成时间，实验结果如图7和图8所示：

图7 平均完成时间对比

图8 平均等待次数对比

由图7和图8可以看出，任务数量相同，即AGV数量相同时，随着潜在冲突数量的增加，子任务的平均完成时间和平均等待时间均逐渐增加。同时，本文算法的子任务平均完成时间和平均等待次数均小于对比算法，并且潜在冲突越多，效率提升越明显。

（2）任务数量不同

针对每批任务分别包含10、20、30、40个子任务进行分类分析，每个类别分别取样200批任务，计算每批任务的平均完成时间和平均等待次数，实验结果如图9和图10所示：

图9 不同任务数量平均完成时间对比

图10 不同任务数量平均等待次数对比

由两图可以看出，当任务数量较少即AGV数量较少时，两种算法的结果没有明显的差异，但是随着任务数量的增加，本文算法相较于对比算法，任务的平均完成时间和等待次数均大幅减少，效率提升明显。

4 总结

针对自动化码头的多AGV路径规划问题，本文结合时间窗理论和Dijkstra算法，提出一种动态路径规划算法，该算法旨在为AGV规划一条连通任务起点和任务终点、无冲突且行驶时间最短的路径。通过仿真实验，将本文算法与先进行路径规划再进行时间窗排布的算法进行对比分析，结果验证了本文算法能够有效减少AGV的行驶时间，提升自动化码头的运行效率。

本文主要针对给定任务起点和终点，规划一条可连通、无冲突且行驶时间最短的路径，然而在实际工程中，载有集装箱的AGV在与其他设备进行交互操作时对集装箱的箱门方向有严格规定，因此如何在本文提出的算法的基础上进一步规划出一条满足倒箱门策略的路径将是今后的研究方向。

[1] Duinkerken M B, Evers J J M, Ottjes J A. Traces： Teaffic Control Engineering System A case-study on container terminal automation[J]. signal, 1999, 3(2)：

[2] Cheng Y L, Sen H C, Natarajan K, et al. Dispatching automated guided vehicles in a container terminal[M]// Supply chain optimization.New York Springer US, 2005, 355 -389.

[3] Moorthy R L, Hock-Guan W, Wing-Cheong N, et al. Cyclic deadlock prediction and avoidance for zone-controlled AGV system[J]. International Journal of Production Economics, 2003, 83(3)： 309-324.

[4] Lehmann M, Grunow M, Günther H O. Deadlock handling for real-time control of AGVs at automated container terminals[J]. Or Spectrum, 2006, 28(4)： 631-657.

[5] Kim K H, Jeon S M, Ryu K R. Deadlock prevention for automated guided vehicles in automated container terminals[M]//Container Terminals and Cargo Systems： Berlin Springer, 2007： 243-263.

[6] Klimm M, Gawrilow E, Möhring R H, et al. Conflict-free vehicle routing： load balancing and deadlock prevention[ROL].[2007-10-31] Technical Report, 2007. http：//w ww.matheon. de/preprints/5137_preprint- staticrouting. pdf, 2007.

[7] Jeon S M, Kim K H, Kopfer H. Routing automated guided vehicles in container terminals through the Q-learning technique[J]. Logistics Research, 2011, 3(1)： 19-27.

[8] 刘国栋,曲道奎,张雷. 多AGV调度系统中的两阶段动态路径规划[J]. 机器人, 2005, 27(3)： 210-214.

[9] 贺丽娜,楼佩煌,钱晓明,等.基于时间窗的自动导引车无碰撞路径规划[J]. 计算机集成制造系统, 2010, 16(12)：2630-2634.

[10] 乔岩,钱晓明,楼佩煌.基于改进时间窗的AGVs避碰路径规划[J].计算机集成制造系统,2012,18(12)：2683-2688.

[11] 胡彬,王冰,王春香,等.一种基于时间窗的自动导引车动态路径规划方法[J]. 上海交通大学学报, 2012, 46(6)：59-63.

[12] Duinkerken M B, Evers J J M, Ottjes J A. Improving quay transport on automated container terminals[C]//Proceedings of the IASTED International Conference Applied Simulation and Modelling (ASM 2002), Crete. 2002.

[13] Dijkstra E W. A note on two problems in connexion with graphs[J]. Numerische mathematik, 1959, 1(1)： 269-271.

Dynamic Routing of Automated Guided Vehicles with Time Window

Zhang Zhengwei1, Chen Bo1, Chen Weidong2
(1.Shanghai Zhenhua Heavy Industries Electric Co., Ltd, Shanghai 200125, China；2. Institute of Automation, Shanghai Jiaotong University, Shanghai 200240, China)

To solve the routing problem for the multiple Automated Guided Vehicles (AGV) in automated container terminals, an improved Dijkstra dynamic routing algorithm based on time window is proposed. Every AGV route is scheduled in order according to the priorities of the tasks and prior information of the map. Based on the planned routes, conflict-free, shortest-time and dynamic routing are achieved by updating the time window information for the planned routes. In comparison with the traditional method, the proposed algorithm can effectively decrease the conflicts between AGV routes and reduce their travel time, thereby the operating efficiency of the terminal can be enhanced.

Automated guided vehicles； Time window； Dynamic routing； Dijkstra algorithm； Automated terminal

TP391

A

1007-757X(2016)11-0046-04

20 16.09.27）

张峥炜（1983-），男，上海振华重工电气有限公司，工程师，博士，研究方向：agv路径问题等，上海 200125

陈 波（1988-），男，上海振华重工电气有限公司，工程师，硕士，研究方向：agv路径问题等，上海 200125

陈卫东（1968-），男，上海交通大学自动化系，教授，研究方向：移动机器人，多机器人学等，上海 200240