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

Download

index.pdf

Date

2015

Author

Beyaz, Muhammed

Metadata

Show full item record

Item Usage Stats

153
views

79
downloads

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

Suggestions

OpenMETU
Core

Hybrid heuristic algorithms for the multi objective load balancing of 2D bin packing problems Muhammet, Beyaz; Dökeroğlu, Tansel; Coşar, Ahmet (null; 2015-09-23) 2D Bin packing problem (2DBPP) is an NP-hard combinatorial optimization problem. Multiobjective versions of this well-known industrial engineering problem can occur frequently in real world application. Recently, Hybrid Evolutionary Algorithms have appear as a new area of research with their ability to combine alternative heuristics and local search mechanisms together for higher quality solutions. In this study, we propose a set of novel multiobjective hybrid genetic and memetic algorithms that make use of...
Robust hyper-heuristic algorithms for the offline oriented/non-oriented 2D bin packing problems Beyaz, Muhammed; Dokeroglu, Tansel; Coşar, Ahmet (2015-11-01) The offline 2D bin packing problem (2DBPP) is an NP-hard combinatorial optimization problem in which objects with various width and length sizes are packed into minimized number of 2D bins. Various versions of this well-known industrial engineering problem can be faced frequently. Several heuristics have been proposed for the solution of 2DBPP but it has not been possible to find the exact solutions for large problem instances. Next fit, first fit, best fit, unified tabu search, genetic and memetic algorith...
Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms Dokeroglu, Tansel; Coşar, Ahmet (2014-09-01) The well-known one-dimensional Bin Packing Problem (BPP) of whose variants arise in many real life situations is a challenging NP-Hard combinatorial optimization problem. Metaheuristics are widely used optimization tools to find (near-) optimal solutions for solving large problem instances of BPP in reasonable running times. With this study, we propose a set of robust and scalable hybrid parallel algorithms that take advantage of parallel computation techniques, evolutionary grouping genetic metaheuristics,...
Converging preferred regions in multi-objective combinatorial optimization problems Lokman, Banu; Köksalan, Murat; Department of Industrial Engineering (2011) Finding the true nondominated points is typically hard for Multi-objective Combinatorial Optimization (MOCO) problems. Furthermore, it is not practical to generate all of them since the number of nondominated points may grow exponentially as the problem size increases. In this thesis, we develop an exact algorithm to find all nondominated points in a specified region. We combine this exact algorithm with a heuristic algorithm that approximates the possible locations of the nondominated points. Interacting w...
Parallel Approximation, and Integer Programming Reformulation Patakı, Gabor; Tural, Mustafa Kemal (null; 2008-03-14) We show that in a knapsack feasibility problem an integral vectorp, which is short, and nearparallel to the constraint vector gives a branching direction with small integer width.We use this result to analyze two computationally efficient reformulation techniques on lowdensity knapsack problems. Both reformulations have a constraint matrix with columns reducedin the sense of Lenstra, Lenstra, and Lov ́asz. We prove an upper bound on the integer widthalong the last variable, which becomes 1,when the density ...

Citation Formats

M. Beyaz, “Hybrid metaheuristic algorithms for single and multi-objective 2d bin packing problem,” M.S. - Master of Science, Middle East Technical University, 2015.