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:
Using a Bin Packing Approach for Stowing Hazardous Containers into Containerships Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

9. Approximate Packing: Integer Programming Models, Valid Inequalities and Nesting

verfasst von : Igor Litvinchev, Luis Infante, Lucero Ozuna

Erschienen in: Optimized Packings with Applications

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Using a regular grid to approximate a container, packing objects is reduced to assigning objects to the nodes of the grid subject to non-overlapping constraints. The packing problem is then stated as a large scale linear 0-1 optimization problem. Different formulations for non-overlapping constraints are presented and compared. Valid inequalities are proposed to strengthening formulations. This approach is applied for packing circular and L-shaped objects. Circular object is considered in a general sense as a set of points that are all the same distance (not necessary Euclidean) from a given point. Different shapes, such as ellipses, rhombuses, rectangles, octagons, etc., are treated similarly by simply changing the definition of the norm used to define the distance. Nesting objects inside one another is also considered. Numerical results are presented to demonstrate the efficiency of the proposed approach.

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 Automatic Design of Optimal LED Street Lights
Nächstes Kapitel Exploiting Packing Components in General-Purpose Integer Programming Solvers
Literatur
1.
Baltacioglu, E., Moore, J.T., Hill, R.R.: The distributor’s three-dimensional pallet-packing problem: a human-based heuristical approach. Int. J. Oper. Res. 1, 249–266 (2006)CrossRefMATH
2.
Castillo, I., Kampas, F.J., Pinter, J.D.: Solving circle packing problems by global optimization: numerical results and industrial applications. Eur. J. Oper. Res. 191, 786–802 (2008)MathSciNetCrossRefMATH
3.
Fasano, G.: Solving Non-standard Packing Problems by Global Optimization and Heuristics. Springer-Verlag, Berlin (2014)CrossRefMATH
4.
Frazer, H.J., George, J.A.: Integrated container loading software for pulp and paper industry. Eur. J. Oper. Res. 77, 466–474 (1994)CrossRef
5.
6.
7.
Hifi, M., M’Hallah, R.: A literature review on circle and sphere packing problems: models and methodologies. Adv. Oper. Res. (2009). doi:10.​1155/​2009/​150624
8.
Lopez, C.O., Beasley, J.E.: A heuristic for the circle packing problem with a variety of containers. Eur. J. Oper. Res. 214, 512–525 (2011)MathSciNetCrossRefMATH
9.
Lopez, C.O., Beasley, J.E.: Packing unequal circles using formulation space search. Comput. Oper. Res. 40, 1276–1288 (2013)MathSciNetCrossRef
10.
Pinter, J.D., Kampas, F.J.: Nonlinear optimization in Mathematica with MathOptimizer Professional. Math. Educ. Res. 10, 1–18 (2005)
11.
Akeb, H., Hifi, M.: Solving the circular open dimension problem using separate beams and look-ahead strategies. Comput. Oper. Res. 40, 1243–1255 (2013)MathSciNetCrossRef
12.
Birgin, E.G., Gentil, J.M.: New and improved results for packing identical unitary radius circles within triangles, rectangles and strips. Comput. Oper. Res. 37, 1318–1327 (2010)MathSciNetCrossRefMATH
13.
Stoyan, Y.G., Yaskov, G.N.: Packing congruent spheres into a multi-connected polyhedral domain. Int. Trans. Oper. Res. 20, 79–99 (2013)MathSciNetCrossRefMATH
14.
Bennel, J.A., Olivera, J.F.: A tutorial in irregular shape packing problems. J. Oper. Res. Soc. 60, 93–105 (2009)CrossRef
15.
Toledo, F.M.B., Carravilla, M.A., Ribero, C., Oliveira, J.F., Gomes, A.M.: The dotted-board model: a new MIP model for nesting irregular shapes. Int. J. Prod. Econ. 145, 478–487 (2013)CrossRef
16.
Galiev, S.I., Lisafina, M.S.: Linear models for the approximate solution of the problem of packing equal circles into a given domain. Eur. J. Oper. Res. 230, 505–514 (2013)MathSciNetCrossRef
17.
Litvinchev, I., Ozuna, L.: Packing circles in a rectangular container. Paper presented at the 1st international congress on logistics and supply chain, Mexican Institute of Transportation, Queretaro, Mexico, 24–25 October 2013
18.
Litvinchev, I., Ozuna, L.: Integer programming formulations for approximate packing circles in a rectangular container. Math. Probl. Eng. (2014). Article ID 317697, doi:10.​1155/​2014/​317697
19.
Litvinchev, I., Ozuna, L.: Approximate packing circles in a rectangular container: valid inequalities and nesting. J. Appl. Res. Technol. 12, 716–723 (2014)CrossRef
20.
Litvinchev, I., Infante, L., Ozuna, L.: Approximate circle packing in a rectangular container: integer programming formulations and valid inequalities. Lect. Notes Comput. Sci. 8760, 47–61 (2014)CrossRef
21.
22.
Burkard, R., Dell’Amico, M., Martello, S.: Assignment Problems, Revised Reprint. SIAM (2012)
23.
Wolsey, L.A.: Integer Programming. Wiley, New York (1999)
24.
ILOG CPLEX, Mathematical programming optimizers. Version 12.6 (2013)
25.
Bortfeldt, A., Wäscher, G.: Constraints in container loading—a state-of-the-art review. Eur. J. Oper. Res. 229, 1–20 (2013)CrossRef
26.
Wang, W., Wang, H., Dai, G., Wang, H.: Visualization of large hierarchical data by circle packing. CHI ’06 Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, April 22–27, Montreal, Canada, pp. 517–520 (2006)
27.
George, J.A.: Multiple container packing: a case study of pipe packing. J. Oper. Res. Soc. 47, 1098–1109 (1996)CrossRefMATH
28.
29.
Litvinchev, I., Infante, L., Ozuna, L.: LP-based heuristic for packing circular-like objects in a rectangular container. Math. Probl. Eng. (to appear)
30.
Litvinchev, I., Tsurkov, V.: Aggregation in Large Scale Optimization. Kluwer, Boston (2003)CrossRefMATH
31.
Burke, E.K., Hellier, R.S., Kendall, G., Whitwell, G.: Irregular packing using the line and arc no-fit polygon. Oper. Res. 58, 948–970 (2010)CrossRefMATH
32.
Litvinchev, I., Infante, L., Ozuna, L.: Packing circular-like objects in a rectangular container. J. Comput. Syst. Sci. Int. 54, 259--267 (2015)
Metadaten
Titel
Approximate Packing: Integer Programming Models, Valid Inequalities and Nesting
verfasst von
Igor Litvinchev
Luis Infante
Lucero Ozuna
Copyright-Jahr
2015
Buch
Optimized Packings with Applications

Print ISBN: 978-3-319-18898-0

Electronic ISBN: 978-3-319-18899-7

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-18899-7_9

Premium Partner

    Bildnachweise