低碳经济下港口泊位—岸桥分配问题

王致远，范元伟 WANG Zhi-yuan, FAN Yuan-wei

（上海理工大学 管理学院，上海200093）

(College of Management, University of Shanghai for Science and Technology, Shanghai 200093, China)

0 引 言

泊位和岸桥是港口的稀缺资源，正因为如此，合理的泊位—岸桥资源分配对于码头和船舶运营成本降低及客户满意度的提高都至关重要[1]。同时，合理的泊位—岸桥分配计划和船舶进港时间的选择对于船舶的油耗成本和二氧化碳的排放量有着直接的关系。但是随着集装箱运输量的持续增长，船舶往往高速驶入港口，造成码头拥挤，船舶只能在锚地等待靠泊，这大大增加了船舶等待的成本以及燃油消耗和二氧化碳的排放，造成环境的污染，不利于绿色航运和节省燃油成本的目标。研究报告表明，每年航运业二氧化碳的排放量超过12 亿吨，约占全球碳排放总量的4%[2]。由于近年来燃油价格的突飞猛涨，如何降低燃油成本已经成为了所有航运公司所关注的焦点，例如，减少ballast/尽量多装货，控制船舶航运速度，设计最佳耗油转速提高燃油使用率。这就需要港口与航运公司之间相互配合，协同合作，信息共享，才能缓解港口拥挤以及航运公司燃油成本过高的严峻情况。

许多文献在研究港口泊位—岸桥分配计划时，往往把船舶到港时间作为一个已知的参数来制定船舶泊位—岸桥分配计划[3-5]，并且它们所关注的问题主要在于保持客户服务水平的情况下，减少船舶在港口等待时间和船舶停泊时产生的二氧化碳排放量，这与航运公司所关切的整个航次的燃油消耗量以及二氧化碳排放量有所不同。本文研究的是在低碳经济下的港口泊位—岸桥问题，不再把船舶到港时间看作是已知的参数，而是作为一个决策变量。同时，对于到港船舶，通过港口与航运公司双方信息的共享，船舶公司根据即将到港船舶的基本信息（船舶长度，船舶装卸箱量，船舶靠泊位置，距离港口的距离，船舶航行的最大和最小航速） 进行泊位—岸桥资源分配，使港口整体资源得到充分利用，为到港的船舶指定其较为偏好的停泊位置，以此为基础，岸桥分配用于确定服务于每艘船舶的岸桥数量。通过优化分析提高停泊时的工作效率，降低船舶在港时间，以此弥补船舶由于降低速度驶入港口所造成的离港延迟。在缓解港口拥挤的情况下，降低船舶在港时的燃油消耗和二氧化碳的排放，以达到低碳经济下绿色航运的目标。

1 模型建立

本文建立的低碳经济下泊位—岸桥分配模型是由低碳经济下的泊位分配和港口的岸桥分配两部分建立而成，不仅能够实现低碳经济下船舶油耗量最小和船舶离港延迟时间最短的目标，同时能够实现港口岸桥分配总量最小，从而节省港口的资源分配，提高港口生产作业系统的整体性能。

1.1 低碳经济下的泊位分配。与传统泊位分配模型不同，本文将船舶到港时间作为决策变量，将船舶燃料消耗量和二氧化碳排放量融入传统泊位分配模型的目标函数中进行优化。然而不能忽视的一个问题是船舶通过改变靠港时的航速来控制到港时间，虽然可以最小化其等待时间，但是会影响到船舶的离港时间，进而影响船期。为了防止出现所有船舶都以最低航速驶近港口进而减少燃料消耗和二氧化碳排放量，并同时缩短在港作业时间的优化结果，本文将船舶平均在港时间最小化的目标函数修改为船舶平均离港延迟时间最小化。

设V：到港船舶集合（包含n艘船舶）；L：岸线长度；li：船舶的船长（考虑了船舶靠泊的安全距离）；hi：船舶i的作业时间；xi：靠泊位置；M：一个足够大的常数。决策变量：yi：船舶的靠泊时间。ai：船舶i的到港时间，ai的取值应介于分别由船舶的最高航速和最低航速确定。辅助决策变量：σij：σij=1 表示船舶i在船舶j的左侧靠泊；否则σij=0；i,j∈V,i≠j； δij：δij=1 表示船舶i在船舶j之前靠泊；否则δij=0；i,j∈V,i≠j。

假设泊位分配计划从零时刻开始，此时船舶距离港口mi（海里）。由赵刚的《国际航运管理》[4]，船舶i每航行天的燃油消耗fi与所采用的航速vi之间的函数关系可以用式（1） 表示。

船舶i从距离港口mi海里处行驶至港口过程中的燃油消耗量Fi可以表示为：

由此可得低碳经济下的BAP 模型如下：

目标函数（11） 为最小化船舶驶近港口期间的燃油消耗。由于船舶二氧化碳排放量与用油量成正比，因此该目标与最小化船舶航行期间的碳排放量是一致的。船舶二氧化碳排放量与用油量之间的比例系数在各文献中有微小差别，本文采用政府间气候变化专门委员会（IPCC: Intergovernmental Panel on Climate Change） 的比例，即1 吨船用油的燃烧产生3.17 吨的二氧化碳[5]。目标函数（4） 为最小化船舶平均离港延迟时间，需要注意的是本文不考虑没有延迟的船舶，而只考虑延迟离港的船舶进行优化，所以这里的参数n为延迟船舶的总数量。

1.2 港口的岸桥分配。设T为时间段集合，为可利用岸桥集合，为船舶的装卸箱量；etbi为船舶i的预计靠泊时间；etui为船舶i的预计离港时间；Cmini为船舶i的最少可分配岸桥数目，由船公司与码头公司的协议决定；Cmaxi为船舶i的最多可分配岸桥数目，由船舶长度和岸桥安全距离决定；v0为单个岸桥作业效率（TEU/h）；决策变量nci为分配给船舶i的作业岸桥数目；从属变量thi为船舶i的作业开始时间，本文假定只有当所需岸桥全准备好后才能开始作业；从属变量tfi为船舶i的作业完成时间；如果岸桥k在时间段j服务船舶i；则从属变量θijk=1，否则θijk=0；岸桥分配子模型如下:

目标函数（12） 表示船舶等待作业平均所需岸桥总量最小，这里需要注意的是，岸桥的利用是可以重复，也就是说假设停泊位置相近或者相同的前后两艘船可以分配到相同编号的岸桥；约束条件（13） 表示各船舶所分配岸桥数目的取值范围；约束条件（14） 表明船舶作业时间与船舶装卸箱量成正比，与所分配岸桥数目成反比；约束条件（15） 保证所有装卸作业需在指定时间窗内完成；约束条件（16） 表明在船舶作业过程中，作业岸桥数目保持不变；约束条件（17） 和（18） 说明没有岸桥在指定时间窗外对船舶进行作业；约束条件（19） 表明一台岸桥在每个时间段内最多可以服务一艘船舶；约束条件（20） 保证各时段内所有作业岸桥数不能超过岸桥总数；约束条件（21） 定义了从属变量。

2 模型求解

本文模型分为两部：低碳经济下的泊位分配以及港口的岸桥分配，利用多目标遗传算法求出全局最优解，达到本文研究的目的。

2.1 低碳经济下的泊位分配算法。本文模型第一部分为低碳经济下的泊位分配，泊位分配问题为NP 难题。本文采用了一种模拟生物进化机制的智能随机优化算法—遗传算法，它把自然遗传机制和计算机科学结合起来，按照个体对环境的适应程度进行概率搜索。因其搜索最优解的过程具有指导性，因此不容易陷入局部最优，即使所定义的适应函数是不连续的、非规则的，它也能以很大的概率找到全局最优解[6]。遗传算法因其优化性能在多目标优化问题中有较为广泛的应用[7-8]。本文结合具体问题对传统的遗传算法进行了改进，具体求解步骤如下。

（1） 染色体编码。本文用两个基因片组成一个染色体个体。子染色体1 表示船舶靠泊顺序，用自然数的编码形式，区别于船舶在码头的具体位置。由于码头和船长是固定的，所以一种靠泊顺序就对应着一个靠泊位置。子染色体2 为靠泊时间，采用小数的编码形式。如表1 所示。

表1 染色体的基因表述

（2） 种群初始化。为保证多样性，采用随机生成初始种群的方法。假设种群的大小为M，在算法开始随机生成M条染色体。

（3） 目标函数计算。任一染色体个体，包含两条子染色体，即船舶靠泊顺序和靠泊时间，通过染色体个体变量可以求解出对应的从属变量，进而计算出对应的目标函数值，将其作为各个体的适应度值。

（4） 交叉操作。将种群个体的信息在种群成员中进行交换，从而产生新的染色体，增加种群的多样性。本文的一个染色体中有两种不同编码形式，因此对于子染色体1（整数编码形式），在交叉时采用两点交叉的方式。对于子染色体2（小数编码形式），采用正交交叉的方式。

（5） 变异操作。在一个种群中，每个个体以概率Pm进行变异，生成新的变异群体。在每个变异的个体中，对于染色体1，采用随机选取两个不同的位置进行交换的方式来进行变异操作。对于染色体2，采用基于取代的方法即随机的选取一个取代位置，并且随机的生成一个满足式（18） 的随机数，用其取代当前位置上的基因信息。

（6） 选择操作。选取当前种群中的所有个体，包括交叉后和变异后的新个体，计算每个染色体个体的适应值，并进行排序，适应值小的排前面，适应值大的排后面，最后从种群前排选出M个个体，作为下一代的新种群。

（7） 终止准则。以进化代数作为终止判断条件，如果进化代数小于设定值，则返回（3），否则输出结果。

2.2 岸桥分配模型算法。模型第二部分为港口的岸桥分配，也采用基于启发式算法的遗传算法进行求解。具体步骤如下。

染色体编码：采用自然数编码形式进行编码，如表2 所示，染色体长度表示船舶数目；基因位置为船舶ID；基因值为船舶分配的岸桥数目nc，该数目由约束条件（13） 随机生成。

遗传操作：选择操作为轮盘赌法，交叉操作为2 点交叉法, 变异操作为交换变异法。

表2 染色体的基因表述

终止条件：到达最大迭代次数。

3 试验算例

3.1 基础数据。本文使用宁波市某著名的国际集装箱码头的实际数据进行研究。其码头岸线长L=1 500 米，取时间为1 天，以小时分段。初始时刻各岸桥均匀分布在码头岸线上。E从（600TEU～2 300TEU）；V0=40TEU/h。设定船舶作业时间初始值set-其中，vr为港口的平均船时效率。采用MATLAB R2013a 编写算法程序，运行机器配置为Pentium（R） D CPU 2.80GHZ。试验确定：初始种群popsize=10，交叉概率pc=0.6，变异概率pm=0.01，迭代次数g=50。我们的目标是：（1） 确定优化目标为船舶离港延迟时间最小，且最小化船舶驶近港口期间的燃油消耗（2） 在完成总工作量的情况下，最小化安排给船舶工作的岸桥总数目。

3.2 结果分析。从图1 中可以看出，第三行和第五行表示的是10 艘船舶的最佳到港时间。Bestfitness 的值为低碳经济下泊位分配的两个目标函数，即离港时间最小化和燃料消耗、二氧化碳排放量最小化的加权和的最优解。Positionx 的值表示的是10 艘船舶最佳的停泊位置。图2 纵坐标表示模型第一部分低碳经济下泊位分配的两个目标函数，即离港时间最小化、燃料和二氧化碳排放最小化的加权和，横坐标表示的是种群个体通过交叉变异的迭代数值，本文设定迭代数为50，红色曲线表示的是每一代两个目标函数的加权和的平均值，蓝色曲线表示的是从各代中挑选出来的最优的目标函数加权值。从图2 中可以看出，随着种群进化迭代数的不断增加，代表各代种群目标函数平均加权和的红色曲线逐渐趋近于代表各代种群目标函数最佳加权和的蓝色曲线，从而可以得出满足在低碳经济下离港时间最小化且燃料、二氧化碳排放量最小化双目标的最佳加权和，从图1 可知最佳加权和值为63.7479，实现本文模型第一部分低碳经济下泊位分配的目标。

