Article

Article title HYBRID APPROACH FOR THREE-DIMENSIONAL PACKAGING PROBLEM
Authors V.V. Kureichik, A.E. Glushchenko, A.N. Orlov
Section SECTION I. EVOLUTIONAL SIMULATION
Month, Year 06, 2016 @en
Index UDC 004.896
DOI
Abstract The article deals with one of the most important optimization problems – the problem of three-dimensional packaging (3DP) of various sized elements. It belongs to the class of NP-hard and complex problems. A hybrid approach for solving 3DP problem were developed. The formulation and restrictions of the 3DPP are considered in the article. Hybrid approach that uses a multi-level evolution and partially allows to avoid a preliminary convergence of algorithms. Genetic and evolutionary algorithms which obtain sets of quasi-optimal solutions in polynomial time were developed. Dividing of the search process in two stages and employment of different algorithms on stages is a conceptual difference of this approach. On the first stage of search is realized genetic algorithm, which allows to make initial block exchange. Evolutionary algorithm is used on the second stage of search, which allow to improve the previous solution. Developed approach allow to obtain sets of quasi-optimal solutions in polynomial time. Work of hybrid algorithm were showed on examples. To cary out computational experiments on test examples (benchmarks) the authors developed a software on the basis of hybrid approach for the 3DPP.Quality of packing obtained on the basis of the developed bioinspired approach is higher on average 2.17% than packing results obtained using known algorithms suggested by Ngoi et al., Bishoff et al., Gehring et al., which demonstrates the effectiveness of the proposed approach. Conducted tests and exper-iments allow possible to clarify the theoretical estimations of algorithm time complexity. In the best case algorithms the time complexity is represented as O (n2), in the worst case – O (n3).

Download PDF

Keywords Three-dimensional packaging; containers packaging; hybrid approach; genetic algorithm; genetic operators; evolutionary algorithm
References 1. Emel'yanov V.V., Kureychik V.V., Kureychik V.M. Teoriya i praktika evolyutsionnogo modelirovaniya [Theory and practice of evolutionary modeling]. Moscow: Fizmatlit, 2003, 432 p.
2. Lutsan M.V., Nuzhnov E.V. Reshenie zadachi trekhmernoy upakovki s paletirovaniem konteynerov [Solving three-dimension packing problem with palletizing], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2014, No. 7 (156), pp. 196-204.
3. Gladkov L.A., Kureychik V.V., Kureychik V.M., Sorokoletov P.V. Bioinspirirovannye metody v optimizatsii [Bioinspired methods in optimization]. Moscow: Fizmatlit, 2009, 384 p.
4. Bova V.V., Kureychik V.V. Integrirovannaya podsistema gibridnogo i kombinirovannogo poiska v zadachakh proektirovaniya i upravleniya [Integrated subsystem hybrid and combined search in problems of design and management], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2010, No. 12 (113), pp. 37-42.
5. Kureychik V.V., Bova V.V., Kureychik Vl.Vl. Kombinirovannyy poisk pri proektirovanii [Combined search in the design], Obrazovatel'nye resursy i tekhnologii [Educational Resources and Technology], 2014, No. 2 (5), pp. 90-94.
6. Kureychik V.M., Kureychik L.V. Kompleksnyy metod upakovki blokov [Integrated packing method units], Informatika, vychislitel'naya tekhnika i inzhenernoe obrazovanie [Information, Computing and Engineering Education], 2015, No. 1 (21), pp. 17-26.
7. Kureychik V.V., Kureychik Vl.Vl. Bioinspirirovannyy poisk pri proektirovanii i upravlenii [Search inspired by natural systems, for the design and management], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 11 (136), pp. 178-183.
8. Kureychik V.V., Kureychik V.M., Rodzin S.I. Teoriya evolyutsionnykh vychisleniy [The theory of evolutionary computing]. Moscow: Fizmatlit, 2012, 260 p.
9. Gladkov L.A., Gladkova N.V., Skubrieva E.S. Reshenie zadachi trekhmernoy upakovki raznogabaritnykh ob"ektov s ispol'zovaniem bionicheskikh metodov [The decision of the 3d-packing problem differently dimensional objects with use bionic methods], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 7 (144), pp. 35-41.
10. Kureychik V.V., Zaruba D.V., Zaporozhets D.Yu. Primenenie geneticheskogo algoritma resheniya zadachi trekhmernoy upakovki [Application of genetic algorithm to three-dimensional packaging problem], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 7 (132), pp. 8-14.
11. Kureychik V.V., Glushchenko A.E. Evristicheskiy podkhod dlya resheniya zadachi 3-khmernoy Upakovki [Heuristic approach to solve the problem of 3-dimensional packaging], I Vserossiyskaya nauchno-tekhnicheskaya onferentsiya "Fundamental'nye i prikladnye aspekty komp'yuternykh tekhnologiya i informatsionnoy bezopasnosti" [I all-Russian scientific-technical conference "fundamental and applied aspects of computer technology and information security], 2015, pp. 399-401.
12. Nuzhnov E.V., Barlit A.V. Trekhmernaya upakovka nesvyaznykh elementov na osnove evristicheskikh protsedur [Three-dimensional packing of disjoint cells based on heuristic procedures]. Taganrog: Izd-vo TRTU, 2002, 23 p.
13. Kacprzyk, J., Kureichik, V.M., Malioukov, S.P., Kureichik, V.V., Malioukov, A.S. General Questions of automated design and engineering, Studiesin Computational Intelligence, 212, 2009, pp. 1-22.
14. Gladkov L.A., Kureychik V.V., Kureychik V.M. Geneticheskie algoritmy [Genetic algorithms]. Moscow: Fizmatlit, 2010, 368 p.
15. Koide S., Suzuki S., Degawa S. A Palletize-Planning System for Multiple Kinds of Loads using GA Search and Traditional Search, Intelligent Robots and Systems 95. 'Human Robot Interaction and Cooperative Robots', Proceedings. IEEE, 1995, Vol. 3, pp. 510-515.
16. Gehring H., Bortfeldt A. A genetic algorithm for solving the container loading problem, International Transactions in Operational Research, 1997, Vol. 4, Issue 5–6, pp. 401-418.
17. Chan F.T.S., Kumar N., Wong T.C. Three-Dimensional Air-Cargo Loading Problem: An Evo-lutionary Algorithm Based Approach, Proceedings of the 7th Asia Pacific Industrial Engineering and Management Systems Conference, 2006, pp. 758-765.
18. Chauny F. A Bloc Heuristic for the Container Loading Problem, Grouped'étudeset de recherche enanalyse des decisions, Montréal, 2005, pp. 1-18.
19. Kacprzyk J., Kureichik V.M., Malioukov S.P., Kureichik V.V., Malioukov A.S. Experimental investigation of algorithms developed (2009), Studies in Computational Intelligence, 212, pp. 211-223+227-236.
20. Zhukov L.A., Korchevskaya O.V. Metod ploskostey: chislennyy eksperiment dlya zadach dvukh i trekhmernoy ortogonal'noy upakovki [The method of planes: numerical experiment for tasks two and three-dimensional orthogonal packing problems], Informatsionnye tekhnologii [Information Technology], 2008, No. 11, pp. 41-45.

Comments are closed.