章文俊 韩晓龙

自动导引车（automated guided vehicle，AGV）是自动化集装箱码头的主要运输设备，用于在码头前沿与后方堆场之间水平运输集装箱。AGV的作业效率不仅受其自身性能的影响，而且受码头布局、行驶路径和道路容量等因素的影响。在码头作业高峰期，随着AGV行驶路径的不断重叠，可能会产生AGV路径冲突问题，导致AGV作业效率下降。为了解决AGV路径冲突问题，本文在传统的速度控制策略的基础上，提出基于道路容量的速度控制与路径再规划相结合的优化策略，并通过算例分析验证优化策略的有效性和优越性。

1 研究背景

AGV路径冲突规避涉及对AGV的实时控制，已有的研究成果包括：YANG等[1]提出一种用于作业设备协调和AGV路径规划的整体调度方案，建立以作业时间最短为目标的双层规划模型;柯冉绚等[2]建立以无效作业时间最短为目标的数学模型，并采用Netlogo仿真软件验证作业面调度模式的优越性;GRUNOW等[3]分析自动化集装箱码头应用环境的特点及其对AGV调度问题的影响，并考虑多种解决方案;GHASEMZADEH等[4]提出网状拓扑系统中AGV调度和路径规划算法;肖海宁等[5]针对单向导引路径网络中AGV碰撞和系统死锁问题，提出一种规避环路死锁搜索方法，定义单环路和多环路死锁临界状态，并设计相应的死锁控制策略;UMAR等[6]采用基于优先级的遗传算法研究AGV路径规划问题，从而使AGV行驶时间最短;王佳溶等[7]提出基于改进后的两阶段控制策略和多目标的带约束遗传算法的控制策略，并采用速度控制方法解决AGV路径冲突问题，从而实现对AGV的优化调度;冯海双[8]采用A*算法检测AGV路径冲突情况，并设置安全距离以规避冲突;张素云等[9]提出一种改进的速度控制策略，根据AGV通过路口节点的优先级来控制AGV的速度;仲美酥等[10]提出交通虚拟环岛策略来避免AGV在行驶过程中产生冲突和拥堵。

从已有的研究成果来看，AGV路径冲突问题最终还是要通过AGV路径规划来解决。部分学者采用速度控制策略规避AGV路径冲突，虽然有一定成效，但仍然存在不足之处。本文在传统的速度控制策略的基础上，提出基于道路容量的速度控制与路径再规划相结合的优化策略。首先，分析常见的AGV路径冲突形式;然后，分别构建道路容量检测模型、速度控制模型以及速度控制与路径再规划相结合模型;最后，利用eM-Plant生产系统仿真软件构建自动化集装箱码头AGV仿真路网，通过算例分析验证速度控制与路径再规划相结合策略的有效性和优越性。

2 问题描述

如图1所示：自动化集装箱码头的主要作业区域包括船舶装卸作业区、水平运输作业区和堆场作业区，分别由岸桥、AGV和场桥完成相应的作业。在码头作业高峰期，整个水平运输系统处于繁忙状态，AGV在路径节点处发生冲突的情形增加，从而造成道路拥堵，进而导致码头整体作业效率下降。AGV路径冲突形式包括：（1）AGV沿同一路径同向而行（见图2a）），且后车速度比前车快;（2）AGV沿同一路径相向而行（见图2b））;（3）不同路径的AGV同时到达同一路口节点（见图2c））;（4）AGV长时间占据路口节点（见图4d）），且相应路径剩余容量不足。目前已建成的自动化集装箱码头大多采用单向导引路径，并且设有多个缓冲区;因此，图2a）和图2b）所示的AGV路径冲突形式少见，图2c）和图2d）所示的AGV路径冲突形式最为常见。本文主要研究图2c）和图2d）所示的AGV路径冲突形式。

3 模型构建

3.1 假设条件

（1）泊位数量与岸桥数量之比为1∶3，岸桥在其作业区域内的位移忽略不计。

（2）岸桥单箱作业时间为100～120 s，AGV在岸桥下的作业时间服从（100，120）的整数分布。

