考虑泊位偏好和岸桥移动的泊位岸桥联合调度

梅益群，韩晓龙

上海海事大学 物流科学与工程研究院，上海 201306

近几十年来，各国间的贸易量疯狂增长，带动了全球运输业的快速发展。据统计，目前有60%以上的货物采用集装箱运输，在一些发达国家甚至近100%的占额，集装箱运输的迅猛增长对集装箱码头的运作效率提出了更高的要求。

泊位是码头沿岸线划分的一系列海面区域，用以船舶停靠，以便进行后续的船舶在港工作。岸桥负责进出口集装箱的装卸工作。泊位和岸桥作为集装箱码头的重要资源，如何准确地为到港船只分配泊位以及调用岸桥将直接影响到整个码头的作业效率。

目前对泊位和岸桥的研究主要分为两种，一种是分开独立研究，包括泊位分配问题（berth allocation problem，BAP）、岸桥分配问题（quay crane assignment problem，QCAP）和岸桥调度问题（quay crane scheduling problem，QCSP）等。第二种是两者结合研究，即泊位和岸桥联合调度问题（berth allocation and quay crane assignment problem，BACAP）。

关于第一种分开独立研究，Guan等[1]研究BAP时，考虑船舶等待时间，将时间和泊位离散化，以船舶在港时间之和最小为目标，用树搜索算法进行求解。韩晓龙等[2]在对BAP建模过程中，加入船舶服务时间价值权重，目标求最小化船舶停靠的加权等待时间。Kim等[3]以船舶偏离偏好泊位成本和延迟离港成本之和最低为目标，构建了一种混合整数线性规划模型并求解。Correcher等[4]考虑了码头复杂的空间约束，提出了一种混合整数线性规划公式和一种启发式算法，得到关于引入新变量的BAP最优解。Liu等[5]研究不确定性条件下的泊位分配问题，采用两阶段的鲁棒性优化方法，构建了三个两阶段的鲁棒模型。Jakub等[6]研究了运行时间限制下的BAP算法选择，通过使用一个最小化解决方案质量损失的线性程序，提出一种新的算法选择方式。吴凌霄等[7]首次提出岸桥调度的时间-成本均衡的混合整数优化模型，设计改进的遗传算法用以求解该模型。乐美龙等[8]以岸桥作业量和作业时间均衡调度为目标，建立岸桥调度优化模型，并设计遗传算法求解QCSP。郑红星等[9]考虑岸桥突发故障对岸桥调度方案的影响，构建以岸桥最大完工时间最小为目标的线性规划模型，设计改进的差分进化算法求解。陆书翔等[10]考虑岸桥闲置对码头运作效率的影响，建立最小化岸桥完工时间和闲置时间的多目标规划模型，基于不同的完工时间下界设计不同算法求解。

关于第二种将两者结合研究的方式，赵虎等[11]综合考虑泊位和岸桥实际作业过程，构建考虑能耗的泊位-岸桥联合调度模型，设计遗传算法进行求解。杨劼等[12]在离散泊位的情况下，建立了以总服务成本最小为目标的动态泊位岸桥协调调度模型，设计遗传算法进行求解。吴迪等[13]以平均在港时间和作业成本最小为目标，构建泊位-岸桥多目标联合优化模型，并设计模拟植物生长交替进化算法求解。Türkogulları等[14]考虑连续泊位分配并且采用时不变的岸桥分配策略，建立了混合整数规划模型，利用后处理算法进行求解。彭丽姣等[15]研究连续泊位下的BACAP，建立了以最小化延迟完工任务量、偏离偏好泊位和岸桥移动惩罚成本为目标的整数规划模型。毛敏俐等[16]以最小化船舶在港总服务成本为目标，基于船时效率的岸桥配置的调整规则，设计启发式算法进行求解。田星等[17]同时考虑泊位、岸桥和集卡三种资源的协同调度，以总物流作业成本最小为目标，构建了协同调度的整数线性规划模型。Hsu[18]将泊位离散化，考虑岸桥工作前的移动和设置时间并设置惩罚成本，以总成本最小为目标，建立混合整数规划模型并使用改进的粒子群算法求解。Wang等[19]研究BACAP时考虑碳排放税，以最小化所有任务的总完成延迟和总岸桥运营成本为目标，建立了多目标模型并设计算法求解。胡鸿涛等[20]研究考虑岸桥维护的泊位岸桥联合调度问题，以最小化船在港时间为目标，设计粒子群算法对模型求解。孙彬等[21]考虑码头作业过程中的不确定因素，分别采用ASAP和MAS的策略调度泊位和岸桥，设计了基于CNP协商机制的调度模型，有效提高系统鲁棒性。

