现实约束下的多挂靠港滚装船舶配载优化

姜彦宁, 徐 奇, 金燕燕, 靳志宏*

(1.大连海事大学 交通运输管理学院,辽宁 大连 116026; 2.交通运输部 科技司,北京 100736)

现实约束下的多挂靠港滚装船舶配载优化

姜彦宁1,2, 徐 奇1, 金燕燕1, 靳志宏*1

(1.大连海事大学 交通运输管理学院,辽宁 大连 116026; 2.交通运输部 科技司,北京 100736)

在分析滚装船舶配载特点的基础上,考虑了船舶稳性、配载效率以及航次收益等现实约束,针对多挂靠港的滚装汽车运输新模式下的配载优化问题进行建模,并基于该问题多阶段、多维约束、多背包组合优化的特点,开发了遗传算法对所构建模型进行求解.对于小规模数值算例实验,运用所设计遗传算法的求解结果与 lingo 软件所得到的精确解比较,平均误差率约为 1.4%;对于大规模仿真算例,遗传算法的求解质量则明显优于现实调度策略,显示出本算法较好的鲁棒性.在此基础上开发了基于 VB 的配载信息系统,实现了配载过程及配载方案的可视化,为实时配载决策奠定了基础.

综合交通运输;滚装船配载;多挂靠港;决策可视化

1 引 言

滚装船配载要在保证船舶航行安全的前提下,进行装船车辆的合理选择和安排,是一个典型的离散组合优化问题.随着船舶大型化趋势的加剧,滚装船 配 载 优 化 问 题 (ro-ro ship loading problem, RRSLP)已发展为大规模、高复杂度的组合优化问题.同时,伴随着这种船舶大型化的趋势,滚装船舶的运输也改变了原来的两港间的直航(无中途停靠港)运输模式,出现了多挂靠港的滚装运输新模式.据调查,目前并无针对这种新滚装运输模式的配载优化的相关文献.

国内外学者对集装箱船配载优化进行了比较深入的研究[1,2],而对滚装船舶配载优化的研究还不是十分深入.孙玉昌等[3]对船载车辆横摇及车辆停放时滚装船稳性问题进行核算,并提出了合理化建议.李冬梅[4]指出滚装船在积载系固方面存在的问题,并给出了车辆的积载和系固方面的要求.宋振洪[5]从保证船舶稳性的角度出发,通过最小化船舶平衡力矩来选择装船车辆.Jia[6]探讨了如何使滚装船上的车辆不需系固也可保证安全,以提高停放车辆的数量.靳志宏与金燕燕[7]考虑了船舶稳性、配载效率及航次收益等现实约束与配载目标,对滚装船配载优化问题进行建模,开发了以贪婪算法为基础的两阶段启发式算法.目前该研究仅限于单一装货港与单一卸货港的直达运输模式,没有考虑多装货港和卸货港,即有中途挂靠港的情形.

本文在参考文献[7]的基础上,将两港间的直航模式扩展到多挂靠港的滚装运输新模式;设计实用优化算法以求解所构建的船舶配载优化模型,开发配载管理信息系统,进而实现智能与可视化配载.

2 问题描述

2.1 问题归结

本文研究的船舶配载是多类型成品车的多装货港多卸货港的多阶段配载问题,根据装货港的不同划分成不同阶段,对每个阶段进行配载.滚装船配载优化问题可归结为特殊的离散优化的背包问题.其特殊性体现在:

(1) 多阶段配载问题,现行研究针对的是两港间的直航(无中途停靠港)运输模式,本文将其扩展到多挂靠港的滚装运输新模式;

(2) 多维约束问题,如载重量约束、空间尺寸约束、船舶稳性约束等;

(3) 多背包问题,即同时进行配载的背包数(各层甲板、以及每层甲板的车道的条数)是多个.

综上,该优化问题可以归结为多阶段、多维约束、多背包组合优化问题.

2.2 现实约束

为了增强配载方案的实用性,本文考虑了如下现实约束:

(1)所有待装船到达某一个卸货港的车辆所占用的车道长度,不能超过分配给这个卸货港的车道长度;

(2) 所有装载到同一条车道上的车辆总长度(包括车辆之间的安全距离)不能超过这条车道的固定长度;

(3) 装载车辆的总重量不能超过船舶允许的最大载重量;

(4) 为保证船舶整体航行稳定性,装载方案必须保证船舶横倾力矩和纵倾力矩位于允许的范围内.

3 现实约束下的配载优化建模

3.1 前提与假设条件

(1) 将船头至船尾方向的中心线看成船舶的纵轴 y,船舶从左到右的方向看成船舶的横轴 x.俯视看,船头是上方,船尾是下方,船舶的左面是左方,右面是右方.船舶的坐标轴示意如图1 所示.

图1 船舶坐标轴示意图Fig.1 Illustration of the coordinate for a ship

(2) 第一个装货港只装不卸,最后一个卸货港只卸不装.

(3)甲板的形状是矩形.

(4) 分配给航线上各中途卸货港的车道条数是整数条.

3.2 符号说明

Z ——完成船舶装载车辆总的航次收益;

I——待装车辆总数;

J ——航线上挂靠港数量;

W ——船舱允许的最大载重吨;

t——第 t个装车港,即配载的阶段数,如 t=1就是第一个装车港和第一个配载阶段,以此类推;

T ——配载阶段数;

Wt-1——前一个装货港船舱已装车辆的总重量减去在t阶段卸船的车辆的重量;

K ——每层甲板车道的总数;

Totalj——航线上到 j港卸货的车辆总数;

L ——每条车道的固有长度;

k ——车道的索引,k=1,2,…,K;

i——车辆的索引;

j——目的港的索引;

vij——车辆 i到港口 j的运价;

Kj——分配给 j港口的车道数;

wi——车辆 i的自重;

li——车辆 i的长度;

Lj——分配给 j港口的车道长度;

(hqx1,hqx2) ——船舱沿 x 轴上的横倾力矩安全范围要求;

(zqy1,zqy2) ——船舱沿 y 轴上的纵倾力矩安全范围要求;——配载阶段 t 到达目的地港口 j的车辆 i配载在车道k上;

(xi,yi) ——车辆 i在船舱中的重心坐标;

(Luxi,Luyi):车辆 i在船舱内的左下角坐标;

(Rdxi,Rdyi):车辆 i在船舱内的右上角坐标.

3.3 优化模型

目标函数

约束条件

其中 式(1)为最大化滚装船所装载车辆的总航次收益;式(2)确保在第 t个装车港装车时船舱所装载车辆的总吨数不超过此时刻船舱容许的最大载重吨;式(3)保证在第 t阶段所有到 j港口的装船车辆总长度不超过分配给第 j港口车道的总长度;式(4)确保每条车道上所装载的车辆总长度不超过车道的固有长度;式(5)、式(6)确保船舱中所装的车辆的总横倾力矩、总纵倾力矩不超过给定的范围;式(7)、式(8)用于计算车辆 i在船舱中的横坐标和纵坐标;式(9)、式(10)计算分配给到达 j港的车道数量和总长度;式(11)确保车辆 i不能同时重复装载.

4 算法设计

针对多阶段、多维约束、多背包组合优化问题的特点,本文设计了针对该特殊背包问题的染色体编码方法:将待求解的变量 X 的每一维度表示成长度为待装车辆总数 I的字符串 x[n],n=1,…, I,n 按照所有待装车辆的卸货港的顺序 j,j=1,…,J 排列,且 x[n]=0 表示车辆 n 不配载,x[n]= 1 表示放入第一个车道,x[n]=2 表示放入第二车道,以此类推.例如:对于 x[n] 为 112001102……000112 的一个编码,第三个位置上的 x[n]=2,表明车辆3是装载在 k=2的车道上,j值代表车辆3将会在第 j个目的港卸载;另外,卸货港 j,j=1,…, J 与配载阶段 t,t=1,…,T,即装货港顺序相互关联,其内在联系可表示为 t=j+1,此时的 x[n]=2意味着 i=3,j=1,k=2,t=2.

在此基础上,设计的遗传算法流程如下.

步骤1初始化.

步骤1-1读入相关信息,如所装车辆的重量weight[j] 、长度 length[j] 、 收 费 profit[j] 和 车 道的最大载重量 contain 及长度 L,其中 j=0,1,…, lchrom-1,lchrom 为染色体长度.

步骤1-2取 x[j]=u(0,1,…,n),j=0,1,…,lchrom-1,其中 u(0,1,…,n) 表示 0 至 n 间的均匀分布整数函数.

若不满足模型的约束条件,则由步骤1-2 重新生成新的染色体个体 chrom;若产生的染色体可行,则将其作为种群的一个个体,经过有限次抽样后,得到 popsize 个可行的染色体 chrom,形成新的种群.

步骤1-3置种群的代数 gen=0.

步骤2计算个体适应度及统计种群适应度.

步骤2-1计算种群中个体适应度:

步骤2-2基于步骤2-1,计算种群的总体适应度,.并且通过排序统计出种群中的最大、最小适应度的染色体个体.

步骤3选择操作.

步骤3-1生成 随机数 rand_Number(0 ＜rand_Number ＜ 1).

步骤3-2按照赌轮法选择个体.

步骤3-3重复两次操作步骤3-1、步骤3-2,生成两个个体作为交叉操作的父代.

步骤4交叉操作.

步骤4-1生成[0,1]的随机数 pp,若 pp ＜pc(pc为交叉概率),则进行步骤4-2;否则将该父代保留为下一代的两个个体.

步骤4-2随机生成 [0,lchrom-1] 的整数作为交叉点,对两个父代个体交叉生成两个新个体.

步骤4-3重复 pop_size/2 次步骤4-1、步骤4-2便可生成 pop_size 个个体组成新的种群.

步骤5变异操作.

步骤5-1生成[0,1]的随机数 pp,若 pp ＜pm(pm为变异概率),进行步骤5-2 变异操作,否则不变异.

步骤5-2若原基因为 0,则新基因变异为 1;若原基因为 1,则新基因变异为 2……;原基因为n,则新基因变异为 0.

步骤6演化.

步骤6-1按步骤2 的方法计算新种群的适应度情况,并找出新种群中适应度最大和最小的个体.

步骤6-2若旧种群的最大个体适应度优于新种群的最大个体适应度,将旧种群中适应度最大的个体代替新种群中适应度最小的个体,否则进行步骤6-3.

步骤6-3种群的代数 gen=gen+1,若 gen＞ Maxgen,结束种群演化,否则转到步骤2.

步骤7多阶段配载.

t=t+1,进入下一配载阶段,初始化下一阶段船舱的剩余容量、每条车道的剩余长度等,转到步骤1.

5 数值实验

5.1 小规模问题与最优解的对比

为考察本文提出的解决小规模问题算法的鲁棒性,用 lingo 的求解结果和本文的算法得出的解相比较.具体算例:航线上有 3 个港口,第 1 个港口有 n=15 候选车辆,每条车道长 L=45,允许最大载重吨 W=68,进行配载的车道条数 k=2;第 2 个港口有 n=10 候选车辆,车道长 L1=35,L2=30,允许最大载重吨分别是 W1=60,W2=45,进行配载的车道条数 k=2;第 3 个港口是末端港口,不进行装货.所装船的车辆种类分别用 1-6 表示,依次按车型大小(重量大小、长度大小)从小到大进行排列.对 n=15,k=2 的小规模配载问题进行随机的 30次试验, 最终结果和 lingo 最优 解相比 较, 如表1所示.

