IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v223y2014i1p137-15410.1007-s10479-014-1634-2.html
   My bibliography  Save this article

Order and static stability into the strip packing problem

Author

Listed:
  • Thiago Queiroz
  • Flávio Miyazawa

Abstract

This paper investigates the two-dimensional strip packing problem considering the case in which items should be arranged to form a physically stable packing satisfying a predefined item unloading order from the top of the strip. The packing stability analysis is based on conditions for the static equilibrium of rigid bodies, differing from others strategies which are based on area and percentage of support. We consider an integer linear programming model for the strip packing problem with the order constraint, and a cutting plane algorithm to handle stability, leading to a branch-and-cut approach. We also present two heuristics: the first is based on a stack building algorithm; and, the last is a slight modification of the branch-and-cut approach. The computational experiments show that the branch-and-cut model can handle small and medium-sized instances, whereas the heuristics found almost optimal solutions quickly for several instances. With the combination of heuristics and the branch-and-cut algorithm, many instances are solved to near optimality in a few seconds. Copyright Springer Science+Business Media New York 2014

Suggested Citation

  • Thiago Queiroz & Flávio Miyazawa, 2014. "Order and static stability into the strip packing problem," Annals of Operations Research, Springer, vol. 223(1), pages 137-154, December.
    • Handle: RePEc:spr:annopr:v:223:y:2014:i:1:p:137-154:10.1007/s10479-014-1634-2
    DOI: 10.1007/s10479-014-1634-2
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-014-1634-2
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-014-1634-2?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. Allen, S.D. & Burke, E.K. & Kendall, G., 2011. "A hybrid placement strategy for the three-dimensional strip packing problem," European Journal of Operational Research, Elsevier, vol. 209(3), pages 219-227, March.
    2. 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.
    3. Michel Gendreau & Manuel Iori & Gilbert Laporte & Silvano Martello, 2006. "A Tabu Search Algorithm for a Routing and Container Loading Problem," Transportation Science, INFORMS, vol. 40(3), pages 342-350, August.
    4. Andreas Bortfeldt & Sabine Jungmann, 2012. "A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraint," Annals of Operations Research, Springer, vol. 196(1), pages 53-71, July.
    5. G Belov & G Scheithauer & E A Mukhacheva, 2008. "One-dimensional heuristics adapted for two-dimensional rectangular strip packing," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(6), pages 823-832, June.
    6. Manuel Iori & Juan-José Salazar-González & Daniele Vigo, 2007. "An Exact Approach for the Vehicle Routing Problem with Two-Dimensional Loading Constraints," Transportation Science, INFORMS, vol. 41(2), pages 253-264, May.
    7. de Queiroz, Thiago A. & Miyazawa, Flávio K., 2013. "Two-dimensional strip packing problem with load balancing, load bearing and multi-drop constraints," International Journal of Production Economics, Elsevier, vol. 145(2), pages 511-530.
    8. Bischoff, E. E. & Ratcliff, M. S. W., 1995. "Issues in the development of approaches to container loading," Omega, Elsevier, vol. 23(4), pages 377-390, August.
    9. Andrea Lodi & Silvano Martello & Daniele Vigo, 2004. "Models and Bounds for Two-Dimensional Level Packing Problems," Journal of Combinatorial Optimization, Springer, vol. 8(3), pages 363-379, September.
    10. Cintra, G.F. & Miyazawa, F.K. & Wakabayashi, Y. & Xavier, E.C., 2008. "Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation," European Journal of Operational Research, Elsevier, vol. 191(1), pages 61-85, November.
    11. Kenmochi, Mitsutoshi & Imamichi, Takashi & Nonobe, Koji & Yagiura, Mutsunori & Nagamochi, Hiroshi, 2009. "Exact algorithms for the two-dimensional strip packing problem with and without rotations," European Journal of Operational Research, Elsevier, vol. 198(1), pages 73-83, October.
    12. 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.
    13. Leonardo Junqueira & Reinaldo Morabito & Denise Sato Yamashita, 2012. "MIP-based approaches for the container loading problem with multi-drop constraints," Annals of Operations Research, Springer, vol. 199(1), pages 51-75, October.
    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. 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.
    2. Çalık, Hatice & Juwet, Marc & Yaman, Hande & Vanden Berghe, Greet, 2023. "Cargo securing under multi-drop and axle weight constraints," European Journal of Operational Research, Elsevier, vol. 307(1), pages 157-176.
    3. Kollsker, Torkil & Malaguti, Enrico, 2021. "Models and algorithms for optimising two-dimensional LEGO constructions," European Journal of Operational Research, Elsevier, vol. 289(1), pages 270-284.
    4. Alyne Toscano & Socorro Rangel & Horacio Hideki Yanasse, 2017. "A heuristic approach to minimize the number of saw cycles in small-scale furniture factories," Annals of Operations Research, Springer, vol. 258(2), pages 719-746, November.
    5. M. T. Alonso & R. Alvarez-Valdes & F. Parreño, 2020. "A GRASP algorithm for multi container loading problems with practical constraints," 4OR, Springer, vol. 18(1), pages 49-72, March.

    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. Carlos A. Vega-Mejía & Jairo R. Montoya-Torres & Sardar M. N. Islam, 2019. "Consideration of triple bottom line objectives for sustainability in the optimization of vehicle routing and loading operations: a systematic literature review," Annals of Operations Research, Springer, vol. 273(1), pages 311-375, February.
    2. 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.
    3. de Queiroz, Thiago A. & Miyazawa, Flávio K., 2013. "Two-dimensional strip packing problem with load balancing, load bearing and multi-drop constraints," International Journal of Production Economics, Elsevier, vol. 145(2), pages 511-530.
    4. Andreas Bortfeldt & Sabine Jungmann, 2012. "A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraint," Annals of Operations Research, Springer, vol. 196(1), pages 53-71, July.
    5. Bonet Filella, Guillem & Trivella, Alessio & Corman, Francesco, 2023. "Modeling soft unloading constraints in the multi-drop container loading problem," European Journal of Operational Research, Elsevier, vol. 308(1), pages 336-352.
    6. Wei, Lijun & Oon, Wee-Chong & Zhu, Wenbin & Lim, Andrew, 2012. "A reference length approach for the 3D strip packing problem," European Journal of Operational Research, Elsevier, vol. 220(1), pages 37-47.
    7. M. T. Alonso & R. Alvarez-Valdes & F. Parreño, 2020. "A GRASP algorithm for multi container loading problems with practical constraints," 4OR, Springer, vol. 18(1), pages 49-72, March.
    8. Jean-François Côté & Manuel Iori, 2018. "The Meet-in-the-Middle Principle for Cutting and Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 646-661, November.
    9. Bortfeldt, Andreas & Wäscher, Gerhard, 2013. "Constraints in container loading – A state-of-the-art review," European Journal of Operational Research, Elsevier, vol. 229(1), pages 1-20.
    10. Galrão Ramos, A. & Oliveira, José F. & Gonçalves, José F. & Lopes, Manuel P., 2016. "A container loading algorithm with static mechanical equilibrium stability constraints," Transportation Research Part B: Methodological, Elsevier, vol. 91(C), pages 565-581.
    11. Manuel Iori & Silvano Martello, 2010. "Routing problems with loading constraints," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 18(1), pages 4-27, July.
    12. Wei, Lijun & Oon, Wee-Chong & Zhu, Wenbin & Lim, Andrew, 2011. "A skyline heuristic for the 2D rectangular packing and strip packing problems," European Journal of Operational Research, Elsevier, vol. 215(2), pages 337-346, December.
    13. 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.
    14. 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.
    15. Kurpel, Deidson Vitorio & Scarpin, Cassius Tadeu & Pécora Junior, José Eduardo & Schenekemberg, Cleder Marcos & Coelho, Leandro C., 2020. "The exact solutions of several types of container loading problems," European Journal of Operational Research, Elsevier, vol. 284(1), pages 87-107.
    16. Wei, Lijun & Hu, Qian & Lim, Andrew & Liu, Qiang, 2018. "A best-fit branch-and-bound heuristic for the unconstrained two-dimensional non-guillotine cutting problem," European Journal of Operational Research, Elsevier, vol. 270(2), pages 448-474.
    17. Ana Moura & Telmo Pinto & Cláudio Alves & José Valério de Carvalho, 2023. "A Matheuristic Approach to the Integration of Three-Dimensional Bin Packing Problem and Vehicle Routing Problem with Simultaneous Delivery and Pickup," Mathematics, MDPI, vol. 11(3), pages 1-16, January.
    18. Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.
    19. Bayliss, Christopher & Currie, Christine S.M. & Bennell, Julia A. & Martinez-Sykora, Antonio, 2021. "Queue-constrained packing: A vehicle ferry case study," European Journal of Operational Research, Elsevier, vol. 289(2), pages 727-741.
    20. Cui, Yaodong & Zhao, Zhigang, 2013. "Heuristic for the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns," European Journal of Operational Research, Elsevier, vol. 231(2), pages 288-298.

    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:spr:annopr:v:223:y:2014:i:1:p:137-154:10.1007/s10479-014-1634-2. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.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.