自动化集装箱码头多层设备调度及仿真分析

王盼龙，梁承姬，王 钰

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

随着进出口贸易的不断发展，我国货物吞吐量持续攀升。2022年上半年，在疫情影响之下，全国港口仍完成货物吞吐量89.2亿t，同比增长0.1%；完成集装箱吞吐量1.7 亿TEU，同比增长4.2%[1]。码头作为货物进出口的主要枢纽，如何提升其运作效率成了各港口及国内外学者关注的焦点。自动化码头因其节能减排、作业安全、装卸效率高等特点，越来越受到各大港口青睐。2017年，先后有青岛全自动化集装箱码头和上海洋山全自动化集装箱码头投入运营。自动化集装箱码头引入了ARMG（自动化轨道吊，automated rail mounted gantry crane）、AGV（自动化导引小车，automated guided vehicle）、双小车岸桥。以洋山港四期为例，截止2022年6月共拥有23 台岸桥、114 台轨道吊、125 台AGV。2021 年洋山四期全年吞吐量达到了570万之高，在如此庞大的体量之下，保证岸桥门架小车、岸桥主小车、AGV、轨道吊之间的紧密协同配合就显得尤为重要。在传统的调度作业中，往往将装卸、水平运输、堆存三个环节单独考虑，造成实际操作中各个环节经常需要互相等待，增加了设备的闲置时间，降低了码头的作业效率。对岸桥门架小车、岸桥主小车、AGV、场桥四层设备进行集成调度，将每个环节的优化视为整体的一部分，能够有效提高整个装卸系统的作业效率，促进集装箱码头各种运输方式之间的无缝连接[2]。

国内外许多文献研究了码头设备的协同调度问题，其中包括两种设备的协同调度和三种设备的协同调度问题，这些研究中大多采用启发式算法、群智能算法或两者结合。对于两种设备的协同调度问题，马孙豫等[3]研究了双小车岸桥与AGV 的协同调度问题，建立以卸船任务结束时间最小化为目标的混合整数规划模型，采用多层编码粒子群算法进行了求解。刘彪等[4]建立了以AGV的总行驶时间和岸桥的总延迟时间最小为目标的多目标优化模型，提出改进遗传算法进行了求解。汤鹏飞等[5]建立了以岸桥作业延迟时间、ALV总行驶时间及岸桥等待ALV的时间之和最小为目标的ALV调度混合整数规划模型，采用遗传算法进行求解。梁承姬等[6]研究了AGV 与双小车岸桥的协同调度问题，考虑双小车岸桥中转平台及其容量限制，设计启发式算法进行了求解。Yue 等[7]对双四十尺双小车岸桥与AGV 的调度问题进行了研究，建立了两阶段双目标混合整数规划模型进行求解。Chen等[8]提出轨道吊和AGV两组流平衡的多商品网络流模型，引入了交替方向乘子法（ADMM）进行了相应计算。Zhang 等[9]研究了轨道吊和AGV 的协同调度问题，引入握手区概念，以最小化AGV等待时间和自动化轨道吊运行时间为目标建立模型进行求解。

对于三种设备的多层协同调度问题，Luan等[10]研究了岸桥、AGV、场桥三种设备的集成调度问题，考虑了容量约束并引入双循环策略。Yang 等[11]提出了装卸设备协调和AGV 路径选择的集成调度方法，建立了双层规划模型，结合了滚动时域和双层遗传算法对问题进行了求解。Yue等[12]提出了一个两阶段模型去最小化装卸船期间的能源消耗、最大化AGV的利用率。Ji等[13]建立了两阶段模型，第一阶段利用自适应遗传算法去计算岸桥、AGV、场桥的集成调度问题，第二阶段利用遗传算法解决AGV 的路径规划问题。He 等[14]研究了岸桥、内集卡、场桥联合调度的问题，用优化算法进行求解，用仿真设计进行评估。仲昭林等[15]结合AGV路径无冲突约束，建立了以最小化船舶在港时间和最小化总能耗为目标的多目标混合整数规划模型，设计了双层遗传算法进行求解，针对集装箱作业规模和决策目标进行仿真实验。Lau等[16]建立了最小化岸桥延误时间、AGV和场桥总运行时间的集成调度模型，算例结果显示最大匹配遗传算法的求解效果要优于多层遗传算法。黄永付等[17]针对码头卸船过程中岸桥、AGV 和场桥的集成调度问题，以最小化卸船完工时间为目标，确定各装卸设备作业序列并优化缓存位-任务的分配关系。秦琴等[18]针对双小车岸桥+AGV+缓冲支架+自动化轨道吊的装卸工艺，利用柔性流水车间调度理论建立集成调度优化模型，设计了NEH 启发式算法产生初始解的遗传算法进行求解。Luo 等[19]以最小化船舶靠泊时间为目标，对场桥、AGV、岸桥的联合调度问题建立了混合整数规划模型，利用自适应遗传算法进行了求解，并测试了自适应遗传算法的效率。

从以上研究中可以发现：

（1）对于自动化集装箱码头场桥、AGV、双小车岸桥三种设备多层联合调度的研究并不多，且已有的研究大多未对设备的调度规则做出详细分析，而码头设备调度过程中所遇到的情况繁多，调度规则的分析有助于说明调度算法的合理性。

（2）对于双小车岸桥中转平台的研究，基本集中在平台容量的约束，很少考虑箱子进出平台的次序，而对于能够容纳多个箱子的平台，箱子进出平台的次序又直接影响装卸效率。

（3）对于场桥、AGV、双小车岸桥联合调度的研究，由于问题的复杂性，大部分学者选择忽略AGV 的拥堵因素，而AGV 拥堵又是影响码头作业效率的关键因素之一。在自动化集装箱码头中，AGV 拥堵问题作为路径规划的重点问题，可能导致码头吞吐量最多下降达85%[20]。

（4）在以往的码头设备调度问题的研究中，很少采用优化算法与仿真结合的方式，由于码头多层设备调度过程中动态因素较多，而仿真软件便于将设备动态作业的过程展现出来，不仅能验证数学模型是否考虑全面，还能弥补数学模型难以分析动态因素的劣势。

为了解决上述问题，本文做出了如下创新：

（1）详细分析了集装箱经由场桥、AGV、双小车岸桥多层设备联合吊运时的各种规则，构建了基于时空节点表示方法的装船任务时空流动图，又通过plant-simulation仿真软件对码头生产过程进行了模拟，用理论分析加仿真实现的方式对调度规则进行了展现，同时获取了实验所需数据。

（2）在上述多层设备联合吊运规则的基础上，考虑了设备的互相等待时间、箱子进出中转平台次序、中转平台容量等约束，建立了以最大完工时间最小化为目标的由堆场到船上的多层设备全流程运作集成调度模型，通过自适应遗传算法求解出场桥、AGV、双小车岸桥的多层设备联合调度方案，并与禁忌搜索算法和模拟退火算法进行了对比，验证了模型及算法的有效性。

（3）提出算法与仿真结合的方式，将调度方案在仿真中进行了实施，利用仿真可直观展示动态过程的优势，即保证了算法所得解的可行性又进一步验证了模型和算法的有效性。

（4）根据求得的调度方案在仿真场景中提出随机路线、固定路线、分组随机路线三种AGV运作策略并进行完工时间、设备等待时间、AGV拥堵次数的对比，通过对不同AGV运作策略进行分析来将调度方式进一步优化。

1 问题描述

1.1 自动化集装箱码头多层设备协调

图1 展示了自动化集装箱码头多层设备布局。陆侧场桥负责堆场装卸箱，为第一层设备；AGV负责水平运输为第二层设备；岸桥门架小车负责将箱子从AGV上吊运至中转平台，为第三层设备；岸桥主小车负责将箱子从中转平台上吊运至船上，为第四层设备。

图1 多层设备协同布局Fig.1 Layout of multi-layer equipment collaboration

在装船过程中场桥接到任务指令后前往目标箱所在场箱位处，将集装箱提起并吊运至堆场前交接点。AGV 接到任务指令后前往堆场前交接点处，接收并转运集装箱至双小车岸桥下交接点。若场桥与AGV未能同时到达堆场前交接点，则先到者产生等待。双小车岸桥门架小车接到指令后前往岸桥下交接点，若门架小车与AGV 未能同时到达岸桥下交接点，则先到者产生等待。门架小车提起集装箱后将箱子吊运至岸桥中转平台，若中转平台有空闲位置，则将集装箱直接放置于空闲位置，若中转平台无空闲位置，则需等待岸桥主小车从平台上吊走一个任务箱。岸桥主小车接到任务指令后前往中转平台处吊运集装箱至船上，若中转平台为空，则主小车需等待集装箱到达中转平台。

1.2 基于多层设备运作规则的时空流动图

本文引入了一种时空节点的方式将码头场景进行了节点划分，由陆侧到海侧节点编号依次增大。图2是装船过程中第一个任务箱的轨迹，图中共有5 种弧，分别为移动弧、等待弧、提箱弧、放箱弧、恢复弧，其中红色弧表示场桥轨迹，黑色弧表示岸桥大车轨迹，绿色弧表示岸桥门架小车轨迹，浅蓝色弧表示岸桥主小车轨迹，深蓝色弧表示AGV轨迹。当两种设备的轨迹弧产生交叉时，表示箱子到达交接点。每一段弧都有对应的坐标，例如移动弧（10，6，0，6）表示该设备从节点10 移动到节点6，起始移动时刻为0，到达节点6的时刻为6。图中场桥先通过移动弧（6，3，0，3）由节点6移动到箱子堆存的位置节点3，然后在节点3进行提箱作业，分别经历了提箱弧（3，4，3，4）和恢复弧（4，3，4，5），整个提箱作业从时刻3开始到时刻5结束。场桥提完箱后在时刻5从节点3 出发，在时刻8 到达节点6，形成移动弧（3，6，5，8）。在时刻8，AGV经历了移动弧（10，6，0，6）和等待弧（6，6，6，8）后到达节点6，在节点6 场桥和AGV 进行箱子的交接，场桥经过了放箱弧（6，5，8，9）和恢复弧（5，6，9，10）后，将箱子交接给了AGV。AGV从节点6出发移动至节点11，形成移动弧（6，11，10，16）。在时刻16，岸桥经过了等待弧（11，11，0，16），在节点11 处与AGV 进行交接。岸桥门架小车进行提箱动作，形成提箱弧（11，12，16，17）和恢复弧（12，11，17，18）。岸桥门架小车接到箱子后，从节点11移动至节点13到达中转平台上方，形成了移动弧（11，13，18，19），然后进行放箱动作。箱子放到中转平台后，岸桥主小车从中转平台上提起箱子，经过提箱弧（13，14，21，22）和恢复弧（14，13，22，23）。主小车提起箱子后移动至船上箱子要堆存的贝位，经过移动弧（13，15，23，24），最后主小车进行放箱动作，将箱子放到船上，产生放箱弧（15，14，24，25）和恢复弧（14，15，25，26），至此该装船箱任务结束。

