Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Anonimisation, Impacts and Challenges into Big Data: A Case Studies Read chapter Read first chapter

2021 | OriginalPaper | Chapter

A Mixed Approach for Pallet Building Problem with Practical Constraints

Authors : Manuel Iori, Marco Locatelli, Mayron C. O. Moreira, Tiago Silveira

Published in: Enterprise Information Systems

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We study a pallet building problem that originates from a case study in a company that produces robotized systems for freight transportation and logistics. We generalize the problem by including the concept of family of items, which allows us to consider specific constraints such as visibility and contiguity. We solve the problem with an algorithm based on a two-step strategy: an Extreme Points heuristic is used to group items into horizontal layers and an exact method is invoked to stack layers one over the other to form pallets. The performance of the algorithm is assessed through extensive computational tests on real-world instances. The results show that the exact model considerably increases the solution quality, creating very compact packings with a limited computational effort.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Improving Corporate Support by Predicting Customer e-Mail Response Time: Experimental Evaluation and a Practical Use Case
next chapter A Reference Process and Domain Model for Machine Learning Based Production Fault Analysis
Literature
1.
Alonso, M.T., Alvarez-Valdes, R., Iori, M., Parreño, F.: Mathematical models for multi container loading problems with practical constraints. Comput. Ind. Eng. 127, 722–733 (2019)CrossRef
2.
Alonso, M.T., Alvarez-Valdes, R., Iori, M., Parreño, F., Tamarit, J.M.: Mathematical models for multi container loading problems. OMEGA 66, 106–117 (2017)CrossRef
3.
Alonso, M.T., Alvarez-Valdes, R., Parreño, F., Tamarit, J.M.: Algorithms for pallet building and truck loading in an interdepot transportation problem. Math. Probl. Eng. 2016, 1–11 (2016)CrossRef
4.
Alvarez-Valdes, R., Parreño, F., Tamarit, J.M.: A branch-and-cut algorithm for the pallet loading problem. Comput. Oper. Res. 32, 3007–3029 (2005)MathSciNetCrossRef
5.
Alvarez-Valdes, R., Parreño, F., Tamarit, J.M.: Reactive GRASP for the strip-packing problem. Comput. Oper. Res. 35, 1065–1083 (2008)CrossRef
6.
Bischoff, E.E., Ratcliff, M.S.W.: Issues in the development of approaches to container loading. Omega 23, 377–390 (1995)CrossRef
7.
Bortfeldt, A., Gehring, H.: A hybrid genetic algorithm for the container loading problem. Eur. J. Oper. Res. 131, 143–161 (2001)CrossRef
8.
Bortfeldt, A., Wäscher, G.: Constraints in container loading - a state-of-the-art review. Eur. J. Oper. Res. 229, 1–20 (2013)MathSciNetCrossRef
9.
Burke, E.K., Kendall, G., Whitwell, G.: A new placement heuristic for the orthogonal stock-cutting problem. Oper. Res. 52, 655–671 (2004)CrossRef
10.
Chazelle, B.: The bottomn-left bin-packing heuristic: an efficient implementation. IEEE Trans. Comput. C-32, 697–707 (1983)
11.
Crainic, T.G., Perboli, G., Tadei, R.: Extreme point-based heuristics for three-dimensional bin packing. INFORMS J. Comput. 20, 368–384 (2008)MathSciNetCrossRef
12.
Crainic, T.G., Perboli, G., Tadei, R.: Recent advances in multi-dimensional packing problems. In: New Technologies, chap. 5. IntechOpen (2012)
13.
Côté, J.F., Dell’Amico, M., Iori, M.: Combinatorial benders’ cuts for the strip packing problem. Oper. Res. 62, 643–661 (2014)MathSciNetCrossRef
14.
da Silva, E.F., Leão, A.A.S., Toledo, F.M.B., Wauters, T.: A matheuristic framework for the three-dimensional single large object placement problem with practical constraints. Comput. Oper. Res. 124, 105058 (2020)
15.
de Queiroz, T.A., Miyazawa, F.K.: Two-dimensional strip packing problem with load balancing, load bearing and multi-drop constraints. Int. J. Prod. Econ. 145, 511–530 (2013)CrossRef
16.
Delorme, M., Iori, M., Martello, S.: Bin packing and cutting stock problems: mathematical models and exact algorithms. Eur. J. Oper. Res. 255, 1–20 (2016)MathSciNetCrossRef
17.
Delorme, M., Iori, M., Martello, S.: Logic based benders decomposition for orthogonal stock cutting problems. Comput. Oper. Res. 78, 290–298 (2017)MathSciNetCrossRef
18.
Egeblad, J., Garavelli, C., Lisi, S., Pisinger, D.: Heuristics for container loading of furniture.Eur. J. Oper. Res. 200, 881–892 (2010)CrossRef
19.
Elhedhli, S., Gzara, F., Yildiz, B.: Three-dimensional bin packing and mixed-case palletization. INFORMS J. Optim. 1(4), 323–352 (2019)MathSciNetCrossRef
20.
Gilmore, P.C., Gomory, R.E.: Multistage cutting stock problems of two or more dimensions. Oper. Res. 13, 94–120 (1965)CrossRef
21.
Gzara, F., Elhedhli, S., Yildiz, B.C.: The pallet loading problem: three-dimensional bin packing with practical constraints. Eur. J. Oper. Res. 287(3), 1062–1074 (2020)MathSciNetCrossRef
22.
Haessler, R.W., Talbot, F.B.: Load planning for shipments of low density products. Eur. J. Oper. Res. 44, 289–299 (1990)CrossRef
23.
Hopper, E., Turton, B.: Application of genetic algorithms to packing problems - a review. In: Soft Computing in Engineering Design and Manufacturing, pp. 279–288 (1998)
24.
Imahori, S., Yagiura, M.: The best-fit heuristic for the rectangular strip packing problem: an efficient implementation and the worst-case approximation ratio. Comput. Oper. Res. 37, 325–333 (2010)CrossRef
25.
Iori, M., de Lima, V.L., Martello, S., Miyazawa, F.K., Monaci, M.: Two-dimensional cutting and packing: Problems and solution techniques. Eur. J. Oper. Res. (2020). (forthcoming)
26.
Iori, M., Locatelli, M., Moreira, M.C.O., Silveira, T.: Solution of a practical pallet building problem with visibility and contiguity constraints. In: International Conference on Enterprise Information Systems, vol. 1, pp. 327–338. SciTePress (2020)
27.
28.
Iori, M., Martello, S.: An annotated bibliography of combined routing and loading problems. Yugoslav J. Oper. Res. 23, 311–326 (2013)MathSciNetCrossRef
29.
Jovanovic, R., Tuba, M., Voß, S.: Fixed set search applied to the traveling salesman problem, pp. 63–77. International Workshop on Hybrid Metaheuristics (2019)
30.
31.
Jovanovic, R., Voß, S.: The fixed set search applied to the power dominating set problem. Expert Systems, p. e12559 (2020)
32.
Józefowska, J., Pawlak, G., Pesch, E., Morze, M., Kowalski, D.: Fast truck-packing of 3D boxes. Eng. Manage. Prod. Serv. 10, 29–40 (2018)
33.
Kurpel, D.V., Scarpin, C.T., Pécora Junior, J.E., Schenekemberg, C.M., Coelho, L.C.: The exact solutions of several types of container loading problems. Eur. J. Oper. Res. 284, 87–107 (2020)MathSciNetCrossRef
34.
Leung, S.C.H., Zhang, D., Sim, K.M.: A two-stage intelligent search algorithm for the two-dimensional strip packing problem. Eur. J. Oper. Res. 215, 57–69 (2011)CrossRef
35.
Lodi, A., Martello, S., Monaci, M., Vigo, D.: Two-Dimensional Bin Packing Problems, pp. 107–129. John Wiley & Sons, Ltd (2014)
36.
37.
Neli\(\beta \)en, J.: How to use structural constraints to compute an upper bound for the pallet loading problem. Eur. J. Oper. Res. 84, 662–680 (1995)
38.
Ranck Júnior, R., Yanasse, H.H., Morabito, R., Junqueira, L.: A hybrid approach for a multi-compartment container loading problem. Expert Syst. Appl. 137, 471–492 (2019)CrossRef
39.
Ribeiro, G.M., Lorena, L.A.N.: Lagrangean relaxation with clusters and column generation for the manufacturers pallet loading problem. Comput. Oper. Res. 34, 2695–2708 (2007)CrossRef
40.
Scheithauer, G.: Introduction to Cutting and Packing Optimization. Springer International Publishing (2018)
41.
Schmid, V., Doerner, K.F., Laporte, G.: Rich routing problems arising in supply chain management. Eur. J. Oper. Res. 224, 435–448 (2013)MathSciNetCrossRef
42.
Silva, E., Oliveira, J.F., Wäscher, G.: The pallet loading problem: a review of solution methods and computational experiments. Int. Trans. Oper. Res. 23, 147–172 (2016)MathSciNetCrossRef
43.
Terno, J.J., Scheithauer, G., Sommerwei\(\beta \), U., Riehme, J.: An efficient approach for the multi-pallet loading problem. J. Eur. J. Oper. Res. 123, 372–381 (2000)
44.
Tsai, D.: Modeling and analysis of three-dimensional robotic palletizing systems for mixed carton sizes. Ph.D. thesis, Iowa State University (1987)
45.
Vidal, T., Crainic, T.G., Gendreau, M., Prins, C.: Heuristics for multi-attribute vehicle routing problems: a survey and synthesis. Eur. J. Oper. Res. 231, 1–21 (2013)MathSciNetCrossRef
46.
Wäscher, G., Hau\(\beta \)ner, H., Schumann, H.: An improved typology of cutting and packing problems. Eur. J. Oper. Res. 183, 1109–1130 (2007)
47.
Wu, K.C., Ting, C.J.: A two-phase algorithm for the manufacturer’s pallet loading problem. In: IEEE International Conference on Industrial Engineering and Engineering Management, pp. 1574–1578 (2007)
Metadata
Title
A Mixed Approach for Pallet Building Problem with Practical Constraints
Authors
Manuel Iori
Marco Locatelli
Mayron C. O. Moreira
Tiago Silveira
Copyright Year
2021
Book
Enterprise Information Systems

Print ISBN: 978-3-030-75417-4

Electronic ISBN: 978-3-030-75418-1

Copyright Year: 2021

DOI
https://doi.org/10.1007/978-3-030-75418-1_7

Premium Partner

    Image Credits