A Heuristic Algorithm for the Two-Dimensional Bin Packing Problem Using a Fitness Function 


Vol. 16,  No. 5, pp. 403-410, Oct.  2009
10.3745/KIPSTB.2009.16.5.403


PDF
  Abstract

The two-dimensional bin packing problem(2D-BPP) has been known to be NP-hard, and it is difficult to solve the problem exactly. Many approximation methods, such as genetic algorithm, simulated annealing and tabu search etc, have been also proposed to gain better solutions. However, the existing approximation algorithms, such as branch-and-bound and tabu search, have shown the low efficiency and the long execution time due to a large of iterations. To solve these problems, we first define the fitness function to simplify and increase the utility of algorithm. The function decides whether an item is packed into a given area, and as an important information for a packing strategy, the number of subarea that can accommodate a given item is obtained from the variant of the fitness function. Then we present a heuristic algorithm for 2D bin packing, constructed by the fitness function and subarea. Finally, the effectiveness of the proposed algorithm will be expressed by the comparison experiments with the heuristic and the metaheuristic of the literatures. As comparing with existing heuristic algorithms and metaheuristic algorithms, it has been found that the packing rate of algorithm BP is the same as 97% as existing heuristic algorithms, FFF and FBS, or better than them. Also, it has been shown the same as 86% as tabu search algorithm or better.

  Statistics
  Cite this article

[IEEE Style]

Y. H. Yon, S. Y. Lee, J. Y. Lee, "A Heuristic Algorithm for the Two-Dimensional Bin Packing Problem Using a Fitness Function," The KIPS Transactions:PartB , vol. 16, no. 5, pp. 403-410, 2009. DOI: 10.3745/KIPSTB.2009.16.5.403.

[ACM Style]

Yong Ho Yon, Sun Young Lee, and Jong Yun Lee. 2009. A Heuristic Algorithm for the Two-Dimensional Bin Packing Problem Using a Fitness Function. The KIPS Transactions:PartB , 16, 5, (2009), 403-410. DOI: 10.3745/KIPSTB.2009.16.5.403.

Forms

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)

Old Journals

Indexing

All publications of TKIPS is indexed in DOI, EBSCO, Google Scholar, Crossref, and CrossCheck.

TKIPS is also selected as the Journal for Accreditation by NRF (National Research Foundation of Korea).

Related Journals