约束规划求解自动化集装箱码头轨道吊调度

丁 一， 田 亮， 林国龙

(上海海事大学 物流科学与工程研究院, 上海 201306)

2018年全球集装箱海运量达2.01亿TEU[1]，海运在当前世界物流体系中承担超过70%的国际货物运输量，是国际物流运输的绝对主力。港口作为海运物流中的重要节点，其作业效率关系到海运物流的运量。港口堆场是进出口集装箱装卸、堆存的主要场所，堆场中集装箱起重机(简称“场桥”)的作业效率直接影响码头执行集装箱运输任务的数量。合理、高效的场桥调度策略不仅能帮助码头在单位时间内增加集装箱流通量，而且能减少,甚至避免因场桥调度不当而造成任务延迟的情况。

关于场桥调度的研究,早期主要针对单场桥调度。KIM等[2]以任务总完成时间最小为目标建立混合整数规划模型(Mixed Integer Programming,MIP)，研究场桥搬运过程中的合理任务顺序;NARASIMHAN等[3]证明单场桥完成集装箱装卸任务为N-P难题，并用分支定界的枚举法求出小规模任务情况下的最优解;NG等[4]以最小化任务总等待时间为目标，研究单台起重机执行1组拥有不同准备时间的集装箱搬运问题。随着港口操作工艺的持续发展，研究者根据轮胎式起重机可跨箱区作业的特点，对多场桥在堆场联合调度的问题进行探究。NG等[5]研究2台场桥协同完成1组拥有不同准备时间的集装箱搬运任务;ZHANG等[6]对堆场中各箱区在不同时段的任务量进行预测，重点规划起重机移动时间和移动路线;CHEUNG等[7]以每段时间内延迟工作量最少为目标，建立整数规划模型，提出逐次分段线性逼近法，并证明该求解方法对大规模场桥调度问题的有效性。与传统码头相比，发展理念更加创新、环保的自动化码头在近十多年得到迅猛发展，2017年年底,全球最大的自动化集装箱码头——洋山港4期开通试运行,将2台轨道式集装箱龙门起重机(Rail-Mounted Gantry Crane,RMG)置于同一个箱区是自动化码头考虑较多的一种策略。LI等[8]重点考虑RMG之间的干扰关系，以所有任务等待和延时的加权时间最短为目标，引入时间离散模型，将在固定长度范围内的任务一起考虑;LI等[9]在已有研究基础上，将模型转变成一个连续时间的场桥调度模型;PARK等[10]通过合理假设场桥运输速度，将时间离散化，考虑场桥作业冲突和翻箱问题，建立以自动导引运输车(Automated Guided Vehicle,AGV)和外集卡等待时间最短为目标的整数规划模型;GHAREHGOZLI等[11]通过仿真证明在堆场中设置共享区有助于提高集装箱搬运效率。

尽管关于场桥调度的研究颇多，但尚无运用约束规划(Contraint Programming,CP)方法解决该问题的研究。本文利用CP对调度问题的适用性，从时间长度设置决策变量。在考虑任务分段和接力区容量有限等要求的同时，将码头堆场在实际操作中选取的调度规则加入CP技术求解过程中。

1 问题描述与条件假设

1.1 问题描述

在自动化集装箱码头，堆场作为进出口集装箱重要的交接和保管场所，通常被分为多个箱区，每个箱区由多个倍位(bay)组成。自动化轨道式龙门起重机(Automatic Rail-Mounted Gantry Crane,ARMG)在自动化集装箱码头(Automated Container Terminal,ACT)堆场中,负责集装箱的水平搬运和附带的垂直搬运作业，主要起到串联港口内部AGV和外部集卡运输的作用。当前，堆场单箱区配置双ARMG的ACT多采用垂岸式设计。[12]靠近海侧的ARMG称为海侧ARMG，靠近陆侧的ARMG称为陆侧ARMG,其中:海侧ARMG的作业效率关系到在港船舶是否能按时离港;陆侧ARMG的作业效率直接涉及外集卡的等待时间。

由于2台ARMG共用同一轨道，相互之间不可跨越，因此须重视ARMG在搬运集装箱过程中的干扰问题。在箱区中间设置接力区是本文考虑用来解决干扰问题的方法,见图1。将1个堆存在路侧箱区的集装箱搬运至海测缓存区，既可由海侧ARMG直接完成作业,也可由陆侧ARMG先将集装箱搬运至箱区中间的接力区，再由海侧ARMG将该集装箱搬运至海侧缓存区。

图1 任务接力示意

1.2 条件假设

本文紧密联系ACT堆场场桥实际作业情况，如：集装箱初始和目标位置已知、集装箱作业要求已知等，提出的假设条件为

1) 堆场2端交接点容量足够大，ARMG在ACT两端作业时无需等待。

2) ARMG作匀速移动。

3) ARMG水平方向移动时间取决于其移动bay数，垂直方向移动时间取决于吊具抓箱和放箱的对准时间，忽略堆高度的影响。

4) 所有作业中不考虑翻箱作业。

5) 集装箱尺寸统一定为20英尺箱，不考虑偶数倍位放40英尺箱的情况。

6) 固定接力区位置，接力区容量可知。

为将ARMG在ACT两端交接区作业时间考虑在模型中，本文将两端的交接区各视为1个Bay，即在原箱区bay数量上增加2个Bay数量。

2 CP模型

本文建立的模型借助CPLEX12.4中的OPL语言实现。OPL语言中提出区间变量[13-14]的概念，区间变量即决策变量，是约束规划在调度问题研究方面的重要扩展。区间变量区别于一般的决策变量，具有起点、终点和长度(起点为任务开始时间，终点为任务结束时间，长度为任务持续的时长)。同时，每个区间变量都有出现状态[13]，该状态用来表示区间变量是否会出现在最终的解中。

本文基于区间变量设计CP模型，采用OPL中特定的函数和约束表达方式，如alwaysEqual、NoOverlap和endBeforeStart等[15]，在下文出现时解释其含义。

2.1 集合与参数

1)R1={1,2,…,m}为不需要通过接力完成的集装箱作业。

2)R2={m+1,m+2,…,n}为需要通过接力完成的集装箱作业。

3)K={1,2}，其中：1为海侧ARMG；2为陆侧ARMG。

4)RS为海侧ARMG作业集合；RL为陆侧ARMG作业集合；R为作业总集合，R=R1∪R2=RS∪RL。

5)t0为ARMG移动1个Bay长度的时间。

6)t1为ARMG在垂直方向上单次抓取或放下集装箱的时间。

7)c为堆场接力区容量。

8)bi,0为集装箱作业i初始Bay；bi,1为接力区Bay；bi,2为集装箱作业目标Bay。

9)B={1,2,…,bn}为堆场Bay集合，其中:1为海侧交接区;bn为陆侧交接区。

10)di为作业i的目标完成时间。

2.2 决策变量与约束条件

2.2.1变量值域约束

CP模型定义xi,k、zki,1和zki,2等3个区间决策变量。

(1)xi,k为ARMGk进行作业i，ARMG的作业顺序是通过求解xi,k开始和结束时刻所得的。对xi,k的值域进行约束,有

start(xi,k)≥0,i∈R

(1)

end(xi,k)≤M

(2)

(3)

presence(xi,k)=1

(4)

式(1)为ARMGk进行作业i的开始时刻必须大于0；式(2)为ARMGk进行作业i的结束时刻，给出一个简单的上界，M为一个自修正的参数；式(3)为ARMGk进行作业i的时长；式(4)为所有属于ARMGk的作业都会被ARMGk执行。

(2)zki,1为需通过接力完成搬运任务的集装箱i的第1段作业，对于i∈R2，k∈K，有

start(zki,1)≥0

(5)

end(zki,1)≤M

(6)

(7)

presence(zki,1)=1

(8)

式(5)为集装箱i第1段作业开始时刻必须大于0；式(6)为集装箱i第1段作业结束时刻；式(7)为集装箱i第1段作业时长；式(8)为所有集装箱i第1段作业都会被执行。

(3)zki,2为需通过接力完成搬运任务的集装箱的第2段作业，有

(9)

end(zki,2)≤M

(10)

(11)

presence(zki,1)=1

(12)

式(9)为集装箱i第2段作业开始时刻须大于等于第1段的结束时刻；式(10)为集装箱i第2段作业结束时刻；式(11)为集装箱i第2段作业时长；式(12)为所有需接力完成搬运的集装箱i第2段作业都会被执行。

CP中针对决策变量之间的关系有特定的表达方式。在此引入alwaysEqual函数，用来表示与控制变量之间关系。对于i∈R2，k∈K，有

alwaysEqual(zki,1,xi,k)

(13)

alwaysEqual(zki,2,xi,k)

(14)

式(13)和式(14)中:由zki,1和zki,2表示的接力箱第1段和第2段作业的开始、结束时刻与由xi,k表示的接力箱作业开始、结束时刻一致，即通过式(13)和式(14)将整个由xi,k所表示的作业顺序补充完整。

2.2.2任务不重叠约束

属于海侧或陆侧ARMG执行的作业在时间上不能重叠，即在ARMGk执行前后2个作业之间有段准备时间,等于ARMGk完成1次搬运作业之后，从当前Bay前往下一个作业位置的时间和2次垂直作业时间之和。为实现这个约束，现定义1个计算准备时间的函数

k∈K，transitionTimesARMGk:

(15)

式(15)中:i,j∈Rk,且i≠j。该函数用来定义海侧或陆侧ARMG在执行前后2个作业之间的准备时间。随后定义序列变量qk，k∈K。1个序列变量是1组决策区间的集合。

(16)

(17)

noOverlap(qk,transitionTimesARMGk)

(18)

式(16)为序列变量qk为所有ARMGk作业集合；式(17)为ARMGk作业设置序号；式(18)保证该序列qk中任务之间不重叠，且2个相继任务之间存在一段准备时间,其计算由系统从序列变量中取得2个作业序号，将这2个作业序号代入计算准备时间的函数中。

2.2.3接力箱的作业顺序约束

需通过接力完成搬运的集装箱作业，第1段作业必须先于第2段作业完成。在此，引入函数表示2个具有顺序关系的作业在发生时间上的先后关系。

endBeforeStart(zki,1,z(3-k)i,2),i∈R2;k∈K

(19)

式(19)为接力箱的第1段作业由ARMGk完成，第2段作业由ARMG(3-k)后完成。

2.2.4接力区集装箱容量约束

接力区由堆场中间固定的Bay组成，其容量有限。在此引入资源约束，表示任意时刻所有作业的资源消耗量不得超过最大值。pulse函数是OPL中的基本累积函数，一般可表示为pulse(a,b)，其括号中参数a为消耗资源的区间变量，参数b为区间变量在执行过程中消耗的资源数。基本累积函数通过累加成为总累积函数，对总累积函数施加约束即为资源约束。

(20)

式(20)中:括号中参数为完成接力任务第1段之后会消耗1个接力区Bay。式(20)为堆存在接力区中的集装箱总数不得大于接力区容量。

2.2.5ARMG之间距离约束

设置辅助决策变量fkb,t：t时刻ARMGk在Bayb上为1，否则为0。

(21)

b×f2b,t-b′×f1b′,t≥α

(22)

式(22)为在任意时刻，海、陆两侧ARMG之间的距离大于规定的安全距离α。

2.3 目标函数

目标是将海、陆两侧ARMG作业总延误时间最小化。

(23)

式(23)中:括号中第1部分为海侧ARMG在完成任务过程中的总延迟时间;第2部分为陆侧ARMG在完成任务过程中的总延迟时间。

3 结合调度规则的求解过程

3.1 调度规则

在ACT堆场上，不同调度规则实质上是ARMG在作业过程中产生冲突时所选择优化的侧重点不同。本文结合ACT堆场作业实际和CP模型考虑的接力区容量，提出3种调度规则。

3.1.1ARMG作业准备时间最短的任务优先

ARMG作业准备时间最短的任务优先(简称“Y1”)可有效缩短ARMG空载行驶距离，借助第2.2.2节提出的ARMG作业准备时间的计算函数transtionTimesARMGk，可帮助ARMG在作业过程中进行任务选择。

3.1.2海侧ARMG任务优先

海侧ARMG作业情况直接关系到港区内部AGV的运行效率，给予海侧ARMG任务优先权(简称“Y2”)可有效缩短海侧ARMG的作业等待时间，提高AGV作业效率。

3.1.3接力箱任务优先

本文考虑的中间接力区是固定Bay。为确保ARMG在接力区作业的便利性，接力区的堆存箱量不能按满载情况考虑。接力箱完成第1段搬运之后，堆存在接力区会造成接力区Bay资源被占据。因此，接力区容量在第2.2.4节作为重要资源进行考虑。优先考虑接力箱任务(简称“Y3”)，可弱化接力区容量带来的限制。

3.2 求解流程

1) 读入时间T内所有集装箱任务始末位置和目标完成时间；设定任务开始时间T0和其他参数。

2) 借助CP技术对时间T内所有的作业任务进行约束传播，如：对接力作业的前后2段作业进行控制，将第2段作业先于第1段作业完成的情况剔除，形成ARMG初始可选任务集合。

3) 将调度规则Y1、Y2和Y3分别置于CP求解阶段，在调度过程中，结合CP具备的搜索能力，求解ARMGk在t时刻从可选任务集合中所选取执行的任务i。

(bi,2-α-∑b·f2b,t)×t0

(24)

4 算例分析

以任务组为单位生成目标完成时间,以2台ARMG在各自固定的初始位置向任务开始运行的时刻作为开始时间，ARMG移动速度为v=6 m/s，即t0=1；安全距离α=2；ARMG垂直方向上抓取或放下1个集装箱的时间t1=30 s；本文箱区总bay包括陆侧交接点和海侧缓存区，共52个bay。将以上CP模型用CPLEX12.4编程求解，运行硬件环境为Intel(R) Core(TM) i5—320 M，2.60 GHz CPU，4 GB内存。多规模算例集求解结果见表1。

表1 多规模算例集求解结果

由表1可知:在小规模(50及以下)任务情况下，结合Y1的求解方式,可在10 s内求解出结果，总延误值皆为最小;在中规模(70～150)任务情况下，3种调度规则求解的总延误值的差距在5 min以内，其中任务规模越大，Y3在求解速度方面的优越性明显;在大规模(180及以上)任务情况下，结合Y3的求解方式有明显优势，求解质量提升约30.87%，且规模越大，提升越多。在求解速度方面，结合Y3的求解方式比其他2种提高1倍。

进一步从海、陆两侧的延误时间和任务延误总次数分析各调度规则对海、陆两侧ARMG作业的影响,见图2。Y2给予海侧ARMG作业优先权，海侧任务总延迟时间在各算例下都明显小于同规则下陆侧任务总延迟时间。在大规模算例下，Y2海侧任务总延迟时间明显优于Y1和Y3。Y1和Y3规则以符合调度规则的任务为优先，没有明确海侧或陆侧ARMG作业优先。在延误总累计次数方面，Y1与Y3有着相反的表现。在小、中规模算例下，Y1延误次数有7次最优;在大规模算例下，Y1延误次数最多,且伴随任务规模增加，延误次数扩增显著;Y3在大规模算例下可减少延误次数。

图2 海、陆侧在不同调度规则下的作业延误情况

5 结束语

在ACT堆场中， ARMG作业是集装箱内、外运输的串联环节，综合考虑其对在港船舶和外集卡的作业效率十分必要。本文建立单箱区双ARMG调度问题CP模型，采用任务接力的方式解决ARMG在作业时存在的干扰问题，设置3种任务调度规则。在CP求解过程中，通过多规模任务量算例分析，CP技术能在港口作业实时性的要求下求解出满足作业要求的调度次序。在小规模任务情况下，结合 ARMG作业准备时间最短、任务优先的搜索方法求解效果最好；在大规模任务情况下，接力箱任务优先的规则有明显优势，求解质量能提升约30.87%，求解时间可缩短1/2。因此，自动化码头的各堆场可根据不同时间段内任务数量规模的实际情况，选取不同的任务调度方式实现效率提升，提高对外服务的质量。