自动化码头堆场穿越式双ASC调度

周亚民，杨勇生，仲美稣，王宇生，许学谦

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

自动化集装箱码头是将原本的集装箱码头的场桥、岸桥、起重机等设备换成与之相对应的自动化的设备，从而更加高效地完成岸边和堆场之间的运输作业、堆场内的作业以及进出道口的作业[1-2]。

现有的集装箱装卸设备（吊两箱、三箱岸桥）和装卸条件（挖入式港池、浮动装卸作业平台）极大地提高了岸边的装卸效率问题，无人集卡、AGV（Automated Guided Vehicle）和ALV（Automated Lifted Vehicle）也能够实现边装边卸的要求[3-4]。堆场内AGV 排队等待、设备利用率低等问题，迫使大部分研究人员将研究方向转移到陆侧的堆场装卸方面[5]。

目前，自动化集装箱码头的陆侧堆场区域布局多采用垂直式的布局和多场桥运作[6-7]。场桥一般采用自动堆垛起重机（Automated Stacking Crane，ASC），用于连接堆场和堆场两侧（海侧和陆侧）。场桥运作中，根据ASC 的数量可以分为单ASC、双ASC 和多ASC。而双ASC最常见的在堆场的场桥布局[8]，其中关于双ASC可以根据两个ASC之间是否可以相互穿越分为不可穿越式双ASC 和可穿越式双ASC（具体见图1、2）[9-10]。前者是两台大小一样的ASC 在同一轨道上运行，两台ASC在箱区的两侧与AGV和集卡进行交接工作。后者是两台大小不一的ASC 分别在两台轨道上运行，并且两台ASC 均可以在箱区的两端与AGV 和集卡进行交接工作。不可穿越式双ASC的堆垛层高比可穿越式双ASC的堆垛层高更高，ASC 的占地面积更小；但是可穿越式双ASC 可以两端作业，减少了因为不可穿越式等原因造成的等待时间，提高了自动化码头的堆场工作效率。

图1 不可穿越式双ASC堆场布局

图2 可穿越式双ASC堆场布局

关于堆场作业已经有一定的研究基础，例如Carlo等人[11]研究包括所使用的物料搬运设备的堆场作业，提出了仓库作业分类方案，其对研究自动化集装箱码头具有重要借鉴。为了有效地装卸集装箱，Cao 等人[12]研究了亚洲布局中堆场堆存问题，设计了贪婪启发式算法，模拟退火（SA）算法和组合式堆场调度启发式算法来解决该问题。Stahlbock 等人[13]为了提高集装箱码头的工作效率，研究了欧洲布局中堆场堆存问题，并设计了三个程序和一个基于SA 的启发式算法，并根据德国汉堡港的集装箱码头进行仿真，结果SA 在高工作负载情况下优于基于规则的其他算法。Vis等人[14]针对场桥的最小化完工时间，提出了一种基于模拟退火算法的启发式算法，通过分支界定法求解场桥的调度模型，并且提出双场桥的避让方法。

随着近年来，自动化码头更多使用双场桥进行作业来提高作业效率，Ng[15]针对不同准备时间的双场桥调度问题，建立了整数规划模型，提出了一种基于动态规划的启发式算法，能够有效解决双场桥的调度问题。随后，Ng等人[16]又提出了以最小化总作业时间为目标，优化堆场内双向行车道的场桥调度问题，并利用启发式算法来求解并证明算法有效性。但是，其模型只考虑了单一箱区中一种类型的任务，并且没有考虑场桥的移动时间。对于欧洲布局中使用单个箱区中双场桥问题，Zhou等人[17]提出了一种根据给定的日期对作业序列和交换点进行排序的方法，并且运用最优化算法最大限度地减少最大迟到、迟到作业的数量和完工时间。魏晨和胡志华[18]以最小化作业总完成时间为目标，建立了双场桥混合整数规划模型，提出了启发式遗传算法，表明大规模算例中遗传算法优于CPLEX算法。

然而在自动化码头中，尤其是双场桥作业时存在诸多不确定性和限制性因素，比如Li等人[19]以任务的提前和延误时间最小化为目标，考虑了场桥之间的干扰和安全作业距离，建立了离散时间整数规划模型，提出滚动周期算法在短时间内产生近似最优的解决方案。Li 等人[20]在考虑码头实际操作环境中的设备数量限制问题的情况下，改进了上述模型，建立了一个连续时间MILP模型，其所提出的启发式算法与滚动周期算法相结合更优于离散时间模型的结果。Wu等人[21]考虑到非交叉场桥的安全距离等约束限制，建立了基于连续时间的混合整数线性规划模型，提出了一种再分配算法，为实时调度中的提供近似最优解作为作业方案。

随着对双场桥调度问题的研究，其可穿越式双ASC具有高效性和灵活性等特点，成为了国内外研究的重点，例如周静娴和胡志华[22]针对穿越式双ASC的调度问题，以ASC的最小化空载时间为目标，建立多目标混合整数规划模型，分析其运行速度、装卸量和存取比例对作业效率的影响。景贞文和韩晓龙[23]针对双ASC 的互相干扰问题，以双ASC的完工时间最小化为目标，提出9条优先权分配规则和两种避让方案（直接避让和动态暂存区），并进行调度仿真实验验证了所提方案的合理性。李敏和韩晓龙[24]为了缩减完工时间，根据优先权规则建立多目标混合整数规划模型，并针对可穿越式双ASC的参数设计了三组实验，证明了该模型可以提高堆场作业效率。

上述文献关于双场桥和可穿越式双ASC的研究都为本文的研究奠定了基础，其通常以最小化完工时间为目标，同时场桥的调度并没有考虑到场桥垂直方向的运行距离等不确定性因素。本文所研究的双ASC的调度问题，其目标函数中引入能耗这一系数，并且根据场桥装载和空载的情况，以及场桥规格大小设置不同的能耗系数，根据堆场集装箱位置设立三维坐标点，同时考虑到场桥作业的不同垂直高度问题，其更符合码头作业的实际情况。

1 问题描述

堆场内双ASC既可以与连接海陆两侧的AGV协调作业，也可以与外部集卡（集装箱卡车）一起协调作业。此外，堆场内的存箱作业和取箱作业也由ASC承担，如果堆场内双ASC 调度安排不合理或效率低下，会造成AGV 和外集卡的等待时间过长。同时，双ASC 空载和重载作业、不同作业速度都直接影响其能耗水平，其反过来直接影响ASC 的作业效率水平，所以合理的ASC调度优化显得尤为重要。

堆场内包含多个箱区（Block），而每个箱区内又包含多个贝（Bay）。在同一箱区的情况下，穿越式ASC可同时进行存箱和取箱作业，当目标集装箱作业的位置不在同一贝位时，两个ASC之间可以相互穿越；当目标集装箱作业的位置处于同一贝位时，两个ASC 之间可能会存在冲突。

如图3所示，穿越式双ASC配备一大一小两台ASC，并且两台ASC 始末位置已规定（横纵坐标箱区区块位置已用数字进行标注和设定）。从开始位置坐标出发，完成所有集装箱任务后返回初始位置坐标。

图3 可穿越式双ASC俯视图

将堆场内的可穿越式双ASC的存取箱作业分为四个步骤：（1）ASC 从上一个集装箱任务结束的终止位置到达随后的集装箱任务的开始位置，将这个过程称为空载过程，所需要的时间成为空载时间，用字母T 表示；（2）ASC 在目标集装箱任务的开始位置，对集装箱进行抓取作业，这个过程所需要的时间用th表示；（3）ASC从集装箱任务的开始位置将集装箱送达集装箱任务的终止位置，将这个过程称为装载过程，所需要的时间称为装载时间，用字母S 表示；（4）ASC在集装箱任务的终止位置，对集装箱进行释放作业，这个过程所需要的时间也用th表示。

2 模型

（1）模型假设

①只考虑一种标准箱型在同一箱区的情况。

②每个ASC在同一时间段内有相同的工作能力。

③在水平和垂直方向均作匀速运动Vk，不考虑其加速和减速。

④忽略集卡或AGV堵塞等因素造成的对场桥调配策略的影响。

⑤在不考虑自动化集装箱码头堆场箱区的堆存能力限制的条件下。

⑥忽略翻箱操作（由于配载安排与堆场堆存顺序不匹配所造成集装箱的移动）[25]。

（2）符号

K={1,2}：堆场内ASC的集合，k ∈K 。

C ∈{1,2,…,NC}：穿越式双ASC 的集装箱装卸任务集合，其中i,j ∈C,i,j ＞0。

OK：假设ASC 在初始位置为一个虚拟集装箱任务，且=C ⋃{OK}。

DK：假设ASC 在终止位置为一个虚拟集装箱任务，且=C ⋃{DK}。

HK：ASCK吊具的高度，HK=(5,6),即H1=5,H2=6。

VK：表示ASCK水平和垂直移动的速度，其中较小ASC 运行速度V1，较大ASC 运行速度V2。

M ：表示无限大的数。

（3）参数

COi=()表示集装箱任务i 的初始位置。

CDi=()表示集装箱任务i 的终止位置。

ROK=()表示ASCK的初始位置。

RDK=()表示ASCK的终止位置。

（4）变量

Ui∈{0,1}：表示集装箱任务i 的存取属性。Ui=1表示集装箱任务i 为存箱作业，否则为取箱作业，Ui=0。

xk,i,j∈{0,1}：xk,i,j=1 表示ASCK依次完成集装箱任务i 和集装箱任务j，否则xk,i,j=0。

xk,i∈{0,1}：xk,i=1 表示集装箱任务i 由ASCK完成，否则xk,i=0。

ak,i：表示ASCK完成集装箱任务i 的初始时间，且ak,i≥0。

dk,i：表示ASCK完成集装箱任务i 的终止时间，且dk,i≥0。

yk：表示ASCK完成最后一个集装箱任务后到达终点位置的时间。

w：表示完成所有集装箱任务的时间，且w ≥0。

sk,i：表示ASCK完成集装箱任务i 所需要的时间。

Tk,i,j：表示ASCK完成集装箱任务i 后到达集装箱任务j 的初始位置所需要的时间。

Tk,Ok,j：表示ASCK从初始位置到第一个集装箱任务所需要的时间。

Tk,j,Dk：表示ASCK完成最后一个集装箱任务后到达终点位置所需要的时间。

目标函数[M]

本文建立了混合整数线性模型[M]，式（6）、（7）表示ASC 的装载时间和耗能情况。式（8）、（9）表示ASCK从初始位置出发，依次完成任务i 和j ，回到终止位置。式（10）～（12）表示每一个集装箱任务只能被执行一次。式（15）表示ASCK完成集装箱任务i 的初始时间加上操作时间不能超过其终止时间。式（16）表示ASCK完成最后一个集装箱任务j 的终止时间加上运行到整个最后点的时间不能超虚拟任务的完成时间。式（17）表示任意两个任务，前一个任务的完成时间加上运行到下一个任务的时间不能超过下一个任务的初始时间。式（18）表示所有集装箱任务的完成时间不小于任意一个集装箱任务的时间。式（19）表示ASC 不能为降低耗能而无限延长集装箱任务的完成时间。

穿越式双ASC 同时处理同一贝位的集装箱任务时，假设ψ1表示终止位置在同一贝位的存箱任务；ψ2表示初始位置在同一贝位的取箱任务；ψ3表示取箱任务的初始位置和存箱任务的终止位置在同一贝位；ψ4表示存箱任务的初始位置和取箱任务的终止位置在同一贝位。

式（20）和（24）表示当集装箱任务i 和j 同为存箱作业且终止位置在同一贝位上，任务i 的完成时间早于任务j。同理，式（21）和（25）、式（22）和（26）和式（23）和（27）。

式（28）～（33）为模型中相关参数的约束范围和条件。

3 算例

以穿越式双ASC 的20 个集装箱任务为例，根据自动化码头的实际情况建立坐标，验证模型的实用性。目前已经知道的20个集装箱任务，如表1、表2所示。

本文使用Matlab进行求解，并且调用Yamlp工具箱和Gurobi 求解器。求解出ASC 的最优序列、最小时间和最小总耗能。即在20 个集装箱工作任务的情况下ASC的总耗能为626.25，具体路线如图4所示。

