0 引言

码头资源调度优化一直是集装箱码头管理的难点问题。泊位和岸桥作为码头的主要稀缺资源，其调度问题是影响码头服务水平的重要因素。合理安排船舶的靠、离港的泊位计划以及装卸计划，有利于提高码头资源的利用率，扩大码头通过能力。在实践中，泊位调度和岸桥调度是两个相互关联的问题。泊位调度计划需要岸桥资源的配合才能顺利完成，反过来岸桥计划要以现有的泊位计划为载体。具体地说，一方面，泊位计划依赖于岸桥的分配，船舶装卸时间与为其分配的岸桥数相关；为船舶分配较多的岸桥能够有效地提高船舶装卸效率，然而岸桥资源有限，若分配不合理有可能导致船舶滞港、压船、压货等现象。另一方面，泊位计划也影响着岸桥的分配，泊位分配不合理有可能导致部分岸桥闲置、资源浪费或者岸桥频繁调度、作业冲突。因此，简单的单独调度很难使泊位和岸桥构成的系统达到整体最优，而泊位岸桥的协调调度问题是将泊位和岸桥资源联系起来进行统筹协调，充分考虑泊位调度和岸桥分配之间相互依赖、相互影响的关系，避免了单独调度的局限性，能够有效地减少船舶在港时间，降低船舶总的服务成本。

对泊位岸桥协调调度问题的研究主要在模型建立和算法设计两方面。在建模方面，由于码头调度是一个复杂的系统，集装箱码头作业过程中，需要泊位、岸桥、集卡及堆场等装卸资源协同配合，才能使码头的效率达到最优，因此如何建立一个更接近码头操作实际情况的模型，避免模型过于理想化是建模的重点和难点。在求解算法的设计方面，随着船舶和泊位数量的增加，模型解的搜索空间迅速膨胀，因此设计一个快速高效的算法以获得更优的解也是研究的重点。

国内外学者对泊位岸桥协调调度问题已经进行了一定的研究：韩骏等^[1]假设船舶装卸时间与停泊位置相关，以所有船舶总在港时间最小为目标建立了协调调度模型，该模型允许服务同一船舶的岸桥在不同时刻开始服务；考虑到调度方案对客户满意度的影响，谭盛强等^[2]建立了基于船舶服务优先级的多目标混合整数规划模型，以最小化泊位偏离惩罚、推迟离港惩罚、船舶总在港时间、靠泊等待时间为目标，设置不同的惩罚系数来满足不同客户的满意程度；李明伟等^[3]针对离散型泊位，以平均集卡运距和所有船舶平均在港时间最小为目标建立了多目标协调调度模型，并采用混沌粒子群算法进行求解；Meisel等^[4]在建模中充分考虑了岸桥间相互干扰导致的生产率损失，并采用吱呀轮优化(Squeaky Wheel Optimization, SWO)算法求解；Zhang等^[5]假设在装卸过程中，分配给船舶的岸桥数量以及具体的岸桥均是可变的，提出了基于拉格朗日松弛和次梯度优化的算法对模型求解；He^[6]为了促进集装箱码头的节能减排，建立了双目标规划以均衡船舶推迟离港的成本和岸桥能耗；Karam等^[7]考虑了码头有限的集卡资源，以最小化船舶平均服务时间为目标对泊位、岸桥和集卡进行了协调调度；Bierwirth等^[8]针对集装箱码头泊位岸桥调度问题进行了综述。

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

本文主要研究集装箱码头泊位岸桥的协调调度问题，具体是指：针对连续泊位，在一个计划周期内，为动态到港的船舶安排停泊时间和停泊位置，并为每艘船舶分配一定数量的岸桥以完成船舶装卸任务。综合考虑船舶到港后等待停泊的时间成本、远离偏好泊位的距离成本、推迟离港的时间成本以及岸桥装卸成本4个方面建立模型，使得船舶总的服务成本最小；同时克服传统遗传算法局部搜索能力较差的缺陷，用改进的遗传算法求解模型。

1 泊位岸桥协调调度模型 1.1 模型假设

本文模型基于以下假设建立：1) 每条船都必须且只能靠泊一次；2) 每条船都有一个偏好泊位，当船舶停泊在偏好泊位时集卡的运输距离最短；3) 船舶装卸时间与分配给该船的岸桥数成反比；4) 在船舶装卸过程中作业的岸桥数以及具体的岸桥不变；5) 岸桥开始作业后，在装卸任务结束前不能中途停止；6) 不考虑多个岸桥同时作业时相互干扰对岸桥工作效率的影响。假设条件1)是泊位调度的基本要求。假设条件2)考虑了堆场距离对码头装卸效率的影响。在船舶抵港前，码头会根据船舶泊位计划预先将出口集装箱集中堆放到堆场，并建立进口集装箱堆存计划，以加速船舶装卸作业。因此在制定泊位计划时应兼顾考虑集卡的运输距离，使船舶停泊位置尽量靠近其偏好泊位，这样才能尽可能缩短集卡运输距离，提高码头运作效率。假设条件3)体现了岸桥分配对泊位决策的影响。假设条件4)~6)是对岸桥分配的要求。

1.2 模型建立

模型涉及的参数如下：L为码头岸线长度；V为计划周期内到港的船舶总数；i为船舶编号；T为计划周期；一个计划周期被划分成等长度的时间段，以1小时为单位，t为时间段编号；Q为码头可用的岸桥数；a_i为船舶i的预计到港时间；b_i为船舶i的偏好泊位；d_i为船舶i的预计离港时间；l_i为船舶i的长度(包括船舶安全距离)；w_i为装卸船舶i所需的岸桥总台时数；q_i为装卸船舶i所需的最小岸桥数；q_i为装卸船舶i所需的最大岸桥数；c₁为船舶到港后等待靠泊的单位时间成本；c₂为船舶停泊位置远离偏好位置的单位距离成本；c₃为船舶推迟离港的单位时间成本；c₄为单位岸桥的单位时间装卸成本；M为极大的正数。

涉及的决策变量如下：E_i为船舶i的停泊时间；B_i为船舶i的停泊位置；q_i为分配给船舶i的岸桥数。

从属变量D_i为船舶i的离港时间；U_it=1表示船舶i在t时刻被服务，否则U_it=0。

于是，泊位岸桥协调调度模型可以表示为：

$\begin{array}{l} \left[{{\rm{Model}}\;{\rm{1}}} \right]\\ \min \;\;f = \sum\limits_i {\left[{{c_1}\left( {{E_i}-{a_i}} \right) + {c_2}\left| {{B_i}-{b_i}} \right| + } \right.} \\ \left. {\;\;\;\;\;\;\;\;\;\;\;\;\;{c_3}{{\left( {{D_i}-{d_i}} \right)}^ + } + {c_4}{q_i}\sum\limits_t {{U_{it}}} } \right] \end{array}$

(1)

${\rm{s}}{\rm{.t}}{\rm{.}}\;\;{E_i} \ge {a_i};\forall i$

(2)

${B_i} + {l_i} \le L;\forall i$

(3)

$\begin{array}{l} 1 \le \left( {{E_i} \ge {D_j}} \right) \vee \left( {{D_i} \le {E_j}} \right) \vee \left( {{B_i} \ge {B_j} + {l_j}} \right) \vee \\ \;\;\;\;\;\left( {{B_i} + {l_i} \le {B_i}} \right) \le 2;\forall i < j \end{array}$

(4)

$\sum\limits_i {{q_i} \times {U_{it}} \le Q;\forall i} $

(5)

$\sum\limits_t {{q_i} \times {U_{it}} \le {w_i};\forall i} $

(6)

$\underline {{q_i}} \le {q_i} \le {{\bar q}_i};\forall i$

(7)

${E_i} + M\left( {{U_{it}}-1} \right) \le t \times {U_{it}} \le {D_i}-1;\forall i, t$

(8)

${D_i} = {E_i} + \sum\limits_t {{U_{it}};\forall i} $

(9)

${\left( {{D_i}-{d_i}} \right)^ + } = \max \left\{ {{D_i}-{d_i}, 0} \right\};\forall i$

(10)

${B_i} \ge 0, \forall i$

