Paper Info
Title
BRKGA/VND Hybrid Algorithm for the Classic Three-dimensional Bin Packing Problem.
Abstract
The classic bin packing problem consists of packing a set of boxes with fixed orientation into the minimum number of bins. In this work we present a variable neighborhood descent (VND) inspired algorithm which improves the state-of-art biased random-key genetic algorithm (BRKGA), proposed in [6], for the three-dimensional bin packing problem. The constructive greedy heuristic method to pack the boxes uses an integer sequence to establish the order of boxes to be packed. The presented BRKGA/VND variant fills the initial and mutant population based on sorted box sequences. The devised hybrid method shows significantly superior average fitness through the generations, therefore, solutions with high quality are found faster. The novel approach is tested with a standard set of 320 instances. The computational experiment demonstrate that BRKGA/VND produces equal or better results compared to other state-of-art algorithms proposed in the literature. The empirical data shows that BRKGA/VND hybrid variant systematically produces high quality solutions at fewer iterations compared to the results attained by BRKGA.
Year
DOI
Venue
2018
10.1016/j.endm.2018.03.023
Electronic Notes in Discrete Mathematics
Keywords
Field
DocType
Bin packing,Three-dimensional,BRKGA,VND
Population,Combinatorics,Hybrid algorithm,Constructive,Greedy algorithm,Mathematics,Bin packing problem,Genetic algorithm,Integer sequence
Journal
Volume
ISSN
Citations 
66
1571-0653
0
PageRank 
References 
Authors
0.34
8
5
Name
Order
Citations
PageRank
Anderson Zudio100.34
Daniel Henrique da Silva Costa200.34
Bruno Porto Masquio300.34
I. M. Coelho45812.95
Paulo E. D. Pinto531.13