Аннотация.

Рассматривается NP-полная задача ортогональной упаковки объектов произвольной размерности. В статье представлен анализ существующих моделей конструирования ортогональной упаковки (матричная, узловая и блочная модели) и предложены новые модели представления ортогональных объектов в контейнерах (модель «виртуальные объекты» и модель потенциальных контейнеров). Эффективность применения различных моделей конструирования упаковки исследована на эталонных задачах трехмерной ортогональной упаковки объектов.

Ключевые слова:

задача упаковки, распределение ресурсов, модель представления объектов, конструирование упаковки, задача трехмерной упаковки.

Стр. 37-45.

V.A. Chekanin, A.V. Chekanin

"Effective methods for solving an orthogonal packing problem"

The multidimensional packing task is considered at the article. Proposed by authors new packing model «virtual objects», used at planning any dimension orthogonal packing task, is investigated. New heuristics for solving the task are described. Computational experiments on standard rectangular two-dimension packing tasks are carried out and the results are dicussed.

Keywords: combinatorial problem, optimization, packing task, orthogonal packing, packing model, multimethodical genetic algorithm, heuristics, computational experiment

Полная версия статьи в формате pdf.

REFERENCES

1. Wascher G., Haubner H., Schumann H. An improved topology of cutting and packing problems // European Journal of Operational Research. 2007. Vol. 183. P. 1109-1130.
2. Sciomachen A., Tanfani E. A 3D-BPP approach for optimising stowage plans and terminal productivity // European Journal of Operational Research. 2007. Vol. 183 (3). P. 1433–1446.
3. Chekanin V.A. Effektivnoe reshenie zadachi dvukhmernoy konteynernoy upakovki pryamougolnykh obektov // Vestnik kompyuternykh i informatsionnykh tekhnologiy. 2011. № 6. S. 35-39.
4. Chekanin V.A., Kovshov Ye.Ye. Modelirovanie i optimizatsiya tekhnologicheskikh operatsiy v promyshlennom proizvodstve na osnove evolyutsionnykh algoritmov // Tekhnologiya mashinostroeniya. 2010. № 3. S. 53-57.
5. Chekanin A.V., Chekanin V.A. Improved packing representation model for the orthogonal packing problem  // Applied Mechanics and Materials.  2013. Vol. 390. P. 591-595.
6. Castro P.M., Oliveira J.F. Scheduling inspired models for two-dimensional packing problems // European Journal of Operational Research. 2011. Vol. 215 (1). P. 45-66.
7. Garey M., Johnson D. Computers Intractability: a Guide to the Theory of NP-completeness. San Francisco: W.H.Freeman, 1979. – 338 p.
8. Bortfeldt A.A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces // European Journal of Operational Research. 2005. Vol. 172. P. 814-837.
9. Filippova A.S. Modelirovanie evolyutsionnykh algoritmov resheniya zadach pryamougolnoy upakovki na baze tekhnologii blochnykh struktur // Informatsionnye tekhnologii. 2006. № 6. Prilozhenie. – 32 s.
10. Chekanin V.A., Chekanin A.V. Algoritm resheniya zadach ortogonalnoy upakovki obektov na osnove multimetodnoy tekhnologii  // Informatsionnye tekhnologii.  2013. № 7. S. 17-21.
11. Chekanin V.A., Chekanin A.V. Optimizatsiya resheniya zadachi ortogonalnoy upakovki obektov // Prikladnaya informatika. 2012. № 4. S. 55-62.
12. Chekanin A.V., Chekanin V.A. Algoritmy effektivnogo resheniya zadachi ortogonalnoy upakovki obektov  // Zhurnal vychislitelnoy matematiki i matematicheskoy fiziki.  2013. T. 53. № 10. S. 1639–1648.
13. Chekanin V.A, Chekanin A.V. Effektivnye modeli predstavleniya ortogonalnykh resursov pri reshenii zadachi upakovki // Informatsionno-upravlyayushchie sistemy. 2012. № 5. S. 29-32.
14. Chekanin A.V., Chekanin V.A. Efficient Algorithms for Orthogonal Packing Problems  // Computational Mathematics and Mathematical Physics. 2013. Vol. 53. No. 10. P. 1457–1465.
15. Babaev F.V. Optimalnyy raskroy materialov s pomoshchyu EVM. M.: Mashinostroenie, 1982. – 168 s.
16. Crainic T.G., Perboli G., Tadei R. Extreme point-based heuristics for three-dimensional bin packing // INFORMS, Journal on Computing. 2008. Vol. 20 (3). P. 368-384.
17. Kartak V.M. Matrichnyy algoritm poiska optimalnogo resheniya dlya resheniya zadachi upakovki pryamougolnikov v polubeskonechnuyu polosu // Informatsionnye tekhnologii. 2008. № 2. S. 24-30.
18. Martello S., Pisinger D., Vigo D. The three-dimensional bin packing problem // Operations Research. 2000. Vol. 48 (2). P. 256-267.
19. Faroe O., Pisinger D., Zachariasen M. Guided local search for the three-dimensional bin packing problem // INFORMS, Journal on Computing. 2003. Vol. 15 (3). P. 267-283.