IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v12y2024i15p2414-d1449139.html
   My bibliography  Save this article

The Normalized Direct Trigonometry Model for the Two-Dimensional Irregular Strip Packing Problem

Author

Listed:
  • Germán Pantoja-Benavides

    (School of Engineering, Los Andes University, Bogota 111711, Colombia
    Department of Mathematics, University of Castilla-La Mancha, 02071 Albacete, Spain)

  • David Álvarez-Martínez

    (School of Engineering, Los Andes University, Bogota 111711, Colombia)

  • Francisco Parreño Torres

    (Department of Mathematics, University of Castilla-La Mancha, 02071 Albacete, Spain)

Abstract

Background: The Irregular Strip Packing Problem (ISPP) involves packing a set of irregularly shaped items within a strip while minimizing its length. Methods: This study introduces the Normalized Direct Trigonometry Model (NDTM), an innovative enhancement of the Direct Trigonometry Model (DTM). The NDTM incorporates a distance function that supports the integration of the separation constraint, which mandates a minimum separation distance between items. Additionally, the paper proposes a new set of constraints based on the bounding boxes of the pieces aimed at improving the non-overlapping condition. Results: Comparative computational experiments were performed using a comprehensive set of 90 instances. Results show that the NDTM finds more feasible and optimal solutions than the DTM. While the NDTM allows for the implementation of the separation constraint, the number of feasible and optimal solutions tends to decrease as more separation among the items is considered, despite not increasing the number of variables or constraints. Conclusions: The NDTM outperforms the DTM. Moreover, the results indicate that the new set of non-overlapping constraints facilitates the exploration of feasible solutions at the expense of optimality in some cases.

Suggested Citation

  • Germán Pantoja-Benavides & David Álvarez-Martínez & Francisco Parreño Torres, 2024. "The Normalized Direct Trigonometry Model for the Two-Dimensional Irregular Strip Packing Problem," Mathematics, MDPI, vol. 12(15), pages 1-25, August.
    • Handle: RePEc:gam:jmathe:v:12:y:2024:i:15:p:2414-:d:1449139
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/12/15/2414/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/12/15/2414/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Aline A.S. Leao & Franklina M.B. Toledo & José Fernando Oliveira & Maria Antónia Carravilla, 2016. "A semi-continuous MIP model for the irregular strip packing problem," International Journal of Production Research, Taylor & Francis Journals, vol. 54(3), pages 712-721, February.
    2. Umetani, Shunji & Murakami, Shohei, 2022. "Coordinate descent heuristics for the irregular strip packing problem of rasterized shapes," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1009-1026.
    3. Cherri, Luiz H. & Mundim, Leandro R. & Andretta, Marina & Toledo, Franklina M.B. & Oliveira, José F. & Carravilla, Maria Antónia, 2016. "Robust mixed-integer linear programming models for the irregular strip packing problem," European Journal of Operational Research, Elsevier, vol. 253(3), pages 570-583.
    4. Akang Wang & Christopher L. Hanselman & Chrysanthos E. Gounaris, 2018. "A customized branch-and-bound approach for irregular shape nesting," Journal of Global Optimization, Springer, vol. 71(4), pages 935-955, August.
    5. Sato, André Kubagawa & Martins, Thiago Castro & Gomes, Antonio Miguel & Tsuzuki, Marcos Sales Guerra, 2019. "Raster penetration map applied to the irregular packing problem," European Journal of Operational Research, Elsevier, vol. 279(2), pages 657-671.
    6. Wascher, Gerhard & Hau[ss]ner, Heike & Schumann, Holger, 2007. "An improved typology of cutting and packing problems," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1109-1130, December.
    7. Martinez-Sykora, A. & Alvarez-Valdes, R. & Bennell, J.A. & Ruiz, R. & Tamarit, J.M., 2017. "Matheuristics for the irregular bin packing problem with free rotations," European Journal of Operational Research, Elsevier, vol. 258(2), pages 440-455.
    8. Yuriy Stoyan & Alexander Pankratov & Tatiana Romanova, 2016. "Cutting and packing problems for irregular objects with continuous rotations: mathematical modelling and non-linear optimization," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 67(5), pages 786-800, May.
    9. Bonfim Amaro Júnior & Plácido Rogério Pinheiro & Pedro Veras Coelho, 2017. "A Parallel Biased Random-Key Genetic Algorithm with Multiple Populations Applied to Irregular Strip Packing Problems," Mathematical Problems in Engineering, Hindawi, vol. 2017, pages 1-11, September.
    10. Abeysooriya, Ranga P. & Bennell, Julia A. & Martinez-Sykora, Antonio, 2018. "Jostle heuristics for the 2D-irregular shapes bin packing problems with free rotation," International Journal of Production Economics, Elsevier, vol. 195(C), pages 12-26.
    11. Jakobs, Stefan, 1996. "On genetic algorithms for the packing of polygons," European Journal of Operational Research, Elsevier, vol. 88(1), pages 165-181, January.
    12. Yuriy Stoyan & Alexandr Pankratov & Tatiana Romanova, 2017. "Placement Problems for Irregular Objects: Mathematical Modeling, Optimization and Applications," Springer Optimization and Its Applications, in: Sergiy Butenko & Panos M. Pardalos & Volodymyr Shylo (ed.), Optimization Methods and Applications, pages 521-559, Springer.
    13. Miguel Santoro & Felipe Lemos, 2015. "Irregular packing: MILP model based on a polygonal enclosure," Annals of Operations Research, Springer, vol. 235(1), pages 693-707, December.
    14. Luiz H. Cherri & Adriana C. Cherri & Edilaine M. Soler, 2018. "Mixed integer quadratically-constrained programming model to solve the irregular strip packing problem with continuous rotations," Journal of Global Optimization, Springer, vol. 72(1), pages 89-107, September.
    15. Silvano Martello & Michele Monaci & Daniele Vigo, 2003. "An Exact Approach to the Strip-Packing Problem," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 310-319, August.
    16. Alvarez-Valdes, R. & Martinez, A. & Tamarit, J.M., 2013. "A branch & bound algorithm for cutting and packing irregularly shaped pieces," International Journal of Production Economics, Elsevier, vol. 145(2), pages 463-477.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Lastra-Díaz, Juan J. & Ortuño, M. Teresa, 2024. "Mixed-integer programming models for irregular strip packing based on vertical slices and feasibility cuts," European Journal of Operational Research, Elsevier, vol. 313(1), pages 69-91.
    2. Leao, Aline A.S. & Toledo, Franklina M.B. & Oliveira, José Fernando & Carravilla, Maria Antónia & Alvarez-Valdés, Ramón, 2020. "Irregular packing problems: A review of mathematical models," European Journal of Operational Research, Elsevier, vol. 282(3), pages 803-822.
    3. Longhui Meng & Liang Ding & Aqib Mashood Khan & Ray Tahir Mushtaq & Mohammed Alkahtani, 2024. "Optimizing Two-Dimensional Irregular Pattern Packing with Advanced Overlap Optimization Techniques," Mathematics, MDPI, vol. 12(17), pages 1-19, August.
    4. Cherri, Luiz Henrique & Carravilla, Maria Antónia & Ribeiro, Cristina & Toledo, Franklina Maria Bragion, 2019. "Optimality in nesting problems: New constraint programming models and a new global constraint for non-overlap," Operations Research Perspectives, Elsevier, vol. 6(C).
    5. Igor Kierkosz & Maciej Łuczak, 2019. "A one-pass heuristic for nesting problems," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 29(1), pages 37-60.
    6. Bennell, J.A. & Cabo, M. & Martínez-Sykora, A., 2018. "A beam search approach to solve the convex irregular bin packing problem with guillotine guts," European Journal of Operational Research, Elsevier, vol. 270(1), pages 89-102.
    7. Kimms, Alf & Király, Hédi, 2023. "An extended model formulation for the two-dimensional irregular strip packing problem considering general industry-relevant aspects," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1202-1218.
    8. Longhui Meng & Liang Ding & Ray Tahir Mushtaq & Saqib Anwar & Aqib Mashood Khan, 2024. "Efficient Packing of 2D Irregular Parts: A Hybrid Approach Incorporating a Modified Genetic Algorithm and Image Processing," Mathematics, MDPI, vol. 12(22), pages 1-21, November.
    9. Sato, André Kubagawa & Martins, Thiago Castro & Gomes, Antonio Miguel & Tsuzuki, Marcos Sales Guerra, 2019. "Raster penetration map applied to the irregular packing problem," European Journal of Operational Research, Elsevier, vol. 279(2), pages 657-671.
    10. Akang Wang & Christopher L. Hanselman & Chrysanthos E. Gounaris, 2018. "A customized branch-and-bound approach for irregular shape nesting," Journal of Global Optimization, Springer, vol. 71(4), pages 935-955, August.
    11. Qiang Luo & Yunqing Rao, 2022. "Improved Sliding Algorithm for Generating No-Fit Polygon in the 2D Irregular Packing Problem," Mathematics, MDPI, vol. 10(16), pages 1-18, August.
    12. Marco Antonio Boschetti & Lorenza Montaletti, 2010. "An Exact Algorithm for the Two-Dimensional Strip-Packing Problem," Operations Research, INFORMS, vol. 58(6), pages 1774-1791, December.
    13. Hagspihl, Thomas & Kolisch, Rainer & Fontaine, Pirmin & Schiffels, Sebastian, 2024. "Apron layout planning–Optimal positioning of aircraft stands," Transportation Research Part B: Methodological, Elsevier, vol. 179(C).
    14. Iori, Manuel & de Lima, Vinícius L. & Martello, Silvano & Miyazawa, Flávio K. & Monaci, Michele, 2021. "Exact solution techniques for two-dimensional cutting and packing," European Journal of Operational Research, Elsevier, vol. 289(2), pages 399-415.
    15. Hu, Xiaoxuan & Zhu, Waiming & Ma, Huawei & An, Bo & Zhi, Yanling & Wu, Yi, 2021. "Orientational variable-length strip covering problem: A branch-and-price-based algorithm," European Journal of Operational Research, Elsevier, vol. 289(1), pages 254-269.
    16. Demiröz, Barış Evrim & Altınel, İ. Kuban & Akarun, Lale, 2019. "Rectangle blanket problem: Binary integer linear programming formulation and solution algorithms," European Journal of Operational Research, Elsevier, vol. 277(1), pages 62-83.
    17. Ortmann, Frank G. & Ntene, Nthabiseng & van Vuuren, Jan H., 2010. "New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems," European Journal of Operational Research, Elsevier, vol. 203(2), pages 306-315, June.
    18. Martinez-Sykora, A. & Alvarez-Valdes, R. & Bennell, J.A. & Ruiz, R. & Tamarit, J.M., 2017. "Matheuristics for the irregular bin packing problem with free rotations," European Journal of Operational Research, Elsevier, vol. 258(2), pages 440-455.
    19. Leung, Stephen C.H. & Zhang, Defu & Sim, Kwang Mong, 2011. "A two-stage intelligent search algorithm for the two-dimensional strip packing problem," European Journal of Operational Research, Elsevier, vol. 215(1), pages 57-69, November.
    20. Önder Aşık & Ender Özcan, 2009. "Bidirectional best-fit heuristic for orthogonal rectangular strip packing," Annals of Operations Research, Springer, vol. 172(1), pages 405-427, November.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:12:y:2024:i:15:p:2414-:d:1449139. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.