Tabu Search with Consistent Neighbourhood for Strip Packing

被引:0
作者
Gomez-Villouta, Giglia [1 ]
Hamiez, Jean-Philippe [1 ]
Hao, Jin-Kao [1 ]
机构
[1] Univ Angers, LERIA, F-49045 Angers, France
来源
TRENDS IN APPLIED INTELLIGENT SYSTEMS, PT I, PROCEEDINGS | 2010年 / 6096卷
关键词
ALGORITHM;
D O I
暂无
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
This papal introduces anew tabu search algorithm for a strip packing problem It, integrates several key features A consistent neighborhood, a fitness function including problem knowledge, and a diversification based on the history of the search. The neighborhood only considers valid, sometimes partial, packings The fitness function incorporates measures related to the empty spaces. Diversification relies on a set of historically "frozen" objects Experimental results are shown on a set of well-known hard instances and compared with previously reported tabu search algorithms as well as the best performing algorithms.
引用
收藏
页码:1 / 10
页数:10
相关论文
共 21 条
[1]   Reactive GRASP for the strip-packing problem [J].
Alvarez-Valdes, R. ;
Parreno, F. ;
Tamarit, J. M. .
COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (04) :1065-1083
[2]   A tabu search algorithm for a two-dimensional non-guillotine cutting problem [J].
Alvarez-Valdes, R. ;
Parreno, F. ;
Tamarit, J. M. .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 183 (03) :1167-1182
[3]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[4]  
Araya I., 2008, Adaptive and Multilevel Metaheuristics, volume 136 of Studies in Computational Intelligence, chapter An Efficient Hyperheuristic for Strip-Packing Problems, P61, DOI DOI 10.1007/978-3-540-79438-7_3
[5]   ORTHOGONAL PACKINGS IN 2 DIMENSIONS [J].
BAKER, BS ;
COFFMAN, EG ;
RIVEST, RL .
SIAM JOURNAL ON COMPUTING, 1980, 9 (04) :846-855
[6]   A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces [J].
Bortfeldt, A .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 172 (03) :814-837
[7]   THE BOTTOM-LEFT BIN-PACKING HEURISTIC - AN EFFICIENT IMPLEMENTATION [J].
CHAZELLE, B .
IEEE TRANSACTIONS ON COMPUTERS, 1983, 32 (08) :697-707
[8]   PACKING PROBLEMS [J].
DOWSLAND, KA ;
DOWSLAND, WB .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1992, 56 (01) :2-14
[9]  
ELHAYEK J, 2006, THESIS U TECHNOLOGIE
[10]   OPTIMAL PACKING AND COVERING IN THE PLANE ARE NP-COMPLETE [J].
FOWLER, RJ ;
PATERSON, MS ;
TANIMOTO, SL .
INFORMATION PROCESSING LETTERS, 1981, 12 (03) :133-137