0.   引言

世界海运效率自20世纪60年代初兴起国际集装箱海上运输以来大幅提升。尽管集装箱船在世界商船总吨位中占比不到10%, 但却占杂货运量的25%, 有些发达国家的集装箱运输比重甚至已超过80%^[1]。以集装箱运输为代表的现代化运输方式已成为国际班轮航线上使用最广泛的运输方式之一。特别是2008年全球金融风暴的到来, 一些大型集装箱班轮运输公司相继采取了一系列应对措施, 如调整航线, 优化航线上的船舶配置, 加强班轮公司战略联盟, 强化供应链网络和腹地货源等来规避风险, 提高自身竞争力^[2-4]。对航运公司而言, 要想在激烈竞争的集装箱班轮运输市场中脱颖而出, 势必要处理好一系列决策问题: 如何合理地将船队中不同船型(吨级) 的集装箱船舶配置到各条班轮航线上, 做到不仅满足各条航线在技术营运方面的要求, 还保证了运输服务质量以及最佳经济效益, 即集装箱班轮航线配船问题。

Ronen研究了在自有船舶不足的情况下, 通过调节租赁船舶和班次以进行补充运输来完成运输任务, 并提出了一些制定船期的方法与航运公司的运营战略^[5]; Taramillo等为有效解决配船问题, 采用了非线性规划法和拉格朗日乘数法, 建立了以船舶速度为目标函数的非线性模型^[6], 但由于整个模型计算过程复杂, 对于经营状况测算实用性不强, 而且运输公司投入在使用模型上的成本极大, 不利于其追求成本最低化的目的; Cho等使用线性规划有关方法配置散货和油轮船队运输, 选取适当的船型与不同的船型数量组合形成新的船队, 分别配置到各条航线上, 基于货运量、船型、航线、港口限制几个因素的考虑, 证实了运营成本和航线配船对港口限制敏感, 而对货运量并不敏感^[7-8]; Gelareh等提出了集装箱班轮航线配船问题, 并在集装箱航线配船的优化和运营决策方向上进行了初步研究^[9]; 徐天芳等基于运力平衡方法提出了两点往返航线配船的数学模型, 为沿海集装箱运输公司投放运力研究奠定了基础^[10]; 靳志宏等构造了基于港口时段与往返航班的时空网络, 建立了0-1整数规划数学模型对班轮船舶调度问题进行了系统研究, 利用蚁群算法求解模型, 并用邻域搜索技术提高求解效率^[11]; 王文等以一定营运期内航线的运营利润为目标, 以船舶载重能力、集装箱的箱型与数量、港口装卸效率为约束条件建立了班轮运营经济优化模型, 结合隐函数求导和函数极值方法进行求解^[12-13]; Meng等提出基于航线运营者、货主和政府三方博弈关系的短途班轮航线优化模型, 应用用户平衡原理, 优化了航线配船与航线结构^[14]; 靳志宏等研究了多航线多船型配船与租船的联合优化问题, 建了混合整数规划模型, 通过小规模问题试验确定了模型与算法参数^[15]; 徐骅等运用博弈论方法分析了集装箱班轮航线的船舶配置决策行为, 提出了多航线多船型配船与运力闲置的联合优化问题, 为航线配船问题提供了新的解决手段^[16]。

国内外大多数针对航线配船模型的研究基本都集中在寻求相对较好的航线配船方案, 但由于市场的无形控制, 航运市场跟随着国际形势转变而变化, 要想准确把握投资尺度显然比较困难, 航运公司特别是班轮公司应当顺应市场, 合理科学地经营船队与有效配置资源。本文借鉴已有相关模型的合理性, 结合班轮航运的实际情况与调度优化目标, 从减小班轮公司经营变动成本入手, 考虑了货运量、港口使用费、燃油成本、过河费等成本, 建立了航线配船的数学模型, 利用蚁群算法求解, 并选取了3条具有代表性的航线进行实例验证。

1.   航线配船数学模型

1.1   问题描述

本文从实际经营角度出发, 在航线、船舶船型和数量既定且满足货运需求的条件下, 以船舶经营成本最小作为目标函数, 建立能够适应发展需求的国际班轮运输航线配船的优化模型, 使优化后的模型更加符合实际需求, 并且对航线配船起到一定的参考作用。运费率随市场调节而上下波动, 在船舶运力能够满足货运需求的情况下, 即货运量一定时, 收入也难以确定, 所以在计算利润最大化时, 可以转化成计算经营成本最小化。而船舶的航线成本分为固定成本和变动成本, 固定成本一般是不变的, 考虑降低航线成本只要降低变动成本就可以实现, 本文主要考虑变动成本中的燃油成本、港口使用费和过河费。

1.2   动态航线配船模型

动态计划模型中原始问题决定各个不相干的步骤, 各个不相干的步骤决定各种状态。在这种情况下, 模型的求解问题就是规划航线的一系列预选呼叫港口上的问题。基于动态计划模型的最佳配船模型建立的假设条件为: 各个港口的可用泊位时窗已知; 行驶速度可随船舶规划而在一定程度内进行调整; 各个港口的货运量包括途经货物可大致预计; 各个港口的终端集装箱运量可随航运公司的需求而在一定程度内进行调整。

基于上述假设, 各个步骤的状态与下一个呼叫港口大致规划的诸多重要因素息息相关。最佳配船问题分解成若干个呼叫港口若干个步骤的行驶速度、码头起重机调度和缓冲时间决策。各个步骤的一些因素都与下一步骤有关。港口i的状态的相关因素有离开港口i的缓冲时间O_i、港口i到下一个港口i+1的行驶速度V_{i, i+1}、到达港口i+1的缓冲时间I_i+1。港口i的估计时间窗W_i的相关因素有到达港口i的估计抵达泊位时间B_i与离开港口i的估计起航时间J_i。由以上分析即有

式中: B_i+1为到达港口i+1的估计抵达泊位时间; P_i为离开港口i的引航时间; S_i+1为港口i到港口i+1的行驶时间; T_i+1为港口i与港口i+1所在区位的时差; C_i+1为到达港口i+1的引航时间; D_i+1为港口i与港口i+1间的距离; L为总的集装箱搬移次数; M_i为港口i的集装箱搬移占比; N为待定系数, 当规划线路是大洋一边至另一边的跨洋运输服务时, N取4, 当规划路线是摆钟式往返运输服务时, N取6, 当规划路线是全球来回返往运输服务时, N取8;F_i为港口i的装卸集装箱时间; A为船队平均运力; U为船队的平均期望利用率; E为标箱占比。

由式(1) ~ (5) 可求出估计时窗, 其中P_i和V_{i, i+1}是2个关键因子。动态航线配船模型在任意步骤都根据可用泊位时窗估计规划航运时窗, 以变动最小为目标确定行驶速度、起重机调度和缓冲时间。

针对航线配船问题, 必须建立一个恰当的还原关系, 以实现可用泊位时窗与估计泊位时窗间的即时总变化最小。解决程序按步骤的正向或逆向进行, 每次都会获得这一步骤的最佳解决方式直到最终一步。航线配船解决程序见图 1。

图  1  解决程序

Figure  1.  Settlement program

下载: 全尺寸图片 幻灯片

航线配船模型能够在泊位时窗限制情况下, 帮助规划者做出更好的决策, 实现公司伙伴或联盟服务网络的整合, 获得更高效的轴心操作机制, 使运输紧密衔接, 服务水平得到提升, 同样可应用于内陆货运计划和合作伙伴要求而重调时窗, 促使操作更加高效。

2.   优化模型

2.1   模型假设

根据航运公司的实际经营情况, 为了有效解决班轮航线配船问题, 本文提出以下几点假设。

(1) 假设在某一时期内, 航运公司的船舶船型和数量既定, 即在某个特定的经营时间段内, 航运公司没有购进或卖出船舶。

(2) 假设航线既定, 并且沿途的挂靠港口排序既定, 相邻两次经过同一挂靠港口的间隔时间, 即发船间隔既定, 港口挂靠时间、运河通过时间既定, 同一航线上经过各个挂靠港口的次数一致。

(3) 同一船型船舶在各相邻港口间的运行速度一致, 不考虑货物的装载状态, 即舱位利用率对船舶航行速度没有影响。由于集装箱舱位利用率比其他运输方式低很多, 舱容减少对船舶影响很小, 因而航行速度基本保持不变。

2.2   优化模型的提出

对于班轮航线配船问题, 航运公司需要考虑如何合理调度船队中的每艘船, 选择合理的航线完成不同航班的运输任务, 在降低运营成本的同时实现经济和社会效益, 由以上分析即有

