自动化集装箱码头AGV 配置与调度耦合问题研究

梁承姬，陈登川

1.上海海事大学 物流科学与工程研究院，上海 201306

2.西安外事学院，西安 710000

1 引言

自动化集装箱码头作为绿色港口与智慧港口的象征，是未来大型港口发展的一个趋势。自动化码头设备主要分为装卸设备和水平运输设备，所以自动化码头可以分为两大系统：装卸系统和水平运输系统。装卸系统主要由岸边桥式起重机（以下简称岸桥）与堆场桥式起重机（以下简称场桥）构成；水平运输系统主要由自动导引小车（Automated Guided Vehicle，AGV）构成。水平运输系统作为连接自动化码头装卸设备的枢纽，有着至关重要的作用。提高水平运输系统的作业效率能够直接提升装卸设备的作业效率，进而提高整个自动化码头的作业效率。增加AGV的使用数量可以直接提升装卸设备的作业效率，但是过多地投入AGV会造成AGV之间的互相等待，从而引起运输区域的拥堵。所以在满足任务时间的要求下尽量减少AGV使用数量能有效减少AGV的拥堵和互相等待。

在传统集装箱码头集卡协调调度研究领域，梁承姬等[1]以岸桥延迟时间、集卡空驶时间及任务对的时间差的加权和最小为目标，建立岸桥集卡协调调度模型，并分析了遍历不同集卡数量时岸桥-集卡最佳的数量配比。赵金楼等[2]考虑空载率和集卡使用数量对集卡运输效率的影响，构建了集装箱码头的集卡两阶段路径优化模型。张笑菊等[3]基于岸桥同贝同步装卸作业的岸桥与集卡联合调度问题，以船舶装卸完工时间最短为目标，建立岸桥与集卡联合调度优化模型，优化岸桥与集卡的任务分配及作业序列。梁承姬等[4]综合考虑集装箱顺序及岸桥干涉、集卡作业面调度等约束，建立混合整数规划模型，并使用遗传算法进行求解。孙清臣等[5]针对双循环集卡操作策略，建立了岸桥和集卡联合优化混合整数规划模型，并验证了模型的有效性。严南南等[6]针对岸桥集卡协调调度，采用遗传算法进行求解建立集卡能耗和岸桥集卡作业时间的多目标数学模型，最终验证了模型和算法的有效性。Tang等[7]针对岸桥、集卡联合角度问题，以最小化装卸船完工时间为目标，建立混合整数规划模型，并利用粒子群算法进行求解。在传统码头集卡调度耦合优化方面，樊陆彬等[8]从不确定性角度出发，采用多学科变量耦合优化设计的方法，同时考虑集装箱任务时间窗约束建立了岸桥和集卡协调调度耦合模型，并验证了模型的有效性和实用性。在传统码头集卡和岸桥的耦合调度问题方面已经有学者进行了研究，为自动化码头AGV调度问题研究提供了思路。

在自动化码头AGV调度的研究领域，杨雅洁等[9]考虑AGV避碰，建立了一个以所有任务最大完工时间最小化为目标的混合整数规划模型，并对有无避碰规则下的实验数据进行了比较和分析。杨勇生等[10]考虑AGV和RMG的任务分配约束，以最小化卸船作业最大完工时间为目标，建立混合整数规划模型，并设计不同规模算例对模型进行验证。添玉等[11]以最小化船舶在港时间和主要设备作业成本为目标，构建了新的装卸混合模式下岸桥、AGV及自动化轨道吊协同调度的混合整数非线性规划模型，并提出一种遗传算法与启发式策略结合的协同调度方法。Wang等[12]考虑边装边卸模式中，用混合整数规划模型描述车辆调度、堆场起重机调度和集装箱存储位置之间的相互关系，小规模用CPLEX求解，大规模用遗传算法求解，有效减少集装箱任务的完成时间来缩短船舶周转时间。马跃汇等[13]为研究不确定环境下自动化集装箱码头AGV调度与配置问题，建立了以最末任务结束时间最小化为目标的基本模型。宗辰光等[14]采用多层编码粒子群-遗传算法融合，对成本优化问题进行了仿真研究，给出了成本变化曲线及AGV调度甘特图。马孙豫等[15]建立以卸船作业最末任务结束时间最小化为目标的混合整数规划模型，采用多层编码粒子群算法进行求解。在自动化码头AGV调度方面，国内外学者多以确定AGV数量的情况下对AGV调度问题展开研究，鲜有学者对AGV数量和AGV调度问题同时展开研究。

综上述可知，目前文献在集卡调度或者AGV调度的研究上多是确定设备数量后再对整体调度方案进行求解。但在自动化集装箱码头的实际生产活动中，装卸设备与运输设备之间为耦合关系，设备的调度方案和设备使用数量之间是相互影响的，所以不应该采用单向协调的方法。本文基于此，综合设备数量和调度方案，采用多学科变量耦合优化设计的思想，建立耦合模型，来获得最优的整体最优调度方案。

2 问题描述

自动化集装箱码头的作业模式分为装船作业和卸船作业，装船作业是出口集装箱（以下简称出口箱）从堆场出发被运输至目标岸桥，再由岸桥抓取集装箱放至船舶目标贝位的过程，卸船作业则与装船作业相反。AGV作为连接岸桥和场桥的运输设备，需要根据集装箱任务的要求选择不同的运输方式，运输方式如图1所示。

图1 自动化集装箱码头AGV运输方式

本文考虑AGV的双循环作业，即有四种运输方式：（a）只卸，岸桥卸箱后满车运输到进口箱区，场桥提箱后，空车回岸边；（b）只装，从堆场的出口箱区满车运输到岸边等待岸桥装船，再空车回堆场；（c）先装后卸，从堆场的出口箱区满车运输到岸边等待岸桥装船，空车去另一台岸桥处等待岸桥卸箱，再满车运输到进口箱区；（d）先卸后装，从岸桥处满车运输到进口箱区，场桥提箱后，空车去出口箱区，此箱区场桥装箱后，满车运输到岸边等待岸桥装船。

在作业过程中，AGV与岸桥之间会产生互相等待的时间，因此需要尽可能缩短互相等待的时间。增加AGV数量能直接减少设备间互相等待的时间，但是一味地增加AGV数量会造成AGV资源浪费、码头前沿交通拥堵等问题。自动化码头AGV作业系统是个复杂的系统，其不仅包括AGV本身，而且还涉及到岸桥和场桥的大型设备，需要采用多设备协调调度的方法来求得复杂系统的最优运行状态。

本文就以此为出发点，根据多学科变量耦合优化设计方法（如图2），将AGV作业系统分解为两个同层级的子系统，即AGV调度子系统和AGV配置子系统，并建立AGV调度模型、AGV配置模型和AGV协调调度耦合模型。AGV调度模型要解决的是AGV具体的任务作业顺序，即每辆AGV以何种顺序运输哪一个集装箱，使得AGV与岸桥的互相等待时间最小；AGV配置模型要解决的是在满足集装箱任务完成情况下需要配置至少几辆AGV的问题；AGV协调调度耦合模型是为了判断上述两个模型计算结果是否符合要求。并将岸桥完成集装箱任务的时刻和AGV的数量作为公用设计变量连接两个子系统，形成耦合关系，并通过迭代的方法不断更新公用设计变量。给出本文的AGV作业系统耦合模型框架，如图3所示。在图3中，AGV调度子模型的输入为AGV数量与岸桥完成集装箱任务的子时刻，输出为岸桥完成集装箱任务的时刻，将该AGV调度子模型的输出输入到协调调度模型中进行运算，若符合迭代计算条件，则将岸桥完成集装箱任务的时刻作为输入条件输入AGV配置子模型。AGV配置模型的输入为岸桥完成集装箱任务的时刻，输出为AGV数量与岸桥完成集装箱任务的子时刻，将AGV配置子模型的输出输入到协调调度模型中进行运算，若符合迭代条件，则将AGV数量和岸桥完成集装箱任务的子时刻作为输入条件输入AGV调度子模型。如此循环求解，形成了两个子模型之间的耦合关系。

