論文

査読有り
2018年1月1日

Efficient overlap detection and construction algorithms for the bitmap shape packing problem

Journal of the Operations Research Society of Japan
  • Yannan Hu
  • ,
  • Sho Fukatsu
  • ,
  • Hideki Hashimoto
  • ,
  • Shinji Imahori
  • ,
  • Mutsunori Yagiura

61
1
開始ページ
132
終了ページ
150
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.15807/jorsj.61.132
出版者・発行元
Operations Research Society of Japan

The two-dimensional strip packing problem arises in wide variety of industrial applications. In this paper, we focus on the bitmap shape packing problem in which a set of arbitrarily shaped objects represented in bitmap format should be packed into a larger rectangular container without overlap. The complex geometry of bitmap shapes and the large amount of data to be processed make it difficult to check for overlaps. In this paper, we propose an efficient method for checking for overlaps and design efficient implementations of two construction algorithms, which are based on the bottom-left strategy. In this strategy, starting from an empty layout, items are packed into the container one by one. Each item is placed in the lowest position where there is no overlap relative to the current layout. We consider two algorithms, the bottom-left and the best-fit algorithm, which adopt this strategy. The computational results for a series of instances that are generated from well-known benchmark instances show that the proposed algorithms obtain good solutions in remarkably short time and are especially effective for large-scale instances.

リンク情報
DOI
https://doi.org/10.15807/jorsj.61.132
ID情報
  • DOI : 10.15807/jorsj.61.132
  • ISSN : 0453-4514
  • SCOPUS ID : 85040345838

エクスポート
BibTeX RIS