These forums are read-only!
3D Bin Packing Algorithm
-
I'm working on this box packing algorithm and from everything I can find this issue is a 3d bin packing algorithm. Basically I was wondering if anyone has any experience with this type of thing or if anyone has any resources, code, etc that might help. I've found tons of academic articles which all have theoretical algorithms and math formulas, but none have any sample code or anything.
The goal is this. You have a number of "Containers" of varying sizes (these are boxes that we have on hand to ship orders in, usually we have thousands in about 5 different sizes). When someone makes an order they will have a number of products, the "boxes" need to be arranged in the least number of "containers" with the least amount of waisted space. I've looked at a couple existing implementations that use volume calculations but it isn't very practical because it doesn't take into account the size of the box relative to the container (a golf club's volume is about the size of a jewelry box).
If anyone has any ideas or any general direction it would be greatly appreciated. -
Interesting problem. My guess is you won't find any code for that, like you said just a lot of papers. If code does exist, it's probably buried deep inside big shipping companies. Keep us posted.
-
Hopefully I'll find something, with all the work that is going into it, if I ever get something working maybe I'll release it as a gem or something. I found some C code but it uses a finite number of containers that are all the same size. The hunt continues.....
-
Bin packing is an NP-hard problem, which means heuristic algorithms. It also means when you go to google for it all you are going to find is mediocre CS students looking for the same code snippet as you to turn in as their own for a homework assignment. Maybe try your local university CS department and offer to supply data and parameters to judge output and maybe you can get a teacher to assign it as homework.
-
Ok so here is some progress. I found some code similar to the problem at hand over at RubyQuiz.com the problem that they were working with is a 2D bin packing problem. I took the code that was written by Ilmari Heikkinen and basically added formatting and some serious comments (I'm a Zealot for readable code).
When the code is ran it takes a first line of input to define the LxW of the container (known as a Trunk in the code), the second line of input is used to define the boxes that need to be packed (ex: 1x3 4x8 3x7 9x4 10x14, this would be 5 boxes). The code then tries to find the best fit for the boxes and places them adding a new Trunk if necessary.
From what I can see I'll need to mod the code to make it 3d instead of 2d, and also make it use trunks of differing size. I feel like this is a pretty good place to start though. If any one has any ideas, comments, suggestions etc. please let me know. I'd love any input.
# This is a 2D fit-first greedy heuristic algorithm that tries to fit each box into the trunk, largest first. If no box fits,
# a new trunk is created.
#
# I'm representing trunks as 2D tables of squares (with one unit of hidden padding around), then fill it starting
# from top left. The fitter-first finds a row with enough empty space to fit the box and then checks if the next box-height
# rows also contain the space. If they do, the box is drawn to the rows.
# Printing is easy because the trunk already is in printable format.
# Not a particularly fast way to do it, mind you :)
#
# If you're interested about different algorithms for solving the 2D bin packing problem,
# here's a paper:http://www.dei.unipd.it/~fisch/ricop/tesi/tesi_dottorato_Lodi_1999.pdf
class Array
#delete the first item (box) found. We don't want to use
#delete() because of any other boxes of the same size
def delete_first item
delete_at index(item)
end
#If a box is [10, 14] this will return a copy in the form
#of [14, 10] effectivley flipping it
def rotate
d = dup
d.push d.shift
d
end
end #end Array class
class Trunk
def initialize(w,h)
@w = w
@h = h
@items = []
@rows = (1..@h+2).map{ "_"*(@w+2) }
end #end initialize
#try adding the box both ways, if either fits we assume its now
#in the Trunk and it will be deleted from the list of boxes
def add box
try_adding(box) or try_adding(box.rotate)
end #end add
def try_adding box
#create a new box row, expanding on both sides. If you expand the Trunk and all the boxes, you can
#essentially forget about the padding, as long as you remember to strip it out later. Also note that boxrow
#is built as a String of "_" characters, so it will be used to find empty Trunk space.
boxrow = "_"*(box[0]+2)
@rows.each_with_index do |r,i|
#break out of the loop as soon as we run out of enough @rows to hold the box (and 2 extra padding @rows)
break if i > @rows.size - (box[1]+2)
#verify that this row holds the box, or move on
next unless r.include?(boxrow)
#fetch the index where the box would fit on @rows needed to hold it below this one
idxs = @rows[i+1, box[1]+1].map{|s| s.index boxrow }
#verify that we got an index for all needed lines, or move on.
next unless idxs.all?
#find the highest of those indices.
idx = idxs.max
#verify that the box does fit on all needed @rows at the highest found index, or move on
next unless @rows[i, box[1]+2].all?{|s| s[idx,boxrow.size] == boxrow }
#if we made it this far, we have a match, so we will draw the box in place. We can
#ignore the padding now, since we already proved there is room.
@rows[i+1, box[1]].each{|s| s[idx+1, box[0]] = "#" * box[0] }
#add the box to the @items, so we know the Trunk isn't empty?(), and return the box to indicate
#a match
@items.push box
return box
end #end each_with_index
nil #default false return, if we didn't find a match
end #end try_adding
#simple... trunk has no items in it
def empty?
@items.empty?
end #end empty?
#this formatting method is called before the trunk is printed.
#the extea space is stripped out of the trunk here
def to_s
@rows[1..-2].map{|r|r[1..-2]}.join("\n")
end #end to_s
end #end Trunk class
###
# Get the trunk size and the box sizes, then split them on "x" and put
# into arrays like this:
# trunk = [10, 20]
# boxes = [[1, 3], [4, 8], [3, 7], [9, 4], [10, 14]]
###
# trunk = "10x20".strip.split("x").map{|i| i.to_i}
# boxes = "1x3 4x8 3x7 9x4 10x14".strip.split(" ").map{|s| s.split("x").map{|i| i.to_i} }
trunk = gets.strip.split("x").map{|i| i.to_i}
boxes = gets.strip.split(" ").map{|s| s.split("x").map{|i| i.to_i} }
#sort the boxes from largest to smallest based on their area (w*h)
boxes = boxes.sort_by{|b| b.inject{|f,i| f*i} }.reverse
#create a new trunk object inside an array. Use of the splat operator on the "trunk"
#variable which separates out the array into width and height
trunks = [Trunk.new(*trunk)]
#while there are boxes this loop will try to fit them
#into the last Trunk. We are going through the boxes from largest to smallest
#and last Trunk will always be the one with the most open space. If a big box doesn't
#have room there, all the smaller boxes will be tried by find()
until boxes.empty?
#try to add the box to the last trunk, if it doesn't go we get nil
fitting = boxes.find{|box| trunks.last.add box }
#if the box fit
if fitting
#remove the box from the boxes that need to be placed
boxes.delete_first fitting
#if the last trunk was empty
elsif trunks.last.empty?
#raise an error because the box is too big to fit into the Trunk
#and a solution is impossible
raise "Can't fit #{boxes.inspect} into the trunk"
#box didn't fit but the last trunk did have items in it
else
#make a new trunk and try to fit it again
trunks << Trunk.new(*trunk) unless boxes.empty?
end #end if fitting
end #end until
#print out the array of Trunk objects, note that to_s gets called
#on each Trunk before it is printed, and we have a custom def for that.
puts
puts trunks.join("\n\n~~~~~~~~~~~~~~~~~~~~~~~~~~~\n\n") -
That seems to be "first fit decreasing" of boxes within n bins of the same size and shape, which wikipedia says will use no more than 11/9*optimal + 1 bins [*] But I don't think it will generalize well to differently-sized bins. Imagine packing n marbles. If your list has refrigerator bins, shoe bins, and single-marble bins, it will might use either 1 refrigerator bin or n marble bins depending on the order of your container list, when you would probably consider a single shoe bin to be the optimal solution.
I would look for a solution to the generalized problem. If there isn't code publically available to do this, I'd prefer to implement the algorithm described by a paper than start with code that doesn't really do the right thing. You might find code for the generalized problem, though, assuming you're content with the approximation of shapes as their bounding box. I think it's common to use bin packing estimation algorithms for analogous problems. (In fact, I've never seen anyone actually using it for physically packing bins.)
Also, I'm assuming most orders are pretty small? Then getting an exact solution might not be too expensive. You could use an exact algorithm for smaller orders and fall back to the approximation algorithm only when the exact algorithm is infeasible.
[*] - assuming that an object's bounding box is a decent approximation of its shape. It wouldn't do as well for bowls, for example. -
The orders usually don't have more than 10 products, and there usually aren't more than 5 possible containers. Also we are always assuming that the containers and products are both rectangular in shape.
To address the marble in a refrigerator box issue, the algorithm will have to account for wasted space in the packing configuration. So for example if it started with a super large box and had a ton of wasted space, it could move to the next largest box and try again until it minimized the amount of wasted space. But then it gets really complicated, because the algorithm should be looking at multiple containers to pack the item in, not just all in one. For example it may be best to pack the order into 1 medium box, and 1 small box, as opposed to 1 large box.
I have quite a few articles that talk about theoretical formulas on how to do this, even in 3 dimensions with accounting for wastage etc, but I can't convert the formulas into code.
Check out the attached PDF, it is the closest thing I've found to a solution in an academic paper.
files1996-39.pdf247K -
So I've been researching this like crazy and I've actually found a academic paper that has the algorithm represented that I think is needed. It would have to be translated from math speak to code but that isn't too tough. In the article they reference test cases from David Pisinger who is cited as one of the active researchers in bin packing algorithms. There is some sample code on this site http://www.diku.dk/~pisinger/codes.html written in C with some test scenarios.
The issue is that when I compiled and ran this code it did come up with the right results, (using a single size bin) but it took forever. The question now is this: If compiled C code took that long, how long would it take ruby. Maybe this intense algorithm isn't a good fit for real-time packing.
That thought then makes me think. Instead of trying to figure out how and where to position the boxes, maybe a quick little algorithm could be made that just uses the box length, width, and volume. Any ideas? -
Any shortcuts you are going to be able to take are going to depend on the specifics involved. What are the dimensions of the 10 products and the 5 bins. If all products have rotational symmetry and share a common dimension I think you should be able to resolve this to a 2D bin packing problem, for example.
-
The code you linked seems to be exact algorithms. I'd thought even that would be relatively fast for the numbers you're talking about, but if not back to the approximation I suppose.
Also, if I found C code for a performance-sensitive calculation, I would not rewrite it in Ruby - I'd just write a Ruby extension to wrap it. -
I don't know if they would share any common dimensions to the exact measurement, but they would all be 6 sided polygons, with length, width, and depth measurements.
Rotational symetry, I'm guessing it would be 2nd order?
Basically boxes similar to shoe boxes, cereal boxes, 12 pack of soda box etc. The bins are cardboard boxes of varying sizes. Here are some examples all in inches:
product boxes (LxWxD)
12x6x6
5x6x6
9x14x12
14x16x20
container boxes (bins, LxWxD)
9x8x9
12x14x13
18x19x22
25x29x28
36x30x38
There are usually only around 5 bin sizes at any time, there are over 3000 products all ov varying sizes (each one is at least small enough to fit in the largest box). However it doesn't matter how many products are in stock, but how many the user orders. That is usually only about 10 or less.
Thanks! -
The following dissertation examines in detail a fast heuristic algorithm for solving a nearly identical problem. Realistic and practical constraints are accounted for. The author describes and implements the algorithm with pseudocode as well as with functional C code. It is an unrestricted document.ACCESSION NUMBER: [ABSTRACT: ADA391201] [DTIC HANDLE TO PDF FULL TEXT]
The Distributer's Three-Dimensional Pallet-Packing Problem: A Human Intelligence-Based Heuristic Approach
MAR 2001 :: Baltacioglu, Erhan :: AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH -
Synchronicity! Of all the random things, I realized just today that an important aspect of a problem I've been working on for a couple of days is in fact a specialized case of a one-dimensional bin packing problem!
-
If any of you actually took the pains of typing the code in link given by Gadget on Feb 9th 2008 could you share? It would save a lot of typing for me and avoid errors too.
-
Have you made any progress on this? FWIW, I did a solution to this problem a few years ago for a warehouse, but it was never rolled out to production and I quit the company shortly thereafter. Now I'm working on an ERP project for another logistics center with similar needs. Unfortunately, I no longer have access to my old code, and it's probably lost anyways. Never mind, I remember roughly what i did then and will probably be able to recreate it without too much effort.
The approach I ended up with last time was to sort the boxes in a descending order and then try to fit each of them inside a container. There were also a number of different, prioritized, containers that the application could choose from, so that it would first try the highest priority, then next highest etc. The algorithm would also rotate the boxes to try to make them fit.
I'll probably start working on the 3d packing within a few weeks and will keep you informed if you're interested. I also have a working 2D packing algorithm that is intended to solve a common problem in accounting, where the accountant has a sum from a number of entries in a journal, that he knows is erroneous, and he is trying to find out which entries are giving him this sum. The algorithm is still prototype only, but I can post my c# code here if anyone's interested in that, too -
Hello!
I worked in one of the first university labs that had a stereolithography machine (Clemson, 93). I worked on a similar problem except with boxes of any dimensions (in other words, we were not limited to a set of box sizes). Since stereolithography build layers take a relatively small amount of time to draw, especially when compared with the time it takes to prepare for the next layer, my goal was to pack all our models into a space with the least possible height.
This is an NP-complete problem. You MUST try all possible solutions and compare them to get the one (or more) best solution(s). My solution was a set of genetic algorithms, which would work toward a "good" solution, if not the very, very best. I made it as far as creating a 500 pair lock puzzle, which the routine could solve (exactly, not close) within a few hours at 1990s Macintosh speeds. I would be happy to share the lock box code and discuss how I was going to apply it to the various tags for box sizes.
Best,
Mick
Email me to discuss... -
Hi 3D, could you provide your solution to the problem. I'm currently working on something similar with GA and would like to use your source as reference. Thanks.
-
This might benefit those who prefer a quick and ready solution to the 3D bin packing problem. Instead of re-inventing the wheel, you could use the packing engine API available at SolvingMaze. They have an "e-Commerice Shipping Calculator" that can handle multiple containers loading of different sizes, and multiple packaging dimensions for merchandise with special handling requirements. It's tailored for e-Commerce shopping cart so it also provides postage calculation.
At the time of this writing, the service is free. -
Hi Guys,
I know,discussed matter is little old,but we have similar problem.
We are working a project that will locate different sized box.
Goal is to place maximum box without wasting any space.(3D boxes)
I mean our boxes will use minimum volume(bulk) and we will place maximum boxes as much as possible.
Thanx for helping -
I have not found any API on this site http://solvingmaze.com/demo
-
The API for that site is at:
http://solvingmaze.com/apidoc
Categories
- All Discussions5,068
- Can Someone Help Me...2,020
- Check This Out232
- Code Exchange29
- Distribution Specific69
- Gigs and Project Work97
- Heads Up125
- Migration to Rackspace Cloud54
- Python Zone33
- Ruby + Rails303
- Scaling and Performance311
- Slice Setup1,507
- Sliceteam1
- Why Should I Trust You Guys?98
- You Guys Really Should...189