Real-polarized genetic algorithm for the three-dimensional bin packing problem

Andre Homem Dornas; Flávio Vinícius Cruzeiro Martins; João Fernando Machry Sarubbi; Elizabeth Fialho Wanner

doi:10.1145/3071178.3071327

Real-polarized genetic algorithm for the three-dimensional bin packing problem

Andre Homem Dornas, Flávio Vinícius Cruzeiro Martins, João Fernando Machry Sarubbi, Elizabeth Fialho Wanner

College of Engineering and Physical Sciences

Research output: Chapter in Book/Published conference output › Conference publication

Abstract

This article presents a non-deterministic approach to the Three-Dimensional Bin Packing Problem, using a genetic algorithm. To perform the packing, an algorithm was developed considering rotations, size constraints of objects and better utilization of previous free spaces (flexible width). Genetic operators have been implemented based on existing operators, but the highlight is the Real-Polarized crossover operator that produces new solutions with a certain disturbance near the best parent. The proposal presented here has been tested on instances already known in the literature and real instances. A visual comparison using boxplot was done and, in some situations, it was possible to say that the obtained results are statistically superior than the ones presented in the literature. In a given instance class, the presented Genetic Algorithm found solutions reaching up to 70% less bins.

Original language	English
Title of host publication	GECCO '17: proceedings of the Genetic and Evolutionary Computation Conference
Place of Publication	New York, NY (US)
Publisher	ACM
Pages	785-792
Number of pages	8
ISBN (Electronic)	978-1-4503-4939-0
ISBN (Print)	978-1-4503-4920-8
DOIs	https://doi.org/10.1145/3071178.3071327
Publication status	Published - 15 Jul 2017
Event	Genetic and Evolutionary Computation Conference, GECCO '17 - Berlin, Germany Duration: 15 Jul 2017 → 19 Jul 2017

Conference

Conference	Genetic and Evolutionary Computation Conference, GECCO '17
Country/Territory	Germany
City	Berlin
Period	15/07/17 → 19/07/17

Bibliographical note

-

Access to Document

10.1145/3071178.3071327

Real-polarized genetic algorithm for the three-dimensional bin packing problemAccepted author manuscript, 775 KB

4 Conference publication

A genetic algorithm for hybrid VANETs with synchronous communication
Sarubbi, J. M., Martins, F. C., Silva, C. M. & Wanner, E., 15 Jul 2017, GECCO '17: proceedings of the Genetic and Evolutionary Computation Conference. New York, NY (US): ACM, p. 303-304 2 p.
Research output: Chapter in Book/Published conference output › Conference publication

Open Access
File
Gaining insights into road traffic data through genetic improvement
Ekárt, A., Patelli, A., Lush, V. & Ilie-Zudor, E., 15 Jul 2017, GECCO '17: proceedings of the Genetic and Evolutionary Computation Conference. New York, NY (US): ACM, p. 1511-1512 2 p.
Research output: Chapter in Book/Published conference output › Conference publication

Open Access
File
Hybrid metaheuristic for combinatorial optimization based on immune network for optimization and VNS
Diana, R. O. M., de Souza, S. R., Wanner, E. F. & França Filho, M. F., 15 Jul 2017, GECCO '17: proceedings of the Genetic and Evolutionary Computation Conference . New York, NY (US): ACM, p. 251-258 8 p.
Research output: Chapter in Book/Published conference output › Conference publication

Open Access
File

Cite this

@inproceedings{3859687472ae44b6ab2eaf0feb55786e,

title = "Real-polarized genetic algorithm for the three-dimensional bin packing problem",

abstract = "This article presents a non-deterministic approach to the Three-Dimensional Bin Packing Problem, using a genetic algorithm. To perform the packing, an algorithm was developed considering rotations, size constraints of objects and better utilization of previous free spaces (flexible width). Genetic operators have been implemented based on existing operators, but the highlight is the Real-Polarized crossover operator that produces new solutions with a certain disturbance near the best parent. The proposal presented here has been tested on instances already known in the literature and real instances. A visual comparison using boxplot was done and, in some situations, it was possible to say that the obtained results are statistically superior than the ones presented in the literature. In a given instance class, the presented Genetic Algorithm found solutions reaching up to 70% less bins.",

author = "Dornas, {Andre Homem} and Martins, {Fl{\'a}vio Vin{\'i}cius Cruzeiro} and Sarubbi, {Jo{\~a}o Fernando Machry} and Wanner, {Elizabeth Fialho}",

note = "-; Genetic and Evolutionary Computation Conference, GECCO '17 ; Conference date: 15-07-2017 Through 19-07-2017",

year = "2017",

month = jul,

day = "15",

doi = "10.1145/3071178.3071327",

language = "English",

isbn = "978-1-4503-4920-8",

pages = "785--792",

booktitle = "GECCO '17: proceedings of the Genetic and Evolutionary Computation Conference",

publisher = "ACM",

address = "United States",

}

Dornas, AH, Martins, FVC, Sarubbi, JFM & Wanner, EF 2017, Real-polarized genetic algorithm for the three-dimensional bin packing problem. in GECCO '17: proceedings of the Genetic and Evolutionary Computation Conference . ACM, New York, NY (US), pp. 785-792, Genetic and Evolutionary Computation Conference, GECCO '17, Berlin, Germany, 15/07/17. https://doi.org/10.1145/3071178.3071327

Real-polarized genetic algorithm for the three-dimensional bin packing problem. / Dornas, Andre Homem; Martins, Flávio Vinícius Cruzeiro; Sarubbi, João Fernando Machry et al.
GECCO '17: proceedings of the Genetic and Evolutionary Computation Conference . New York, NY (US): ACM, 2017. p. 785-792.

Research output: Chapter in Book/Published conference output › Conference publication

TY - GEN

T1 - Real-polarized genetic algorithm for the three-dimensional bin packing problem

AU - Dornas, Andre Homem

AU - Martins, Flávio Vinícius Cruzeiro

AU - Sarubbi, João Fernando Machry

AU - Wanner, Elizabeth Fialho

N1 - -

PY - 2017/7/15

Y1 - 2017/7/15

N2 - This article presents a non-deterministic approach to the Three-Dimensional Bin Packing Problem, using a genetic algorithm. To perform the packing, an algorithm was developed considering rotations, size constraints of objects and better utilization of previous free spaces (flexible width). Genetic operators have been implemented based on existing operators, but the highlight is the Real-Polarized crossover operator that produces new solutions with a certain disturbance near the best parent. The proposal presented here has been tested on instances already known in the literature and real instances. A visual comparison using boxplot was done and, in some situations, it was possible to say that the obtained results are statistically superior than the ones presented in the literature. In a given instance class, the presented Genetic Algorithm found solutions reaching up to 70% less bins.

AB - This article presents a non-deterministic approach to the Three-Dimensional Bin Packing Problem, using a genetic algorithm. To perform the packing, an algorithm was developed considering rotations, size constraints of objects and better utilization of previous free spaces (flexible width). Genetic operators have been implemented based on existing operators, but the highlight is the Real-Polarized crossover operator that produces new solutions with a certain disturbance near the best parent. The proposal presented here has been tested on instances already known in the literature and real instances. A visual comparison using boxplot was done and, in some situations, it was possible to say that the obtained results are statistically superior than the ones presented in the literature. In a given instance class, the presented Genetic Algorithm found solutions reaching up to 70% less bins.

U2 - 10.1145/3071178.3071327

DO - 10.1145/3071178.3071327

M3 - Conference publication

SN - 978-1-4503-4920-8

SP - 785

EP - 792

BT - GECCO '17: proceedings of the Genetic and Evolutionary Computation Conference

PB - ACM

CY - New York, NY (US)

T2 - Genetic and Evolutionary Computation Conference, GECCO '17

Y2 - 15 July 2017 through 19 July 2017

ER -

Real-polarized genetic algorithm for the three-dimensional bin packing problem

Abstract

Conference

Bibliographical note

Access to Document

Fingerprint

Research output

A genetic algorithm for hybrid VANETs with synchronous communication

Gaining insights into road traffic data through genetic improvement

Hybrid metaheuristic for combinatorial optimization based on immune network for optimization and VNS

Cite this