基于双目标规划的班轮航线配船

潘 静 静

(1.福建农林大学 交通与土木工程学院，福建 福州 350002；2.上海海事大学 信息工程学院，上海 201306)

基于双目标规划的班轮航线配船

潘 静 静1,2

(1.福建农林大学 交通与土木工程学院，福建 福州 350002；2.上海海事大学 信息工程学院，上海 201306)

为了优化班轮公司的船舶资源配置，以规划周期内船舶运营总成本和碳排放量最小化为目标，建立了一个双目标规划航线配船模型，使用Gurobi工具对模型进行求解，通过数值实验对模型的可行性和有效性进行验证。研究表明：同更小容量的船舶相比，大容量船舶不仅具有单箱成本的竞争优势，而且排放更少的CO2，更加有益于环境保护；通过提升船舶的技术以减少船舶的燃油消耗常数、减速航行以及配置大型船舶为主的运力结构这3种方法是显著减少船舶运营成本和碳排放量的有效措施。

交通运输工程；航运网络；航线配船；碳排放；双目标优化

0 引 言

在国际贸易中，海上运输是最主要的运输方式之一，超过90%的国际贸易货物通过海上运输[1]。伴随着经济全球化深入发展，国际贸易量持续增长，航运业成为全球经济发展的支柱。与此同时，航运业的碳排放问题也引起了国际社会越来越多的关注。国际海事组织(International Maritime Organization，简称“IMO”) 2014年发布的第三次温室气体研究报告[1]显示，2012年全球航运业二氧化碳排放总量为9.38亿吨，其中国际航运碳排放量为7.96亿吨，约占全球碳排放总量的2.2%。该研究报告同时指出，根据目前的碳排放增长趋势，预计到2050年航运业碳排放量将增长50%～250%。从政府层面引导低碳经济的发展，常见的调控手段是征收碳排放税和推行碳排放权交易[2]；而企业层面实行碳减排，通常为设定碳排放目标的做法，将考虑环境友好的低碳可持续发展作为经营战略。

航运业的碳排放取决于船舶的燃油消耗[3]。在既定的船舶技术条件下，燃油消耗与配置到航线上运营的船舶的数量与类型密切相关。航线配船即为特定航线分配一定数量的特定类型的船舶[4]。航线配船问题是一个复杂的规划问题，已有大量研究人员从不同的角度对航线配船模型和算法进行研究，如S.GELAREH等[5]提出一个非线性整数规划模型解决短期航线配船问题；李佳等[6]建立了最大化船公司航线运营利润和最小化运力浪费的双目标航线配船模型；K.FAGERHOLT等[7]设计了一个启发式算法用于求解滚装车运输航线上的配船问题；S. GELAREH等[8]则同时考虑航线网络设计和航线配船问题等。M.CHRISTIANSEN等[9]对近年来航线配船的经典文献进行了回顾，并提出关注燃油成本控制与考虑航运业对环境的影响是航线配船研究的两大趋势；WANG Shuai’an等[10]同样认为尽可能减少航运对环境的影响是航线配船问题的重要研究方向。许欢等[11]将船队利润最大和碳排放量最小作为优化目标对航线配船进行决策；薛颖霞等[12]在航线配船模型中加入碳排放量约束条件；叶德亮等[13]建立了考虑碳税成本的班轮航线配船模型，认为引入碳税机制必然引起船队收益下降。

从历史文献来看，考虑碳排放的班轮航线配船研究并不多，并且在近几年才开始得到关注。为了填补低碳环境下的班轮运力优化配置研究，笔者以最小化船舶运营成本和碳排放量为目标，建立了一个双目标整数规划模型。通过算例验证模型的可行性和有效性，并深入分析了模型参数对目标函数的影响机理。实验结果表明，建立的数学模型可以给出最优航线配船方案，为班轮公司经营的航线分配合适的船舶类型与数量，可以为班轮公司运力投放、租用船舶、闲置船舶等运力配置优化决策提供依据。

1 问题描述

图1 航线路径Fig.1 Shipping route

(1)

给定规划周期T，根据航次时间可以计算出一艘第v种船舶在第r条航线上至多完成的航次数量Xvr，如式(2)：

(2)

船舶在海上运行时，船用燃油燃烧后产生大量CO2，碳排放量随着燃油消耗量增加而增加，而船舶的燃油消耗量是一个关于航速三次方的函数[14]。设Bv为第v种类型船舶的燃油消耗常数，船舶在第r条航线上行驶,每小时的燃油消耗量Qvr与航速之间的幂函数关系如式(3)。式中，燃油消耗常数与船舶结构、主机功率及船龄等船舶技术有关[3]：

(3)

当燃油市场价格为Pr美元/t时，一艘船舶完成一个航次所需燃油成本Cvr，计算如式(4)：

(4)

船舶的碳排放量= 该船舶的排放因子δCO2×燃料消耗量[3]。第v种类型船舶在第r条航线上的碳排放量Evr结合式(3)推导如下：

(5)

从式(4)、式(5)可以看出，低速航行是班轮公司控制燃油成本和碳排放量的一种途径。然而，由式(1)、式(2)可见，在既定的船队规模下，航速越慢，往返航次时间越长，船舶完成的航次数量越少，相当于航线上配置的运力越少。也就是说，航速受到影响服务水平的往返航次时间、满足货量需求的运力供给两个因素的制约，是班轮公司在服务水平、货量需求情况、市场运价水平等因素综合考虑下做出的决策。因此，笔者将航速设定为参数。

2 数学模型

2.1 符号说明

2.2 模型建立

2.2.1 建立航线配船模型

考虑船舶运营总成本最小化，建立航线配船模型[M1]：

[M1] minfC=fX+fI+fL

(6)

其中：

(7)

(8)

(9)

s.t.

∑vKvxvr≥Dr

(10)

∑rnvr≤Nv

(11)

(12)

(13)

(14)

nvr≤xvr

(15)

(16)

目标函数式(6)为船队运营总成本，式(7)～式(9)为航线上的船舶运营成本、租赁船舶的租金成本以及闲置船舶的养护成本；式(10)为货量运输需求应被满足；式(11)、式(12)为可分配的自有船舶和租入船舶的数量为约束；闲置船舶数量通过式(13)计算；式(14)为航次数受到该条航线上分配的船舶数量的限制；式(15)为约束航次数与航线上分配船舶数量的关系；式(16)为决策变量的非负整数约束。

2.2.2 船舶运输过程的碳排放

在船舶运营总成本最小化的基础上，考虑船舶运输过程中碳排放的问题。设规划周期内船舶的碳排放总量为fE，结合式(5)，按式(17)计算：

(17)

为[M1]增加一个碳排放量最小化目标函数fE，得到一个双目标规划模型[M2]，如式(18)：

[M2] minf=(fC,fE)

(18)

式中：[M2]的约束条件与[M1]相同。

常见的求解多目标规划问题的方法是为每个目标函数赋予权重，将多个目标函数线性加权为一个目标函数进行求解[15]。设置权重WC和WE，将目标函数fC和fE合并为一个目标函数f，即式(18)转换为式(19)进行求解：

[M2] minf=WC·fC+WE·fE

(19)

3 实验及分析

假设规划周期为360 d，某班轮公司在6条运营航线上配置8种类型集装箱船，船舶的经济航速设为18 kn，发船频率为每周一班。船用燃油的排放因子主要与船用燃油质量及船舶设计有关，简化起见，参照IMO公布的数据，笔者将排放因子设为每吨燃油消耗量排放二氧化碳3.114 4 kg[3, 16]。其余实验参数设定见表1、表2。

表1 船舶配置

表2 航线参数

表3 航线配船结果

表4 单箱燃油成本和单箱碳排放量

注：∂vr表示航线上单箱燃油成本；βvr表示单箱碳排放量。

根据表3中运量占比和运力占比这两列可以统计出，航线上88.95%运量由35艘8 000～18 000 TEU船舶完成，运力占比为31.25%的25艘10 000～18 000 TEU船舶完成了76.14%的运量。

从表4中可以看出，船舶容量越大，其单箱燃油成本和单箱碳排放量越小。以航线5为例，18 000 TEU船舶的单箱燃油成本比13 000 TEU船舶低5.6%，比5 000 TEU船舶低33.3%，比3 000 TEU船舶低53.4%，比2 000 TEU船舶低62.6%；从单箱碳排放量来看，13 000，5 000，3 000，2 000 TEU船舶的单箱碳排放量分别是18 000 TEU船舶的1.1，1.5，2.1和2.7倍。

基于上述实验结果，对模型参数按照-75%，-50%，-25%，﹢25%，﹢50%，﹢75%调整大小，分析模型参数变化对[M2]中目标函数的影响，参数敏感性分析实验结果见表5。

表5 [M2]参数敏感性分析

从表5的实验结果中可以看出：

1)船舶的燃油消耗常数和货量需求这两个参数变动，将引起船舶运营成本和碳排放量大致同比例的变动；

2)燃油市场价格和船舶运营成本之间存在线性相关影响，和碳排放量之间则没有相关性；

3)港口使费、航次管理费、船舶租金和闲置成本对船舶运营成本和碳排放量影响可以忽略不计；

4)规划周期越长，船舶运营成本越小，这是由于较长周期内船舶在连续航次上运营，有利于提高船舶的利用率，减少船舶的往返航次数量，从而降低船舶运营成本和碳排放量；

5)航速和船舶容量这两个参数变动对目标函数产生的影响十分显著，为此进一步分析航速和运力结构与船舶运营成本和碳排放量之间的关系。

令航速Svr变动区间为[1,40]，ΔSvr=1 kn，分析航速变化对船舶运营成本与碳排放量的影响，如图2。

图2 航速变化对船舶运营成本与碳排放量产生的影响Fig.2 Effect of speed changes on the cost of shipping operation and carbon dioxide emissions

由图2中船舶运营成本曲线可以看出：

1)航速在区间[1,3]内变动时，船舶运营成本为0，这是由于航速过低导致运力不足无法满足运量需求，模型无可行解。

2)航速从4 kn提升至14 kn时，船舶运营成本不断下降，计算数据显示，航速值在区间[4,14]时，班轮公司通过向航运市场租赁运力弥补自有运力不足以完成运输任务。

4)航速由14 kn增加至40 kn时，船舶运营成本迅速增加，主要是由燃油消耗成本随着航速增加而呈幂次方的增长引起。与船舶运营成本曲线相比，碳排放量曲线明显更加陡峭，这反映了随着航速增加，碳排放量的增速高于运营成本的增速。这意味着，班轮公司采用高航速策略以提高客户服务水平的同时，产生对环境的影响代价要高于自身经营成本代价，即班轮公司的服务水平与碳排放这两个经营目标之间存在效益背反关系。通过计算可以得出，在经济航速18 kn时，碳排放总量要减少10%，则航速要降低6%，同时引起平均航次时间增加5%，船舶运营总天数增加8%。

在保证总运力大体不变的条件下，调整各种船型的船舶数量，分析班轮公司运力结构改变对模型目标函数的影响。将5 000 TEU及以下级别船舶定义为“小型船舶”，8 000～10 000 TEU级别船舶定义为“中型船舶”，13 000 TEU及以上级别船舶定义为“大型船舶”。考虑航运市场上船舶大型化发展趋势，减少中小型船舶比例，增加大型船舶比例，对各种船型的船舶数量进行调整，运力结构改变对船舶运营成本与碳排放量产生的影响实验结果见表6。

表6 运力结构调整实验结果

从表6可以看出，在满足航线上同等货量需求的情况下，减少中小型船舶数量和增加大型船舶数量的运力配置方案，可以减少航线上投放船舶的总数量，并降低了船舶运营成本和碳排放量。其主要原因是更大容量的大型船舶所需运营航次数少于中小型船舶。这也意味着，配置大型船舶为主的运力结构不仅可以减少班轮公司的运营成本和碳排放量，也有利于船队投资总成本的降低。

4 结 论

针对班轮公司的航线配船问题，兼顾班轮公司的经济效益和环境效益，考虑船舶运营成本和碳排放量的最小化，建立了一个双目标规划模型；通过算例验证模型的可行性和有效性，并得出以下结论：

1)与容量更小的船舶相比，大型船舶具备燃油成本和碳排放量更低的双重优势；

2)通过提升船舶的性能技术以减少其燃油消耗常数、减速航行以及配置大型船舶为主的运力结构这3种方法是显著减少船舶运营成本和碳排放的有效措施。

值得说明的是，笔者建立的数学模型仅从单个班轮公司出发，未考虑航运联盟中运力合作对船舶运营成本和碳排放量的影响，基于全球航运网络的视角对航线配船进行优化将是进一步研究的重点。

[1] SMITH T W P, JALKANEN J P, ANDERSON B A, et al. Third IMO GHG Study 2014[R]. London: International Maritime Organization,2014.

[2] 俞姗姗,汪传旭.不同碳排放调控政策下的船舶航速优化[J].大连海事大学学报,2015,41(3):45-50. YU Shanshan, WANG Chuanxu. Speed optimization under different carbon emission control policy[J].JournalofDalianMaritimeUniversity,2015,41(3):45-50.

[3] KONTOVAS C A. The green ship routing and scheduling problem (GSRSP): a conceptual approach[J].TransportationResearchPartD:TransportandEnvironment,2014,31(5):61-69.

[4] MUIDER J, DEKKER R. Methods for strategic liner shipping network design[J].EuropeanJournalofOperationalResearch,2014,235(2):367-377.

[5] GELAREH S, MENG Qiang. A novel modeling approach for the fleet deployment problem within a short-term planning horizon[J].TransportationResearchPartE:LogisticandTransportationReview,2010,46(1):76-89.

[6] 李佳,徐奇,殷翔宇,等.基于双目标规划和遗传算法的航线配船优化[J].大连海事大学学报,2010,36(4):27-30. LI Jia, XU Qi, YIN Xiangyu, et al. Optimization of fleet deployment based on bi-objective programming and genetic algorithm[J].JournalofDalianMaritimeUniversity,2010,36(4):27-30.

[7] FAGERHOLT K, JOHNSEN T A V, LINDSTAD H. Fleet deployment in liner shipping: a case study [J].MaritimePolicy&Management:TheFlagshipJournalofInternationalShippingandPortResearch,2009,36(5):397-409.

[8] GELAREH S, PISINGER D. Fleet deployment, network design and hub location of liner shipping companies[J].TransportationResearchPartE:LogisticandTransportationReview,2011,47(6):947-964.

[9] CHRISTIANSEN M, FAGERHOLT K, NYGREEN B, et al. Ship routing and scheduling in the new millennium[J].EuropeanJournalofOperationalResearch,2013,228(3):467-483.

[10] WANG Shuai’an, MENG Qiang, LIU Zhiyuan. Bunker consumption optimization methods in shipping: A critical review and extensions[J].TransportationResearchPartE:LogisticandTransportationReview,2013,53(4):49-62.

[11] 许欢,刘伟,尚雨廷.低碳经济下班轮航线配船模型及其算法实现[J].交通运输系统工程与信息,2013,13(4):176-181. XU Huan, LIU Wei, SHANG Yuting. Fleet deployment model for liners under low-carbon economy and its algorithms implementation[J].TransportationSystemsEngineeringandInformation,2013,13(4):176-181.

[12] 薛颖霞,邵俊岗.低碳经济背景下班轮航线配船[J].中国航海,2014,37(4):115-119. XUE Yingxia, SHAO Jungang. Fleet deployment for liner shipping in low-carbon economy[J].NavigationofChina,2014,37(4):115-119.

[13] 叶德亮,黄有方,胡坚堃.低碳模式下班轮航线配船问题研究[J]. 华中师范大学学报(自然科学版),2015,49(2):322-326. YE Deliang, HUANG Youfang, HU Jiankun. Study on fleet deployment question for liners with low carbon pattern[J].JournalofCentralChinaNormalUniversity(NaturalScience),2015,49(2):322-326.

[14] FAGERHOL K, LAPORTE G, NORSTAD I. Reducing fuel emissions by optimizing speed on shipping routes[J].TheJournaloftheOperationalResearchSociety,2010,61(3):523-529.

[15] HU Zhihua . Multi-objective genetic algorithm for berth allocation problem considering daytime preference[J].Computers&IndustrialEngineering,2015,89:2-14.

[16] WAN Zheng, ZHU Mo, CHEN Shun, et al. Pollution: three steps to a green shipping industry[J].Nature,2016,530(7590):275-277.

Fleet Deployment for Liner Ship Based on Bi-objective Programming

PAN Jingjing1, 2

(1. College of Transportation and Civil Engineering, Fujian Agriculture and Forestry University, Fuzhou 350002, Fujian, P. R. China; 2. College of Information Engineering, Shanghai Maritime University, Shanghai 201306, P. R. China)

In order to optimize the allocation of resources of liner ship companies, a fleet deployment model based on bi-objective programming was established to minimize the total costs of shipping operation and carbon dioxide emissions in the planning period. And then the model was solved by Gurobi. The feasibility and effectiveness of the model was verified by numerical experiments. Computational results show that comparing with ones with smaller capacity, the ship with large capacity is more competitive in single box cost and generates less carbon dioxide emissions, which will be better for the environment protection. Three methods of ship capacity structure, such as reducing the ship’s fuel consumption constants by improving the ship technology, slow steaming and the main configuration of large ship, are effective measures to significantly reduce ship operation costs and carbon dioxide emissions.

traffic and transportation engineering; shipping network; fleet deployment; carbon dioxide emissions; bi-objective optimization

2015-12-22；

2016-04-07

福建省社科规划项目(FJ2015C107)；国家自然科学基金项目(71471109)

潘静静(1984—)，女，福建仙游人，博士，主要从事物流与供应链管理、航运大数据分析方面的研究。E-mail: pan_jingjing@126.com。

10.3969/j.issn.1674-0696.2016.06.28

U692.3；F550.6

A

1674-0696(2016)06-136-05