基于时空网络的自动化集装箱码头自动化导引车路径规划

高一鹭，胡志华

（上海海事大学物流研究中心，上海201306）（*通信作者电子邮箱zhhu@shmtu.edu.cn）

0 引言

自动化导引车（Automated Guided Vehicle，AGV）是自动化集装箱码头（Automated Container Terminal，ACT）水平运输的主要设备［1］，承担岸边与堆场之间集装箱的搬运任务，与岸桥和场桥互相协调共同完成码头的装卸作业。AGV 路径是指搬运任务作业过程中，AGV 从任务起点（Origin，O）到终点（Destination，D）的行驶轨迹，而ACT 连续作业下，多辆AGV同时共享道路网络并行完成大量装卸任务，因此AGV 行驶轨迹可能发生交叉或重叠从而导致AGV 发生碰撞、拥堵等冲突问题。AGV 路径冲突若处理不当，则导致AGV 单次作业时间延长，作业成本增加，同时增加岸桥或场桥的等待时间，延长ACT 整体装卸时间，从而降低其运作效率并大幅度增加码头作业成本。因此考虑冲突规避的多AGV 路径规划是ACT 运作管理的关键问题，相关的模型与算法研究为码头的运营和管理提供重要的理论依据［2-4］。

冲突规避的AGV 路径规划问题已成为当前研究的重点。Lyu 等［5］将带时间窗的Dijkstra 算法嵌入遗传算法中，搜索最短路径同时检测多车辆的碰撞情况；Fazlollahtabar等［6］建立混合整数规划模型并提出两阶段优化方法（搜索解空间和寻找最优解）来规避AGV 之间的冲突；Nishi 等［7］提出动态环境中双向AGV 系统调度和路径冲突规避的Petri网分解方法，整个Petri 网分解为任务子网和AGV 子网并在AGV 子网中嵌入避免死锁的方法；Miyamoto 等［8］建立混合整数规划模型，并提出局部随机搜索方法求解容量限制的AGV 系统调度和冲突规避的路径规划问题。以上研究同时考虑AGV 路径规划以及任务调度问题，通过调整AGV 任务作业序列以规避路径冲突。然而，大部分情况下AGV任务执行顺序是确定的。

在AGV 任务作业顺序确定条件下，较多文献关注于路径搜索方法：Małopolski 等［9］用矩阵描述运输系统布局，将AGV的运动视为以固定的平均速度从矩阵到矩阵的运动，进而提出一种防止AGV碰撞和死锁的新方法；Antakly等［10］利用时间Petri 网进行建模并提出三阶段的启发式算法，通过对AGV 施加适当的延迟以避免与其他AGV 发生碰撞；Mohammadi 等［11］提出一种基于仿真的高级柔性工艺模型，通过预见机制以动态预防AGV的碰撞和死锁；Fanti等［12］通过区域控制分散协议协调AGV 运动以规避碰撞；郭兴海等［13］考虑动态环境下根据障碍物的运动情况，提出感应转向算法使AGV 规避障碍物；Nishi 等［14］考虑AGV 加速或减速条件下冲突规避的路径规划问题，建立连续时间模型并提出基于列生成的启发式算法；刘二辉等［15］提出路径微调算子使路径片段变短以避开障碍物，实现基于遗传算法的动态路径规划；曹小华等［16］结合图论提出一种基于顶点属性和实时位置信息的冲突预测方法，建立混合整数规划模型并提出一种适用于多AGV 系统避碰决策优化的改进粒子群优化算法；李军军等［17］通过分析路段与节点冲突问题建立混合整数规划模型并提出一种诱导蚁群粒子群算法，在算法的状态转移规则中，增加诱导因子来引导AGV 规避冲突；郑延斌等［18］针对多Agent 路径规划问题，提出一个基于蚁群算法及博弈论的两阶段路径规划算法，为解决多Agent 之间的碰撞，利用博弈论构建多Agent 之间的动态避障模型并利用虚拟行动法来求解多Nash 均衡的选择问题。以上研究通过设计和调整AGV 行驶路线或者采取等待措施以规避路径冲突，然而，大部分冲突规避的路径规划研究主要面向生产制造系统。

自动化码头与制造系统相比，运输区域面积更大且无障碍物，交通规则更灵活，并且AGV 尺寸更大且数量更多，码头全自动连续作业要求AGV 与岸桥和场桥交互作业误差尽可能小，因此对AGV 路径进行合理规划具有一定难度。Xin等［19］提出一种层次控制体系结构以满足交互设备的集成调度，并且按照调度的总体图序列，通过顺序求解混合整数规划问题以获得满足AGV冲突规避的轨迹规划；Yang等［20］建立一个双层编程模型并提出基于道路堵塞预防规则的双层遗传算法，以解决码头起重机、自动导引车和堆场起重机的集成调度问题；Xin 等［21］提出一种两级能量感知方法，通过高级控制器解决控制问题以确定各个AGV 的碰撞规避轨迹；Li等［22］提出AGV 系统流量控制算法，通过减少每个区域的最小允许面积来提高工作区的利用率并设计一种紧急交通控制方案，以避免因车辆故障而导致的车辆碰撞和死锁。然而目前，自动化码头AGV路径规划相关研究较少。

上述文献提出的算法大多数在规划路径时设计冲突预测机制以检测冲突，发现冲突后则返回路径规划或者调度问题求解中，然而算法并没有实时检测冲突路段进行一次路径规划，因此增加了计算的复杂性。本文研究自动化码头AGV 路径规划问题，在AGV 作业任务顺序确定条件下，通过构造AGV 的时空网络以实时反映AGV 状态信息和检测冲突路段，并以任务完工时间最小为目标，对实际路段拥堵情况建立模型和设计时空网络算法，优先调整路线以规避路径的碰撞和拥堵。

1 问题描述

ACT 由岸边、AGV 和堆场三个作业区组成，布局如图1所示。其中，AGV 作业区包括海陆两侧装卸区、缓冲区和行驶区，海侧装卸区和行驶区下设有能控制小车转弯方向的车道。AGV 作业可分为进口箱和出口箱作业。以进口箱作业为例说明其作业流程。1）在海侧装卸区的起始位置（O点），岸桥放置集装箱到AGV 上，AGV 完成装载；2）AGV 转弯进入缓冲区进行排序，根据规划的路径进入指定的行驶区车道，行驶到陆侧装卸区的目标位置（D点）；3）场桥卸载AGV 上的集装箱移至堆场箱区存储，AGV 完成一次装卸作业。对于出口箱作业任务，则反之。一辆AGV 同一时刻只能作业一个任务，只有完成当前的作业任务才可以执行下一个任务，同一个任务在作业过程中不能中断。另外，AGV 行驶过程需遵守港区局部物流交通系统中的交通规则，例如转弯、拥堵停车和让道等，当某一道路拥堵时AGV可在缓冲区等待。

图1 自动化集装箱码头布局Fig.1 Layout of automated container terminal

通常，将一辆AGV 从任务的O点到D点的行驶路径设为两点之间的最短路径，并且假定该最短路径上的所有路段都是通畅可行的［23］，然而该做法没有考虑AGV 在实际路段中的运行轨迹以及运行过程中的实时动态干涉，导致AGV 根据规划路径进行作业时产生冲突。路径冲突情况包括碰撞和拥堵，在图2中，举例说明AGV 冲突问题。任务1 和任务2 同为进口箱作业，任务1和任务2的OD点分别为O1D1、O2D2，实线表示小车实际经过的路线，虚线表示计划行驶但未行驶的路线。图2（a）展示了碰撞的发生情况，执行任务1 的AGV 与执行任务2 的AGV 在不同时刻出发却在同一时刻到达点A，发生碰撞导致任务执行失败。图2（b）展示了拥堵的发生情况，执行任务1和执行任务2的2辆AGV 会在同一时刻到达A点，但为避免碰撞，执行任务2 的AGV 行驶到缓冲区B点时停车等待，造成拥堵现象。AGV 发生碰撞将直接导致设备损坏，大幅度增加成本，设备停留在路段中占用路段资源，可能与即将行驶进路网的AGV 发生二次碰撞，并且处理碰撞事故所需时间和人力成本较高；等待是避免碰撞的常用手段，但AGV减速及加速过程所消耗的电力成本较高，并且AGV 等待减少了可用的道路资源，道路会因为AGV 的等待而出现拥堵，严重时会导致整个路网瘫痪导致ACT 被迫停止运作。所以，当路段本身成为临界资源时，AGV 对路段具有独占性，因此，考虑AGV 在不同时刻在路网上的状态是判别碰撞和拥堵的前提条件。

图2 AGV在路网上的冲突情况Fig.2 Conflicts of AGVs in road network

在AGV 的行驶过程中，从当前时刻的位置出发，下一时刻可选的到达位置通常有多个；在各个不同位置上的下一个可能到达的位置又是不同的，因此，建立在道路网络背景下随时间演变的时空网络。利用AGV 在不同时刻可能到达的不同位置，从而刻画出AGV 从任务起点出发的一个可行的带有时间和位置标签的网络，路径规划则是在该网络中选择一条完工时间最短的路径。本文在ACT 背景下建立AGV时空网络，在时空网络中规划AGV 最短路径，以任务完工时间最短为目标，建立数学模型并设计时空网络算法，使规划路径规避碰撞并缓解拥堵。

2 数学模型

路径优化基础模型如M1所示，其相关符号定义如表1所示。

模型M1的目标函数（1）为最小化时间成本；约束（2）和（3）表示任务作业的先后关系，AGV 从起始位置O开始作业，作业完成后回到终点位置D；约束（4）是网络流量平衡约束，任意节点的出度等于节点的入度。

M1不考虑AGV 在实际路段中的运行轨迹，并假定路径之间不会互相干涉。实际上，M1规划出的当前路径可能产生一些时刻下的不可行路段，若执行后续任务的AGV 占用不可行路段将产生冲突。为了规避冲突，保证AGV 在运行过程中路径的畅通，根据上述界定的2 种冲突情况（碰撞和拥堵）进行建模。建模思想为：通过更新路网中新任务开始时刻下的可用节点集合实时规避该路径可能出现的碰撞以及缓解路网的拥堵；更新方法为：在时空网络下剔除当前任务规划下的不可用路段。值得注意的是，每一次规划新任务路径前，由于当前任务的路径产生了一些时刻下的新不可行路段，因此每个节点的碰撞和拥堵状态是任务开始时刻计算出来的并且在每个新任务开始前会进行更新。对于执行某具体任务的AGV 而言，需要做出以下决策：1）经过的路段；2）经过该路段的时间；3）该路段是否可用（不存在冲突情况）。建立模型M2，其相关符号定义如表2所示。

表1 模型M1相关符号定义Tab.1 Related symbol definitions of model M1

表2 模型M2相关符号定义Tab.2 Related symbol definitions of model M2

建模的具体说明如下：1）定义道路网络Net=(N，E)，其中，将道路网络离散化为间隔是单位时间1 的网络，即Tl=1，l∈E。2）定义离散时间集合T。扩 展Net定 义NetT=(NT，ET)，其中NT=，对于a∈NT，a[1]和a[2]分别取路网节点和时间；，对 于e∈ET，e[1]和e[2]分别表示第一个和第二个节点的状态。3）考虑路网中部分节点在特定时间被占用的问题，引入表示不可用节点，据此得到不可达集合，，并更新扩展网络为。

模型M2剔除了时空网络中因路径冲突而产生的不可行路段，在更新后的新时空网络中规划最优路径，目标函数（5）为最小化时间成本；约束（6）和（7）表示在可行的路网中任务作业的先后关系，AGV从起始位置O开始作业，作业完成后回到终点位置D；约束（8）是可行路网流量平衡约束，任意节点的出度等于节点的入度。

3 算法设计

3.1 时空网络求解算法

