A Heuristic Approach Based on Shape Similarity for 2D Irregular Cutting Stock Problem - Intelligent Computing for Sustainable Energy and Environment - page 281

as {FD n , 0<n<N}. The similarity between the query shape Q and the target shape T is
given by the Euclidean distance d between their FDs.
2

1
2

N



Q T

d = ( FDFD − )

.

i i

i = 1

4 Performance Evaluation

All algorithms are implemented in Visual C++ and we also use the library CGAL to
do some geometrical operations. The tests are performed on a computer with
processor Intel Pentium Dual 1.8 GHz, 2 GB of RAM, and Windows XP operating
system.
Few work for packing problems with pieces of irregular shape are done in the
literature, and especially we can hardly find any related work for the 2DCSP and
2DBPP when pieces have irregular shape. As a result, we adapt some other known
instances for packing problems with one open dimension to test our algorithms. The
generated instances are adapted from the Two-Dimensional Irregular Strip Packing
problem, and they can be found at the ES-ICUP website. In these instances, the
following information is available: the quantity of pieces; the set of allowable
rotations for these pieces; and, the size of the stock.
The instances from AM Del Valle .et .al 2012 are adapted and adopted in this
research [22]. Table 1 presents solutions computed by our algorithm. We use the total
area of the pieces divided by the area of one stock as a lower bound for the optimal
solution. The rows in this table contain the following information: instance name
(Name); solution value computed by our algorithm (Solution); the lower bound (LB);
the difference (in percentage) on number of stocks computed by Solve 2DCSP and
LB; the time spent in seconds (Time).
From Table 1 we can see that the value of the solutions returned by the algorithm is
on average 38.487% larger than the lower bound (in the worst case), However, for
instance DIGHE1, it is 84.375% larger. The results of the algorithm should be much
closer to the optimal solutions and these differences are mainly due to the weakness
of the lower bound. The instance SHIRTS took 1,232,468.32 s ( ≈ 14 days) of CPU
processing. The CPU time spent is on average 140896.16s. Since the complexity of
the working with pieces of irregular shape is largely increased, the problem becomes
harder than the working with rectangular pieces and some instances even take a long
time to be solved.
It is worth to mention that all the instances are executed 30 times, except SHIRTS
(2 time), SWIM (20 times) and TROUSERS (10 times) due to the high CPU time
required by them. All the results presented on Table 1 are the average values of all
executions. Such results show that the algorithm returns good solutions for the cutting
stock problem with pieces of irregular shape. However, it requires high CPU time
when solving instances with several pieces of completely irregular shape.