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

The exact solutions of several types of container loading problems

Author

Listed:
  • Kurpel, Deidson Vitorio
  • Scarpin, Cassius Tadeu
  • Pécora Junior, José Eduardo
  • Schenekemberg, Cleder Marcos
  • Coelho, Leandro C.

Abstract

In this paper, we address multiple container loading problems, consisting of placing rectangular boxes, orthogonally and without overlapping, inside containers in order to optimize a given objective function, generally maximizing the value of the packed boxes or minimizing the number of containers required to pack all available boxes. Four techniques to enumerate the possible locations of boxes inside a container, some of them not yet tested in the literature, are evaluated. We also propose new techniques to obtain primal and dual bounds for these problems. In addition, we study the constraints related to box orientation, load stability, and separation of boxes. Detailed analysis on well-known benchmark instances shows that our method is very competitive, generating mathematical models containing significantly fewer variables and constraints than the traditional approach existing in the literature. We test our methods on five different benchmark sets. We provide a detailed comparison with different approaches from the CLP literature, proving new optimal solutions and improving the best-known results for several instances.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:284:y:2020:i:1:p:87-107
    DOI: 10.1016/j.ejor.2019.12.012
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221719310136
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2019.12.012?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. Nicos Christofides & Charles Whitlock, 1977. "An Algorithm for Two-Dimensional Cutting Problems," Operations Research, INFORMS, vol. 25(1), pages 30-44, February.
    2. 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.
    3. 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.
    4. 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.
    5. Mohanty, Bidhu B. & Mathur, Kamlesh & Ivancic, Nancy J., 1994. "Value considerations in three-dimensional packing -- A heuristic procedure using the fractional knapsack problem," European Journal of Operational Research, Elsevier, vol. 74(1), pages 143-151, April.
    6. 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.
    7. Wei, Lijun & Zhu, Wenbin & Lim, Andrew, 2015. "A goal-driven prototype column generation strategy for the multiple container loading cost minimization problem," European Journal of Operational Research, Elsevier, vol. 241(1), pages 39-49.
    8. 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.
    9. Zhu, Wenbin & Huang, Weili & Lim, Andrew, 2012. "A prototype column generation strategy for the multiple container loading problem," European Journal of Operational Research, Elsevier, vol. 223(1), pages 27-39.
    10. Toffolo, Túlio A.M. & Esprit, Eline & Wauters, Tony & Vanden Berghe, Greet, 2017. "A two-dimensional heuristic decomposition approach to a three-dimensional multiple container loading problem," European Journal of Operational Research, Elsevier, vol. 257(2), pages 526-538.
    11. Tian, Tian & Zhu, Wenbin & Lim, Andrew & Wei, Lijun, 2016. "The multiple container loading problem with preference," European Journal of Operational Research, Elsevier, vol. 248(1), pages 84-94.
    12. Chen, C. S. & Lee, S. M. & Shen, Q. S., 1995. "An analytical model for the container loading problem," European Journal of Operational Research, Elsevier, vol. 80(1), pages 68-76, January.
    13. Sheng, Liu & Hongxia, Zhao & Xisong, Dong & Changjian, Cheng, 2016. "A heuristic algorithm for container loading of pallets with infill boxes," European Journal of Operational Research, Elsevier, vol. 252(3), pages 728-736.
    14. J. E. Beasley, 1985. "An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure," Operations Research, INFORMS, vol. 33(1), pages 49-64, February.
    15. 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.
    16. F. Parreño & R. Alvarez-Valdes & J. Oliveira & J. Tamarit, 2010. "A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing," Annals of Operations Research, Springer, vol. 179(1), pages 203-220, September.
    17. Silvano Martello & David Pisinger & Daniele Vigo, 2000. "The Three-Dimensional Bin Packing Problem," Operations Research, INFORMS, vol. 48(2), pages 256-267, April.
    18. Alonso, M.T. & Alvarez-Valdes, R. & Iori, M. & Parreño, F. & Tamarit, J.M., 2017. "Mathematical models for multicontainer loading problems," Omega, Elsevier, vol. 66(PA), pages 106-117.
    19. Gonçalves, José Fernando & Resende, Mauricio G.C., 2013. "A biased random key genetic algorithm for 2D and 3D bin packing problems," International Journal of Production Economics, Elsevier, vol. 145(2), pages 500-510.
    20. Ramos, António G. & Silva, Elsa & Oliveira, José F., 2018. "A new load balance methodology for container loading problem in road transportation," European Journal of Operational Research, Elsevier, vol. 266(3), pages 1140-1152.
    21. Eley, Michael, 2002. "Solving container loading problems by block arrangement," European Journal of Operational Research, Elsevier, vol. 141(2), pages 393-409, September.
    22. Che, Chan Hou & Huang, Weili & Lim, Andrew & Zhu, Wenbin, 2011. "The multiple container loading cost minimization problem," European Journal of Operational Research, Elsevier, vol. 214(3), pages 501-511, November.
    23. Martin Grunewald & Thomas Volling & Christoph Müller & Thomas S. Spengler, 2018. "Multi-item single-source ordering with detailed consideration of transportation capacities," Journal of Business Economics, Springer, vol. 88(7), pages 971-1007, September.
    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. Papp, Dávid & Regős, Krisztina & Domokos, Gábor & Bozóki, Sándor, 2023. "The smallest mono-unstable convex polyhedron with point masses has 8 faces and 11 vertices," European Journal of Operational Research, Elsevier, vol. 310(2), pages 511-517.
    2. Chagas, Guilherme O. & Coelho, Leandro C. & Darvish, Maryam & Renaud, Jacques, 2023. "Modeling and solving the waste valorization production and distribution scheduling problem," European Journal of Operational Research, Elsevier, vol. 306(1), pages 400-417.
    3. Silva, Allyson & Coelho, Leandro C. & Darvish, Maryam & Renaud, Jacques, 2022. "A cutting plane method and a parallel algorithm for packing rectangles in a circular container," European Journal of Operational Research, Elsevier, vol. 303(1), pages 114-128.
    4. Gajda, Mikele & Trivella, Alessio & Mansini, Renata & Pisinger, David, 2022. "An optimization approach for a complex real-life container loading problem," Omega, Elsevier, vol. 107(C).

    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. I. Gimenez-Palacios & M. T. Alonso & R. Alvarez-Valdes & F. Parreño, 2021. "Logistic constraints in container loading problems: the impact of complete shipment conditions," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(1), pages 177-203, April.
    3. 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.
    4. Tian, Tian & Zhu, Wenbin & Lim, Andrew & Wei, Lijun, 2016. "The multiple container loading problem with preference," European Journal of Operational Research, Elsevier, vol. 248(1), pages 84-94.
    5. Castellucci, Pedro B. & Toledo, Franklina M.B. & Costa, Alysson M., 2019. "Output maximization container loading problem with time availability constraints," Operations Research Perspectives, Elsevier, vol. 6(C).
    6. Sheng, Liu & Hongxia, Zhao & Xisong, Dong & Changjian, Cheng, 2016. "A heuristic algorithm for container loading of pallets with infill boxes," European Journal of Operational Research, Elsevier, vol. 252(3), pages 728-736.
    7. Araya, Ignacio & Moyano, Mauricio & Sanchez, Cristobal, 2020. "A beam search algorithm for the biobjective container loading problem," European Journal of Operational Research, Elsevier, vol. 286(2), pages 417-431.
    8. 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.
    9. 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.
    10. Novas, Juan M. & Ramello, Juan Ignacio & Rodríguez, María Analía, 2020. "Generalized disjunctive programming models for the truck loading problem: A case study from the non-alcoholic beverages industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    11. Toffolo, Túlio A.M. & Esprit, Eline & Wauters, Tony & Vanden Berghe, Greet, 2017. "A two-dimensional heuristic decomposition approach to a three-dimensional multiple container loading problem," European Journal of Operational Research, Elsevier, vol. 257(2), pages 526-538.
    12. Ramos, António G. & Silva, Elsa & Oliveira, José F., 2018. "A new load balance methodology for container loading problem in road transportation," European Journal of Operational Research, Elsevier, vol. 266(3), pages 1140-1152.
    13. Gajda, Mikele & Trivella, Alessio & Mansini, Renata & Pisinger, David, 2022. "An optimization approach for a complex real-life container loading problem," Omega, Elsevier, vol. 107(C).
    14. Wei, Lijun & Zhu, Wenbin & Lim, Andrew, 2015. "A goal-driven prototype column generation strategy for the multiple container loading cost minimization problem," European Journal of Operational Research, Elsevier, vol. 241(1), pages 39-49.
    15. Zhu, Wenbin & Huang, Weili & Lim, Andrew, 2012. "A prototype column generation strategy for the multiple container loading problem," European Journal of Operational Research, Elsevier, vol. 223(1), pages 27-39.
    16. Vélez-Gallego, Mario C. & Teran-Somohano, Alejandro & Smith, Alice E., 2020. "Minimizing late deliveries in a truck loading problem," European Journal of Operational Research, Elsevier, vol. 286(3), pages 919-928.
    17. Silva, Elsa & Ramos, António G. & Oliveira, José F., 2018. "Load balance recovery for multi-drop distribution problems: A mixed integer linear programming approach," Transportation Research Part B: Methodological, Elsevier, vol. 116(C), pages 62-75.
    18. 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.
    19. Gzara, Fatma & Elhedhli, Samir & Yildiz, Burak C., 2020. "The Pallet Loading Problem: Three-dimensional bin packing with practical constraints," European Journal of Operational Research, Elsevier, vol. 287(3), pages 1062-1074.
    20. Gonçalves, José Fernando & Resende, Mauricio G.C., 2013. "A biased random key genetic algorithm for 2D and 3D bin packing problems," International Journal of Production Economics, Elsevier, vol. 145(2), pages 500-510.

    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:284:y:2020:i:1:p:87-107. 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.