图2 多层设备协同作业时空流动图Fig.2 Time and space flow of multi-layer equipment collaboration

1.3 装船任务完工时间计算

装船任务完工时间即为最后一个任务箱装上船的时间，本文以最小化完工时间为目标，建立了多层设备协同调度模型，利用自适应遗传算法对该模型进行了求解，在理想时间内得到了较优的多层设备协同调度方案并将该方案在仿真中进行了实施。

场桥作为第一层设备，其吊运一个任务箱的时间计算逻辑见图3。在场桥到堆场中进行提箱时，需要判断场桥在做该任务箱之前是否还做了其他任务。若做了其他任务，则场桥开始抓该任务箱的时间即为场桥做完上一个任务箱后来到本次任务箱位置的时间，该任务箱到达场桥与AGV交接点的时间点为场桥抓完上一个箱后来到本次任务箱位置的时间点加上场桥将箱子从堆场提起至将箱子放到AGV上的时间。若场桥做该任务箱之前没做其他任务，则该任务箱为这台场桥作业的第一个任务，场桥开始抓本次任务箱的时间记为0，该任务箱到达场桥与AGV交接点的时间为场桥将箱子从堆场提起至将箱子放到AGV上的时刻。

图3 第一层设备作业时间计算逻辑Fig.3 Logic for calculating working time of first layer of equipment

AGV 作为第二层设备，其载运一个任务箱的时间计算逻辑见图4。当箱子到达堆场前的交接点时，需要判断分配给该箱子的AGV在作业该任务箱之前是否还作业了其他箱子。若之前作业了其他箱子，则箱子交接给AGV 的时间为AGV 作业完上一个箱子后回到堆场交接点处的时间与场桥带着箱子到达交接点处的时间之间取较大值，箱子到达岸桥下交接点的时间为该较大值加上AGV将箱子运输至岸桥下交接点的时间。若该任务箱是AGV作业的第一个箱子，则AGV接到箱子的时间为场桥到达交接点的时间与AGV从起始位置出发后到达场桥交接点的时间之间的较大值，箱子到达岸桥下交接点的时间为该较大值加上AGV将箱子运输至岸桥下交接点的时间。

图4 第二层设备作业时间计算逻辑Fig.4 Logic for calculating working time of second layer of equipment

岸桥门架小车作为第三层设备，其吊运一个任务箱的时间计算逻辑见图5。当箱子到达岸桥下交接点时，需判断岸桥门架小车在作业该任务前是否还作业了其他任务。若之前作业了其他任务，则比较门架小车作业完上一个任务箱后回到交接点处的时间与AGV带着箱子到达岸桥下交接点处的时间，取两者的较大值记为M。然后判断岸桥在做该任务箱之前所做的任务数量是否小于2，若小于2则中转平台上一定有位置，门架小车从AGV上提起集装箱的时间即为M，箱子放到中转平台上的时间即为M加上门架小车处理箱子的时间。若岸桥之前所做的任务数量大于等于2，则将该任务箱记为岸桥作业的第i个箱，在岸桥作业的第i-2 个箱被岸桥主小车提起的时刻与M之间取较大值，记为N，则N为门架小车将箱子从AGV 上提起的时间。箱子放到中转平台上的时间为N加上门架小车处理箱子的时间。若门架小车之前没有作业过其他任务，则中转平台上一定有位置，门架小车提箱时间即为AGV 带着箱子到达岸桥下交接点处的时间，箱子被放到中转平台上的时间即为AGV到达交接点的时间加上门架小车处理箱子的时间。

图5 第三层设备作业时间计算逻辑Fig.5 Logic for calculating working time of third layer of equipment

岸桥主小车为第四层设备，其作业时间判断逻辑见图6。箱子到达中转平台时，需判断该任务箱是否为主小车作业的第一个任务，若是第一个任务，则箱子放上船的时间为：箱子到达中转平台的时间加上主小车处理该任务箱的时间；若不是第一个任务，则在主小车做完上一个任务后回到中转平台的时间点与箱子到达中转平台的时间点之间取较大值，记为P，箱子放上船的时间为P加上主小车处理该箱子的时间。

图6 第四层设备作业时间计算逻辑Fig.6 Logic for calculating working time of fourth layer of equipment

1.4 AGV运作策略

为了证明算法的合理性及优化调度方式，提出了AGV的随机路线、固定路线、分组随机路线三种运作策略。

