How to create an optimized 3D volume-packing function in python?

Question

So I have been given the task to create a shipping module for a webshop system. It may be a bit overkill, but I would really like to create one that can figure out how to pack parcels in the most optimized way. Having learned programming simply by doing it, this is an area where I have no knowledge - yet! Anyways I can just give short description of the actual problem.

So when users buy stuff at webshops they will have x products in their cart with possibly varying sizes and weight. So I want to give that list of products to the function and let it figure out how these products should be packed in parcel(s).

• max length of parcel: 100
• max width of parcel: 50
• max height of parcel: 50
• max weight of parcel: 20

Every product has a weight, length, width and height as well.

Since parcels and products are basically boxes, I'm guessing this would be rather complex, as there are different ways of putting the products inside the parcel. My goal is not to make the perfect packaging function, but I would like to do something better than just putting products inside the parcel until a limit has been reached.

Now, I don't expect you guys to make this for me, but what I would like to ask is three things.

1. Where can I find good online resources that will teach me the basics needed?
2. Are there some native python tools that would be good to use?
3. Some pointers of what I need to be aware of, pitfalls etc

Like I said, I don't plan for this to be perfect and 100% optimized, but I would like to end up with something that will come close. I would hate if users feel that the sending fee will be a lot higher than it actual is.

Answer 1

That’s your typical knapsack problem. Many solutions for different languages can be found at Rosetta Code.

Answer 2

The fact that you have height, length and width makes it harder than a simple knapsack problem. Here's an interesting discussion of a 3D knapsack problem.

Here's a paper on the topic by the same guys.

Answer 3

This seems a good problem to which to apply the simplex algorithm or some sort of genetic algorithm. If you never heard of the latter, I highly recommend you to read about them. As I can see from your question, you're doing this enhancement because you like to make things work optimally, and not because you were told to do so. Imagine when you tell them you applied an Artificial Intelligence technique for solving their problem!

There are many straight-forward algorithms that solve your problem, but this can be a great opportunity to learn some evolutionary computation. Some interesting links about genetic algorithms [everyone, feel free to edit and add]:

1. These pages introduce some fundamentals of genetic algorithms.
2. Genetic Algorithms in Plain English

Luck with that!
Manuel

Answer 4

This an old question, but just in case somebody stumbles upon this... there is python library called pyshipping that solves this problem:

https://pypi.python.org/pypi/pyShipping