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

Cargo securing under multi-drop and axle weight constraints

Author

Listed:
  • Çalık, Hatice
  • Juwet, Marc
  • Yaman, Hande
  • Vanden Berghe, Greet

Abstract

This study emerges from a real-world cargo securing application to ensure safer road transportation and falls into the category of container loading problems with practical constraints. The literature has lacked efficient methods for the secure loading of items with non-identical dimensions, weights and rotations into containers while ensuring that the securing efforts necessary are minimal when also taking into account multi-drop and axle weight constraints. This paper puts forward a new way of ensuring cargo stability that gives rise to a novel combinatorial optimization problem, which is a generalization of the two-dimensional rectangular strip packing problem with orthogonal rotations. We formally demonstrate the intractability of the problem and provide a mixed integer programming formulation. The formulation is based on a discretization of the packing polyhedron, enabling us to model a range of complicated and practical constraints. A group of practical constraints tends to be large in number and makes it difficult to solve the formulation in a reasonable amount of time. In order to overcome this difficulty, we develop an exact algorithmic framework. This framework initially solves certain relaxations of the problem to obtain strong lower bounds before subsequently embedding those lower bounds into a branch-and-cut algorithm. The experimental study serves three purposes: (i) evaluating the performance of the algorithmic framework and the mathematical formulation to assess the merits of the two methods, (ii) identifying the characteristics of hard problem instances and (iii) extracting insights regarding challenges in cargo securing to help managers and practitioners in decision making.

Suggested Citation

  • Ç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.
  • Handle: RePEc:eee:ejores:v:307:y:2023:i:1:p:157-176
    DOI: 10.1016/j.ejor.2022.08.031
    as

    Download full text from publisher

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

    File URL: https://libkey.io/10.1016/j.ejor.2022.08.031?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. 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.
    2. Jean-François Côté & Michel Gendreau & Jean-Yves Potvin, 2014. "An Exact Algorithm for the Two-Dimensional Orthogonal Packing Problem with Unloading Constraints," Operations Research, INFORMS, vol. 62(5), pages 1126-1141, October.
    3. Alonso, M.T. & Martinez-Sykora, A. & Alvarez-Valdes, R. & Parreño, F., 2022. "The pallet-loading vehicle routing problem with stability constraints," European Journal of Operational Research, Elsevier, vol. 302(3), pages 860-873.
    4. 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.
    5. 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.
    6. 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.
    7. Hanne Pollaris & Kris Braekers & An Caris & Gerrit K. Janssens & Sabine Limbourg, 2016. "Capacitated vehicle routing problem with sequence-based pallet loading and axle weight constraints," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 5(2), pages 231-255, June.
    8. J. E. Beasley, 1985. "An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure," Operations Research, INFORMS, vol. 33(1), pages 49-64, February.
    9. Lim, Andrew & Ma, Hong & Qiu, Chaoyang & Zhu, Wenbin, 2013. "The single container loading problem with axle weight constraints," International Journal of Production Economics, Elsevier, vol. 144(1), pages 358-369.
    10. 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.
    11. 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.
    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. Jéssica Gabriela Almeida Cunha & Vinícius Loti de Lima & Thiago Alves Queiroz, 2020. "Grids for cutting and packing problems: a study in the 2D knapsack problem," 4OR, Springer, vol. 18(3), pages 293-339, September.
    14. 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.
    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. 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.
    2. Alonso, M.T. & Martinez-Sykora, A. & Alvarez-Valdes, R. & Parreño, F., 2022. "The pallet-loading vehicle routing problem with stability constraints," European Journal of Operational Research, Elsevier, vol. 302(3), pages 860-873.
    3. 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.
    4. 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).
    5. 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.
    6. 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).
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. Konstantinos N. Androutsopoulos & Eleni Karouti, 2022. "A safety-driven truck loading problem," Operational Research, Springer, vol. 22(5), pages 4931-4963, November.
    13. 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.
    14. 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.
    15. 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.
    16. Silva, Elsa & Oliveira, José Fernando & Silveira, Tiago & Mundim, Leandro & Carravilla, Maria Antónia, 2023. "The Floating-Cuts model: a general and flexible mixed-integer programming model for non-guillotine and guillotine rectangular cutting problems," Omega, Elsevier, vol. 114(C).
    17. 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.
    18. 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).
    19. Paquay, Célia & Limbourg, Sabine & Schyns, Michaël, 2018. "A tailored two-phase constructive heuristic for the three-dimensional Multiple Bin Size Bin Packing Problem with transportation constraints," European Journal of Operational Research, Elsevier, vol. 267(1), pages 52-64.
    20. Manuel Ostermeier & Sara Martins & Pedro Amorim & Alexander Hübner, 2018. "Loading constraints for a multi-compartment vehicle routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(4), pages 997-1027, October.

    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:307:y:2023:i:1:p:157-176. 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.