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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Journal of Combinatorial Optimization
Erschienen in: Journal of Combinatorial Optimization 2/2016

01.08.2016

A hybrid algorithm based on variable neighbourhood for the strip packing problem

verfasst von: Defu Zhang, Yuxin Che, Furong Ye, Yain-Whar Si, Stephen C. H. Leung

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2016

Einloggen

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

search-config
loading …

Abstract

This paper addresses the strip packing problem, which has a wide range of real-world applications. Our proposed algorithm is a hybrid metaheuristic that combines an improved heuristic algorithm with a variable neighbourhood search. Different neighbourhoods are constructed based on the concept of block patterns. The proposed algorithm has three interesting features. First, a least-waste strategy is used to improve the constructive heuristics. Second, a better sorting sequence is selected to generate an initial solution. Finally, different neighbourhoods are constructed based on block patterns. The computational results from a diverse set of problem instances show that the proposed algorithm performs better than algorithms reported in the literature for most of the problem sets compared.
Vorheriger Artikel Tabu search for the real-world carpooling problem
Nächster Artikel Solving the maximum vertex weight clique problem via binary quadratic programming

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 "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

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
Literatur
Alvarez-Valdes R, Parreo F, Tamarit JM (2008) Reactive GRASP for the strip-packing problem. Comput Oper Res 35:1065–1083CrossRefMATH
Belov G, Scheithauer G, Mukhacheva EA (2008) One-dimensional heuristics adapted for two-dimensional rectangular strip packing. J Oper Res Soc 59:823–832CrossRefMATH
Beltran JD, Calderon JE, Cabrera RJ, Moreno Perez JA, Moreno-Vega JM (2004) GRASP/VNS hybrid for the strip packing problem. In: Proceedings of the first international workshop on hybrid metaheuristics (HM 2004), Valencia, Spain, pp. 22–23
Berkey JO, Wang PY (1987) Two-dimensional finite bin packing algorithms. J Oper Res Soc 38:423–429CrossRefMATH
Bortfeldt A (2006) A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces. Eur J Oper Res 172(3):814–837MathSciNetCrossRefMATH
Bortfeldt A, Gehring H (2006) New large benchmark instances for the two-dimensional strip packing problem with rectangular pieces. In: Proceedings of the 39th annual hawaii international conference on system sciences (HICSS’06) vol 2, p. 30b
Burke EK, Kendall G, Whitwell G (2004) A new placement heuristic for the orthogonal stock-cutting problem. Oper Res 52(4):655–671CrossRefMATH
Burke EK, Kendall G, Whitwell G (2009) A simulated annealing enhancement of the best-fit heuristic for the orthogonal stock cutting problem. INFORMS J Comput 21(3):505–516CrossRefMATH
Burke EK, Hyde MR, Kendall G, Woodward JR (2010) A genetic programming hyper-heuristic approach for evolving 2-D strip packing heuristics. IEEE Trans Evol Comput 14(6):942–958CrossRef
Chen B, Wang Y, Yang S (2015) A hybrid demon algorithm for the two- dimensional orthogonal strip packing problem. Math Prob Eng. Article ID 541931. doi:10.​1155/​2015/​541931
Christofides N, Whitlock C (1997) An algorithm for two-dimensional cutting problems. Oper Res 25:30–44CrossRefMATH
Cui YD, Yang YL, Cheng X, Song PH (2008) A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem. Comput Oper Res 35(4):1281–1291CrossRefMATH
Derrac J, García S, Molina D, Herrera F (2011) A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm Evol Comput 1(1):3–18CrossRef
Dowsland KA, Herbert EA, Kendall G, Burke EK (2006) Using tree search bounds to enhance a genetic algorithm approach to two rectangle packing problems. Eur J Oper Res 168:390–402MathSciNetCrossRefMATH
Gonçalves JF, Resende MGC (2011) A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem. J Comb Optim 22(2):180–201MathSciNetCrossRef
He K, Jin Y, Huang WQ (2013) Heuristic for two-dimensional strip packing problem with 90 rotations. Expert Syst Appl 40:5542–5550CrossRef
He K, Ji P, Li C (2015) Dynamic reduction heuristics for the rectangle packing area minimization problem. Eur J Oper Res 241:674–685MathSciNetCrossRef
Hopper E, Turton BCH (2001) An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem. Eur J Oper Res 128:34–57CrossRefMATH
Jefferson LM, da S, Eduardo CX, Flávio KM (2014) Two-dimensional strip packing with unloading constraints. Discret Appl Math 164(2):512–521MathSciNetMATH
Leung SCH, Zhang D, Sim KM (2011) A two-stage intelligent search algorithm for the two-dimensional strip packing problem. Eur J Oper Res 215(1):57–69CrossRef
Leung SCH, Zhang D (2011) A fast layer-based heuristic for non-guillotine strip packing. Expert Syst Appl 38(10):13032–13042MathSciNetCrossRef
Martello S, Vigo D (1998) Exact solution of the two-dimensional finite bin packing problem. Manag Sci 44:388–399CrossRefMATH
Mitsutoshi K, Takashi I, Koji N, Mutsunori Y, Hiroshi N (2009) Exact algorithms for the two-dimensional strip packing problem with and without rotations. Eur J Oper Res 198:73–83MathSciNetCrossRefMATH
Pinto E, Oliveira JF (2005) Algorithm based on graphs for the non-guillotinable two-dimensional packing problem. Second ESICUP Meeting, Southampton
Riff MC, Bonnaire X, Neveu B (2009) A revision of recent approaches for two-dimensional strip-packing problems. Eng Appl Artif Intell 22(4–5):823–827CrossRef
Valenzuela CL, Wang PY (2001) Heuristics for large strip packing problems with guillotine patterns: an empirical study. In: Proceedings of the 4th metaheuristics international conference. University of Porto, Portugal, pp. 417–421
Wang Y, Chen L (2015) Two-dimensional residual-space-maximized packing. Expert Syst Appl 42:3297–3305CrossRef
Wascher G, Hausner H, Schumann H (2007) An improved typology of cutting and packing problems. Eur J Oper Res 183(3):1109–1130CrossRefMATH
Wei L, Oon WC, Zhu W, Lim A (2011) A skyline heuristic for the 2D rectangular packing and strip packing problems. Eur J Oper Res 215(2):337–346MathSciNetMATH
Wei L, Tian T, Zhu W, Lim A (2014) A block-based layer building approach for the 2D guillotine strip packing problem. Eur J Oper Res 239(1):58–69MathSciNetCrossRefMATH
Yang S, Han S, Ye W (2013) A simple randomized algorithm for two-dimensional strip packing. Comput Oper Res 40(1):1–8CrossRef
Zhang D, Wei L, Leung SCH, Chen Q (2013) A binary search heuristic algorithm based on randomized local search for the rectangular strip-packing problem. INFORMS J Comput 25(2):332–345CrossRef
Metadaten
Titel
A hybrid algorithm based on variable neighbourhood for the strip packing problem
verfasst von
Defu Zhang
Yuxin Che
Furong Ye
Yain-Whar Si
Stephen C. H. Leung
Publikationsdatum
01.08.2016
Verlag
Springer US
Erschienen in
Journal of Combinatorial Optimization / Ausgabe 2/2016
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-016-0036-6

Weitere Artikel der Ausgabe 2/2016

Journal of Combinatorial Optimization 2/2016 Zur Ausgabe

OriginalPaper

The expected values of Hosoya index and Merrifield–Simmons index in a random polyphenylene chain

OriginalPaper

An improved bound on 2-distance coloring plane graphs with girth 5

OriginalPaper

A quasi-human algorithm for the two dimensional rectangular strip packing problem: in memory of Prof. Wenqi Huang

Guest Editorial

Introduction: Special issue dedicated to the memory of professor Wenqi Huang

OriginalPaper

Multi-neighborhood based path relinking for two-sided assembly line balancing problem

OriginalPaper

Multi-neighborhood based iterated tabu search for routing and wavelength assignment problem

Premium Partner

    Bildnachweise