At work we build large machines, these get deconstructed, placed i crates and shipped away to the client. Now we are just guessing how many trucks we need and how we lay the crates out to fit as many of them inside a truck.

For example:

We have a truck and want to load 8 crates of equal size into it. There are 2 possible "solutions" to this problem.enter image description here

But here you can see that the second option is better in space used (all pallets fit).

Now the real question. Is there a algorithme out there that can do this, even with irregular crates (meaning diffrent in size). Or do i need to invent one myself?

EDIT: Some more details:

The crates can vary in dimensions. But are always rectacles or squares.

The crate dimensions voor in the form of an Excel file where width height and lenght are defined.

  • 2
    $\begingroup$ Are all crates rectangulars? Do the all have the same dimsions? $\endgroup$ Jul 25 '18 at 18:38
  • 1
    $\begingroup$ Please share more details, how large is your input, how many crates, what do you mean by irregular? It seems like standard 2d packing problem, so maybe you can use approximation or use bounding boxes to your irregular shapes? $\endgroup$
    – Evil
    Jul 25 '18 at 18:55
  • $\begingroup$ Added some extra details $\endgroup$ Jul 26 '18 at 7:09

This already exists, but might not be what you are looking for.

While this might not be a problem for your application, notice that this is a more general problem than the (already NP-hard) bin packing problem, so for a large amount of crates finding the optimal solution will be hard.

On the other hand, for a small enough number of crates, brute force might be sufficient. For example, you could round all dimensions to multiples of 10cm and look at the trucks in terms of 10x10 tiles that crates can occupy, giving you a finite (hopefully small enough) number of potential solutions.

  • $\begingroup$ The link looks like comercial product not algorithm description. $\endgroup$
    – Evil
    Jul 25 '18 at 19:38
  • $\begingroup$ This indeed looks kinda like what we want to achieve. But we want an inhouse program $\endgroup$ Jul 26 '18 at 7:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.