随机路线策略中AGV 为作业面调度，被所有设备共享，即AGV 可服务于任意场区和岸桥，根据AGV 的目的地选择较近的行驶路线，见图7。

图7 随机路线策略路线布局Fig.7 Random route strategy route layout

固定路线行驶策略中AGV固定的服务于某一场区和岸桥，AGV 只能在固定的路线上行驶，见图8。图中不同颜色的箭头分别代表不同组的AGV 路线，黄色箭头为服务于岸桥QC1和场区B1的AGV路线，红色箭头为服务于岸桥QC2和场区B2的AGV路线，绿色箭头为服务于岸桥QC3和场区B3的AGV路线，粉色箭头为服务于岸桥QC4 和场区B4 的AGV 路线，AGV 只能在一条路线行驶，不能跨越到其他路线。

图8 固定路线策略布局图Fig.8 Fixed route strategy route layout

分组随机策略中将场区和岸桥划分为两组，红色分隔线左右两侧分别为一组，在每一个分组内仍采用随机策略运行，见图9。

图9 分组随机路线策略布局图Fig.9 Grouping random strategy route layout

1.5 仿真场景

基于上文自动化集装箱码头多层设备协同作业规则，在plant-simulation仿真软件中搭建装船运作场景如图10，该场景包含一条150 m长的船、四台场桥、四台双小车岸桥，分别对不同规模的任务进行仿真，并获取相关数据，仿真场景见图10。

图10 仿真场景Fig.10 Simulation scene

仿真实验旨在证明算法的有效性及提高算法的适用性。本文在仿真场景中对算法所求多层设备协同调度方案进行了实施，对所提出的随机路线、固定路线、分组随机路线三种AGV 运作策略进行了详细分析，弥补了模型及算法难以分析动态因素的劣势。

综上，自动化集装箱码头多层设备集成调度运作规则极其繁杂，如果设备调度方案不合理，就极易造成等待时间增加和阻塞严重，从而使得最终完工时间增加。为解决这一问题，本文以最小化最大完工时间为目标，考虑了各设备之间的互相等待时间、中转平台的容量约束、任务箱进出中转平台的次序等，利用plant-simulation仿真软件对码头多层设备联合调度的运作过程进行了模拟，建立了多层设备集成调度的模型，通过自适应遗传算法对模型进行了求解，并与禁忌搜索算法和模拟退火算法进行了对比。将算法求得的调度方案在仿真中进行了实施，验证了算法的有效性。最后基于求得的调度方案在仿真场景中对AGV随机路线、固定路线、分组随机路线三种运作策略下的完工时间、设备互相等待时间、拥堵次数等进行详细分析，进一步证明算法有效性的同时找出了能最大化算法效用的运作方式。

2 数学模型构建

本文研究了场桥、AGV、岸桥门架小车、岸桥主小车的多层设备联合调度问题，以最小化最大完工时间为目标，建立了多层设备集成调度模型，对设备调度方案进行了优化，已知条件如下：

（1）任务箱的堆存位置已知；

（2）场桥将任务箱由堆存位置送到固定交接点所需的时间已知；

（3）任务箱、场桥、岸桥、AGV的数量已知；

（4）模型中AGV被所有的岸桥和场桥共享；

（5）AGV在任意两个节点间的运行时间已知；

（6）场桥、岸桥门架小车、岸桥主小车处理每个集装箱所需时间已知。

2.1 模型假设

（1）场桥、岸桥主小车、岸桥门架小车、AGV分别一次只能处理一个集装箱；

（2）不考虑翻箱问题；

（3）AGV拥堵在模型中不考虑，在仿真实施时考虑；

（4）任务箱均为40英尺；

（5）双小车岸桥中转平台可容纳两个40英尺集装箱。

2.2 模型参数及决策变量

2.2.1 模型参数

K：场桥集合，编号为{1…k}，k∈K；

V：AGV集合，编号为{1…v}，v∈V；

Q′：岸桥门架小车集合，编号为{1…q′}，q′∈Q′；

Q"：岸桥主小车集合，编号为{1…q"}，q"∈Q"；

L：所有任务的集合，编号为{1…i}，i∈L；

O：虚拟起始任务；

θ：虚拟终止任务；

M：足够大的正数；

U：中转平台上缓存位置的集合，编号为{1…u}，u∈U；

2.2.2 决策变量

pui为0-1变量，任务i被分配给中转平台上的缓存位u则为1，否则为0。

2.3 目标函数及约束条件

式（1）为最小化最大完工时间目标函数，完工时间为最后一个任务箱被岸桥主小车装上船的时间。

关于场桥的约束：

式（2）表示一个任务箱只能被处理一次；式（3）表示一台场桥一次只能处理一个集装箱；式（4）为保证集装箱按次序被场桥处理；式（5）为场桥处理任务箱的时间约束，表示当场桥k依次处理任务箱i和任务箱j时，处理任务箱j的开始时间应等于场桥处理完任务箱i后来到任务箱j所在位置的时间。式（6）表示场桥k处理完任务箱i的时间应等于开始处理任务箱i的时间加上处理的时间。

关于AGV的约束：

式（7）表示一个任务箱只能被处理一次；式（8）表示AGV一次只能运送一个任务箱；式（9）为保证集装箱按次序被AGV运送；式（10）表示若AGV依次运送任务箱i和j，则AGV运送任务箱j的开始时间应等于或晚于AGV 运送任务箱i的结束时间加上结束任务箱i后来到任务箱j所在位置的空载时间。式（10）、（11）联合表示当AGV 依次处理任务箱i和j时，AGV 开始处理任务箱j的时间为在场桥处理任务箱j的结束时间与AGV 处理完任务箱i后回到场桥交接点的时间之间取较大值。式（12）表示AGV运送任务箱i的结束时间应等于运送任务箱i的开始时间加上运输时间。

关于岸桥门架小车的约束：

式（13）表示一个任务箱只能被岸桥门架小车处理一次；式（14）表示岸桥门架小车一次只能处理一个任务箱；式（15）表示岸桥门架小车必须按次序处理任务箱；式（16）表示任务箱只有一个紧前任务和一个紧后任务；式（17）表示若岸桥门架小车依次处理任务箱i和j，则门架小车开始处理任务箱j的时间应等于或晚于门架小车处理完任务箱i后回到岸桥下交接点的时间；式（17）、（18）表示当岸桥门架小车依次处理任务箱i和j时，岸桥门架小车开始处理任务箱j的时间为在AGV处理任务箱j的结束时间与岸桥门架小车处理完任务箱i后回到岸桥下交接点的时间之间取较大值。式（19）表示岸桥门架小车处理任务箱i的结束时间等于处理任务箱i的开始时间加上处理时间。

关于岸桥主小车的约束：

式（20）表示一个任务箱只能被处理一次；式（21）表示岸桥主小车一次只能处理一个任务箱；式（22）为保证岸桥主小车按次序处理任务箱；式（23）表示任务箱只有一个紧前任务和一个紧后任务；式（24）表示若岸桥主小车依次处理集装箱i和j，则开始处理任务箱j的时间应等于或晚于执行完任务i后岸桥主小车回到中转平台的时间；式（24）、（25）联合表示当岸桥主小车依次处理任务箱i和j时，岸桥主小车开始处理任务箱j的时间为在岸桥门架小车处理任务箱j的结束时间与岸桥主小车处理完任务箱i后回到中转平台的时间之间取较大值。式（26）表示岸桥主小车处理任务箱i的结束时间等于处理任务箱i的开始时间加上处理时间。

关于岸桥中转平台的约束：

式（27）表示每个任务箱只分配给一个中转平台上的缓存位；式（28）表示一个缓存位只能放一个任务箱；式（29）表示岸桥门架小车从AGV上提起岸桥作业的第x个任务箱i的时间应晚于岸桥主小车将岸桥作业的第x-2 个任务箱从中转平台上提起的时间。

3 模型求解

由于全设备调度问题变量规模巨大，难以用精确算法进行求解，而遗传算法、禁忌搜索算法、模拟退火算法等具有全局搜索能力的启发式算法在诸如此类调度问题中已有所应用，并取得了一定效果。尽管有很多新的启发式算法被用在码头的设备调度问题中，但因为自适应遗传算法中的染色体能够很方便地将问题的决策变量表示出来，且能够在较短时间内求得结果，所以自适应遗传算法依然很适用于去研究[19]。本文基于装船过程中的设备调度规则，引入了自适应遗传算法，如图11。

图11 算法流程图Fig.11 Algorithm flow chart

算法步骤如下：

步骤1随机生成初始种群P。

步骤2对种群P进行个体评价，计算适应度。

步骤3采用了随机通用采样和精英保留策略结合的方法对种群P进行了选择操作。

步骤4交叉后产生种群P1，计算种群P1 的适应度标准差。

步骤5对种群P1 进行变异操作产生种群P2，计算种群P2 的适应度标准差。

步骤6比较种群P1 和种群P2 的适应度标准差，若P2 适应度标准差小于P1，说明P2 的种群多样性较差，则将变异率pm增加0.01；否则，保持变异率不变。

步骤7将经过选择、交叉、变异操作后得到的候选种群与父代精英保留策略下保留下来的优秀个体进行了重插入操作，得到了子代种群。

步骤8判断是否达到迭代终止条件，若未达到，则将子代种群作为下一代的父代种群，重复步骤2～7；若达到，则结束。

3.1 自适应遗传算法

（1）染色体编码

采用实数编码方式，任务箱的数量即为染色体的长度。如图12 所示，为三台AGV、三台场桥、两台岸桥协同处理九个集装箱。以染色体第一列为例（4，3，2，2）表示集装箱4分别被3号AGV、2号场桥、2号岸桥处理，染色体其他列以此类推。从单个设备来看，各设备处理任务的次序都为从左至右，1 号AGV 先后处理（2，3，1，5）四个集装箱，2 号AGV 先后处理（9，6，7）三个集装箱，3号AGV 先后处理（4，8）两个集装箱；1 号场桥先后处理（2，3，1）三个集装箱，2号场桥先后处理（4，6，5）三个集装箱，3 号场桥先后处理（9，7，8）三个集装箱；1 号岸桥先后处理（2，9，6，7，8）五个集装箱，2 号岸桥先后处理（4，3，1，5）四个集装箱；以此方法来确定各设备作业的任务及作业次序。

