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

现实约束下的多挂靠港滚装船舶配载优化姜彦宁;徐奇;金燕燕;靳志宏【摘要】在分析滚装船舶配载特点的基础上，考虑了船舶稳性、配载效率以及航次收益等现实约束，针对多挂靠港的滚装汽车运输新模式下的配载优化问题进行建模,并基于该问题多阶段、多维约束、多背包组合优化的特点，开发了遗传算法对所构建模型进行求解.对于小规模数值算例实验，运用所设计遗传算法的求解结果与lingo软件所得到的精确解比较，平均误差率约为1.4%;对于大规模仿真算例，遗传算法的求解质量则明显优于现实调度策略,显示出本算法较好的鲁棒性.在此基础上开发了基于VB的配载信息系统，实现了配载过程及配载方案的可视化，为实时配载决策奠定了基础.【期刊名称】《交通运输系统工程与信息》【年(卷)，期】2014(014)001【总页数】7页(P117-123)【关键词】综合交通运输;滚装船配载;多挂靠港;决策可视化【作者】姜彦宁;徐奇;金燕燕;靳志宏【作者单位】大连海事大学交通运输管理学院，辽宁大连116026;交通运输部科技司，北京100736;大连海事大学交通运输管理学院，辽宁大连116026;大连海事大学交通运输管理学院，辽宁大连116026;大连海事大学交通运输管理学院，辽宁大连116026【正文语种】中文【中图分类】U695.2+93滚装船配载要在保证船舶航行安全的前提下，进行装船车辆的合理选择和安排，是一个典型的离散组合优化问题.随着船舶大型化趋势的加剧,滚装船配载优化问题(ro-roshiploadingproblem,RRSLP)已发展为大规模、高复杂度的组合优化问题同时，伴随着这种船舶大型化的趋势，滚装船舶的运输也改变了原来的两港间的直航(无中途停靠港)运输模式，出现了多挂靠港的滚装运输新模式.据调查，目前并无针对这种新滚装运输模式的配载优化的相关文献.国内夕卜学者对集装箱船配载优化进行了比较深入的研究［1,2］,而对滚装船舶配载优化的研究还不是十分深入.孙玉昌等［3］对船载车辆横摇及车辆停放时滚装船稳性问题进行核算,并提出了合理化建议.李冬梅［4］指出滚装船在积载系固方面存在的问题,并给出了车辆的积载和系固方面的要求.宋振洪［5］从保证船舶稳性的角度出发，通过最小化船舶平衡力矩来选择装船车辆.Jia［6］探讨了如何使滚装船上的车辆不需系固也可保证安全，以提高停放车辆的数量.靳志宏与金燕燕［7］考虑了船舶稳性、配载效率及航次收益等现实约束与配载目标，对滚装船配载优化问题进行建模，开发了以贪婪算法为基础的两阶段启发式算法.目前该研究仅限于单一装货港与单一卸货港的直达运输模式,没有考虑多装货港和卸货港，即有中途挂靠港的情形.本文在参考文献［7］的基础上,将两港间的直航模式扩展到多挂靠港的滚装运输新模式；设计实用优化算法以求解所构建的船舶配载优化模型，开发配载管理信息系统，进而实现智能与可视化配载.2.1问题归结本文研究的船舶配载是多类型成品车的多装货港多卸货港的多阶段配载问题,根据装货港的不同划分成不同阶段,对每个阶段进行配载.滚装船配载优化问题可归结为特殊的离散优化的背包问题.其特殊性体现在：多阶段配载问题，现行研究针对的是两港间的直航(无中途停靠港)运输模式,本文将其扩展到多挂靠港的滚装运输新模式；多维约束问题，如载重量约束、空间尺寸约束、船舶稳性约束等；⑶多背包问题，即同时进行配载的背包数(各层甲板、以及每层甲板的车道的条数)是多个.综上，该优化问题可以归结为多阶段、多维约束、多背包组合优化问题.2.2现实约束为了增强配载方案的实用性，本文考虑了如下现实约束：所有待装船到达某一个卸货港的车辆所占用的车道长度，不能超过分配给这个卸货港的车道长度；所有装载到同一条车道上的车辆总长度(包括车辆之间的安全距离)不能超过这条车道的固定长度；装载车辆的总重量不能超过船舶允许的最大载重量；为保证船舶整体航行稳定性，装载方案必须保证船舶横倾力矩和纵倾力矩位于允许的范围内.3.1前提与假设条件将船头至船尾方向的中心线看成船舶的纵轴y,船舶从左到右的方向看成船舶的横轴乂俯视看，船头是上方，船尾是下方，船舶的左面是左方佑面是右方.船舶的坐标轴示意如图1所示.第一个装货港只装不卸,最后一个卸货港只卸不装.⑶甲板的形状是矩形.⑷分配给航线上各中途卸货港的车道条数是整数条.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不能同时重复装载.针对多阶段、多维约束、多背包组合优化问题的特点，本文设计了针对该特殊背包问题的染色体编码方法:将待求解的变量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=j+1,此时的x[n]=2意味着i=3,j=1,k=2,t=2.在此基础上,设计的遗传算法流程如下.步骤1初始化.步骤1-1读入相关信息，如所装车辆的重量weight[j]、长度length[j]、收费profit。]和车道的最大载重量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.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%.且在近三分之一的情况下，两者得到的目标函数值相同,显示出本算法较好的鲁棒性能.5.2大规模问题与现实调度规则的对比由于目前尚无这方面的实验数据可以进行直接文献比较，本文以现场通常采用的实用调度规则所产生的调度方案作为比较对象.具体包括:按先到先服务原则配载、按装载尽可能多的车辆数配载、按待装车辆重量大小配载和按待装车辆收费高低配载.大规模问题算例设计如下:滚装船舶每层甲板车道条数为6条，航线上共停靠4个港口，第1个港口是装货港，第4个港口是卸货港，中间两个是挂靠港，既有车辆装船也有车辆卸船，且每个可卸货的港口至少都有一条车道的车辆进行卸载,所以最终分配给某个卸货港的车道条数介于1~4条之间.但滚装船配载还要保证船舶的稳性，所以当遇到车道条数为单数时，要将单数车道一分为二，则对于到达某个卸货港的车辆进行装船时，同时进行装载的车道条数最小是2条，最大是4条.候选装船的车辆数随机产生，到达的同一类型的车辆的重量也在一定的范围内随机产生，分别进行100次的随机数值实验.分别对车道数为2、4的大规模配载问题与实用调度规则进行对比，以验证本文算法的有效性.对比结果如图2、图3所示.由上述结果可以看出，本文遗传算法的求解质量明显优于其它常用调度策略，并且运算速度很快.随着车道数的增加，这种优越性更加明显显示了良好的实用性及鲁棒性,可以有效地解决现实规模的滚装船配载优化问题.6.1车辆定位的启发式规则上述优化模型与算法给出了决策变量,即在每一个配载阶段t（也即第t个装货港口）给出了到达每一个目的地港口j的车辆i配载在车道k上，但却无法给出配载所要求的进一步的在每一车道上的具体配载位置.因此，需要依据一定的启发式规则，分配每一辆车在每一条所分配车道的具体位置.现实中常用的启发式规则有:为保证装船稳性，将到达同一港口的车辆在船舱中左右对称摆放;最先卸载的车辆尽量摆放在外侧,最后卸载的车辆尽量摆放在内侧;最先卸载的车辆摆放在前，最后卸载的车辆则摆放在后;到达同一港口的车辆安排在同一条车道上;尽量不要拆分分配给同一港口的双数车道;如分配给某一港口的车道数是双数n,就左右各n/2,如果是单数,就将其一分为二同类车辆排在一起.同一列车道上不同种类车辆的排列顺序要兼顾大小车型尽量均衡的原则，防止船舶发生纵倾到达同一港口的车辆，在对称位置上摆放时，车型的摆放顺序也是对称的;当分属于两个港口的半条车道组成同一条车道时，车型的摆放顺序应上下对称等.6.2配载可视化基于上述规则,本文采用VisualBasic语言开发了滚装船配载车辆定位软件,以实现配载的可视化.通过输入滚装船所装车辆的基本信息(装货港、卸货港、车型、车长、车重、运输价格等),就可以生成配载方案，如图4所示.其中，车道背景不同代表着其各自不同的卸货港，矩形图案不同代表不同的车辆类型.同时,也可以针对不同的配载方案、车辆定位,输出此时滚装船的横倾力矩、纵倾力矩以随时查看，保证船舶的稳性，如图5所示.进而实现配载可视化.本文在建立成品车多装货港、多卸货港的多阶段配载模型的基础上，设计了遗传算法对其进行求解，并通过仿真算例显示了模型的有效性及算法的鲁棒性.并进一步根据实用的启发式车辆定位规则，开发了滚装船舶配载信息管理系统，实现了装载的过程透明化、智能化，以及车辆在船舱内配置的可视化，提高了装卸效率及准确性,有助于提高滚装船运输的安全性.进一步研究将集中于动态配载优化方面，即在配载决策时点，待装运车辆的信息不完全已知情形下的配载优化问题.【相关文献】靳志宏，兰辉，郭贝贝，等.基于现实约束的集装箱配载优化及可视化[J].系统工程理论与实践,2010,30(9):1722-1728.[JINZH,LANH,GUOBB,etal.Optimizationandvisualizationofthecontainerloadingproblemswithrealisticconstraints[J].SystemsEngineering-theory&Practice,2010,30(9):1722-1728.]郭贝贝，靳志宏,石丽红，等.现实约束条件下的集装箱多箱装载优化[J].上海海事大学学报,2009,30:8-13.[GUOBB,JINZH,SHILH,etal.Optimizationofmultiplecontainerloadingunderpracticalconstraints[J].JournalofShanghaiMaritimeUniversity,2009,30(2):8-13.]孙玉昌,龙熙陵.载车状态对滚装船稳性的影响[J].航海工程,2004,4:7-9.[SUNYC,LONGXL.Theinf