The 2-constraint bin packing problem consists in packing a given number of items, each one characterised by two different but not related dimensions, into the minimum number of bins in such a way to do not exceed the capacity of the bins in either dimension. The development of the heuristics for this problem is challenged by the need of a proper definition of the criterion for evaluating the feasibility of the two capacity constraints on the two different dimensions. In this paper, we propose a computational evaluation of several criteria, and two simple but effective algorithms – a greedy and neighbourhood search algorithms – for solving the 2-constraint bin packing problem. An extensive computational analysis supports our main claim.

Simple but effective heuristics for the 2-Constraint Bin Packing Problem

ARINGHIERI, ROBERTO;DUMA, DAVIDE;GROSSO, Andrea Cesare;HOSTEINS, Pierre
2018

Abstract

The 2-constraint bin packing problem consists in packing a given number of items, each one characterised by two different but not related dimensions, into the minimum number of bins in such a way to do not exceed the capacity of the bins in either dimension. The development of the heuristics for this problem is challenged by the need of a proper definition of the criterion for evaluating the feasibility of the two capacity constraints on the two different dimensions. In this paper, we propose a computational evaluation of several criteria, and two simple but effective algorithms – a greedy and neighbourhood search algorithms – for solving the 2-constraint bin packing problem. An extensive computational analysis supports our main claim.
24
3
345
357
http://link.springer.com/article/10.1007%2Fs10732-017-9326-0
Aringhieri, Roberto; Duma, Davide; Grosso, Andrea; Hosteins, Pierre
File in questo prodotto:
File Dimensione Formato  
2017-2CBP-online.pdf

Accesso riservato

Descrizione: PDF editoriale
Tipo di file: PDF EDITORIALE
Dimensione 442.17 kB
Formato Adobe PDF
442.17 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
2017-2CBP-postprint.pdf

Accesso aperto con embargo fino al 16/03/2018

Descrizione: POST PRINT
Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 528.88 kB
Formato Adobe PDF
528.88 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2318/1627345
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 5
social impact