Skip to main content
SpringerLink
Log in

Logistic constraints in container loading problems: the impact of complete shipment conditions

  • Original Paper
  • Published:
TOP Aims and scope Submit manuscript

Abstract

Container loading problems (CLP), in which a set of boxes have to be loaded into containers or onto trucks, are at the core of many transportation problems. Good solutions to these packing problems are crucial for the efficient use of logistic resources. However, to produce solutions that are useful in practice, besides the basic conditions ensuring that boxes do not exceed the container dimensions and do not overlap each other, other physical and logistic constraints have to be included when solving the CLP. In this study, we focus on a special type of logistic constraint: complete shipment constraints, which ensure that either all or none of the boxes in each customer order are loaded. Although these constraints have seldom been considered in the literature, they arise very often in practice. Customers do not want to receive incomplete parts of their orders in successive deliveries and retailers do not want to have to store incomplete orders and wait until the remaining boxes arrive to deliver the orders to the customers. We include these constraints in an integer linear formulation of the CLP and develop four heuristic strategies to deal with them efficiently. An extensive computational study compares the relative performance of these strategies and shows that when a good strategy is used the impact of these constraints on the solution of the CLP is quite small.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  • Alonso MT, Alvarez-Valdes R, Parreño F, Tamarit JM (2014) A reactive GRASP algorithm for the container loading problem with load-bearing constraints. Eur J Ind Eng 8(1):669–694

    Google Scholar 

  • Alonso MT, Alvarez-Valdes R, Iori M, Parreño F, Tamarit JM (2017) Mathematical models for multicontainer loading problems. Omega 66:106–117

    Google Scholar 

  • Alonso MT, Alvarez-Valdes R, Iori M, Parreño F (2019) Mathematical models for multi container loading problems with practical constraints. Comput Ind Eng 127:722–733

    Google Scholar 

  • Araujo OCB, Armentano VA (2007) A multi-start random constructive heuristic for the container loading problem. Pesqui Operac 27(2):311–331

    Google Scholar 

  • Araya I, Riff MC (2014) A beam search approach to the container loading problem. Comput Oper Res 43:100–107

    Google Scholar 

  • Araya I, Guerrero K, Nuñez E (2017) VCS: a new heuristic function for selecting boxes in the single container problem. Comput Oper Res 82:27–35

    Google Scholar 

  • Battarra M, Monaci M, Vigo D (2009) An adaptive guidance approach for the heuristic solution of a minimum multiple trip vehicle routing problem. Comput Oper Res 36:3041–3050

    Google Scholar 

  • Beasley J (1985) An exact two-dimensional non-guillotine cutting tree search procedure. Oper Res 33(1):49–64

    Google Scholar 

  • Bischoff EE, Ratcliff MSW (1995) Issues in the development of approaches to container loading. Omega 23(4):377–390

    Google Scholar 

  • Bortfeldt A (2012) A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints. Comput Oper Res 39:2248–2257

    Google Scholar 

  • Bortfeldt A, Gehring H (2001) A hybrid genetic algorithm for the container loading problem. Eur J Oper Res 131(1):143–161

    Google Scholar 

  • Bortfeldt A, Wäscher G (2013) Constraints in container loading. A state of the art review. Eur J Oper Res 229(1):1–20

    Google Scholar 

  • Bortfeldt A, Gehring H, Mack D (2003) A parallel tabu search algorithm for solving the container loading problem. Parallel Comput 29(5):641–662

    Google Scholar 

  • Boschetti M, Mingozzi A (2002) New upper bounds for the two-dimensional orthogonal non-guillotine cutting stock problem. IMA J Manag Math 13(2):95–119

    Google Scholar 

  • Ceschia S, Schaerf A (2013) Local search for amulti-drop multi-container loading problem. J Heuristics 19:275–294

    Google Scholar 

  • Christensen SG, Rousøe DM (2009) Container loading with multi-drop constraints. Int Trans Oper Res 16:727–743

    Google Scholar 

  • Christofides N, Whitlock C (1977) An algorithm for towo-dimensional cutting problems. Oper Res 25(1):30–44

    Google Scholar 

  • Codas A, Camponogara E (2012) Mixed-integer linear optimization for optimal lift-gas allocation with well-separator routing. Eur J Oper Res 217(1):222–231

    Google Scholar 

  • Correcher JF, Alonso MT, Parreño F, Alvarez-Valdes R (2017) Solving a large multicontainer loading problem in the car manufacturing industry. Comput Oper Res 82(1):139–152

    Google Scholar 

  • Côté J, Iori M (2018) The meet-in-the-middle principle for cutting and packing problems. INF J Comput 30(4):646–661

    Google Scholar 

  • Dabia S, Ropke S, Van Woensel T (2019) Cover inequalities for a vehicle routing problem with time windows and shifts. Transp Sci 53(5):1354–1371

    Google Scholar 

  • Davies AP, Bischoff EE (1999) Weight distribution considerations in container loading. Eur J Oper Res 114(3):509–527

    Google Scholar 

  • de Almeida Cunha JG, de Lima VL, de Queiroz TA (2019) Grids for cutting and packing problems: a study in the 2D knapsack problem. 4OR-Q J Oper Res. https://doi.org/10.1007/s10288-019-00419-9

    Article  Google Scholar 

  • Egeblad J, Garavelli C, Lisi S, Pisinger D (2010) Heuristics for container loading of furniture. Eur J Oper Res 200(3):881–892

    Google Scholar 

  • Eley M (2003) A bottleneck assignment approach to the multiple container loading problem. OR Spectr 25:45–60

    Google Scholar 

  • EUROSTAT (2017) Eurostat statistics explained, transport. https://ec.europa.eu/eurostat/. Online Accessed 26 Dec 2019

  • Fanslau T, Bortfeldt A (2010) A tree search algorithm for solving the container loading problem. INF J Comput 22(2):222–235

    Google Scholar 

  • Fekete SP, Schepers J, Van der Veen JC (2007) An exact algorithm for higher-dimensional orthogonal packing. Oper Res 55(3):569–587

    Google Scholar 

  • Fuellerer G, Doerner K, Hartl RF, Iori M (2010) Metaheuristics for vehicle routing problems with three-dimensional loading constraints. Eur J Oper Res 201:751–759

    Google Scholar 

  • Gehring H, Bortfeldt A (2002) A parallel genetic algorithm for solving the container loading problem. Int Trans Oper Res 9(4):497–511

    Google Scholar 

  • Gendreau M, Iori M, Laporte G, Martello S (2006) A tabu search algorithm for a routing and container loading problem. Transp Sci 40:342–350

    Google Scholar 

  • Jamrus T, Chien CF (2016) Extended priority-based hybrid genetic algorithm for the less-than-container loading problem. Comput Ind Eng 96:227–236

    Google Scholar 

  • Jin Z, Ohno K, Du J (2004) An efficient approach for the three-dimensional container packing problem with practical constraints. Asia-Pac J Oper Res 21(3):279–295

    Google Scholar 

  • Junqueira L, Morabito R, Sato Yamashita D (2012a) MIP-based approaches for the container loading problem with multi-drop constraints. Ann Oper Res 199(1):51–75

    Google Scholar 

  • Junqueira L, Morabito R, Sato Yamashita D (2012b) Three-dimensional container loading models with cargo stability and load bearing constraints. Comput Oper Res 39(1):74–85

    Google Scholar 

  • Lim A, Ma H, Qiu C, Zhu W (2013) The single container loading problem with axle weight constraints. Int J Prod Econ 144(1):358–369

    Google Scholar 

  • Liu WY, Yue Y, Dong Z, Mapple C, Keech M (2011) A novel hybrid tabu search approach to container loading. Comput Oper Res 38:797–807

    Google Scholar 

  • Mack D, Bortfeldt A, Gehring H (2004) A parallel hybrid local search algorithm for the container loading problem. Int Trans Oper Res 11(5):511–533

    Google Scholar 

  • Makarem OC, Haraty RA (2010) Smart container loading. Comput Methods Sci Technol 10:S231–S245

    Google Scholar 

  • Martello S, Pisinger D, Vigo D (2000) The three-dimensional bin packing problem. Oper Res 48(2):256–267

    Google Scholar 

  • Moura A, Oliveira JF (2005) A GRASP approach to the container-loading problem. IEEE Intell Syst 20(4):50–57

    Google Scholar 

  • Paquay C, Schyns M, Limbourg S (2016) A mixed integer programming formulation for the three-dimensional bin packing problem deriving from an air cargo application. Int Trans Oper Res 23(1):187–213

    Google Scholar 

  • Parreño F, Alvarez-Valdes R, Tamarit JM, Oliveira JF (2008) A maximal-space algorithm for the container loading problem. INF J Comput 20(3):412–422

    Google Scholar 

  • Parreño F, Alvarez-Valdes R, Oliveira JF, Tamarit JM (2010) Neighborhood structures for the container loading problem: a VNS implementation. J Heuristics 16:1–22

    Google Scholar 

  • Pollaris H, Braekers K, Caris A, Janssens G, Limbourg S (2016) Capacitated vehicle routing problem with sequence-based pallet loading and axle weight constraints. EURO J Transp Logist 5:231–255

    Google Scholar 

  • Ramos AG, Oliveira JF, Gonçalves JF, Lopes MP (2015) Dynamic stability metrics for the container loading problem. Transp Res Part C Emerg Technol 60:480–497

    Google Scholar 

  • Ramos AG, Oliveira JF, Lopes MP (2016) A physical packing sequence algorithm for the container loading problem with static mechanical equilibrium conditions. Int Trans Oper Res 23(1–2):215–238

    Google Scholar 

  • Ramos A, Silva E, Oliveira J (2018) A new load balance methodology for container loading problem in road transportation. Eur J Oper Res 266(3):1140–1152

    Google Scholar 

  • Ren J, Tian Y, Sawaragi T (2011) A tree search method for the container loading problem with shipment priorities. Eur J Oper Res 214:526–535

    Google Scholar 

  • Scheithauer G (1992) Algorithms for the container loading problem. In: Gaul W, Bachem A, Habenicht W, Runge W, Stahl WW (eds) Operations research proceedings. vol 1991. Springer, Berlin, Heidelberg, pp 445–452

  • Scheithauer G, Terno J (1996) The g4-heuristic for the pallet loading problem. J Oper Res Soc 47(4):511–522

    Google Scholar 

  • Shebalov S, Park Y, Klabjan D (2015) Lifting for mixed integer programs with variable upper bounds. Discrete Appl Math 186(1):226–250

    Google Scholar 

  • Sheng L, Xiuqin S, Changjian C, Hongxia Z, Dayong S, Feiyue W (2017) Heuristic algorithm for the container loading problem with multiple constraints. Comput Ind Eng 108:149–164

    Google Scholar 

  • Toffolo TAM, Esprit E, Wauters T, Vanden Berghe G (2017) A two-dimensional heuristic decomposition approach to a three-dimensional multiple container problem. Eur J Oper Res 257(2):526–538

    Google Scholar 

  • UNCTAD (2018) Report of maritime transport 2018. https://unctad.org. Online Accessed 26 Dec 2019

  • Wang N, Lim A, Zhu W (2013) A multi-round partial beam search approach for the single container loading problem with shipment priority. Int J Prod Econ 145:531–540

    Google Scholar 

  • Wäscher G, Haußner H, Schumann H (2007) An improved typology of cutting and packing problems. Eur J Oper Res 183(3):1109–1130

    Google Scholar 

  • Zhu W, Oon W, Lim A, Weng Y (2012) The six elements to block-building approaches for the single container loading problem. Appl Intell 37(3):1–15

    Google Scholar 

Download references

Acknowledgements

This work has been partially supported by the Spanish Ministry of Science, Innovation, and Universities, project RTI2018-094940-B-I00, partially financed with FEDER funds and by the Junta de Comunidades de Castilla-La Mancha, project SBPLY/17/180501/000282, partially financed with FEDER funds.

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Castilla-La Mancha, Albacete, Spain

    I. Gimenez-Palacios, M. T. Alonso & F. Parreño

  2. Department of Statistics and Operations Research, University of Valencia, Valencia, Spain

    R. Alvarez-Valdes

Authors
  1. I. Gimenez-Palacios
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. T. Alonso
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. R. Alvarez-Valdes
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. F. Parreño
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to R. Alvarez-Valdes.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gimenez-Palacios, I., Alonso, M.T., Alvarez-Valdes, R. et al. Logistic constraints in container loading problems: the impact of complete shipment conditions . TOP 29, 177–203 (2021). https://doi.org/10.1007/s11750-020-00577-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-020-00577-8

Keywords

Mathematics Subject Classification

Search

Navigation