One of the main issues in addressing three-dimensional packing problems is finding an efficient and accurate definition of the points at which to place the items inside the bins, because the performance of exact and heuristic solution methods is actually strongly influenced by the choice of a placement rule. We introduce the extreme point concept and present a new extreme point-based rule for packing items inside a three-dimensional container. The extreme point rule is independent from the particular packing problem addressed and can handle additional constraints, such as fixing the position of the items. The new extreme point rule is also used to derive new constructive heuristics for the three-dimensional bin-packing problem. Extensive computational results show the effectiveness of the new heuristics compared to state-of-the-art results. Moreover, the same heuristics, when applied to the two-dimensional bin-packing problem, outperform those specifically designed for the problem.

Extreme-Point-based Heuristics for the Three-Dimensional Bin Packing problem / CRAINIC T., G; Perboli, Guido; Tadei, Roberto. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - STAMPA. - 20:3(2008), pp. 368-384. [10.1287/ijoc.1070.0250]

Extreme-Point-based Heuristics for the Three-Dimensional Bin Packing problem

PERBOLI, Guido;TADEI, Roberto
2008

Abstract

One of the main issues in addressing three-dimensional packing problems is finding an efficient and accurate definition of the points at which to place the items inside the bins, because the performance of exact and heuristic solution methods is actually strongly influenced by the choice of a placement rule. We introduce the extreme point concept and present a new extreme point-based rule for packing items inside a three-dimensional container. The extreme point rule is independent from the particular packing problem addressed and can handle additional constraints, such as fixing the position of the items. The new extreme point rule is also used to derive new constructive heuristics for the three-dimensional bin-packing problem. Extensive computational results show the effectiveness of the new heuristics compared to state-of-the-art results. Moreover, the same heuristics, when applied to the two-dimensional bin-packing problem, outperform those specifically designed for the problem.
File in questo prodotto:
File Dimensione Formato  
extr-points-crainic-perboli-tadei-final.pdf

accesso aperto

Tipologia: 1. Preprint / submitted version [pre- review]
Licenza: PUBBLICO - Tutti i diritti riservati
Dimensione 216.76 kB
Formato Adobe PDF
216.76 kB Adobe PDF Visualizza/Apri
2008-joc-extr-points-crainic-perboli-tadei-final.pdf

non disponibili

Tipologia: 2. Post-print / Author's Accepted Manuscript
Licenza: Non Pubblico - Accesso privato/ristretto
Dimensione 492.38 kB
Formato Adobe PDF
492.38 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
versione_finale.zip

non disponibili

Tipologia: Altro materiale allegato
Licenza: Non Pubblico - Accesso privato/ristretto
Dimensione 1.83 MB
Formato Unknown
1.83 MB Unknown   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

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/11583/1512183
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo