集装箱班轮服务网络优化和货运路径设计

胡坚堃 彭子良 黄有方

摘要：

为提高班轮公司的资源优化能力，解决航线选择、重箱运输路径、空箱调运路径、多类型船舶配置以及船速设定等问题，根据实际班轮运输组织方式的特征，构建多港挂靠和轴辐式混合网络，建立以运营总成本最小为目标的非线性混合整数规划模型。采用大M法把这个非线性模型转换成线性模型后通过CPLEX进行求解，并用中远集运在亚洲—大洋洲—欧洲区域的部分航线验证模型的有效性。通过灵敏度分析发现：港口装卸效率的提升对减少班轮公司运营成本效果显著;船舶的燃油成本与运营成本之间存在着相关性，故油价的持续上涨迫使班轮公司选择降速、配置更多的船舶来降低整体成本。

关键词：

水路运输; 船队运营; 混合整数规划; 班轮网络; 集装箱运输路径; 空箱调运

中图分类号： U692.3

文献标志码： A

Abstract：

In order to improve the resource optimization ability of liner companies and solve the issues such as route selection， heavy container shipping route， empty container repositioning， multitype ship configuration and ship speed setting， etc.， according to the characteristics of actual liner transportation organization mode， a multiportcalling and hubandspoke hybrid network is constructed， and a nonlinear mixed integer programming model with the objective of minimum total operating cost is established. The big M method is used to transform the nonlinear model into a linear model， and the CPLEX is used to solve the model. The validity of the model is verified using some routes of COSCO in the AsiaOceaniaEurope region. Through sensitivity analysis， it is found that the improvement of port loading and unloading efficiency has a significant effect on reducing the operating cost of liner companies， and that there is a correlation between fuel cost and operating cost of ships， so the continuous increase of oil price forces the liner companies to reduce speed and deploy more ships to reduce overall cost.

Key words：

waterway transportation; fleet operation; mixedinteger programming; liner network; container transportation route; empty container repositioning

0引言

近年來，班轮运力过剩、燃油价格上涨、船队配置不合理等问题凸显。在船队发展领域，大多数国内班轮企业仍然依靠管理者自身经验和常识制定班轮网络和船队调度决策，缺乏科学依据和说服力[1]。在学术领域，已有不少学者开展了相关研究。在班轮网络规划方面：CHUANG等[2]综合考虑重箱运输和空箱调运方案，采用了模糊遗传算法求解需求不确定的多港挂靠网络优化问题;宋向群等[3]研究了轴辐式运输网络中区域性网络系统的最小费用流问题，设计了蚁群优化算法进行求解;IMAI等[4]对比了轴辐式网络和多港挂靠网络，以成本最小为目标，探讨了不同船型的两种典型的航线网络方案;陈康等[5]考虑了航线网络与港口集装箱货运需求之间的关系，以航线收益最大为目标，开发了基于遗传算法的启发式算法来证明新的集装箱班轮网络优化模型能够有效提高航线运营效率;李建等[6]以每周运营成本最小为目标，设计了启发式算法解决空箱调运问题，并证明了对考虑空箱调运的班轮航线进行优化可减少班轮公司总成本;吴琼等[7]以CKYH联盟为例，建立了混合整数规划模型，并利用列生成算法和CPLEX提供了一种航运网络优化的新方法;杨华龙等[8]通过对航线货流量的分析预测，对中转制和直航制两种方案下的班轮航行时间进行了比较，并确定了对应的配船数;薛颖霞等[9]考虑了低碳背景下航运网络配船总成本和碳排放量，建立了双目标规划模型，实现了班轮公司节能减排的目的。在班轮船队调度方面，要解决的是将不同船型配置到不同的航线上使得收益最大或成本最小。MENG等[10]建立了运输需求不确定情况下的双层随机规划模型求解船队调度;寿涌毅等[11]在合理配置班轮和不存在时间冲突的条件下建立了01整数规划模型，并利用蚁群算法进行求解;杨立乾[12]考虑了船舶容量和时间限制，构建了船舶调度模型，并利用粒子群算法进行求解;靳志宏等[13]以总航行成本最小为目标函数，考虑现实因素建立了船队调度模型并进行求解;蔡佩林等[14]以中欧航线为例，建立了随机规划模型，并进行敏感度分析，最终得到了合理的船舶调度方案。

现有的研究对班轮网络中航线设置、船舶配载、船速设定、集装箱运输路径之间的相互关联性考虑较少。本文借鉴部分现有成果，对多港挂靠和轴辐式混合网络中的多类型船舶配置、重箱运输路径、空箱调运路径、船速控制等问题进行整体优化，以成本最小为目标，以船舶容量限制、每周发船频率、箱量平衡、满足运输需求等为约束条件，建立数学模型，设计相应的求解流程，并通过中远集运的部分实际航线进行验证和分析。

1问题描述

1.1班轮网络

班轮网络由港口和航线组成，本文设定的班轮网络为多港挂靠与轴辐式混合运输网络，即保留多港挂靠航线，并允许航线在枢纽港进行中转，见图1。图1中：圆形和方形分别代表两种不同类型的港口，其中圆形代表喂给港，方形代表枢纽港;港口A为港口C、G、F的枢纽港，港口B为港口D、E的枢纽港，集装箱的中转须通过喂给港所属的枢纽港完成;航线1、航线2、航线3和航线4均用港口序列表示;船舶在同一条航线上相邻两个港口之间的航行路段，称为航段，例如CG为航线1上的一个航段;每段弧上的数字为该航段的长度;船舶在同一条航线上任意两个港口之间的航行路程，称为航程，例如船舶从港口C到港口F的航行路程为航线1上的一个航程，航程由一个或多个航段组成。

1.2集装箱运输路径

在班轮网络中存在大量的重箱运输需求，单位重箱运输需求包括启运港、目的港和运输量。对于单位重箱运输需求，多条运输路径均可以满足。假设图1的网络中有一个从港口C到港口E重箱运输需求，则共存在5条运输路径：（1）通过航线2从港口C直达港口E，航程为5 037.50 n mile;（2）通过航线1从港口C直达港口E，航程为5 738.89 n mile;（3）通过航线3从港口C到港口B，在港口B中转后，通过航线4到达港口E，航程为6 995.82 n mile;（4）通过航线2从港口C到达港口B，在港口B中转后，通过航线4到达港口E，航程为14 513.34 n mile;（5）通过航线3从港口C到达港口B，在港口B中转后，通过航线2到达港口E，航程9 386.03 n mile。运输路径1为最短路径，但班轮公司为了均衡运输和充分利用船舶负载，可能将一部分重箱通过其他路径运输，这就需要更长的航程和时间，从而会降低班轮公司的服务质量，最终导致客户的流失。本文设置阈值为1.5，即若备选运输路径的长度是最短路径长度的1.5倍以上，则该备选运输路径不可行。在上述5条运输路径中，最短的航程为5 037.5 n mile，则允许的最长的航程为7 556.25 n mile，故路径4、5不可行。

由于贸易的不平衡，各港口会出现空箱缺少或多余的情况。空箱运输不同于重箱运输，它没有明确的运输出发地和目的地，只需满足网络中各港口的空箱需求和运输过程中船舶的容量限制，本文中不考虑有空箱与重箱比例约束的船舶积载规则。

1.3船速和配船

班轮公司的船队中有不同类型的船舶，本文以不同的容量代表不同的船舶类型，不同的船舶类型有不同的速度区间以及相应速度下的油耗率。假设发船频率为每周一次，即每条航线上，在每周的同一时刻从同一港口发船挂靠航线上的其他港口，则一个航次所需的时间为168×航线上所配的船数（单位为h，一周为168 h）。一般而言，船速越快，油耗越多，燃油成本越高，但是完成一个航次所需的时间越短，因此可通过减少在这条航线上配置的船舶数量来降低船舶的运行费用（包括保险、船员工资、维修费等）。

1.4系统流程框架

集装箱班轮网络设计和运输路径优化的求解流程见图2。已知数据为港口数据（包括港口类型和喂给港分配）、重箱运输需求（包括启运港、目的港和运输量）、航线数据（包括港口挂靠顺序和航段的长度）和船舶数据（包括船舶类型、每周运维费和油耗率）;航段集合由航线数据计算得到;港口空箱需求由港口數据和重箱运输需求计算得到;可行重箱运输路径由重箱运输需求、航线数据和设定的运输效率值计算得到;航程集合由可行重箱运输路径计算得到;船队配置、船速设定、运输路径上分配的箱量等为决策变量;总成本由空箱装卸费、重箱装卸费和船舶航行费构成。由此，建立统一的规划模型进行求解。

班轮公司的航运网络有多条航线，每条航线上需要配置足够多的船舶，以便提供具有一定频率的运输服务。班轮运输路径、航线配船数量、船速、空箱运输数量等通常会直接影响班轮公司总成本。根据船队运力和各港口集装箱运输需求确定各航线上船舶类型、配船数量、最佳船速等并最小化班轮公司运营成本是本文要解决的问题。

2建模与求解

2.1变量和参数定义

集合：港口集合为P，港口p∈P;航线集合为R，航线r∈R;航段集合为L，航段l∈L;航程集合为S，航程s∈S;航线r上的航程集合为Sr;集装箱港口重箱运输需求集合为O，具体港口需求o∈O;船舶类型集合为V，船舶类型v∈V; v型船的可行速度集合为Fv，船速f∈Fv;船舶可行运输路径集合为E，具体可行运输路径e∈E;集装箱港口重箱运输需求o的可行运输路径集合为Eo;包含航程s的可行运输路径集合为Es。

已知变量或计算可得变量：gr为航线r的长度;w（r）为航线r上的港口数量;δrsl表示在航线r上的航程s是否包含航段l，若包含则取1，否则取0;no为集装箱港口重箱运输需求o的运输量;hp为港口p由于贸易不平衡产生的空箱量;uv为v型船的容量;Cvf为v型船船速为f时的油耗率。

参数：α为每吨燃油的价格;β为每个重箱的装卸费;β～为每个空箱的装卸费;γ为港口装卸单位集装箱所需时间;χv为v型船每周的运行费用。

决策变量：xrv，若v型船配置在航线r上，则xrv取1，否则取0;xrvf，若配置在航线r上的v型船船速为f，则xrvf取1，否则取0;ys为通过航程s运输的重箱量;ye为在可行运输路径e上分配的重箱量;rp为在航线r上的港口p装载的空箱量;z～rp为在航线r上的港口p卸载的空箱量;arli为通过航线r上第i个航段运输的空箱量;Nr为在航线r上配置的船舶数量。

2.2优化模型

以班轮公司每周的总成本最小为目标建立模型：

min FF=r∈Rv∈V（χvNrxrv）+

r∈Rv∈Vf∈Fv（αCvfgrf-1xrvf）+

2βs∈Sys+β～r∈Rp∈r（rp+z～rp）

（1）

式（1）为目标函数，包含了非线性项Nrxrv。采用大M法，令prv=Nrxrv（表示航線r上配置的v型船的数量），通过等价变换，上述模型转化为混合整数线性规划模型：

min F|F=r∈Rv∈V（χvprv）+

r∈Rv∈Vf∈Fv（αCvfgrf-1xrvf）+

2βs∈Sys+β～r∈Rp∈r（rp+z～rp）

（2）

s. t.

Nr≤prv+M（1-xrv）（3）

Nr=v∈Vprv（4）

v∈Vxrv≤1（5）

f∈Fvxrvf=xrv（6）

no=e∈Eoye（7）

ys=e∈Esye（8）

hp=r∈R（rp-z～rp）（9）

2γs∈Srys+γp∈P（rp+z～rp）+

v∈Vf∈Fv（grf-1xrvf）≤168Nr

（10）

arli+rp（i+1）-z～rp（i+1）=arl（i+1），

i=1，2，…，w（r）-1

（11）

arlw（r）+rp1-z～rp1=arl1（12）

s∈Srδrslys+arl≤v∈Vuvxrv（13）

ys，ye，rp，z～rp≥0 （14）

Nr∈Z+∪{0} （15）

式（2）为等价目标函数，由4部分组成，分别为船舶运行费、燃油费、重箱装卸费和空箱装卸费;式（3）和（4）保证目标式的变换是等价的;式（3）保证一条航线上只能配置一种类型的船舶，其中M表示一个足够大的数;式（4）表示航线r上配置的船舶数量;式（5）保证每条航线上配置一种类型的船舶或者取消运营;式（6）保证每艘船在航线上以某一固定速度航行;式（7）使得每个重箱运输需求都得到满足;式（8）指出每个航程上通过的箱量等于所有包含该航程的运输路径上运输箱量的总和;式（9）确保每个港口的空箱需求得到满足;式（10）保证每周的发船频率，不等号左边3项分别是重箱装卸时间、空箱装卸时间和航行时间，不等号右边是一个航次所需的最长时间;式（11）和（12）保证每个港口的空箱进出量保持平衡;式（13）是船舶的容量限制，左边2项分别是重箱量和空箱量;式（14）和（15）为非负和整数的约束。

3模拟计算和结果分析

3.1计算环境与参数

以中远集运在亚洲—大洋洲—欧洲区域挂靠港口相对集中的部分航线为实例，对上述模型和求解方法进行验证。该班轮网络包含22个港口和12条航线。船队中有容量为3 000 TEU、5 000 TEU和10 000 TEU等3种类型的船舶，不同类型的船舶在不同船速下的油耗率不同。运算环境为：CPU，Intel i5 2.53 GHz; RAM，3GB。

3.2计算结果

随机生成200个重箱运输需求，每个需求的运输量在100～300 TEU范围内，油价为300美元/t，装卸单位空箱的费用为40美元，装卸单位重箱的费用为60美元，港口装卸单位集装箱所需时间为0.01 h。通过大M法将模型转化为线性规划模型，并利用CPLEX进行求解，具体优化结果见表1。由表1可得每条航线上配置的船舶类型、船舶数量、船速、运行时间及时间分布，其中原航线4上的运输任务可通过其他航线进行运输。

3.3灵敏度分析

3.3.1港口装卸速度

在油价和单位集装箱装卸费用不变的前提下，分析港口装卸单位集装箱所需时间（取0.01、0.02和0.03 h等3个值，相应的港口装卸速度分别为100、50和 33.33 TEU/h）对船队运行成本和船舶配置数量的影响，见图3和4。分析结果如下：（1）港口装卸速度的提升使得装卸时间在航行周期中占的

比例有明显的降低。（2）港口装卸速度的提升对集装箱运输路径基本没有影响，这是因为空箱和重箱的装卸费基本没有变化。（3）装卸时间的减少使得整个航行周期缩短，需要配置的船舶数量减少，船队运行总成本从1 629美元降到1 444美元，成本降低幅度比较明显。

图3港口装卸速度对船队运行成本的影响

图4港口装卸速度对船舶配置数量的影响

3.3.2油价

在港口装卸单位集装箱所需时间和装卸费不变的前提下，分析油价（分别为300、400、500、600美元/t）对船队运行成本和船舶配置数量的影响，见图5和6。分析结果如下：（1）油价的上升对集装箱运输路径基本没有影响，这是因为空箱和重箱的装卸费基本没有变化。（2）油价的上升直接造成了船舶燃油费的上升。（3）油价的上升迫使船舶选择低速航行以减少燃油费，但是会延长整个航行周期，需要配置的船舶数量会增多，这意味着一部分燃油费被转嫁至船舶运行费，从而达到整体最优。

