Geodesic
Efficient algorithms for orthogonal packing problems
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 53 (2013) no. 10, pp. 1639-1648 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{ZVMMF_2013_53_10_a4,
     author = {A. V. Chekanin and V. A. Chekanin},
     title = {Efficient algorithms for orthogonal packing problems},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1639--1648},
     year = {2013},
     volume = {53},
     number = {10},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2013_53_10_a4/}
}
TY  - JOUR
AU  - A. V. Chekanin
AU  - V. A. Chekanin
TI  - Efficient algorithms for orthogonal packing problems
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2013
SP  - 1639
EP  - 1648
VL  - 53
IS  - 10
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2013_53_10_a4/
LA  - ru
ID  - ZVMMF_2013_53_10_a4
ER  - 
%0 Journal Article
%A A. V. Chekanin
%A V. A. Chekanin
%T Efficient algorithms for orthogonal packing problems
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2013
%P 1639-1648
%V 53
%N 10
%U http://geodesic.mathdoc.fr/item/ZVMMF_2013_53_10_a4/
%G ru
%F ZVMMF_2013_53_10_a4
A. V. Chekanin; V. A. Chekanin. Efficient algorithms for orthogonal packing problems. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 53 (2013) no. 10, pp. 1639-1648. http://geodesic.mathdoc.fr/item/ZVMMF_2013_53_10_a4/

[1] Gary M., Johnson D., Computers intractability: a guide to the theory of NP-completeness, W. H. Freeman, San Francisco, 1979 | MR

[2] Emelyanov V. V., Kureichik V. V., Kureichik V. M., Teoriya i praktika evolyutsionnogo modelirovaniya, Fizmatlit, M., 2003

[3] Fekete S. P., Schepers J., “A combinatorial characterization of higher-dimensional orthogonal packing”, Math. Operat. Research, 29:2 (2004), 353–368 | DOI | MR | Zbl

[4] Chekanin V. A., Kovshov E. E., “Modelirovanie i optimizatsiya tekhnologicheskikh operatsii v promyshlennom proizvodstve na osnove evolyutsionnykh algoritmov”, Tekhnologiya mashinostr., 2010, no. 3, 53–57

[5] Norenkov I. P., “Evristiki i ikh kombinatsii v geneticheskikh metodakh diskretnoi optimizatsii”, Informatsionnye tekhnologii, 1999, no. 1, 2–7

[6] Valiakhmetova Yu. I., Filippova A. S., “Multimetodnyi geneticheskii algoritm dlya resheniya zadach ortogonalnoi upakovki”, Informatsionnye tekhnologii, 2007, no. 12, 50–56

[7] Valeeva A. F., “Primenenie metaevristiki muravinoi kolonii k zadacham dvumernoi upakovki”, Informatsionnye tekhnologii, 2005, no. 10, 36–43

[8] Lodi A., Martello S., Monaci M., “Two-dimensional packing problems: A survey”, Europ. J. Operat. Research, 141:2 (2002), 241–252 | DOI | MR | Zbl

[9] Chekanin B. A., Kovshov E. E., Khue N. N., “Povyshenie effektivnosti evolyutsionnykh algoritmov pri reshenii optimizatsionnykh zadach upakovki ob'ektov”, Sistemy upravleniya i informatsionnye tekhnologii, 2009, no. 3, 63–67

[10] Filippova A. S., “Modelirovanie evolyutsionnykh algoritmov resheniya zadach pryamougolnoi upakovki na baze tekhnologii blochnykh struktur”, Informatsionnye tekhnologii, 2006, no. 6, Prilozhenie | MR

[11] Chekanin V. A., “Effektivnoe reshenie zadachi dvukhmernoi konteinernoi upakovki pryamougolnykh ob'ektov”, Vestn. kompyuternykh i informatsionnykh tekhnologii, 2011, no. 6, 35–39

[12] Fekete S. P., Schepers J., “An Exact Algorithm for Higher-Dimensional Orthogonal Packing”, Operat. Research., 55:3 (2007), 569–587 | DOI | MR | Zbl

[13] Chekanin V. A., “Sravnitelnyi analiz evristicheskikh algoritmov dlya resheniya zadachi trekhmernoi upakovki ob'ektov”, Prikl. informatika i matem. modelirovanie, Mezhvuzovskii sbornik nauchnykh trudov, MGUP, M., 2009, 179–188

[14] Martello S., Pisinger D., Vigo D., “The three-dimensional bin packing problem”, Operat. Research., 48:2 (2000), 256–267 | DOI | MR | Zbl

[15] Faroe O., Pisinger D., Zacharjasen M., “Guided local search for the three-dimensional bin packing problem”, INFORMS, J. Comput., 15:3 (2003), 267–283 | DOI | MR | Zbl

[16] Crainic T. G., Perboli G., Tadei R., “Extreme point-based heuristics for three-dimensional bin packing”, INFORMS, J. Comput., 20:3 (2008), 368–384 | DOI | MR | Zbl

[17] Lodi A., Martello S., Vigo D., “Heuristic algorithms for the three-dimensional bin packing problem”, Europ. J. Operat. Research., 141:2 (2002), 410–420 | DOI | MR | Zbl

[18] Boschetti M. A., “New lower bounds for the finite three-dimensional bin packing problem”, Discrete Appl. Math., 140 (2004), 241–258 | DOI | MR | Zbl

[19] Biblioteka OR-library naborov ob'ektov iz zadach Fekete i Schepers, (data obrascheniya: 23 marta 2013) http://people.brunel.ac.uk/m̃astjjb/jeb/info.html

[20] Fekete S. P., Schepers J., “New class of lower bounds for bin packing problems”, Integer Program. Comput. Optimizat., IPCO 98, Lecture Notes in Computer Science, 1412, eds. R. E. Bixby, E. A. Boyd, R. Z. Rios-Mercado, Springer, Berlin, 1998, 257–270 | DOI | MR | Zbl