This article is cited in 11 papers

Efficient algorithms for orthogonal packing problems

A. V. Chekanin, V. A. Chekanin

Moscow State University of Technology “STANKIN”, Vadkovskii per. 1, Moscow, 127994, Russia

Abstract: The NP complete problem of the orthogonal packing of objects of arbitrary dimension is considered in the general form. A new model for representing objects in containers is proposed that ensures the fast design of an orthogonal packing. New heuristics for the placement of orthogonal packing are proposed. A single-pass heuristic algorithm and a multimethod genetic algorithm are developed that optimize an orthogonal packing solution by increasing the packing density. Numerical experiments for two- and three-dimensional orthogonal packing problems are performed.

Key words: packing problem, orthogonal packing problem, distribution of resources, object representation model, decoder, heuristic, genetic algorithm, evolutionary algorithm, multimethod genetic algorithm, numerical experiment.

UDC: 519.247

Received: 21.06.2012
Revised: 26.03.2013

DOI: 10.7868/S0044466913100049

 English version: Computational Mathematics and Mathematical Physics, 2013, 53:10, 1457–1465

Bibliographic databases:

• 
• 
• 
• 
•