基于粒度划分的内河集装箱船全航线配载研究*

徐 进 张 煜 李 俊

(武汉理工大学物流工程学院 武汉 430063)

0 引 言

集装箱船全航线配载作为集装箱运输的核心环节，在保障船舶安全航行、货物安全运输，以及营运效率中扮演着重要角色.目前，国内外学者对集装箱船配载研究，主要集中在模型构建和算法开发等方面，涉及单港口和全航线等船舶配载问题.在单港口船舶配载方面，乐美龙等[1]构建了集装箱船配载问题模型，设计启发式算法求解；李俊等[2]设计了吱呀轮-混合演算策略两阶段算法，求解带有堆场发箱顺序约束的船舶配载问题；李坤等[3]建立最小化装船时间和Bay位重量差的多目标规划模型，设计两阶段启发式算法求解模型；Maria 等[4]从码头角度考虑集装箱配载问题，并设计两阶段启发式算法最小化集装箱运输时间的堆场翻箱次数；Eliseu等[5]将船舶配载决策视作三维装箱问题，最小化挂靠港装卸操作次数和船舶非稳性，并提出帕累托聚类搜索(Pareto clustering search)算法求解模型.在全航线配载方面，Alberto[6]建立全航线配载的整数规划模型和约束规划模型，使用CPLEX和Gecode软件分别对模型进行求解；Dario[7]从翻倒箱量和岸桥利用率出发，建立全航线配载的整数规划模型，采用大邻域搜索算法进行求解；Daniela等[8]设计启发式算法对全航线船舶配载问题进行求解，最小化船舶驻港总时间；Daniela等[9]又以全航线集装箱配载为研究对象，建立考虑标准箱、冷藏箱、上开口箱及舱盖板的混合整数规划模型，并以MIP Solver进行验证；Ding等[10]以最小化全航线翻箱率为目标建立全航线配载模型，并设计启发式算法对其进行求解.Opher等[11]针对全航线集装箱配载倒箱量最小而设计一种基于紧凑而高效编码方式的遗传算法，搜索模型最优解.

以上船舶配载相关研究均针对海运展开，基本都是将船舶的整贝或单个箱位作为存储单元设计模型和算法[12-13].由于内河集装箱船舶船体较小、船方更加强调舱容利用率，本文将内河集装箱船各个贝划分为不同粒度的存储单元，结合数学规划方法，构建基于粒度划分策略的内河集装箱船全航线配载模型，实现航线同目的港集装箱在内河船舶存储单元的集中堆放，进而提高船舶利用率.结合长江真实运输场景设计多组算例，通过算例验证模型的有效性.

1 问题描述

集装箱船全航线配载问题可归为多港主贝计划问题(multi-port master bay plan problem，MP-MBPP)，是根据航线各个挂靠港集装箱的尺寸、质量等级、目的港、数量等信息，将各个挂靠港集装箱集合有效划分并分配到船舶各个贝内，需要保证船舶稳性、强度、容量等约束，避免翻倒箱，提高船舶全航线装载率.内河集装箱船全航线配载，见图1.各挂靠港按遍历顺序组成多个航段，集装箱流向O-D(起始港-目的港)以一段有向弧a表示.在内河支线集装箱船全航线配载决策中，船舶船体更小(多为3 000～5 000 t级船型)，没有舱盖板，强调舱容利用率.

图1 全航线配载示意图

文中对内河集装箱船全航线配载决策进行研究，基于粒度划分策略，将内河集装箱船的存储空间(由贝-堆栈-箱位组成)划分为不同数量、不同大小的多个存储单元，进而构建内河集装箱船全航线配载的多粒度数学规划模型.此处，粒度是用来描述船舶存储单元大小的.最粗粒度的船舶存储单元对应船舶偶数贝箱位集合，中间粒度的船舶存储单元对应船舶偶数贝多个相邻堆栈的箱位集合，最细粒度的船舶存储单元对应船舶偶数贝堆栈的箱位集合.通过以上灵活定义，粒度越粗的数学规划模型，其约束和变量减少，可以有效提高模型求解效率.同时，基于粒度划分策略构建启发式算法，还可以在求解精度和运算效率间获得平衡.

2 模型构建

基本参数：H为航线港口集合；B为船舶贝集合；B(k),BP(k),BA(k)，BL,l(k),BR,l(k)分别为k粒度下船舶整体、船舶前半部、船舶后半部、船舶贝l∈B左半部和右半部的存储单元集合；Pt(i),Ps(i),P(i)为航线上港口i对应的O—D副集合，Pt(i)={a|o,i,d∈H,o

决策变量：xbg(a)为港口副流向a分配到船舶存储单元b的g质量等级集装箱的数量；yb(i)为0-1变量，若在港口i船舶存储单元b被占用，则y为1，否则为0；zb(a)为0-1变量，若船舶存储单元b被a副流向下集装箱占用，则z为1，否则为0.

1) 粒度计算

「‖Nrow‖/2j⎤>1)+2，j为自然数

(1)

Nk=「‖Nrow‖/2m-k⎤，k=1,2,…,m

(2)

‖|B(k)‖=‖Nbay‖·Nk，k=1,2,…,m

(3)

式(1)为最细粒度；式(2)为k粒度下船舶贝内存储单元数量；式(3)为k粒度下船舶存储单元数量.

2)k粒度下的混合整数规划模型，记为MIP(k)

f=min(∑i∈H∑b∈B(k)yb(i)/

((‖H‖-1)×‖B(k)‖))

(4)

s.t. ∑b∈B(k)xbg(a)=Ng(a)

∀i∈H,a∈Ps(i),g∈G

(5)

zb(a1)+zb(a2)≤1∀i∈H,b∈B(k),

(a1,a2)∈D(i)

(6)

∑a∈P(i)∑g∈Gxbg(a)≤CTeub

∀i∈H,b∈B(k)

(7)

∑a∈P(i)∑g∈Gwg·xbg(a)≤CTonb

∀i∈H,b∈B(k)

(8)

|∑a∈P(i)∑g∈G∑b∈BL,l(k)(wg·xbg(a))-

ΔGh∀i∈H，∀l∈B

(9)

0≤∑a∈P(i)∑g∈G∑b∈BA(k)wg·xbg(a)-

∑a∈P(i)∑g∈G∑b∈BP(k)wg·xbg(a)≤ΔGc

∀i∈H

(10)

yb(i)≤∑a∈P(i)zb(a)≤yb(i)·M

∀i∈H,b∈B(k)

(11)

zb(a)≤∑g∈Gxbg(a)≤zb(a)·M

∀i∈H,b∈B(k),a∈P(i)

(12)

目标函数(4)最小化船舶存储单元在全航线配载的平均使用数量，使被占用的存储单元尽可能多装箱，即提升船舶存储单元利用率；约束(5)确保任一挂靠港待装集装箱都装船；约束(6)确保不同目的港集装箱不混装；约束(7)和(8)分别确保船舶在任一挂靠港装完后满足存储单元最大容量和最大载荷要求；约束(9)和(10)分别确保船舶在各挂靠港装载完成后满足横倾和纵倾力矩允许的重量偏差要求；约束(11)和(12)定义了三个决策变量之间的关系.

3 算法设计

针对内河集装箱船全航线配载问题，结合内河运输特征，设计基于多粒度配载模型的启发式算法，算法包括存储单元动态划分及分支定界算法求解单一粒度下配载模型两部分.其中，存储单元动态划分即根据粒度确定贝内存储单元数量，均匀地将各贝划分为多个存储单元.为船舶配载主贝计划的制定确定最小装载单元，及横、纵向重量差计算方式；分支定界算法即在执行过程中将全部可行解空间不断分割为越来越小的子集(称为分支)，并为每个子集内的解的值计算一个下界或上界(称为定界)，从其中寻得最佳解.模型中通过CPLEX优化软件调用分支定界算法对单个粒度下的配载模型进行求解.算法具体搜索流程见图2.

图2 启发式算法搜索流程

4 算例验证

4.1 算例设计

根据文献[14]选取集装箱船，其参数见表1.

根据以上船舶参数，构建不同船型，不同挂靠港的36组算例验证模型.算例以S(船型:1,2,3)、P(挂靠港口数量:4,6)、R(TEU/FEU箱数量比例：1～5∶5,2～7∶3)、W(轻、中、重箱数量比例：1～6∶3∶1,2～3∶6∶1,3～3∶4∶3)组合来标识.例如，S2P4R1W2表示该算例采用2号船舶且航线依此挂靠四个港口，在各挂靠港TEU/FEU箱数量比约为5∶5，轻、中、重箱数量比约为3∶6∶1.

表1 集装箱船装载参数

4.2 模型验证