时空网络记录AGV 在不同时刻能到达的多个位置及其可行的路段，故AGV 的时间状态信息体现在网络节点上。构造时空网络的目的是让AGV 在所有可行路段中选择一条路径，在规避冲突下完成从起点到终点的任务。对于时空网络的结构而言，不同的道路交通规则下时空网络表现出不同的形态，而同一道路交通规则下的时空网络在更新时不改变其形态，每个网络节点仍记录AGV 的时间状态信息。因此，时空网络是空间网格在时间维度的迭代，而空间网格是港区道路网络依据单位时间距离的离散化。具体而言，对每一个路段，依据单位时间距离进行近似等分得到路段上的节点，这些中间节点仅仅与相邻节点以单位时间连通。依据模型M2的定义，离散后得到的道路网络节点记为N，时空网络的节点记为NT，在路段上单位时间连通的节点构成ET中的元素，不可用节点集合标记为-NT，并据此得到-ET。

基于以上的概念和模型，设计基于时空网络的算法——TS-SP（Tempo-Spatial Shortest Path），TS-SP 算法由算法1 和算法2组成。其中，算法1通过生成时空网络，更新时空网络，以及调用M2计算最短路径获得给定一个OD的AGV 路径；算法2调用算法1，通过迭代策略求解OD任务序列中的所有O和D配对的路径。算法2 根据已获得的路径更新不可用节点集合-NT（步骤5）以实时检测冲突，而算法1则利用不可用节点集合更新时空网络（步骤2）以实时规避冲突并进行一次路径规划（步骤3），因此针对多个OD任务，在时空网络上运用最短路径算法，根据路径结果更新时空网络，并通过迭代最终获得满足避碰和缓解拥堵条件的路径规划，而M2的求解过程能够通过拓展基本最短路径算法（如Dijkstra 算法）实现。时空网络算法流程如图3 所示。算法开始，依据时间顺序从任务集中选取任务执行。针对每一个当前任务，首先生成时空网络，并依据当前的不可用节点集合更新时空网络，接着在更新后的时空网络中采用Dijkstra算法计算任务最短路径，并依据当前任务的最短路径结果更新不可用节点集合。判断任务集是否为空：任务集不为空则选择下一个任务执行；任务集为空则说明已完成所有任务，算法结束。

图3 时空网络算法流程Fig.3 Flowchart of tempo-spatial network algorithm

算法1 单个OD任务最短路径优化算法（Single_OD_SP）。

输入 任务的起点O和终点D、开始时间t0、调度周期总时长T；所有节点的集合N，不可用节点集合-NT；

步骤1 生成时空网络NetT=(NT，ET)：NT={(i，t)|i∈N，t∈T}；

步骤2 更新时空网络：

步骤3 采用M2计算最短路径：

对Pe中的节点，取a[1]=O作为开始节点，依次顺序插入后续节点得到Path

算法2 OD任务序列最短路径优化算法。

输入 任务集合OD={(O，D)}、开始时间t0、调度周期总时长T；所有节点的集合N，不可用节点集合；

输出 路径集合Paths={(O，D，Path)}。

步骤2 取(O，D) ←OD[i]。

步骤3 求最短路径：

步骤4 更新路径集合：Paths←Paths∪{(O，D，Path)}。

步骤6i←i+1，如果i＜|OD|，转到步骤2；否则终止。

3.2 算法举例

为了分析算法的机理，在图4中，设计例证说明算法求解最优路径及其更新过程。设节点集合N={1，2，…，9}，离散时间集合T={0，1，2，…}，任务集合I={i，j}，任务i，j的OD位置及出发时间分别为(1，9，0)，(2，9，1)。AGV行驶过程中从一个节点出发只能到达其右边或其下边相邻的节点，如节点2 可到达节点3 或节点5，并且经过每一条短边的时间成本记为1个单位时间。AGV 在时空网络中行驶对应时间和空间位置要素，如执行任务i的AGV 在0时刻从节点1 出发，此时AGV状态记为(1，0)。

算法开始，在图4（a）中，任务i的时空网络如式（9）、（10）。此时不可用节点及边集合，产生一条最优路径Pathi，如式（11）。在图4（b）中任务j的时空网络如式（12），（13）。此时，若规划任务j在时空网络下的最优路径Pathj，如式（14），则两个任务所规划的路径在节点5存在冲突，即执行任务i的AGV 和执行任务j的AGV 在T=2时刻同时到达节点5，如图4（c）。因此，为了任务i和任务j的路径均可行，首先依据Pathi确定不可行节点与路段集合，如式（15）、（16），更新任务j的时空网络，，如式（17）、（18），再规划路径，如式（19），以此消除冲突，如图4（d）。然而，任务j更新后的路径和任务i的路径，在到达终点的时刻相等，即AGV 在执行卸载（或装载）集装箱操作时发生冲突。因此，使任务j在节点6 等待1 个单位时间，得到Path″j，如式（20）。至此，任务i和任务j的路径规划完成，在规避所有冲突的条件下得到最优路径，Pathi，j，如式（21）。算法结束，其机理得以验证。

图4 算法优化路径的过程Fig.4 Process of optimizing path planning by the algorithm

4 计算实验与结果分析

4.1 算例设计

参照上海洋山四期自动化集装箱码头的工艺布局设计算例，首先说明自动化码头的设计参数，如表3 所示，然后，设置规则并生成算例。考虑两种类型的任务，即进口箱作业和出口箱作业。同一岸桥或同一堆场释放一个待AGV运输的进口箱或出口箱时间间隔分别服从均匀分布U(100，120)、U(40，60)。以进口箱作业为例，说明算例的生成规则。每个进口箱任务包括5 个参数：开始时间t0、作业岸桥Qi、装卸车道Li、目标箱区Bi以及目标车位Pi，其中，依据表3的参数设置，Qi、Li、Bi、Pi分别服从均匀分布U(1，2)、U(1，4)、U(1，3)、U(1，5)。根据作业任务数量，分别产生5组不同规模的算例R10、R50、R100、R200、R400。其中，算例R10见表4。

表3 参数设置Tab.3 Parameter settings

表4 算例集R10Tab.4 Dataset R10

4.2 实验设置

AGV时空网络由Python3.7 平台的NetworkX 工具包编译实现，网格精度设置为6 m ×6 m。算例设计3 组实验以验证模型和算法的有效性。实验假设：1）AGV 数量满足装卸任务需要；2）岸桥和场桥的装卸效率足够高，没有出现延迟或等待现象。实验中采用的基本最短路径算法选取Dijkstra 算法。值得注意的是，AGV 路径规划问题有2个特征，分别为车辆碰撞和路网拥堵，时空网络算法则是能够避免路径之间的碰撞并缓解路网拥堵，因此依据该问题特征，实验对比了2 种不同路径规划求解策略，即基本最短路径求解策略和停车等待求解策略，据此设计了2 个对比求解算法，分别为算法P、SP，算法特征如表5所示。P算法求解过程中不更新时空网络，因此不能规避路径中可能发生的冲突；SP 算法则更新时空网络，检测冲突路段，小车按原最短路径行驶，在缓冲区停车等待以规避碰撞；TS-SP算法通过更新时空网络，检测冲突路段，并且在更新后的时空网络中规划路径以缓解路网的拥堵。

表5 算法特征Tab.5 Algorithm features

实验一 模型与算法的避碰效果验证。分别考虑进口箱作业和出口箱作业下，采用P算法和TS-SP算法求解不同规模的算例，计算两种算法规划出的路径下小车发生的碰撞次数。依据AGV 实际尺寸，实验设置AGV 之间的安全距离为12 m，计算不同规模算例下执行每一个任务的AGV 与路网中其他执行任务的AGV 之间的最小相对距离，其中任务数量用N表示。

实验二 模型与算法的缓解拥堵效果验证。分别考虑进口箱作业和出口箱作业下，采用SP 算法和TS-SP 算法求解不同规模的算例，计算小车总行驶路程、小车总行驶时间、最小完工时间、小车总延误时间、延误任务数量以及延误任务数量占比，分别表示为S、T、M、W、K和G。以算例R400为例，与P 算法求解得的最小任务完成时间相比，计算SP 算法和TS-SP 算法求解下执行每个任务的AGV 到达时间差。又因路网中的拥堵现象表现为小车在行驶过程中因避免碰撞而发生等待行为，故以任务延误时间比上最小任务完成时间表示路网平均拥堵度［24］，其中，N为任务数量。

