时间窗下单船岸桥调度——基于数学规划和规则的启发式算法

乐美龙，赵彦营，刘秀玲

LE Meilong,ZHAO Yanying,LIU Xiuling

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

The Logistics Research Center,Shanghai Maritime University,Shanghai 201306,China

1 引言

随着集装箱运输的不断发展，集装箱港口竞争日益激烈，为此，提高集装箱港口生产率尤其重要。涉及集装箱港口生产率的操作有两项：岸桥、龙门吊的装卸操作和集卡的水平运输。其中，岸桥是集装箱港口最重要也是最昂贵的设备。合理制定岸桥的调度计划，有助于提高岸桥的生产率，减少船舶作业时间，降低港口运作成本，对提高集装箱港口的竞争力具有重要意义。

岸桥问题分为两种：岸桥安排问题QCAP（Quay Crane Assignment Problem）和岸桥调度问题QCSP（Quay Crane Scheduling Problem）。QCSP是指给已指定的一组岸桥进行装卸排程。为此，必须定义装卸任务属性和岸桥属性。

装卸的任务属性定义包括三个方面：

（1）任务的定义

①贝位域（Bay areas）：一个任务是由某些贝位上的装卸集装箱组成。

②单个贝位（Bays）：一个任务是一个贝位上的所有装卸集装箱。

③堆垛（Stacks）：同一贝位同一个列位置的一些集装箱。

④集装箱组（Groups）：同一贝位上的某几个列上的集装箱。它们通常有相同的目的地、类型等。

本文任务的定义：先根据贝位和装卸操作分为一系列大任务，再将每个贝位上的有装卸操作任务的一个集装箱视为一个小任务，只有当岸桥出现替接移动时，才会出现大任务的分割。

（2）任务的优先顺序：根据集装箱在船上同一贝位的位置和装还是卸操作而定。如一艘船舶：同一贝位先卸后装；先卸甲板再卸舱内；先装舱内再装甲板。

（3）任务的不可同时执行性：由于岸桥的安全距离要求，有些任务不可以同时执行。

岸桥属性定义包括六个因素：

（1）准备时间（Ready times）：每台岸桥的最早可获得时间。

（2）时间窗（Time windows）：每台岸桥都有一个可作业的时间窗。

（3）位置（Position）：每台岸桥都有一个初始位置和终止位置。

（4）转移时间（Travel times）：每台岸桥在贝位之间转移的时间。

（5）安全距离（Safety margins）：同时作业的两台岸桥之间都有一个最小的安全距离，即8个贝位距离。

（6）岸桥的装卸速度：由于岸桥或岸桥司机的操作熟练程度不一样，每台岸桥的装卸速度也不一样。

理论研究中主流的岸桥调度目标函数有两个：一是最小化岸桥的最迟作业完成时间和所有岸桥作业时间总和，前者权重大于后者；二是最小化岸桥的最迟作业完成时间。

在岸桥调度研究方面，Dirk Steenken[1]等人建立了just-in-time调度模型，研究了出口集装箱船的每个集装箱的船上储位问题，目的是减少岸桥的等待时间。Kim和Park[2]研究了单艘船舶的岸桥调度问题，在考虑岸桥任务的优先顺序、岸桥之间的安全距离等因素下，建立混合整数线性模型，运用分支定界法和贪婪随机自适应算法进行了求解。Luigi Moccia[3]等人在Kim和Park模型基础上进一步拓展了约束条件的范围，他们运用CPLEX和分支-切割算法来分别求解小、大规模岸桥问题。Young-Man Park[4]等人研究了在堆场龙门吊干扰下的岸桥调度问题，运用贪婪随机自适应算法进行了求解。Marcello Sammarra[5]等人采用Kim和Park的模型，将岸桥调度问题分解为路径和排程两个子问题，从而转化为求解最小化最长路径问题，分别运用禁忌搜索算法和局部搜索算法进行求解。Der-HorngLee[6]等人在以一个船舱为一个任务、岸桥之间没有相互干涉限制的条件下建立了混合整数线性模型，运用遗传算法进行了求解。R.Tavakkoli-Moghaddam[7]等人拓展了Kim和Park的模型，从岸桥成本角度，通过建立混合整数线性规划模型，研究了多条船舶的岸桥安排问题和岸桥调度问题QCSAP（Quay Crane Scheduling Assignment Problem），并运用 LINGO和一种有效的遗传算法分别求解了小、大规模问题。Frank Meisel[8]等人研究了单向移动的岸桥调度问题，他们通过建立分割图模型（Disjunctive graph model），运用分支定界启发式算法进行求解，并提出了新的分支原则。Kap Hwan Kim[9]等人研究了双吊具技术下的岸桥调度问题，它以最大的双吊具岸桥的操作次数（也就是最小化岸桥的操作次数）为目标函数，运用一种混合启发式算法进行求解。Der-Horng Lee[10]等人研究了关于进口集装箱的岸桥和集卡联合调度问题，通过建立混合整数线性模型，并运用遗传算法和改正的规则启发式算法（Modified Johnson’s Rule-based Heuristic Algorithm，MJRHA）进行了求解。Frank Meisel[11]建立了带有时间窗的岸桥调度模型，并运用树枝搜索启发式算法进行了求解。Frank Meisel[12]等人研究了单艘船舶的岸桥调度问题，在不同工作效率、时间窗，并向同一个方向移动条件下，建立混合整数线性模型，运用分支定界法求解模型，并提出了新的分支原则。

在上述研究基础上，综合考虑岸桥属性和任务属性因素，提出了基于规则的、更贴近实际的、带有时间窗的岸桥调度优化问题，并进行了分阶段求解。

2 问题描述

在文献[11-12]基础上，给定一组岸桥，采用最小化单艘船舶岸桥最迟作业完成时间为目标函数；考虑任务属性中任务的优先顺序、不可同时执行性和岸桥属性中岸桥的时间窗、转移时间、初始位置、安全距离、装卸速度等因素，通过建立混合整数线性模型P1，得出各台岸桥的装卸任务时序表。岸桥调度问题流程如图1所示。

图1 岸桥调度问题流程

模型基于以下假设：

（1）岸桥在同一轨道上作业，因此岸桥不能交叉作业；

（2）岸桥只能在可获得的时间窗内作业；

（3）同时作业的两台岸桥之间都有一个最小的安全距离，即8个贝位距离；

（4）岸桥的装卸速度：岸桥是同一性的。但由于港口每台岸桥司机的操作熟练程度不一样，岸桥的工作速度也不一样。

3 数学模型P1

3.1 参数

3.2 决策变量

W ，船舶装卸完成时间；Ci，任务i的完成时间；Ek，k岸桥的结束时间。

Zij，任务i和任务 j不能同时执行；任务i完成后，任务 j才能开始取1，反之0。

3.3 目标函数

目标函数式（1）表示单艘船舶的最小化作业完成时间。目标函数也可以表示为：

3.4 约束条件

模型最终给出船舶的岸桥作业完成时间和带时间窗的岸桥调度时序表，其中岸桥调度时序表包含了每台岸桥的任务次序、每项任务的开始时间和结束时间。公式（3）表示船舶作业完成时间不早于任何一台岸桥的最迟作业完成时间。公式（4）定义了每台岸桥的第一项任务。公式（5）定义了每台岸桥的最后一项任务。公式（6）定义了一项任务一次只能有一台而且必须有一台岸桥去执行。公式（7）表示岸桥执行任务的流动平衡，即每台岸桥不管从哪个任务进入任务 j，就必须从任务 j转入别的任务。公式（8）定义了每项任务的完成时间。公式（9）定义了有优先顺序的集合对(i，j)，任务i必须在任务 j开始之前完成。公式（10）表示若任务i在任务 j之前，任务 j开始时间必须在任务i完成后。公式（11）定义了当任务i和任务 j距离小于8个贝位时，任务i和任务 j不能同时作业；要么任务i作业在前，任务 j作业在后；要么任务 j在前，任务i在后。公式（12）定义了每台岸桥的完成时间。公式（13）和公式（14）定义了每台岸桥可作业的时间窗。公式（15）～（17）定义了三个正数变量。公式（18）和公式（19）定义了四个0-1变量。

4 基于规则的启发式算法

4.1 简单模型P2

为降低上述模型P1的求解复杂度，在文献[11-12]基础上建立了简单模型P2。P2只初步求解单艘船舶岸桥的最短作业完成时间，不求每台岸桥的每项任务的开始时间和完成时间。

4.1.1 简单模型P2问题描述

给定一组岸桥，考虑岸桥的时间窗、移动时间和装卸速度三个因素，建立以单艘船舶岸桥的最短作业完成时间为目标函数的模型P2。基于下述假设，建立模型P2。

（1）岸桥之间不存在干扰，不考虑岸桥之间的安全距离。

（2）不考虑装卸任务之间的优先关系。

（3）每台岸桥都有可作业的时间窗。

（4）岸桥在两个贝位间有一定的转移时间。

4.1.2 简单模型P2引入新的决策变量如下：

Dk1，如果k岸桥；0，否则。

简单模型P2：

公式（1）仍是目标函数，表示单艘船舶的最短作业完成时间。公式（20）定义了船舶作业完成时间不早于任何一台岸桥的最迟作业完成时间。公式（21）定义了每台岸桥可作业的时间窗。公式（22）～（28）定义了每台岸桥的最小移动时间。公式（29）定义了三个正数变量。公式（30）和公式（31）定义了两个0-1变量。

4.2 基于规则的启发式算法

在给定的岸桥时间窗下，为岸桥制定岸桥调度时序表，它是指给各岸桥分配船舶装卸作业任务并安排作业先后顺序。目标是使各岸桥结束作业必须在岸桥的时间窗内结束，并且船舶在港的作业时间最短。启发式算法的主要思想：阶段1，根据装卸船基本原则构建模型初始值。阶段2，在初始值基础上，根据装卸船基本原则和岸桥的具体工作时间进行局部调整，如果求得的解优于当前解，则更新当前解；否则，不断迭代，直到得到满意解。基于规则的启发式算法流程图如图2所示。

图2 基于规则的启发式算法流程图

4.2.1 启发式算法阶段1

阶段1根据装卸船基本原则构建模型初始值。

装卸船规则的优先级：

首先进行重点路的判断。

（1）如果有重点路，保证重点路作业，保证不使次重点路人为变成重点路。

（2）如果没有重点路，先做高柱贝位，避免产生重点路；尽量平衡各路作业量。

其次考虑挖孔作业，方便后来同时多路作业。

最后按照岸桥的移动方向完成整艘船舶作业。

步骤1根据船舶的贝位任务柱形图3确认是否有重点路。

图3 船舶贝位柱形集装箱图

重点路定义为：单船相邻两个大贝位上的任务箱量大于平均作业路数箱量。两个大贝位（八个贝位）的最大箱量 Qz：当时，。平均作业路数箱量Qm=总作业量/作业路数，Qm=Q/m。当Qz≥Qm，此为重点路，进入步骤2和步骤3；当Qz＜Qm，此船无重点路，进入步骤2和步骤4。

根据船舶的贝位任务数量，即船舶的贝位任务柱形图（见图3），结合该船总的装卸箱量，可确认该船舶是否有重点路。

步骤2挖孔作业思想

挖孔作业是指单船上连续三个大贝位都有装卸任务时，安排岸桥先执行中间的一个贝位上的任务，即当li+4=lj，且lj+4=ll，先安排岸桥执行lj贝位上的 j任务。目的是方便后来的任务i和任务 j被不同的岸桥同时作业。

步骤3如果该船舶有重点路，则运用有重点路情况下的启发式算法。具体步骤如下：

第3.1步：结合挖孔作业思想，安排作业速度最快的岸桥作重点路任务。

第3.2.1步：如果li和lj是重点路任务，li+4=lj，且lj+4=ll，那么安排作业速度最快的岸桥k作lj贝位上的 j任务。

第3.2.2步：如果li和lj是重点路任务，li+4=lj，且lj+4≠ll，ll+4≠li，那么可以安排作业速度最快的岸桥从重点路的任意一个贝位开始执行任务。

第3.3步：如果li+4=lj，且lj+4=ll，安排岸桥作lj贝位上的任务；再根据贝位上的优先任务顺序执行。

第3.4步：岸桥的替接移动。当岸桥QC1完成li贝位上的任务，li+4=lj，且岸桥QC2在执行ll贝位上的任务，lj+4=ll；即当两项任务的间隔距离dij≥8时，当其中一台岸桥有空闲时，可以发生一次替接移动。两台岸桥同时向有未完成任务的方向移动，形成两台岸桥平行作业。

第3.5步：岸桥在完成一项任务时，去执行距离它最近的任务。岸桥任务依次循环，直至所有任务都被执行结束。

步骤4如果没有重点路，则用没有重点路情况下的启发式算法。具体步骤如下：

第4.1步：将总的装载箱量除以作业路数，得到平均每路作业的箱量。

第4.2步：按前后顺序将任务分配给各作业路。

第4.3步：对分配给各路的作业，结合挖孔思想，先安排各岸桥执行柱形图中的高柱贝位任务。

第4.4步：岸桥的替接移动。当岸桥QC1完成li贝位上的任务，li+4=lj，且岸桥QC2在执行ll贝位上的任务，lj+4=ll，即当两个任务的间隔距离dij≥8时，当其中一台岸桥有空闲时，可以发生一次替接移动。两台岸桥同时向有未完成任务的方向移动，形成两台岸桥平行作业。

第4.5步：岸桥在完成一项任务时，根据各作业路任务群去执行距离它最近的任务。岸桥任务依次循环，直至所有任务都被执行结束。

4.2.2 启发式算法阶段2

阶段2在初始值基础上，进行局部调整，寻求最优解。

根据岸桥作业的均衡化原则，及各岸桥的相应任务的同步性原则，在初始值的基础上进行局部调整，得到新解。如果求得的新解优于当前解，则更新当前解；否则，继续迭代，直到得到满意解。

5 算例

5.1 算例数据

计算数据为宁波某集装箱港口数据。具体数据见表1～表4。表4为两两任务距离表。另外岸桥的单位贝位移动时间t为0.003 h，岸桥间的最小距离为8个贝位距离。

表1 船舶装卸任务数据表

表2 岸桥数据表

5.2 模型P2解算

采用上述数据，运用LINGO9.0软件对P2模型进行求解。在惠普6515bADM Athlon64 X2双核处理器、内存为1 GB和硬盘为160 GB的个人计算机上，运行了24.5 h，得到了全局最优解，最短完成时间9.971111 h，它为模型P1的下限边界值。详细求解结果如表5，每台岸桥的工作任务、完成时间和左右最小移动时间。

表3 岸桥首个任务距离表

表5 简单模型P2求解结果

5.3 基于规则的启发式算法解算P1

同样采用上述数据，根据3.2节所述基于规则的启发式算法对模型P1进行求解，得到船舶的岸桥调度时序表如表6～表10。

5.4 数据分析

对模型P2和模型P1的求解结果（表11）进行比较，发现目标值从9.971111 h上升到10.427 h，增加了0.456 h。但是模型P2中有些岸桥的某些任务安排不符合港口实际，如岸桥在实际执行任务时不能相互跨越；模型P2中的岸桥1的任务14，岸桥2的任务20。

