Hybrid metaheuristic algorithms for single and multi-objective 2d bin packing problem

Date

2015

Author

Beyaz, Muhammed

Metadata

Show full item record

Item Usage Stats

11
views

9
downloads

Cite This

2D Bin packing problem (2DBPP) is an NP-hard combinatorial optimization problem. Objects with di erent width and length sizes are packed in order to minimize the number of unit-capacity bins according to an objective function. Single or multiobjective versions of this well-known industrial engineering problem can be faced frequently in real life situations. There have been several heuristics proposed for the solution of 2DBPP until now where it is not possible to find the exact solutions for large problem instances. Next fit, First Fit, Best Fit, Unified Tabu Search and Genetic Algorithms are some of these algorithms. Recently, Memetic Algorithms have put themselves forward as a new area of research in evolutionary computation with their ability to combine di erent heuristics and local search mechanisms together for higher quality solutions. In this thesis, we propose a set of single and multiobjective memetic and genetic algorithms that make use of the state-of-the-art metaheuristics and local search techniques for the solution of 2DBPP. We analyze the optimization time and the resulting solution quality of the algorithms on a 2DBPP benchmark offline problem set with 500 instances. Through results of exhaustive experiments and with the aid of a novel visual analyzer developed in this study, we conclude that the proposed memetic and hybrid genetic algorithms are robust with their ability to obtain very high percentage of the optimal solutions for the given benchmark problem instances.

Subject Keywords

Genetic algorithms., Heuristic algorithms., Computer algorithms., Combinatorial optimization., Combinatorial packing and covering.

URI

http://etd.lib.metu.edu.tr/upload/12618455/index.pdf
https://hdl.handle.net/11511/24446

Collections

Graduate School of Natural and Applied Sciences, Thesis