许欢,刘伟,刘诗
上海海事大学交通运输学院,上海 201306
◎工程与应用◎
低碳经济下的港口泊位分配模型及其算法实现
许欢,刘伟,刘诗
上海海事大学交通运输学院,上海 201306
航运公司正在进行前所未有的努力以减少船舶的燃油消耗量及碳排放量,而港口所制定的泊位分配计划对于船舶的油耗量和碳排放量有着直接的影响。由于船舶的到港时间是港方制定泊位分配计划的关键参数,因此将船舶到港时间作为决策变量引入传统的泊位分配(BAP)模型中,设计了港口与船方协调调度的新的泊位分配策略——VAT(Variable Arrival Time)策略,同时将船舶油耗和碳排放量融入BAP模型的目标函数中,建立了船舶油耗量最小和船舶离港延迟时间最短的双目标优化模型。采用多目标遗传算法对该模型进行求解,并用仿真算例验证了该策略的有效性。计算结果表明,VAT策略可以大大削减航运公司的燃油消耗和船舶的碳排放,同时可以提高港口的服务水平,缩短船舶在港等待时间。
低碳经济;泊位分配;遗传算法;可变的到港时间(VAT)策略
研究报告显示,航运业目前每年排放的二氧化碳超过12亿吨,约占全球碳排放总量的4%[1]。为了减轻对环境的负面影响,在过去十年中国际社会已加强对于船舶排放的立法。与此同时,船用燃油价格在过去几年中飞涨,燃油成本已成为航运公司经营成本中的绝大部分。基于这两方面的原因,航运公司正在进行前所未有的努力以减少船舶的燃油消耗及碳排放量,从技术上和管理层面上尝试各种可能的措施来减少燃油消耗。例如,减缓船舶航速。目前航运公司普遍采用低于20节的船舶经济航速[2]。不论是从经济上还是从环境上来考虑船舶油耗以及碳排放的问题,其对于航运公司的策略选择的影响是深远的,包括营销策略,船舶配置及调度,航线选择等。
船舶进港时机的选择及港口所制定的泊位分配计划对于船舶的油耗量和碳排放量有着直接的影响,不论是在船舶驶近港口期间还是船舶在港停泊期间。通过采用船舶航行优化系统,以及制定更好的船舶靠泊计划,对船舶的进港时机进行优化,既能缩短船舶在港口外等待进港的时间和其在港口的周转时间,又能减少温室气体的排放量。然而,现实的情况是船舶往往以一个较高的航速行驶至港口,港口拥堵,船舶无法靠泊,只能在锚地等待,这既增加了船舶等待期间的燃料消耗和碳排放,也增加了船舶在港口附近海域航行时的燃料消耗和碳排放。如果港口在制定泊位分配计划时就考虑到船舶的油耗及碳排放的问题,港口和航运公司之间努力合作,并进行充分的信息共享,情况就会有所改变。
船舶的到港时间是港口制定泊位分配计划的关键参数,在以往的泊位分配计划制定过程中,通常将船舶到港时间作为一个已知的参数,港口根据由船期所确定的船舶到港时间来制定泊位分配计划。同时,港口所关注的问题主要在于在保持客户服务水平的情况下,尽可能减少船舶在港等待的时间和船舶在港口停泊时产生的碳排放,这与航运公司所关切的整个航次的燃油消耗量以及碳排放量有所不同。低碳经济下的泊位分配不再将船舶到港时间看作一个已知的参数,而是作为一个决策变量,同时要求港口在掌握了即将靠泊的船舶的有关资料的基础上,在综合考虑码头和航运公司所关注的问题的情况下制定泊位分配计划。然后,港口给即将到达的船舶发送其建议,船方根据港方的建议选择一个合适的速度航行至港口。也就是说,港方应考虑到其客户——航运公司的效率,而不是孤立地制定其作业计划。当然这需要双方之间进行充分的信息共享,船方必须事先将船舶的基本信息(船舶长度,装载/卸载量,所要求的出发时间,距港口的距离,船舶的最大/最小航速等)向港口主动传达。
由以上分析可知,低碳经济下的泊位分配计划应该是港方和船方共同决策的结果,双方合作的潜力在于协调控制驶近船舶的航速,以确定其靠港时间。这就要求船舶加速或减速航行以确定特定的装载、卸载时段,避免港口拥堵,同时最大限度地减少船舶在港区附近航行和在港停泊期间的油耗和碳排放量,以达到港口资源和航运企业利益与大气环境之间的微妙平衡。这种平衡可以通过改进传统的泊位分配模型(Berth Allocation Problem,BAP)来实现。
自20世纪90年代以来,泊位分配问题被广泛研究,关于其最新研究的详细回顾,可以参考Bierwirth[3]和Meisel[4]所著文章,这里不再赘述。
在以往的文献中,通常将船舶到港时间作为已知的参数来建立泊位分配模型,并且常以提高港口作业效率作为优化目标,如减少船舶起航延误,缩短船舶的等待时间和在港作业时间等,而考虑到船舶油耗和碳排放问题的文献较少。Golias[5]等人于2009年认为:在建立BAP模型时,应将船舶到达时间作为决策变量,而不是已知的参数。他们尝试通过减少船舶等待时间来达到减少船舶燃料消耗和碳排放的目的。然而,其目标仅仅是减少船舶在港口停泊时的碳排放。事实上,相比于在港停泊期间,船舶在驶近港口的过程中的碳排放更多[6],因此,应给予更多的关注。Lang和Veenstra[7]在2010年也考虑将船舶到达时间作为决策变量,并最大限度地减少船舶驶近港口过程中的油耗。他们的研究首次对船舶燃油消耗进行了直接的定量分析,并阐明将船舶到达时间作为决策变量引入BAP模型可以为港口运营商和航运公司之间提供潜在的协调机会,这将会节省船舶在航行期间的燃油消耗。这个基本思想也被本文的研究所采用。然而,其研究无法处理船舶燃油消耗量与航速之间的非线性函数关系,他们只是简单地把非线性回归以线性回归来代替。此外,并没有考虑船舶碳排放的问题。Alvarez[8]等人在2010年进行了有关泊位分配和船舶航速控制的混合优化问题的研究,并开发了一个离散事件仿真工具,提出了既能节省燃料又能提高港口生产率的新泊位分配策略。通过将船舶航速的可行域离散化,避开了燃油消耗与航速之间的非线性关系,但这种离散化方法可能会使计算不够精确。此外,也没有考虑船舶碳排放的问题。本文将船舶到达时间作为决策变量引入BAP模型中,同时将船舶油耗和碳排放量融入BAP模型的目标函数,试图弥补此项空白。
3.1 传统的泊位分配模型
在传统的泊位分配(BAP)模型中,船舶随着时间的推移不断到达港口,港口计划人员为每艘船舶分配岸线泊位和靠泊时间,以使船舶能够尽快驶离码头。
模型参数:
V为到港船舶集合(包含n艘船舶);L为岸线长度;ai为船舶i的到港时间;li为船舶i的船长(考虑了船舶靠泊的安全距离);hi为船舶i的作业时间;M为一个足够大的常数。
决策变量:
xi为船舶i的靠泊位置;yi为船舶i的靠泊时间。
辅助决策变量:
σij:σij=1表示船舶i在船舶j的左侧靠泊;否则σij=0;i,j∈V,i≠j。
δij:δij=1表示船舶i在船舶j之前靠泊;否则δij=0;i,j∈V,i≠j。
传统的泊位分配模型[9]如下:
在这个模型中,目标函数式(1)是最小化船舶平均在港时间,它是衡量集装箱码头服务水平的一个具有代表性的指标,也是码头作业计划制定者经常采用的决策目标;约束条件式(2)保证所有船舶都在给定岸线内靠泊;约束条件式(3)~(5)保证任意两艘船舶在占用码头岸线和在港作业时间上不相互重叠;约束条件式(6)表明船舶只有到港后才能靠泊;约束条件式(7)定义了从属变量。
值得注意的是,在这个传统的BAP模型中,码头作业计划制定者是根据船舶的预计抵达时间来分配船舶靠泊位置和靠泊时间的,也就是说,码头作业计划制定者把每艘船舶的到达时间看成是一个已知的恒定的参数。把这个泊位分配策略称为CAT(Constant Arrival Time)策略。然而,把船舶到港时间作为决策变量,将为优化船舶燃料消耗和减少碳排放提供可能。这个新的泊位分配策略可以称之为VAT(Variable Arrival Time)策略。在VAT策略中,把船舶的燃料消耗量和碳排放量融入BAP模型的目标函数中进行优化。
3.2 低碳经济下的泊位分配模型
下面勾勒出VAT策略的基本思路,并将船舶油耗和碳排放融入BAP模型的目标函数。一般来说,对于船舶i,航运公司可以通过调整其航速来控制其到达港口的时间,即把ai作为决策变量,而不再将其看成恒定的参数。ai的取值应介于[aˉi],和aˉi分别由船舶的最高航速和最低航速确定。
假设泊位分配计划从零时刻开始,此时船舶i距离港口mi(nmile)。由赵刚的《国际航运管理》[10],船舶i每航行天的燃油消耗量fi与所采用的航速vi之间的函数关系可以用式(8)表示。
船舶i从距离港口minmile处行驶至港口过程中的燃油消耗量Fi可以表示为:
由于船舶到港时间ai成为决策变量,而不再是恒定不变的参数,因此原目标函数值可以通过调整ai和yi的取值而实现最小化。然而必须要考虑的一个问题是,船舶通过改变其靠近港口时的航行速度来控制其到港时间,虽然可以最小化其等待时间及在港作业时间,但是会影响到其离港时间,进而影响到船期。为防止出现所有船舶都以最低航速驶近港口进而减少燃料消耗和碳排放,并同时缩短在港作业时间的优化结果,需对原目标函数进行改进,即将船舶平均在港作业时间最小化的目标函数修改为船舶平均离港延迟时间最小化。
用di表示船舶预计离港时间,原目标函数修改为:
由此可得低碳经济下的BAP模型如下:
目标函数式(11)为最小化船舶驶近港口期间的燃油消耗。由于船舶二氧化碳排放量与用油量成正比,因此该目标与最小化船舶航行期间的碳排放量是一致的。船舶二氧化碳排放量与用油量之间的比例系数在各文献中有微小差别,本文采用政府间气候变化专门委员会(Intergovernmental Panel on Climate Change,IPCC)的比例,即一吨船用油的燃烧产生3.17吨的二氧化碳[11]。目标函数式(12)为最小化船舶平均离港延迟时间,这个时间也可作为港口服务水平的一个衡量指标。
不包括约束条件式(19),该模型由5n2/2+n/2个约束条件和2n2+n个变量组成,其中2n2-2n个变量是二进制的。同时,目标函数f1和f2都是非线性的,这给用分支定界法来求解模型带来了极大的挑战。考虑到研究模型与约束条件的复杂性,本文采用了一种模拟生物进化机制的智能随机优化算法——遗传算法。遗传算法属于进化类优化算法的一种,是一种启发式算法,它把自然遗传机制和计算机科学结合起来,按照个体对环境的适应程度进行概率搜索。因其搜索最优解的过程具有指导性,因此不容易陷入局部最优,即使所定义的适应函数是不连续的、非规则的,它也能以很大的概率找到全局最优解[12]。遗传算法因其优化性能在多目标优化问题中有较为广泛的应用[13-14]。
本文结合具体问题对传统的遗传算法进行了改进,具体求解步骤如下。
4.1 染色体编码
在前述泊位分配优化模型中有三个决策变量x、y、a,其中变量a为船舶的到港时间,其取值与决策变量y
图1 染色体的基因表述
4.2 种群初始化
为保证多样性,采用随机生成初始种群的方法。假设种群的大小为M,在算法开始时随机生成M条染色体。每条染色体有两条子染色体,见图1中的染色体编码。子染色体1根据船舶的数量随机生成排序序列;子染色体2,在满足式(17)及式(18)的情况下,随机生成靠泊时间。
4.3 目标函数值计算
对于给定的任一染色体个体,包含两条子染色体,即船舶服务序列和船舶靠泊时间。通过染色体个体变量可以求解出对应的从属变量,进而计算出对应的目标函数值fk,k∈{1,2},将其作为各个体的适应度值。
4.4 交叉操作
交叉操作是以随机的方式将种群个体的信息在种群成员之间进行交换,从而产生新的染色体,增加种群的多样性。交叉操作的方式很多,采用何种方式需要根据染色体的编码形式。由于本文在一个染色体中,采用了两种不同的编码形式,因此相应地采用了两种不同的方式进行交叉操作。
对于子染色体1,采用的是整数的编码形式,在交叉时采用两点交叉的方式。如果交叉后得到的子代不可行,即不同船舶存在相同的靠泊顺序,则需要进一步采取交换策略和调整策略。图2以6艘船舶的交叉操作为例,A、B为父代,交叉后得到中间代C1、D1。查看C1可知,船舶1和船舶3的靠泊顺序重复,为保证船舶靠泊顺序是个排序序列,即不重复,需要对重复的位置进行交换。为保存交叉操作的成果,在交换策略中,交叉区域的基因不进行变化,仅仅变换交叉区域外的基因。交换策略共分为三步:(1)从左至右查找C1交叉区域内出现过两次的靠泊顺序编号(如顺序1),并找到D1内对应基因位置的靠泊顺序编号(如顺序4);(2)在C1交叉区域外找到顺序1对应的船舶决策变量,在D1交叉区域外找到靠泊顺序4对应的船舶决策变量,两者进行交换;(3)重复(1)、(2)直至交叉区域查找完毕。交换操作所得结果还可能出现不满足约束条件式(18)的情况,则需要进行调整。调整策略的规则是把不符合约束条件的船舶服务时间用可行的船舶服务时间进行替换,即人为缩小搜索空间以避免多余的交换,最终可确定父代A、B的子代为C、D。
图2 子染色体1的两点交叉操作
对于子染色体2,采用的是小数的编码形式,采用正交交叉的方式进行交叉操作。设参与重组的Q个父代个体为p1,p2,…,pQ,其中pi=(pi1,pi2,…,piN)且i∈{1,2,…,Q},其正交交叉操作具体步骤如下:将每一个参与重组的父代个体看作是正交交叉操作的一个水平,即N水平;然后将每一个父代个体分成F个片段,每个片段作为正交交叉操作的一个因素,即F个因素。这样就将Q个父代个体的重组问题转化为Q水平、F因素的交叉问题,最后构造正交表LM(QF),进行正交交叉操作产生M个子代个体。图3显示了子染色体2的正交交叉操作过程(以Q=3,M=9,F=3为例),其具体交叉过程见参考文献[15],这里不再赘述。
图3 子染色体2的正交交叉操作
4.5 变异操作
在一个种群中,每个个体以概率Pm进行变异,生成新的变异群体。在每个变异的个体中,对于子染色体1,采用随机选取两个不同的位置进行交换的方式来进行变异操作;对于子染色体2,采用基于取代的方法,即随机选取一个取代位置,并且随机生成一个满足式(18)的随机数,用其取代当前位置上的基因信息。
4.6 选择操作
选取当前种群中的所有个体,包括交叉后的新个体,变异后的新个体,进行4.3节中的目标函数值计算,即计算每个染色体个体的适应度值fk,k∈{1,2}。然后根据适应度值对当前群体进行升序排序,即把适应度值fk,k∈{1,2}比较小的排在前面,适应度值fk,k∈{1,2}比较大的排在后面,最后从种群中选出排在前面的M个个体,作为下一代的新种群。
4.7 终止准则
以进化代数作为终止判断条件,如果进化代数小于设定值,则返回到步骤4.3;否则输出结果。
5.1 数据
本文使用宁波市某著名的国际集装箱码头的实际数据进行研究。其码头岸线长L=1 600 m,以此集装箱码头2011年7月14日到港船舶的信息数据为例,具体数据见表1。
5.2 CAT策略下的泊位分配方案
按照传统的泊位分配模型,即采用CAT策略,得到的泊位分配方案如图4所示。其求解过程可参照文献[16],这里不再赘述,而是直接给出求解结果。
经计算可得,在CAT策略下,各船舶从零时开始至其到达码头期间的燃油消耗总和为=763 t,排放的二氧化碳总量为2 418.8 t,船舶平均在港时间为7 h,17艘船舶总共等待时间为其中第6、 10、11、12、13、15、16、17号船舶的等待时间分别为4、1、5、3、5、1、1、2 h,其余船舶的等待时间为0。各船舶的离港延迟时间均为0,即=0。
表1 到港船舶数据
图4 CAT策略下的泊位方案示意图
5.3 VAT策略下的泊位分配方案
取零时作为码头泊位分配计划开始的时刻,不考虑计划期前靠泊的船舶,根据各船舶目前所采用的航速及其最高、最低航速,可以计算出各船舶在码头泊位分配计划开始时刻与码头的距离mi(nmile)及各船舶的最快到港时间和最慢到港时间,如表2所示。
本文采用C#语言编写算法程序,运行机器配置为Pentium D CPU 2.80 GHz。通过实验确定多目标遗传算法各参数如下:种群大小pop=40;遗传迭代次数G= 1 024;交叉概率Pc=0.8,变异概率Pm=0.1,所耗时间为1 min 7 s。通过前述优化算法,将相关数据输入所编程序,能求得低碳经济下泊位分配模型的多个Pareto最优解,即Pareto最优解集,如表3所示(由于篇幅限制只随机地列出六种方案)。
表2 零时刻各船舶与码头的距离mi及最快、最慢到港时间
由表3后两列的对比结果可知,VAT策略在减少燃油消耗、减排二氧化碳这一目标上明显优于CAT策略;同时VAT策略可以减少船舶等待作业的时间,进而减少船舶平均在港时间。但VAT策略在目标二上劣于CAT策略,即船舶的平均离港延迟时间在VAT策略下多于CAT策略。船舶平均离港延迟时间越长,节省的燃油量越多。对于同一个Pareto最优解,目标一的优化程度要明显高于目标二的被影响程度。综合考虑,VAT策略既能提高港口的服务水平(船舶平均在港时间缩短),又能减少船舶的燃料消耗和碳排放,在目前的高油价下,为船公司节省了大量的燃油成本,即既有经济效益又有环境效益,并且对各方都有益。或者说,VAT策略从不同程度上平衡了两个相互矛盾的目标,能获得更大的综合效益。
表3 Pareto最优解集
VAT策略的另一个好处是码头作业计划制定者可以在船舶离港延迟最小化和燃油消耗最小化这两个目标之间进行权衡,根据实际情况选择合适的方案。并且对于每种方案,所编写的算法程序都可以导出对应的变量取值EXCEL表和泊位分配甘特图,这里由于篇幅的限制,没有具体列出。
本文将船舶到港时间作为决策变量引入BAP模型中,设计了港口与船方协调调度的新的泊位分配策略——VAT(Variable Arrival Time)策略,同时将船舶油耗和碳排放量融入BAP模型的目标函数中,建立了船舶油耗量最小和船舶离港延迟时间最短的双目标优化模型。采用多目标遗传算法对该模型进行求解,并用仿真算例验证了该策略的有效性。研究结果表明,VAT策略可以大大削减船舶的燃油消耗和碳排放量,同时可以提高港口的服务水平,缩短船舶在港等待时间。换句话说,VAT策略,建立了一个协调机制,它可以为港口和航运公司带来双赢的经济效益和环境效益。必须指出的是,港口与航运公司之间的信息共享是实施VAT策略的先决条件。
VAT策略也有一定的局限性。首先,在这项研究中,没有考虑码头装卸机械的分配,它会对船舶在港作业时间和等待作业时间产生影响。第二,虽然船舶在航行时的废气排放量相对于在港口停泊时的排放量来说更多,但是后者是一个比较敏感的话题,并受到广泛的关注。因为船舶在停泊期间其辅机所产生的废气是港口污染物的主要来源。船舶排放物如氮氧化物(NOx),硫氧化物(SOx)和颗粒物(PM)等,造成了港区大气环境的恶化,甚至对港口城市和沿海社区居民的健康产生了巨大且明显的影响。该模型仅考虑了船舶在驶近港口期间的油耗和碳排放,而船舶在港停泊期间产生的碳排放没有考虑在内。第三,没有考虑连续的动态泊位分配问题。船舶靠泊港口是一个连续的动态的过程,但本文仅考虑了一个时间段内的静态泊位分配问题。最后,该模型只考虑了一个码头及其客户,而实际问题可能会延伸到多个码头,甚至涉及多个港口。克服这些限制,并优化模型将是未来进一步的研究方向。
[1]袁象.低碳经济对我国海运业的影响及应对措施[J].交通企业管理,2010(2):1-3.
[2]刘宝亮.减速航行正在成为航运业趋势[J].中国船检,2008(10):60-61.
[3]Bierwirth C,Meisel F.A survey of berth allocation and quay crane scheduling problems in container terminals[J]. Eur J Oper Res,2010,202(3):615-627.
[4]Meisel F,Bierwirth C.Heuristics for the integration of crane productivity in the berth allocation problem[J].Transport Res E-Logist Transport,2009,45(1):196-209.
[5]Golias M M,Saharidis G K,Boile M,et al.The berth allocation problem:optimizing vessel arrival time[J].Marit Econom Logist,2009,11(4):358-377.
[6]Schrooten L,De Vlleger I,Panis L I,et al.Inventory and forecasting of maritime emissions in the Belgian sea territory,an activity-based emission model[J].Atmos Environ,2008,42(4):667-676.
[7]Lang N,Veenstra A.A quantitative analysis of container vessel arrival planning strategies[J].OR Spectrum,2010,32(3):477-499.
[8]Alvarez J F,Longva T,Engebrethsen E S.A methodology to assess vessel berthing and speed optimization policies[J]. Marit Econom Logist,2010,12(4):327-346.
[9]杨春霞,王诺,杨华龙.集装箱码头泊位——岸桥分配耦合优化[J].计算机集成制造系统,2011(10):2270-2277.
[10]赵刚.国际航运管理[M].大连:大连海事大学出版社,2006:93-94.
[11]王海峰,白佳玉.国际海运温室气体排放的量化分析及中国对策研究[J].海洋环境科学,2010(6):923-926.
[12]王小平,曹立明.遗传算法——理论、应用与软件实现[M].西安:西安交通大学出版社,2002:78-79.
[13]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.
[14]崔逊学.多目标进化算法及其应用[M].北京:国防工业出版社,2006:45-48.
[15]蔡自兴,江中央,王勇,等.一种新的基于正交实验设计的约束优化进化算法[J].计算机学报,2010(5):855-864.
[16]乐美龙,刘菲.基于Memetic算法的泊位和岸桥分配问题[J].武汉理工大学学报,2011,33(11):66-71.
XU Huan,LIU Wei,LIU Shi
College of Transport&Communications,Shanghai Maritime University,Shanghai 201306,China
Shipping companies are making an unprecedented effort to reduce fuel consumption and carbon emissions during the voyage,which are directly effected by port’s berth allocation plan.Considering the ship’s arrival time is a key parameter in the formulation of berth allocation plan for ports,this paper introduces the ship’s arrival time into the traditional BAP(Berth Allocation Problem)model as a decision variable,designs a new berth allocation strategy—VAT(Variable Arrival Time)strategy,which is based on the coordination between the ports and the ship operators,blends the fuel consumption and carbon emission in the BAP model’s target function and builds bi-objective(minimizing fuel consumption and departure delay time)optimization model,uses MOGA(Multi-Objective Genetic Algorithms)to solve the model and validates the strategy by a simulation example.The calculation indicates that VAT strategy can reduce shipping companies’fuel consumption and carbon emission greatly.At the same time,it can also improve the service level of the ports and cut down the waiting time of the ships.
low-carbon economy;berth allocation plan;genetic algorithm;Variable Arrival Time(VAT)strategy
A
F550.62;U691+.3
10.3778/j.issn.1002-8331.1210-0283
XU Huan,LIU Wei,LIU Shi.Berth allocation model under low-carbon economy and its algorithms implementation. Computer Engineering and Applications,2014,50(6):219-225.
国家自然科学基金(No.71272219);上海市科学技术委员会科研计划项目(No.11510501800);上海海事大学研究生创新能力培养专项基金资助项目(No.YC2010030)。
许欢(1981—),女,博士研究生,讲师,研究领域为国际航运现代化管理;刘伟(1954—),男,博士,教授,研究领域为物流系统规划与设计;刘诗(1989—),男,硕士研究生,研究领域为国际航运现代化管理。E-mail:lovely_xuhuan@163.com
2012-10-29
2013-01-08
1002-8331(2014)06-0219-07
CNKI网络优先出版:2013-01-18,http://www.cnki.net/kcms/detail/11.2127.TP.20130118.1024.001.html