Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/15300

Solving the two-dimensional bin packing problem with a probabilistic multi-start heuristic
Baumgartner, Lukas; Schmid, Verena; Blum, Christian
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
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.
Peer Reviewed
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
Two-dimensional bin packing
Heuristic algorithms
Heurística
Problema de bin packing
info:eu-repo/semantics/publishedVersion
Artículo
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Blum, Christian; Hemmelmayr, Vera C.; Hernández Pibernat, Hugo; Schmid, Verena
Hemmelmayr, Vera C.; Schmid, Verena; Blum, Christian
Hernández Pibernat, Hugo; Baumgartner, Tobias; Blesa Aguilera, Maria Josep; Blum, Christian; Kröller, Alexander; Fekete, Sandor P.