A hybrid evolutionary algorithm for the offline Bin Packing Problem

Istvan Borgulya ()
Additional contact information
Istvan Borgulya: University of Pecs Hungary

Central European Journal of Operations Research, 2021, vol. 29, issue 2, No 4, 425-445

Abstract: Abstract In this paper we present an evolutionary heuristic for the offline one-dimensional Bin Packing Problem. In this problem we have to pack a set of items into bins of the same capacity, and the objective is to minimize the number of bins used. Our algorithm is a hybrid evolutionary algorithm where an individual is a feasible solution, and it contains the description of the bins. The algorithm works without recombination; it uses two new mutation operators and improves the quality of the solutions with local search procedures. The mutation operators’ work is based on a relative pair frequency matrix, and, based on this matrix, we know the frequency of every pair of items i.e. how often they are included in the same bin in the best solutions. The frequency matrix helps to pack items into subsets of items; these subsets are the bins in our problem. The algorithm was tested on well-known benchmark instances from the literature and was compared with both evolutionary and state-of-the-art algorithms. Our algorithm achieved a valuable result with the difficult hard28 test set, and in most of the test problems it reached the optimum.

Keywords: Local search; Bin packing; Evolutionary algorithm (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10100-020-00695-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:cejnor:v:29:y:2021:i:2:d:10.1007_s10100-020-00695-5

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10100

DOI: 10.1007/s10100-020-00695-5

Access Statistics for this article

Central European Journal of Operations Research is currently edited by Ulrike Leopold-Wildburger

More articles in Central European Journal of Operations Research from Springer, Slovak Society for Operations Research, Hungarian Operational Research Society, Czech Society for Operations Research, Österr. Gesellschaft für Operations Research (ÖGOR), Slovenian Society Informatika - Section for Operational Research, Croatian Operational Research Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().