Open AccessHybridizing Beam Search with Tabu Search for the Irregular Packing Problem
Author(s) -
Yunqing Rao,
Peng Wang,
Qiang Luo
Publication year - 2021
Publication title -
mathematical problems in engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.262
H-Index - 62
eISSN - 1026-7077
pISSN - 1024-123X
DOI - 10.1155/2021/5054916
Subject(s) - beam search , tabu search , benchmark (surveying) , packing problems , polygon (computer graphics) , sequence (biology) , mathematical optimization , search algorithm , algorithm , generator (circuit theory) , guided local search , hybrid algorithm (constraint satisfaction) , mathematics , best first search , local search (optimization) , computer science , power (physics) , telecommunications , physics , constraint logic programming , geodesy , frame (networking) , quantum mechanics , biology , stochastic programming , constraint programming , genetics , geography
The irregular packing problem involves arranging all the irregular pieces on a plate with the objective of maximizing the use of material. In this article, the layout is formed by the ordered sequence of the irregular pieces which is obtained by a hybrid search algorithm and where the order is decoded by a proposed placement principle. First, a novel no-fit-polygon (NFP) generator is introduced. Then, a placement principle is presented with the new NFP generator. Finally, a search algorithm hybridized with beam search (BS) and tabu search (TS) is proposed to search over the sequence. The numerical experiments with many benchmark problems show that the hybrid algorithm is an applicative and effective approach for solving the irregular packing problem. The hybrid algorithm can produce competitive solutions in less time than many other typical algorithms.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom