考虑路径冲突的AGV配置与调度优化

范厚明， 岳丽君， 李 荡， 马梦知

(大连海事大学 交通运输工程学院,辽宁 大连 116026)

0 引言

随着船舶大型化的发展，近年来自动化集装箱码头进入新一轮的快速发展时期。班轮等集装箱船对靠港装卸时间要求严格，即在规定的时间内码头需要完成对靠港船舶的装卸作业，所以保证每艘船在规定的时间内完成集装箱的装卸作业是码头重要的目标。集装箱船的装卸过程如图1所示，包括三个阶段：卸船阶段、装卸同步阶段、装船阶段。在卸船阶段，所有岸桥进行卸船作业，AGV在岸桥下接收进口集装箱并送箱到达指定进口箱区，交付该集装箱后空载行驶到作业下一集装箱的岸桥下。在装卸同步阶段，部分岸桥装船、部分岸桥卸船，AGV在卸船岸桥下接收进口箱并送到指定箱区后，可以前往出口箱区提取装船集装箱并载箱到达指定的装船岸桥下，也可以前往卸船岸桥下作业下一卸船集装箱。在装船阶段，所有岸桥进行装船作业，AGV在出口箱区取箱送至装船岸桥。

AGV作为水平运输工具，往来于船边和堆场之间，服务于岸桥和场桥。若AGV载箱/空驶到达岸桥或场桥下的时刻，晚于岸桥或场桥相应的计划放/提箱时刻，则会导致作业时间发生延误，进而可能无法在要求的时间内完成装卸作业。

为减少场桥延误，大多数自动化集装箱码头在箱区内设立缓冲支架。如图1所示，AGV在卸船岸桥下接收进口集装箱后，沿卸船路线前往堆场送箱，当送箱AGV到达进口箱区的时间早于场桥计划作业时间，若缓冲支架全被占用，即缓冲空间已满，则AGV在场桥下等待；若缓冲空间未满，AGV将进口箱放置到缓冲支架上后继续作业下一集装箱。对于出口集装箱，若取箱AGV到达出口箱区的时间晚于场桥计划作业时间，场桥将集装箱放置在缓冲支架上，AGV到达后在缓冲支架上取箱后，沿装船路线前往岸桥下送箱。缓冲支架的设置减少了场桥延误。为减少岸桥延误，大多数码头选择增加AGV的配置数量。AGV数量增加一方面增加了AGV的等待时间，导致AGV的利用率降低；另一方面增大了发生路径冲突概率，导致AGV到达岸桥下的时间不确定，不一定能有效保证完工时间。

因此，考虑路径冲突条件下，优化AGV的配置及调度以满足船舶的装卸时间要求是迫切需要解决的问题。

图1 装卸过程中AGV运行流程图

针对船舶装卸作业优化问题，韩少龙等[1]利用集装箱港口仿真软件Flexsim-CT建立了包括泊位、岸桥、集卡、场桥和堆场资源在内的集装箱港口装卸作业仿真模型，分析了作业面、作业线和同步装卸三种调度模式对船舶装卸作业时间和装卸设备作业效率的影响。Zeng等[2]以最小化船舶完工时间为目标，分别构建了全场调度模式和同船调度模式下的调度优化模型，并设计了两阶段禁忌搜索算法和Q学习算法来求解这两种模型，最后证明同船调度模式可以减少水平运输工具的空驶时间，提高水平运输工具的利用率。Kim等[3]研究了在确定和随机环境下装卸设备的集成调度问题，以最小化船舶完工时间为目标，将AGV同步分配给岸桥。陶莎等[4]提出了协调岸桥、集卡和场桥作业时间的三级装卸搬运分时协调策略，采用统计学中有序样本聚类的最优分割法将整体作业时间分为几个阶段，分别求最优解。Homayouni等[5]和Luo等[6]分别研究了岸桥和场桥与AGV的协同调度优化，均以最小化最大完工时间为目标，构建了混合整数规划模型，应用模拟退火算法对模型求解。Lim等[7]通过为岸桥配置不同数量的内集卡，来控制岸桥的作业效率。证明了几种不确定环境下，该调度方式可以自动恢复岸桥作业效率、保障船舶装卸时间。常祎妹等[8]讨论了设备作业效率不确定时，集装箱码头各设备的集成调度问题，建立了车船装卸作业集成调度模型并设计了改进的多层遗传算法求解模型。Azevedo等[9]联合考虑船舶配积载计划和岸桥调度问题，研究制定了一系列船舶箱位分配和岸桥调度规则，模拟集装箱装卸顺序和岸桥调度规则的组合，采用遗传算法求解船舶的总装卸时间，比较所有组合的效率。Yang等[10]研究了自动化集装箱码头中岸桥、AGV和场桥的集成调度问题，以最小化完工时间为目标构建了双层模型，设计了基于堵塞预防规则的双层遗传算法求解模型。

针对自动化集装箱码头AGV配置与调度问题，Zhang等[11]提出了三种AGV调度模型并改进了贪婪算法求解；韩晓龙等[12]利用仿真软件分析了不同的AGV调度策略及AGV配置数量对集装箱港口装卸效率的影响；Nishi等[13]同时考虑了AGV的调度和路径规划问题，构建双层混合整数规划模型并利用拉格朗日松弛算法进行求解；Kim等[14]研究了多目标的自动化集装箱码头AGV调度，采用改进的进化算法对问题仿真模拟，得出AGV的配置和调度方案。Choe等[15]提出了OnPL(online preference learning)算法，通过更新偏好函数实时动态调整AGV的调度方案。Wang等[16]研究了同时装卸船模式下AGV调度和堆存位置分配问题，采用树结构表示解空间以增强邻域解搜索能力。鲁渤等[17]建立了ALV调度与堆场位置分配集成优化模型，设计了基于遗传的启发式算法对模型求解，得到了最小化最大完工时间的调度方案。Roy等[18]基于交通流的闭合排队网络模型研究了AGV配置的数量和AGV拥堵对码头吞吐量的影响。张素云等[19]研究了AGV可能发生的路径冲突问题，采用位向量交集运算法检测路径冲突发生概率，通过仿真实验比较了速度控制策略在AGV路径冲突问题中的可行性及有效性。

综上，通过梳理现有文献发现：(1)在船舶装卸作业优化方面，已有文献多为集装箱装卸设备间的调度协同优化，以使得装卸完工时间最小，没有考虑班轮对装卸时间的要求，实际完工时间过短或过长都会对码头造成损失；(2)在自动化集装箱码头AGV的配置与调度优化的研究中，主要优化AGV的配置数量和调度模式，忽略了AGV在运输过程中，因路径冲突造成的实际交箱时间的不确定性对船舶装卸完工时间的影响；(3)现有文献很少考虑AGV利用率问题，在实际运营环境中，码头的AGV资源有限且有较高的运行成本和闲置成本，在保证船舶装卸时间要求的基础上提高AGV的利用率，即调度过程中最小化AGV的空载和等待时间，可以增加码头运营方的效益。

本文在已有研究的基础上，针对集装箱船装卸时间要求，考虑AGV运输过程中因路径冲突导致交箱时间的不确定性，以最小化最大完工时间和最小化AGV的空载和等待时间为目标构建AGV调度优化模型，并设计改进NSGA-Ⅱ算法对模型进行求解，最后通过算例分析验证了本文所提调度优化方案的有效性。

1 问题描述

