nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

A Mixed Approach for Pallet Building Problem with Practical Constraints

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

Erschienen in: Enterprise Information Systems

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Improving Corporate Support by Predicting Customer e-Mail Response Time: Experimental Evaluation and a Practical Use Case

Nächstes Kapitel A Reference Process and Domain Model for Machine Learning Based Production Fault Analysis

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

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

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

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

Alvarez-Valdes, R., Parreño, F., Tamarit, J.M.: Reactive GRASP for the strip-packing problem. Comput. Oper. Res. 35, 1065–1083 (2008)CrossRef

Bischoff, E.E., Ratcliff, M.S.W.: Issues in the development of approaches to container loading. Omega 23, 377–390 (1995)CrossRef

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

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

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.

Iori, M., Martello, S.: Routing problems with loading constraints. TOP 18, 4–27 (2010)MathSciNetCrossRef

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.

Jovanovic, R., Voß, S.: Fixed set search applied to the minimum weighted vertex cover problem. In: Kotsireas, I., Pardalos, P., Parsopoulos, K.E., Souravlias, D., Tsokas, A. (eds.) SEA 2019. LNCS, vol. 11544, pp. 490–504. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34029-2_31CrossRef

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.

Martins, G.H.A., Dell, R.F.: Solving the pallet loading problem. Eur. J. Oper. Res. 184, 429–440 (2008)MathSciNetCrossRef

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)

Titel: A Mixed Approach for Pallet Building Problem with Practical Constraints
verfasst von: Manuel Iori
Marco Locatelli
Mayron C. O. Moreira
Tiago Silveira
Verlag: Springer International Publishing
Buch: Enterprise Information Systems
Print ISBN: 978-3-030-75417-4

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

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

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"