基于两阶段混合动态规划算法的龙门吊路径优化

《基于两阶段混合动态规划算法的龙门吊路径优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第２３卷第３期运筹与管理Ｖｏｌ．２３，Ｎｏ．３２０１４年６月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＪｕｎ．２０１４基于两阶段混合动态规划算法的龙门吊路径优化１２１边展，杨惠云，靳志宏（１．大连海事大学交通运输管理学院，辽宁大连１１６０２６；２．大连口岸物流科技有限公司，辽宁大连１１６６０１）摘要：产业界已出现利用多台轨道式龙门吊同时作业以提升集装箱码头装船效率的情况，由于需要确定每台龙门吊的取箱作业集合以及增加了“避免碰撞”、“顺次移动”等现实约束，故其移动路径规划问题在模型建立与求解上比单台轨道式龙门吊更为复杂。本文针对两台轨道式龙门吊同时

2、作业的情形，建立了龙门吊移动路径网络模型，并开发了基于贪婪算法与动态规划的两阶段混合算法，并通过仿真算例，借助与基于实际调度规则所得到的调度方案的对比，验证了模型及优化算法的有效性与实用性。关键词：运筹学；路径规划；贪婪算法；动态规划；两阶段混合算法中图分类号：Ｕ６９５．２２文章标识码：Ａ文章编号：１００７-３２２１（２０１４）０３-００５６-０８OptimizationonLoadingSchedulingforMultipleGantryCranesBasedonTwo-stageHybridDynamicProgramming１２１ＢＩＡＮＺｈａｎ，ＹＡＮＧＨｕｉ-ｙｕｎ，

3、ＪＩＮＺｈｉ-ｈｏｎｇ（１．DalianMaritimeUniversity，CollegeofTransportationManagement，Dalian１１６０２６，China；２．DalianPortLogisticsTechnologyCo．，Ltd，Dalian１１６６０１，China）Abstract：Ｔｈｉｓｐａｐｅｒｄｉｓｃｕｓｓｅｓｔｈｅｌｏａｄｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｏｆｍｕｌｔｉｐｌｅｙａｒｄｃｒａｎｅｓ．Ｔｈｅｐｒｏｂｌｅｍｉｓｔｏｓｃｈｅｄｕｌｅｔｗｏｙａｒｄｃｒａｎｅｓａｔｄｉｆｆｅｒｅｎｔｃｏｎｔａｉｎｅｒｂｌｏｃｋｓｗｈｉｃｈｓｅｒｖｅ

4、ｔｈｅｌｏａｄｉｎｇｏｐｅｒａｔｉｏｎｓｏｆｏｎｅｑｕａｙｃｒａｎｅｓｏａｓｔｏｍｉｎｉ-ｍｉｚｅｔｈｅｔｏｔａｌｄｉｓｔａｎｃｅｏｆｖｉｓｉｔｉｎｇｐａｔｈｓａｎｄｔｈｅｍａｋｅ-ｓｐａｎａｔｓｔａｃｋａｒｅａ．Ａｍａｔｈｅｍａｔｉｃａｌｍｏｄｅｌ，ｗｈｉｃｈｃｏｎｓｉｄｅｒｓｉｎｔｅｒｆｅｒｅｎｃｅｂｅｔｗｅｅｎａｄｊａｃｅｎｔｙａｒｄｃｒａｎｅｓ，ｉｓｐｒｏｖｉｄｅｄｂｙｍｅａｎｓｏｆｔｉｍｅ-ｓｐａｃｅｎｅｔｗｏｒｋｔｏｆｏｒｍｕｌａｔｅｔｈｅｐｒｏｂｌｅｍａｎｄａｔｗｏ-ｓｔａｇｅｈｙｂｒｉｄａｌｇｏｒｉｔｈｍｃｏｍｐｏｓｅｄｏｆｇｒｅｅｄｙａｌｇｏｒｉｔｈｍａｎｄｄｙ

5、ｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇｉｓｄｅｖｅｌｏｐｅｄｔｏｓｏｌｖｅｔｈｅｐｒｏｐｏｓｅｄｍｏｄｅｌ．Ｎｕｍｅｒｉｃａｌｅｘｐｅｒｉｍｅｎｔｓｓｈｏｗｔｈｅｅｆｆｅｃｔｉｖｅｎｅｓｓａｎｄｐｒａｃｔｉｃａｂｉｌｉｔｙｏｆｔｈｅｍｏｄｅｌａｎｄｔｈｅａｌｇｏ-ｒｉｔｈｍｉｎｔｈｉｓｓｔｕｄｙｂｙｍｅａｎｓｏｆｔｈｅｃｏｍｐａｒｉｓｏｎｗｉｔｈａｃｔｕａｌｓｃｈｅｄｕｌｉｎｇｒｕｌｅｓ．Keywords：ｏｐｅｒａｔｉｏｎｓｒｅｓｅａｒｃｈ；ｒｏｕｔｅｐｌａｎｎｉｎｇ；ｇｒｅｅｄｙａｌｇｏｒｉｔｈｍ；ｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇ；ｔｗｏ-ｓｔａｇｅｈｙｂｒｉｄａｌｇｏｒｉｔｈ

6、ｍ０引言为加快装卸速度，缩短船舶在港时间，堆场一般配备多台轨道式龙门吊同时进行作业。码头经营人会详细规划其移动路径、停驻位置与取箱数量，以减少因轨道式龙门吊往复移动所产生的延误，从而提高作业效率。［１］Ｃｈｕｎｇ等最早提出了轨道式龙门吊路径选择问题，目的是减少龙门吊的不必要移动路径，提高作业［２，３］效率。Ｋｉｍ和Ｋｉｍ研究了单台龙门吊的路径优化问题，建立了混合整数规划模型以确定龙门吊在不同［４］贝位的作业顺序及取箱数量。针对同样的问题，Ｋｉｍ和Ｋｉｍ又提出了相应的遗传算法和集束搜索算法。［５］Ｎａｒａｓｉｍｈａｎ和Ｐａｌｅｋａｒ假设出口箱贝位计划已知，以龙门吊作业时间最小化为目

7、标，提出并验证了一个收稿日期：２０１２-０５-１２基金项目：国家自然科学基金项目（７１１７２１０８）；教育部高等学校博士学科点专项科研基金（２０１２２１２５１１０００９）作者简介：边展（１９９０-），女，山东菏泽人，博士研究生，研究方向：物流系统优化；通讯作者：靳志宏（１９６３-），男，辽宁沈阳人，教授，博士生导师，研究方向：物流系统优化。第３期边展，等：基于两阶段混合动态规划算法的龙门吊路径优化５７［６］精确的分支定界算法。Ｋｉｍ等研究了集卡动态到达条件下的单台龙门吊调度问题，