带任务顺序约束的岸桥集卡集成调度约束规划模型

秦天保，彭嘉瑶，沙梅

(上海海事大学交通运输学院，上海 201306)

0 引言

集装箱码头运营有许多调度问题，其中岸桥调度(Quay Crane Scheduling Problem，QCSP)和堆场内集卡调度(Yard Truck Scheduling Problem，YTSP)是两个互相联系的调度问题.但是，现有文献大多分开研究这两个子问题.KIM等［1］针对QCSP提出一个考虑任务顺序关系及岸桥冲突约束的混合整数规划(Mixed Integer Programming，MIP)模型，并设计分支定界算法和贪婪随机适应性搜索算法求解.MOCCIA等［2］设计分支割算法求解QCSP，改进解的质量.SAMMARRA等［3］进一步设计禁忌搜索(Tabu Search，TS)算法求解该问题，求解时间大大缩短，但解的质量稍差.BIERWIRTH等［4］设计一个基于分支定界的单向调度启发式算法求解QCSP，算例表明该算法能够在更短时间内产生比以往文献中算法质量更好的解.CHUNG等［5］设计一个改进的遗传算法求解QCSP，其质量和效率未超过文献［4］提出的算法.曾庆成等［6］将随机贪婪适应性搜索算法融入遗传算法求解QCSP.董良才等［7］提出带时间窗的岸桥调度MIP模型，并设计遗传算法求解.针对YTSP，BISH等［8］提出贪婪算法研究集卡调派问题.NG 等［9］设计遗传算法求解 YTSP.吕显强［10］对集装箱码头集卡分配问题建立整数规划模型.康志敏等［11］提出集装箱码头物流系统有色Petri网建模的基本构架和一种新的遗传算法编码方式求解YTSP.

由于岸桥和集卡具有很强的交互作用，将二者进行集成调度能够得到更好的全局解，这就是岸桥与集卡集成调度问题(Integrated Quay Crane and Yard Truck Scheduling Problem，IQCYTSP)，但集成调度文献较少.文献［12］中建立的基于时间最短的集卡线路优化模型，对岸桥的处理仅使用其作业时间，将所有岸桥作为一个整体考虑，没有涉及到岸桥与集卡之间作业时间衔接的约束以及岸桥执行各个任务的调度.CAO等［13］研究IQCYTSP，建立MIP模型、设计遗传算法并改进基于约翰逊规则的启发式算法求解，但其只求解小规模的问题，而且未考虑岸桥卸载任务具有顺序关系约束.

IQCYTSP问题是NP(Non-deterministic Polynomial)难题［13］，现有文献基本上都是设计各种启发式算法进行求解.本文针对IQCYTSP建立一个考虑岸桥卸载任务顺序关系的新的MIP模型和一个约束规划(Constraint Programming，CP)模型(CP是计算机科学、人工智能和运筹学的交叉技术)，设计问题的下界，通过实验验证CP模型求解的高效性.

1 问题描述与MIP模型

集装箱码头船舶装卸有多种组织方式，其中作业线方式是一种较常见的组织方式.一组岸桥服务于一艘船，卸船先于装船，本文只考虑卸船过程.船上的集装箱依贝划分为若干区域，一般情况下，每个区域配备一台岸桥.在已知每台岸桥所服务的集装箱区域的情况下，只需考虑单台岸桥的调度，所有岸桥调度结果是单台岸桥调度结果的简单综合.一组固定的集卡服务一台岸桥，称为一条作业线.集卡在岸桥处装载卸下的集装箱，运输到堆场指定箱区，由场桥卸下集装箱，集卡再空载返回到岸桥处装载下一个集装箱.假设一个集装箱为一个任务，岸桥执行卸载任务，集卡执行运输任务.各集装箱被岸桥卸载所用的时间不同.通常，靠近岸边的集装箱比远离岸边的集装箱卸载时间短，上面的集装箱比下面的集装箱卸载时间短.另外，码头实践中，会事先安排好船上的集装箱到堆场的某一特定位置，因此集卡运输不同集装箱到堆场的时间不同.这样，不同的集装箱卸载次序和对集卡的不同任务分配会导致不同的完工时间，该问题需要寻求一个最优的卸载次序以及集卡任务分配以使得总完工时间最短.

