André Homem Dornas
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.
- 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.Google Scholar
- 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.Google Scholar
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Kathryn A Dowsland and William B Dowsland. 1992. Packing problems. European journal of operational research 56, 1 (1992), 2--14.Google Scholar
- Harald Dyckhoff. 1990. A typology of cutting and packing problems. European Journal of Operational Research 44, 2 (1990), 145--159.Google ScholarCross Ref
- Thomas A. Feo and Mauricio G. C. Resende. 1995. Greedy Randomized Adaptive Search Procedures. Journal of Global Optimization 6, 2 (1995), 109--133.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- John A George and David F Robinson. 1980. A heuristic for packing boxes into a container. Computers & Operations Research 7, 3 (1980), 147--156.Google ScholarCross Ref
- Silvano Martello, David Pisinger, and Daniele Vigo. 2000. The three-dimensional bin packing problem. Operations Research 48, 2 (2000), 256--267. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Silvano Martello and Paolo Toth. 1990. Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, Inc., New York, NY, USA. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Melanie Mitchell. 1998. An introduction to genetic algorithms. MIT press. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
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 computationGenetic 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