Hybrid genetic algorithm and simulated annealing for two-dimensional non-guillotine rectangular packing problems

Soke A., Bingul Z.

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE, vol.19, pp.557-567, 2006 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 19
  • Publication Date: 2006
  • Doi Number: 10.1016/j.engappai.2005.12.003
  • Journal Name: ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.557-567
  • Keywords: genetic algorithm, improved bottom left algorithm, Simulated annealing, two-dimensional non-guillotine rectangular packing problems, CUTTING STOCK PROBLEM, ORTHOGONAL PACKING, SEARCH
  • Kocaeli University Affiliated: Yes

Abstract

In this paper, genetic algorithm (GA) and simulated annealing (SA) with improved bottom left (BL) algorithm were applied to two-dimensional non-guillotine rectangular packing problems. The performance and efficiency of these algorithms on several test problems [Hopper, E., Turton, B.C.H., 2000. An empirical investigation of meta-heuristic and heuristic algorithms for two-dimensional packing problem. European Journal of Operational Research 128 (1), 34-57] were compared. These test problems consist of 17 and 29 individual rectangular pieces to place in main object limited with a size of 200 x 200 units. Both solution approaches were compared, based on the trim losses of the test problems. Also, the influences of the GA parameters (population sizes, mutation rates. crossover techniques) and of the SA parameters (cooling schedules, neighborhood moves, the number of inner loop, different temperature values) on the solution of these problems were examined. For considering all solutions of the test problems, the hybrid GA produces much better results than the hybrid SA. (c) 2006 Elsevier Ltd. All rights reserved.