4结论

本文通过模拟班轮企业运营环境中的班轮网络特征，创新性地将航线选择、重箱运输路径、空箱调运路径、船舶配置方案、最优船速这5个要素进行了整体优化，建立了非线性混合整数规划模型，用大M法将该非线性模型等价转化为线性模型后用CPLEX进行求解，并用中远集运的部分航线对模型

和算法进行验证。通过分析发现：港口装卸效率的提升对减少整体成本效果显著;船舶的燃油成本与运行成本存在着相关性，故油价的持续上涨迫使班轮公司选择降速、配置更多的船舶使整体成本降低。

海运过程中产生的碳排放是造成环境污染的重要原因。碳排放量的产生跟油耗量有关，油耗量又与船速密切相关，但是从油价敏感度分析结果看，尽管油价从300美元/t上涨到600美元/t，但是船舶的配置数量没有明显的增多，这意味着船速没有明显的下降，故通过纯市场调控进行节能减排收效甚微，如何制定有效的政策措施是下一步努力的方向。

參考文献：

[1]杨秋平， 谢新连， 赵家保. 船队规划研究现状与动态[J]. 交通运输工程学报， 2010， 10（4）： 8590.

[2]CHUANG T N， LIN C T， KUNG J Y， et al. Planning the route of container ships： a fuzzy genetic approach[J]. Expert Systems with Applications， 2010， 37（4）： 29482956. DOI： 10.1016/j.eswa.2009.09.040.

[3]宋向群， 张鹏， 郭子坚. 基于蚁群算法的港口集装箱运输网络径流优化[J]. 大连理工大学学报， 2007， 47（6）： 853857.

[4]IMAI A， SHINTANI K， PAPADIMITRIOUS S. Multiport vs.HubandSpoke port calls by containerships[J]. Transportation Research Part E： Logistics and Transportation Review， 2009， 45（5）： 740757. DOI： 10.1016/j.tre.2009.01.002.

[5]陈康， 杨忠振. 港口和航线互动的集装箱航线优化模型[J]. 中国航海， 2012， 35（4）： 104109.

[6]李建， 韩晓龙. 考虑空箱调运的远洋班轮航线优化[J]. 广西大学学报（自然科学版）， 2016， 41（5）： 14491456. DOI： 10.13624/j.cnki.issn.10017445.2016.1449.

[7]吴琼， 郑士源， 朱太球. 基于列生成算法的集装箱班轮运输网络优化[J]. 上海海事大学学报， 2014， 35（1）： 2934. DOI： 10.13340/j.jsmu.2014.01.007.

[8]杨华龙， 陈晓东. 大陆北方/台湾班轮航线方案优化研究[J]. 系统工程理论与实践， 2001（3）： 112115.

[9]薛颖霞， 邵俊岗. 低碳经济背景下班轮航线配船[J]. 中国航海， 2014， 37（4）： 115119.

[10]MENG Qiang， WANG Tingsong， WANG Shuaian. Shortterm liner ship fleet planning with container transshipment and uncertain container shipment demand[J]. European Journal of Operational Research， 2012， 223（1）： 96105.

[11]寿涌毅， 赖昌涛， 吕如福. 班轮船舶调度多目标优化模型与蚁群算法[J]. 交通运输工程学报， 2011， 11（4）： 8488.

[12]杨立乾. 基于轴辐式网络的集装箱支线运输多船型船舶调度模型[J]. 中国管理科学， 2015， 23（S1）： 860864.

[13]靳志宏， 解玉真， 李阳， 等. 集装箱支线运输船舶调度优化问题[J]. 中国航海， 2008， 31（4）： 415419.

[14]蔡佩林， 曾艳英， 涂建军. 基于机会约束规划的集装箱船舶调度研究[J]. 物流技术， 2013， 32（13）： 303306. DOI： 10.3969/j.issn.1005152X.2013.07.098.

（编辑赵勉）