IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v303y2022i3p1009-1026.html
   My bibliography  Save this article

Coordinate descent heuristics for the irregular strip packing problem of rasterized shapes

Author

Listed:
  • Umetani, Shunji
  • Murakami, Shohei

Abstract

We consider the irregular strip packing problem of rasterized shapes, where a given set of pieces of irregular shapes represented in pixels should be placed into a rectangular container without overlap. The rasterized shapes provide simple procedures of the intersection test without any exceptional handling due to geometric issues, while they often require much memory and computational effort in high-resolution. To reduce the complexity of rasterized shapes, we propose a pair of scanlines representation called the double scanline representation that merges consecutive pixels in each row and column into strips with unit width, respectively. Based on this, we develop coordinate descent heuristics for the raster model that repeat a line search in the horizontal and vertical directions alternately, where we also introduce a corner detection technique used in computer vision to reduce the search space. Computational results for test instances show that the proposed algorithm obtains sufficiently dense layouts of rasterized shapes in high-resolution within a reasonable computation time.

Suggested Citation

  • 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.
  • Handle: RePEc:eee:ejores:v:303:y:2022:i:3:p:1009-1026
    DOI: 10.1016/j.ejor.2022.03.034
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221722002582
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2022.03.034?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. E. K. Burke & R. S. R. Hellier & G. Kendall & G. Whitwell, 2010. "Irregular Packing Using the Line and Arc No-Fit Polygon," Operations Research, INFORMS, vol. 58(4-part-1), pages 948-970, August.
    2. 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.
    3. 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.
    4. 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.
    5. Li, Zhenyu & Milenkovic, Victor, 1995. "Compaction and separation algorithms for non-convex polygons and their applications," European Journal of Operational Research, Elsevier, vol. 84(3), pages 539-561, August.
    6. 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.
    7. Gomes, A. Miguel & Oliveira, Jose F., 2006. "Solving Irregular Strip Packing problems by hybridising simulated annealing and linear programming," European Journal of Operational Research, Elsevier, vol. 171(3), pages 811-829, June.
    8. Egeblad, Jens & Nielsen, Benny K. & Odgaard, Allan, 2007. "Fast neighborhood search for two- and three-dimensional nesting problems," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1249-1266, December.
    9. Voudouris, Christos & Tsang, Edward, 1999. "Guided local search and its application to the traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 113(2), pages 469-499, March.
    10. Elkeran, Ahmed, 2013. "A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering," European Journal of Operational Research, Elsevier, vol. 231(3), pages 757-769.
    11. 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.
    12. Dowsland, Kathryn A. & Vaid, Subodh & Dowsland, William B., 2002. "An algorithm for polygon placement using a bottom-left strategy," European Journal of Operational Research, Elsevier, vol. 141(2), pages 371-381, September.
    13. Guntram Scheithauer, 2018. "Introduction to Cutting and Packing Optimization," International Series in Operations Research and Management Science, Springer, number 978-3-319-64403-5, April.
    14. Dyckhoff, Harald, 1990. "A typology of cutting and packing problems," European Journal of Operational Research, Elsevier, vol. 44(2), pages 145-159, January.
    15. Gomes, A. Miguel & Oliveira, Jose F., 2002. "A 2-exchange heuristic for nesting problems," European Journal of Operational Research, Elsevier, vol. 141(2), pages 359-370, September.
    16. 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.
    17. Julia A. Bennell & Kathryn A. Dowsland, 2001. "Hybridising Tabu Search with Optimisation Techniques for Irregular Stock Cutting," Management Science, INFORMS, vol. 47(8), pages 1160-1172, August.
    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. Wang, Qianqing & Pantoja-Rosero, Bryan German & Santos, Ketson R.M. dos & Beyer, Katrin, 2024. "An image convolution-based method for the irregular stone packing problem in masonry wall construction," European Journal of Operational Research, Elsevier, vol. 316(2), pages 733-753.
    2. 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).
    3. 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.

    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. 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.
    4. 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.
    5. Elkeran, Ahmed, 2013. "A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering," European Journal of Operational Research, Elsevier, vol. 231(3), pages 757-769.
    6. 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.
    7. Chehrazad, Sahar & Roose, Dirk & Wauters, Tony, 2022. "A fast and scalable bottom-left-fill algorithm to solve nesting problems using a semi-discrete representation," European Journal of Operational Research, Elsevier, vol. 300(3), pages 809-826.
    8. 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.
    9. 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.
    10. 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).
    11. 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.
    12. 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.
    13. Egeblad, Jens & Nielsen, Benny K. & Odgaard, Allan, 2007. "Fast neighborhood search for two- and three-dimensional nesting problems," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1249-1266, December.
    14. 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.
    15. Jie Fang & Yunqing Rao & Xusheng Zhao & Bing Du, 2023. "A Hybrid Reinforcement Learning Algorithm for 2D Irregular Packing Problems," Mathematics, MDPI, vol. 11(2), pages 1-17, January.
    16. 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.
    17. Frank J. Kampas & János D. Pintér & Ignacio Castillo, 2023. "Model Development and Solver Demonstrations Using Randomized Test Problems," SN Operations Research Forum, Springer, vol. 4(1), pages 1-15, March.
    18. Burke, E.K. & Hellier, R.S.R. & Kendall, G. & Whitwell, G., 2007. "Complete and robust no-fit polygon generation for the irregular stock cutting problem," European Journal of Operational Research, Elsevier, vol. 179(1), pages 27-49, May.
    19. 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.
    20. 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.

    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:eee:ejores:v:303:y:2022:i:3:p:1009-1026. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.