船舶装卸过程中，AGV在岸桥与场桥之间运输集装箱。岸桥作业的理想状态为岸桥不等待AGV，即AGV在岸桥下随时待命，以使完工时间最小化；AGV运输的理想状态为到达岸桥或场桥后可以立刻取/交集装箱，AGV在岸桥和场桥下的等待时间及空驶时间最短。因此，必须综合考虑岸桥和AGV的目标进行协同优化，单一优化某个目标使其达到理想状态并不满足码头实际作业的要求。要保证岸桥在要求完工时间内完工且AGV空载和等待时间最小，则需要解决以下三个问题：(1)AGV配置数量。配置数量过少时，AGV不能及时到达导致岸桥等待，岸桥不能按计划作业又会产生后续的AGV等待，总装卸完工时间较长，AGV利用率低；数量较多时产生多辆AGV在岸桥/场桥下等待的现象，AGV的空载和等待时间较长；(2)AGV调度方案。调度方案追求的是在给定AGV数量下，确保岸桥完工时间最小化和AGV的空载及等待时间最小化；(3)运输过程中的多辆AGV间的路径冲突。如图2所示，多辆AGV同时到达一个路径节点产生的交叉冲突，多辆AGV同向而行产生的等待冲突，会影响AGV的实际到达时间。

图2 AGV之间路径冲突示意图

在实际作业过程中，路径冲突会增加AGV的运输时间，若AGV的实际到达时间早于岸桥开始作业时间，则AGV在冲突点的额外作业时间不会影响岸桥作业，否则导致岸桥等待，如图3所示，岸桥实际开始作业集装箱2的时刻晚于计划开始作业时刻，最终导致集装箱实际装卸完工时间晚于装卸时间要求。定义该部分为延误时间DT，即岸桥的延误时间=实际完工时间-装卸作业要求时间。

图3 岸桥作业示意图

在船舶装卸作业要求时间内预留一段缓冲时间，有利于最终的实际完工时间早于要求完工时间。AGV因路径冲突导致的岸桥延误时间很难有一个明确的、固定的值。为了衡量其对AGV调度方案的影响，以设置合理的缓冲时间，采用多AGV系统下冲突点等待的调度策略，利用爱尔朗分布模拟实际作业过程中AGV经过冲突点的额外作业时间，则在一次送/取箱过程中，AGV经过m个冲突点时额外作业时间为：

(1)

式(1)中m为AGV经过的冲突点的总个数；θ为AGV在冲突点的平均等待时间。总的AGV额外作业时间服从均值为mθ的爱尔朗分布。假设n个集装箱在运输过程中，发生冲突的概率为β，预设缓冲时间为：

t0=β×n×m×θ

(2)

因为卸船阶段、装卸同步阶段和装船阶段的装卸设备作业特点不同，且各阶段具有机动时间的传递性，为保证船舶装卸时间要求的同时提高AGV利用率，解决存在路径冲突时AGV配置与调度优化问题，本文采用分阶段调度策略，将装卸时间要求分三个阶段，即卸船阶段时间要求、装卸同步阶段时间要求和装船阶段时间要求。在各个阶段内分别考虑AGV的配置与调度方案对船舶装卸时间的影响，建立以最小化最大完工时间和最小化AGV空载等待时间为双目标的调度优化模型。配置的AGV数量不同，模型的非支配最优解不同，将不同AGV数量下模型的非支配解放入调度方案集合中。根据本阶段的实际完工时间，从最优解集中选择下一阶段满足装卸时间要求且AGV利用率最高的配置与调度方案。

2 模型建立

2.1 前提假设

研究基于以下假设：

(1)待作业集装箱位置信息及装卸顺序已知，AGV运输起点为出口箱所属堆场和作业进口箱的卸船岸桥，终点为存储进口箱的堆场和作业出口箱的装船岸桥；

(2)所有待作业集装箱箱型一致最终所有的进口箱运送到指定堆场，所有出口箱运送到船上指定箱位；

(3)堆场按进口箱区和出口箱区分类，每个箱区有且只有一台场桥作业；

(4)只有在前一集装箱作业完成后才能作业后一集装箱，即岸桥、场桥和AGV均不能同时作业两个集装箱。

2.2 符号说明

(1)输入变量