该问题的一个特点是岸桥从船上卸载一个集装箱后，若下面无集卡(集卡可能还未返回)，则岸桥必须等待，即处于阻塞状态，这一点模型中必须考虑，为此设计两个决策变量为岸桥从船上提取集装箱i并移动到陆侧的时刻，本文称之为岸桥卸载集装箱i的结束时刻;di为岸桥放下集装箱i到集卡上的时刻，也就是集装箱离开岸桥的时刻.di－即为岸桥阻塞的时间.岸桥放下集装箱到集卡上后才能开始一段过渡时间去卸载下一个集装箱.另一个特点是岸桥卸载船上集装箱时必须遵守一定的卸载顺序，如上层的集装箱必须先于下层集装箱卸载.下面，先建立本问题的MIP模型.

1.1 模型参数

n为集装箱数目;m为集卡数目;pi为岸桥卸载集装箱i所需时间;ti为集卡运输集装箱i到堆场的时间，也等于其返程时间;d为场桥从集卡卸载一个集装箱到堆场所需时间;sij为岸桥将集装箱i放到集卡上后，立即卸载集装箱j的过渡时间;Φ为具有顺序关系的岸桥卸载任务对集合，若任务(集装箱)i必须在任务j前(不一定是紧前)卸载，则(i，j)∈Φ;M为一个足够大的正整数.

1.2 决策变量

1.3 MIP 模型

目标函数(1)是最小化所有集装箱由船舶卸载到堆场存放的完工时间.约束(2)保证总完工时间大于所有集装箱运到堆场并堆放完成的时间.约束(3)保证岸桥卸载集装箱i时至少经过一段卸载时间(不包含岸桥等待集卡的时间)才能完全卸载操作.约束(4)保证任一集装箱只能分配给一辆集卡运输.约束(5)保证集装箱i离开岸桥的时刻大于岸桥卸载集装箱i的结束时刻.约束(6)保证集装箱i离开岸桥的时刻等于集卡开始运输集装箱i的时刻，该约束表达岸桥与集卡间的衔接关系.约束(7)和(8)保证岸桥卸载两个不同集装箱间要经过一段过渡时间，约束(7)表示如果集装箱j先于i被岸桥卸载(yij=0)，则j离开岸桥后至少经过sji的过渡时间才能开始卸载i.约束(8)表示如果集装箱i先于j被岸桥卸载(yij=1)，则i离开岸桥后至少经过sij的过渡时间才能开始卸载j.约束(9)表示若集装箱j先于i被同一集卡 k运输(yij=0，xik，xjk=1)，则运输并堆放j到堆场完成后，至少经过tj的过渡时间(即返程时间)才能开始运输i.约束(10)表示若集装箱i先于j被同一集卡k运输(yij=1，xik，xjk=1)，则运输并堆放i到堆场完成后，至少经过ti的过渡时间(即返程时间)才能开始运输j.约束(11)是岸桥卸载任务顺序约束，若(i，j)∈Φ，则任务(集装箱)j的卸载开始时间必须大于或等于i的完成时间.式(12)和(13)是决策变量域约束.

2 约束规划模型

2.1 模型特征

下面建立相应的CP模型.CP模型在不同的CP系统中表示方法不同，表达方式也不一致.本文所建CP模型是用IBM ILOG CPLEX Optimization 12.4中的OPL 12.4语言实现的.OPL针对调度问题提出一种新的概念，即区间(决策)变量.区间变量概念是约束规划在调度领域应用的一个重要扩展.LABORIE等［14］首次正式介绍CP中应用区间变量的内在机制.区间变量不同于一般MIP模型中的决策变量，区间变量具有起点、终点和长度(通常情况下，区间变量的长度等于终点与起点之间的长度)等内在属性，起点、终点都是整数，故以下的CP模型中，时间都被离散化为整数.

区间变量经常用于建模一段任务(活动)时间，起点为任务开始时刻，终点为任务结束时刻.本文提出的CP模型就是基于区间变量设计的.CP系统提供大量函数访问区间变量的属性和设置约束.为简单起见，主要采用BAPTISTE等［15］和OPL中的符号表示法表示基于区间变量的CP模型，该文献中提出的“活动”变量就是区间变量的雏形，提出的许多作用于活动变量的函数亦可用于区间变量，这些函数都是简单自明的.如start(a)表示区间变量a的起点、end(a)表示区间变量a的终点、presence(a)表示区间变量a是否出现在最终调度中(即在最终调度中是否被执行).文献［15］中未提到的一些函数和构造本文直接采用OPL中的构造.采用这套表示法表达的CP模型很容易转化成OPL语言实现.

2.2 模型参数

CP模型中除sij外，其他参数定义与MIP模型中的定义相同.CP模型中的sij为岸桥卸载集装箱i后立即卸载集装箱 j的过渡时间(i=1，…，n;j=1，…，n+1)，其中 si，n+1=0 是虚拟过渡时间.

2.3 决策变量与约束条件

2.3.1 变量域约束

CP模型定义3组区间决策变量:xi，yi和zki.xi表示岸桥卸载集装箱i的任务，其起点表示任务开始时刻，终点表示任务结束时刻，长度为卸载该集装箱的持续时间.求解结果中将得出开始时刻、结束时刻.对xi的域限制约束:∀1≤i≤n，

约束(14)限制岸桥卸载集装箱i的开始时刻必须大于0.约束(15)限制岸桥卸载集装箱i的结束时刻，这里给出一个简单的上界，即所有任务串行执行时完工时间的总和.约束(16)规定岸桥卸载集装箱的所需时间为pi.约束(17)保证岸桥任务i必须出现在最终调度中，即必须被执行.

区间变量yi表示集卡运输集装箱i的任务(这里将运输任务执行时长定义为集卡运输时间与场桥卸载时间之和)，对yi的域限制约束:∀1≤i≤n，

约束(18)限制集卡运输集装箱i的开始时刻必须大于0.约束(19)规定集卡运输集装箱i的结束时刻上界.约束(20)规定集卡执行任务的时间长度为ti+d.约束(21)保证任务必须被执行.

二维区间变量zki表示集卡k运输集装箱i的任务，它表示一个运输任务可能由任意一个集卡完成(最终会利用选择约束(alternative约束)限制仅能由一辆集卡完成).因此，可以将zki理解为一种模式选择区间变量，即一个任务可能有多种完成模式(一辆集卡为一个模式).∀1≤i≤n，1≤k≤m，

约束(22)，(23)，(24)分别限制 zki的起点、终点和长度.对zki的约束中没有presence约束，说明并非所有zki都必须被执行，只有那些被选中的才会被执行.

2.3.2 集卡任务选择约束

yi和zki受限制于alternative约束，表示如果执行运输任务 yi，则所有的 zki(k=1，2，…，m)中只能有一个被执行，且其起止时间与yi完全相同，这样就能保证每个集装箱只能由一辆集卡运输，即对一个运输任务yi要从多种执行模式(集卡)zki中选择一个来执行.∀1≤i≤n，1≤k≤m，

2.3.3 任务不重叠约束

所有的岸桥任务xi之间不能重叠，即岸桥只能一次一个、依次卸载集装箱，而且岸桥执行的前后任务之间还有一段过渡时间.为实现此约束，首先定义一个过渡函数transitionTimesQuay:{i|i=1，…，n}×{j|j=1，…，n}→{sij|i，j=1，…，n}，该函数用于定义岸桥卸载任务(集装箱)i到j的过渡时间为sij.然后，定义一个序列变量q.一个序列变量是一组区间的集合，这里，利用式(26)定义序列变量q为所有岸桥任务的集合.式(27)为顺序变量中的任务xi设置类型i，即任务类型就是任务(集装箱)编号，后面的约束将使用这个类型.利用约束(28)保证该序列中的任务不重叠，且两个相继任务之间需要一段过渡时间，系统取得序列变量中任意两个任务的类型，代入过渡函数transitionTimesQuay即可求得过渡时间.∀1≤i≤n，

类似地，集卡k执行的任务zki(i=1，2，…，n)也不能重叠，且集卡卸箱到堆场后，需要一段时间返回到岸桥，才能开始下一个运输任务，故集卡的两个相继运输任务之间有过渡时间，这个过渡时间就是返程时间.定义过渡函数transitionTimesTruck:{i|i=1，…，n}×{j|j=1，…，n}→{ti|i=1，…，n}，集卡任务i到j的过渡时间为ti.定义序列变量rk为集卡k的任务集合(见(29)).式(30)为顺序变量中的任务zki设置类型i，即任务类型就是集装箱编号.利用约束(31)保证集卡k的任务不重叠，且两个相继任务之间有一段过渡时间，系统取得序列变量中任意两个任务的类型，代入过渡函数transition Times Truck即可求得过渡时间.∀1≤i≤n，1≤k≤m，

2.3.4 岸桥与集卡任务顺序约束

在卸船过程中，对任一集装箱i，应该先由岸桥卸载，再由集卡运输，此顺序关系约束:∀1≤i≤n，

2.3.5 岸桥与集卡任务衔接关系约束

岸桥任务与集卡任务之间有一个衔接关系，即当岸桥卸载集装箱i完成时，必须等待集卡开始运输集装箱i，再经过一段过渡时间，才能开始卸载下一个集装箱j.

这个约束可以用蕴含约束(33a)表示，约束(33a)虽然直观易于理解，但是通过实验发现其求解效率较低，因为它是meta约束(指整个约束式中还含有其他约束式)，不是直接约束，故约束传播能力不强.实验发现采用OPL提供的startOfNext函数可得到更高的求解效率，故最终采用约束(33b)的形式.其中startOfNext函数返回的是q中xi紧后任务的开始时间.当 xi已经是最后的任务时，start－OfNext返回M.该约束说明q中岸桥任务xi的紧后任务的开始时间大于集卡任务yi的开始时间加上一段过渡时间.这里特别要说明的是过渡时间si，typeOfNext(q，xi，n+1)脚标的含义.要求得两个相继岸桥任务间的过渡时间，必须得到它们的任务编号(即任务类型).约束(33b)涉及两个岸桥的相继任务，前一个任务xi的编号是i，后一个任务的编号是typeOfNext(q，xi，n+1)，这里 typeOfNext函数返回 xi的紧后任务的类型，根据式(27)，岸桥任务类型等于其编号，故这两个相继任务的过渡时间为si，typeOfNext(q，xi，n+1).当 xi已经是 q 中最后一个任务时，typeOfNext(q，xi，n+1)返回 n+1，这个 n+1 表示虚拟岸桥任务的编号，定义任何岸桥任务到虚拟任务的过渡时间都为 0.∀1≤i，j≤n;i≠j，

2.3.6 岸桥卸载任务顺序约束

约束(34)确保若(i，j)∈Φ，则任务(集装箱)i的卸载完成时间必须早于任务j的开始时间.

2.3.7 资源约束

以上约束已经可以完全描述本文提出的岸桥集卡集成调度问题，但为了进一步提高CP引擎的求解效率，引入累积(cumulative)约束，它表示任一时刻所有任务消耗的资源总数不得超过设定值.这里将集卡作为资源，任一集卡任务yi执行期间会消耗一辆集卡资源，任一时刻集卡总消耗量不得大于集卡总数m.累积约束是全局约束，因此非常有助于求解器进行全局推理，从而提升求解效率.

约束(35)中pulse函数是OPL中的基本累积函数，其中的第一个参数表示消耗资源的区间变量，第二个参数表示区间变量在执行过程中消耗的资源数(集卡数).基本累积函数求和后成为汇总累积函数，代表所有基本累积函数在执行过程中消耗的资源总量.对汇总累积函数施加约束即为资源约束，这里运输任务消耗的集卡数不超过集卡总数.

图1 汇总累积函数

图1表示汇总累积函数消耗资源的曲线，其中H是资源量限制，各个a是区间变量.可以看出，执行每个区间变量时，汇总累积函数值增加，执行完区间变量后，汇总累积函数值减少.对汇总累积函数上限施加的限制就是累积约束，也就是资源限制约束.

2.4 目标函数

目标函数(36)是最小化集卡任务的最晚完工时间，也就是整体完工时间:∀1≤i≤n，

比较CP模型和混合整数线性规划(Mixed Integer Linear Programming，MILP)模型，可以发现 CP模型约束可以自然简洁地表达逻辑约束，无须使用大量0-1变量.

2.5 搜索策略

为进一步提升ILOG CP优化器搜索本问题解空间的效率，可以对默认搜索策略进行调整.这里利用ILOG CP提供的搜索阶段(search phase)机制干预搜索策略.通过搜索阶段可以指定CP优化器固定变量的次序，不同的次序可能会对搜索效率产生显著影响.通过实验尝试几个不同的次序，发现先固定顺序变量数组r，再固定q的搜索效率最高.搜索阶段用ILOG脚本定义如下:

3 下界分析

为评价CP模型的求解质量，需要得到较紧的下界(即完成所有任务时间的下界).本节提出一个新的求解上述问题下界的方法，即:完工时间下界=最后一辆集卡出发时刻的下界+其后所需运输时间的下界.以下介绍具体求法.

首先引入符号，记a(k)表示一组数值A={ai|i=1，…，n}中第k小的元素，即把ai从小到大排序后第k个元素;b［k］表示一组数值 B={bi|i=1，…，n}中第k大的元素，即把bi从大到小排序后第k个元素.

(1)计算最后一辆集卡出发时刻的下界.卸船开始时，m辆集卡在岸桥下等待.卸船任务从开始到最后一辆集卡出发所经历的最小时间(即下界)可表示为式(37)，即m个任务已由岸桥卸载完毕，包括岸桥工作时间和相邻两个任务间的过渡时间.

式中:p(m)表示所有卸载任务按卸载时间从小到大排序后第m个卸载时间;s(m－1)表示所有过渡时间从小到大排序后第m－1个过渡时间.

(2)计算最后一辆集卡出发后所需运输时间的下界.最后一辆集卡出发后所需的运输时间下界=(所有任务运输时间－最后一辆集卡出发前已经历的运输时间－全部集卡最后一次最大返程时间总和)÷集卡数，其中所有任务的运输时间(包括集卡在堆场的卸载时间和返程时间)为

最后一辆集卡出发前其他所有集卡的运输时间可以集卡为对象进行研究.第1辆集卡的运输时间为

第2辆集卡的运输时间为

第m－1辆集卡的运输时间为

累加上述式子得最后一辆集卡出发前已经历的运输时间为

全部集卡最后一次最大返程时间总和为

其中t［m］表示所有任务单程运输时间从大到小排序后第m个运输时间.故根据“最后一辆集卡出发后所需运输时间的下界”的计算公式以及式(38)，(39)和(40)，可得最后一辆集卡出发后所需运输时间的下界:

(3)完工时间下界.根据前面提出的完工时间下界计算公式，结合式(35)和(41)可得问题下界:

4 数值试验

将以上CP模型用IBM ILOG CPLEX Optimization Studio 12.4中的OPL语言实现，并利用其中的CP优化器求解.计算时采用默认参数配置，测试硬件平台为 Intel Core i5-24003.1 GHz CPU，2 GB内存.

为了测试CP方法能否求解实际规模的例子，随机生成7个不同规模的实例集，每个实例集含10个实例.各实例集装箱数(即任务数)分别为10，20，30，40，60，80 和100，集卡统一为 5 辆.生成数据时设置 pi服从［45，85］上的均匀分布，ti服从［180，600］上的均匀分布，sij服从［20，40］上的均匀分布，d为50.生成具有顺序关系的岸桥任务对(i，j)的规则:将每个实例的集装箱平均分为5组，前一组的集装箱必须在后一组集装箱之前卸载.

(1)小规模实例测试.对于10个任务5辆集卡的小规模实例，可用CPLEX求MIP模型得最优解，CPLEX得到的最优值与CP的求解结果的比较见表1.表1中“最优值”是CPLEX求得的最优目标值，“时间”是CPLEX求得最优解所用的时间，“CP值”是CP模型求得的最佳目标值，“差距百分比”是CP值相对“最优值”的差距百分比.观察表1可知，CP方法几秒内都得到最优解，说明CP的求解效率和求解质量都很高.

