离散泊位布局下的泊位岸桥动态协调调度

杨 劼，高 红，刘 巍

1.大连海事大学 交通运输管理学院，辽宁 大连 116026

2.大连海事大学 数学系，辽宁 大连 116026

1 引言

泊位和岸桥作为集装箱码头的主要稀缺资源，其调度问题直接影响着顾客满意度和码头的运营成本。泊位计划和岸桥计划的制定相互依赖、相互影响。合理的岸桥计划能够保证泊位计划的顺利实施，避免因岸桥调配不合理而导致的船舶滞港、压船、压货等现象；另一方面，合理的泊位计划能够充分利用岸桥资源，避免岸桥资源的闲置或浪费。因此，充分考虑泊位调度和岸桥分配之间的相互关系，协调调度码头资源，符合码头作业的实际情况，具有十分重要的实践意义。

泊位调度问题按照码头泊位布局的空间属性可以分为连续泊位调度、离散泊位调度和混合泊位调度；按照船舶抵港的时间属性可以分为动态调度和静态调度。Bierwirth和Meisel[1-2]综述了这两种属性任意组合下的泊位和岸桥调度的研究成果。本文研究基于离散泊位布局的泊位岸桥动态协调调度，具体是针对离散泊位，在一个计划周期内，为动态到港的船舶安排停泊时间和停泊泊位，并为每艘船舶分配一定数量的岸桥以完成船舶装卸任务。国内外学者对离散泊位布局下的泊位岸桥协调调度进行了大量研究。Liang等[3-4]以最小化船舶总的在港时间与延迟时间之和为目标建立数学模型。船到船的直接转运能够减少堆场的使用，从而加快船舶的处理速度，Liang等[5]考虑了船舶之间货物的转运，建立了以船舶在港时间、延迟时间及等待转运时间之和最小为目标的模型，并设计了分阶段求解算法确定泊位和岸桥调度计划。以上是从操作层面考虑泊位岸桥调度问题，Giallombardo等[6]从战术层面上进行资源调度，旨在一个较长的计划周期内均衡码头收益和顾客满意度，为码头管理者在与船公司的协商谈判中提供决策支持，同时提出了两阶段启发式算法对模型求解，第一阶段采用禁忌搜索算法安排泊位计划，第二阶段用数学规划方法更新岸桥计划。Lalla-Ruiz等[7]继续从战术层面解决集装箱码头泊位岸桥调度问题，并设计了偏随机密钥遗传算法求解模型。杨春霞等[8]以最小化船舶在港时间和码头生产成本为目标建立了码头资源调度优化模型，但模型没有考虑时间与岸桥资源之间的约束，并且在建模中假设船舶装卸时间是固定的。李明伟等[9]假设船舶装卸时间与分配的岸桥数相关，以平均集卡运距和所有船舶平均在港时间最小为目标建立了双目标协调调度模型，并采用混沌云粒子群算法寻求模型的满意解。

以上研究大多立于码头管理者的角度，以最小化船舶在港时间为目标建立模型。然而对于船公司来说，船舶到港后在完成装卸任务的同时应使生产成本最小。本文从船公司的角度出发，以最小化船舶总的服务成本为目标提出泊位岸桥动态协调调度模型。

泊位岸桥调度问题的求解是个NP难题，目前常用的求解方法主要是进化算法和启发式算法，包括遗传算法[10-12]、粒子群算法[13]、禁忌搜索算法[14]、文化基因算法[15]等。采用进化算法求解能够找到理论最优解，然而搜索空间将随着船舶和泊位数量的增加迅速膨胀，从而出现组合爆炸问题。启发式算法的设计则依赖于具体的问题，容易陷入局部最优。本文基于具体的问题设计了改进遗传算法对模型求解。

2 泊位岸桥动态协调调度模型

2.1 问题描述与模型假设

