自动化集装箱码头岸桥-堆场作业均衡调度研究

丁 一，张 琼，林国龙

(上海海事大学 物流研究中心，上海 201306)

0 引 言

由于人工成本快速上涨、船舶大型化加速，如何提高自动化程度成为港口业界越来越关心的话题。自动化集装箱码头是将集装箱码头岸边与堆场之间的运输、堆场内的作业、道口的进出等全过程实现自动化运作的码头，自动化集装箱码头凭借其在节省人力成本、提高码头运行效率、绿色环保、安全稳定高效等方面的独特优势得到各国重视。目前，全球已有32座自动化集装箱码头建成。我国天津港、上海港和厦门港等正在为建成自动化集装箱码头积极布局。

自动化集装箱码头主要覆盖堆场与船边、堆场与道口间的水平运输及岸桥、轨道吊的垂直作业。堆场常用的自动化装卸设备是自动堆垛起重机(automated stacking crane, ASC)，在码头作业中发挥了重要功能。岸桥作为集装箱码头海侧装卸集装箱的主要设备，其装卸效率直接决定了港口的整体运营效率。因此，优化岸桥作业调度，对提高港口运作效率和竞争力具有重要意义。笔者将讨论自动化集装箱码头的QCSP。

目前国内外学术界对自动化集装箱码头的QCSP研究较少。S.M.HOMAYOUN[1]设计遗传算法解决了自动化集装箱码头中岸桥、自动导引车(automated guided vehicle, AGV)和分平台堆存系统的集成调度问题；S.H.SADEGIAN等[2]研究了缓存区空间无限制的自动化集装箱码头岸桥和自动升降车(automated lifting vehicles, ALV)集成调度优化问题；周秀丹等[3]针对自动化集装箱码头直接中转模式下的岸桥调度问题，以最小化中转完工时间和岸桥等待时间为目标，建立多目标优化模型，设计多目标遗传算法对模型进行求解。

传统集装箱码头的QCSP优化研究对本文同样有借鉴意义。对于单船的QCSP，WANG Y等[4]探讨了考虑堆场箱区工作负载的QCSP，并采用贪婪随机自适应搜索算法求解；K.H.KIM等[5]考虑岸桥任务的优先顺序、岸桥间的安全距离等因素，建立了混合整数规划模型，运用分支定界法和贪婪随机自适应算法进行求解；N.KAVESHGAR等[6]基于K.H.KIM等[5]提出的模型，运用改进的遗传算法求解QCSP，采用一种新的方法定义染色体以减少决策变量的数量，并且使用新的程序计算得出决策变量更加严谨的上下界；H.J.DA等[7]在QCSP中考虑了避免堆场场桥作业冲突约束，采用贪婪随机自适应搜索算法求解；乐美龙等[8]以岸桥作业集装箱量和作业时间两个均衡调度为目标，研究了集装箱码头岸桥作业均衡调度优化问题；对于多船的QCSP，S.CHOO等[9]通过堆场作业冲突约束将多艘船舶的QCSP相连接，并采用基于拉格朗日松弛定理的启发式算法解决该问题；S.H.JUNG等[10]解决了码头多场桥和多岸桥对于出口集装箱的提取调度问题，提出的遗传算法和模拟退火算法均考虑了相邻场桥作业冲突约束；Y.M.FU等[11]基于岸桥可以在多船间移动作业，综合分析了码头岸桥作业和调度问题，采用混合整数规划方法建模并用遗传算法求解。

对于堆场机械，其首要目标是在一定时间内，尽可能多地服务AGV，使得AGV可以持续不断地供给岸桥，满足岸桥作业要求，从而减少船舶的周转时间。在自动化集装箱码头堆场机械调度方面，T.PARK等[12]提出了基于启发式算法和局部搜索算法的自动化码头双ASC的实时协调作业问题；I.F.A.VIS等[13]以最小化ASC作业时间为目标，利用算法求解穿越式双ASC作业调度问题。

大部分文献在优化岸桥调度时主要以岸桥装卸任务完工时间最小化为目标，兼顾堆场箱区间作业量差异的研究是罕见的，箱区冲突一般由规定时间段内叠加的作业箱量是否超过箱区预设能力评估。求解结果通常在时间维度上使得箱区间作业量分配不均，从而造成水平运输设备和装卸设备忙闲不均，增加场区交通拥堵和作业冲突，延长码头装卸作业周期，增加码头的整体运营成本。相较于已有的研究，笔者的贡献是在自动化集装箱码头这一背景下，综合考虑作业效率和均衡性，深入研究QCSP。旨在探讨如何最小化船舶装卸作业时间的同时均衡堆场箱区间作业量，制定优化的岸桥作业计划，以实现码头设备合理调度，提高整体运作效率。目前国内自动化集装箱码头建设尚处于起步阶段，相应的理论研究较为缺乏，故笔者的研究具有重要的现实意义及创新性。

1 问题描述

集装箱船舶靠泊后，集装箱码头会配置一定数量的岸桥对船舶进行装卸作业。岸桥调度是指在确定船舶靠泊位置和分配岸桥数量后，考虑每台岸桥的作业开始时间、结束时间、岸桥间安全距离、各个任务的作业次序等约束，为船舶安排特定岸桥进行装卸服务，以确保船舶任务能够在规定的时间内完成。岸桥调度的主要作用是制定一个岸桥作业计划来衔接岸边和堆场作业，减少岸边和箱区的作业冲突，从而提高码头的整体运作效率。

岸桥按照作业顺序依次将相对应的集装箱装卸到集装箱船舶中，堆场内的ASC需要按照此顺序操作对应的任务，通过水平运输系统与岸边对接，从而满足岸桥作业要求，两种机械需协同完成装卸船任务。最后一个装卸任务的完工时间直接关系到岸桥对船舶的装卸时间，而最后一个装卸任务的完工时间由ASC和岸桥共同决定。所以堆场箱区的作业效率影响着岸桥对船舶的作业效率，进而影响了整个码头的作业效率。

自动化集装箱码头与传统集装箱码头在堆场布局、作业模式等方面存在极大差异。根据堆场自动化设备不同，可分为不同类型的自动化集装箱码头，笔者重点研究箱区采用对称式双ASC的自动化集装箱码头。如图1，传统集装箱码头堆场为顺岸式布局，各箱区内作业的场桥数量不均，场桥可在不同箱区间便捷移动。而自动化集装箱码头堆场为垂岸式布局如图2，在箱区的海陆两侧各配置1台ASC，ASC不可在不同箱区间移动。传统集装箱码头在箱区侧面车道任意位置进行集装箱交互，每台场桥作用相同，均可负责船舶作业和外集卡作业。而自动化集装箱码头只能在海陆两侧交换区进行集装箱交互，海陆两侧的ASC不可相互跨越，作业分工明确，分别负责海侧交换区的船舶作业任务与陆侧交换区的外集卡作业任务。

图1 传统集装箱码头堆场布局Fig. 1 Traditional container terminal yard layout

图2 自动化集装箱码头堆场布局Fig. 2 Automated container terminal yard layout

自动化集装箱码头与传统集装箱码头具有本质的区别，这决定了传统集装箱码头岸桥调度中的优化因素与原则不适用于自动化集装箱码头中。对于传统集装箱码头，在岸桥调度中若箱区间作业量分布不均，则为在指定工时内完成装卸船作业，必然导致场桥在不同工作负荷的箱区间移动，如此则难以有效提升装卸效率。而对于自动化集装箱码头而言，各箱区只有海侧ASC负责装卸船作业，在岸桥调度中若堆场各箱区工作量均衡程度低，某些箱区装卸任务过于集中，超出海侧ASC单位时间内最大负载能力限制，可能导致堆场该区域交通拥堵和设备作业冲突；某些箱区装卸任务过少，资源闲置浪费，如此不仅难以提高装卸效率甚至影响整个码头的正常运作。

为解决该问题，在自动化集装箱码头中，对某一计划期内所有靠泊作业的船舶进行岸桥调度研究。除考虑船期因素和业务约束如岸桥间安全距离外，充分考虑堆场箱区间作业量的均衡性，以最小化计划期内每艘船舶的装卸完工时间和均衡各时段内堆场箱区间作业量为目标，建立混合整数规划模型，求解岸桥的最优作业序列。

2 模型建立

2.1 模型假设

为保证抽象数学模型的有效构建，结合港口实际运作情况，对问题提出以下合理假设：

1)与岸桥装卸时间相比，岸桥在贝位间的移动时间很小，故此予以忽略；

2)岸桥投入船舶装卸作业后需等到其服务的船舶完成装卸任务后才退出；

3)岸桥本身不加区分，均有相同的工作参数及速率；

4)不考虑岸桥等待AGV的现象；

5)按靠泊先后顺序为船舶依次编号，将所有船舶的所有船贝依次编号，并且所有的岸桥都位于一条水平轨道上，将其从左至右依次编号；

6)每个贝位的任务可由多台岸桥在不同时间段完成；

7)不考虑船舶作业优先度。

