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

Overlap Detection in 2D Amorphous Shapes for Paper Optimization in Digital Printing Presses

Author

Listed:
  • Yainier Labrada-Nueva

    (Research Center in Engineering and Applied Sciences, Autonomous University of Morelos State (UAEM), Cuernavaca 62209, Mexico)

  • Martin H. Cruz-Rosales

    (Faculty of Accounting, Administration & Informatics, UAEM, Cuernavaca 62209, Mexico)

  • Juan Manuel Rendón-Mancha

    (Research Center in Sciences, IICBA-UAEM, Cuernavaca 62209, Mexico)

  • Rafael Rivera-López

    (Computation and Systems Department, National Technological Institute/Veracruz Technological Institute, Veracruz 91860, Mexico)

  • Marta Lilia Eraña-Díaz

    (Research Center in Engineering and Applied Sciences, Autonomous University of Morelos State (UAEM), Cuernavaca 62209, Mexico)

  • Marco Antonio Cruz-Chávez

    (Research Center in Engineering and Applied Sciences, Autonomous University of Morelos State (UAEM), Cuernavaca 62209, Mexico)

Abstract

Paper waste in the mockups design with regular, irregular, and amorphous patterns is a critical problem in digital printing presses. Paper waste reduction directly impacts production costs, generating business and environmental benefits. This problem can be mapped to the two-dimensional irregular bin-packing problem. In this paper, an iterated local search algorithm using a novel neighborhood structure to detect overlaps between amorphous shapes is introduced. This algorithm is used to solve the paper waste problem, modeled as one 2D irregular bin-packing problem. The experimental results show that this approach works efficiently and effectively to detect and correct the overlaps between regular, irregular, and amorphous figures.

Suggested Citation

  • Yainier Labrada-Nueva & Martin H. Cruz-Rosales & Juan Manuel Rendón-Mancha & Rafael Rivera-López & Marta Lilia Eraña-Díaz & Marco Antonio Cruz-Chávez, 2021. "Overlap Detection in 2D Amorphous Shapes for Paper Optimization in Digital Printing Presses," Mathematics, MDPI, vol. 9(9), pages 1-22, May.
    • Handle: RePEc:gam:jmathe:v:9:y:2021:i:9:p:1033-:d:548143
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/9/9/1033/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/9/9/1033/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. Eunice López-Camacho & Gabriela Ochoa & Hugo Terashima-Marín & Edmund Burke, 2013. "An effective heuristic for the two-dimensional irregular bin packing problem," Annals of Operations Research, Springer, vol. 206(1), pages 241-264, July.
    3. 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.
    4. Han, Wei & Bennell, Julia A. & Zhao, Xiaozhou & Song, Xiang, 2013. "Construction heuristics for two-dimensional irregular shape bin packing with guillotine constraints," European Journal of Operational Research, Elsevier, vol. 230(3), pages 495-504.
    5. 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.
    6. Dyckhoff, Harald, 1990. "A typology of cutting and packing problems," European Journal of Operational Research, Elsevier, vol. 44(2), pages 145-159, January.
    7. J A Bennell & J F Oliveira, 2009. "A tutorial in irregular shape packing problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 93-105, May.
    8. Bennell, Julia A. & Oliveira, Jose F., 2008. "The geometry of nesting problems: A tutorial," European Journal of Operational Research, Elsevier, vol. 184(2), pages 397-415, January.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Walaa H. El-Ashmawi & Ahmad Salah & Mahmoud Bekhit & Guoqing Xiao & Khalil Al Ruqeishi & Ahmed Fathalla, 2023. "An Adaptive Jellyfish Search Algorithm for Packing Items with Conflict," Mathematics, MDPI, vol. 11(14), pages 1-28, July.
    2. 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.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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).
    8. 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.
    9. Eunice López-Camacho & Gabriela Ochoa & Hugo Terashima-Marín & Edmund Burke, 2013. "An effective heuristic for the two-dimensional irregular bin packing problem," Annals of Operations Research, Springer, vol. 206(1), pages 241-264, July.
    10. J A Bennell & J F Oliveira, 2009. "A tutorial in irregular shape packing problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 93-105, May.
    11. Josef Kallrath & Tatiana Romanova & Alexander Pankratov & Igor Litvinchev & Luis Infante, 2023. "Packing convex polygons in minimum-perimeter convex hulls," Journal of Global Optimization, Springer, vol. 85(1), pages 39-59, January.
    12. Martinez-Sykora, Antonio & Alvarez-Valdes, Ramon & Bennell, Julia & Tamarit, Jose Manuel, 2015. "Constructive procedures to solve 2-dimensional bin packing problems with irregular pieces and guillotine cuts," Omega, Elsevier, vol. 52(C), pages 15-32.
    13. 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.
    14. Toledo, Franklina M.B. & Carravilla, Maria Antónia & Ribeiro, Cristina & Oliveira, José F. & Gomes, A. Miguel, 2013. "The Dotted-Board Model: A new MIP model for nesting irregular shapes," International Journal of Production Economics, Elsevier, vol. 145(2), pages 478-487.
    15. Erjavec, J. & Gradisar, M. & Trkman, P., 2012. "Assessment of stock size to minimize cutting stock production costs," International Journal of Production Economics, Elsevier, vol. 135(1), pages 170-176.
    16. Parreño, F. & Alvarez-Valdes, R., 2021. "Mathematical models for a cutting problem in the glass manufacturing industry," Omega, Elsevier, vol. 103(C).
    17. Gahm, Christian & Uzunoglu, Aykut & Wahl, Stefan & Ganschinietz, Chantal & Tuma, Axel, 2022. "Applying machine learning for the anticipation of complex nesting solutions in hierarchical production planning," European Journal of Operational Research, Elsevier, vol. 296(3), pages 819-836.
    18. 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.
    19. Russo, Mauro & Sforza, Antonio & Sterle, Claudio, 2013. "An improvement of the knapsack function based algorithm of Gilmore and Gomory for the unconstrained two-dimensional guillotine cutting problem," International Journal of Production Economics, Elsevier, vol. 145(2), pages 451-462.
    20. 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.

    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:9:y:2021:i:9:p:1033-:d:548143. 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.