n=1,2,…,N,N为待装卸集装箱总量，其中N+表示待装船集装箱总量，N-表示待卸船集装箱总量；k=1,2,…,K,K为装卸船岸桥配置数量；c=12,…,C,C为场桥数量；v=1,2,…,V，V为AGV配置数量；b=1,2,…,B，B为船舶总贝位数；P为缓冲容量，即每个箱区的缓冲支架上可以同时放置集装箱的数量；τ1和τ2分别为岸桥、场桥完成一个集装箱装卸作业的平均时间；σ为岸桥移动一个贝位的时间；eik为第i个集装箱在岸桥k下的计划开始作业时间，即岸桥k计划从AGV上提起待装船集装箱i的时刻，或岸桥k计划放下待卸船集装箱i到AGV的时刻；TF为每个阶段要求的装卸完工时间。

(2)中间变量

Nk为岸桥k作业集装箱的总数量；Eik为AGV无路径冲突时岸桥k实际开始作业集装箱i的时间；Emax为最大实际完工时间，是AGV无路径冲突时岸桥提起最后一个待装船集装箱或放下最后一个待卸船集装箱的时刻；wikv为运载集装箱i的第v辆AGV在岸桥k下的等待时间；tiv为第v辆AGV运载集装箱时的行驶时间；tijv为第v辆AGV交付集装箱i后前往下一个集装箱j所在位置的空驶时间；[ETic,LTic]为场桥c下AGV可放/提集装箱的时间窗；wicv为运载集装箱i的第v辆AGV在场桥c下的等待时间；τij为岸桥k提取/放下集装箱i后作业集装箱j所用的时间；tab为岸桥k由贝位a移动到贝位b所需要的时间；ubk为岸桥k开始作业贝位b的时刻；div为第v辆AGV开始作业集装箱i的时刻，tiv为第v辆AGV将集装箱i运输到目的地所用的时间，即运输待装船集装箱到作业岸桥下或运输待卸船集装箱到堆存箱区。Fvc为第v辆AGV已经送箱到箱区c或已从箱区c取箱的数量；Sic为场桥c开始作业集装箱i的时刻；Hc为场桥c已装卸集装箱的数量。

(3)决策变量

征稿内容： 自然灾害(特别是地质灾害)与人为灾害防治，生态环境、资源环境和地质环境保护，水文地质与工程地质，岩土工程与工程勘察，与本学科有关的边缘和交叉学科等方面的优秀论文，最新科技成果，新理论、新方法、新技术研讨，及工程技术经验总结，新成就、新动向方面的综述、述评，新书刊、新设备评介等。

2.3 优化模型

本文采用分阶段调度策略，将整个装卸作业分为三个阶段，在每个阶段内建立AGV的调度优化模型，如下：

调度优化目标：

(3)

(4)

约束条件：

(5)

(6)

(7)

(8)

ejk=max(Eik+τij,ejk),i,j∈N

(9)

Eik=max(div+tiv,eik),∀i∈N+

(10)

(11)

ubk≥uak+tab

(12)

Emax≤TF-t0

(13)

(14)

Sic+τ2≤ETic,∀i∈N+

(15)

ETic≤Sic, ∀i∈N-

(16)

wikv=max{eik-div-tiv,0},∀i∈N+

(17)

wikv=max{eik-div,0},∀i∈N-

(18)

wicv=max{ETic-div,0},∀i∈N+

(19)

wicv=max{ETic-div-tiv,0},∀i∈N-

(20)

div+tiv+wikv+tijv+wjcv≤djv,∀i∈N+,j∈N+

(21)

div+tiv+wikv+tijv+wjkv≤djv,∀i∈N+,j∈N-

(22)

div+tiv+wicv+tijv+wjcv≤djv,∀i∈N-,j∈N+

(23)

div+tiv+wicv+tijv+wjkv≤djv,∀i∈N-,j∈N-

(24)

(25)

xiv,yik,zic,xijv∈{0,1},∀i,j∈N

(26)

div≥0, ∀i∈N

(27)

