变尺寸装箱问题的迭代/贪婪动态规划算法

• 作者: 姚汝林 尹石军 郭蕴华
• 来源期刊: 江苏船舶
• 关键词: 变尺寸装箱 动态规划 启发式 船舶建造 管材切割
• 年，卷（期）: 2021,（1）
• 所属期刊栏目: 船舶设计与研究
• 页码范围: 1-4
• 页数: 4页
• 分类号: U671.91+3
• 语种: 中文
• DOI: 10.19646/j.cnki.32-1230.2021.01.001

摘要

针对船舶建造中管材切割规划这一类特殊的变尺寸装箱问题,提出了一种迭代贪婪/动态规划算法(IGDP)并对其进行求解.首先,提出了求解子集和问题的贪婪操作与动态规划的组合解法.然后,基于贪婪操作与动态规划的组合解法实现对整个问题的构造启发式求解,并且通过迭代的拆箱/再分配操作提高了算法的局部搜索能力.最后,通过8个算例的仿真实验,对所提算法与现有算法进行了性能比较.结果表明:IGDP的性能优于现有算法,且具有可以接受的计算耗费.