基于最小松弛量的启发式一维装箱算法

摘要：

一维装箱问题是组合优化中的NP难问题,在有限的时间内获得问题的精确解非常困难.启发式算法和遗传算法是解决装箱问题的两类主要方法,但是,采用经典启发式装箱算法得到的结果在极端情况下非常差,而遗传算法在解决装箱问题的过程中容易出现无效解,致使需要处理的数据量十分巨大.为了获得装箱问题的近似最优解,文中针对目前的装箱问题算法展开分析,提出了一种新型的启发式装箱算法.提出的IAMBS算法允许装箱有一定的松弛量,使用随机思想搜索局部最优,进而获得装箱问题的全局最优解.随机松弛量使该算法不易陷入局部最优,具有较强的发现全局最优解的能力.采用来自两个数据集的1410个基准测试实例进行实验.最终,IAMBS算法获得了1152个实例的最优解.实验数据表明,IAMBS算法可以有效地获得近似最优解,比经典装箱算法更有优势.

关键词：装箱问题、启发式算法、随机算法、蒙特卡洛

所属期刊栏目：46

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金61472139;华东理工大学2017年教育教学规律与方法研究项目ZH1726107

在线出版日期：2019-10-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：315-320