图2 多学科变量耦合优化设计方法

3 数学模型

3.1 Model I：AGV调度模型

符号：

i,j：集装箱任务。

I,F：虚拟的初始和结束任务。

P：集装箱任务总和。

J+：装箱任务集。

J-：卸箱任务集，且有J=J+⋃J-。

k：AGV的集， ||k=K，有k辆AGV完成运输任务，则有k条直接路径。

Jˉ ：所有任务，Jˉ={ }I,F ⋃J。

参数：

ti,j：AGV在作业任务i与任务 j之间的时间间隔。

si,j：AGV在任务间的空车行驶时间。

hqi：岸桥处理各任务的时间。

hyi：场桥处理各任务的时间。

ωi,j：AGV完成任务i紧接着去完成任务 j产生的时间延误成本。

qsi：岸桥可处理集装箱任务i的时刻。

图3 AGV作业系统耦合模型框架

决策变量：

xijk：0-1变量，1表示AGVk完成任务i后去完成任务 j。

ωi,j分为两种情况：AGV晚到，即qsi+ti,j-qsj≥0，此时岸桥需要等待AGV；AGV早到，即qsj-qsi-ti,j≥0,此时AGV需要等待岸桥。所以：

其中，a是AGV早到引起延误的时间成本系数，b是AGV晚到的引起延误的时间成本系数，a和b均为不大于1的正随机数。由于岸桥的是自动化码头唯一与船舶直接接触的设备，岸桥误工会引起船期的延误，所以应当调节系数的大小，尽量避免岸桥等待AGV。

ti,j表示AGV在作业任务i与任务 j之间的时间间隔，根据AGV运输方式确定ti,j的计算方式为：

由于船舶装卸集装箱对船舶平稳性有严格的要求，所以本文假设每台岸桥有着严格的装卸作业顺序，相应地计算ti,j不能违反岸桥的装卸顺序，例如对于岸桥k，若i>j，则规定ti,j=M,M趋向于正无穷，表示岸桥k的i任务不能在 j任务之前完成。

方程（2）为Model I的目标函数，表示各集装箱任务作业过程中总延误时间成本最小；约束（3）表示每个任务的继后任务只能由同一辆AGV完成；约束（4）表示对于每个任务的先前任务只能由同一辆AGV完成；约束（5）表示对于中间任务，需要运输平衡，即输入等于输出；约束（6）表示k辆AGV都必须完成起始任务，即共有k辆AGV参与调度；约束（7）表示k辆AGV完成结束任务，即共有k辆AGV结束调度；约束（8）表示决策变量AGV的作业顺序为0-1变量，1表示AGVk完成任务i之后完成任务 j。

通过上述模型求解出AGV的作业任务顺序，即调度方案。通过实际的AGV任务作业顺序，可以计算出每个集装箱任务的实际被操作时刻ri,ri分为卸船时刻和装船时刻。卸船时刻即为吊具接触集装箱的时刻，装船时刻即为吊具离开集装箱的时刻，ri的计算公式如下：

3.2 Model II：AGV配置模型

岸桥装卸每个任务都有作业时间窗，本文由ei和ri这两个值构成时间窗[ei,ri]，其中ei为任务i的最早可处理时刻，ri为岸桥实际处理其所属集装箱的任务完成时刻。将每个任务的时间窗等分成n段，则每个任务可在这n个时刻中选择一个时刻完成，当选择的任务完成子时刻点越来越接近ei时，表示单个任务的延误时间越来越小，从而使所有任务的延误时间最小化。以5个任务为例，每个任务的作业时间窗4等分，可得到如图4所示的网络图。在图4中，第一台AGV从起点s点出发依次经过任务1、4、6、22，最后到达终点 t。第二台AGV从起点s点出发，只经过任务9后直接到达终点t点。所以从起始点s点出发到达结束点t点并经过所有时间窗，至少需要2条直接路径，所以完成5个任务至少需要2台AGV。其中s点表示虚拟起始任务完工时刻，t点表示虚拟结束任务完工时刻，图中的AGV必须满足车辆约束和时间窗约束。