实验三 算法性能验证。分别考虑进口箱作业和出口箱作业下，采用P 算法、SP 算法和TS-SP 算法求解不同规模的算例，在Win10-PC、i7CPU、内存8 GB 的计算环境下各算法的计算时间，保留4位有效数字。

4.3 结果分析

1）实验一结果与分析。用P 算法和TS-SP 算法求解的碰撞次数以及AGV最小相对距离分别如表6、图5所示。

表6 P和TS-SP算法求解下碰撞次数Tab.6 Number of collisions in P and TS-SP algorithms

图5 AGV最小相对距离图Fig.5 The minimum relative distances of AGVs

由表6可知，P算法求解下小车在任务规模较大时碰撞次数较多，如进口箱作业N=400时，并且碰撞次数随着任务规模的增加而增加，如出口箱作业。而在时空网络算法下，无论任务的规模多大，AGV 之间碰撞次数均为0。该结果说明时空网络算法规划的路径互不干涉，AGV 之间无碰撞从而保证AGV安全作业。

由图5 可知，P 算法求解下部分执行任务的AGV 发生碰撞，AGV 最小相对距离则为0，在未发生碰撞的情形下，仍有部分执行任务的AGV 最小相对距离小于安全距离，如出口箱作业算例R100时。TS-SP 算法求解下，无论任务的规模多大，执行每个任务的AGV 最小相对距离都大于或等于安全距离。AGV 在实际行驶时由于车身长度因素会对不止一个路段具有独占性，从而对路网中其他AGV 行驶产生影响，时空网络算法充分考虑到AGV 车身长度因素使得AGV 最小相对距离始终大于安全距离，结果说明该算法下AGV 行驶过程中是安全的，提高了AGV运行效率。

2）实验二结果与分析。用SP算法与TS-SP算法求解任务集结果、AGV 到达时间差以及路网平均拥堵度分别如表7、图6、7所示。

由表7 可知，1）进口箱作业下，SP 算法和TS-SP 算法求解同一规模算例下AGV 总行驶时间与最小完工时间均相同，任务总延误时间随着任务规模的增加而增加。同等规模下，因TS-SP 算法为避免小车发生碰撞而选择规划新路径，故TS-SP算法求解得总行驶路程大于SP 算法求解得总路程，但TS-SP算法求解得总延误时间小于SP 算法求解得总延误时间，在较大规模下，TS-SP 算法求解得延误任务占比数值较小，如N=400时。2）出口箱作业下，两种算法求解同一规模算例下AGV最小完工时间相同。TS-SP算法求解得总路程大于SP算法下的总路程，但SP 算法下AGV 总行驶时间则较大，如N=200时。任务总延误时间随着任务规模的增加而增加，同等规模下，TS-SP 算法求得任务总延误时间小于SP 算法求得总延误时间；并且当任务规模较大时，TS-SP 算法能有效地缩短总延误时间，如N=400时。TS-SP 算法能有效减少延误任务数量，降低延误任务占比数值，如N=200时。

表7 SP和TS-SP算法求解结果比较分析Tab.7 Comparison of SP and TS-SP solving results

由图6（a）可知，进口箱作业下，TS-SP算法与SP算法求解400 个任务时，大部分执行任务的AGV 到达时间差为0，少部分AGV到达时间差大于0且集中出现在任务规模较大时。在求解第227 个任务时，TS-SP 算法下AGV 到达时间差较大，其他情况下AGV 到达时间差数值相等。SP 算法下平均时间差为3.56 s，TS-SP 算法下平均时间差为3.67 s。由图6（b）可知，出口箱作业下，TS-SP算法与SP算法求解结果中有较多执行任务的AGV 到达时间差大于0 且分布较为均匀。其中，大部分AGV 到达时间差数值相等，少部分到达时间差数值不等，SP 算法求解得AGV 到达时间差较大的任务个数为9，TSSP 算法求解得AGV 到达时间差较大的任务数量为3。SP 算法下平均时间差为3.3 s，TS-SP 算法下平均时间差为3.18 s。值得注意的是，TS-SP算法下AGV到达时间差大于0是由于新规划的路径长度较长，AGV 行驶时间长且行驶过程中也可能出现等待行为；而SP 算法下的时间差大于0是由于AGV 在原路径行驶过程中发生等待行为。该结果表明，大部分任务下，时空网络算法下AGV 依据新规划的路径行驶的时间与停车等待策略下依据原路径行驶的时间相等；少部分任务下，时空网络算法减少了任务完成时间。

由图7 可知，同一作业模式下TS-SP 算法比SP 算法求解得路网平均拥堵度低，当任务规模较大时，路网平均拥堵度较低，如出口箱作业N=400时。由于出口箱作业数量多且间隔时间短，出口箱作业下路网平均拥堵度比进口箱作业下路网平均拥堵度高，如N=200时，进口箱作业下拥堵度为0.089%，而出口箱作业下拥堵度则为0.630%。该结果说明时空网络算法能有效缓解路网的拥堵，减少AGV 停车等待成本，AGV的畅通行驶提高了码头运作效率。

图6 AGV到达时间差Fig.6 AGV arrival time difference

3）实验三结果与分析。用P 算法、SP 算法和TS-SP 算法求解不同规模的算例的计算时间如图8所示。

由图8 可知，进口箱作业和出口箱作业下P 算法、SP 算法和TS-SP 算法求解不同规模算例的计算时间趋势相同，以进口箱作业模式为例，说明计算时间增长趋势。如图8（a）所示，进口箱作业下，计算时间随任务规模的增大而增大，在任务数量小于等于200时，随任务数量增大，计算时间平稳增长；当任务数量为400时，计算时间大幅增长，尤其表现为SP 和TSSP 算法，增长幅度分别为319.86%和347.31%；当任务数量大于等于100时，TS-SP 算法计算时间比SP 算法计算时间长，这是因为TS-SP算法考虑了问题的2个特征（碰撞及拥堵），而SP 算法仅考虑了车辆避碰条件。同等任务规模下，完成出口箱作业的计算时间比完成进口箱作业的计算时间要长，如当N=400时，出口箱作业下TS-SP 算法计算时间为71.870 1 s，而进口箱作业下的计算时间为52.842 s。计算结果说明，TSSP 算法可以在有效的计算时间内完成较大规模任务集计算。

图7 路网平均拥堵度Fig.7 Average congestion rate of road network

图8 3种算法求解不同规模的算例的计算时间对比Fig 8 Calculating time comparison of three algorithms for sloving different scale examples

以上实验结果表明，时空网络算法能有效求解冲突规避的大规模路径规划问题，减少任务延误时间，使进出口集装箱满足岸边或堆场堆存计划安排，大幅度降低自动化码头运营的时间成本以及其他人力、物力成本，并且算法可以考虑AGV 车身长度对路网的影响，更加符合自动化码头实际规划情况。

5 结语

本文针对自动化集装箱码头AGV 行驶过程中路网实际可用路段资源有限的特征，以任务完工时间最短为目标，建立了路径优化的整数规划模型，为求解模型，设计了基于时空网络的启发式算法。算例分析结果表明，该算法能完全避免路径之间的碰撞，与停车等待策略下的路径优化算法相比，该算法能降低路网平均拥堵度，最大降低程度为0.68%。与已有研究相比，本文主要工作包括：1）所建模型考虑了路网中路段的时变冲突并以冲突规避为约束优化AGV 作业路径；2）提出基于时空网络的迭代求解策略，提高ACT 作业系统优化的精细化程度。本文考虑了冲突规避的AGV 作业路径优化问题，而对AGV 能耗约束、任务送达时间窗约束没有考虑，进一步研究还可以考虑基于时空网络的AGV 调度问题，拓展时空网络算法的研究方向。