综合以上研究发现，现有的文献大多是把船舶到港时间作为已知参数来考虑，优化船舶延期到港时间和船舶延期离港时间等。而本文把船舶到港时间看作变量，考虑船舶抵港后偏离偏好泊位的距离和岸桥移动频数对码头作业效率影响。本文构建了考虑船舶偏离距离的动态泊位-岸桥分配模型和考虑岸桥移动频数的动态岸桥调度模型，求解可得出具体的泊位-岸桥分配计划和岸桥调度方案。

1 问题描述

集装箱港口布局如图1，船舶进港后工作流程如图2，船舶抵港后，港口为其安排泊位，若暂无可用泊位则需等待，产生等待成本。同时需要注意的是，由于堆场存在多个箱区，各船舶的集装箱需要运往不同的箱区，因此各船都有其偏好泊位，若船舶偏离偏好泊位同样也会造成装卸效率的降低。岸桥作为装卸集装箱船的主要工具，需要根据实时工作情况而调动，以满足资源的最大化利用，但同时也要尽量降低移动频数，减少损耗。

图1 集装箱港口布局图Fig.1 Container port layout

图2 船舶进港作业流程Fig.2 Operation flow of inbound ship

本文考虑的是基于连续泊位布局的动态泊位-岸桥联合调度问题。动态泊位分配即船舶的到达时间是可变的。码头和船公司共享运营信息，在船舶到港之前，码头向船公司提供泊位信息，船公司根据船舶的航速（最大最小航速）以及船舶与港口之间距离可预测该船的抵港时间范围。

本文问题分为两阶段进行，第一阶段根据船舶到港的偏好泊位以及船舶的待装卸工作量，对船舶实际靠泊位置与偏好泊位的偏离距离、船舶延迟离港时间以及船舶抵港至靠泊的等待时间设置了惩罚成本，并在约束条件中引入泊位偏离因子表示船舶偏离偏好泊位对船工作量的间接影响，构建以最小化泊位偏离成本、延迟离港成本以及等待成本之和为目标的混合整数规划模型。第二阶段在第一阶段的基础上加入岸桥干扰约束，建立以最小化岸桥移动频数为目标的整数规划模型。结合两模型求解结果可以得到最佳泊位-岸桥联合调度计划。

模型构建基于以下假设：

（1）岸线水深满足所有即将到港船舶的吃水需求。

（2）所有岸桥工作效率、移动速度都相同。

（3）所有到港船舶能在计划期内完成装卸工作。

（4）船舶在抵港之前根据所在位置距离港口远近程度进行抵港时间预报。

（5）船舶预计离港时间已知。

2 模型建立

2.1 第一阶段模型构建

（1）集合和参数

约束条件（4）保证船i工作的连续性；约束条件（5）保证船i在完成所有工作之后才能离港；约束条件（6）表示船i的工作时间范围。

约束条件（7）～（9）表示当船i的实际离港时间超过预期离港时间时，计算超出预期时间的延迟离港时间成本，当船i实际离港时间不超过预期离港时间时，延迟时间成本为0。

2.2 第二阶段模型构建

第一阶段模型的求解可得出各船舶的靠泊情况，第二阶段模型在第一阶段模型的基础上，加入岸桥干扰约束，为各时间段在不同泊位工作的船舶调配岸桥，目标是尽可能少的岸桥移动频数。模型如下。

（1）集合和参数

约束条件（30）～（32）表示船i在t时段的服务岸桥数限制，当船i在t时段不是工作状态则没有岸桥为其服务。

约束条件（35）～（37）表示岸桥q在t时段和t-1时段的对船i服务状态的不同导致的yiqt的变化。

3 算法设计

本文问题为NP-Hard问题，此类问题多采用群智能算法，粒子群算法（PSO）作为一种群智能算法，特点是有记忆性，求解过程中会保留好的解，在分配问题方面具有良好表现，因此针对本文模型设计了改进自适应变异的粒子群算法，在编码过程中，为了保持种群多样性，增加了粒子的自适应变异操作，避免陷入局部最优解。根据种群的适应度方差σ2计算变异概率P，公式如下：

其中，N表示种群规模，Pmax和Pmin分别表示最大和最小变异概率，分别设置为0.4和0.1。

本文算法流程如下：

步骤1设置种群参数（空间维数、种群规模、迭代次数、位置及速度上下界、惯性权重及学习因子），给出适应度函数。

步骤2初始化粒子的位置和速度。

步骤3判断是否满足约束条件，若满足则转至步骤4；否则，转至步骤2。

步骤4计算每个粒子的适应度值，将每个粒子的适应度值与它的个体极值gbest比较，若较优，则替换gbest。将此时的gbest与群体最优zbest比较，若较优，则替换zbest。

步骤5进入迭代，更新粒子的速度和位置，对部分粒子进行自适应变异。

步骤6计算新粒子的适应度值，并更新gbest和zbest。

步骤7若达到最大迭代次数，则算法终止，否则回到步骤5。

3.1 编码方式

一共有n艘船(i=1,2,…,n)，t个时间段，每艘船都有4+t个待求变量。因此，本文粒子群算法的自变量是( 4+t)·n维矩阵，粒子的搜索空间维度为( 4+t)·n。

自变量表示如下：

其中前4行分别表示为每艘船的靠泊位置bi、离港时间td、靠泊时间tb、到港时间ta，后t行表示为每艘船每个时段内的岸桥数。

3.2 种群初始化

粒子群算法所需参数较少，易于实现，主要参数包括：种群规模N、迭代次数G、惯性权重w、个体学习因子c1、群体学习因子c2、位置参数Xmax和Xmin以及速度参数Vmax和Vmin，其中需要注意的是位置参数和速度参数。

位置参数Xmax和Xmin：自变量x的上下限，本文位置参数上限表示为：

1～4行分别表示各船舶的靠泊位置、离开时间、靠泊时间和到港时间的上限，后t行表示每艘船每时间段内岸桥数上限。位置参数下限的表示则与上限相反。粒子位置初始化公式为：

3.3 适应度函数及约束

结合本文模型给出适应度函数：

关于船舶工作量的约束条件：

用泊位偏离因子β来表示船舶偏离对船工作量的影响。

3.4 迭代和变异

在计算完每个粒子的初始适应度值并得到初始的gbest和zbest之后，对每个粒子速度和位置进行迭代更新。在每一次迭代过程中计算群体适应度方差σ2，群体适应度方差的值越小，说明粒子群越聚集，根据式（44）计算P，生成随机数rand∈[ ]0,1，若rand≥P，则对粒子群进行自适应变异。

4 算例分析

为验证本文提出的模型和算法的可行性，结合相关文献以及上海某港的相关运营数据设计算例进行研究。

4.1 算例参数

设集装箱码头连续岸线长1 200 m，岸边共有12台岸桥顺序编号1～12，每台岸桥工作效率相同，均为40 TEU/h，偏离成本按0.1元/(TEU·m-1)。计划期为1天，1天内有8艘船到港。具体参数见表1。

表1 算例参数Table 1 Data of example

4.2 算法性能分析

针对本文提出的模型及算例，设置相关的算法参数：种群规模N=300、迭代次数G=100、惯性权重w=0.729 8、个体学习因子c1=1.490 5、群体学习因子c2=1.490 5。根据算例，船舶数量n=8、时间段按半小时划分t=48，位置参数Xmax和Xmin表示如下：

在不考虑泊位偏离对船工作量影响的前提下（即泊位偏离因子β=0），设置5组不同规模的算例，并分别使用CPLEX和MATLAB编码的粒子群算法求解，来验证算法的有效性。结果如表2，其中，算法求解结果为10次求解的平均值。

表2 CPLEX与本文算法求解结果对比表Table 2 Result comparison of CPLEX and proposed algorithm

当船舶数量为8时，算法收敛图如图3。

图3 算法结果收敛图Fig.3 Convergence diagram of algorithm results

从表2可看出，当船舶数量相同时，CPLEX求解结果和本文算法求解结果误差较小，说明本文设计的改进自适应变异的粒子群算法是可行的。而且随着算例规模的增大，可以发现，CPLEX耗费时间明显比算法所需时间多，由此验证了该算法的高效性。

将该算法求解结果与传统粒子群算法求解结果比较，如表3。

表3 传统粒子群算法与本文算法求解结果对比表Table 3 Result comparison of traditional PSO and proposed algorithm

由表3可看出，不同规模的算例下，本文算法求解结果均优于传统粒子群算法求解结果，证明本文算法求解该问题效果更好。

4.3 算例结果分析

泊位偏离因子β表示船舶偏离给船装卸工作带来的间接影响，本文表现为对船工作量的间接增加。为了更直观地发现β变化对总成本的影响，将总成本分成三部分表示，船舶数量不同时，β值变化对各部分成本的影响如表4所示。

表4 不同泊位偏离因子下的求解结果Tab.4 Results of different berth deviation factors

为了更清楚地反映以上数据的变化，将表4表示为折线图，如图4所示。

从图4可以看出，随着泊位偏离因子β的增加，船舶在港总成本也是不断增大的，其中，β值的变化主要影响船舶的延迟离港成本，这是因为当泊位偏离因子变大，船舶对岸桥的工作量需求增多，而岸桥的工作效率是一定的，因此船舶的在港工作时间就会被延长，从而导致延迟离港。

图4 求解结果走势图Fig.4 Line graph of solution results

观察图4还能发现，当β值从0.15增加到0.2时，规模为12艘船的成本变化幅度比规模为6艘船的大，这是因为规模为6艘时，所有船舶总的装卸工作量较小，远低于所有岸桥的总工作负荷，β值变化所带来的额外工作量可以轻松被各岸桥分担。而当规模增大至12艘时，所有船的总工作量较大，β值变化所带来的额外工作量较大，岸桥资源不变，从而导致等待成本的降低（在港等待时间缩短）和延迟成本的激增（离港时间延长），以充分利用有限的岸桥资源。因此，在实际码头工作中，β值应随着计划期内到港的所有船舶总工作量变化而变化，当总工作量较大时，应当采用较大的β值，以充分利用岸桥资源。

5 结语

相比于其他研究，本文考虑船舶到港时间可变的到港策略，通过船公司与集装箱码头相互间的信息共享，在船舶到港之前，码头及时告知船公司泊位资源情况，船公司再根据泊位信息调整船舶航速控制船舶到港时间，达到节约资源的目的。考虑岸桥干扰约束，同时引入泊位偏离因子β表示船舶偏离间接给码头带来的额外工作量，建立了泊位-岸桥联合调度两阶段模型。使用MATLAB软件设计改进的自适应变异粒子群算法，并设计算例将算法求解结果与CPLEX求解结果比较，证明算法的可行性和优越性。模型求解结果表明，在一定计划期内，岸桥资源不变，船舶偏离偏好泊位会影响码头的总运作成本。预计到港船舶的总工作量较大时，取较大的β值能够缩短船舶的在港等待时间，提高岸桥作业效率，因此在解决该问题时考虑泊位偏离因子β能够帮助码头工作者权衡资源利用和作业成本，做出合理的决策。

通过本文模型的求解，可以得出给定计划期内的泊位-岸桥联合调度计划。然而在实际码头作业过程中，当计划期较长时，泊位和岸桥的实际工作情况会与计划的有所出入。未来的研究可以考虑采用滚动计划法，对于计划期较长的情况，先按照原计划实行一段时间观察成效，若与原计划产生偏差，则取下一个新的计划期进行新的泊位-岸桥联合调度计划。