图12 染色体示例Fig.12 Chromosome example

（2）种群初始化

本文在考虑约束条件的前提下，采用随机生成法产生初始种群。

（3）目标函数计算

模型以最小化最大完工时间为目标，对由堆场到船上这一作业过程中场桥、AGV、岸桥门架小车、岸桥主小车四层设备协调作业的调度方案进行了计算，四层设备之间的详细协调规则见1.1～1.2 节，算法的设计即是基于该协调规则。

算法中目标函数即完工时间的计算逻辑见1.3 节，将该计算逻辑转化为数学模型后，算法对模型中约束的具体处理示例如下：

以图12 中染色体为例，从左至右依次计算各集装箱的完工时间，再取出所有集装箱的完工时间的最大值，即为所有任务的总完工时间。以图12 染色体中第一个箱号为4的集装箱的完工时间的计算为例，其依次被2 号场桥、3 号AGV、2 号岸桥作业，详细计算方法如下文，其中各约束公式对应的详细解释见2.3节，其余集装箱完工时间的计算方法与此相同。

对于第一层设备场桥，先根据式（2）～（6）对2 号场桥处理4号集装箱的完工时间进行计算。首先判断4号集装箱是否为2号场桥的首个任务，若为首个任务，则2号场桥开始处理4 号集装箱的时间记为0，因此可根据式（6）直接得出2号场桥处理4号集装箱的完工时间；若4号集装箱不是2号场桥的首个任务，则需根据式（5）得出2号场桥开始处理4号集装箱的时间，再根据式（6）得出2号场桥处理4号集装箱的完工时间。

对于第二层设备AGV，根据式（7）～（12）对3 号AGV 处理4 号集装箱的完工时间进行计算。首先判断4 号集装箱是否为3 号AGV 的首个任务，若为首个任务，则3号AGV开始处理4号集装箱的时间为2号场桥处理4 号集装箱的完工时间；若4 号集装箱不是3 号AGV的首个任务，则需联合式（10）、（11）得出3号AGV开始处理4 号集装箱的时间，再根据式（12）得出3 号AGV处理4号集装箱的完工时间。

对于第三层设备岸桥门架小车，根据式（13）～（19）对2号岸桥门架小车处理4号集装箱的完工时间进行计算。首先判断4号集装箱是否为2号岸桥门架小车作业的前两个任务。如果4号集装箱是2号岸桥门架小车作业的前两个任务，则由式（27）、（28）及中转平台可容纳两个40 英尺集装箱可知中转平台上一定有空位，此时若4 号集装箱为2 号岸桥门架小车的首个任务，则2 号岸桥门架小车开始处理4 号集装箱的时间为3 号AGV处理4号集装箱的完工时间。若4号集装箱是2号岸桥门架小车的第二个任务，则先联合式（17）、（18）得出2号岸桥门架小车开始处理4 号集装箱的时间，即在3 号AGV 处理4 号集装箱的结束时间与2 号岸桥门架小车处理完上一个任务箱后回到岸桥下交接点的时间之间取较大值，再根据式（19）得出2 号门架小车处理4 号集装箱的完工时间。如果4号集装箱不是2号岸桥门架小车的前两个任务，则岸桥中转平台上可能没有位置，需要联合式（17）、（18）和式（29）来计算2号岸桥门架小车开始处理4 号集装箱的时间，其中式（29）用于保证2 号岸桥门架小车开始处理4号集装箱的时间应晚于2号岸桥主小车将4 号集装箱之前的第二个箱子从中转平台上提起的时间，即当2 号岸桥主小车将4 号集装箱之前的第二个箱子从中转平台上提起后，中转平台上才有空位置；计算出2 号门架小车处理4 号集装箱的开始时间后，再根据式（19）得出该操作的完工时间。

对于第四层设备岸桥主小车，根据式（20）～（26）对2 号岸桥主小车处理4 号集装箱的完工时间进行计算。首先判断4 号集装箱是否为2 号岸桥主小车的首个任务，若为首个任务，则2号岸桥主小车开始处理4号集装箱的时间为2号岸桥门架小车处理4号集装箱的完工时间；若4号集装箱不是2号岸桥主小车的首个任务，则需联合式（24）、（25）得出2 号岸桥主小车开始处理4 号集装箱的时间，再根据式（26）得出2 号岸桥主小车处理4号集装箱的完工时间，即该任务箱装上船的时间。

（4）适应度计算

适应度函数采用目标函数的倒数，适应度值较大的个体其完工时间较小。

其中，T为一个调度方案的完工时间。

（5）选择算子的设计

采用随机通用采样（stochastic universal sampling）与精英保留策略结合的选择方法。精英保留策略用于避免优良个体的丢失。

（6）交叉算子设计

对于表示集装箱的部分，采用部分匹配法交叉（partially matching crossover），对于AGV 和岸桥部分采用均匀交叉，如图13、图14所示。

图13 部分匹配交叉Fig.13 Partially matching crossover

图14 均匀交叉Fig.14 Uniform crossover

（7）变异算子设计

本文对变异前后父代和子代种群适应度的标准差进行比较，若子代小于父代，则将变异率增加0.01；若子代大于或等于父代，则保持变异率不变。