图3 中，bestpop2 的值表示的是码头分配给每艘船最多的岸桥总数。Bestfitness2 的值表示的是码头只需要11 台岸桥便可以完成10 艘船舶到港装卸货物的任务。Popindex 每一行的值表示的每艘船舶使用岸桥的编号，需注意的是0 表示的是没有使用岸桥。图4 为求解港口岸桥分配时遗传算法的迭代过程图。图4 横坐标表示的是岸桥使用的总数量，纵坐标表示的是进化的迭代数。本文设定进化代数为50。红色曲线表示的是种群个体每一代岸桥分配总量的平均值，蓝色曲线表示的是种群个体每一代最佳的岸桥分配总数量。从图4 可以发现，随着种群进化迭代数目的不断增加，代表各代种群个体岸桥分配总量平均值的红色曲线逐渐趋近于代表各代种群个体岸桥分配总量最佳值得蓝色曲线，从而可以表示为通过确定每艘船舶的泊位位置和停靠时间，而得出港口最佳的岸桥分配总量为11 个。不仅满足了低碳经济下的泊位分配最佳，也满足了港口岸桥分配总量的最佳。

4 结 论

本文将船舶到港时间作为决策变量引入传统泊位分配模型中，同时将船舶油耗和碳排放量融入传统泊位分配模型的目标函数中，建立了船舶油耗最小和船舶离港延迟时间最短的双目标优化模型，并且加入岸桥分配模型，使得港口整体优化，在满足能够完成船舶装卸任务的情况下，避免不必要的岸桥分配，提高港口的工作效率。然而研究仍然存在很多的局限性，首先，没有考虑船舶在港停泊时的排放量问题；其次，模型只考虑了一个码头及其客户，而实际问题可能会延伸到涉及多个码头，甚至多个港口。克服这些限制，并优化模型将是未来进一步的研究方向。

[1] Meisel F, Bierwirth C. Heuristics for the integration of crane productivity in the berth allocation problem[J]. Transportation Research Part E: Transportation Review, 2009,45(1):196-209.

[2] 袁象. 低碳经济对我国海运业的影响及应对措施[J]. 交通企业管理，2010(2):1-3.

[3] BIERWIRTH C, MEISEL F. A survey of berth allocation and quay crane scheduling problems in container terminal[J]. European Journal of Operational Research, 2010,202(3):615-627.

[4] STEENKEN D, VOB S, STAHLBOCK R. Container terminal operation and operations research——a classification and literature review[J]. OR Spectrum, 2004,26(1):3-49.

[5] STAHLBOCK R, VOB S. Operations research at container terminals: a literature update[J]. OR Spectrum, 2008,30(1):1-52.

[6] 王小平，曹立明. 遗传算法——理论、应用与软件实现[M]. 西安：西安交通大学出版社，2002:78-79.

[7] 赵刚. 国际航运管理[M]. 大连：大连海事大学出版社，2006:93-94.

[8] 王海峰，白佳玉. 国际海运温室气体排放的量化分析及中国对策研究[J]. 海洋环境科学，2010(6):923-926.

[9] KALYANMOY D, AMRIT P, SAMEER A, et al. A fast and elitist multi-objective genetic algorithm NSGA-II[J]. IEEE Trans on Evolutionary Computation, 2002,6(2):182-197.

[10] 崔逊学. 多目标进化算法及其应用[M]. 北京：国防工业出版社，2006:45-48.