(11)

${U_{it}} \in \left\{ {0, 1} \right\}, \forall i, t$

(12)

${q_i} \in \left\{ {1, 2, \cdots, Q} \right\};\forall i$

(13)

其中目标函数(1)表示最小化船舶总的服务成本。式(2)表示船舶到港后才能靠泊；式(3)表示所有船舶必须停靠在码头岸线内；式(4)避免了任意两船在停泊时间和停泊位置上有重叠；式(5)表示任意时刻作业的岸桥数不超过码头岸桥总数；式(6)表示必须满足每条船舶装卸所需的岸桥台时数；式(7)限制了分配给每条船舶的岸桥数量；式(8)表示船舶装卸作业必须是连续的，作业过程中间不能停顿；式(9)定义了船舶离港时间；式(10)定义了船舶推迟离港的时间；式(11)~(13)定义了决策变量取值范围。

2 模型求解

本文设计了改进的遗传算法来求解泊位岸桥协调调度模型，克服了传统遗传算法局部搜索能力较差、极易陷入局部最优的缺点。

2.1 个体编码和种群初始化

如图 1所示，本文用3个决策变量E_i、B_i、q_i描述船舶i的状态，每个种群个体用两组染色体表示，其中：子染色体1对应于船舶停泊时间和分配给该船的岸桥数，子染色体2对应于船舶停泊位置。子染色体1采用自然数编码，子染色体2采用实数编码。

依据约束条件(6)、(8)、(9)、(12)，决策变量D_i和U_it可以表示为：

$\begin{array}{l} {D_i} = {E_i} + \left[{{\omega _i}/{q_i}} \right]\\ {U_{it}} = \left\{ \begin{array}{l} 1, \;\;\;{E_i} \le t \le {D_i} -1\\ 0, \;\;\;其他 \end{array} \right. \end{array}$

依据约束条件(2)、(3)、(7)、(11)、(13)可得决策变量E_i，B_i，q_i的搜索区间分别为$\left[{{a_i}, T-\left\lceil {{\omega _i}/{{\bar q}_i}} \right\rceil } \right], \left[{0, L-{l_i}} \right], \left[{\underline {{q_i}} .{{\bar q}_i}} \right]$；所有船舶必须在计划周期内离港，即D_i≤T，于是有：

${E_i} + \left\lceil {{\omega _i}/{q_i}} \right\rceil \le T$

(14)

生成初始种群后，若种群个体中船舶i不满足约束条件(14)，则为其分配最多的岸桥数，即令${q_i} = {{\bar q}_i}$，于是种群个体只需要满足约束条件(4)、(5)即为可行解，否则为不可行解。

2.2 适应度函数

在遗传算法进化后期种群趋于稳定，个体间的差异变小，群体进化能力基本丧失，这导致算法过早收敛于局部最优解。为了使群体继续保持进化能力，本文在种群中始终保持一定数量的不可行解，这与通常采用的在种群进化后期增大变异概率所起的作用一样，都是为了增大个体间差异，增加种群多样性，促进新个体的产生，从而使算法跳出局部最优解。为了避免盲目选择，需要对不可行解进行评价，使得保留下来的不可行解具有更大的潜力在交叉、变异操作中生成可行解。常用的评价方法如层次分析法、德菲尔法及模糊综合评价法等依赖于专家的主观判断，且难以实现定性知识的定量化。可拓关联函数是可拓学的一个基本概念和方法^[14]，通过可拓关联度定量、客观地表征事物具有某种性质的程度及其量变与质变的过程，从而避免主观因素的过分干预^[15]。本文建立可拓关联函数，以关联度度量不可行解违反约束的程度。

1) 个体关于约束条件(4)的关联函数。

离散函数g_{i_j}(x)=(E_i≥D_j)∨(D_i≤E_j)∨(B_i≥B_j+l_j)∨(B_i+l_i≤B_j)的取值为0，1，2，且函数值取0时个体为不可行解。因此，建立离散关联函数如下：

${k_{i\_j}}\left( x \right) = \left\{ \begin{array}{l} -1, \;\;\;\;\;{g_{i\_j}}\left( x \right) = 0\\ 0, \;\;\;\;\;\;\;其他 \end{array} \right.$

2) 个体关于约束条件(5)的关联函数。

离散函数${l_t}\left( x \right) = \sum\limits_i {{q_i} \times {U_{it}}} $的值域较大，且函数值大于Q时个体为不可行解。因此，建立正域为有限区间[0, Q]且最优点处于区间右端点的简单关联函数如下：

${k_t} = \left\{ \begin{array}{l} 0, \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{l_t}\left( x \right) \in \left[{0, Q} \right]\\ 1 -{l_t}\left( x \right)/Q, \;\;\;{l_t}\left( x \right) > Q \end{array} \right.$

由于在模型中约束条件(4)、(5)同等重要，于是个体关于约束的综合关联函数记作：

$h\left( x \right) = \sum\limits_{i < j} {{k_{i\_j}}\left( x \right)} + \sum\limits_t {{k_t}\left( x \right)} $

对可行解和不可行解分别建立适应度函数(15)和(16)：

$fitnes{s_1}\left( x \right) = {f_{\max }}-f\left( x \right)$

(15)

$fitnes{s_2}\left( x \right) = h\left( x \right)-{h_{\min }}$

(16)

其中:f(x)为模型的目标函数，f_max为可行解的目标函数值最大值，h_min为不可行解的综合关联度最小值，fitness₂(x)越大表明不可行解违反约束的程度越小。

2.3 选择操作

本文采用精英选择+轮盘赌的策略对种群个体进行选择。首先，分别对可行解和不可行解依据适应度值降序排列；其次，选择精英个体，在可行解中选择适应度大的个体放入交配池中，若可行解数量小于预设的精英数量，则在不可行解中选择适应度大的个体补足精英数量；然后，保留不可行解，选择适应度大的不可行解放入交配池中(按顺序选择，避免与精英个体中的不可行解重复)，保证种群中至少有一定比例的不可行解，若不可行解数量不足，则在所有不可行解中用轮盘赌选择补齐；最后，在整个种群中用轮盘赌选择策略补齐种群数。

该选择策略在避免最优个体丢失的同时，保证了至少一定比例的不可行解被选择，能够有效地维持种群多样性。

2.4 交叉和变异操作

交叉操作决定了被选择的个体如何进行基因交换。对选择出的父代个体以交叉概率进行实值交叉，即：

${{x'}_i} = x_i^1 + {r_i}\left( {x_i^2-x_i^1} \right)$

其中:x′_i是子代的第i个决策变量，x_i¹, x_i²分别为两个父代的第i个决策变量，r_i为[0, 1]上均匀分布的随机数。

采用高斯变异，随机选择父代个体的一个变量x_i进行高斯扰动，即：

${{x'}_i} = {x_i}\left( {1 + {\delta _i}} \right)$

其中:x′_i是子代的第i个决策变量，δ_i为服从均值为0、方差为1的髙斯分布的随机数。

注意  个体的子染色体1在交叉、变异操作后要进行取整运算。

种群个体经过选择、交叉和变异的不断迭代最终收敛至最优解。算法设定当迭代次数达到预先设定的值时，算法终止。改进遗传算法的流程如图 2所示。

3 数值实验

本文对改进的遗传算法使用Matlab R2009a，m脚本语言编程，在英特尔Core i3 2.53 GHz双核处理器，2 GB内存和Windows 7操作系统下完成实验。为了保证算法的高效性，通过实验选取算法基本参数：种群规模为200，迭代次数为1 000，交叉和变异概率分别为0.8和0.2，精英数为40，种群中至少保留20%的不可行解。选择岸线长为1 200 m(岸线被分割成50 m为单位的等长度的泊位段)，12个岸桥的码头作为算例，以72 h为一个计划周期。依据表 1随机生成了6个算例(包含的船舶数分别为10，12，14，16，18，20)，且每个算例中包含小船30%，中船50%，大船20%，船舶服务成本参数设为c₁=150，c₂=100，c₃=200，c₄=150。

3.1 资源利用率分析

现有的泊位岸桥调度模型(如文献[5, 16])，目标函数中并不考虑岸桥的装卸成本，这有可能导致部分岸桥没有参与装卸任务却被占用。本文设置对比项Model 2，与本文模型Model 1进行对比。

$\begin{array}{l} \left[{{\rm{Model}}\;{\rm{2}}} \right]\\ \min \;f = \sum\limits_i {\left[{{c_1}\left( {{E_i}-{a_i}} \right) + {c_2}\left| {{B_i}-{b_i}} \right| + {c_3}{{\left( {{D_i}-{d_i}} \right)}^ + }} \right]} \end{array}$

(17)

s.t.约束(2)~(13)

图 3给出了两种模型下泊位和岸桥的利用率。可以看到，当船舶数量相对较少时，Model 1下的泊位利用率相对较小，两种模型下的岸桥利用率相差不大，因此，图 3(b)中的两条折线几乎重合，Model 1下的岸桥利用率稍小。这是因为当(D_i-d_i)⁺=0时，Model 2缺少对装卸船舶i的岸桥台时数的限制。例如，装卸船舶i所需的岸桥台时数为12，在Model 2下：1) 用3台岸桥工作4 h；2) 用3台岸桥工作5 h；3) 用4台岸桥工作3 h；4) 用5台岸桥工作3 h，这4种情况都满足约束条件且目标函数值相等，然而第2)、4)两种情况存在泊位和岸桥资源的浪费现象，而本文模型在目标函数中加入岸桥装卸成本后，能够避免这两种情况发生。当船舶数量相对较多时，船舶之间相互影响较大，在Model 2下，即使(D_i-d_i)⁺=0，为了满足其他船舶的停泊和装卸条件，实际装卸船舶i的岸桥台时数只能取到最小值，因此与Model 1下的资源利用率相等。