4 实验分析

为了进一步分析参数变化对结果的影响，本文分别从集装箱任务数量、速度，还有耗能系数的角度设计了三组不同的对比实验。

实验1 分析了不同数量集装箱任务条件下，双ASC总时间和总耗能的变化，如图5 所示，可以看出随着集装箱数量的增加，其总能耗呈线性增长。

实验2 比较1#ASC 与2#ASC 之间速度比值不同，即比较不同大小的V1/V2，对双ASC 总时间和总耗能的影响，具体情况如表3 所示（其他影响因素保持不变）。其不同双ASC速度之比下，其总作业时间和耗能的变化如图6所示。

表1 测试数据集合

表2 ASC耗能和速度

图4 双ASC的最优作业顺序图

图5 双ASC总时间和总耗能的随集装箱数量的变化

表3 双ASC速度、总时间和耗能

图6 不同双ASC速度之比下总时间和耗能的变化

由图6 可知，当V1/V2 处于（6/10，1）的范围时，总耗能随着比值的增大而减小。当V1/V2=9/10 时，双ASC的总作业时间最大，并且其总耗能是处于一个比较低的数值，整体上符合六阶多项式的关系。所以，进一步说明当双ASC 对同一箱区的集装箱进行任务时，可以合理调整两个ASC 的速度之比，使其耗能的增加速度达到最小，从而以最小的能耗作业更多的集装箱任务。

实验3 比较1#ASC和2#ASC装载和空载的耗能系数不同，对双ASC总时间和总耗能的影响结果（其他影响因素保持不变，例如：集装箱任务数量和速度），具体情况如表4所示。

由图7可知，当α/β=1/2 时，即当1#ASC与2#ASC之间的能耗系数比为1/2 时，在不同条件的情况下其总作业时间总是保持最小。并且当α1/α2 处于（1/3，1）时，其总耗能的增长速度也随着增加，当α1/α2 处于（1/4，1/3）时，其总耗能的增长速度随之减小。

图7 不同耗能系数下总时间和耗能的变化

表4 双ASC装载与空载耗能系数、总时间和总耗能

综上所述，三组实验从整体上表明：当双ASC对同一箱区的集装箱进行任务时，可以通过合理地调整两个ASC在不同状态下的耗能系数之比，从而达到耗能的增加速度最小，来提高双ASC的作业效率。

5 结束语

随着信息技术的发展，自动化的集装箱码头成为国内外发展的趋势。越来越多的传统码头正在进行自动化改造。本文研究自动化集装箱码头为在穿越式双ASC作业的单个箱区内，给予其作业一定数量集装箱任务下不同的耗能系数，以最小化集装箱任务的总完成时间和总耗能为目标，建立了混合整数规划模型。并且通过设计了三组基于集装箱任务，双ASC 总时间和总耗能的对比实验。实验结果表明：（1）在不同能耗系数条件下，当双ASC的耗能系数达到一定值，能够保证其耗能的增加速度最小化，能够以最小的能耗作业集装箱任务，来降低码头作业成本。（2）当两个ASC（可穿越式）的耗能系数达到一定的数值时，能够保证其作业并完成集装箱任务的总时间最小。所以，自动化码头可以通过不断改进和优化双ASC 的耗能水平（通过改变其作业速度），使得作业集装箱任务的总时间和总耗能达到最小或最优的情况。（3）在自动化码头的堆场作业中，可以通过调整其作业的集装箱任务数量和双ASC 的作业速度，来减少总时间和总耗能，从而提高码头堆场的作业效率，节约自动化码头作业成本。

在自动化码头的复杂的实际作业环境中（岸桥、水平运输和场桥），堆场作业作为配合水平运输和岸桥作业的重要环节，直接制约着其他作业环节和流程的运行，其双ASC 的作业决定着水平运输和岸桥的作业效率。减少堆场中ASC的能耗水平，提高其作业效率，对整个自动化码头的作业效率都具有重要意义。本文对双ASC的考虑中并没有考虑其诸多的限制因素和其与水平运输的协同调度等问题，可以在未来研究中进行进一步的探讨。