# Optimisation Problem for Pipe Nesting

I work in a company where we are supposed to produce and send pipes using trucks to buyers. Pipes of smaller diameter can be nested inside pipes of larger diameter while sending to minimize number of trucks.

The trucks that carry these pipes are usually 40 feet / 12.192 meters long while the pipes are 12 metres long. Hence, they are placed length wise along the trailer.

The trucks are usually 8 feet / 2.438 metres high and wide ie 8x8.

The outer diameters of pipe that we make are 90, 110, 125, 140, 160, 180, 200, 250 and 315 (all sizes in mm).

A constraint here is that while nesting, pipe of one size can only be nested inside pipe one size greater than the next size. Example, 90 pipe can go into 125 and higher pipe size, 140 pipe can go into 160 or higher pipe size.

I wish to mathematically derive a system for optimum loading of the trucks to minimize the number of trucks to deliver the ordered quantity of various sizes using nesting because we often goof-up with nesting resulting in huge cost implications. Can some one please help?

(Also, I am a naive user. It would also be helpful if you can suggest the appropriate tags that I should put along the question to help people notice the question.)

• You haven't really specified a constraint for how many pipes of some size you want to transport. In that case the answer you be 1, which is clearly incorrect. You need to enumerate (or at least give a constraint) on how many of certain pipe sizes you want to move before dealing with optimality. – Malcolm Jun 17 '15 at 23:17
• Hey Malcolm, the costraint here is the width and the height of the truck which limits the number of pipes that i can place side by side and on top of each other.I get orders with different quantities of different sizes. Say, 15pipes of 110mm, 48 pipes of 160mm, 80 pipes of 200 mm dia and so on. The orders require more than one truck. My agenda is to minimize the number of trucks – Shobhan Taparia Jun 17 '15 at 23:21
• Well first you should take a look at this article which is about circle packing in a square. They've calculated the optimal packing strategy up to 20 circles. Secondly, a general off the cuff optimization model that comes on the top of my head is putting all the pipes of the biggest and same size on one truck and packing as many pipes in them as you can linkhere, and repeating this for the next truck with whatever pipes you have left over. This is based on intuition though, not anything remotely numerical since you have provided none. – Malcolm Jun 17 '15 at 23:49
• Should one transport equal number of all sizes of pipes, or would the company be happy if we (for example) only transport the smallest pipes? – Tommi Jun 18 '15 at 6:08
• Hey Malcolm, I wish to have a generic solution and not a specific solution of one single problem. You can assume the following data for a sample case: 90mm-138061 meter, 110mm-48000 meter, 125mm-1306 meter, 140mm-16509 meter , 160mm-10615 meter, 200mm-166 meter. – Shobhan Taparia Jun 18 '15 at 8:27

I doubt there is an optimal analytical strategy for solving the problem. You will want to use an optimization approach.

A naive greedy strategy, which is probably decent, but almost certainly not optimal:

1. Pack in all the largest pipes. For any given truck, this amounts to a problem of packing as many circles as possible into a square; as Malcolm mentioned in a comment, this problem has been explicitly solved in some cases and numerics probably also exist; see https://en.wikipedia.org/wiki/Circle_packing_in_a_square. Use as few trucks as possible.

2. Consider the largest kind of pipe that has not been packed in yet. First nest them inside the larger pipes. If pipes still remain, try to fit them into the gaps between the larger pipes; pack as carefully as possible. This is a matter of packing circles into an arbitrary bounded area and optimization literature might exist, but explicit solutions almost certainly will not. You can do this one truck at a time. If there are still pipes of the same size remaining, add new trucks; this reduces to step 1., above.

3. Repeat step 2 for all pipe sizes.

A naive, and not efficient, optimization method would be to remove a pipe (and all nested pipes) of a given size and then try to fit two or more smaller ones into the hole. You should first fill all the trucks with the naive method and then check what size of pipes are in the final one; these are the ones you will want to pack more effectively.

Suppose there are at least two trucks filled with pipes of the critical size. Try removing pipes larger than that from other trucks and replacing them with pipes of the critical size. Take the most empty truck with critical pipes as the one you are trying to empty. Into the other(s) you will try to insert the pipes you have removed from elsewhere.

This would be cumbersome, so probably just stick with the naive algorithm.