Tabu Search with Consistent Neighbourhood for Strip Packing

TitreTabu Search with Consistent Neighbourhood for Strip Packing
Type de publicationCommunication
TypeCommunication avec actes dans un congrès
Date du colloque2010
Titre du colloque23rd International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2010
Titre des actes ou de la revueTrends in Applied Intelligent Systems
Pagination1 - 10
AuteurGómez-Villouta, Giglia, Hamiez, Jean-Philippe , Hao, Jin-Kao
ISBN978-3-642-13021-2 / 978-3-642-13022-9
Mots-clésalgorithm analysis and problem complexity, Artificial Intelligence (incl. Robotics), Computation by Abstract Devices, consistent neighborhood, Database Management, Information Storage and Retrieval, Information Systems Applications (incl.Internet), Strip packing, tabu search
Résumé en anglais

This paper introduces a new 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.


Date du colloque : 06/2010

URL de la notice
Lien vers le document en ligne