基于改进布谷鸟算法的集装箱码头配载优化研究.pdf
《基于改进布谷鸟算法的集装箱码头配载优化研究.pdf》由会员分享,可在线阅读,更多相关《基于改进布谷鸟算法的集装箱码头配载优化研究.pdf(7页珍藏版)》请在咨信网上搜索。
1、引用NAVIGATIONOFCHINASep.20232023年9 月Vol.46 No.3中国第46 卷第3期海航文章编号:10 0 0-46 53(2 0 2 3)0 3-0 0 6 5-0 7基于改进布谷鸟算法的集装箱码头配载优化研王永金2,黄鹏飞12,陈麒龙,储雨峰1-2,张宁1,2(1.集美大学航海学院,福建厦门36 10 2 1;2.集美大学海上交通运行智能控制与仿真技术国家地方联合工程研究中心,福建厦门36 10 2 1)摘要:为对集装箱码头配载问题进行研究,在满足船舶适航性的基础上,建立了以集装箱水平运输时间、岸桥作业时间以及堆场倒箱时间最短为目标的多约束的数学模型。将改进的布
2、谷鸟算法(Improved Cuckoo Search,ICS)应用求解,首先在布谷鸟算法的莱维飞行阶段,分别从种群整体、当代最优、自身个体中抽取鸟巢信息,建立不同的鸟巢位置更新模式;其次,采用动态机制控制发现概率P。;最后计算每个鸟巢的适应度,来找到最优解。试验表明:改进的布谷鸟算法可以有效找到最优解,优化结果相比较于标准的布谷鸟算法提升2 5%,该方法具有可行性和有效性。关键词:集装箱船舶;配载;改进布谷鸟算法中图分类号:U169.65文献标志码:AD0I:10.3969/j.issn.1000-4653.2023.03.010Loading optimization for contai
3、ner terminal basedon Improved Cuckoo Search algorithmWANG Yongjinl-2,HUANG Pengfeil-2,CHEN Qilong,(CHU Yufengl-2,ZHANG Ningl.2(1.Navigation College,Jimei University,Xiamen 361021,China;2.National Local Joint Engineering Research Center for Ship-Aided Navigation Technology,Jimei University,Xiamen 361
4、021,China)Abstract:A multi-constraint optimization model is built to minimize horizontal container transportation time,quayoperation time and container dumping time in the yard under the condition of maintain the seaworthiness of the ship.TheImproved Cuckoo Search algorithm is used to solve the prob
5、lem.The nest information is extracted from the population as awhole,the contemporary optimal solution and its own individuals in the Levi flight stage and a variety of location updatingmodes are established.The discovery probability P,is controlled by dynamic mechanism.The optimal solution is found
6、bycalculating the fitness function value of each net.Experiments are carried out with a typical data set.For the cited data,the optimization result is 25%higher than that produced by conventional cuckoo algorithm.Which proves the feasibility andeffectiveness of the method.Key words:container ship;lo
7、ading;Improved Cuckoo Search algorithm集装箱船舶配载在实际的操作过程中是一个多约束、多目标组合优化问题。配载计划的优劣程度关系到集装箱船舶在港口的装卸效率、船舶的适航性等。近些年来,我国港口集装箱吞吐量成倍增长,这给集装箱船舶配载带来了很大压力。本文的研究目的就是在现有大批量集装箱配载的条件下,提高配载的效率并保证配载计划结果的最优化。现有的集装箱船舶配载研究应用的算法主要有收稿日期:2 0 2 2-0-1基金项目:福建省自然科学基金资助项目(2 0 2 1J01820)作者简介:王永金(19 9 6 一),男,硕士研究生,研究方向为交通运输系统规划与管理
8、。E-mail:通信作者:黄鹏飞(19 7 5一),男,副教授,研究方向为交通运输工程。E-mail:格式:王永金,黄鹏飞,陈麒龙,等.基于改进布谷鸟算法的集装箱码头配载优化研究J.中国航海,2 0 2 3,46(3):6 5-7 1.WANG Y J,HUANG P F,CHEN Q L,et al.Loading optimization for container terminal based on Improved Cuckoo Search algorithmJ.Navigation of China,2023,46(3):65-71.(in Chinese)中海国66第46 卷第3
9、期航遗传算法、蚁群算法和禁忌搜索算法等,研究内容主要从船舶预配计划和码头实配计划2 种研究角度进行。关于集装箱船舶配载研究,AMBROSINO等2 针对集装箱配载问题,在禁忌搜索算法的基础上,利用蚁群算法对问题进行求解,但此研究只考虑到了船舶配载,没有综合考虑堆场的情况。为了更综合地考虑码头的实际配载,田维等3 提出解决集装箱码头配载堆场取箱顺序问题,设计了一个三阶段启发式算法,来对堆场提箱顺序与船舶贝内配载计划进行联合优化求解。PARRENO等41针对配载问题,将一种不同的整数规划模型和贪婪随机自适应搜索算法相结合,能够在很短的时间之内找到最优方案。黄莉莉5 在考虑码头协调作业的前提下研究了
10、集装箱船舶自动配积载的方法,利用基于产生式规则的专家系统进行算法求解和全局优化。关于求解配载问题的算法研究,现有的研究主要采用传统整数规划方法、启发式算法较多。田维等6 和DING等7 都采用了启发式算法求解配载问题,并用实例证明了该算法可以有效解决小规模配载问题。AZEVEDO等8 建立了一个以翻箱量和稳性为目标的函数,并通过实例数据对比了常见启发式算法。在此基础上,ARAUJO等9 针对此双目标数学模型,采用帕累托聚类搜索算法来进行求解。PARRENO等【10 采用了贪婪随机自适应搜索算法求解配载中的箱位计划问题的整数规划模型。汪圆圆等1-1 和王雅芬等13 针对贝内配载问题采用粒子L.1
11、1-12群算法进行求解,但文中所用试验数据规模较小。本文针对上述研究的不足,建立了考虑堆场翻箱时间、集卡运输时间和岸桥作业时间的优化模型,提出了一种改进的布谷鸟算法对所建立的集装箱码头配载模型进行求解,并以一条实例船舶配载验证了算法的有效性。1问题描述集装箱配载计划是提高码头作业效率的关键。集装箱实配计划是已知待装集装箱和待装集装箱在堆场的位置等信息的条件下,在满足船方预配载计划的要求下综合考虑堆场情况、装卸设备以及翻倒箱等因素,寻找最佳的配载方案,使待装集装箱具体安排到船舶上合理的位置14。O集装箱实际积载的过程是一个从堆场取箱,经过集卡运输至岸边,再由岸桥装载到船上的多环节且复杂的过程。堆
12、场箱位的位置选择、集卡运输路径的选择和岸桥装卸模式的选择构成了一个复杂决策的网络模型,因此配载计划的制订必须合理综合考虑各个环节,使各个环节协调运作。因为现在集装箱船舶越来越朝着大型化的方向发展,所以对配载计划制订的速度和合理性都提出了较高要求。本文从上述说明的方向出发,建立考虑多环节协作的配载优化模型,并采用高效的智能优化算法进行求解。2模型建立在进行集装箱船舶配载的过程中,码头方要保证集装箱船舶能够依照靠泊计划按时离港,所以装卸速度和效率是关键因素。本文在综合考虑研究意义及现实意义的情况下,建立一个考虑多因素的配载模型,将翻箱量最少、装卸效率最大作为目标的数学模型,并用改进的布谷鸟算法进行
13、求解。2.1假设条件1)在码头进行实际配载之前,预配船图应由船方提供给码头方,保证待配载集装箱的各种信息(如尺寸大小)都已知。本文从码头的视角出发,主要考虑码头方装船配载方案的优化。2)本文考虑的是单船配载作业,且为了避免装卸同时进行时设备冲突的增加以及翻箱量的上升,不考虑边装边卸。为了建模的方便,做出以下合理的假设条件:冷藏箱、危险品箱等特殊箱已设定具体配载位置,同时不考虑垫脚箱;码头机械设备(像岸桥、场桥等)数量充足,配置合理,确保配载过程的效率不受大的影响,同时配载作业过程中不受机械故障停修的影响;装卸不同工艺的集装箱所用的时间相同,集装箱作业工艺不影响作业时间;预配待出口集装箱的数量不
14、超过计划可装载的船箱位数量。2.2参数定义m为贝位号,贝位号集合M=1,2,m;c为列号,列号集合C=1,2,,c;r 为层号,层号集合R=1,2,r;b为堆场箱区具体编号,B=1,2,,b ;i j 为码头堆场待装集装箱编号,I=1,2,,i,J=1,2,jl;P为船舶箱位集合,p(m,c,r)为船箱位具体编号,其中peP;8,为堆场箱位p(k,c,r)的开始装箱时间;U(p)为位于船舶箱位p(k,c,r)同贝同列上一层p(k,c,r+1)的箱位;t表示时间间隔,T=1,2,t,V t e T;A,为与集装箱i同一堆栈的上层集装箱集合;,为堆场翻一次箱所需要的时间;w;位集装箱i的质量;nb
15、为t时间段内箱区b已完成堆场到船任务的集装箱数量;e。为岸67王永金,等:基于改进布谷鸟算法的集装箱码头配载优化研究桥o完成集装箱i到相应船箱位所用的时间;Wm为船舶贝位m中单列允许的集装箱最大载重量;Tip为集装箱i从堆场箱位到船箱位p(k,c,r)的水平运输时间;Li,为场箱位为i装载到船箱位p(k,c,r)的离场时间,L,=8,-Tip,其中Viel,peP;u为箱区b在时间段t的箱区作业量阈值;Q为一个极大的正数。2.3决策变量当且仅当待装船集装箱i符合预配图要求从而配载到船舶所对应的船舶箱位p(m,c,r)为1,否则为0。当且仅当待装船集装箱i位于箱区b为1,否则为0。xjucp)当
16、且仅当集装箱配载到船箱位p(m,c,r+1)上时为1,否则为0。x,当且仅当集装箱i配载到船箱位p上时为1,否则为0。z,当且仅当集装箱i在集装箱j之前配载时为1,否则为0。其中je;2.4目标函数及约束条件mina:ZTipip+2012+PEPieljeAi3(1)iE1PEp式(1)中:第一部分minnZ.Ti表示完成ielpeP配载计划集装箱所需的水平运输时间最短;第二部分min三表示堆场翻箱时间最短;第三部IjeA;分e,岸桥完成装卸任务所用的时间,其中ielpeP12;均为大于零的权重系数15S.T.1(2)ielpePt-(s,-Lp)xip=O,VieI,peP,t=T(3)W
17、;ipwju(p)(4)jeJ(5)jeAPEPielpePxipX;U(p)(6)ie1ielxipip(7)ieTPEPielpeP1Wm,VmEM(8)B0.ixip=nb(9)6-1nb,bEB,tET(10)式(2)表示一个船箱位只能装载一个集装箱;式(3)表示待装集装箱离开箱区必须符合桥吊作业的时间安排;式(4)表示箱区集装箱轻不压重的堆垛要求;式(5)表示位于同一堆场不同层数的待装集装箱离开箱区的先后顺序和翻箱的关系;式(6)表示待装集装箱在船舶箱位紧挨着的下方有集装箱,即不能悬空;式(7)表示待装集装箱与船舶贝位的匹配满足预配要求;式(8)表示贝位配载的集装箱的总质量不能超过额
18、定质量;式(9)表示确保离场集装箱数量与待装集装箱数量相同;式(10)表示箱区作业量限制,防止作业量过大。3ICS算法设计3.1ICS算法适用性说明CS算法作为一种新型启发式算法,它具有参数少、操作简单和全局寻优能力强的优点,尤其对于集装箱船舶配载计划这种NP-hard问题,其优化问题能力优于遗传算法和粒子群算法,但面对多维且复杂的适应度函数时,其收敛速度会变慢且易早熟,容易陷入局部最优16 。针对CS算法求解此类问题的缺陷,本文采用ICS算法进行求解,运用信息交互式动态选择的位置更新模式,增加算法寻优的速度,同时也避免其过早陷人局部最优。3.2莱维飞行机制的改进在传统的CS算法中,虽然莱维飞
19、行机制能够进行短步长与长步长相互交替,有效探索全局空间,但其中长步长将短步长组成的集聚分隔开来,短步长出现的频率较高,长步长出现的频率较低,随着迭代次数的增加,种群个体之间的相似概率增加,算法容易陷入局部极值。另外,在莱维飞行过程所采取的机制中,采集到的个体信息片面。为了解决这样的问题,在每一次鸟巢迭代的过程中引人新的鸟巢信息,在鸟巢位置更新方式中加入鸟巢的交互信息,以此来保证鸟巢搜索过程中信息的多样性,以增加搜索的范围。交互信息能够体现出不同个体之间适应度的差异,以此来判断算法的进化方向,提高搜索的精度、速度和收敛速度13。改进的莱维机制数学表达式如下所示:rif(AF&A1-F)(xi+a
20、Levy(入)+(Cauchy?xj-x)(11)中海国68航第46 卷第3期式(14)中。Fe0,1,A=rand(0,p,),P,为鸟巢总数,xjvu是两个随机鸟巢,nebest为当前迭代最优鸟巢,步长因子表达式为:a=0.01(xi:-X nebest)(12)的数学表达式为:auc1m=0.5+auchyarctanTg(13)tan(m-0.5)auchy其中,g=1为尺度参数。式(11)中,创建了3组鸟巢位置的更新方式,不同种群之间的差值搭建起不同种群之间的信息交互机制,这其中包括种群整体(N)、当代最优(N)、当前个体(N,),并从这三个种群中获取交互信息,并加人鸟巢位置更新中,
21、并计算当前鸟巢的适应度值,再随机选取位置更新策略。交互信息对随机鸟巢的影响很大,为了保证交互信息的全面性和综合性,此处引人Cauchy算子,利用Cauchy算子对鸟巢进行扰动,cauehy算子具有遍历所有种群个体并不重复的能力,这种方式可以有效收集种群信息。更新策略1中,个体的差异度体现在种群内两个随机鸟巢之间的差值(构建N,与N,的交互信息),在N,&N,(种群整体)范围之内全局寻优;更新方式2 中,计算N,与N,适应度的区别(构建N与N,之间的交互信息),在N,&N的维度上更新鸟巢位置;更新方式3中,构建N,与N,之间的交互信息,因为N,与N,之间存在一定差异。通过构建种群Ni、N和N,之
22、间的交互信息,可以有效避免迭代鸟巢信息单一化和片面化,扩展了算法的搜索领域和寻优能力,以一种动态的方式找寻最优解,避免了静态寻优方法的缺陷3.3发现概率的改进算法研究发现,如果发现概率P。越大,其收敛速度就越快,搜索能力就越强;P。值越小,越不利于收敛速度及搜索精度17 ,因此,本文采用动态机制:DPD一taaminamaxamin(14)Pla为第t代种群的第i个个体的发现概率,Pmax为发现概率的上限,Pamin为发现概率的下限,fbest、Jf r i分别为最优个体和当期个体的目标函数值18 ICS算法实现流程如图1所示。ICS算法的主要步骤为:1)设置种群的规模、初始的位置、代的次数等
23、参数。2)计算种群中每个个体的适应度,并保留最开始设置种群个数、送迭代的次数、维度、鸟巢初始化操作计算种群中所有个体的适应度,并保留最优解根据式(14)进行位置的更新计算所有个体的适应度,并保留最优解到下一代根据式(14)进行位置更新是HPaa根据公式(17)位置不变计算发现概率计算适应度,并保留最优鸟巢至下次进化是否达到算法终止条件是输出最终结果结束图1ICS算法流程图Fig.1ICS algorithm flow chart优解。3)根据式(11)将位置进行更新,再计算位置更新后所有个体的适应度,通过精英策略将最优解保留至下一代。4)通过式(14)计算发现概率,比较P。与随机函数生成的随机
24、数H的大小。如果HP。,则丢弃此劣质鸟巢,继续更新;否则,保留当前鸟巢位置。5)计算步骤4)之后的所有鸟巢的适应度,最优的鸟巢将进人到下一轮的迭代。6)如果最终结果满足算法结束条件,则输出最后结果;反之,返回步骤3)继续迭代,直到迭代结果满足终止条件。3.4编码方式集装箱码头船舶配载的核心问题在于在满足约束条件、使目标函数达到最优的情况下确定待装集装箱在船上的位置,使得最初的配载计划既满足船方的配载要求也能满足码头方的配载目标和要求,所以采用图2 的编码方式来确定集装箱在堆场的位置和安排船舶舱位的位置。本文的假设条件中,假设码头方的各作业计划已知,其中包括桥吊作业和场桥作业的计划是已知的,因此
25、相对应船贝的作业顺序和作业开始时间也可以确定,对应堆场集装箱安排到具体的船箱位也是确定的,船箱位的配载次序也可以得到。本文设计了自然数n代表场箱位进行了实数编码,自然数王永金改进布谷鸟算法的集装箱码头配载优化研究69m代表船舶舱箱位编码顺序19 。如图2 所示的编码的上层代表场箱位,下层代表船舶舱箱位。图2展示了n个场箱位匹配船箱位的匹配关系图。4771958668999n一361117445564m图2编码顺序Fig.2Coding sequence如图2 所示,第一列表示为场箱位编号为4的待装集装箱匹配船箱位为1的位置,第四列表示为第19 位场箱位装载船箱位为11的位置。按照这样的编码方式
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 改进 布谷鸟 算法 集装箱码头 配载 优化 研究
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。