不确定箱量下内河集装箱班轮航线动态配载决策

李 俊， 张 煜， 计三有， 马 杰

（1.武汉科技大学 汽车与交通工程学院，湖北 武汉430081；2.武汉理工大学 物流工程学院，湖北 武汉430063；3.武汉理工大学 航运学院，湖北 武汉430063）

0 引言

内河集装箱班轮由于体型较小、容量有限，船舶稳性对配载计划十分敏感，且与班期相比船方往往更强调舱容利用率。同时，内河集装箱班轮运输中，海关抽检可能导致外贸箱发生箱量变化，班轮航线配载决策需要不断考虑箱量变化影响，是一个动态决策问题。

已有的集装箱班轮航线配载决策理论大多研究海运船舶，往往假设船舶在航线上各港口节点的作业集装箱信息已知来制定航线配载方案，仍属于静态决策的范畴。这些学者的研究方法主要包括启发式算法［1～3］、遗传算 法［4～6］、多阶段方法［7，8］、整数规划［9］等。内河集装箱班轮与海运船舶相比，一方面由于货流不均衡性且船舶体型更小，船方往往更强调舱容利用率；另一方面班轮航线配载会受到集港过程中外贸箱箱量变化影响，已有的静态决策方法配载效率退化明显，难以满足内河集装箱班轮航线动态配载决策需求。

为此，本文考虑内河集装箱班轮运输中外贸箱不确定箱量影响，研究不确定箱量下班轮航线动态配载决策方法。考虑海关抽检导致外贸箱箱量变化这一随机事件，基于随机事件驱动的滚动调度策略，构建班轮航线多港口多阶段滚动调度的动态配载决策模型。同时引入大邻域搜索思想，设计一种包含混合整数规划模型、破坏器与修复器的精确启发式算法，实现港口多阶段配载决策。最后基于真实场景的算例研究验证模型与算法的有效性。

1 问题描述与建模分析

内河集装箱班轮航线运输中顺序遍历多个港口节点，航线上任意两个港口节点（始发港o和目的港d）之间的集装箱流向可用一个二元副a＝（o，d）唯一标识，记为O-D副a流向。班轮航线配载决策中，上一港口节点输出的配载计划作为输入来制定下一港口节点配载计划。对于外贸箱而言，由于存在海关抽检这一随机事件，其集港过程中普遍存在集港后临时抽检、放关情况不理想、临时加箱等不确定性因素干扰，使配载计划隐含极强的脆性，如图1所示。

图1 内河集装箱班轮航线动态配载决策

具体来说，集装箱集港后海关进行临时抽检以及抽检后放关情况不理想会使得原计划中包含的集装箱无法进行装船作业，从而导致装船集装箱箱量的减少；同时由于海关抽检而错过原航次的集装箱进行临时装船使得原计划中未包含的集装箱需要进行装船作业，从而导致装船集装箱箱量的增加。由于内河集装箱班轮船体结构的特殊性，实际箱信息的微小误差都会使得当前港口的预配与实配计划发生失效，从而需要对原计划进行动态调整。不仅会增加港口的额外作业成本，也会对班轮运输的经济性和时效性产生不良影响。

综上，内河集装箱班轮航线配载决策中，对于外贸箱而言，需考虑海关抽检导致箱量变化对其影响。在满足船舶航行安全性前提下，制定出满足航线各港口节点之间运输需求的配载计划。同时考虑到内河班轮运输的独特性和经济性，以最小化航线班轮堆栈占用数量为目标，实现被占用堆栈的高效利用，保证船舶的舱容利用率。

2 模型构建

2.1 假设条件

针对内河集装箱班轮航线运输中外贸箱集港特点，考虑现实约束，做出以下假设：

（1）考虑同一尺寸的普通箱；

（2）集装箱集港后存在临时抽检以及抽检后放关情况不理想；

（3）由于临时抽检而错过原航次的集装箱需要进行临时装船。

2.2 模型建立

为了方便建模，将内河集装箱班轮贝位内堆栈按前半部、后半部、左半部、右半部分成不同的堆栈集合，如图2所示。

图2 内河集装箱班轮结构

（1）集合

P：航线港口集合；Q（p）：当前港口p的O-D副集合，Q（p）＝Qb∪Qs（p），∀p∈P；Qb（p）：途径当前港口p的O-D副集合，Qb（p）＝｛a｜o，p，d∈P，o≺p≺d，a＝（o，d）｝；Qs（P）：当前港口p始发的O-D副集合，Qs（p）＝｛a｜o，p，d∈P，o＝p≺d，a＝（o，d）｝；G：集装箱重量等级集合，分为轻、中、重三个等级，即G＝｛1，2，3｝；J：班轮所有堆栈集合，从船头到船尾、从左到右依次对堆栈进行编号得到堆栈集合，J＝JF∪JA＝JL∪JR；JF：班轮前半部堆栈集合；JA：班轮后半部堆栈集合；JL：班轮左半部堆栈集合；JR：班轮右半部堆栈集合；NTp：当前港口p的阶段数集合，NTp＝｛t｜0≤t≤Tp｝。

（2）参数

Tp：当前港口p截港时的最后阶段；Ntg（a）：t阶段，从当前港口p流向后续港口d的重量等级为g的待装船集装箱箱量（TEU），∀t∈NTp，a＝（o，d）∈Qs（p），g∈G；（a）：t阶段，由于海关抽检导致的从当前港口p流向后续港口d的重量等级为g的增加箱量（TEU），∀t∈NTp-｛0｝，a＝（o，d）∈Qs（p），g∈G；（a）：t阶段，由于海关抽检导致的从当前港口p流向后续港口d的重量等级为g的减少箱量（TEU），∀t∈NTp-｛0｝，a＝（o，d）∈Qs（p），g∈G；wg：重量等级为g的集装箱平均重量（ton），g∈G；ΔLG：班轮允许的最大纵向重量差（ton）；ΔCG：班轮允许的最大横向重量差（ton）；STj：堆栈j的最大箱位容量（TEU），∀j∈J；SWj：堆栈j的最大载重量（ton），∀j∈J；L：一个大数。

（3）变量

xtjg（a）：t阶段，堆栈j内a流向下重量等级为g的集装箱箱量（TEU），∀t∈NTp，g∈G，j∈J，a∈Q（p），p∈P；ytj（a）：0-1变量。t阶段，若班轮堆栈j被a流向下的集装箱占用则为1；否则为0，∀t∈NTp，j∈J，a∈Q（p），p∈P。

（4）模型

针对内河集装箱班轮运输中外贸箱箱量变化特点，采用基于随机事件驱动的滚动调度策略来实现班轮航线动态配载决策。考虑船舶的舱容利用率，以最小化班轮堆栈占用数量为目标，实现被占用堆栈空间的高效利用，保证班轮航线运输的经济性。对于航线上任意港口的配载决策而言，利用多阶段决策的无后效性，针对海关抽检导致外贸箱箱量变化这一随机事件，基于随机事件将当前港口的配载决策划分为多个阶段，每个随机事件驱动一个阶段，保证各阶段最优来实现整体最优。基于随机事件驱动的班轮航线多港口多阶段滚动调度策略如图3所示。图中，初始状态下阶段数t＝0，当海关抽检导致箱量发生变化时，更新阶段数t＝t+1，依次类推，当前港口p截港时记录下最后阶段Tp。构建当前港口p任意阶段t的配载决策模型（Stowage Planning Model），记为SPM（t），∀t∈NTp-｛0｝，p∈P-｛1｝：

图3 内河集装箱班轮航线多港口多阶段滚动调度策略

式（1）～式（2）为目标函数，其中式（1）表示最小化当前港口任意阶段的班轮堆栈占用数量，实现航线班轮堆栈占用数量最小，保证被占用堆栈的高效利用；式（2）表示最小化当前港口相邻阶段之间配载计划偏差，保证配载计划的鲁棒性。式（3）～式（14）为约束条件。其中式（3）表示当前港口任意阶段集装箱装船约束；式（4）表示当前港口任意阶段的集装箱流平衡约束；式（5）表示到达当前港口时已装船集装箱箱位固定约束；式（6）保证当前港口任意O-D阶段班轮航线上任意副流向下的集装箱至少占用一个堆栈；式（7）保证当前港口任意阶段班轮任意堆栈至多被一种O-D副流向下的集装箱占用，避免出现为了卸载下方集装箱，而需要暂时卸下再重新装船的阻塞箱；式（8）定义决策变量xtjg（a）与ytj（a）之间的关系：若xtjg（a）＞0，则说明当前港口t阶段堆栈j内堆放有a流向下的集装箱，此时ytj（a）＝1；若xtjg（a）＝0，则说明当前港口t阶段堆栈j内没有堆放a流向下的集装箱，此时ytj＝0；式（9）保证当前港口任意阶段班轮任意堆栈的载箱量满足容量约束；式（10）保证当前港口任意阶段班轮任意堆栈的载重量满足约束；式（11）保证当前港口任意阶段班轮满足纵向重量差约束；式（12）保证当前港口任意阶段班轮满足横向重量差约束；式（13）和（14）定义决策变量的取值范围。

由于不存在上一阶段，去除上述子目标（2）和约束（4）可得到当前港口p初始阶段t＝0的配载决策模型SPM（0）如下：（SPM（0））｛f1（0）＝yoj（a）：（3），（5）～（14）｝。

2.3 下界值模型

对于优化目标f1（t）而言，直接基于当前港口截港时最后阶段t＝Tp的集装箱信息进行配载决策，不考虑当前港口各阶段配载计划之间的差异性，即不考虑配载计划的鲁棒性，可得到原问题中优化目标f1（t）的下界值模型（Low Bound Model 1，LBM1）。当前港口p截港后所有待装船集装箱的箱量等信息均变为已知，即NTpg（a）已知。此时，将约束式（4）修改为：

同样地，对于优化目标f2（t）而言，不考虑优化目标f1（t）影响，直接对其进行单独优化，可得到其下界值模型（Low Bound Model 2，LBM2）：

上述模型LBM1与LBM2分别用来确定模型SPM中两个优化目标f1（t）和f2（t）的下界值，进行后续模型及算法求解性能分析。

3 算法设计

精确启发式算法（Matheuristic Algorithm，MA）是将数学规划融入到启发式架构中的一种算法。已有船舶航线配载相关研究中，仅文献［10］针对海运集装箱船舶的全航线主贝计划设计了名为两阶段渐进随机修复进程（Two-level progressive Random Fixing Procedure）的混合整数规划启发式（Mixed Integer Programming Heuristic）方法，通过对模型中变量的松弛与修复来分阶段实现求解。本文引入大邻域搜索思想，设计一种包含混合整数规划模型、破坏器与修复器的精确启发式算法，来实现内河集装箱班轮航线运输中当前港口多阶段配载决策。算法主要思路如下：

Step 1初始解生成。当前港口初始阶段t＝0时，求解模型SPM（0）得到当前港口的初始配载方案；

Step 2阶段数更新。当海关抽检导致外贸箱箱量发生变化时，更新当前港口阶段数t＝t+1；

Step 3破坏器设计。当前阶段t（t＞0）下，将当前港口始发的所有O-D副流向按集装箱箱量是否发生变化，分为两部分。其中未发生箱量变化的O-D副流向集合记为A0（t），发生箱量变化的记为A1（t）。设计两种不同的破坏策略，对上一阶段的配载计划进行破坏，将部分集装箱取出后重新配载，实现对初始解邻域结构的搜索：

（1）随机破坏（Random Destruction）。从集合A0（t）和A1（t）内随机选择集装箱进行破坏，其中对于集合A0（t）内任意O-D副流向a′而言，假设其对应集装箱占用堆栈数量为O（a′），则随机生成［0，O（a′）］范围内整数，实现对应数量堆栈内集装箱破坏，取出的集装箱需重新配载。对于集合A1（t）内任意O-D副流向a″而言，假设其对应集装箱占用堆栈数量为O（a″），若箱量变化为正数（即箱量增加），则随机生成［0，O（a″）］范围内整数，实现对应数量堆栈内集装箱破坏，取出的集装箱与增加的集装箱需重新配载；若箱量变化为负数（即箱量减少），则随机生成［1，O（a″）］范围内整数k，若k个堆栈内任意重量等级g下的集装箱箱量之和ng（k）满足gn（k）≥（a″），则对该k个堆栈内集装箱进行破坏，若ng（k）不满足ng（k）≥（a″），则重新生成k至满足条件，取出的集装箱减去减少箱量后需重新配载；

（2）固定破坏（Fixed Destruction）。集合A0（t）内集装箱保留上一阶段的配载结果，对集合A1（t）内所有O-D副流向集装箱进行破坏，取出的集装箱需重新配载；

Step 4修复器设计。当前阶段t（t＞0）下，对破坏器取出的集装箱进行重新配载，实现配载计划的修复。针对破坏后取出的集装箱，基于下界模型LBM2求解实现重新配载。由于初始阶段下已对原问题中优化目标f1（t）即当前港口的班轮堆栈占用数量进行优化，在下一阶段中仅考虑对优化目标f2（t）进行优化，保证与上一阶段配载计划中堆栈占用结果的偏差最小，亦可保证对当前阶段下班轮堆栈占用数量的优化。以此类推，可以滚动实现当前港口后续所有阶段配载计划的求解；

Step 5完成模型LBM2求解，输出当前港口t（t＞0）阶段下的配载方案；

Step 6重复上述Step 2～5，完成当前港口多阶段滚动配载决策。

图4 精确启发式算法设计

4 算例研究

4.1 算例设计

根据国家标准GB/T 19283-2010，以长江集装箱班轮运输为例，选取三艘不同尺寸类型（小、中、大型）的集装箱班轮进行算例研究，班轮相关信息如表1所示。

表1 长江集装箱班轮信息

为验证不同模型的求解效果，基于长江集装箱班轮实际运输场景设计一系列算例进行研究。考虑4条包含不同港口数目的航线，见表2。每条航线中，考虑3种不同的班轮装载率，见表3。其中，班轮装载率是指班轮离港时所有装船集装箱总箱量与其总容量之间的比率值，值越大表示班轮装载集装箱越多。采用诸如S1L1C45的方式来表示不同的算例，其中第一部分S1表示班轮船型，第二部分L1表示班轮航线，第三部分C45表示班轮装载率。

表2 班轮航线设计

表3 班轮装载率

4.2 算例求解

所有的数学模型SPM、LBM1以及LBM2均采用Gurobi 7.5.1求解。采用随机破坏和固定破坏策略的精确启发式算法（MA）分别记为MA_Random和MA_Fixed，基于Python 3.6编程实现。所有的算例均在4GB内存笔记本电脑（Intel Core I7-5500U，2.40GHz）上运行求解。每个算例中，航线各港口均考虑5个阶段的箱量变化，各阶段下不同副流向下集装箱箱量可增可减且箱量变化随机生成。为了保证模型的求解效率，将其单次求解时间限制设置为60秒。

4.2.1 多目标优化权重分析

由于模型SPM中含有两个子目标，引入权重系数λ1、λ2将其目标函数转化为：

为了确定合适的权重系数，选择体型最大的班轮S3对应算例设计多组对比试验，结果如下表4所示。表中，f1表示航线班轮堆栈占用数量，对所有港口最后阶段班轮堆栈占用数量求和得到，即（单位：个）；f2表示班轮航线配载计划偏差之和，即f2＝｜（单位：个）；T表示每个算例的求解时间（单位：秒）。

表4 不同权重比率下求解结果

从表4中可以看出，不同权重系数λ1、λ2比率下，模型SPM对两个子目标的优化程度差异不大，仅在求解时间方面存在一定差异性。综合来看设置λ1：λ2＝1：10时，模型SPM优化两个子目标时平均值均最小，且平均求解时间与最短平均时间的差异也较小。为此，后续模型SPM求解时，选择设置λ1：λ2＝1：10。

4.2.2 模型与算法结果

由于算法MA_Random具有一定随机性，每个算例连续优化10次后取平均值。对于不同班轮而言，模型SPM与不同算法MA的求解结果如表5～7所示。表中，f1、f2、T含义与表4中一致；gap1和gap2分别表示模型与算法求解不同目标与下界值 之 间 偏 差（单 位：%），其 中，gap1＝100×

表5 模型与不同算法求解结果-班轮S1

表6 模型与不同算法求解结果-班轮S2

表7 模型与不同算法求解结果-班轮S3

从表5中可以看出，对于小型班轮S1而言，由于考虑航线配载计划的鲁棒性，模型SPM、算法MA_Random与MA_Fixed求解得到的航线班轮堆栈占用数量与下界值之间的平均偏差较大。但从表6和表7中可以看出，随着班轮体型的增大以及堆栈数量的增多，模型及算法得到的航线班轮堆栈占用数量与下界值之间的平均偏差逐渐减小至3%左右。总体来看，在优化航线班轮堆栈占用数量方面，模型SPM、算法MA_Random与MA_Fixed三者之间差异不大。

从表5至表7中可以看出，由于采用下界模型LBM2作为修复器，算法MA_Random与MA_Fixed总能求得与下界值相同的航线配载计划偏差之和，因而它们在鲁棒性方面的表现要优于模型SPM。同时在求解时间方面，算法MA_Random与MA_Fixed也较模型SPM更优。两种不同破坏策略下，算法MA_Random在求解时间方面表现略优。

综上，由于模型SPM、算法MA_Random与MA_Fixed考虑对班轮航线各港口各阶段配载计划之间偏差进行优化，其对应航线班轮堆栈占用数量与下界值模型（LBM1）之间存在较大的偏差。但模型LBM1仅基于当前港口最后阶段的集装箱信息进行配载决策，其结果势必会在较大程度上优于上述两者。同时，随着船舶体型增大，模型SPM、算法MA_Random以及MA_Fixed对应平均偏差逐步减少至合理范围内。对于班轮航线配载计划偏差之和而言，模型SPM对应结果在数量上与下界值模型（LBM2）之间差异很小；而算法MA_Random与MA_Fixed则表现更优，总是可以得到与模型LBM2相同结果，说明模型SPM、算法MA_Random与MA_Fixed在配载计划的鲁棒性方面均表现较好。算例研究表明，模型SPM与算法MA可用来辅助实现不确定箱量下内河集装箱班轮航线动态配载决策，且后者表现更优。两种不同破坏策略下，算法MA_Random在求解时间方面略优于算法MA_Fixed。

5 结论

本文针对内河集装箱班轮运输中外贸箱箱量变化特点研究班轮航线动态配载决策方法。基于随机事件驱动的滚动调度策略，以最小化航线班轮堆栈占用数量为目标，构建班轮航线多港口多阶段滚动调度的动态配载决策模型。同时，基于大邻域搜索思想设计一种精确启发式算法来实现港口的多阶段滚动配载决策。算例研究发现，针对外贸箱箱量变化特点，模型SPM和算法MA可用来辅助实现内河集装箱班轮航线动态配载决策。算法MA较模型SPM而言表现更优，且随着船舶体型增大，模型与不同算法求解航线班轮堆栈占用数量结果与下界值之间偏差呈逐渐减小趋势。对于算法MA而言，两种不同破坏策略在求解质量方面无差异，在求解时间方面算法MA_Random表现略优。下一步研究中，将针对求解效率更高的动态配载决策算法进行开发。