A column generation-based heuristic for the three-dimensional bin packing problem with rotation
| Autor: | Batoul Mahvash, Satyaveer Singh Chauhan, Anjali Awasthi |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Marketing
0209 industrial biotechnology Mathematical optimization 021103 operations research Heuristic Bin packing problem Strategy and Management 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research Atomic packing factor Management Information Systems 020901 industrial engineering & automation Orientation (geometry) Column generation Extreme point Reduced cost Rotation (mathematics) Mathematics |
| Zdroj: | Journal of the Operational Research Society. 69:78-90 |
| ISSN: | 1476-9360 0160-5682 |
| DOI: | 10.1057/s41274-017-0186-7 |
| Popis: | This paper addresses a three-dimensional bin packing problem (3D-BPP) with rotation. The aim is finding the best way of packing 3D items into bins to increase the packing factor with the purpose of minimizing the number of bins. No restrictions apply to the orientation of the items, in which case items can be rotated both vertically and horizontally. 3D-BPP is solved by using a column generation (CG) technique-based heuristic. To generate new columns, fast CG is carried out by applying a heuristic pricing method, in which items with most negative reduced cost are sequentially positioned into bins based on an extreme point concept. The CG technique outperforms the best significant techniques in the literature in terms of solution quality. We also provide the new lower bounds for 3D-BPP with no rotation using CG technique. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink