经典的基础模型

连续动态泊位分配

参考：Berth scheduling by simulated annealing
作者：Kim, K.H., Moon, K.C.

问题描述

连续动态泊位分配问题的特点：（1）岸线是连续的，船舶可以靠泊在岸线的任意位置（2）船舶在规划期内陆续到达。经典的连续动态泊位分配问题就是要去决策到港船舶何时可以靠泊，靠泊在岸线的什么位置，目标是最小化船舶在港时间（粗略估算为锚地的等待时间加上装卸作业时间）或最小化船舶离港延误等。从一个更直观的角度讲，连续动态泊位分配问题可以归结为二维装箱问题的变体，一个二维图上表示出来（两个维度分别对应时间和空间）。

集合和参数

：泊位计划中所考虑的船舶的集合
：码头岸线的长度
：船舶的长度，
：船舶的装卸作业时间，
：船舶的预计到港时间，
：船舶要求的离港时间，
：一个足够大的常数

决策变量和辅助变量

：船舶的船头相对于岸线的位置，
：船舶的开始靠泊时刻，
：辅助变量，如果船舶停靠在船舶的右边则取1，否则取0
：辅助变量，如果船舶在船舶离开泊位之后才开始靠泊则取1，否则取0

模型建立

目标函数最小化船舶离港延误，如果把船舶离港时刻估算为船舶开始靠泊的时刻+装卸作业时间，则目标函数可以写为：

的含义是

约束1：单一船舶合法靠泊位置——任何船舶靠泊的位置都不能使船身超出岸线

约束2：单一船舶的合法靠泊时间——任何船舶最早靠泊时间不超过其提交的预计到港时间

约束3：多船靠泊位置和时间不冲突约束——体现在时空图上就是矩形之间不存在重叠部分

为什么上面三个约束完整刻画任意两个矩形之间合法的位置关系

对于确定的和可以枚举出的所有可能取值：

A 对应时空图中3，5，8的情形
B 对应时空图中1，4，6的情形
C 对应时空图中1，2，3的情形
D 对应时空图中6，7，8的情形
矛盾，但是可以通过这个约束给排除掉
E ，就是A，C交集，对应时空图中3的情形
F ，就是A，D交集，对应时空图中8的情形
G ，就是B，C交集，对应时空图中1的情形
H ，就是B，D交集，对应时空图中6的情形
矛盾，但是可以通过这个约束给排除掉

不难发现A~H的并集就涵盖了两个矩形在平面上所有合法的不重叠的位置关系。

约束4：变量范围约束

离散动态泊位分配

参考：专用泊位租赁与混合泊位分配的联合优化研究
作者：王鑫珏

问题描述

离散动态泊位分配和连续动态泊位分配最大的区别就在于是否允许在岸线的任意位置停靠，不同于连续动态泊位分配，离散动态泊位分配中泊位均为相互独立的空间,且每一个泊位只能挂靠一艘船。要决策的问题变为船舶何时可以靠泊，靠泊在哪一个泊位。目标函数和连续动态泊位分配的常见取法差不多。

集合和参数

：泊位计划中所考虑的船舶的集合
：可用泊位的集合
：船舶的装卸作业时间，
：船舶的预计到港时间，
：船舶要求的离港时间，
：一个足够大的常数

决策变量和辅助变量

：01变量，船舶是否靠泊在泊位，
：船舶在泊位的开始靠泊时刻，
：辅助变量，如果船舶在船舶离开泊位之后才开始靠泊则取1，否则取0

模型建立

目标函数最小化船舶离港延误，如果把船舶离港时刻估算为船舶开始靠泊的时刻+装卸作业时间，则目标函数可以写为：

的含义是

约束1：泊位计划中的每条船舶都得被分配一个泊位

约束2：每条船舶的合法靠泊时间——任何船舶最早靠泊时间不超过其提交的预计到港时间

约束3：多船靠泊时间不冲突约束——体现在时空图上就是矩形之间不存在重叠部分

为什么约束4保证离散动态泊位分配中两条船靠泊时间不冲突

针对船舶，第一种情况：如果它们停在同一个泊位上，那么需要有才能保证不冲突，这个显然是可以办到的；第二种情况：如果它俩不是停在同一个泊位上，那应该要有，假设船舶靠泊在泊位，船舶靠泊在泊位，对于任意非泊位，显然有成立，但在泊位观察到有，啊？怎么没有限制住？别慌，进一步分析，只要则必然违反约束3当中的后两条约束，所以当它俩不在一个泊位时一定有。

约束4：变量范围约束

实验设计思路

元启发式算法的性能评估实验设计

参考：Integrated planning of berth allocation and vessel sequencing in a seaport with one-way navigation channel
作者：Baoli Liu, Zhi-Chun Li, Dian Sheng, Yadong Wang

元启发式算法的性能评估实验

算法性能评估就分为两个方面：（1）求解时间（2）当前最优解目标函数值和最优解目标函数值的下界之间的GAP。但是元启发式算法在求解的过程当中本身没有办法给出问题的一个比较紧的界，所以要评价指标（2）我们就必须找一个“桥梁”。常用的“桥梁”包括——线性松弛模型、拉格朗日松弛模型。这篇文章用的是线性松弛作为“桥梁”，也就是把线性松弛模型的最优解目标函数值作为原问题最优解目标函数值的一个估计下界，然后去评估元启发式得到的解和这个下界之间存在多大的偏差。