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

Soke A., Bingul Z.

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

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 19
  • Basım Tarihi: 2006
  • Doi Numarası: 10.1016/j.engappai.2005.12.003
  • Dergi Adı: ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.557-567
  • Anahtar Kelimeler: genetic algorithm, improved bottom left algorithm, Simulated annealing, two-dimensional non-guillotine rectangular packing problems, CUTTING STOCK PROBLEM, ORTHOGONAL PACKING, SEARCH
  • Kocaeli Üniversitesi Adresli: Evet

Özet

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.