图4 AGV配置模型的网络示意图

通过Model II计算得到的结果有：AGV数量和任务完成子时刻。AGV数量为Model I输入条件，任务完成子时刻作为新的qsi的值。

集合：E表示所有任务完成子时刻的集合。

符号：

i,j：表示集装箱任务；

g,h：表示集装箱任务处理的子时刻；

s,t：表示虚拟的起始时刻和结束时刻；

n：时间窗的等分量。

参数：

ei：任务i的最早完成时刻；

ri：岸桥实际完成其所属的集装箱任务的时刻；

ti,j：表示运输时间。

决策变量：

Zgh=1表示AGV在g时刻完成某一任务后在h时刻完成下一个任务；

v表示AGV的数量。

建立模型：

方程（10）为Model II的目标函数，表示最小AGV数量；约束（11）表示起始点有v辆AGV；约束（12）表示终止点有v辆AGV；约束（13）表示中间点输入输出平衡；约束（14）表示对于每个任务，其继后任务时间窗内的子时刻只能选择一个；约束（15）表示对于每个任务，其先前任务时间窗内的子时刻也只能选择一个；约束（16）表示同一AGV完成的先后任务的子时刻的时间间隔不能小于任务间的运输时间；约束（17）表示作业顺序中继后任务的时刻不能小于先前任务；约束（18）表示决策变量为0-1变量，AGV数量为整数。

将Model II得到的AGV数量和任务完成子时刻输入AGV协调调度耦合模型，判断是否符合迭代条件，若是，则将新的AGV数量作为输入条件入Model I中计算。

3.3 AGV协调调度耦合模型

在上述AGV调度和AGV配置子模型的基础上协调调度和配置问题，实现AGV协调调度的最优。这需要将调度和配置子模型进行多次的循环迭代计算，不断更新公用设计变量的值，并设定相应迭代计算判断条件来控制协调子模型的耦合计算。

迭代计算条件：

式（19）约束了任务的最早处理时刻和实际处理时刻差的容许范围不得超过ε；式（20）约束了AGV的数量，nqc表示岸桥数量，nb表示箱区数量；式（21）表示同一岸桥的先后集装箱任务处理时刻差不能小于其最早处理时刻差；式（22）表示同一岸桥的先后集装箱任务在任务时间窗内处理的子时刻差不能小于其最早处理时刻差。

迭代计算流程如下：

将Model I中求得的 ri代入式（19）和式（21）判断是否符合，如符合，则将ri代入Model II中；若不符合则跳回Model I重新计算，直到满足式（19）和（21）。

将Model II中得出的AGV数量与任务处理子时刻g,h值分别代入式（20）和式（22）进行判断，若符合，则将AGV数量与更新后的qsi输入Model I进行第二次迭代；否则，重新计算Model II，直到满足式（20）和（22）。

为了更直观地表示迭代计算流程，给出如图5所示的迭代计算流程图。

图5 迭代计算流程图

按照上述流程不断地循环迭代，直到不再符合迭代条件，或者所求的目标函数值不再变动，则停止循环迭代计算，最终将得到最优的AGV配置数量和调度方案。

4 算法设计

根据上述建模思路，本文提出一种循环求解算法，分为Model I算法和Model II算法，并将耦合迭代条件融入两个算法中。

4.1 Model I算法设计

本文中的AGV调度问题为NP-hard问题，在现有的研究中，遗传算法广泛应用于AGV的调度研究中。Model I为AGV调度模型，决策变量为AGV作业集装箱任务的顺序，求解算法采用遗传算法来设计，设计的内容主要为如下5个部分。

（1）染色体编码

染色体采用实数编码的形式，染色体长度等于m（集装箱任务总数）+n（AGV数量）+1，即染色体长度=m+n+1，基因值为任务编号，其中不同AGV之间的任务用0元素隔开。把同一台AGV任务所在的基因片段称为任务片段。如图6所示的染色体，从第二个基因位开始基因值依次为4，9，23，14，3，37，表示第1台AGV的作业编号，依次为4，9，23，14，3，37。

