research-article

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

Authors:

André Homem Dornas,

Flávio Vinícius Cruzeiro Martins,

João Fernando Machry Sarubbi,

Elizabeth Fialho WannerAuthors Info & Claims

GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 785 - 792

https://doi.org/10.1145/3071178.3071327

Published: 01 July 2017 Publication History

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.

References

[1]

Eberhard E Bischoff, F Janetz, and MSW Ratcliff. 1995. Loading pallets with non-identical items. European journal of operational research 84, 3 (1995), 681--692.

[2]

FO Cecilio and Reinaldo Morabito. 2004. Refinamentos na heurística de George e Robinson para o problema de carregamento de caixas dentro de contêineres. Transportes 11, 2 (2004), 32--45.

[3]

CS Chen, Shen-Ming Lee, and QS Shen. 1995. An analytical model for the container loading problem. European Journal of Operational Research 80, 1 (1995), 68--76.

[4]

Teodor Gabriel Crainic, Guido Perboli, and Roberto Tadei. 2008. Extreme point-based heuristics for three-dimensional bin packing. Informs Journal on computing 20, 3 (2008), 368--384.

Digital Library

[5]

Kathryn A Dowsland and William B Dowsland. 1992. Packing problems. European journal of operational research 56, 1 (1992), 2--14.

[6]

Harald Dyckhoff. 1990. A typology of cutting and packing problems. European Journal of Operational Research 44, 2 (1990), 145--159.

[7]

Thomas A. Feo and Mauricio G. C. Resende. 1995. Greedy Randomized Adaptive Search Procedures. Journal of Global Optimization 6, 2 (1995), 109--133.

[8]

Michel Gendreau, Manuel Iori, Gilbert Laporte, and Silvano Martello. 2006. A tabu search algorithm for a routing and container loading problem. Transportation Science 40, 3 (2006), 342--350.

Digital Library

[9]

John A George and David F Robinson. 1980. A heuristic for packing boxes into a container. Computers & Operations Research 7, 3 (1980), 147--156.

[10]

Silvano Martello, David Pisinger, and Daniele Vigo. 2000. The three-dimensional bin packing problem. Operations Research 48, 2 (2000), 256--267.

Digital Library

[11]

Silvano Martello, David Pisinger, Daniele Vigo, Edgar Den Boef, and Jan Korst. 2007. Algorithm 864: General and robot-packable variants of the three-dimensional bin packing problem. ACM Transactions on Mathematical Software (TOMS) 33, 1 (2007), 7.

Digital Library

[12]

Silvano Martello and Paolo Toth. 1990. Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, Inc., New York, NY, USA.

Digital Library

[13]

F. V. C. Martins, E. G. Carrano, E. F. Wanner, R. H. C. Takahashi, G. R. Mateus, and F. G. Nakamura. 2014. On a Vector Space Representation in Genetic Algorithms for Sensor Scheduling in Wireless Sensor Networks. Evolutionary Computation 22, 3 (2014), 361 -- 403.

Digital Library

[14]

Melanie Mitchell. 1998. An introduction to genetic algorithms. MIT press.

Digital Library

[15]

Lúcio Lopes Rodrigues Neto. 2005. Um Algoritmo Genético para Solução do Problema de Carregamento de Ccontainer. Ph.D. Dissertation. Universidade Federal do Rio de Janeiro.

[16]

R. H. C. Takahashi, J. A. Vasconcelos, J. A. Ramirez, and L. Krahenbuhl. 2003. A multiobjective methodology for evaluating genetic operators. IEEE Transactions on Magnetics 3, 39 (2003), 1321--1324.

[17]

Tian Tian, Wenbin Zhu, Andrew Lim, and Lijun Wei. 2016. The multiple container loading problem with preference. European Journal of Operational Research 248, 1 (2016), 84--94.

[18]

Wenbin Zhu, Zhaoyi Zhang, Wee-Chong Oon, and Andrew Lim. 2012. Space defragmentation for packing problems. European Journal of Operational Research 222, 3 (2012), 452 -- 463.

Cited By

NISHIYAMA SLEE CMASHITA T(2021)Solving 3D Container Loading Problems Using Physics Simulation for Genetic Algorithm EvaluationIEICE Transactions on Information and Systems10.1587/transinf.2020EDP7239E104.D:11(1913-1922)Online publication date: 1-Nov-2021
https://doi.org/10.1587/transinf.2020EDP7239
Nishiyama SLee CMashita T(2020)Designing a Flexible Evaluation of Container Loading Using Physics SimulationOptimization and Learning10.1007/978-3-030-41913-4_21(255-268)Online publication date: 15-Feb-2020
https://doi.org/10.1007/978-3-030-41913-4_21

Index Terms

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

Recommendations

An improved genetic algorithm with conditional genetic operators and its application to set-covering problem

The genetic algorithm (GA) is a popular, biologically inspired optimization method. However, in the GA there is no rule of thumb to design the GA operators and select GA parameters. Instead, trial-and-error has to be applied. In this paper we present an ...
Biased random-key genetic algorithms for combinatorial optimization

Random-key genetic algorithms were introduced by Bean (ORSA J. Comput. 6:154---160, 1994) for solving sequencing problems in combinatorial optimization. Since then, they have been extended to handle a wide class of combinatorial optimization problems. ...
A multipopulation cultural algorithm based on genetic algorithm for the MKP
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

Genetic Algorithms (GAs) have been used to solve the NP-complete problems effectively such as the Multi Knapsack Problem (MKP). This work presents a combination between CAs and GAs with multipopulation model for the MKP. The benchmark simulation results ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

July 2017

1427 pages

ISBN:9781450349208

DOI:10.1145/3071178

General Chair:
Peter A. N. Bosman
Centrum Wiskunde & Informatica (CWI)

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

FAPEMIG
CNPq
CAPES

Conference

GECCO '17

Sponsor:

SIGEVO

GECCO '17: Genetic and Evolutionary Computation Conference

July 15 - 19, 2017

Berlin, Germany

Acceptance Rates

GECCO '17 Paper Acceptance Rate 178 of 462 submissions, 39%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
160
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

NISHIYAMA SLEE CMASHITA T(2021)Solving 3D Container Loading Problems Using Physics Simulation for Genetic Algorithm EvaluationIEICE Transactions on Information and Systems10.1587/transinf.2020EDP7239E104.D:11(1913-1922)Online publication date: 1-Nov-2021
https://doi.org/10.1587/transinf.2020EDP7239
Nishiyama SLee CMashita T(2020)Designing a Flexible Evaluation of Container Loading Using Physics SimulationOptimization and Learning10.1007/978-3-030-41913-4_21(255-268)Online publication date: 15-Feb-2020
https://doi.org/10.1007/978-3-030-41913-4_21

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents