Volume 16, No 4, 2009, P. 61-86

UDC 519.178
A. S. Rudnev
Probabilistic tabu search algorithm for the packing circles and rectangles into the strip

Abstract:
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.

Rudnev Anton Sergeevich ¹
1. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: anton.rudnev@gmail.com