基于鲁棒优化的集装箱码头连续泊位分配研究

摘 要：合理的泊位调度计划能够提高码头资源的利用率，为解决不确定条件下的连续型泊位分配问题，对其建立了鲁棒优化模型，通过调节引入参数的值，可以根据不同的保守性得到不同代价下的鲁棒解。结果表明鲁棒解降低了船舶作业时间约束的保守性，提高了目标函数的最优性，因此可有效地降低决策的风险，在解决实际问题的过程中更为实用。

关键词：集装箱码头；泊位分配；鲁棒优化

中图分类号：U691 文献标识码：A

Abstract： Reasonable berth allocation plan can improve the utilization ratio of terminal resources. In order to solve the continuous berth allocation problem under uncertainty， a robust optimization model is proposed. The model can control the robustness of the solut❅ion by adjusting the parameters of protective level. The results show that the robust solution can lower the conservation of the ship operation time and improve the optimality of the objective function. Therefore the risk of decision-making is reduced and it is of great practical value.

Key words： container terminal； berth allocation； robust optimization

0 引 言

集装箱港口在国际物流和国民经济中具有很重要的地位，泊位分配计划是港口作业的基础，对港口运营方和船公司来说，制定合理高效的泊位计划都是非常重要的。

动态泊位分配问题，是指为船舶分配泊位时，并不是所有船舶都已到港，泊位分配时根据预计的船舶到港时间和相关信息安排停泊顺序和泊位[1]。连续泊位分配就是将码头岸线看成是一个整体，船舶到达后可以在任意位置停靠，充分利用岸线资源，为了使在一定时间内所有的到港船舶在港总时间最短，需要对船舶进行合理的泊位分配。

研究动态连续泊位分配问题时，主要依靠研究设计各种启发式算法以便于更高效的解决问题。如Guan和Cheung[2]针对动态泊位分配提出一个树搜索程序。Kim和Moon[3]用模拟退火算法求解BAP。Imai[4]等基于拉格朗日松弛技术求解这类连续BAP。Cordeau[5]等设计了禁忌搜索算法求解。Wang和Lim[6]设计了随机定向搜索算法求解动态连续泊位分配问题。Lee[7]等设计了两个贪婪随机适应性搜索算法求解动态连续泊位分配问题。

由于DCBAP问题是NP难题，以上文献基本上都是设计各种启发式算法进行求解。但在实际工作中，计划人员制定泊位调度计划时，通常存在一些不确定因素，如船舶到达时间，泊位作业时间等，将会对泊位分配计划的可用性造成重大影响。鲁棒优化可以应对港口不可避免的变动，使得泊位调度和员工工作计划有序实施，以提高码头的运作效率。本文的主要贡献在于运用新的方法――鲁棒优化的角度建模求解DCBAP问题。一方面，通过实验比较判断鲁棒优化方法应用于本问题的适用性，另一方面，为学术界开拓一个新的视角。

1 问题描述

泊位分配的流程为：船舶到港后先在锚地候泊，如果有空闲泊位且满足船舶的长度要求，则进入泊位，否则在指定区域等待；靠泊后需要等待岸桥等装卸机械及工人就绪后才能开始装卸作业；从船上将集装箱吊起，然后放在集装箱卡车上运往堆场，随后由龙门起重机将集装箱放入堆场中的指定位置。集装箱装船流程与此相反，如此往复，直至完成装卸，该船舶离港。

一个典型的集装箱码头泊位，可同时容纳多艘船舶，当没有空余的泊位时，船舶需要排队等待。为了简单起见，我们将船舶的等待时间和处理时间的总称为在港时间，我们的目标是为船舶分配泊位，并安排船舶使得总加权在港时间最小。

2 传统连续泊位分配模型

考虑泊位分配管理的一般性，本文建立动态泊位分配模型。假设每个泊位一次最多处理一艘船泊，装卸过程中不会中断操作并且泊位水深满足所有船只的停泊需求。基于以上问题的定义与假设，建立连续泊位分配模型。

2.1 参 数

S：连续泊位的长度；T：计划期长度；N：船舶总数；p：船舶i的处理时间；s：船舶i的大小，s包含了邻近船舶之间的相关数据；a：船舶i的到达时间；w：船舶i的分配权重，w是由港口运营商决定来代表船舶i优先的因素。

2.2 决策变量

u：船舶i的停泊时间；v：船舶i开始占用泊位的位置；c：船舶i离开的时间；m：在时间空间图里，如果船舶i完全在船舶j的左侧，则为1，否则，为0；k：在时间空间图里，如果船舶i完全在船舶j的下面，则为1，否则，为0。

2.3 目标函数

min∑wc-a （1）

目标函数（1）表示船舶总加权在港时间最短。

2.4 约束条件

v-v-s-k-1・S≥0 ？坌1≤i， j≤N， i≠j （3） m+m+k+k≥1 ？坌1≤i， j≤N， i≠j （4）

m+m≤1 ？坌1≤i， j≤N， i≠j （5）

k+k≤1 ？坌1≤i， j≤N， i≠j （6）

p+u=c ？坌1≤i≤N （7）

a≤u≤T-p， 0≤v≤S-s ？坌1≤i≤N （8）

m，k∈0，1 ？坌1≤i， j≤N， i≠j （9）

约束（2）和（3）对决策变量m和k进行了定义。约束（4）～（6）确保了船舶i和j在时间空间图中不会重叠。约束（7）表达了船舶i的完成时间c和停泊时间u之间的关系。约束（8）和（9）定义了决策变量u、v、m、k的可行范围。

3 基于鲁棒优化的连续泊位分配模型

3.1 鲁棒优化原理

鲁棒优化源于鲁棒控制，应用领域很广泛。它的解对于所有不确定参数的实现都具有良好性能，弥补了随机规划和灵敏度分析等方法的不足。该方法对不确定参数不进行分布假定，当它面向最坏情况时，代表一个ญ最保守的结果。如何将其转化为多项式可解的问题是鲁棒优化的关键点。

考虑一般性线性优化问题：

max cx

s.t. Ax≤b

1≤x≤u

假设不确定数据只出现在矩阵A中，而目标函数系数c是确定的。

Soyster[8]方法保证了满足其取值范围内的任何不确定参数的实现条件，故其保护度过高，考虑其缺点，Bertsimas和Sim[9]在线性规划问题中将系数矩阵A中所有不确定参数a看作是一个取值于区间a-， a+对称的随机变量。对于每个约束，引进一个参数Γ在0，J内取值，用来灵活地调整解的保守性水平。实际上，不太可能所有的a都不确定，所以在鲁棒优化模型中，让不确定数据a中的？WΓ」（不大于Γ的最小整数）在区间a-， a+内变化，另一个系数则在a-Γ-？WΓ」， a+Γ-？WΓ」内变化，并且不指定a中哪个？WΓ」在a-， a+内变化。基于以上方法建立鲁棒对应式，可将鲁棒优化模型变成确定性优化问题。

3.2 基于鲁棒优化的连续泊位分配模型

在传统泊位分配模型的基础上，我们考虑船舶作业时间的不确定性，首先增加不确定性时间，再引入保守度的自定义参数Γ及辅助参数ω和r，则可得相应的鲁棒对应式：

u-u-p-m-1・T≥♥ωΓ+r （10）

ω+r≥ （11）

ω≥0 （12）

r≥0 （13）

4 数值实验

对于鲁棒优化模型，为了获得较好的鲁棒性，可以对不确定性因素做进一步的情景分析，但情景向量的设置会导致模型的输入量大大增加，因此从实用的角度考虑，这里我们采用Soyster方法进行处理，对Γ只取整数，而不考虑取小数的情况；当然，这样处理虽然对于建模容易一些，但也增加了解的保守性。做如下测试：

（1）设定Γ=0，此时表示完全不考虑数据的不确定性，得到的结果和传统模型相同。

（2）设定Γ=1，此时模型保守性最强，解得最优值为409。

5 结 论

合理的泊位调度计划能够提高资源的利用率，提升顾客满意度，本论文结合国内外已有研究成果，对不确定性条件下的连续型泊位分配问题进行研究，建立了鲁棒优化的泊位分配模型，通过调节引入参数Γ的值，我们可以根据不同的保守性得到不同船舶作业时间下的鲁棒解。结果表明相对鲁棒优化解降低了约束的保守性，提高了目标函数的最优性，因此可有效地降低决策的风险，在解决实际问题的过程中更为实用。由于MIP模型的局限性，只能 ☻求解小规模的实例集，对于大规模实例求解不太理想。因此如何快速求解鲁棒优化的泊位分配模型是下一步的研究方向。

参考文献：

[4] Imai A， Nishimura E， Papadimitriou S. Corrigendum to “The dynamic berth allocation problem for a container port”[J]. Transportation Research Part B， 2005，39（3）：197.

۵[5] Cordeau J F， Laporte G， Legato P， Moccia L. Models and tabu search heuristics for the berth allocation problem[J]. Transportation Science， 2005，39（4）：526-538.

[6] Wang F， Lim A. A stochastic beam search for the berth allocation problem[J]. Decision Support Systems， 2007，42（4）：2186

-2196.

[9] Bertsimas， A. Thiele. A robust optimization approach to inventory theory[J]. Oprations Research， 2006，54（1）：150-168.