基于环绕模式的近洋集装箱班轮航线优化

杨华龙，刘英，朱全英，张燕

(大连海事大学交通运输管理学院，辽宁大连 116026)

0 引言

集装箱班轮航线设计是班轮公司的重要战略决策，直接关系到航线配船和船型选择，对班轮公司的运营成本和效益产生长远的影响.随着近年来集装箱航运市场需求的剧烈波动和竞争的不断加剧，班轮公司如何依据运营区域内货流需求和港口条件，科学合理地优化设计班轮航线，引起业界和学界的高度关注.国内外学者已进行大量的相关研究，取得许多可喜的成果.AGARWAL等［1]利用时间网络拓展思想探讨船队规划和靠泊顺序的综合航线优化问题.SHINTANI等［2]考虑靠泊港口选择、靠泊顺序、航速和空箱调运等问题，对集装箱班轮航线进行优化设计.NICKEL 等［3]和 GELAREH 等［4]提出一种选择枢纽港口模式对航线网络进行优化.GEIR［5]设计一种传统船舶航线网络和“中心-分支”航线网络模型.MENG等［6-7]建立多阶段船舶舰队规划模型，并采用动态规划的方法进行求解.丁明明等［8]针对上海港、天津港和深圳港3大港口，建立集装箱出口中转港选择整数规划数学模型.董岗［9]通过班轮航线、港口评价、比例关系、社会距离和非对称层次矩阵对港口进行顾客选择、聚合链接、自我中心和层次结构分析，从而得出东北亚班轮航线的港口发展格局.吴文一［10]主要考虑系统最优情况下运输网络的优化.陈康等［11]针对航线网络与港口集装箱货运需求之间具有相互影响的动态反馈关系，建立航线收益最大化模型.计明军等［12]以枢纽港船舶限制时间和支线船舶容量为基础，分析轴辐式网络运输模式，建立支线集装箱运输混合整数规划模型.殷允健等［13]考虑船公司与竞争对手运营策略的动态博弈过程，对集装箱班轮发船间隔时间进行优化，以使船公司获得最大利益.已有研究大都集中在挂靠港口已明确的条件下对航线进行优化设计，而对近洋环绕模式下如何从候选港口中确定枢纽港和喂给港集合并确定港口挂靠顺序、喂给港与枢纽港间如何链接等方面的研究还很不充分.

为此，本文结合近洋环绕模式班轮干/支线运输特点，在满足区域内集装箱货运需求的前提下，以班轮公司收益最大化为目标，构建班轮航线优化设计模型，以便从候选港口中确定枢纽港和喂给港集合，确定集装箱船舶的干线运输航线及挂靠枢纽港顺序，并为每个喂给港确定与其相连的最优枢纽港及支线运输航线，从而为班轮公司在近洋区域内整体干/支线航线优化设计提供决策依据.

1 问题描述

由于班轮运输具有投资大、运营成本高的特点，为能够吸引更多的货主，培养更多的忠诚客户，班轮公司在其运营的近洋区域内一般都采用“中心-分支”港的环绕模式设计班轮航线.该模式能解决航线上的货流不平衡问题，提高船舶舱位利用率和集装箱利用率，其干支线网络见图1.

图1 干支线网络

从图1可见:每个枢纽港可与多个喂给港相连，但每个喂给港仅能连接一个枢纽港;干线上船舶按一定顺序依次挂靠枢纽港，形成一个有向的闭环.“中心-分支”环绕模式包含两种航段:由两个枢纽港连接的枢纽航段和由一个枢纽港与一个喂给港连接的支线航段.

因此，基于环绕模式的班轮航线设计问题可以表述如下:班轮公司在其运营的近洋区域内，通过调查分析所有候选港口之间的集装箱班轮的航行成本、港口使费、集装箱装卸成本等，分析预测港口间一定时期内集装箱运输需求量和运价，在满足集装箱货物运输需求的前提下，以班轮公司效益最大化为目标，优选出合适的枢纽港，以环绕的形式将各枢纽港连接起来形成班轮干线运输线路(简称直运线路);再对余下的每个喂给港，选出其最合适的一个枢纽港，与之相连形成支线运输线路，在这些支线上，班轮公司可另派支线运输船舶承运或将集装箱货物转给其他支线船公司承运(这里统称为转运).最终，班轮公司可通过直运或转运方式完成近洋区域内所有港口间的集装箱货物运输.

2 模型建立

假设某班轮公司在覆盖多个港口的某近洋区域内经营班轮运输业务，不失一般性，本文引入以下符号:Ω为所有候选港口的集合;Ωm为枢纽港集合;wij为从港口 i到 j的集装箱运输需求量，i，j∈Ω;Lij为港口i，j对间的距离;Ct为集装箱船舶航行时的单位费用(包括船舶航行费用和航行期间的船舶成本等);fij为从港口i到j的集装箱单位运价;λ为转运因数，表示班轮公司需要将支线部分的运输收入支付给支线转运公司的比例;tij为船舶从港口i到j的航行时间;W为船舶装载集装箱容量;Pi为船舶在枢纽港i的挂靠费用(包括港口使费和停靠期间的船舶成本等);Sij为船舶从枢纽港i驶向紧邻的枢纽港j的0-1变量;Xij为将集装箱货物从枢纽港i运向枢纽港j的0-1变量;Yij为将集装箱货物从喂给港i运向枢纽港j的0-1变量;Zij为将集装箱货物从枢纽港i运向喂给港j的0-1变量.

根据上述问题描述，可建立以下基于环绕模式的近洋班轮航线优化设计模型M1:

在模型M1中:式(1)表示班轮运输总收益最大，即运输总收入减去班轮航行成本和集装箱转运成本后最大;式(2)和(3)表示枢纽港之间连接成环绕航线，即每个枢纽港进向(Inbound)和去向(Outbound)分别都有且仅有一个枢纽港与之相连;式(4)表示班轮容量约束，即班轮在干线各航段所装载的集装箱总量不能超过集装箱船舶的最大装载容量限制;(5)～(8)为变量的0-1约束.

3 模型求解

模型M1为非线性模型，利用一般算法很难求解，为此本文结合班轮运输实际情况设计以下求解步骤.

步骤1 假设班轮公司安排船舶遍历挂靠所有港口(此时各港口均为枢纽港)，Ωm=Ω，不存在集装箱货物转运情况.集装箱班轮运输成本由干线上船舶航行时的费用和挂靠港口时的费用两部分组成，这样原问题便可简化为求解等价的运输成本最小化问题M2.

在模型M2中:式(9)表示班轮运输总成本最小;式(10)和(11)表示各港口之间连接成环绕航线;式(12)为班轮容量约束;式(13)为变量的0-1约束.很显然，模型M2是一个典型的在完全有向图中搜索一条具有最小权值和的Hamilton回路问题，亦即旅行商问题(Traveling Salesman Problem，TSP).求解模型M2，便可得到初始的班轮运输优化航线，即船舶挂靠各港口的顺序.计算模型M2的目标函数便可得到班轮公司一个航次的总成本，记为C0.此时班轮公司的航次总收益为

步骤2 计算与每一枢纽港k相关的收益为

选取收益最小的一个港口，记为港口k0，同时把求解模型M2所得的最优航线中与港口k0相连接的进向和去向两个港口分别记为和.去除港口k0后，将和直接相连接，形成新的环绕式干线.此时，令 Ωm=Ωm- { k0}.

步骤3 在Ωm中选取与港口k0距离最近的一个港口，记为 k′0.将 k0作为喂给港并与相连，形成支线.

步骤4 计算在新形成的干线和支线网络下的班轮运营费用为

比较 C′和 C0.若 C′＜ C0，则令 C0=C′，转入步骤2.

步骤5 确定最终枢纽港集合和喂给港集合，并得到优化的班轮航线以及模型M1中的所有决策变量 Sij，Xij，Yij和 Zij的值，从而可根据模型 M1 中的目标函数求得班轮公司的最终总收益.

4 算例分析

