Geodesic
Probabilistic tabu search algorithm for the packing circles and rectangles into the strip
Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 4, pp. 61-86.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider the two-dimensional problem of packing of different-sized circles and rectangles into the strip of the minimal length. The problem is formulated as a mixed integer nonlinear programming problem (MINLP). For solving this problem, we develop a probabilistic tabu search algorithm based on a new 2-contact representation scheme. Computational results show that the developed algorithm is able to find solutions of good quality for random by generated and known instances. The algorithm has found new record solutions for four known circle strip packing problem. Il. 6, tabl. 6, bibl. 34.
Keywords: strip packing, representation schemes, tabu search. 
@article{DA_2009_16_4_a4,
     author = {A. S. Rudnev},
     title = {Probabilistic tabu search algorithm for the packing circles and rectangles into the strip},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {61--86},
     publisher = {mathdoc},
     volume = {16},
     number = {4},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2009_16_4_a4/}
}
TY  - JOUR
AU  - A. S. Rudnev
TI  - Probabilistic tabu search algorithm for the packing circles and rectangles into the strip
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2009
SP  - 61
EP  - 86
VL  - 16
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2009_16_4_a4/
LA  - ru
ID  - DA_2009_16_4_a4
ER  - 
%0 Journal Article
%A A. S. Rudnev
%T Probabilistic tabu search algorithm for the packing circles and rectangles into the strip
%J Diskretnyj analiz i issledovanie operacij
%D 2009
%P 61-86
%V 16
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2009_16_4_a4/
%G ru
%F DA_2009_16_4_a4
A. S. Rudnev. Probabilistic tabu search algorithm for the packing circles and rectangles into the strip. Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 4, pp. 61-86. http://geodesic.mathdoc.fr/item/DA_2009_16_4_a4/

[1] Goncharov E. N., Kochetov Yu. A., “Veroyatnostnyi poisk s zapretami dlya diskretnykh zadach bezuslovnoi optimizatsii”, Diskret. analiz i issled. operatsii. Ser. 2, 9:2 (2002), 13–30 | MR | Zbl

[2] Geri M. R., Dzhonson D. S., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[3] Mukhacheva E. A., “Obzor i perspektivy razvitiya kombinatornykh metodov resheniya zadach raskroya i upakovki”, Materialy konferentsii “Diskretnyi analiz i issledovanie operatsii”, Izd-vo In-ta matematiki, Novosibirsk, 2002, 80–87

[4] Stoyan Yu. G., Yakovlev S. V., Matematicheskie modeli i optimizatsionnye metody geometricheskogo proektirovaniya, Nauk. dumka, Kiev, 1986, 266 pp. | MR

[5] Alvarez-Valdes R., Parreno F., Tamarit J. M., “Reactive GRASP for the strip packing problem”, Comput. Oper. Res., 35:4 (2008), 1065–1083 | DOI | Zbl

[6] Araya I., Neveu B., Riff M. C., “An efficient hyperheuristic for strip-packing problems”, Studies in Comput. Intelligence, 136 (2008), 61–76 | DOI

[7] Beisiegel B., Kallrath J., Kochetov Y., Rudnev A., “Simulated annealing based algorithm for the 2D bin packing problem with impurities”, Operations research proceedings, 2005, Springer-Verl., Bremen, 2005, 109–113

[8] Birgin E. G., Martinez J. M., Nishihara F. H, Roncony D. P., “Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization”, Comput. Oper. Res., 33 (2006), 3535–3548 | DOI | MR | Zbl

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

[10] Burke E., Kendall G., Whitwell G., Metaheuristic enhancements of the best-fit heuristic for the orthogonal stock cutting problem, Computer Science Technical Report No NOTTCS-TR-2006-3, University of Nottingham, 2006, 30 pp.

[11] Dowsland K. A., Dowsland W. B., “Packing problems”, Europ. J. Oper. Res., 56 (1992), 2–14 | DOI | Zbl

[12] Dreo J., Petrowski A., Siarry P., Taillard E., Methaheuristics for hard optimization: methods and case studies, Springer-Verl., Berlin, 2005, 369 pp. | MR

[13] George J. A., George J. M., Lamar B. W., “Packing different-sized circles into a rectangular container”, Europ. J. Oper. Res., 84 (1995), 693–712 | DOI | Zbl

[14] Glover F., Laguna M., Tabu search, Kluwer Acad. Publ., Dordrecht, 1997, 382 pp. | MR | Zbl

[15] Hifi M., M'Hallah R., “A hybrid algorithm for the two-dimensional layout problem: the cases of regular and irregular shapes”, Intern. Transaction in Oper. Res., 10 (2003), 195–216 | DOI | MR | Zbl

[16] Hifi M., M'Hallah R., “Approximate algorithms for constrained circular cutting problems”, Comput. Oper. Res., 31 (2004), 675–694 | DOI | Zbl

[17] Hopper E., Turton B. C. H., “An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem”, Europ. J. Oper. Res., 128 (2001), 34–57 | DOI | Zbl

[18] Huang W., Chen D., Xu R., “A new heuristic algorithm for rectangle packing”, Comput. Oper. Res., 34 (2007), 3270–3280 | DOI | MR | Zbl

[19] Huang W. Q., Li Y., Akeb H., Li C. M., “Greedy algorithms for packing unequal circles into a rectangular container”, J. Oper. Res. Soc., 56 (2005), 539–548 | DOI | Zbl

[20] Huang W. Q., Li Y., Li C. M., Xu R. C., “New heuristics for packing unequal circles into a circular container”, Comput. Oper. Res., 33 (2006), 2125–2142 | DOI | Zbl

[21] Ibaraki T., Imahori S., Yagiura M., “Hybrid metaheuristics for packing problems”, Studies in Comput. Intelligence, 114 (2008), 185–219 | DOI

[22] Iori M., Martello S., Monaci M., Metaheuristic algorithms for the strip packing problem, Kluwer Acad. Publ., Dordrecht, 2003, 159–179 | MR | Zbl

[23] Kallrath J., “Cutting circles and polygons from area-minimizing rectangles”, J. Global Optimization, 43 (2009), 299–328 | DOI | MR | Zbl

[24] Kallrath J., Kochetov Y., Rudnev A., “Strip packing problem for circles and rectangles”, 4th ESICUP Meeting, University of Tokyo, Tokyo, 2007, 20

[25] Kenmochi M., Imamichi T., Nonobe K., Yagiura M., Nagamochi H., “Exact algorithms for two-dimensional strip packing problem with and without rotations”, Europ. J. Oper. Res., 198 (2009), 73–83 | DOI | MR | Zbl

[26] Lin J. M., Chang Y. W., “TCG: A transitive closure graph-based representation for non-slicing floorplans”, Proc. DAC, 2001, ACM, Las Vegas, 2001, 764–769

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

[28] Lodi A., Martello S., Vigo D., “Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems”, INFORMS J. Computing, 11 (1999), 345–357 | DOI | MR | Zbl

[29] Lodi A., Martello S., Vigo D., “Recent advances on two-dimensional bin packing problems”, Discrete Appl. Math., 123/124 (2002), 373–380 | DOI | MR

[30] Lubachevsky B. D., Graham R., “Dense packing of congruent circles in rectangles with a variable aspect ratio”, Discrete and computational geometry, Algorithms and combinatorics, 25, Springer-Verl., Heidelberg, 2003, 633–650 | MR | Zbl

[31] Stoyan Y. G., Yaskov G. N., “Mathematical model and solution method of optimization problem of placement of rectangles and circles taking into account special constraints”, Intern. Trans. Oper. Res., 5:1 (1998), 45–57 | Zbl

[32] Stoyan Y. G., Yaskov G. N., “A mathematical model and a solution method for the problem of placing various-sized circles into a strip”, Europ. J. Oper. Res., 156 (2004), 590–600 | DOI | MR | Zbl

[33] Yu H. X., Zhang L. W., “A nonlinear programming model for the packing of unequal circles into a square box”, Proceedings of the 6th World Congress on intelligent control and automation, IEEE Robotics and Automation Society, Dalian, 2006, 1044–1047

[34] Zhang D. F., Chen S. D., Liu Y. J., “An improved heuristic recursive strategy based on genetic algorithm for the strip rectangular packing problem”, Automatica Sinica, 33:9 (2007), 911–916 | Zbl