图6 Model I算法染色体编码示意图

具体步骤：

步骤1在染色体第一位生成第一个0元素。

步骤2若第i位基因值为0，那么随机选取nqc个最小qsi值所对应的任务编号作为第i+1位基因值。否则，转步骤3。

步骤3根据第i位基因值选取满足车辆约束与时间窗约束的继后任务编号，若继后任务数量为0，则选取0元素作为第i+1为基因值，并转步骤2；若继后任务数量等于1，则选择唯一任务号作为第i+1为基因值；若继后任务数量大于1，则转步骤4。

步骤4在若干可行继后任务号中，计算各个继后任务与先前任务的ri值，规定每个继后任务的都有适应度值 f=1/(ri-ri-1)，应用轮盘赌法选择出继后任务号作为第i+1位基因值。转步骤3。

步骤5重复步骤2，直至所有任务选取完毕。其中继后任务编号满足迭代约束条件（19）和约束（21）。

（2）适应度函数

Model I为最小化问题，适应度越大的染色体对应的目标函数应该越小，其中f1(x)为适应度值，y1(x)为目标函数值。

（3）选择、交叉

选择操作为轮盘赌法。

由于染色体中含有0元素，不能直接进行交叉，在这里采用线性交叉的方法，具体步骤如下：

步骤1随机选择一个不与0元素相邻的基因作为交叉片段1的起点 p，交叉片段1为：从 p开始至任务片段最后一个基因为止。

步骤2寻找是否存在允许任务p作为继后任务的不与0元素相邻的任务q。若存在，标记q的继后任务为 p′，生成交叉片段2：从 p′开始至其所在任务片段最后一个基因为止；若不存在，则转步骤1。

步骤3交换交叉片段1与交叉片段2在染色体中的位置。

步骤4重新计算各个任务的ri，若使ri满足约束（19）和（21），则结束变异过程；若不满足，则转到步骤1，重新开始。

为更清楚地展示交叉过程，给出交叉过程示意图，如图7所示。

图7 Model I算法交叉过程示意图

（4）变异

步骤1随机选择一个非0元素基因作为变异点s。

步骤2若s为其所在任务片段的第一个任务，发现s的继后任务为z，随机选出任务z的非s可行先前任务s′。

步骤3检查s′替换为s后染色体的可行性，若可行，则交换s与s′的位置；若不可行，则返回步骤1。

步骤4重新计算各个任务的ri，若使ri满足约束（19）和（21），则结束变异过程；若不满足，则转到步骤1，重新开始。

为了更清楚地展示交叉过程，给出交叉过程示意图，如图8所示。

图8 Model I算法变异过程示意图

（5）循环终止条件

达到设定最大迭代次数即终止循环。

4.2 Model II算法设计

Model II模型目标函数为最小化AGV的使用数量。通过对Model II模型的特点进行分析，考虑AGV配置模型的特殊性，采用单亲遗传算法。给出的Model II算法如下：

（1）染色体编码

采用浮点数编码方式，染色体长度等于m（集装箱任务总数）+n（AGV数量）+1，即染色体长度=m+n+1。基因值的整数部分为任务编号，小数部分为整数部分任务的任务完成子时刻在时间窗中的具体等分点，AGV的数量为0元素数量总和减1。如图9所示，第二个基因值为1.4，表示1号任务的完成子时刻为第4个等分点，其染色体基因值顺序满足车辆约束与时间窗约束。

图9 Model II算法染色体编码示意图

具体步骤：

步骤1根据4.1节染色体生成方式生成Model II算法染色体的整数部分。

步骤2根据已生成的整数部分为每个整数值添加小数部分，小数部分满足约束（21）与（22）。

步骤3检查AGV数量是否满足约束（20）。若是，则结束编码过程；否则，重新开始步骤1。

（2）适应度函数

f2(x)=1/(c(x)+y2(x))，其中f2(x)为适应度函数值，c(x)为AGV数量的最大估计值，y2(x)为Model II的目标函数值。

（3）选择、变异操作