通常情况下，船舶在抵港前就将相关信息（包括船型、即将到港时间、载箱量和预计离港时间等）预报给即将挂靠的码头，码头工作人员依据这些信息以及码头设备状态为船舶制定泊位和岸桥计划，船舶抵港后便依据该计划进行装卸作业直至船舶离港。如图1给出了集装箱船舶在码头作业的流程图。船舶抵港后，若为其分配的泊位空闲，则船舶进入泊位等待为其分配岸桥，否则需在锚地等待泊位空闲；船舶靠泊后，若为其分配的岸桥可用，则开始船舶装卸作业，否则需在泊位等待岸桥可用；船舶装卸作业完成后，则立即离港。显然，泊位计划和岸桥计划共同影响着整个码头生产作业的效率，任一计划的单独最优往往会因另一计划未能与其完美对接而无法顺利实施。泊位岸桥协调调度就是充分考虑泊位调度和岸桥分配之间相互关联、相互影响的关系，使二者共享参数和变量，确定到港船舶的最优停泊泊位、停泊顺序以及分配给船舶的岸桥数，从而达到系统整体最优状态。

本文基于离散型泊位布局进行研究，即整个岸线被分割成若干个泊位，同一时刻每个泊位最多可停靠一艘船舶，且每艘船只能停泊在一个泊位内。由于各泊位的长度及其前沿水深不尽相同，因此，在制定船舶泊位计划时要充分考虑船舶的安全船长和安全水深因素。

具体模型是基于以下假设建立的：（1）每艘船都必须且只能靠泊一次；（2）每艘船都有一个偏好泊位，当船舶停泊在偏好泊位时集卡的运输距离最短；（3）船舶装卸时间与分配给该船的岸桥数成反比；（4）在船舶装卸过程中作业的岸桥数以及具体的岸桥不变；（5）岸桥开始作业后，在装卸任务结束前不能中途停止；（6）不考虑多个岸桥同时作业时相互干扰对岸桥工作效率的影响。

假设（1）和（2）是泊位调度的基本假设。本文并不考虑半集装箱船舶，因此船舶抵港后没有移泊的必要性，而从船公司的角度，移泊会增加移泊费用和拖轮费用，为了使成本最小化，船方并不希望船舶移泊。考虑码头工作人员预先制定的堆场计划以及船舶可停泊的泊位，每艘船必然都至少有一个偏好泊位，当船舶停泊在偏好泊位时，泊位到堆场的集卡运输距离最短。假设（3）和（6）体现了岸桥资源对泊位决策的影响，是模型的理想假设。对船舶装卸时间的假设大致可分为三类：船舶装卸时间是固定的、船舶装卸时间与停靠位置相关、船舶装卸时间与岸桥（数量或效率）相关。本文假设船舶装卸时间与分配的岸桥数成反比，能够在一定程度上更接近码头实际生产情况。假设（4）和（5）避免了码头生产作业中岸桥频繁调度，有利于减少岸桥作业相互干扰。由于很难对岸桥间的干扰进行量化，因此假设（6）排除了干扰对模型的影响。

2.2 模型建立

图1 集装箱船舶在码头作业流程图

模型涉及的参数：V为计划周期内到港的船舶总数；B为码头可用的泊位数；T为计划周期；Q为码头可用的岸桥数；ai为船舶i的预计到港时间；bi为船舶i的偏好泊位；di为船舶i的预计离港时间；VLi为船舶i的安全船长（含横向安全预留距离）；VDi为船舶i的安全水深（含纵向安全预留距离）；BLj为泊位j的长度；BDj为泊位j的前沿水深；wi为装卸船舶i所需的岸桥总台时数为装卸船舶i所需的最小岸桥数为装卸船舶i所需的最大岸桥数；c1为船舶到港后等待靠泊的单位时间成本；c2为船舶停泊位置远离偏好泊位的单位距离成本；c3为船舶推迟离港的单位时间成本；c4为单位岸桥单位时间装卸成本；M为极大正数。

涉及的决策变量：Bi为船舶i的停泊泊位；Oi为船舶i的停泊顺序；qi为分配给船舶i的岸桥数。

涉及的从属变量：Ei为船舶i的停泊时间；Di为船舶i的离港时间；Uit=1表示船舶i在t时刻被服务，否则Uit=0；Uijk=1表示船舶i在j泊位按次序k被服务，否则Uijk=0。

基于以上模型假设及变量设置，本文建立泊位岸桥动态协调调度模型如下：

其中，目标函数（*）表示最小化船舶总的服务成本。式（1）表示船舶到港后才能靠泊；式（2）和式（3）表示船舶只能停泊在满足其安全船长和安全水深的泊位；式（4）表示每艘船有且只有一次靠泊机会；式（5）表示一个泊位至多只能同时服务一艘船；式（6）定义了船舶的服务顺序；式（7）避免了同一泊位服务的船舶在服务时间上的冲突；式（8）表示任意时刻作业的岸桥数不超过码头岸桥总数；式（9）表示必须满足每艘船舶装卸所需的岸桥台时数；式（10）限制了分配给每艘船舶的岸桥数；式（11）保证了连续的船舶装卸作业；式（12）定义了船舶离港时间；式（13）定义了船舶推迟离港的时间；式（14）～（16）定义了决策变量和从属变量的取值范围。

3 模型求解

鉴于模型约束较多，在算法设计中尽可能地将约束条件嵌入算法结构，从而降低模型求解难度。本文结合具体问题，设计遗传算法对模型求解，具体步骤如下。

3.1 个体编码及种群初始化

每个种群个体用3组染色体表示，分别对应于模型中的3个决策变量，即船舶停泊泊位、停泊顺序以及分配给船舶的岸桥数。3组染色体均采用自然数编码。例如，图2中，船舶4停泊在2号泊位，停泊顺序为4，分配的岸桥数为4台。

图2 种群个体编码

个体子染色体1的每个基因值分别从满足各个船舶安全船长和安全水深的泊位中产生，这满足了约束条件（2）、（3）；子染色体2的基因值是自然数1到V以任意顺序排成的一个序列，子染色体3的每个基因值分别从满足各船舶岸桥数量约束的区间中产生，这两组子染色体的生成规则满足了约束条件（4）、（5）、（10）。这样生成的初始种群虽然就单个基因而言都是合理的，但是组合起来几乎不可能组成可行解，尤其是随着问题规模的扩大，必然出现大量的约束冲突。因此，有必要对生成的种群个体进行基因调整以满足所有的约束条件。

逐时刻基因调整：

为了更直观地显示各船舶的资源调度情况，通常采用如图3所示的示意图表示模型的解，其中矩形表示船舶，矩形中的数字表示船舶编号及分配给船舶的岸桥数，矩形的位置表示船舶的靠泊顺序。矩形的长表示船舶的安全船长，宽表示船舶装卸时间。考虑到离散泊位布局的特点，这些矩形块的排列结果与矩形的长无关，因此图3中的矩形均设置为等长。矩形的宽（船舶装卸时间）由约束条件（9）、（11）、（12）确定，即：

于是泊位岸桥调度问题可以形象地看作矩形块在

图3 离散泊位下泊位岸桥调度结果示意图

泊位-时刻空间内的排队问题。对于生成的个体，用式（18）计算出各船舶具体的靠泊时间和离港时间，这满足了约束条件（1）、（6）、（7）。

这样生成的初始解只需要满足约束条件（8）即为可行解，否则为不可行解。因此有必要对初始解进行基因调整，使得个体满足时间T和岸桥Q之间的关系。具体采用逐时刻基因调整策略来突破T-Q关系冲突，步骤如下：

步骤1对所有船舶按照由公式（18）计算得到的靠泊时间（升序排列）重新编号。

步骤2依次对每一艘船舶构建与其有T-Q关系冲突的船舶集合，并对最晚靠泊的船舶以及与其共享泊位单元的后来船舶进行逐时刻后移，重复这一过程使得任意时刻总服务岸桥数量不超过码头岸桥总数。

步骤3依据新的船舶靠泊时刻更新船舶靠泊顺序。

通过逐时刻基因调整方法，能够保证个体的可行性。因此在种群的迭代过程中，也采用该方法对不可行解进行修复。

3.2 适应度函数

遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数为依据，利用种群个体的适应度来进行搜索。适应度函数的构建要能够反映一个解的优劣。基于本文模型的目标函数以及适应度函数非负性要求，建立适应度函数如下：

其中，f(x)为模型的目标函数，fmax为种群个体中的目标函数值最大值。

3.3 选择操作

本文采用精英选择+轮盘赌的策略对种群个体进行选择。首先，对种群个体依据其适应度值降序排列；其次，选择精英个体，根据预设的精英数量EN，选择前EN个个体直接放入交配池中；最后，采用轮盘赌选择策略从整个种群中选择个体补齐交配池中的种群数量。

该选择策略能够有效的避免最优个体丢失，加快种群收敛速度。

3.4 交叉和变异操作

由于种群个体由3组染色体共同表示，且3组染色体分别表示的决策变量需满足不同的要求。因此有必要对3组染色体分别进行交叉和变异操作。

（1）子染色体1和子染色体3

子染色体1和子染色体3分别表示船舶的停泊泊位及分配给船舶的岸桥数，各基因的取值相互独立，因此采用单点交叉法对这两组染色体分别进行基因重组，即在染色体中随机选择一个交叉点，交换两个父代染色体中的部分基因。对两组染色体的基因变异采用单点变异法，随机选择一个变异点，重新生成新的基因值。

（2）子染色体2

子染色体2表示船舶的停泊顺序，各基因的取值为1到V的自然数且不能重复，采用两点交叉对该染色体进行基因重组，即在染色体中随机选择两个交叉点，两个交叉点之间的区域即为交叉区域，交换两个父代染色体交叉区域的基因。由于各基因之间的相互关系，交叉后的子代往往会不满足约束条件（4）、（5），需要进一步调整基因的取值。如图4所示，两个父代交叉后得到两个中间代，均不符合船舶靠泊要求，其中中间代1中，O1=O3=1，O5=O7=6，中间代2中，O1=O5=2,O2=O4=4。具体的基因调整策略分为3步：（1）对比中间代与其相应父代的交叉区域的基因值，确定中间代缺失的基因和重复的基因；（2）在中间代交叉区域外，查找重复基因并确定其位置；（3）依次用中间代缺失的基因去替代上一步确定的基因。图4中，在交叉过程中，父代1交叉区域的基因用1、5、6替换了原来的5、4、2，于是中间代1中缺失了基因4、2，重复了1、6，通过调整策略，用基因4、2分别替换交叉区域外的基因1、6，最终得到子代1，对中间代2的基因调整同理。

图4 两点交叉规则

表2 两种算法求解结果对比

同样为了保证子染色体2的变异子代符合靠泊要求，采用两点变异，即随机选择两个变异点，交换两点处的基因值。

对于交叉和变异操作过程中产生的不可行解采用逐时刻基因调整策略（见3.1节）进行修复。依次对种群个体进行选择、交叉和变异操作，并不断迭代至迭代次数达到预先设定的值，算法结束。

4 数值实验

基于某集装箱码头的基础数据设计案例，以验证本文模型及算法的可行性和有效性。该码头具有离散型泊位布局，岸线长1 200 m，拥有4个泊位，12台岸桥，1#～4#泊位长度分别为200 m、300 m、400 m、400 m，到港船舶按照船舶等级分为小船、中船和大船，船舶可靠泊泊位依据船舶等级确定，即小船可停靠1#～4#泊位，中船可停靠2#～4#泊位，大船可停靠3#～4#泊位。以72 h为一个计划周期随机生成6个算例（包含的船舶数分别为10、12、14、16、18、20），且每个算例中包含不同等级船舶的比例分别为小船30%，中船50%，大船20%，船舶到港时间ai～U[1,60]，船舶服务成本参数设为c1=150,c2=100,c3=200,c4=150。其他相关参数设置如表1所示。本文算法采用MATLAB R2009a，m脚本语言编程，在英特尔Core i3 2.53 GHz双核处理器，2 GB内存和Win 7操作系统下完成实验。算法基本参数通过实验选取：种群规模为200，迭代次数为1 000次，交叉和变异概率分别为0.8和0.2，精英数为40。

表1 船舶参数设置

港口工作人员在资源调度过程中通常依据先到先服务原则，采用人工贪婪算法为船舶分配泊位及岸桥。贪婪算法又叫步步最优算法，即最先到达的船靠泊在最先可用的泊位，并在船舶装卸要求等约束条件下分配最多的岸桥。表2给出了每个算例下本文算法与贪婪算法求解结果的对比情况。

由表2可知，针对随机生成的6个算例，本文提出的模型和算法在船舶在港时间及船舶服务成本方面均比人工贪婪算法下获得的结果更优，并且随着船舶数量的增加，本文模型及算法的优势更加明显。当船舶数量为20时，本文算法较人工贪婪算法在船舶在港时间上改善了39.60%，在船舶服务成本方面改善了29.18%。

5 结论

随着集装箱码头运输需求的日益增长，港口间的竞争越发激烈，合理配置港口稀缺资源以提高港口竞争力成为推动港口未来发展的重要手段。本文对离散泊位布局下的泊位岸桥协调调度问题进行了研究，建立了基于非线性整数规划的泊位岸桥协调调度优化模型，并设计了改进的遗传算法对模型求解。运用本文算法不仅能够简化模型求解难度，而且较人工贪婪算法更好地改善了船舶在港时间和船舶服务成本，能够为集装箱码头的资源调度优化提供科学合理的解决方案和决策依据。

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

[2]Bierwirth C，Meisel F.A follow-up survey of berth allocation and quay crane scheduling problems in container terminals[J].European Journal of Operational Research，2015，244（3）：675-689.

[3]Liang C，Lin L，Jo J.Multiobjective hybrid genetic algorithm for quay crane scheduling in berth allocation planning[J].International Journal of Manufacturing Technology and Management，2009，16（1/2）：127-146.

[4]Liang C，Guo J，Yang Y.Multi-objective hybrid genetic algorithm for quay crane dynamic assignment in berth allocation planning[J].Journal of Intelligent Manufacturing，2011，22（3）：471-479.

[5]Liang C，Hwang H，Gen M.A berth allocation planning problem with direct transshipment consideration[J].Journal of Intelligent Manufacturing，2012，23（6）：2207-2214.

[6]Giallombardo G，Moccia L，Salani M，et al.Modeling and solving the tactical berth allocation problem[J].Transportation Research Part B：Methodological，2010，44（2）：232-245.

[7]Lalla-Ruiz E，González-Velarde J L，Melián-Batista B，et al.Biased random key genetic algorithm for the tactical berth allocation problem[J].Applied Soft Computing，2014，22：60-76.

[8]杨春霞，王诺.基于多目标遗传算法的集装箱码头泊位—岸桥分配问题研究[J].计算机应用研究，2010，27（5）：1720-1722.

[9]李明伟，康海贵，耿静，等.基于多目标混沌云粒子群算法的泊位-岸桥分配研究[J].水运工程，2014（1）：90-96.

[10]Imai A，Chen H C，Nishimura E，et al.The simultaneous berth and quay crane allocation problem[J].Transportation Research：Part E Logistics&Transportation Review，2008，44（5）：900-920.

[11]Lee D，Wang H Q.Integrated discrete berth allocation and quay crane scheduling in port container terminals[J].Engineering Optimization，2010，42（8）：747-761.

[12]毕娅，李文锋.集装箱港口集群下多港口多泊位联合调度方法[J].计算机应用，2012，32（2）：448-451.

[13]张红菊，乐美龙.基于多目标粒子群算法的泊位-岸桥分配研究[J].武汉理工大学学报，2012，34（2）：59-64.

[14]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（4）：327-336.

[15]He J.Berth allocation and quay crane assignment in a container terminal for the trade-off between time-saving and energy-saving[J].Advanced Engineering Informatics，2016，30（3）：390-405.