Solving the two-dimensional bin packing problem with a probabilistic multi-start heuristic

Home | About RECERCAT | Contact

Català | Castellano

All of RECERCAT

By Communities &
Collections By Defense Date By Authors By Titles By Subject

This Collection

By Defense Date By Authors By Titles By Subject

Statistics

View Statistics All RECERCAT

My RECERCAT

Other repositories directory

RECERCAT Home > Universitat Politècnica de Catalunya > Documents de recerca > View document

To access the full text documents, please follow this link: http://hdl.handle.net/2117/15300

dc.contributor	Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics
dc.contributor	Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
dc.contributor.author	Baumgartner, Lukas
dc.contributor.author	Schmid, Verena
dc.contributor.author	Blum, Christian
dc.date	2011
dc.identifier.citation	Baumgartner, L.; Schmid, V.; Blum, C. Solving the two-dimensional bin packing problem with a probabilistic multi-start heuristic. "Lecture notes in computer science", 2011, vol. 6683, p. 76-90.
dc.identifier.citation	0302-9743
dc.identifier.citation	10.1007/978-3-642-25566-3_6
dc.identifier.uri	http://hdl.handle.net/2117/15300
dc.language.iso	eng
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
dc.subject	Two-dimensional bin packing
dc.subject	Heuristic algorithms
dc.subject	Heurística
dc.subject	Problema de bin packing
dc.title	Solving the two-dimensional bin packing problem with a probabilistic multi-start heuristic
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/article
dc.description.abstract	The two-dimensional bin packing problem (2BP) consists in packing a set of rectangular items into rectangular, equally-sized bins. The problem is NP-hard and has a multitude of real world applications. We consider the case where the items are oriented and guillotine cutting is free. In this paper we first present a review of well-know heuristics for the 2BP and then propose a new ILP model for the problem. Moreover, we develop a multi-start algorithm based on a probabilistic version of the LGFi heuristic from the literature. Results are compared to other well-known heuristics, using data sets provided in the literature. The obtained experimental results show that the proposed algorithm returns excellent solutions. With an average percentage deviation of 1.8% from the best know lower bounds it outperformes the other algorithms by 1.1% − 5.7%. Also for 3 of the 500 instances we tested a new upper bound was found.
dc.description.abstract	Peer Reviewed

Show simple item record

All of RECERCAT

This Collection

Statistics

My RECERCAT

Related documents

Other documents of the same author