文献类型：期刊文献

中文题名：基于最小松弛量的启发式一维装箱算法

英文题名：Heuristic One-dimensional Bin Packing Algorithm Based on Minimum Slack

作者：罗飞[1];任强[1];丁炜超[1];卢海峰[1]

机构：[1]华东理工大学信息科学与工程学院

年份：2019

卷号：46

期号：9

起止页码：315

中文期刊名：计算机科学

外文期刊名：Computer Science

收录：CSTPCD;;北大核心:【北大核心2017】；CSCD:【CSCD_E2019_2020】；

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

语种：中文

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

外文关键词：Bin packing problem;Heuristic algorithm;Random algorithm;Monte Carlo

摘要：一维装箱问题是组合优化中的NP难问题,在有限的时间内获得问题的精确解非常困难。启发式算法和遗传算法是解决装箱问题的两类主要方法,但是,采用经典启发式装箱算法得到的结果在极端情况下非常差,而遗传算法在解决装箱问题的过程中容易出现无效解,致使需要处理的数据量十分巨大。为了获得装箱问题的近似最优解,文中针对目前的装箱问题算法展开分析,提出了一种新型的启发式装箱算法。提出的IAMBS算法允许装箱有一定的松弛量,使用随机思想搜索局部最优,进而获得装箱问题的全局最优解。随机松弛量使该算法不易陷入局部最优,具有较强的发现全局最优解的能力。采用来自两个数据集的1410个基准测试实例进行实验。最终,IAMBS算法获得了1152个实例的最优解。实验数据表明,IAMBS算法可以有效地获得近似最优解,比经典装箱算法更有优势。
The one-dimensional bin packing problem is a NP-hard problem in the combinatorial optimization,and it is extremely difficult to obtain an accurate solution of the problem in a limited time.Heuristic algorithms and genetic algorithms are the two main methods to solve the bin packing problem.However,the results obtained by the classical heuristic packing algorithm are very poor in extreme cases.The genetic algorithm is prone to generate invalid solutions in the process of solving the packing problem,thus resulting in large amount of data to be processed.In order to obtain the approximate optimal solution of the packing problem,this paper analyzed the current packing problem algorithm and proposed a new heuristic packing algorithm.The proposed IAMBS algorithm uses the idea of random to search for local optimum by allowing a certain amount of slack in the bin-packing,and then obtains the global optimal solution of the packing problem.The allowable slack can prevent this algorithm from falling into local optimum,and has strong ability to discover global optimal solutions.1 410 benchmark test instances from two sources were utilized for the experiment,and the optimal solution of 1 152 instances were implemented by the IAMBS algorithm.Experimental data demonstrate that the IAMBS algorithm can effectively obtain the approximate optimal solution,and it is more advantageous than the traditional classical packing algorithm.