（3）岸桥下方和堆场均设有缓冲区，AGV在缓冲区等待作业时产生的路径冲突忽略不计。

（4）不考虑设备故障等因素的影响。

3.2 符号说明

用赋权有向图G=（S，N）表示AGV路网布局。当规划多条AGV路径时，S为边集，Sk（i，j）=（ni，nj）为路径k上第i个节点到第j个节点的边，N为AGV路网中所有节点的集合。为了便于建模，引入以下符号：L为AGV的长度;Ls为行驶过程中AGV之间的安全距离;Pk为第k条路径，k=1，2，3，…，K;K为AGV路径的集合，k∈K;Dk为路径k的长度;R（Pk）为路径k的道路容量;E（Pk）为路径k的已用容量;v0为AGV的正常行驶速度;a为AGV在行驶过程中的加速度。

3.3 分步控制模型

针对AGV路径冲突问题构建模型，即

其中：式（1）和式（2）表示每个节点最多被同一AGV访问1次，以免造成环路死锁;式（3）表示路径k的长度为其所有节点所在边之和。

不同的AGV同时经过同一路口节点会产生AGV路径冲突，需要其中一台AGV减速或停车，以避让另一台AGV。此外，同一路径上的AGV需要保持安全距离Ls。

针对图2d）所示的AGV路径冲突形式，需要考虑路径剩余容量，即

其中：式（4）表示路径k的道路容量，Round为向下取整函数;式（5）表示路径k的剩余容量。

当AGV申请进入的路段剩余容量为0时，应暂时禁止其进入路口节点，以免其长时间占据路口节点导致其他AGV无法运行，造成道路擁堵或死锁。计算路径k1和k2的冲突节点集合，即

C（k1，k2）=∩（6）

式中：和分别为路径k1和k2的冲突节点。

3.4 速度控制模型

对于检测存在路径冲突的AGV，根据AGV的优先级采取相应策略：优先级较高的AGV保持现有速度匀速通过冲突节点，优先级较低的AGV则以加速度a减速至v1。据此构建速度控制模型，即

其中：式（7）表示优先级较低的AGV从距离冲突节点处开始减速，并以减速后的速度v1匀速通过冲突节点;式（8）表示优先级较低的AGV从正常速度v0减速至v1的行驶距离;式（9）表示优先级较低的AGV在到达冲突节点前的减速行驶时间以及通过冲突节点后的加速行驶时间;式（10）表示优先级较高的AGV 以正常速度v0通过冲突节点所需要的时间;式（11）表示使AGV经过冲突节点前后所需要的时间最短。

3.5 速度控制与路径再规划相结合模型

对于检测存在路径冲突的AGV，在采取速度控制策略的同时，根据道路容量决定是否重新规划AGV路径。如果优先级较低的AGV减速行驶至路口节点后，下一路段的AGV仍未全部驶出该路段，导致AGV需要在路口节点等待较长时间，则考虑重新规划AGV路径。据此构建速度控制与路径再规划相结合模型，即

其中：式（12）表示下一路段的AGV全部以正常速度v0驶出该路段所需要的时间;式（13）表示AGV从距离路口节点处开始减速;式（14）表示AGV在距离路口节点处开始减速行驶直至停在路口节点所需要的时间;式（15）表示AGV从相邻路段以正常速度v0行驶所需要的时间;式（16）表示AGV在路口节点等待下一路段的AGV全部驶出该路段的时间;式（17）表示使AGV通过路口节点的时间最短。

4 算例分析

4.1 参数设置

参照图1，利用eM-Plant软件构建自动化集装箱码头AGV仿真路网（见图3）。假设每艘船安排3台岸桥同时作业，并且每台岸桥对应多个箱区。设置基本参数如下：L=6 m，Ls=2 m，v0=4 m/s，v1=2 m/s，作业箱量为200个。

4.2 仿真结果比较

采用Dijkstra算法规划AGV初始路径，在eM-Plant软件中设置传感器检测AGV路径冲突节点，通过速度控制策略和速度控制与路径再规划相结合策略规避AGV路径冲突，并计算和比较采用不同策略完成相同作业量所需要的时间、冲突节点处相邻路径的利用率和平均等待率、AGV在作业过程中的利用率和平均等待率等。

由图4可见：随着作业量增加，速度控制与路径再规划相结合策略在作业时间方面的优势逐步显现;当作业量达到200个集装箱时，采用速度控制与路径再规划相结合策略完成作业量所需要的时间明显短于速度控制策略。

由图5可见：在速度控制策略下，冲突节点处相邻3条路径的利用率分别为35.67%、60.47%和61.18%，路径1的利用率远远低于路径2和路径3;在速度控制与路径再规划相结合策略下，冲突节点处相邻3条路径的利用率分别为48.68%、53.94%和46.95%，三者相差不大，路径利用更为合理。

由图6可见：在速度控制策略下，冲突节点处相邻3条路径的平均等待率分别为13.48%、36.10%和24.42%;在速度控制与路径再规划相结合策略下，冲突节点处相邻3条路径的平均等待率分别为13.22%、18.02%和22.47%，总体低于速度控制策略下的平均等待率，其中路径2的平均等待率大幅下降18个百分点。

由图7可见：在速度控制策略下，AGV在作业过程中的利用率为92.7%，平均等待率为7.3%;在速度控制与路径再规划相结合策略下，AGV在作业过程中的利用率为95.8%，平均等待率为4.2%，优于速度控制策略下的同类指标。

5 结束语

本文在传统的速度控制策略的基础上，提出基于道路容量的速度控制与路径再规划相结合的优化策略，以解决自动化集装箱码头AGV路径冲突问题。仿真结果表明：速度控制与路径再规划相结合策略不仅能够有效解决自动化集装箱码头AGV路径冲突问题，而且效果优于速度控制策略。需要注意的是：本次仿真过程中设定的作业量较少，只有200个集装箱;未来需要验证速度控制与路径再规划相结合策略是否适用于大规模作业和复杂路网情况，并针对其可能存在的问题进一步优化模型，以满足自动化集装箱码头的实际需要。

参考文献：

[1] YANG Y S， ZHONG M S， DESSOUKY Y， et al. An integrated scheduling method for AGV routing in automated container terminals[J]. Computers & Industrial Engineering， 2018， 126（12）：482-493.

[2] 柯冉绚，任亚东. 集装箱码头AGV调度优化[J]. 集美大学学报（自然科学版），2016，21（1）：35-41.

[3] GRUNOW M， G躈THER H O， LEHMANN M. Dispatching multi-load AGVs in highly automated seaport container terminals[J]. OR Spectrum， 2004， 26（2）：211-235.

[4] GHASEMZADEH H， BEHRANGI E， AZGOMI M A. Conflict- free scheduling and routing of automated guided vehicles in mesh topologies[J]. Robotics and Autonomous Systems， 2009， 57（6/7）：738-748.

[5]肖海宁，楼佩煌.自动导引车系统避碰及环路死锁控制方法[J]. 计算机集成制造系统，2015，21（5）：1244-1252.

[6] UMAR U A， ARIFFIN M K A， ISMAIL N， et al. Priority-based genetic algorithm for conflict-free automated guided vehicle routing[J]. Procedia Engineering， 2012（50）：732- 739.

[7] 王佳溶，楼佩煌，王晓勇. 基于改进的两阶段控制策略的AGV路径优化调度研究[J]. 机械科学与技术，2008，27（9）：1211-1216.

[8] 馮海双. AGV自动运输系统调度及路径规划的研究[D]. 哈尔滨：哈尔滨工业大学，2013.

[9] 张素云，杨勇生，梁承姬，等. 自动化码头多AGV路径冲突的优化控制研究[J]. 交通运输系统工程与信息，2017，17（2）：83-89.

[10] 仲美酥，杨勇生. 卸船作业模式下自动化码头AGV路径仿真优化[J]. 水运工程，2018（4）：122-127.

（编辑：张敏 收稿日期：2019-07-14）