Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2014 | OriginalPaper | Buchkapitel

1. Non-standard Packing Problems: A Modelling-Based Approach

verfasst von : Giorgio Fasano

Erschienen in: Solving Non-standard Packing Problems by Global Optimization and Heuristics

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

The general subject of packing objects, exploiting the available volume, as much as possible, has represented, for centuries, or even longer, an extremely tricky task. This issue seems trivial, until one encounters it. The question arose, for instance, when dealing with cannon ball stowage in ancient vessels. It is not surprising at all that it gained the role of the packing issue par excellence, when Hilbert announced his eighteenth problem (to date resolved by computer-assisted proof, e.g. Gray 2000). It concerned the accommodation of equal spheres, attaining the maximum density. This chapter introduces the overall subject of packing.

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
Nächstes Kapitel Tetris-like Items
Literatur
Addis, B., Locatelli, M., Schoen, F.: Efficiently packing unequal disks in a circle: a computational approach which exploits the continuous and combinatorial structure of the problem. Oper. Res. Lett. 36(1), 37–42 (2008a)CrossRefMATHMathSciNet
Addis, B., Locatelli, M., Schoen, F.: Disk packing in a square: a new global optimization approach. INFORMS J. Comput. 20(4), 516–524 (2008b)CrossRefMATHMathSciNet
Allen, S.D., Burke, E.K., Kendall, G.: A hybrid placement strategy for the three-dimensional strip packing problem. Eur. J. Oper. Res. 209(3), 219–227 (2011)CrossRefMATHMathSciNet
Allen, S.D., Burke, E.K., Mareček, J.: A space-indexed formulation of packing boxes into a larger box. Oper. Res. Lett. 40(1), 20–24 (2012)CrossRefMATHMathSciNet
Bennell, J.A., Han, W., Zhao, X., Song, X.: Construction heuristics for two-dimensional irregular shape bin packing with guillotine constraints. Eur. J. Oper. Res. 230(3), 495–504 (2013)CrossRefMathSciNet
Bennel, J.A., Lee, L.S., Potts, C.N.: A genetic algorithm for two-dimensional bin packing with due dates. Int. J. Prod. Econ. 145(2), 547–560 (2013)CrossRef
Bennell, J.A., Oliveira, J.F.: A tutorial in irregular shape packing problems. J. Oper. Res. Soc. 60(S1), S93–S105 (2009)CrossRefMATH
Birgin, E., Martinez, J., Nishihara, F.H., Ronconi, D.P.: Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization. Comput. Oper. Res. 33(12), 3535–3548 (2006)CrossRefMATHMathSciNet
Bortfeldt, A., Gehring, H.: A hybrid genetic algorithm for the container loading problem. Eur. J. Oper. Res. 131(1), 143–161 (2001)CrossRefMATH
Bortfeldt, A., Gehring, H., Mack, D.: A parallel tabu search algorithm for solving the container loading problem. Parallel Comput. 29(5), 641–662 (2003)CrossRef
Bortfeldt, A., Wäscher, G.: Container loading problems—a state-of-the-art review. FEMM working papers 120007, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management, Magdeburg (2012)
Burke, E.K., Hellier, R., Kendall, G., Whitwell, G.: A new bottom-left-fill heuristic algorithm for the 2D irregular packing problem. Oper. Res. 54(3), 587–601 (2006)CrossRefMATHMathSciNet
Burke, E.K., Guo, Q., Hellier, R., Kendall, G.: A hyper-heuristic approach to strip packing problems. In: Proceedings of the 11th International Conference on Parallel Problem Solving from Nature: Part I, pp. 465–474. Springer, Berlin (2010)
Cagan, J., Shimada, K., Yin, S.: A survey of computational approaches to three-dimensional layout problems. Comput. Aided Des. 34, 597–611 (2002)CrossRef
Castillo, I., Kampas, F.J., Pintér, J.D.: Solving circle packing problems by global optimization: numerical results and industrial applications. Eur. J. Oper. Res. 191(3), 786–802 (2008)CrossRefMATH
Chen, C.S., Lee, S.M., Shen, Q.S.: An analytical model for the container loading problem. Eur. J. Oper. Res. 80, 68–76 (1995)CrossRefMATH
Chernov, N., Stoyan, Y.G., Romanova, T.: Mathematical model and efficient algorithms for object packing problem. Comput. Geom. Theor. Appl. 43(5), 535–553 (2010)CrossRefMATHMathSciNet
Coffman, E., Garey, J.M., Johnson, D.: Approximation Algorithms for Bin Packing: A Survey. PWS Publishing Company, Boston (1997)
Dowsland, K.A., Herbert, E.A., Kendall, G., Burke, E.: Using tree search bounds to enhance a genetic algorithm approach to two rectangle packing problems. Eur. J. Oper. Res. 168(2), 390–402 (2006)CrossRefMATHMathSciNet
Dyckhoff, H., Scheithauer, G., Terno, J.: Cutting and packing. In: Dell’Amico, M., Maffioli, F., Martello, S. (eds.) Annotated Bibliographies in Combinatorial Optimization, pp. 393–412. Wiley, Chichester (1997)
Egeblad, J., Nielsen, B.K., Odgaard, A.: Fast neighborhood search for two-and three-dimensional nesting problems. Eur. J. Oper. Res. 183(3), 1249–1266 (2007)CrossRefMATHMathSciNet
Egeblad, J., Pisinger, D.: Heuristic approaches for the two- and three-dimensional knapsack packing problems. DIKU Technical-Report No. 2006-13, SSN: 0107-8283, Department of Computer Science, University of Copenhagen, Denmark (2006)
Egeblad, J., Pisinger, D.: Heuristic approaches for the two- and three-dimensional knapsack packing problem. Comput. Oper. Res. 36, 1026–1049 (2009)CrossRefMATHMathSciNet
Faroe, O., Pisinger, D., Zachariasen, M.: Guided local search for the three-dimensional bin packing problem. INFORMS J. Comput. 15(3), 267–283 (2003)CrossRefMATHMathSciNet
Fasano, G.: Satellite Optimal Layout. Application of Mathematical and Optimization Techniques. IBM Europe Institute, Garmisch-Partenkirchen, Germany (1989)
Fasano, G.: A global optimization point of view to handle non-standard objective packing problems. J. Global. Optim. 55(2), 279–299 (2013)CrossRefMATHMathSciNet
Fekete, S.P., Schepers, J.: A new exact algorithm for general orthogonal d-dimensional knapsack problems. In: Burkard, R., Woeginger, G. (eds.) Algorithms ESA ’97. Springer Lecture Notes in Computer Science, vol. 1284, pp. 144–156. Springer, Berlin (1997)
Fekete, S., Schepers, J.: A combinatorial characterization of higher-dimensional orthogonal packing. Math. Oper. Res. 29, 353–368 (2004)CrossRefMATHMathSciNet
Fekete, S., Schepers, J., van der Veen, J.C.: An exact algorithm for higher-dimensional orthogonal packing. Oper. Res. 55(3), 569–587 (2007)CrossRefMATHMathSciNet
Fischetti, M., Luzzi, I.: Mixed-integer programming models for nesting problems. J. Heuristics 15(3), 201–226 (2009)CrossRefMATH
Floudas, C.A., Akrotirianakis, I.G., Caratzoulas, S., Meyer, C.A., Kallrath, J.: Global optimization in the 21st century: advances and challenges for problems with nonlinear dynamics. Comp. Chem. Eng. 29, 1185–1202 (2005)CrossRef
Floudas, C.A., Pardalos, P.M.: A Collection of Test Problems for Constrained Global Optimization Algorithms. Springer, New York (1990)CrossRefMATH
Floudas, C.A., Pardalos, P.M., et al.: Handbook of Test Problems in Local and Global Optimization, Nonconvex Optimization and Its Applications Series 33. Kluwer Academic Publishers, Dordrecht, The Netherlands (1999)CrossRef
Floudas, C.A., Pardalos, P.M. (eds.): Encyclopedia of Optimization. Kluwer Academic Publishers, Dordrecht, The Netherlands (2001)MATH
Gehring, H., Bortfeldt, A.: A parallel genetic algorithm for solving the container loading problem. Int. Trans. Oper. Res. 9(4), 497–511 (2002)CrossRefMATHMathSciNet
Gomes, A.M., Olivera, J.F.: A 2-exchange heuristics for nesting problems. Eur. J. Oper. Res. 141, 359–570 (2002)CrossRefMATH
Gonçalves, J.F., Resende, M.G.: A parallel multi-population biased random-key genetic algorithm for a container loading problem. Comput. Oper. Res. 39(2), 179–190 (2012)CrossRefMATHMathSciNet
Gray, J.J.: The Hilbert Challenge. Oxford University Press, Oxford (2000)MATH
Hadjiconstantinou, E., Christofides, N.: An exact algorithm for general, orthogonal, two-dimensional knapsack problems. Eur. J. Oper. Res. 83(1), 39–56 (1995)CrossRefMATH
Hopper, E., Turton, B.C.: A review of the application of meta-heuristic algorithms to 2D strip packing problems. Artif. Intell. Rev. 16(4), 257–300 (2001)CrossRefMATH
Hopper, E., Turton, B.C.: An empirical study of meta-heuristics applied to 2D rectangular bin packing—part II. Studia Informatica Universalis 2(1), 93–106 (2002)
Horst, R., Pardalos, P.M. (eds.): Handbook of Global Optimization. Kluwer Academic Publishers, Dordrecht, The Netherlands (1995)MATH
Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches, 3rd edn. Springer, Berlin (1996)CrossRefMATH
Horst, R., Pardalos, P.M. (eds.): Developments in Global Optimization. Kluwer Academic Publishers, Dordrecht, The Netherlands (1997)MATH
Ibaraki, T., Imahori, S., Yagiura, M.: Hybrid metaheuristics for packing problems. In: Blum, C., Aguilera, M.J., Roli, A., Sampels, M. (eds.) Hybrid Metaheuristics: An Emerging Approach to Optimization. Studies in Computational Intelligence (SCI), vol. 114, pp. 185–219. Springer, Berlin (2008)CrossRef
Iori, M., Martello, S., Monaci, M.: Metaheuristic algorithms for the strip packing problem. In: Pardalos, P.M., Korotkikh, V. (eds.) Optimization and Industry: New Frontiers, pp. 159–179. Kluwer Academic Publishers, Dordrecht, The Netherlands (2003)CrossRef
Kallrath, J.: Mixed-integer nonlinear applications. In: Ciriani, T., Ghiozzi, S., Johnson, E.L. (eds.) Operations Research in Industry, pp. 42–76. Macmillan, London (1999)
Kallrath, J.: Modeling difficult optimization problems. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, 2nd edn, pp. 2284–2297. Springer, New York (2008)
Kampas, F.J., Pintér, J.D.: Optimization with Mathematica: Scientific, Engineering, and Economic Applications. Springer Science + Business Media, New York (forthcoming)
Kang, M.K., Jang, C.S., Yoon, K.S.: Heuristics with a new block strategy for the single and multiple container loading problems. J. Oper. Res. Soc. 61, 95–107 (2010)CrossRefMATH
Kenmochi, M., Imamichi, T., Nonobe, K., Yagiura, M., Nagamochi, H.: Exact algorithms for the two-dimensional strip packing problem with and without rotations. Eur. J. Oper. Res. 198, 73–83 (2009)CrossRefMATHMathSciNet
Li, H.L., Chang, C.T., Tsai, J.F.: Approximately global optimization for assortment problems using piecewise linearization techniques. Eur. J. Oper. Res. 140, 584–589 (2002)CrossRefMATHMathSciNet
Liberti, L., Maculan, N. (eds.): Global Optimization: From Theory to Implementation. Springer Science + Business Media, New York (2005)
Locatelli, M., Raber, U.: Packing equal circles into a square: a deterministic global optimization approach. Discrete Appl. Math. 122, 139–166 (2002)CrossRefMATHMathSciNet
Lodi, A., Martello, S., Monaci, M., Vigo, D.: Two-dimensional bin packing problems. In: Paschos, V.T. (ed.) Paradigms of Combinatorial Optimization, pp. 107–129. Wiley/ISTE, Hoboken, NJ (2010)
López-Camacho, E., Ochoa, G., Terashima-Marín, H., Burke, E.: An effective heuristic for the two-dimensional irregular bin packing problem. Ann. Oper. Res. 206(1), 241–264 (2013)CrossRefMATHMathSciNet
Mack, D., Bortfeldt, A., Gehring, H.: A parallel hybrid local search algorithm for the container loading problem. Int. Trans. Oper. Res. 11(5), 511–533 (2004)CrossRefMATH
Oliveira, J.F., Gomes, A.M., Ferreira, J.S.: TOPOS—a new constructive algorithm for nesting problems. OR Spectrum 22(2), 263–284 (2000)CrossRefMATHMathSciNet
Padberg, M.W.: Packing small boxes into a big box. Office of Naval Research, N00014-327, New York University (1999)
Pardalos, P.M., Resende, M.G. (eds.): Handbook of Applied Optimization. Oxford University Press, Oxford (2002)MATH
Pardalos, P.M., Romeijn, H.E. (eds.): Handbook of Global Optimization. Kluwer Academic Publishers, Dordrecht, The Netherlands (2002)MATH
Pintér, J.D.: Global Optimization in Action. Kluwer Academic Publishers, Dordrecht, The Netherlands (1996)CrossRefMATH
Pintér, J.D.: Software development for global optimization. In: Pardalos, P.M., Coleman, T.F. (eds.) Global Optimization: Methods and Applications, Fields Institute Communications, vol. 55, pp. 183–204. American Mathematical Society, Providence, RI (2009)
Pisinger, D., Sigurd, M.: The two-dimensional bin packing problem with variable bin sizes and costs. Discrete Optim. 2(2), 154–167 (2005)CrossRefMATHMathSciNet
Pisinger, D., Sigurd, M.: Using decomposition techniques and constraint programming for solving the two-dimensional bin packing problem. INFORMS J. Comput. 19(1), 36–51 (2007)CrossRefMATHMathSciNet
Rebennack, S., Kallrath, J., Pardalos, P.M.: Column enumeration based decomposition techniques for a class of non-convex MINLP problems. J. Global Optim. 43(2–3), 277–297 (2009)CrossRefMATHMathSciNet
Scheithauer, G., Stoyan, Y.G., Romanova, T.Y.: Mathematical modeling of interactions of primary geometric 3D objects. Cybern. Syst. Anal. 41, 332–342 (2005)CrossRefMATHMathSciNet
Stoyan, Y., Scheithauer, G., Gil, N., Romanova, T.: Φ-functions for complex 2D-objects. 4OR Q. J. Belgian French Italian Oper. Res. Soc. 2(1), 69–84 (2004)MATHMathSciNet
Teng, H., Sun, S., Liu, D., Li, Y.: Layout optimization for the objects located within a rotating vessel a three-dimensional packing problem with behavioural constraints. Comput. Oper. Res. 28(6), 521–535 (2001)CrossRefMATH
Terashima-Marín, H., Ross, P., Farías-Zárate, C.J., López-Camacho, E., Valenzuela-Rendón, M.: Generalized hyper-heuristics for solving 2D regular and irregular packing problems. Ann. Oper. Res. 179, 369–392 (2010)CrossRefMATHMathSciNet
Wang, Z., Li, K.W., Levy, J.K.: A heuristic for the container loading problem: a tertiary-tree-based dynamic space decomposition approach. Eur. J. Oper. Res. 191(1), 86–99 (2008)CrossRefMATH
Yeung, L.H., Tang, W.K.: A hybrid genetic approach for container loading in logistics industry. IEEE Trans. Ind. Electron. 52(2), 617–627 (2005)CrossRef
Zhang, D., Kang, Y., Deng, A.: A new heuristic recursive algorithm for the strip rectangular packing problem. Comput. Oper. Res. 33, 2209–2217 (2006)CrossRefMATH
Metadaten
Titel
Non-standard Packing Problems: A Modelling-Based Approach
verfasst von
Giorgio Fasano
Copyright-Jahr
2014
Buch
Solving Non-standard Packing Problems by Global Optimization and Heuristics

Print ISBN: 978-3-319-05004-1

Electronic ISBN: 978-3-319-05005-8

Copyright-Jahr: 2014

DOI
https://doi.org/10.1007/978-3-319-05005-8_1