二维离线非旋转装箱问题的一个混合算法

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (7): 16-19.

二维离线非旋转装箱问题的一个混合算法

曹大勇1，杨梅2，刘润涛3

1.哈尔滨理工大学应用数学系，哈尔滨 150080
2.哈尔滨工业大学电气工程系，哈尔滨 150001
3.哈尔滨理工大学信息与科学计算技术研究所，哈尔滨 150080

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-03-01 发布日期:2011-03-01

Hybrid algorithm for two-dimensional off-line oriented bin packing problem

CAO Dayong1，YANG Mei2，LIU Runtao3

1.Department of Applied Mathematics，Harbin University of Science and Technology，Harbin 150080，China
2.Department of Electrical Engineering，Harbin Institute of Technology，Harbin 150001，China
3.Institute of Information and Scientific Computing，Harbin University of Science and Technology，Harbin 150080，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-03-01 Published:2011-03-01

摘要/Abstract

摘要： 针对二维离线非旋转装箱问题，在凹角和适应值的思想的基础上，提出了一个改进型的Best-Fit启发式算法，并结合基于自然数编码的遗传算法构建了混合算法。同时在遗传迭代过程中，引入二维装箱问题的下界思想作为迭代的终止条件之一，减少了遗传算法无效迭代次数，另外根据问题自身特点，有效地降低了染色体长度，提高了整体的计算速度。在36个标准测试案例的测试基础上与一些经典的算法进行了比较，实验结果表明该算法在工业生产可接受的时间内与其他经典的算法相比能够获得更为满意的结果。

关键词: 启发式算法, 下界, 遗传算法, 二维装箱问题

Abstract: 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.

Key words: heuristic algorithm, lower bound, genetic algorithm, 2D bin packing problem

曹大勇1，杨梅2，刘润涛3. 二维离线非旋转装箱问题的一个混合算法[J]. 计算机工程与应用, 2011, 47(7): 16-19.

CAO Dayong1，YANG Mei2，LIU Runtao3. Hybrid algorithm for two-dimensional off-line oriented bin packing problem[J]. Computer Engineering and Applications, 2011, 47(7): 16-19.

[1]	李昱奇，刘志乾，程凝怡，王莹莹，朱春丽. 多约束条件下无人机航迹规划[J]. 计算机工程与应用, 2021, 57(4): 225-230.
[2]	杨玮，吴莹莹，王婷. 子母式穿梭车仓储系统配置优化问题研究[J]. 计算机工程与应用, 2021, 57(4): 258-265.
[3]	程帅，吴华锋，梅骁峻. 交替非负约束框架的海洋传感网协同定位[J]. 计算机工程与应用, 2021, 57(23): 129-136.
[4]	李倩，蒋丽，梁昌勇. 基于模糊时间窗的多目标冷链配送优化[J]. 计算机工程与应用, 2021, 57(23): 255-262.
[5]	杜守信，毋涛. 双种群混合遗传算法的裁剪分床应用研究[J]. 计算机工程与应用, 2021, 57(22): 182-189.
[6]	曹立佳，刘洋. 制造车间自动导引车调度新进展[J]. 计算机工程与应用, 2021, 57(21): 59-67.
[7]	陈倩茹，李雅丽，许科全，刘铱龙，王淑琴. 自调优自适应遗传算法的WKNN特征选择方法[J]. 计算机工程与应用, 2021, 57(20): 164-171.
[8]	石宇强，田永政，张雨琦，石小秋. 运用含复杂网络结构的多种群遗传算法求解FJSP[J]. 计算机工程与应用, 2021, 57(2): 257-266.
[9]	代江涛，韩晓龙. 考虑作业状态能耗的集装箱码头设备协调调度[J]. 计算机工程与应用, 2021, 57(19): 290-298.
[10]	张呈玲，李进金，林艺东. 基于OE-概念格的形式背景属性约简[J]. 计算机工程与应用, 2021, 57(15): 82-89.
[11]	冯晓东，黄世荣，戴冠鸥，杨伟家，罗尧治. 天牛须遗传杂交算法的研究与应用[J]. 计算机工程与应用, 2021, 57(15): 90-100.
[12]	苏庆，林华智，黄剑锋，林志毅. 结合CNN和Catboost算法的恶意安卓应用检测模型[J]. 计算机工程与应用, 2021, 57(15): 140-146.
[13]	姜良重，雷航，李贞昊，钱伟中，施甘图. 采用自适应优化权重的出库货位优化方法研究[J]. 计算机工程与应用, 2021, 57(15): 271-278.
[14]	贺娇，谭代伦. 基于视野范围和遗传算法的三维地形路径规划[J]. 计算机工程与应用, 2021, 57(15): 279-285.
[15]	王秀丽，周鹏，侯静楠，王仕俊，林霞. 面向变电站机器人巡检路径规划中的算法研究[J]. 计算机工程与应用, 2021, 57(14): 245-250.