在实际操作中，岸桥完成箱量为36箱的船贝装卸作业大概需1 h，而岸桥在相邻两个贝位间的移动时间不超过1 min，故假设1)合理。由于岸桥的不可穿越约束，为满足岸桥分配原则，集装箱码头往往要求岸桥一旦投入某船舶作业，必须完成该装卸任务，不能中途退出，故假设2)合理。影响岸桥装卸速度的不确定因素较多，但是相差基本不大，故可假设岸桥工作参数及速率一致，即假设3)合理。为了尽可能缩短船舶在港时间，集装箱码头往往投入足够多的AGV来配合岸桥作业，很少发生岸桥等待AGV的情况，故假设4)合理。为简化模型构建进行顺序编号，同时由于岸桥的不可穿越约束，为船舶分配的岸桥编号必然是连续的，故假设5)合理。在满足岸桥间安全距离和不可穿越的前提下，每个贝位的任务由多台岸桥在不同时间段完成可优化岸桥操作，提高作业效率，故假设6)合理。船舶作业优先度一般受到船舶靠泊时间和船方要求等因素影响，但由于船舶装卸完工时间取决于码头装卸效率，所以相对于最小化船舶装卸完工时间这一目标而言，船舶作业优先度相同，故假设7)合理。

一组岸桥服务于一艘船舶，卸船先于装船，为了便于阐述，笔者只进行出口箱装船作业，然而模型同样适用于卸船过程。

2.2 参数定义

对参数中符号的定义如下：

i为船舶编号；j为船舶贝位编号(按其在船上位置从左至右编号)；q为岸桥编号(按其相对位置从左至右编号)；b为堆场箱区编号；S为计划期内待装卸作业的船舶数量；Qi为船舶i装卸作业所配置的岸桥数量；Bi为船舶i的贝位数量；Z为船舶装卸作业时所关联堆场箱区数量；T为计划期内时间段总数，时间段由t(第几小时)表示，T={1,2,…,t,…}，L为计划期时间跨度；r为相邻岸桥所在贝位编号的最小差值，即最小安全距离；Pij为船舶i上j贝位的任务量；Mi为船舶i的最大装卸作业时间；Ni为计划期内，船舶i装卸开工时间与计划期开始时间之差；Hbt为在t时间段箱区b的最大作业能力；α、β分别为目标函数中船舶装卸作业时间最小化和箱区间作业量均衡的权重系数。

2.3 决策变量

引入决策变量如下：

对部分决策变量的进一步解释如图3。

图3 部分决策变量示意Fig. 3 llustration of some decision variables

2.4 数学模型

综合考虑堆场箱区间作业量均衡因素，建立了岸桥调度的混合整数规划模型。

目标函数：

(1)

约束条件：

(2)

(3)

i=1,…,S,j=2,…,Bi,q=1,…,Qi,t=1,…,T

(4)

i=1,…,S,j=1,…,Bi-1,q=1,…,Qi,t=1,…,T

(5)

(6)

(7)

λijqbt≤xijqt,

i=1,…,S,j=1,…,Bi,q=1,…,Qi,

b=1,…,Z,t=1,…,T

(8)

i=1,…,S,j=1,…,Bi,b=1,…,Z

(9)

i=1,…,S,j=1,…,Bi,b=1,…,Z,t=1,…,T

(10)

b=1,…,Z,t=1,…,T

(11)

(12)

(13)

xijqt,λijqbt,uit∈{0,1},i=1,…,S,j=1,…,Bi,

q=1,…,Qi,b=1,…,Z,t=1,…,T

(14)

q=1,…,Qi,b=1,…,Z,t=1,…,T

(15)

目标函数(1)是最小化计划期内每艘船舶装卸完工时间之和及均衡各时段内堆场箱区间作业量，其中，将最小化每艘船舶的装卸完工时间之和，转换为最大化一个计划期内船舶装卸完工之后的时间之和。约束(2)确保1台岸桥在任意时间段内只能且必须位于船舶的一个贝位上。约束(3)确保在任意时间段内任意1个船贝上只能分配1台岸桥进行装卸操作。约束(4)和(5)规定了相邻岸桥间必须保持至少r贝位的安全距离。约束(6)和(7)表示岸桥间依次排序方式。约束(8)保证任意岸桥作业于任意船贝时需已分配给该船贝。约束(9)确保所有集装箱任务在计划期内都必须完成。约束(10)表示船舶装卸任务完成标志，即保证某一船舶所有贝位上的任务全部完成时才表示该船舶装卸任务完成。约束(11)定义了箱区剩余可作业能力Rbt。约束(12)表示在某一时间段内所有堆场箱区中的最小剩余可作业能力。约束(13)确保所有船舶的装卸作业时间不超过其规定的最大装卸时间。约束(14)定义了相关决策变量为0～1变量。约束(15)表示该决策变量的取值范围约束。

3 算例分析

为验证笔者所提出的模型的正确性与有效性，根据上海某集装箱码头的实际数据，进行算例设计与分析。结合该集装箱码头的实际情况，假设在该算例中，1台标准岸桥在相邻船贝间的移动时间为1 min，处理1个集装箱任务需2.5 min。ASC在箱区将集装箱吊起并沿箱区轨道搬运至目的地，ASC处理任务能力相同，处理1个集装箱任务的平均时间为3.5 min。堆场箱区单位时间最大作业能力由箱区海侧ASC单位时间可作业箱量衡量。船舶装卸作业所关联箱区作业能力相同，同时，为了便于表示，对船舶作业所关联箱区进行重新编号。

由于在多船岸桥调度模型中，若不考虑堆场箱区间作业量均衡约束，则各艘船舶的岸桥调度计划是相互独立的。故随机连续选取两艘船期重叠的船舶，根据船舶的计划靠、离泊时间，设定计划期T共有24个时间段(第几小时)，在计划期起止时间内，根据已知船舶作业参数(船舶信息、船舶靠离泊计划信息、岸桥作业数据等)进行岸桥调度分析研究。相关输入数据见表1。

基于以上数据，在运行环境为Intel(R) Core(TM) i3-2350M CPU@2.30 GHz、内存为4G的个人计算机上，使用IBM ILOG CPLEX Optimization Studio V12.2编程对模型进行求解，最终得到了各艘船舶满意的岸桥调度结果，并将该调度结果绘制成船舶贝位作业的示意，如图4和图5。

图4 船舶1岸桥调度结果示意Fig. 4 Diagram of QC scheduling result of ship NO.1

图5 船舶2岸桥调度结果示意Fig. 5 Diagram of QC scheduling result of ship NO.2

船舶编号作业船贝量作业箱量配置岸桥数量关联箱区数量计划靠泊时间计划离泊时间最大装卸时间/min1192 020332.009-27(09:30)09-28(12:00)1 4402151 102521.009-27(10:00)09-28(10:30)720平均数171 561426.5——1 080

图4与图5中实心矩形部分表示岸桥正在进行作业，包括提箱、放箱作业以及负载集装箱运输作业，实线部分表示岸桥空载运行。问题的实质即如何编排每台岸桥的任务次序和每项任务的开始与结束时间，使得岸桥的最大完工时间最短，从而得到最优的岸桥调度计划。

以所得岸桥调度结果进行装卸船作业，船舶1与船舶2所需作业时间分别约为1 408 min和690 min，能够保证船舶在最大允许装卸时间内作业完工，尽早离泊。由岸桥调度结果示意图可知，在整个作业过程中，岸桥装卸船作业较为集中，在作业过程中位置来回摆动较少。岸桥工作保持了连续性，且每个任务均在调度的序列中，每个任务完成且仅完成了一次。由此可以看出所提出的模型对于求解自动化集装箱码头多船情形下岸桥调度优化问题是有效并且可靠的。

为了进一步分析模型中箱区作业量均衡约束对岸桥调度的影响，将原模型中权重系数设置为α=1,β=0，以装卸作业完工时间最小化为目标，并将箱区均衡约束(11)、(12)进行松弛，得到单目标岸桥调度模型。同样采用CPLEX编程求解，得出两种目标下各艘船舶的岸桥总作业时间，结果如表2。

表2 不同目标下调度方案结果Table 2 Scheduling results by different targets

针对两种目标下生成的调度方案，绘制出两种调度方案在计划期各时段内的堆场箱区作业量不均衡度图，如图6。

由表2可知，考虑箱区间作业量均衡的多目标调度方案所得各艘船舶岸桥总作业时间比仅以装卸完工时间最小化为目标的调度方案分别减少了近8.83%和10.09%。由图6可知，在各时段内，多目标模型中各箱区作业量标准差，即不均衡度较单

图6 不同目标下堆场箱区作业不均衡度Fig. 6 Workload imbalance degree of yard blocks by different targets

目标模型中各箱区作业量不均衡度有所降低，从2%到15%不等。单目标调度方案中由于各时段内箱区间作业量参差不齐导致任务最大完工时间增加。因此，在自动化集装箱码头岸桥调度中考虑箱区间作业均衡性是有必要的，运用笔者建立的模型可有效均衡堆场箱区间作业量，在很大程度上减少了船舶装卸作业时间。从长远角度看，在岸桥调度过程中考虑均衡箱区间作业量，可极大地提高设备资源整体利用率，减少岸边和箱区的作业冲突，从而提高码头的整体运作效率和服务水平。

4 结 语

研究了自动化集装箱码头多船情形下岸桥调度优化问题，考虑岸桥间互不跨越、安全距离及堆场箱区作业量均衡等多方约束，以最小化船舶装卸完工时间且均衡各时段内堆场箱区间作业量为目标，建立混合整数规划模型，并用CPLEX验证了模型的正确性。在算例分析中，为了进一步探讨箱区作业量均衡对岸桥调度的影响，通过设定相应权重α、β，松弛箱区间作业量均衡约束，得到仅以船舶装卸完工时间最小化为目标的调度方案。通过实例对两种调度方案进行比较分析，验证得出在自动化集装箱码头岸桥调度决策中，考虑堆场箱区间作业量均衡的必要性和可行性，有利于减少岸边和箱区的作业冲突、缩短船舶装卸作业时间，提高码头的整体运作效率。需指出的是，由于自动化集装箱码头岸桥调度作业系统具有复杂性，所设计的算例规模较小，当问题规模扩大到一定程度时CPLEX无法求解，因此对该问题的相关算法设计与求解有待进一步的探讨。

参考文献(References)：

[1] HOMAYOUNI S M, TANG S H, MOTLAGH O. A genetic algorithm for optimization of integrated scheduling of cranes, vehicles, and storage platforms at automated container terminals[J].JournalofComputational&AppliedMathematics, 2014, 270:545-556.

[2] SADEGHIAN S H, HONG T S, ISMAIL N B. Integrated scheduling of quay cranes and automated lifting vehicles in automated Container Terminal with Unlimited Buffer Space[J].AdvancesinSystemsScience, 2014,240:599-607.

[3] 周秀丹, 胡志华. 自动化集装箱码头成组直接中转的岸桥作业调度及其遗传算法[J]. 武汉理工大学学报(交通科学与工程版), 2016, 40(4):719-724.

ZHOU Xiudan, HU Zhihua. A multi-objective genetic algorithm for quay crane scheduling problem considering group-based strategy and direct transshipment at automated container terminal[J].JournalofWuhanUniversityofTechnology(TransportationScience&Engineering), 2016, 40(4):719-724.

[4] WANG Y, KIM K H. A quay crane scheduling algorithm considering the workload of yard cranes in a container yard[J].JournalofIntelligentManufacturing, 2011, 22(3):459-470.

[5] KIM K H, PARK Y M. A crane scheduling method for port container terminals[J].EuropeanJournalofOperationalResearch, 2004, 156(3):752-768.

[6] KAVESHGAR N, HUYNH N, RAHIMIAN S K. An efficient genetic algorithm for solving the quay crane scheduling problem[J].ExpertSystemswithApplications, 2012, 39(18):13108-13117.

[7] DA H J, PARK Y M, LEE B K, et al. A quay crane scheduling method considering interference of yard cranes in container terminals[J].SpringerBerlinHeidelberg,2006,4293:461-471.

[8] 乐美龙, 徐根龙, 文洪蕊.基于作业均衡的集装箱码头岸桥作业调度优化[J]. 重庆交通大学学报(自然科学版), 2016, 35(3):155-161.

LE Meilong, XU Genlong, WEN Hongrui. Quay crane scheduling optimization considering operation balance at container terminal[J].JournalofChongqingJiaotongUniversity(NaturalScience) 2016, 35(3):155-161.

[9] CHOO S, KLABJAN D, SIMCHI-LEVI D. Multiship crane sequencing with yard congestion constraints[J].TransportationScience, 2010, 44(1):98-115.

[10] JUNG S H, KIM K H. Load scheduling for multiple quay cranes in port container terminals[J].JournalofIntelligentManufacturing, 2006, 17(4):479-492.

[11] FU Y M, DIABAT A, TSAI I T. A multi-vessel quay crane assignment and scheduling problem: formulation and heuristic solution approach[J].ExpertSystemswithApplications, 2014, 41(15): 6959-6965.

[12] PARK T, CHOE R, OK S M, et al. Real-time scheduling for twin RMGs in an automated container yard[J].OperationsResearch-Spektrum, 2010, 32(3):593-615.

[13] VIS I F A, CARLO H J. Sequencing two cooperating automated stacking cranes in a container terminal[J].TransportationScience, 2010, 44(44):169-182.