Effective Data Structure for the Multidimensional Orthogonal Bin Packing Problems

Alexander V. Chekanin; Vladislav A. Chekanin

doi:10.4028/www.scientific.net/AMR.962-965.2868

Paper Titles

An Object Detection Algorithm Based on Statistical Classification of Video Stream Pixels
p.2848

Application Research of the Pro/3 Inference Information Report and Transformer Fault Diagnosis Based on Forward Reasoning
p.2852

Denoising Method for Calibration Data of Landing Guidance Radar Based on EMD and Wavelet
p.2856

Simulations of Three Navigation Mode of Wing-Diesel Ship
p.2863

Effective Data Structure for the Multidimensional Orthogonal Bin Packing Problems
p.2868

Impact of Carrier Movement on Landing Guidance Radar Precision
p.2872

The Key Factors of Mathematical Formula Affecting the Size of a Clustered Index
p.2877

An Efficient and Robust Kernelized Possibilistic C-Means Clustering Algorithm
p.2881

Research of New Media Wireless Ad Hoc Network Broadcast Algorithm
p.2886

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 962-965Effective Data Structure for the Multidimensional...

Effective Data Structure for the Multidimensional Orthogonal Bin Packing Problems

Abstract:

The actual in industry multidimensional orthogonal packing problem is considered in the article. Solution of a large number of different practical optimization problems, including resources saving problem, optimization problems in logistics, scheduling and planning comes down to the orthogonal packing problem which is NP-hard in strong sense. One of the indicators characterizing the efficiency of packing constructing algorithm is the efficiency of the used data structure. In the article a multilevel linked data structure that increases the speed of constructing of a packing is proposed. The carried out computational experiments show the high efficiency of the new data structure. Multilevel linked data structure is applicable for multidimensional orthogonal bin packing problems any kind.

You might also be interested in these eBooks

Resources and Sustainable Development III

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 962-965)

Pages:

2868-2871

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.962-965.2868

Citation:

Cite this paper

Online since:

June 2014

Authors:

Alexander V. Chekanin, Vladislav A. Chekanin*

Keywords:

Cutting, Data Structure, Multidimensional, Multilevel Linked Data Structure, Optimization, Orthogonal, Packing Problem, Resources Allocation, Resources Saving, Waste Minimization

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

* - Corresponding Author

References

[1] M. Gary, D. Johnson: Computers Intractability: a Guide to the Theory of NP-completeness (W.H. Freeman, San Francisco 1979).

Google Scholar

[2] A. Bortfeldt, G. Wascher: Constraints in container loading – A state-of-the-art review. European Journal of Operational Research. Vol. 229: 1 (2013), pp.1-20.

DOI: 10.1016/j.ejor.2012.12.006

Google Scholar

[3] G. Wascher, H. Haubner, H. Schumann: An improved typology of cutting and packing problems. European Journal of Operational Research. Vol. 183: 3 (2007), pp.1109-1130.

DOI: 10.1016/j.ejor.2005.12.047

Google Scholar

[4] A.V. Chekanin, V.A. Chekanin: Efficient algorithms for orthogonal packing problems. Computational Mathematics and Mathematical Physics. Vol. 53: 10 (2013), pp.1457-1465.

DOI: 10.1134/s0965542513100047

Google Scholar

[5] T.G. Crainic, G. Perboli, R. Tadei: Extreme point-based heuristics for three-dimensional bin packing. INFORMS, Journal on Computing. Vol. 20: 3 (2008), pp.368-384.

DOI: 10.1287/ijoc.1070.0250

Google Scholar

[6] A.V. Chekanin, V.A. Chekanin: Improved packing representation model for the orthogonal packing problem. Applied Mechanics and Materials. Vol. 390 (2013), pp.591-595.

DOI: 10.4028/www.scientific.net/amm.390.591

Google Scholar

[7] V.A. Chekanin, A.V. Chekanin: Optimization of the solution of the orthogonal packing problem. Applied informatics (Prikladnaya informatika). Vol. 4 (2012), pp.55-62, in Russian.

Google Scholar

[8] S. Martello, D. Pisinger, D. Vigo: The three-dimensional bin packing problem. Operations Research. Vol. 48: 2 (2000), pp.256-267.

DOI: 10.1287/opre.48.2.256.12386

Google Scholar

[9] M.A. Weiss: Data Structures and Algorithm Analysis in C++ (Pearson Education 2014).

Google Scholar