Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 6373))
Included in the following conference series:
1755Accesses
Abstract
This paper deals with the so-called variable sized bin packing problem, which is a generalization of the one-dimensional bin packing problem in which a set of items with given weights have to be packed into a minimum-cost set of bins of variable sizes and costs. First we propose a heuristic and a beam search approach. Both algorithms are strongly based on dynamic programming procedures and lower bounding techniques. Second, we propose a variable neighborhood search approach where some neighborhoods are also based on dynamic programming. The best results are obtained by using the solutions provided by the proposed heuristic as starting solutions for variable neighborhood search. The results show that this algorithm is very competitive with current state-of-the-art approaches.
This work was supported by the binational grantAcciones Integradas ES16-2009 (Austria) and MEC HA2008-0005 (Spain), and by grant TIN2007-66523 (FORMALISM) of the Spanish government. In addition, Christian Blum acknowledges support from theRamón y Cajal program of the Spanish Government of which he is a research fellow, and Hugo Hernández acknowledges support from the Catalan Government through anFI grant.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alves, C., Valério de Carvalho, J.M.: Accelerating column generation for variable sized bin packing problems. European Journal of Operational Research 183, 1333–1352 (2007)
Belov, G., Scheithauer, G.: A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths. European Journal of Operational Research 141, 274–294 (2002)
Chu, C., La, R.: Variable-sized bin packing: tight absolute worst-case performance ratios for four approximation algorithms. SIAM Journal on Computing 30, 2069–2083 (2001)
Friesen, D.K., Langston, M.A.: Variable sized bin packing. SIAM Journal on Computing 15, 222–230 (1986)
Hansen, P., Mladenović, N.: Variable neighborhood search: Principles and applications. European Journal of Operational Research 130(3), 449–467 (2001)
Haouari, M., Serairi, M.: Heuristics for the variable sized bin-packing problem. Computers & Operations Research 36(10), 2877–2884 (2009)
Haouari, M., Serairi, M.: Relaxations and exact solution of the variable sized bin packing problem. Computational Optimization and Applications (2009) (in press)
Kang, J., Park, J.: Algorithms for the variable sized bin packing problem. European Journal of Operational Research 147, 365–372 (2003)
Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack problems. Springer, Berlin (2004)
Mladenović, N., Hansen, P.: Variable neighborhood search. Computers & Operations Research 24(11), 1097–1100 (1997)
Monaci, M.: Algorithms for packing and scheduling problems. Ph.D. thesis, University of Bologna (2002)
Ow, P.S., Morton, T.E.: Filtered beam search in scheduling. International Journal of Production Research 26, 297–307 (1988)
Author information
Authors and Affiliations
ALBCOM Research Group, Universitat Politècnica de Catalunya, Barcelona, Spain
Christian Blum & Hugo Hernández
Department of Business Administration, Universität Wien, Vienna, Austria
Vera Hemmelmayr & Verena Schmid
- Christian Blum
You can also search for this author inPubMed Google Scholar
- Vera Hemmelmayr
You can also search for this author inPubMed Google Scholar
- Hugo Hernández
You can also search for this author inPubMed Google Scholar
- Verena Schmid
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
Universitat Politècnica de Catalunya, Omega 213 Campus Nord Jordi Girona 1-3, 08034, Barcelona, Spain
María J. Blesa
ALBCOM Research Group, Universitat Politècnica de Catalunya, Omega 112, Campus Nord, Jordi Girona 1-3, 08034, Barcelona, Spain
Christian Blum
Institute of Computer Graphics and Algorithms, Vienna University of Technology, Favoritenstraße 9–11/1861, 1040, Vienna, Austria
Günther Raidl
Università di Bologna, Sede di Cesena, Via Venezia 52, 47521, Cesena, Italy
Andrea Roli
Université Libre de Bruxelles, IRIDIA CP 194/6, Avenue Franklin D. Roosevelt 50, 1050, Bruxelles, Belgium
Michael Sampels
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Blum, C., Hemmelmayr, V., Hernández, H., Schmid, V. (2010). Hybrid Algorithms for the Variable Sized Bin Packing Problem. In: Blesa, M.J., Blum, C., Raidl, G., Roli, A., Sampels, M. (eds) Hybrid Metaheuristics. HM 2010. Lecture Notes in Computer Science, vol 6373. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-16054-7_2
Download citation
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-642-16053-0
Online ISBN:978-3-642-16054-7
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative