题目：A survey of berth allocation and quay crane scheduling problems in container terminals
作者：Christian Bierwirth, Frank Meisel

摘要

Due to the variety of technical equipments and terminal layouts, research has produced a multitude of optimization models for seaside operations planning in container terminals. To provide a support in modeling problem characteristics and in suggesting applicable algorithms this paper reviews the relevant literature. For this purpose new classification schemes for berth allocation problems and quay crane scheduling problems are developed. Particular focus is put on integrated solution approaches which receive increasing importance for the terminal management.

批注：这是一篇综述文章，讲的就是集装箱码头岸边（seaside）运营层面——泊位分配（每个船舶什么时候可以使用自己的泊位）、岸桥分配（每个船舶分配多少岸桥）和岸桥调度（针对每个船舶分配得到的岸桥如何区完成具体的任务）的研究现状。并且对现有的模型进行了分类。然后着重讨论了下如何将这些集装箱码头岸边操作的问题集成起来优化。

泊位分配问题

In the BAP we are given the berth layout of a CT(Container Terminal) together with a set of vessels that have to be served within the planning horizon. For each vessel additional data like the vessel’s length including clearance, its draft, the expected time of arrival, and the projected handling time can be given. All vessels must be moored within the boundaries of the quay. They are not allowed to occupy the same quay space at a time. The problem is to assign a berthing position and a berthing time to each vessel, such that a given objective function is optimized.

批注：这块儿讲的是泊位分配问题的定义，就是给定规划期需要靠泊的船只的长度、船期表等信息以及泊位的布局给每个船只安排对应的泊位和靠泊时间。

Spatial constraints restrict the feasible berthing positions of vessels according to a preset partitioning of the quay into berths.

批注：按照泊位布局的不同可以把BAP分为离散（就像画线的停车位）、连续（不画线的车位）、混合（部分画线部分不画线的车位）和内凹。

Temporal constraints can restrict the berthing times and the departure times of vessels.

Static arrival: There are no arrival times given for the vessels or arrival times impose merely a soft constraint on the berthing times. In the former case it is assumed that vessels already wait at the port and can berth immediately. In the latter case it is assumed that a vessel can be speeded up at a certain cost in order to meet a berthing time earlier than the expected arrival time.
Dynamic arrival: Fixed arrival times are given for the vessels, hence, vessels cannot berth before the expected arrival time.

批注：按照对船舶可开始停泊时间的限制可以把BAP分为静态和动态的。静态文献中常常有两种做法，一种是直接不考虑船舶的预计到达时间，这时研究的BAP就是假设在规划期开始所有船舶已经在港口等着被分配泊位了，另一种则介于静态和动态之间，就是说船舶可以在预计到达时间前使用泊位，但是得受到惩罚。而动态则是说船舶不能在其船期表规定的预计到达时间开始前使用泊位，例如Berth allocation considering fuel consumption and vessel emissions这篇论文的约束条件（3）。

Vessel handling times are assumed deterministic in the vast majority of published BAP models. Still, literature deals with vessel handling times in different ways.

1. They are known in advance and considered unchangeable, i.e. they are fixed.
1. They depend on the vessels’ berthing positions.
1. They depend on the number of cranes serving the vessels.
1. They depend on the work schedules of the assigned cranes.
1. They obey to combinations of (b), (c), and (d).

批注：文献中对船舶在港处理时间的处理方法。

岸桥分配

In the QCAP we are given a feasible berth plan and a set of identical QCs, which are available for service. For each vessel included in the berth plan, the volume of containers to be loaded and unloaded is known as well as the maximum number of cranes allowed to serve it simultaneously. The cranes are supposed to be lined up alongside the quay. They can be moved to every vessel but they are not able to pass each other. The problem is to assign cranes to vessels such that all required transshipments of containers can be fulfilled.QCAP and BAP are basically interrelated, because solving the QCAP can have a strong impact on the vessels’ handling times. Only in case of a discrete berth layout, where each berth holds a set of dedicated cranes, an explicit assignment of cranes to vessels is not necessary.

In practice, the QCAP is not found a difficult problem if solved by rules of thumb. Therefore, the problem has hardly received attention by its own in academic research. Due to the profound impact on vessels’ handling times, however, crane assignment decisions are involved in some advanced berth planning models.

批注：岸桥分配对船舶在港处理时间有很大影响，而处理时间又是BAP的输入参数，所以一般把QCAP和BAP放到一起优化。但对于离散BAP问题，因为泊位都有专用的岸桥，所有可以不考虑岸桥的分配问题。

岸桥调度

In the QCSP we consider a set of tasks, representing transshipment operations for a vessel, and a set of assigned QCs. Precedence relations among tasks can be given to ensure that unloading precedes loading and to represent the stacking of containers as defined by a stowage plan. Every task must be processed (usually without preemption) once by a QC while a QC can process at most one task at a time. A solution to the problem, called a QC schedule, defines a starting time for every task on a crane. Usually, the minimization of the makespan of the QC schedule is pursued because it represents the handling time of the considered vessel.

批注：岸桥调度问题的定义就是已知分配给每个船舶的岸桥，将对应船舶上的集装箱按特定方式划分为任务。决策岸桥处理每个任务的开始时间，去最小化完工时间（对应船舶的处理时间）。

BAP、QCAP和QCSP的整合

批注：第一种简单的思路就是按顺序决策这三个问题，但这样做是有坏处的——“existing interrelations between the planning levels are almost completely ignored by sequential planning. Often, this leads to plans of poor overall quality. If, for example, the vessel handling times are assumed too tight in the BAP, the QCSP might get infeasible. On the other hand, if the handling times are too loose, crane schedules will show a lot of slack time that cannot be used productively anymore.”

另外两种思路是Deep integration（深度整合）和 functional integration（功能性整合）。Deep integration将两个子问题合并为一个部分整体化的问题表述，这使得指令的传递以及对这些问题之间关系的明确考量变得不再必要。例如，深度整合可用于将泊位分配问题（BAP）和 quay crane分配问题（QCAP）合并为一个泊位分配与起重机分配的综合问题。功能集成通过一种计算方法来实现，该方法定义了解决子问题的顺序以及基础层和顶层之间的数据交换。两个问题实现功能集成的方式有两种，要么通过纳入反馈循环结构，要么通过纳入预处理阶段。

批注：不太理解深度整合，是指完全把两个问题融合成一个优化模型吗？功能性整合分两种，第一种是使用反馈回路，上层模型指导下层模型的求解，下层模型的求解结果反过来又修改上层模型的指导。For example, in a loop where the QCAP and the QCSP are involved, the QCAP determines crane assignments for vessels served simultaneously. For each vessel an individual QCSP instance results, which is solved at the base-level. At the top-level the returned crane schedules are used to check whether sufficient crane capacity is assigned to the vessels.另一种功能性整合式纳入预处理阶段，预处理阶段求解base level的模型，给top levle一定的提示，然后再依次求解top level和base level。