摘要
针对二维离线非旋转装箱问题,在凹角和适应值的思想的基础上,提出了一个改进型的Best-Fit启发式算法,并结合基于自然数编码的遗传算法构建了混合算法。同时在遗传迭代过程中,引入二维装箱问题的下界思想作为迭代的终止条件之一,减少了遗传算法无效迭代次数,另外根据问题自身特点,有效地降低了染色体长度,提高了整体的计算速度。在36个标准测试案例的测试基础上与一些经典的算法进行了比较,实验结果表明该算法在工业生产可接受的时间内与其他经典的算法相比能够获得更为满意的结果。
An Improved Best-Fit algorithm（IBF） is proposed as heuristic algorithm based on the concave corner and the fitness strategy.Combining IBF with genetic algorithm based on natural number coding,a hybrid algorithm for the two-dimensional off-line oriented bin packing problem is presented.The low bound value is introduced as one of the conditions for iteration termination in the iteration to reduce the number of invalid iterations.And the length of chromosome is decreased to reduce computing time on account of the characteristics of two-dimensional bin packing problem.The experiments of 36 standard test instances with some classical algorithms from literatures indicate that more satisfactory results can be achieved with the new approach than related classic algorithms in acceptable time for industry production.
出处
《计算机工程与应用》
CSCD
北大核心
2011年第7期16-19,92,共5页
Computer Engineering and Applications
基金
国家自然科学基金No.10571037
黑龙江省教育厅项目No.11511027
哈尔滨理工大学青年科学研究基金(No.2009YFL005)~~
关键词
启发式算法
下界
遗传算法
二维装箱问题
heuristic algorithm
lower bound
genetic algorithm
2D bin packing problem
