Heuristic and Metaheuristic Approaches for a Class of Two-Dimensional Bin Packing Problems

DOI Web Site 7 Citations
  • Andrea Lodi
    Dipartimento di Elettronica, Informatica e Sistemistica, University of Bologna, Viale Risorgimento, 2-40136 Bologna, Italy
  • Silvano Martello
    Dipartimento di Elettronica, Informatica e Sistemistica, University of Bologna, Viale Risorgimento, 2-40136 Bologna, Italy
  • Daniele Vigo
    Dipartimento di Elettronica, Informatica e Sistemistica, University of Bologna, Viale Risorgimento, 2-40136 Bologna, Italy

Description

<jats:p> Two-dimensional bin packing problems consist of allocating, without overlapping, a given set of small rectangles (items) to a minimum number of large identical rectangles (bins), with the edges of the items parallel to those of the bins. According to the specific application, the items may either have a fixed orientation or they can be rotated by 90°. In addition, it may or not be imposed that the items are obtained through a sequence of edge-to-edge cuts parallel to the edges of the bin. In this article, we consider the class of problems arising from all combinations of the above requirements. We introduce a new heuristic algorithm for each problem in the class, and a unified tabu search approach that is adapted to a specific problem by simply changing the heuristic used to explore the neighborhood. The average performance of the single heuristics and of the tabu search are evaluated through extensive computational experiments. </jats:p>

Journal

  • INFORMS Journal on Computing

    INFORMS Journal on Computing 11 (4), 345-357, 1999-11

    Institute for Operations Research and the Management Sciences (INFORMS)

Citations (7)*help

See more

Details 詳細情報について

Report a problem

Back to top