式(3)和式(4)为目标函数，其中f1表示最小化最大完工时间，f2表示最小化所有AGV的空载时间、场桥下等待时间和岸桥下等待时间之和；式(5)和式(6)表示一个集装箱由且仅由一辆AGV运输；式(7)和式(8)分别表示一个集装箱由一台岸桥或场桥作业；式(9)表示更新后的岸桥计划作业时间；式(10)和式(11)分别表示作业装船集装箱或卸船集装箱的岸桥的实际作业时间；式(12)表示岸桥由当前贝位移动到下一贝位后开始作业时间；式(13)表示每个阶段的船舶装卸要求约束；式(14)表示每个箱区的缓存容量约束；式(15)和式(16)分别表示作业待装船集装箱或待卸船集装箱的岸桥开始作业的时间约束；式(17)和式(18)分别表示AGV交付装船集装箱或提取卸船集装箱时在岸桥下的等待时间；式(19)和(20)分别表示AGV提取装船集装箱或交付卸船集装箱在场桥下的等待时间；式(21)和式(22)分别表示AGV在送完装船集装箱后，作业下一个装船集装箱或卸船集装箱的时间约束；式(23)和式(24)分别表示AGV在送完卸船集装箱后，作业下一个装船集装箱箱或卸船集装箱的时间约束；式(25)表示本阶段AGV的利用率；式(26)和式(27)分别表示变量的类型和取值范围。

3 模型求解

3.1 算法设计

本文研究的AGV配置与调度优化问题属于NP-hard问题，很难获得精确地最优解，又因为所建立的混合整数规划模型需要优化两个目标，NSGA-Ⅱ算法[20]具有全局优化性能，在多目标优化中有较为广泛的应用，因此，本文结合具体问题对NSGAⅠ算法进行了改进，详细求解步骤如下：

(1)个体编码和解码

本文研究内容属于实际调度优化问题，采用实数矩阵编码的方式更易于理解。设计一个三行n列的染色体，染色体长度代表待装卸的集装箱总量，染色体第一至三行的基因值分别为集装箱作业序号、岸桥序号、场桥序号。以10个待装卸的集装箱，3辆AGV为例。如图4所示，首先对待装卸的集装箱按其岸桥计划作业时间的先后顺序进行编号，岸桥计划作业时间较早的集装箱作业序号小；岸桥序号表示，装/卸相应集装箱的岸桥的编号，由进口集装箱所在船舶贝位和出口集装箱的目标贝位决定；场桥序号表示作业相应集装箱的场桥的编号，由集装箱在堆场中的位置决定；集装箱箱号与作业序号、岸桥序号、场桥序号一一对应。

(2)初始种群生成

随机生成初始种群，根据可利用的AGV数量生成随机切断点，两断点间的染色体分配相同的AGV序号，AGV序号表示运载相应集装箱的AGV的编号，如图4所示。

图4 染色体

(3)非支配排序与精英保留策略

对候选池中个体，依据公式(3)和(4)计算两个目标函数值，两目标值不能同时小于其他个体的所有个体组成非支配前沿，非支配前沿中个体视为精英个体，直接进入下一代。若非支配前沿个体数量小于种群规模，则计算下一前沿面中个体的拥挤度。个体的拥挤度设定为与相邻个体相应目标值的差，均一化处理后得到每个个体的拥挤度，保留拥挤度值较大的个体进入下一代。

(4)交叉

采用部分匹配交叉(PMX，Partial Mapped Crossover)的交叉方式对两个父代个体进行交叉操作生成同等规模的两类子代。具体操作过程如图5所示。

图5 染色体交叉

从所有个体的第一行(即集装箱的作业序列)中，随机选择两个用来交叉的父代个体，然后再随机选择两个交叉点位置，置换两交叉点之间的染色体片段，剩余部分按顺序排列，形成两个子代染色体。子代染色体中，每辆AGV作业量与父代相同，作业的集装箱序号发生改变。父代个体和子代个体均进入候选池中。

(5)变异

采用均匀变异算子(Uniform Mutation)的方式，变异作业序列对应的AGV序号。在[0,V]内，产生均匀分布的随机数，以一定的概率来替换父代染色体对应的原有AGV序号，最终产生新的AGV分配方式，如图6所示。

图6 染色体变异

(6)终止条件设置

若算法的迭代次数达到预先设置的最大次数，则输出结果，否则返回到步骤(3)。

3.2 算法性能评价指标

采用NSGA Ⅰ算法对模型求解，得到一组非劣解集形成的近似Pareto前沿，通过计算非劣解集的收敛性和分布性可判断解的优劣[21]，结合现有研究和集装箱码头调度问题的特性，采用收敛度和分布性评价本文算法性能：

(1)收敛度

收敛度可以反映非劣解集与真实 Pareto前沿之间的逼近程度。随着待装卸集装箱数量的增加，问题复杂度增大，真实的Pareto前沿无法获取。因此本文用函数的最小值代替模型最优解。考虑理想状态下，若AGV在岸桥和场桥下不等待，由公式(4)～(8)和(21)～(22)可解得f1的最小值o1；若岸桥不延误，由公式(3)、(5)～(12)可解得f2的最小值o2。计算第G代收敛度值时，首先计算非劣解中各点到(o1,o2)的欧几里得距离：

(28)

然后将第G代解集中各点欧几里得距离均值除以初始解中对应的距离均值，可得收敛度γ，γ越小表明算法性能越好。

(2)分布性

分布性可以体现非劣解集中个体在前沿面分布的均匀程度。通过近似Pareto前沿中每个个体到与其最近的个体的距离求分布性Δ：

(29)

(3)运行时间

算法的复杂度直接影响算法的运行时间，程序计算时间AT越小，算法性能越好。

4 算例分析

4.1 算例比较

为了评价在优化集装箱码头AGV调度问题中所提出的算法的性能，参考文献[22]中目标函数和数据，最小化AGV空载时间与岸桥延误时间和场桥运行时间的总和，其中三个目标函数的比例分别为0.1、0.8和0.1。运行程序20次，对比所得目标函数值。表1中列举了文献[22]和本文算法的计算结果，Optimal、Best、Average分别表示最优解、启发式算法所求解的最优值、平均值，AT表示算法运行时间，Dev表示最优值与最优解间的偏差。

表1 小规模算例结果对比

由表1知，当问题规模扩大到16个集装箱时，CPLEX已经无法在有限时间内求得精确解，而本文提出的算法，却可以在很短的时间内，求得近似最优解，并且本文提出的算法所求得的函数值与CPLEX求得的精确解之间的平均误差仅为3.08%，故本文算法可用于求解集装箱码头AGV调度问题。

4.2 实例分析

本文以青岛某自动化码头车道布局图及水平交通规则[23]为研究背景，待装卸船舶到达泊位后，设有2台岸桥同时作业。将整个集装箱码头分为8个作业点，其中1～2为岸桥作业点，3～5为进口箱区场桥的作业点，6～8为出口箱区场桥的作业点。AGV空载速度为5m/s，重载速度为3.5m/s，岸桥和场桥的平均单箱作业时间分别为：120s和180s。岸桥沿船舶方向移动一个贝位所需时间为300s，场桥下缓冲支架最多可同时放置4个集装箱。随机生成船上每个贝位(共有12个贝位)中待装、卸集装箱数量，如图7所示。待卸船集装箱在堆场的目标箱区和待装船集装箱现堆存箱区已知，如表2所示。

图7 待装卸集装箱堆存位置

表2 进出口箱区场桥作业集装箱数量

所有集装箱要求24h内完成装卸作业，分配装船、装卸同步和卸船三个阶段中的岸桥作业量和装卸时间要求如表3所示。采用爱尔朗分布模拟实际作业中因路径冲突产生的额外作业时间，AGV在冲突点的平均等待时间θ=2.5，AGV一次运输过程中经过冲突点的个数m=2，AGV发生冲突的概率β=0.2。

表3 各阶段作业集装箱量和装卸时间要求

(1)计算结果

采用matlab 2016b编写算法，设置种群大小为100，最大迭代次数为1000。对配置不同数量AGV时上述实例中三个阶段的调度模型求解10次，将10次的运算结果放入最优解集中，从中选出种群规模大小、分布均匀的非支配解。在每阶段非支配解集中选择满足装卸时间要求且AGV利用率最高的调度方案，AGV空载和等待时间、岸桥完工时间、AGV利用率、算法收敛度和分布性以及运算时间的结果见表4。

