Investigation of Genetic Algorithm Parameters and Comparison of Heuristic Arrangements for Container Packing Problem
Article Sidebar
Main Article Content
Abstract
The container packing problem (CPP) has gained a great deal of attention from researchers. CPP is included in the NP-complete problem, which means that the problem is very difficult to find the best solution in a reasonable time. The total numbers of the solutions depend on the number of the containers arranged (n!) multiplied by six ways of turning each box (6th). Genetic algorithm (GA) is one of the stochastic search methods that are suitable for solving NP-complete problems. The aims of this work were to find the optimal GA parameters and mechanisms (including population size, number of generations, probabilities of crossover and mutation and types of crossover and mutation) for CPP and to compare two approaches of heuristic arrangement (wall-building and guillotine cutting). Two different sizes of packing problem (100 and 500 various sizes of boxes) were considered in a sequential experiment. The results obtained from the effective designed experiments showed that only some GA parameters were statistically significant. It was also found that wall-building approach produced better solutions than guillotine cutting approach.
Keywords: -
Corresponding author: E-mail: [email protected]
Article Details
Copyright Transfer Statement
The copyright of this article is transferred to Current Applied Science and Technology journal with effect if and when the article is accepted for publication. The copyright transfer covers the exclusive right to reproduce and distribute the article, including reprints, translations, photographic reproductions, electronic form (offline, online) or any other reproductions of similar nature.
The author warrants that this contribution is original and that he/she has full power to make this grant. The author signs for and accepts responsibility for releasing this material on behalf of any and all co-authors.
Here is the link for download: Copyright transfer form.pdf
References
[2] Gen, M. and Cheng, R. 1997 Genetic Algorithms and Engineering Design. New York, John Wiley and Sons.
[3] Goldberg, D.E. 1989 Genetic Algorithms in Search, Optimisation and Machine Learning. Massachusetts, Addison-Wesley.
[4] Aytug, H., Khouja, M., and Vergara, F.E. 2003 Use of genetic algorithm to solve production and operation management problems: a review, International Journal of Production Research, 41(17). 3955-4009
[5] Gehring, H. and Bortfeldt, A. 1997 A genetic algorithm for solving the container loading problem, International Transactions in Operational Research, 4(5-6), 401-418
[6] Dyckhoff, H. 1990 A typology of cutting and packing problems, European Journal of Operational Research, 44(2), 145-159
[7] Gilmore, P.C. and Gomory, R.E. 1965 Multistage cutting stock problems of two and more dimensions, Operations Research, 13(1), 94-120
[8] George, J.A. and Robinson, D.F. 1980 A heuristic for packing boxes into a container, Computers and Operations Research, 7(3), 147-156
[9] Morabito, R. and Arenales, M. 1994 An AND/OR graph approach to the container loading problem, International Transactions in Operational Research, 1(1), 59-73
[10] Bortfeldt, A. and Gehring, H. 1997 Applying tabu search to container loading problems. Operations Research Proceedings, Berlin, pp. 533-538.
[11] Gehring, M., Menscher, K., and Meyer, M. 1990 A computer-based heuristic for packing pooled shipment containers, European Journal of Operational Research, 44(2), 277-288
[12] Bischoff, E.E. and Marriott, M.D. 1990 A comparative evaluation of heuristics for container loading, European Journal of Operational Research, 44(2), 267-276
[13] Blazewicz, J., Ecker, K.H. Pesch, E., Schmidt, G., and Weglarz, J. 1996 Scheduling Computer and Manufacturing Processes. Berlin, Springer.
[14] Pongcharoen, P., Stewardson, D.J., Hicks, C., and Braiden, P.M. 2001 Applying designed experiments to optimize the performance of genetic algorithms used for scheduling complex products in the capital goods industry, Journal of Applied Statistic, 28(3-4), 441-455
[15] Chainate, W. 2005 A hybridization of genetic algorithm and neural network for solving the travelling salesman problems. Master thesis, Naresuan University.
[16] Pongcharoen, P., Hicks, C., Braiden, P.M., and Stewardson, D.J. 2002 Determining optimum genetic algorithm parameters for scheduling the manufacturing and assembly for complex products, International Journal of Production Economics, 78(3), 311-322
[17] Todd, D. 1997 Multiple criteria genetic algorithms in engineering design and operation. Ph.D. thesis, University of Newcastle upon Tyne, UK.
[18] Garzon, I.E., Taher, M.A., and Anderson, A. 2000 Evaluating Taguchi tools through case studies. Proceedings of the Industrial Statistics in Action Conference.
[19] Pongcharoen, P., Hicks, C., and Braiden, P.M. 2004 The development of genetic algorithms for the finite capacity scheduling of complex products, with multiple levels of product structure, European Journal of Operational Research, 152(1), 215-225