选择操作为轮盘赌法。适应度较大的染色体被选择的概率会比较大。

在此算法设计的染色体中，随意变异某个基因值的整数部分会引起一连串基因值的变化，且对AGV数量的变化不会起到明显的作用。所以变异方法为：在每个任务片段中随机选取一个基因值，将其小数部分变为满足约束（21）与（22）的值。

（4）循环终止条件

达到设定最大迭代次数即终止循环。

5 算例分析及算法比较

5.1 设计算例

结合上述数学模型，设计算例，岸桥数量nqc=6，箱区数量nb=6，任务数量P=60。各岸桥的作业顺序、处理各任务的时间及完成各任务的最早时刻见表1。M25为QC1与QC2的卸船箱区，M26为QC3、QC4的卸船箱区，M27为QC5、QC6的卸船箱区。QC1与QC2为M24的装船岸桥，QC3与QC4为M28的装船岸桥，QC5与QC6为M29的装船岸桥。岸桥与箱区间距离、岸桥间距离与箱区间距离分别见表2～4。

表1 岸桥作业顺序表

表2 岸桥与箱区之间的距离

在Model I算法中：交叉过程能够以增加解的多样性的方式提高GA的全局搜索能力，交叉系数不可过小，过小的变异系数会导致GA的全局搜索能力大大下降；变异过程能提高GA的局部搜索能力，变异系数不宜过大，过大的变异系数容易使GA陷入局部最优解。故设置Model I中交叉系数Pc=0.7，变异系数Pm=0.1，经试算，Model I算法迭代次数为1 000得出的结果较好。在Model II算法中：由于Model II算法采用单亲遗传算法，只有变异过程能提高GA的搜索能力，使用过小的变异系数对GA的搜索能力的提高收益甚微，故设置Model II中变异系数Pm=0.3。理论上时间窗等分点越多，所求得的集装箱任务完成子时刻的值就越精确，但过多的等分点数量会影响GA的计算速度，故n取值为8。若ε取值过小，会影响模型计算速度，若ε取值过大，则会影响模型求解的精度，所以迭代计算条件中ε取15。经试算Model I算法在迭代次数小于100时就多次收敛，故设置Model I算法迭代次数为100。

表3 箱区之间的距离

表4 岸桥之间的距离

由表1～4可得出ti,j和si,j，再根据Model I中所述的计算ti,j的规则进而得出各任务间的ti,j。通过对上海港洋山四期自动化集装箱码头的实地调研获得以下数据：hqi的值93%以上落在0.630 1～1.411 7 min，且基本服从N(1,0.04)的正态分布；在不考虑场桥对AGV和岸桥的影响的前提下，场桥的作业时间hyi均匀分布在0.8～1.6之间；AGV的运动参数：全速6 m/s，转弯2 m/s，最小转弯半径9 m。

5.2 结果分析

5.2.1 模型有效性验证

基于上述数据，利用MATLAB2018a编写算法对上述模型进行迭代计算。

以12辆AGV作为Model I的初始输入条件，设定最大遗传代数为1 000代，得到总延误时间和初始任务调度方案，总延误时间迭代过程如图10所示，当AGV数量为12时，总延误时间在Model I算法迭代至522次的时候收敛，最小总延误时间为59.2 min。

图10 Model I第1代迭代过程

将Model I求出的任务时间窗输入Model II AGV配置模型中，设定最大遗传代数为100代。执行计算后得到AGV数量、任务作业子时刻以及更新后的任务时间窗，AGV数量迭代过程如图11所示，在Model II算法迭代至第24次时收敛至11台，且符合AGV数量约束。各个任务完成子时刻等分点的选取结果如图12所示，任务总数为60，任务完成子时刻等分点的数值越小，表示其实际任务完成时刻越接近ei。其中，任务完成子时刻等分点大于等于5的任务数量占比65%，所以初次运算所得任务时间窗仍有优化的空间；但选取任务子时刻等分点小于等于5的任务数量占比35%。以上结果表明Model II的优化效果明显，验证了Model II的有效性。

图11 Model II第1代迭代过程

