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

  • Authors

    • Mohammad Sadegh Arefi Department of Computer Science, Faculty of Mathematics, University of Sistan and Baluchestan, Iran.
    • Hassan Rezaei
    2015-04-15
    https://doi.org/10.14419/jacst.v4i1.4348
  • Container Loading, Evolutionary Algorithms, Genetic Algorithm, Random Keys.
  • 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.

  • References

    1. [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.

  • Downloads

  • How to Cite

    Arefi, M. S., & Rezaei, H. (2015). Problem solving of container loading using genetic algorithm based on modified random keys. Journal of Advanced Computer Science & Technology, 4(1), 190-197. https://doi.org/10.14419/jacst.v4i1.4348