假定某班轮公司在中国—东南亚近洋区域内的12个港口间开展班轮运输业务，选用2 400 TEU的集装箱船投入干线运营，支线则采用转租方式.船舶航行时的单位费用为30美元/n mile，船舶挂靠各港口的费用均为25 000美元.各港口对间的集装箱运输需求量(经预测所得到的在一定时期内较稳定的 需求量)、距离和单位集装箱运价分别见表1～3.

表1 港口对间的集装箱运输需求量 TEU

表2 港口对间的距离 n mile

表3 港口对间的单位集装箱运价 美元/TEU

为求解上述问题，本文采用MATLAB语言编程实现上述算法步骤.当所有港口都作为枢纽港时，由步骤1可得初始优化航线，见图2(a).此时根据式(14)可得班轮公司的航次总收益为3 286 665美元.当给定转运因数λ=0.95时，按上述算法步骤进行迭代求解，可得最终优化航线见图2(b).

图2 初始和最终优化航线

由此可得，班轮公司的优化航次总收益为3 335 742.5美元.与初始优化航线方案相比，班轮公司收益可增加49 077.5美元.

5 结束语

本文基于环绕模式的近洋集装箱班轮航线优化设计问题，以班轮公司收益最大化为目标，在假定一定时期内集装箱运输需求比较稳定的情形下，构建班轮航线优化模型，设计模型的求解算法，以便从区域内候选港口中确定枢纽港和喂给港集合，确定集装箱船舶的干线运输航线及挂靠枢纽港顺序，并为每个喂给港确定与其相连的最优枢纽港及支线运输航线.算例分析表明，本文构建的模型和算法简便易行，而且经过优化后的航线可为班轮公司减少运营费用，同时也能大大提高班轮公司的航次总收益.

考虑到区域内集装箱运输需求的不确定性和市场竞争性等因素，下一步应在考虑班轮航次周期时间约束、需求不确定以及航运竞争条件下，进行集装箱班轮航线的优化设计.

［1]AGARWAL R，ERGUN Ö.Ship scheduling and network design for cargo routing in liner shipping［J].Transportation Science，2008，42(2):175-196.

［2]SHINTANI K，IMAI A，NISHIMURA E，et al.The container shipping network design problem with empty container repositioning［J].Transportation Research Part E:Logistics＆ Transportation Review，2007，43(1):39-59.

［3]NICKEL S，PISINGER D.Liner shipping hub network design in a competitive environment［J].Transportation Research Part E:Logistics＆ Transportation Review，2010，46(6):991-1004.

［4]GELAREH S，MENG Qiang.A novel modeling approach for the fleet deployment problem within a short-term planning horizon［J].Transportation Research Part E:Logistics＆ Transportation Review，2010，46(1):76-89.

［5]GEIR B.A multi-start local search heuristic for ship scheduling:a computational study［J].Computers ＆ Operations Res，2007，34(3):900-917.

［6]MENG Qiang，WANG Tingsong.A chance constrained programming model for short-term liner ship fleet planning problems［J].OR Spectrum，2010，37(4):329-446.

［7]MENG Qiang，WANG Tingsong，WANG Shuai’an.Short-term liner ship fleet planning with container transshipment and uncertain container shipment demand［J].Eur J Operational Res，2012，223(1):96-105.

［8]丁明明，梁承姬.中国内陆集装箱出口中转港选择模型［J].上海海事大学学报，2012，33(4):39-44.

［9]董岗.基于班轮航线的东北亚港口发展格局［J].上海海事大学学报，2010，31(2):1-6，17.

［10]吴文一.港口对区域经济推动作用研究［J].交通企业管理，2008(2):54-55.

［11]陈康，杨忠振.港口和航线互动的集装箱航线优化模型［J].中国航海，2012，35(4):104-109.

［12]计明军，陈哲，王清斌.集装箱船舶支线运输航线优化算法［J].交通运输工程学报，2011，11(4):68-75.

［13]殷允健，赵刚.集装箱班轮发船间隔时间动态博弈模型及其应用——以应对“天天马士基”为例［J].上海海事大学学报，2012，33(4):52-56，63.