求解长方体Packing问题的纯粹拟人算法

被引：8

作者：

黄文奇

何琨

机构：

[1] 华中科技大学计算机科学与技术学院

来源：

中国科学(F辑:信息科学) | 2009年 / 39卷 / 06期

基金：

中国博士后科学基金;

关键词：

Packing问题; NP难度; 启发式算法; 拟人方法; 穴度;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

对于具有NP难度的长方体Packing问题,挖掘出了中国古代谚语"金角银边草肚皮"中隐藏的智慧,并进一步发展出新子句"价值最高钻石穴".在利用现代西方的先进数学工具经过确切化、完整化与形式化后,得出了一种纯粹拟人型的求解算法.试算了国际上公开通行的两组有代表性的算例(benchmark).对于100个强异构型的困难算例,所得布局图案达到了87.31%的平均空间利用率,刷新了当今国际上的最好纪录,将它提高了1.83个百分点.对于47个无方向约束的困难算例,得到了92.05%的平均空间利用率,将当今国际上的最好纪录提高了1.05个百分点.

引用

页码：617 / 622

页数：6

共 10 条

[1] 求解Packing问题的拟物方法 [J].

黄文奇 ;

詹叔浩 .

应用数学学报, 1979, (02) :176-180

[2] A multi-faced buildup algorithm for three-dimensional packing problems [J].

Lim, A ;

Rodrigues, B ;

Wang, Y .

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2003, 31 (06) :471-481

[3]

A Parallel Genetic Algorithm for Solving the Container Loading Problem.[J].Hermann Gehring;Andreas Bortfeldt.International Transactions in Operational Research.2002, 4

[4] A hybrid genetic algorithm for the container loading problem [J].