Numerical optimization method for packing regular convex polygons

Sh. I. Galiev   ; M. S. Lisafina

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 56 (2016) no. 8, pp. 1416-1427

Résumé

An algorithm is presented for the approximate solution of the problem of packing regular convex polygons in a given closed bounded domain $G$ so as to maximize the total area of the packed figures. On $G$ a grid is constructed whose nodes generate a finite set $W$ on $G$, and the centers of the figures to be packed can be placed only at some points of $W$. The problem of packing these figures with centers in $W$ is reduced to a $0$–$1$ linear programming problem. A two-stage algorithm for solving the resulting problems is proposed. The algorithm finds packings of the indicated figures in an arbitrary closed bounded domain on the plane. Numerical results are presented that demonstrate the effectiveness of the method.

Bibliographie

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

[2] CoQman E. G., Garey M. R., Johnson D. S., “Approximation algorithms for bin packing: a survey”, Approximation Algorithms, ed. Hochbaum D., PWS Publishing Company, 1997

[3] Mukhacheva E. A., Mukhacheva A. S., “L. V. Kantorovich i zadachi raskroya-upakovki: novye podkhody dlya resheniya kombinatornykh zadach lineinogo raskroya i pryamougolnoi upakovki”, Zapiski nauch. sem. POMI, 312, 2004, 239–255

[4] Gilmore P. C., Gomery R. E., “A linear approach to the cutting-stock problem”, Operations Research, 9 (1961), 849–859 | DOI | MR | Zbl

[5] Carvalho J., “Lp models for bin packing and cutting stock problems”, European J. Operat. Research, 141 (2002), 253–273 | DOI | MR | Zbl

[6] Casazza M., Ceselli A., “Mathematical programming algorithms for bin packing problems with item fragmentation”, Computers Operations Research, 46 (2014), 1–11 | DOI | MR

[7] Bortfeldt A., “A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces”, Eur. J. Oper. Research, 172 (2006), 814–837 | DOI | MR | Zbl

[8] Bortfeldt A., Hermann G., “A Parallel genetic algorithm for solving the container loading troblem”, Internat. Trans. in Operat. Research, 9:4 (2002), 397 | MR

[9] Mukhacheva F. S., Chiglintsev A. V., Smagin M. A., Mukhacheva E. A., “Zadachi dvumernoi upakovki: razvitie geneticheskikh algoritmov na baze smeshannykh protsedur lokalnogo poiska optimalnogo resheniya”, Prilozhenie k zhurnalu “Informatsionnye tekhnologii. Mashinostroenie”, 2001, no. 10

[10] Burke E. K., Kendall G., Whitwell G., “A new placement heuristic for the orthogonal stock-cutting problem”, Operations Research, 52:4 (2004), 655–671 | DOI | Zbl

[11] Huang W., Chen D., “An efficient heuristic algorithm for rectangle-packing problem”, Simulation Modelling Practice and Theory, 15 (2007), 1356–1365 | DOI

[12] Huang W., Chen D., Xu R., “A new heuristic algorithm for rectangle packing”, Computers Operat. Research, 34 (2007), 3270–3280 | DOI | MR | Zbl

[13] Cassioli A., Locatelli M., “A heuristic approach for packing identical rectangles in convex regions”, Computers Operat. Research, 38 (2011), 1342–1350 | DOI | MR | Zbl

[14] Poshyanonda P., Bahrami A., Dagli C. H., “Two dimensional nesting problem: artificial neural network and optimization approach Neural Networks”, International Joint Conference, 4:4 (1992), 572–577

[15] Zhuk C. H., “Priblizhennye algoritmy upakovki pryamougolnikov v neskolko polos”, Diskretnaya matem., 18:1 (2006), 91–105 | DOI | Zbl

[16] Kozyurin N. N., Pospelov A. I., “Veroyatnostnyi analiz razlichnykh shelfovykh algoritmov upakovki pryamougolnikov v polosu”, Sb. trudov ISP RAN, Matem. metody i algoritmy, 12, 2006, 17–26 | Zbl

[17] Stoyan Y., Scheithauer G., Gil N., Romanova T., “$\Phi$-functions for complex $\mathrm{2D}$-objects”, 40R: Quarterly J. Belgian, French and Italian Operations Research Soc., 2 (2004), 69–84 | MR | Zbl

[18] Chernov N., Stoyan Yu., Romanova T., “Mathematical model and efficient algorithms for object packing problem”, Computational Geometry: Theory and Application, 43 (2010), 535–553 | DOI | MR | Zbl

[19] Fowler R. J., Paterson M. S., Tanimoto S. L., “Optirnal packing and covering in the plane are NP-complete”, Information Processing Letters, 12:3 (1981), 133–137 | DOI | MR | Zbl

[20] Leung T., Tarn C. S., Young G., Chin F., “Packing squares into square”, J. Parallel and Distributed Computing, 10:3 (1990), 271–275 | DOI | MR

[21] Kuzyurin N. N., “O slozhnosti postroeniya asimptoticheski optimalnykh pokrytii i upakovok”, Dokl. AN, 363:1 (1998), 11–13 | MR | Zbl

[22] Galiev Sh. I., Lisafina M. S., “Packing regular polygons into a bounded domain”, Abstract of V International Conference on Optimization Methods and Applications (Petrovac, Montenegro, September 28–October 4, 2014), 70–71

[23] Litvinichev I., Infante L., Espinosa E. L. O., “Using different norms in packing circular objects”, Intelligent Information and Database Systems, Lecture Notes in Computer Science, 9012, 2015, 540–548 | DOI

[24] Galiev Sh. I., Lisafina M. S., “Linear models for the approximate solution of the problem of packing equal circles into a given domain”, European J. Operat. Research, 230:3 (2013), 505–514 | DOI | MR | Zbl

[25] Galiev Sh. I., Lisafina M. S., “Chislennye metody optimizatsii upakovok ravnykh ortogonalno orientirovannykh ellipsov v pryamougolnuyu oblast”, Zh. vychisl. matem. i matem. fiz., 53:11 (2013), 1923–1938 | DOI | MR | Zbl

[26] Ward J. E., Wendel R. E., “Using block norms for location modeling”, Operation research, 33 (1985), 1074–1090 | DOI | MR | Zbl

[27] Rocafellar R. T., Convex analysis, Princeton University Press, Princeton, NY, 1970 | MR