Exact algorithms for the rectilinear block packing problem

DOI Web Site 参考文献21件 オープンアクセス
  • MATSUSHITA Ken
    Department of Mathematical Informatics, Graduate School of Informatics, Nagoya University
  • HU Yannan
    Department of Mathematical Informatics, Graduate School of Informatics, Nagoya University
  • HASHIMOTO Hideki
    Department of Logistics and Information Engineering, Tokyo University of Marine Science and Technology
  • IMAHORI Shinji
    Department of Information and System Engineering, Chuo University
  • YAGIURA Mutsunori
    Department of Mathematical Informatics, Graduate School of Informatics, Nagoya University

抄録

<p>The rectilinear block packing problem is a problem of packing a set of rectilinear blocks into a larger rectangular container with fixed width and unrestricted height. A rectilinear block is a polygonal block whose interior angles are either 90◦ or 270◦. The objective is to pack all the blocks into the container so as to minimize the height of the container. This problem is among classical combinatorial optimization problems and is known to be NP-hard. In this paper, we propose two exact algorithms for the rectilinear block packing problem: one is based on two IP problems and the other is based on a new solution representation. The basic idea of our algorithms is that we iteratively compute lower and upper bounds on the optimal value until the lower bound on the value of an optimal solution for the current search space becomes larger than or equal to the best upper bound found during the search by then, or the search space becomes empty, which means that an optimal solution of this problem has been found. The computational results show that both algorithms obtain five exact and one heuristic solutions for six instances. The algorithm based on a new solution representation improves the running time of the algorithm based on two IP problems.</p>

収録刊行物

参考文献 (21)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