表6 QC1调度时序表1）

表7 QC2调度时序表1）

表8 QC3调度时序表1）

表9 QC4调度时序表1）

表10 QC5调度时序表1）

表11 两种方法结果比较表

由模型1的岸桥调度时序表，可得到任务衔接图（图4）。由图4可以直观看出各岸桥的相应任务完成时间很接近，这与港口的实际操作相符；另外各岸桥均在时间窗内作业。由此可见：该艘船舶的岸桥调度时序表和目标值10.427 h是符合实际的较好的满意解。

图4 单艘船舶岸桥任务时间分布图

6 结语

岸桥调度研究有利于缩短船舶在港作业时间，提高港口生产率。本文的主要创新点是在注重理论研究的基础上，更加关注实际应用，表现在：一是考虑了岸桥属性中岸桥的时间窗、装卸速度等实际因素。二是根据港口中控人员的实际操作，抽象出岸桥的工作原则，提出了基于规则的启发式算法，将其求解结果与下限值进行比较分析，发现该解属于较好的满意解。

本文的不足之处是没有考虑其他设备（集卡、龙门吊）对岸桥调度问题的影响，也没有考虑实际港口作业中的随机因素影响，如岸桥故障、天气的影响。因此，随机因素可作为进一步研究的方向。

[1]Steenken D，Winter T，Zimmermann U T.Stowage and transport optimization in ship planning[M]//Grotschel M，Krumke S，Rambau J.Online Optimization of Large Scale Systems.Berlin：Springer，2001：731-745.

[2]Kim K H，Park Y M.A crane scheduling method for port containerterminals[J].European JournalofOperational Research，2004，156：752-768.

[3]Moccia L，Cordeau J F，Gaudioso M，et al.A branch-andcut algorithm for the quay crane scheduling problem in a container terminal[C]//AIRO Annual Conference，Cameerino，Italy，2005.

[4]Da Hunjung，Park Y M，Lee B K，et al.A quay crane scheduling method considering interference of yard cranes in container terminals[C]//LNAI 4293：Proceedings of the Fifth Mexican International Conference on Artificial Intelligence（MICAI2006）.Berlin Heidelberg：Springer-Verlag，2006：461-471.

[5]Sammarra M，Cordeau J F，Laporte G，et al.A tabu search heuristic for the quay crane scheduling problem[J].Journal of Scheduling，2007，10：327-336.

[6]Lee Der-Horng，Wang Huiqiu，Miao Lixin.Quay crane scheduling with non-interference constraints in port container terminals[J].Transportation Research Part E，2008，44：124-135.

[7]Tavakkoli-Moghaddam R，Makui A，Salahi S，et al.An efficient algorithm for solving a new mathematical model for a quay crane scheduling problem in container ports[J].Computers&Industrial Engineering，2009，56：241-248.

[8]Bierwirth C，Meisel F.A fast heuristic for quay crane scheduling with interference constraints[J].Journal of Scheduling，2009，12：345-360.

[9]Zhang Haipeng，Kim K H.Maximizing the number of dualcycle operations of quay cranes in container terminals[J].Computers&Industrial Engineering，2009，56：979-992.

[10]Cao Jinxin，Shi Qixin，Lee Der-Horng.Integrated quay crane and yard truck schedule problem in container terminals[J].Tsinghua Science and Technology，2010，15：467-474.

[11]Meisel F.The quay crane scheduling problem with time windows[J].Naval Research Logistics，2011，58（7）：619-636.

[12]Legato P，Trunfio R，Meisel F.Modeling and solving rich quay crane scheduling problems[J].Computers&Operations Research，2012，39：2063-2078.

[13]Meisel F，Bierwirth C.A survey of berth allocation and quay crane scheduling problems in container terminals[J].European Journal of Operational Research，2010，202：615-627.