表4 配置不同数量AGV时的最优调度结果和算法性能

卸船阶段计划两台岸桥共卸载393个集装箱，计划完工时间为27720s，预设缓冲时间为393s；由表3可知，配置6辆AGV时利用率最高。采用爱尔朗分布模拟实际运输过程，所得路径冲突造成岸桥等待作业时间为248s，完工时间为27565s，可比计划完工时间提前155s。装卸同步阶段计划岸桥1卸载240个集装箱，岸桥2装载247个集装箱，预设缓冲时间为487s；配置4辆AGV，模拟实际运输过程得路径冲突造成岸桥等待作业时间为412s，完工时间为32947s，可比计划完工时间提前547s。装船阶段计划装载363个集装箱，预设缓冲时间为363s；配置6辆AGV，模拟实际运输过程得路径冲突造成岸桥等待作业时间为207s，完工时间为26418s，可比计划完工时间提前138s。在考虑路径冲突时，整个装卸过程实际完工时间为85560s，比船舶装卸要求完工时间提前了840s。该配置下相应的AGV的调度方案如图8所示：

图8 AGV配置与调度方案

(2)与现有调度方案对比分析

为了进一步验证本文所提的双目标调度优化方案的有效性，将本文与单一目标最优时的调度优化方案对比，即分别以最小化AGV空载和等待时间为目标(方案一)和最小化最大完工时间为目标(方案二[6])，对上述算例进行数值实验，计算不考虑路径冲突时最优配置下各个阶段AGV的空载和等待时间、实际完工时间、延误时间、AGV的利用率。实验结果如表5所示。

对比三种调度优化方案发现，采用方案一时，三个阶段延误时间之和为15302s，最高AGV利用率可达到53.8%，表明以最小化AGV空载和等待时间为调度目标，虽然有较高的AGV利用率，但不能在要求的时间内完成装卸船作业，不符合实际码头作业要求；采用方案二时船舶可提前4102s完成集装箱装卸作业，最高AGV利用率仅为16.4%；采用本文方案时船舶可提前156s完成装卸作业，且最高AGV利用率为37.2%，AGV空载和等待时间相较于方案二减少了162505s，满足实际作业要求的同时提高了AGV的利用率。对比结果说明本文研究在保证船舶装卸时间和提高AGV的利用率方面具有优势。

表5 不考虑路径冲突时不同优化目标调度结果

(3)鲁棒性分析

忽略AGV运输过程中的路径冲突，将会影响调度方案的鲁棒性，可能导致船舶装卸作业的延迟。为了验证存在AGV路径冲突时本文模型和调度策略的有效性，保持其他参数不变，改变冲突发生概率β和冲突点个数m的值，最终的实际完工时间和AGV的利用率如图9和图10所示。

图9 不同β和值对实际完工时间的影响

图10 不同β和值对AGV利用率的影响

从图9中看出，在发生冲突概率不同、冲突点个数不同的情况下，本文所提的分阶段调度策略均可以保证在船舶装卸时间的要求内完成装卸作业。从图10中看出β和m发生变化时，AGV的利用率会降低，但整体利用率仍高于方案二。本文所提模型和调度策略更符合自动化集装箱码头的实际要求。

5 结论

本文在对自动化集装箱码头AGV配置与调度问题的研究中，考虑了靠港船舶装卸时间要求的约束和AGV运输中路径冲突对岸桥作业时间的影响，建立了AGV调度优化的多目标模型，并改进了NSGA-Ⅱ算法对其求解，算例分析结果表明：本文所提出的AGV配置与调度方案可以确保船舶在要求完工时间内结束装卸作业，同时提高了AGV利用率。但本文还存在一些不足，没有考虑集装箱在船舶和堆场位置分配，而实际操作中，集装箱的堆存位置会影响AGV的送取箱时间，进而影响船舶的装卸作业时间。因此，综合考虑集装箱堆存位置约束和船舶装卸时间要求，优化AGV的配置与调度方案将作为未来的研究方向。