Your diagram of the nesting shapes was very satisfying.  I can see how there is almost a direct relationship between your optimisation problem and SA.  It's tempting to think that all that needs doing is to shake the shapes until they line up!

Seriously though, I wonder how often does this optimisation need to be done, and how long does it take?  A few years ago case-based reasoning was used to organise aerospace parts for curing.  (Sorry can't find a good ref).  If there are lots of different combinations of parts, then I wonder whether CBR might be helpful in your case.  Perhaps a hybrid approach where SA comes up with methods of combining a small number of pieces, and the CBR can then note similarities and combine parts of the solution into a whole...