3.2 算法性能分析 3.2.1 算法高效性

为了验证本文算法(Improved GA, I-GA)的高效性，选择贪婪算法(GReedy Algorithm，GRA)以及文献[17]中提出的算法(T-GA)进行对比分析。其中，GRA又叫步步最优算法，即最先到达的船靠泊在最先可用的泊位，并在船舶装卸要求等约束条件下分配最多的岸桥；T-GA分两步实现，首先采用基于优先级编码的遗传算法确定船舶的停泊位置和停泊顺序，然后在此优化基础上利用遗传算法为每艘船分配合理的岸桥数量^[17]。对每个算例分别采用I-GA和T-GA求解20次，并取目标函数值的平均值与GRA的结果进行对比，结果如表 2所示。

由表 2可知，随着船舶数量的增加，I-GA相对于另外两种算法的优化程度增大。这是因为到港船舶数量的增加加剧了泊位、岸桥以及时间资源之间的相互冲突，算法搜索到可行解的难度增大，而本文提出的I-GA通过在种群中始终保留一定数量的不可行解, 较好地维持了种群的多样性，使得其比T-GA更容易跳出局部极小点，从而获得更优解。

3.2.2 算法收敛性

图 4给出了船舶数(V)分别为12、14、16时的三组算例下的算法收敛情况。可以看出，三组算例经过迭代进化均得到了一定的改善并最终收敛至最优解，且船舶数量越多算法收敛所需的迭代次数越多，这是因为泊位、岸桥和时间资源之间的相互冲突随着船舶数的增加而加剧，模型求解难度也随之增大。图中每条曲线在纵轴方向上的跨度说明了种群的进化程度。当船舶数量为16时，进化过程中最优解的改进最多，最优解改善了30.4%。

4 结语

对集装箱码头泊位岸桥协调调度问题进行了研究，在目标函数中考虑了岸桥装卸成本，建立了基于非线性混合整数规划的泊位岸桥协调调度模型，并结合可拓关联函数设计了改进的遗传算法对模型求解。改进的算法能够有效地维持种群多样性，提高了种群在进化后期的搜索效率，避免算法陷入局部最优。算例分析表明，本文提出的调度模型和求解算法能在有限时间内制定出港口资源调度计划，同时能够有效地避免港口资源浪费，为集装箱码头资源调度优化问题提供了科学合理的解决方案和决策依据。