以算例S1P4R2W3为例，依据式(1)～(3)可求得四个粒度，基于多粒度配载模型，结合CPLEX优化软件对各个粒度进行仿真分析，验证模型的可行性.算例求解结果见表2，结果显示粒度划分越细，约束及变量个数越多，求解时间越长，模型复杂度呈指数增长.通过多组算例验证显示上述结论针对所有算例均成立，多粒度配载模型通过对存储单元粒度的不断细分可优化存储单元占用率，细粒度下模型求解时间最长，复杂度最高.但最细粒度下的解并不一定是最优解，具体结果见模型性能分析部分.

表2 CPLEX优化多粒度配载模型相关参数

注：*为通过删除约束(6)所求得该粒度下的最优解.

为进一步验证模型的可行性，以算例S1P4R2W3最优解为集装箱配载方案绘制最优粒度下船舶存储单元在各挂靠港装载情况见图3.图中每个单元格对应一个存储单元，格中数字分别对应该存储单元装载的集装箱数量及其总重.其中由两个或两个以上图标组合标识的为多个挂靠港集装箱混装结果，如在挂靠港2，左下角存储单元由左斜线图标及网格图标组合标识，表示在挂靠港2，该存储单元装载挂靠港1发往后续港口的集装箱和挂靠港2发往后续港口的集装箱(各区域面积并不代表装箱数量).各挂靠港依次占用存储单元数量为15，15，15，该航次中船舶存储单元平均占用率为83.33%，各存储单元装载率高，符合最小化存储单元占用原则.此外，通过计算，各挂靠港船舶横向重量差和纵向重量差均满足船舶营运安全性约束.综上所述，多粒度配载模型在一定程度上能够有效细化装载空间，提高集装箱船利用率，获得满足集装箱配载要求的最优解.此外，粒度与模型复杂度的关系使得建模者可在时间及优化解之间做出权衡，亦可从较粗粒度的快速求解特性出发快速产生初始解用于拓展其他优化算法.

图3 案例S1P4R2W3各挂靠港存储单元占用情况

4.3 模型性能分析

以启发式算法结合CPLEX优化软件对36组算例进行求解，考虑细粒度下求解时间较长，设定各粒度的优化时间限值为30 min，各算例求解结果见表3.由表3可知，36组算例平均横向质量差、平均纵向质量差分别为14.93，16.92 t，均满足船舶航行安全性约束；36组算例平均求解时间为290.64 s，平均gap值为6.16%，求解时间及求解结果均在可允许范围内.

表3 36组算例仿真结果

续表3

注：--表示无该参数(粗粒度下以整贝为存储单元，此时不考虑贝内横倾；对粒度求均值无意义)；gap值由CPLEX求解模型时给出，为最优粒度模型的下界值;*表示该均值计算剔除无效数据，采用所有有效数据进行计算.

作为船舶配载的重要影响因素，船舶横、纵向重量差的变化也是检验模型的一项重要指标，本文将启发式算法求得各挂靠港船舶各贝横向重量差及船舶纵向重量差作箱形图见图4.

图4 质量差箱形图

图4a)横向质量差箱形图中垂线下端点对应某一算例中各挂靠港船舶各贝中最小横向质量差，垂线上端点对应最大横向质量差，矩形框上边缘对应某一算例中船舶横向质量差上四分位点，下边缘对应下四分位点，三角形位置代表中位值，图4b)类似.

由图4a)可知，各案例船舶贝内横向质量差波动范围较均匀，均在0～26 t.根据中位数的定义可知多个算例的船舶在各挂靠港、各贝的横向质量差多数处于0～20 t.由图4b)可知，多个案例在各挂靠港船舶整体纵向质量差(尾倾)小于25 t，整体处于5～23 t.故多粒度配载模型求解结果降低船舶横向质量差、保留适当尾倾，保证了集装箱船舶的适航性.

综上所述，多粒度配载模型可有效完成存储空间的划分，实现内河集装箱紧凑的堆存方式，可准确、快速得出集装箱船配载方案.此外，根据细粒度下并非最优的结论，通过对粒度的合理选取可减少解空间，加快模型求解速率.

5 结 束 语

文中针对内河集装箱船全航线配载问题展开研究，构建了基于粒度划分的船舶全航线配载模型，并设计启发式算法对模型进行求解.结合长江真实运输场景设计多组算例，验证了多粒度配载模型的有效性.多组算例表明粒度的划分程度直接影响模型计算的复杂度，粒度划分越细，获得解最优的概率越大，但最优解确不一定出现在最细粒度.故通过粒度的合理选择可实现模型求解中目标和时间的均衡，且通过较粗粒度的快速求解特性可较快产生初始可行解，有利于开发灵活高效的算法.