式中: Z为经营成本; b_uv为船舶u在航线v上的港口使用费; r_uv为船舶u在航线v上的过河费; h_uv为船舶u在航线v上的燃油成本; X为船舶总数量; x_uv为船舶u在航线v上的数量; n为可供选择的船舶数量; m为可供选择的航线数量; Q为船舶总运量; q_uv为船舶u在航线v上的运量。

假定船舶总量和货物总量一定, 为了实现利润最大化, 达到航线配船的最终目的, 就要使经营变动成本降到最低, 即将分配到各个航线上经营的船舶满足燃油成本、过河费和港口使用费三者总和最小。

2.3   优化模型参数

2.3.1   港口使用费

货物装卸费用是按船舶(货物) 净吨与某一比例的乘积收取的, 而除装卸费以外的其他港口费用虽然种类繁多, 但主要费用也是按船舶净吨乘以一定比例所得的计算结果来收取, 船舶净吨是港口使用费的重要参数。航舶u在航线v上的港口使用费b_uv为

式中: G_u为航舶u的净吨数; P_v为航线v的单位收入; k为平均港口使用费率。

2.3.2   燃油成本

燃油成本主要与船舶日燃油消耗量以及船舶航行距离有关。根据模型的假设条件, 同一船型船舶在各个相邻港口间的航行速度一致, 所以对于同一船型的日燃油消耗量是一定的。船型和航线里程是某一船型船舶日燃油消耗量的最主要参数。航舶u在航线v上的燃油成本h_uv为

式中: d_u为航舶u的日均燃油消耗量; s_v为航线v的里程; f为燃油价格; v_u为航舶u的航行速度。

2.3.3   过河费

过河费是通过苏伊士运河和巴拿马运河时支付的费用, 若航线的目的港口分布在欧洲或美洲东海岸, 则需要交纳此项费用。巴拿马运河与苏伊士运河过河费收取方式不一样, 巴拿马运河过河费主要根据巴拿马运河吨来收取, 苏伊士运河过河费则根据船舶船型的净吨来收取。经过换算, 航舶u在航线v上的过河费r_uv为

式中: f_s、f_b分别为苏伊士运河和巴拿马运河的过河费率。

3.   蚁群算法

蚁群算法以类似蚂蚁觅食的方式在求解复杂组合优化问题上取得了良好的仿真结果^[17-18]。蚁群算法的优势在于避免了冗长的编程和筹划, 程序本身是基于一定规则的随机运行来寻找最佳配置, 程序可以通过蚂蚁寻找食物时的信息素原理, 不断地去修正原来的路线, 使整个路线越来越短, 从而使可行解逐步收敛于最优解。

针对班轮航线配船问题, 假设蚁群共有M只蚂蚁, 其中蚂蚁m₁已到达第g个阶段, 在之前的每个阶段h (h=1, 2, …, g-1), 将船舶u分配给航线v。在第g个阶段, 航线v选择船舶u的概率A_uv为^[19]

式中: τ (u, v) 为船舶u在航线v上的信息素浓度; L_g为在当前阶段g的可选班轮船舶构成的集合。

由于部分船舶已经分配给了第1个到第g-1个往返航线, 且又需要避免航线之间的时间冲突, 因此, L_g中的部分船舶将不能用于当前往返航线的调度。可见, 可选船舶集合L_g依赖于蚂蚁之前的搜索路径。通过逐步搜索, 可以构造出可行的配船方案, 蚂蚁根据配船方案的质量更新相应路径上的信息素浓度。信息素全局更新规则为

式中: τ (u, v) ₂、τ (u, v) ₁分别为船舶u为航线v上的更新前后的新旧信息素浓度; 为船舶u在航线v上的蚂蚁m₁释放的信息素浓度增量; Y为待定常数; 为蚂蚁m₁所构造的配船方案的目标函数值。

为了避免算法过快收敛于局部最优解, 在完成全局更新后, 需要引入信息素挥发机制, 以有利于蚂蚁探索新的解空间。挥发机制为

式中: ρ为信息素挥发系数。

当蚂蚁从第1个往返航线逐步搜索到最后1个往返航线, 就生成了1个可行的配船方案, M只蚂蚁同步搜索多次, 当蚂蚁搜索次数达到预定值, 算法终止, 算法流程见图 2。

图  2  算法流程

Figure  2.  Algorithm flow

下载: 全尺寸图片 幻灯片

在上述蚁群算法中, 为了提高搜索效率, 引入了邻域搜索技术^[20-21], 该技术针对给定的班轮船型配船方案, 随机选择其中的某个航线, 然后再从可选船舶集合中随机选择一个新的船舶。如果新方案优于已有方案, 则保留新方案; 否则放弃调整。