3.2 结果分析

为了验证模型及算法的有效性，本节运用了模型算法与仿真运行结合的方法。先运行仿真模型，获取场桥作业各任务箱的起步空载时间、重载时间、两个任务之间的空载时间;获取AGV 在各岸桥交接点和场桥交接点之间运行所需行驶时间；获取岸桥门架小车和主小车的单箱作业时间。再将获取的基础数据分别代入自适应遗传算法（AGA）、禁忌搜索算法（TS）、模拟退火算法（SA）中，进行了16组不同任务规模的对比实验，对每组实验求解10次，以平均值作为最终结果，各算法所得调度方案均放回仿真模型中进行运行，以确保解的可行性及观察模型是否考虑问题全面。运行结果见表1及图15。实验运用plant-simulation15.0.0 及MATLAB 2018a，运行环境为Window10操作系统，Intel®CoreTMi7-7700HQ CPU@2.80 GHz，8 GB内存。

表1 AGA-TS-SA算法数据对比Table 1 Data comparison of AGA-TS-SA algorithm

图15 AGA、TS和SA完工时间对比Fig.15 Comparison of completion time of AGA，TS and SA

从实验结果可以看出：

（1）在16 组实验中有13 组为自适应遗传算法求得的解优于禁忌搜索和模拟退火。

（2）在16 组实验中有11 组为自适应遗传算法计算时间小于模拟退火算法；有16 组为自适应遗传算法计算时间小于禁忌搜索算法。

（3）以表1中实验4及实验14为例，实验4中集装箱数量为20，AGV数量为6，完工时间为16.6 min；实验14中集装箱数量为40，AGV数量为6，完工时间为35 min，基本符合现阶段自动化码头作业调度时间。

（4）随着集装箱数量增多，完工时间也随之增加；同等任务数时，一定程度上增加AGV 数量可以提高装卸效率。

为了进一步比较三种算法的性能，分别在不同规模任务下对三种算法的收敛性进行对比，结果见图16、图17。其中图16 和图17 分别为集装箱数为20 和40 时的收敛情况。从图中可以看出，自适应遗传算法的收敛时间随着任务规模的增大而增大，且收敛结果优于另外两种算法，这是由于自适应遗传算法采用自适应变异策略使得算法能够跳出局部最优解，而其他两种算法均过早收敛且陷入局部最优解。

图16 20个任务箱算法收敛情况对比Fig.16 Comparison of algorithm convergence of 20 task containers

图17 40个任务箱算法收敛情况对比Fig.17 Comparison of algorithm convergence of 40 task containers

4 AGV运行策略仿真分析

由于自动化集装箱码头多层设备协同调度问题较为复杂，数学模型难以将因素考虑全面，因此本文在前述研究的基础上利用plant-simulation 仿真软件对提出的随机路线、固定路线、分组随机路线三种AGV运行策略进行了对比分析，进一步验证文中所提算法的合理性及改善调度方式，找出能使算法发挥出最大效用的AGV运作策略。

4.1 随机路线策略仿真

随机路线策略中综合考虑了全局情况，对AGV 进行作业面调度，能够提高AGV 的利用率。本文模型及算法部分即采用了随机路线策略，将随机路线策略在仿真中实施后所得数据见表2及图18。

表2 随机路线仿真数据Table 2 Random route simulation data

图18 随机路线策略下完工时间Fig.18 Completion time under random route strategy

由表2 和图18 可以看出，在不同规模实验中，随着AGV 数量的递增，完工时间、场桥等待时间、门架小车等待时间、主小车等待时间均在AGV 数量为8 时达到最小值，而AGV 在场桥交接点处的停留时间却逐步递增；因此AGV配额为8时装船效率最高，当AGV数量过大时会造成资源浪费。

4.2 固定路线策略仿真

为了进一步证明算法的合理性，利用仿真可以动态分析复杂问题的优势，在仿真场景中引入按固定路线行驶的AGV 运行策略，与算法中的随机路线策略进行对比。固定路线行驶策略为AGV固定的服务于某一场区和岸桥，当场区和岸桥数量较多时，需至少拥有与场区或岸桥同等数量的AGV 才能作业，对固定路线进行分析后所得数据见表3及图19。

表3 固定路线仿真数据Table 3 Fixed route simulation data

图19 固定路线策略下完工时间Fig.19 Completion time under fixed route strategy

由表3 及图19 可以看出，在固定路线行驶策略下，当AGV 数量为8 时，完工时间、场桥总等待时间、门架小车总等待时间、主小车总等待时间均达到最小值且不再随着AGV 数量的递增而改变，该结果进一步说明了该实验场景下8 台AGV 为最优配额，此时的完工时间为相应规模任务的最优完工时间；此外，当AGV数量达到8以后，场桥的等待时间为0，岸桥的等待时间也不再变化，说明在当前的设备效率及数量配置下已达到最优效果，此时能够影响完工时间的不再是AGV的数量，而是设备作业能力及场地大小等其他因素。在AGV数量为8 时，对AGV 速度进行灵敏度分析，结果见图20，随着AGV 速度的提升，最优完工时间平滑下降固定路线策略虽能取得很好的效果，但该策略需要为每一台岸桥和每一个场区提供专用的AGV，当场区和岸桥数量较多时，AGV数量也需增加，而对于任务箱所在箱区较分散的情况就需要足够多的AGV 才能作业；如果任务箱数量少且分布不集中，则可能会造成AGV资源利用不充分，而随机路线策略采用AGV 共享模式，可避免该问题。将随机路线与固定路线完工时间进行对比，S表示随机路线，G表示固定路线，结果见表4。

表4 随机路线与固定路线数据对比Table 4 Comparison of random route and fixed route data

图20 AGV速度灵敏度分析Fig.20 Sensitivity analysis of AGV speed

由表4可看出，随机路线与固定路线在任务规模相同时，完工时间接近。表4中差额=（S完工时间-G完工时间）/S完工时间，20 个任务箱8 台AGV 时，完工时间相同；40个任务箱8台AGV时，完工时间差额为6.89%；因此按随机路线进行计算的算法具有一定效果。

4.3 分组随机路线策略仿真

随机路线策略虽能对全局综合考虑，但由于设备众多会造成算法时间复杂度较高，算法求解耗时较长。为了能够提高算法的适用性，提出了分组随机路线的策略。

将随机路线和分组随机路线进行对比，结果见表5及图21、22；其中完工差额=（随机路线完工时间-分组随机完工时间）/随机路线完工时间，运行时间差额=（随机路线运行时间-分组随机路线运行时间）/随机路线运行时间。

表5 随机路线与分组随机路线数据对比Table 5 Comparison of random route data and grouped random route data

图21 20箱分组随机路线与随机路线运算时间对比Fig.21 Comparison of calculation time between grouped random route and random route of 20 task containers

图22 40箱分组随机路线与随机路线运算时间对比Fig.22 Comparison of calculation time between grouped random route and random route of 40 task containers

由表5 可看出，两种策略下完工时间最小差额为0.63%，最大差额为7.69%，差额较小。由图21、22 可看出，同等任务规模下分组随机能够大大缩短算法计算时间，各规模算例下最低缩短运行时间33.21%，最高缩短运行时间59.24%。由于分组随机中AGV的行驶范围较小，且两组AGV 互不干扰，因此AGV 之间的堵塞次数也有所减少，在8 组对比实验中有5 组分组随机策略阻塞次数小于随机策略阻塞次数，有2 组阻塞次数相同，见图23、24。

图23 20箱分组随机路线与随机路线阻塞次数对比Fig.23 Comparison of blocking times between grouped random routes and random routes of 20 task containers

图24 40箱分组随机路线与随机路线阻塞次数对比Fig.24 Comparison of blocking times between grouped random routes and random routes of 40 task containers

综上，分组随机策略在取得与随机策略相近的完工时间的同时，还能大大减少算法运行时间并减少阻塞次数，提高了算法的适用性。

5 结论

本文重点研究了集装箱由堆场到船上这一过程中多层设备的集成调度问题，所做工作及成果如下：

（1）详细分析了自动化集装箱码头中多层设备联合吊运集装箱时的各种规则。采用由整体到局部的思想，先在规则的基础上以时空节点的方式构建了装船任务时空流动图，从集装箱的视角出发，分析了集装箱在整个装船过程中被多层设备吊运的情况。又将多层设备进行拆分，从各层设备的视角出发，对每层设备在运行期间的完工时间计算逻辑进行了分析，将规则与所提出的模型联系了起来。通过以上工作弥补了过往研究中对设备调度规则分析不够深入的不足，即为本文中的模型及仿真提供了支撑，又为码头设备调度类问题的研究提供了一些参考。

（2）采用了数学模型与仿真相结合的思想。在设备调度规则的基础上，建立了多层设备集成调度模型和仿真场景。数学模型用于调度方案的求取，仿真场景用于调度规则及调度方案的实施和分析，用仿真方法弥补了数学模型难以全面考虑复杂动态问题的劣势。

（3）分别利用自适应遗传算法、模拟退火算法和禁忌搜索算法进行了求解，并将各算法求得的调度方案放入仿真模型中进行验证对比。结果表明所提出的自适应遗传算法在执行时间和求解结果方面均优于其他两种算法，证明了所提出的自适应遗传算法在码头多层设备调度问题中的有效性。

（4）为了能够进一步验证算法的有效性及最大化算法的使用效果，提出了随机路线、固定路线、分组随机路线三种AGV 运行策略。在仿真场景中，对三种策略下的各设备等待时间、AGV 最优配额、完工时间、AGV 阻塞次数、算法运行时间进行了对比和分析，结果表明在文中实验场景下AGV 配额为8 台时，完工时间和各设备等待时间均最短，当AGV配额大于8台时，会造成资源的浪费。同时也证明了所提出的自适应遗传算法与分组随机路线策略结合既能保证完工时间较优又能减少AGV 阻塞次数，还将算法运行时间缩短了33.21%至59.24%。

本文的不足之处在于：所提出算法的性能仍有很大的提升空间；只研究了装船过程中的多层设备集成调度问题。未来将尝试采用混合算法或寻找求解速度快且精度高的其他算法去求解装卸同步进行的多层设备集成调度问题。