Полудискретное геометрическое моделирование объектов в задаче двумерной упаковки

Полудискретное геометрическое моделирование объектов в задаче двумерной упаковки

Акентьев В. В.
Дискретный анализ и исследование операций, 33, 1, 5-25 (2026)
Скачать статью

УДК 519.7 
DOI: 10.33048/daio.2026.33.845

Аннотация:

Рассматривается задача двумерной упаковки (nesting problem), заключающаяся в размещении набора объектов произвольной формы в ограниченную полосу с целью минимизации её используемой длины. Одним из ключевых этапов решения подобных задач является выбор способа моделирования геометрических объектов, который определяет как точность аппроксимации их формы, так и вычислительные затраты алгоритма упаковки. Предлагается новый метод моделирования объектов на основе адаптивных трапеций. В отличие от актуального метода — сегментного подхода — он позволяет значительно снизить избытки аппроксимации, возникающие при несовпадении вершин с узлами сетки, и повысить точность представления формы объектов. Проведённые вычислительные эксперименты на типовых наборах данных ESICUP показали, что использование предложенного метода при выполнении алгоритма упаковки вниз-влево (bottom-left-fill) обеспечивает более плотное размещение объектов при умеренном увеличении вычислительных затрат. Полученные результаты подтверждают эффективность предложенного метода и его практическую применимость в задачах двумерной упаковки. 

Табл. 2, ил. 11, библиогр. 11.

Литература:
  1. Stoyan Y., Terno J., Scheithauer G., Gil N., Romanova T. Phi-functions for primary 2D-objects // Stud. Inform. Univers. 2002. V. 2, No. 1. P. 1–32.
     
  2. Oliveira J. F., Ferreira J. S. Algorithms for nesting problems // Applied simulated annealing. Heidelberg: Springer, 1993. P. 255–273. DOI: 10.1007/ 978-3-642-46787-5_13.
     
  3. Ma H., Liu C. C. Fast nesting of 2-D sheet parts with arbitrary shapes using a greedy method and semi-discrete representations // IEEE Trans. Autom. Sci. Eng. 2007. V. 4, No. 2. P. 273–282. DOI: 10.1109/TASE.2006.874973.
     
  4. Akunuru R., Babu N. R. A semi-discrete geometric representation for nesting problems // Int. J. Prod. Res. 2013. V. 51, No. 14. P. 4155–4174. DOI: 10.1080/00207543.2012.751508.
     
  5. Burke E., Hellier R., Kendall G., Whitwell G. A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem // Oper. Res. 2006. V. 54, No. 3. P. 587–601. DOI: 10.1287/opre.1060.0293.
     
  6. Chehrazad S., Roose D., Wauters T. A fast and scalable bottom-left-fill algorithm to solve nesting problems using a semi-discrete representation // Eur. J. Oper. Res. 2022. V. 300, No. 3. P. 809–826. DOI: 10.1016/j.ejor.2021.10.043.
     
  7. Babu A. R., Babu N. R. A generic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms // Comput. Aided Des. 2001. V. 33, No. 12. P. 879–891. DOI: 10.1016/S0010-4485(00)00112-3.
     
  8. Bennell J. A., Oliveira J. F. The geometry of nesting problems: A tutorial // Eur. J. Oper. Res. 2008. V. 184, No. 2. P. 397–415. DOI: 10.1016/j.ejor.2006.11.038.
     
  9. Dowsland K. A., Dowsland W. B., Bennell J. A. Jostling for position: Local improvement for irregular cutting patterns // J. Oper. Res. Soc. 1998. V. 49, No. 6. P. 647–658. DOI: 10.1057/palgrave.jors.2600563.
     
  10. Han G.-C., Na S.-J. Two-stage approach for nesting in two-dimensional cutting problems using neural network and simulated annealing // Proc. Inst. Mech. Eng. Part B: J. Eng. Manuf. 1996. V. 210, No. 6. P. 509–519. DOI: 10.1243/PIME_PROC_1996_210_150_02.
     
  11. Oliveira J. F., Gomes A. M., Ferreira J. S. TOPOS — A new constructive algorithm for nesting problems // OR Spectrum. 2000. V. 22, No. 2. P. 263–284. DOI: 10.1007/s002910050105.

Исследование выполнено в рамках государственного задания Института математики им. С. Л. Соболева (проект № FWNF–2022–0019). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Акентьев Всеволод Владиславович
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: akentevvv01@gmail.com 

Статья поступила 19 ноября 2025 г.
После доработки — 12 декабря 2025 г.
Принята к публикации 22 декабря 2025 г.

Abstract:

The paper addresses the two-dimensional nesting problem, which consists in arranging a set of irregularly shaped objects within a bounded strip so as to minimize its utilized length. One of the key aspects affecting the efficiency of nesting algorithms is the choice of geometric representation, as it determines both the accuracy of shape approximation and the computational cost of the packing process. We introduce a novel object representation method based on adaptive trapezoids. In contrast to the commonly used segment-based approach, the proposed technique significantly reduces approximation errors caused by the misalignment between polygon vertices and grid nodes, thereby improving the fidelity of the geometric model. Computational experiments conducted on standard ESICUP benchmark datasets demonstrate that integrating the proposed representation into a bottom-left-fill packing algorithm yields denser layouts with only a moderate increase in computational effort. The results confirm the effectiveness and practical applicability of the proposed method for two-dimensional nesting problems. 

Tab. 2, illustr. 11, bibliogr. 11.

References:
  1. Y. Stoyan, J. Terno, G. Scheithauer, N. Gil, and T. Romanova, Phifunctions for primary 2D-objects, Stud. Inform. Univers. 2 (1), 1–32 (2002).
     
  2. J. F. Oliveira and J. S. Ferreira, Algorithms for nesting problems, in Appliad Simulated Annealing (Springer, Heidelberg, 1993), pp. 255–273, DOI: 10.1007/978-3-642-46787-5_13.
     
  3. H. Ma and C. C. Liu, Fast nesting of 2-D sheet parts with arbitrary shapes using a greedy method and semi-discrete representations, IEEE Trans. Autom. Sci. Eng. 4 (2), 273–282 (2007), DOI: 10.1109/TASE.2006.874973.
     
  4. R. Akunuru and N. R. Babu, A semi-discrete geometric representation for nesting problems, Int. J. Prod. Res. 51 (14), 4155–4174 (2013), DOI: 10.1080/ 00207543.2012.751508.
     
  5. E. Burke, R. Hellier, G. Kendall, and G. Whitwell, A new bottom-leftfill heuristic algorithm for the two-dimensional irregular packing problem, Oper. Res. 54 (3), 587–601 (2006), DOI: 10.1287/opre.1060.0293.
     
  6. S. Chehrazad, D. Roose, and T. Wauters, A fast and scalable bottom-leftfill algorithm to solve nesting problems using a semi-discrete representation, Eur. J. Oper. Res. 300 (3), 809–826 (2022), DOI: 10.1016/j.ejor.2021.10.043.
     
  7. A. R. Babu and N. R. Babu, A generic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms, Comput. Aided Des. 33 (12), 879–891 (2001), DOI: 10.1016/S0010-4485(00)00112-3.
     
  8. J. A. Bennell and J. F. Oliveira, The geometry of nesting problems: A tutorial, Eur. J. Oper. Res. 184 (2), 397–415 (2008), DOI: 10.1016/j.ejor.2006.11.038.
     
  9. K. A. Dowsland, W. B. Dowsland, and J. A. Bennell, Jostling for position: Local improvement for irregular cutting patterns, J. Oper. Res. Soc. 49 (6), 647–658 (1998), DOI: 10.1057/palgrave.jors.2600563.
     
  10. G.-C. Han and S.-J. Na, Two-stage approach for nesting in two-dimensional cutting problems using neural network and simulated annealing, Proc. Inst. Mech. Eng., Part B: J. Eng. Manuf. 210 (6), 509–519 (1996), DOI: 10.1243/PIME_PROC_1996_210_150_02.
     
  11. J. F. Oliveira, A. M. Gomes, and J. S. Ferreira, TOPOS — A new constructive algorithm for nesting problems, OR Spectrum 22 (2), 263–284 (2000), DOI: 10.1007/s002910050105.