表1 小规模实例结果比较

(2)中大规模实例测试.进一步测试CP方法对中大规模实例的求解结果，求解时限为半小时(对这些实例，CPLEX无法求得最优解，会发生内存溢出).为了更加准确地观察求解收敛情况和解的质量，分5 min，10 min，30 min等3个时间段统计实验结果，结果见表2.表2中“下界”是每个实例集中10个实例的平均下界，“5 min内目标”是CP在5 min内求得的最佳目标值(为10个实例的平均值)，“时间1”是5 min内求得最佳目标的具体时间(为10个实例的平均值)，“差距1”是5 min内最佳目标相对下界的差距百分比(为10个实例的平均值)，其他以此类推.

表2 中大规模实例测试结果

观察表2可以发现，不超过80个任务的实例集在5 min内就可得到质量较好的解，而100个任务的实例集也可在10 min内得到质量较好的解.在半小时内所有实例都可得到质量较好的解.

5 结束语

采用CP技术建模求解带任务顺序关系约束的岸桥与集卡联合调度问题，在采用提高求解效率的累积约束及更加高效的约束表达式后，利用不同规模实例进行测试，结果显示CP具有很高的求解效率和求解质量，能够求解规模更大的问题.未来的一个研究方向是考虑将场桥调度也集成进来，开发集成范围更大的模型.

［1］KIM K H，PARK Y M.A crane scheduling method for port container terminals［J］.Eur J Operational Res，2004，156(3):752-768.

［2］MOCCIA L，CORDEAU JF，GAUDIOSO M，et al.A branch-and-cut algorithm for the quay crane scheduling problem in a container terminal［J］.Naval Res Logistics，2006，53(1):45-59.

［3］SAMMARRA M，CORDEAU J-F，LAPORTE G，et al.A tabu search heuristic for the quay crane scheduling problem［J］.J Scheduling，2007，10(4/5):327-336.

［4］BIERWIRTH C，MEISEL F.A fast heuristic for quay crane scheduling with interference constraints［J］.J Scheduling，2009，12(4):345-60.

［5］CHUNG S H，CHOY K L.A modified genetic algorithm for quay crane scheduling operations［J］.Expert Systems with Applications，2012，39(4):4213-4221.

［6］曾庆成，高宇.集装箱码头装卸桥调度优化模型与算法［J］.计算机工程与应用，2006，(32):7-219.

［7］董良才，丁以中，宓为建.基于时间窗的集装箱装卸桥调度［J］.上海海事大学学报，2011，32(1):1-7.

［8］BISH E K，CHEN F Y，LEONG Y T，et al.Dispatching vehicles in a mega container terminal［M］//Container Terminals ＆ Cargo Systems.Springer，2007:179-194.

［9］NG W C，MAK K L，ZHANG Y X.Scheduling trucks in container terminals using a genetic algorithm［J］.Eng Optimization，2007，39(1):33-47.

［10］吕显强.集装箱码头分派车辆的整数规划模型［J］.大连水产学院学报，2004，6(19):18-20.

［11］康志敏，吴洪明.港口集装箱码头集卡优化调度研究［J］.物流工程与管理，2011，33(2):59-61.

［12］计明军，靳志宏.集装箱码头集卡与岸桥协调调度优化［J］.复旦学报:自然科学版，2007，46(4):476-480.

［13］CAO J X，SHI Q X，LEE D H.Integrated quay crane and yard truck schedule problem in container terminals［J］.Tsinghua Sci＆ Technol，2010，15(4):467-474.

［14］LABORIE P，ROGERIE J.Reasoning with conditional time-intervals［C］//Proc 21st Int Florida Artificial Intelligence Research Society Conf Coconut Grove，USA，2008:555-560.

［15］BAPTISTE P，LABORIE P，PAPE C L，et al.Constraint-based scheduling and planning［M］//ROSSI F，van BEEK P，WALSH T.Handbook of Constraint Programming.Netherlands:Elsevier，2006:761-794.