可以看出,用本文的遗传算法与 lingo 软件所得到的精确解比较,平均误差率约为 1.4%.且在近三分之一的情况下,两者得到的目标函数值相同,显示出本算法较好的鲁棒性能.

表1 仿真算例的实验结果Table1 The experimental results of the simulation examples

5.2 大规模问题与现实调度规则的对比

由于目前尚无这方面的实验数据可以进行直接文献比较,本文以现场通常采用的实用调度规则所产生的调度方案作为比较对象.具体包括:按先到先服务原则配载、按装载尽可能多的车辆数配载、按待装车辆重量大小配载和按待装车辆收费高低配载.

大规模问题算例设计如下:滚装船舶每层甲板车道条数为 6 条,航线上共停靠 4 个港口,第 1 个港口是装货港,第 4 个港口是卸货港,中间两个是挂靠港,既有车辆装船也有车辆卸船,且每个可卸货的港口至少都有一条车道的车辆进行卸载,所以最终分配给某个卸货港的车道条数介于1～4条之间.但滚装船配载还要保证船舶的稳性,所以当遇到车道条数为单数时,要将单数车道一分为二,则对于到达某个卸货港的车辆进行装船时,同时进行装载的车道条数最小是 2 条,最大是 4 条.候选装船的车辆数随机产生,到达的同一类型的车辆的重量也在一定的范围内随机产生,分别进行 100 次的随机数值实验.

分别对车道数为 2、4 的大规模配载问题与实用调度规则进行对比,以验证本文算法的有效性.对比结果如图2、图3 所示.

图2 300 辆车 2 条车道配载结果对比Fig.2 The loading results comparison based on 300 vehicles and 2 lanes

图3 300 辆车 4 条车道配载结果分析Fig.3 The loading results analysis based on 300 vehicles and 4 lanes

由上述结果可以看出,本文遗传算法的求解质量明显优于其它常用调度策略,并且运算速度很快.随着车道数的增加,这种优越性更加明显,显示了良好的实用性及鲁棒性,可以有效地解决现实规模的滚装船配载优化问题.

6 滚装船舶配载可视化系统实现

6.1 车辆定位的启发式规则

现实中常用的启发式规则有:为保证装船稳性,将到达同一港口的车辆在船舱中左右对称摆放;最先卸载的车辆尽量摆放在外侧,最后卸载的车辆尽量摆放在内侧;最先卸载的车辆摆放在前,最后卸载的车辆则摆放在后;到达同一港口的车辆安排在同一条车道上;尽量不要拆分分配给同一港口的双数车道;如分配给某一港口的车道数是双数n,就左右各 n/2,如果是单数,就将其一分为二;同类车辆排在一起.同一列车道上不同种类车辆的排列顺序要兼顾大小车型尽量均衡的原则,防止船舶发生纵倾;到达同一港口的车辆,在对称位置上摆放时,车型的摆放顺序也是对称的;当分属于两个港口的半条车道组成同一条车道时,车型的摆放顺序应上下对称等.

6.2 配载可视化

基于上述规则,本文采用 Visual Basic 语言开发了滚装船配载车辆定位软件,以实现配载的可视化.通过输入滚装船所装车辆的基本信息(装货港、卸货港、车型、车长、车重、运输价格等),就可以生成配载方案,如图 4 所示.其中,车道背景不同代表着其各自不同的卸货港,矩形图案不同代表不同的车辆类型.

图4 展示界面Fig.4 Display interface

同时,也可以针对不同的配载方案、车辆定位,输出此时滚装船的横倾力矩、纵倾力矩以随时查看,保证船舶的稳性,如图5 所示.进而实现配载可视化.

图5 力矩输出界面Fig.5 The torque output interface

7 研究结论

本文在建立成品车多装货港、多卸货港的多阶段配载模型的基础上,设计了遗传算法对其进行求解,并通过仿真算例显示了模型的有效性及算法的鲁棒性.并进一步根据实用的启发式车辆定位规则,开发了滚装船舶配载信息管理系统,实现了装载的过程透明化、智能化,以及车辆在船舱内配置的可视化,提高了装卸效率及准确性,有助于提高滚装船运输的安全性.