以11台AGV作为Model I的初始输入条件，并分别将更新后的任务时间窗与原任务时间窗输入Model I，得到的结果见表5。

表5 11台AGV不同任务时间窗下计算结果对比

表5显示，当AGV数量为11台时，求解Model I得出的总延误时间要比AGV数量为12台时降低34.63%，且输入更新后的任务时间窗得到的总延误时间比输入原任务时间窗得到的总延误时间少7.8 min。这一结果证明了Model II的有效性。

5.2.2 数值计算结果

基于上述第1代耦合迭代，继续进行后续迭代，得到的结果见表6，并将结果与利用YALMIP调用CPLEX12.8计算得出的结果进行比较。

表6 AGV耦合调度计算结果

从表6可以看出，从第3代开始，由GA求得的AGV数量保持不变，总延误时间波动范围为不超过0.4 min；从第5代开始，由CPLEX求解的AGV数量和总延误时间保持不变。从收敛速度上看，GA的收敛速度明显优于CPLEX；从求解精度上看，GA与CPLEX求解结果精度一致。上述结果符合耦合迭代流程终止条件，求得了最优AGV数量为10台，最小总延误时间为12.2 min。

从计算结果上看，本文所提出的算法与CPLEX在求解耦合模型上比较具有以下优点：（1）收敛速度快，在第3代就已经收敛；（2）在计算大规模AGV调度问题上有潜在优势。

根据最优解对应的AGV调度方案，画出甘特图如图13所示。

图13 AGV最优调度方案甘特图

在图13中，AGV1对应的任务编号依次为：12，26，36，40，52，18，即AGV1依次执行第12号，26号，36号，40号，52号，18任务。

5.3 算法比较

本文扩大算例规模，设计9组实验，每组实验用GA与不同算法进行求解，并对求解结果进行对比。表7为不同算例规模下PSO、ACO和GA的求解结果，每组实验每个算法分别运算5次，结算结果均取平均值。

实验1、2、3显示：在计算AGV数量上，GAP2到达16.7%，ACO在求解AGV数量上性能较弱；在计算总延误时间上，GAP3与GAP4均小于5%，PSO、ACO与GA求得的总延误时间几乎相近。实验4，5，6显示：在计算AGV数量上，GAP1与GAP2最大均达到7.7%，表明GA求解AGV数量的精度均要高于PSO与ACO；在计算总延误时间上，GAP3最大达到14.74%，GAP4最大达到30.22%，表明GA求得的总延误时间最优。直到实验6为止，实验规模的增加对PSO与ACO求解精度都带来了不小的困难，而GA由于其强大的全局搜索能力，在求解精度上始终保持领先。实验7，8，9显示：GAP1与GAP2最大均达到20%，GAP3最大达到31.99%，GAP4最大为59.19%，不管是AGV数量还是总延误时间，GA均表现出了优于PSO与ACO的求解能力。以上9组实验进一步证明了GA在求解大规模算例上的优势。经研究表明，本文提出的模型，通过遗传算法的求解，可以很大程度降低AGV与岸桥之间相互等待时间，并能有效减少AGV的使用数量。

表7 不同算例规模下GA与各算法求解结果比较

6 结语

本文运用多学科变量耦合优化设计的方法，将AGV调度系统解构为AGV调度和配置两个子系统，分别建立AGV调度和AGV配置的数学模型，并建立AGV协调调度耦合模型来协调AGV调度模型和AGV配置模型。设计算例，采用GA进行求解，并给出了最优AGV数量与最优AGV调度方案。为了更适应码头实际生产情况，本文扩大算例规模，用GA与PSO和ACO算法进行对比，实验表明GA在求解大规模算例时性能优于PSO与ACO。由此可见，本文提出的模型与算法对于解决实际问题有一定的效用，并能大大减少船舶的在港时间，减少码头前沿AGV的拥堵。

本文尚未考虑场桥对AGV调度的影响，因此在今后的自动化码头AGV调度与配置耦合问题研究中，同时考虑岸桥、AGV和场桥这三者的影响来寻求最佳决策将更加具有现实意义。