4.   计算结果分析

4.1   数据搜集

4.1.1   选取论证航线

针对远洋集装箱班轮运输形势, 考虑货运量、港口使用费、船队燃油成本、过河费, 本文选取3条具有代表性的航线, 搜集其2012年的实际运行数据进行验证。

航线1为东南亚—美国西部航线, 线路为蛇口—香港—横滨—长滩—西雅图—温哥华—横滨—神户—蛇口—香港, 见图 3; 航线2为中国—美国西部航线, 线路为新港—大连—青岛—上海—神户—长滩—奥克兰—横滨—神户—新港—大连—青岛—上海, 见图 4; 航线3为中国—美国东部航线, 线路为青岛—上海—宁波—横滨—纽约—波士顿—诺福克—青岛, 见图 5。

图  3  东南亚—美国西部航线

Figure  3.  Southeast Asia-Western America route

下载: 全尺寸图片 幻灯片

图  4  中国—美国西部航线

Figure  4.  China-Western America route

下载: 全尺寸图片 幻灯片

图  5  中国—美国东部航线

Figure  5.  China-East America route

下载: 全尺寸图片 幻灯片

4.1.2   船舶配置与基础数据

根据交通运输部水运科学研究院、中国远洋运输(集团) 总公司、上海远洋运输公司等搜集到3条航线的资料, 航线的船舶数据见表 1, 3条航线的基础数据见表 2, 3种船舶在各个航线上的成本(简称为船舶成本) 见表 3。

表  1  船舶数据

Table  1.  Ship data

下载: 导出CSV 

| 显示表格

表  2  航线数据

Table  2.  Route data

下载: 导出CSV 

| 显示表格

表  3  船舶成本

Table  3.  Ship costs

下载: 导出CSV 

| 显示表格

4.1.3   货运量与航线成本

2012年, 3条航线上的燃油消耗与货运量见表 4。各个船舶在各个航线上的成本(简称为航线成本) 是不同船舶航行在不同航线上产生的成本, 主要根据不同船舶在不同航线上的燃油消耗以及在港口停泊时产生的费用统计出的成本, 优化前的航线成本见表 5。

表  4  燃油成本与货运量

Table  4.  Fuel costs and freight volumes

下载: 导出CSV 

| 显示表格

表  5  优化前的航线成本

Table  5.  Route costs before optimization

下载: 导出CSV 

| 显示表格

4.2   优化成本分析

假定计算周期内的燃油价格为2 700元·t^-1, 按载货量计, 平均港口使用费为10元·t^-1, 3条航线均不通过苏伊士运河, 巴拿马运河过河费率为15元·t^-1, 航线分配见表 6, 优化后的总成本见表 7。

表  6  航线分配

Table  6.  Route distribution

下载: 导出CSV 

| 显示表格

表  7  优化后的航线成本

Table  7.  Route costs after optimization

下载: 导出CSV 

| 显示表格

将表 7与表 5的数据进行对比, 优化后的总成本为36 652.6万元, 降低了110.6万元, 下降了约3%。可见, 优化后的配船模型计算可获得总成本较低的配船方案, 有效节省了费用, 提高了经营效率。

4.3   成本对比分析

除了采用蚁群算法对相关数据进行分析之外, 同时采用遗传算法、模拟退火算法对相同的原始数据进行处理, 并将计算结果进行比较, 结果见表 8。

表  8  计算结果对比

Table  8.  Comparison of calculation results

下载: 导出CSV 

| 显示表格

由表 8可知, 相比于常见的遗传算法和模拟退火算法, 使用本文方法, 计算得到的成本最低。班轮航线配船优化模型可行, 蚁群算法在班轮航线配船模型优化领域内具有较好的优势。

5.   结语

本文在对传统集装箱航线配船模型比较分析的基础上, 考虑了货运量港口使用费、燃油成本、过河费, 建立了优化配船模型, 选取东南亚—美国西部航线、中国—美国西部航线、中国—美国东部航线等3条具有代表性的航线及其实际运行数据进行了实证分析。优化后的配船模型有效节省了费用, 提高了经营效率。该模型是基于航线确定、货运量确定的情况展开的, 而货运需求是不断变化的, 在未来的研究中需不断完善, 改进成为更具广泛适用性的模型, 为航运公司降低成本, 提高经济效益提供理论和现实依据。