进一步研究将集中于动态配载优化方面,即在配载决策时点,待装运车辆的信息不完全已知情形下的配载优化问题.

[1] 靳志宏,兰辉,郭贝贝,等.基于现实约束的集装箱配载优化及可视化[J].系统工程理论与实践,2010,30 (9):1722-1728.[JIN Z H,LAN H,GUO B B,et al. Optimization and visualization of the container loading problems with realistic constraints[J]. Systems Engineering-theory & Practice, 2010, 30(9): 1722-1728.]

[2] 郭贝贝,靳志宏,石丽红,等.现实约束条件下的集装箱多箱装载优化[J].上海海事大学学报,2009,30 (2):8-13.[GUO B B,JIN Z H,SHI L H,et al. Optimization of multiple container loading under practical constraints[J].Journal of Shanghai Maritime University,2009,30(2):8-13.]

[3] 孙玉昌,龙熙陵. 载车状态对滚装船稳性的影响[J]. 航海工程,2004,4:7-9.[SUN Y C,LONG X L. The influence of loading condition on the stability of Ro/ Ro vessels[J].Ship&Ocean Engineering,2004,4: 7-9.]

[4] 李冬梅. 滚装客船承载车辆的积载、系固及其管理[J]. 中 国 海 事,2008,4:46-49.[LI D M.Stowage, securing and management of vehicles loaded onboard Ro/Ro passenger ships[J].China Maritime Safety, 2008,4:46-49.]

[5] 宋振洪. 客滚船舶车辆的动态装载算法[J]. 计算机工 程,2004,30:522-523.[SONG Z H.Dynamic algorithm ofvehicle loading forrolling-ship[J]. Computer Engineering,2004,30:522-523.]

[6] JIA Jun-bo.Investigations of vehicle securing without lashings for Ro-Ro ships[J].J.Mar.Sci.Technol., 2007,12:43-57.

[7] 靳志宏,金燕燕. 滚装船配载优化算法及其软件化实现[J]. 中国航海,2010,33(2):84-94.[JIN Z H,JIN Y Y.A two-phase heuristic algorithm for ro-ro ship stowage planning[J].Navigation of China,2010,33 (2):84-94.]

Optimization of Ro-Ro Ship Loading for Multiple Ports Based on Realistic Constraints

JIANG Yan-ning1,2,XU Qi1,JIN Yan-yan1,JIN Zhi-hong1
(1.College of Transportation Management,Dalian Maritime University,Dalian 116026,Liaoning,China; 2.Department of Transportation Technology Division,Ministry of Transport,Beijing 100736,China)

Based on the analysis of characteristics of ro-ro ship loading,the ro-ro ship loading problem for multiple ports is formulated as a mixed integer programming,considering realistic restrictions such as the stability of vessels,the efficiency of loading and the income of voyage.With the characteristics of multistage,multi-dimensional restrictions,multi-bag combinational optimization,a genetic algorithm(GA)is developed for solving the proposed model.As to the small-scale problems,the GA solved results are quite near to the exact solutions only by 1.4%;as to the large-scale problems,results from the GA are obviously better than those derived from practical dispatching rules,thus the robustness of the proposed algorithm is verified.Furthermore,a MIS based on Visual Basic is developed to realize the visualization of both loading process and loading patterns,which can provide some assistance for real-time decision-making.

integrated transportation; ro-ro ship loading; multiple loading/unloading ports; decision visualization

1009-6744(2014)01-0117-07

U695.2+93

A

2013-09-02

2013-10-30录用日期:2013-11-12

国家自然科学基金(71172108,71302044);教育部博士点基金资助项目(20122125110009).

姜彦宁(1979-),女,辽宁丹东人,博士生.*通讯作者:jinzhihong@dlmu.edu.cn