Problem solving of container loading using genetic algorithm based on modified random keys

 
 
 
  • Abstract
  • Keywords
  • References
  • PDF
  • Abstract


    This article presents a solution to the container loading problem. Container loading problem deals with how to put the cube boxes with different sizes in a container. Our proposed method is based on a particular kind of genetic algorithm based on biased random keys. In the proposed algorithm, we will face generations' extinction. Population decreases with time and with the staircase changes in the rate of elitism, the algorithm is guided towards the global optimum. Biased random keys in the proposed method are provided as discrete. The algorithm also provides the chromosomes that store more than one ability. In order to solve container loading using a placement strategy, due to the size of the boxes and containers, the containers are classified as small units and equal unites in size. Finally the algorithm presented in this paper was compared with three other methods that are based on evolutionary algorithms. The results show that the proposed algorithm has better performance in terms of results and performance time in relation to other methods.


  • Keywords


    Container Loading; Evolutionary Algorithms; Genetic Algorithm; Random Keys.

  • References


      [1] Gonçalves, J.F., Resende, M.G.C., "A parallel multi-population biased random-key genetic algorithm for a container loading problem", Computers and Operations Research, Vol.39, No.2, (2012), pp.179–190, available online: http://dx.doi.org/10.1016/j.cor.2011.03.009.

      [2] Gonçalves, J.F., Resende, M.G.C., "A biased random key genetic algorithm for 2D and 3D bin packing problems", Int. J. Production Economics, Vol.145, No.2, (2013), pp.500-510, available online: http://dx.doi.org/10.1016/j.ijpe.2013.04.019.

      [3] W¨ascher G., Haussner, H., Schumann, H., "An improved typology of cutting and packing problems", European Journal of Operational Research, Vo1.83, (2007), pp. 1109–30, available online: http://dx.doi.org/10.1016/j.ejor.2005.12.047.

      [4] Scheithauer, G., "Algorithm for the container loading problem", Operational Research Proceedings, (1992), pp. 445–452, available online: http://link.springer.com/chapter/10.1007%2F978-3-642-46773-8_112.

      [5] Pisinger, D., "Heuristics for the container loading problem", European Journal of Operational Research. Vol. 141, (2002), pp. 143–53, available online: http://dx.doi.org/10.1016/S0377-2217(02)00132-7.

      [6] Martello, S., Pisinger, D.,Vigo, D., "The three dimensional bin packing problem", Operations Research,Vol.48, No.2, (2000), pp. 256–67, available online: http://pubsonline.informs.org/doi/abs/10.1287/opre.48.2.256.12386. http://dx.doi.org/10.1287/opre.48.2.256.12386.

      [7] George, AJ, Robinson, DF, "A heuristic for packing boxes into a container, Computers and Operations Research", Vol. 7, No.3, (1980), pp. 147–56, available online: http://dx.doi.org/10.1016/0305-0548(80)90001-5.

      [8] H. Dyckhoff., "A typology of cutting and packing problems", European Journal of Operational Research,Vol. 44, No.2, (1990), pp.145–159, available online: http://dx.doi.org/10.1016/0377-2217(90)90350-K.

      [9] Peeraya Thapatsuwan., Pupong Pongcharoen., Chris Hicks., Warattapop Chainate.," Development of a stochastic optimisation tool for solving the multiple container packing problems", Int. J. Production Economics, Vol.140, No.2, (2012), pp.737–748, available online: http://dx.doi.org/10.1016/j.ijpe.2011.05.012.

      [10] Lai, K., Chan, J., "Developing a simulated annealing algorithm for the cutting stock problem", Computers and Industrial Engineering, Vol.32, No.1, (1997), pp.115–127, available online: http://dx.doi.org/10.1016/S0360-8352(96)00205-7.

      [11] Davies AP., Bischoff EE., "Weight distribution considerations in container loading", European Journal of Operational Research, Vol.114, No.3, (1999),pp. 509–527,available online: http://dx.doi.org/10.1016/S0377-2217(98)00139-8.

      [12] Gendreau, M., Iori, M., Laporte, G., Martello, S., "A tabu search algorithm for a routing and container loading problem", Transportation Science, Vol.40, (2006), pp. 342–350, available online: http://pubsonline.informs.org/doi/abs/10.1287/trsc.1050.0145. http://dx.doi.org/10.1287/trsc.1050.0145.

      [13] Eley M., "Solving container loading problems by block arrangement", European Journal of Operational Research, Vol.141, No.2, (2002), pp.393–409, available online: http://dx.doi.org/10.1016/S0377-2217(02)00133-9.

      [14] Bean JC., "Genetics and random keys for sequencing and optimization", ORSA Journal on Computing, Vol.6, No.2, (1994), pp.154–60, available online: http://dx.doi.org/10.1287/ijoc.6.2.154.

      [15] Bortfeldt A., Gehring H., "A parallel genetic algorithm for solving the container loading problem", International Transactions in Operational Research, Vol.9, No.4, (2002), pp.497–511, available online: http://onlinelibrary.wiley.com/doi/10.1111/1475-3995.00369/abstract. http://dx.doi.org/10.1111/1475-3995.00369.

      [16] Bischoff EE., Ratcliff MSW., "Issues in the development of approaches to container loading", Omega, International Journal of Management Science,Vol.23, No.3, (1995), pp.377–90, available online: http://dx.doi.org/10.1016/0305-0483(95)00015-G.

      [17] Goldberg. D.,Holland, J., "Genetic Algorithms and Machine Learnin", Machine Learning, Vol.3, No.2, (1988), pp.95-99, available online: http://link.springer.com/article/10.1023%2FA%3A1022602019183?LI=true. http://dx.doi.org/10.1023/A:1022602019183.


 

View

Download

Article ID: 4348
 
DOI: 10.14419/jacst.v4i1.4348




Copyright © 2012-2015 Science Publishing Corporation Inc. All rights reserved.