468,161 Members | 1,981 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,161 developers. It's quick & easy.

Bin packing problem

Does anyone have code to solve a 3-d bin packing problem in php? I am
trying to solve the issue of packing various sized rectangular shaped
objects into boxes of three different sizes so as to use as few packing
peanuts as possible (to some reasonable approximation) to fill the
gaps.

I have found some c code and plenty of discussions on the subject, but
I was thinking that someone out there has to have done this in php
already.

FWIW, this would be off-line bin packing, and there are no "this side
up" or weight constraints.

Oct 30 '06 #1
9 5451

This has "homework" written all over it. I think you will need to
work it out for yourself.

fraz wrote:
Does anyone have code to solve a 3-d bin packing problem in php? I am
trying to solve the issue of packing various sized rectangular shaped
objects into boxes of three different sizes so as to use as few packing
peanuts as possible (to some reasonable approximation) to fill the
gaps.

I have found some c code and plenty of discussions on the subject, but
I was thinking that someone out there has to have done this in php
already.

FWIW, this would be off-line bin packing, and there are no "this side
up" or weight constraints.
Oct 31 '06 #2
Marcin Dobrucki wrote:
This has "homework" written all over it. I think you will need to
work it out for yourself.
Sounds like it, but this is for a real issue. I work at a brewery, we
ship all kinds of stuff (albeit, not the beer), and we want to keep the
shipping costs as low as possible for the purchaser by optimizing the
number of packages sent (as the first pound is always the costliest)
while concurrently reducing the amount of packaging materials needed
(peanuts, bubble wrap, etc.).

I have found an implementation in c for a version of this that isn't
quite what I need, and if I were to use it I would need to write a php
extension or pull out of safe-mode to run system/exec calls.

I guess it just seems like there have to have been some people who have
tackled this before considering how many on-line sales sites are out
there written in php, and any help would be appreciated by this
overworked sysadmin/programmer/dbadmin/graphic designer/cable
runner/taste tester who has, unfortunately, very little time to pore
over white papers titled "Guided local search for the three-dimensional
bin packing problem" trying to rekindle my memory on Big-O notation and
figure out how to convert this into applicable code.

Oct 31 '06 #3
fraz wrote:
Marcin Dobrucki wrote:
>>This has "homework" written all over it. I think you will need to
work it out for yourself.


Sounds like it, but this is for a real issue. I work at a brewery, we
ship all kinds of stuff (albeit, not the beer), and we want to keep the
shipping costs as low as possible for the purchaser by optimizing the
number of packages sent (as the first pound is always the costliest)
while concurrently reducing the amount of packaging materials needed
(peanuts, bubble wrap, etc.).

I have found an implementation in c for a version of this that isn't
quite what I need, and if I were to use it I would need to write a php
extension or pull out of safe-mode to run system/exec calls.

I guess it just seems like there have to have been some people who have
tackled this before considering how many on-line sales sites are out
there written in php, and any help would be appreciated by this
overworked sysadmin/programmer/dbadmin/graphic designer/cable
runner/taste tester who has, unfortunately, very little time to pore
over white papers titled "Guided local search for the three-dimensional
bin packing problem" trying to rekindle my memory on Big-O notation and
figure out how to convert this into applicable code.
Ah, that makes it simple. No PHP code needed. Just:

1. Place items in compactor
2. Activate compactor
3. Wrap results in brown paper.

No boxes and no peanuts required. And you can blame the damage on the
shipping company :-)

Seriously - I haven't seen anything like that in PHP. But I wouldn't
think it would be too hard to convert. Do you have some examples of the
C code?

--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
js*******@attglobal.net
==================
Oct 31 '06 #4
Seriously - I haven't seen anything like that in PHP. But I wouldn't
think it would be too hard to convert. Do you have some examples of the
C code?
<a
href="http://www.diku.dk/~pisinger/3dbpp.c">http://www.diku.dk/~pisinger/3dbpp.c</a>

I have been checking out this code for the last day when I have time.
It apparently restricts objects to not be rotatable, and the bins to
fill are all of the same size. So, in those two respects it is not
applicable, but I have hopes to modify it to my needs as a last resort.
It's just a bit dense, but I didn't necessarily expect anything less
out of the problem.

One constraint though that I could throw into the mix is that I don't
expect n (no. of items to pack) to exceed, say, 25 in all but the most
unusual scenarios. Hence, I could get by with a hacky brute force
heuristic that errs on the side of simpler code rather than an elegant
algorithm that approaches a "log n" efficiency. Ultimately, I just want
to be able to abstract the items that are to be packed so that the
addition of new types of items doesn't throw the whole procedure and
require a rewrite.
>
--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
js*******@attglobal.net
==================
Oct 31 '06 #5
fraz wrote:
>>Seriously - I haven't seen anything like that in PHP. But I wouldn't
think it would be too hard to convert. Do you have some examples of the
C code?


<a
href="http://www.diku.dk/~pisinger/3dbpp.c">http://www.diku.dk/~pisinger/3dbpp.c</a>

I have been checking out this code for the last day when I have time.
It apparently restricts objects to not be rotatable, and the bins to
fill are all of the same size. So, in those two respects it is not
applicable, but I have hopes to modify it to my needs as a last resort.
It's just a bit dense, but I didn't necessarily expect anything less
out of the problem.

One constraint though that I could throw into the mix is that I don't
expect n (no. of items to pack) to exceed, say, 25 in all but the most
unusual scenarios. Hence, I could get by with a hacky brute force
heuristic that errs on the side of simpler code rather than an elegant
algorithm that approaches a "log n" efficiency. Ultimately, I just want
to be able to abstract the items that are to be packed so that the
addition of new types of items doesn't throw the whole procedure and
require a rewrite.

Yuk! Some of the worst C code I've ever seen. Virtually no comments,
meaningless single character variable names and even the function names
are cryptic. I'm sure it works - but I'd hate to have to spend the time
understanding the code. And quite frankly I'd be embarrassed to even
post it.

But back to your problem. Brute force might be the easiest way.
Figuring you have 3 different orientations of the packages (assuming
they have symmetric shapes), a recursive routine might work. And as
long as you don't have to make too many calculations it should be
relatively fast.

--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
js*******@attglobal.net
==================
Oct 31 '06 #6

Jerry Stuckle wrote:
Yuk! Some of the worst C code I've ever seen. Virtually no comments,
meaningless single character variable names and even the function names
are cryptic. I'm sure it works - but I'd hate to have to spend the time
understanding the code. And quite frankly I'd be embarrassed to even
post it.

But back to your problem. Brute force might be the easiest way.
Figuring you have 3 different orientations of the packages (assuming
they have symmetric shapes), a recursive routine might work. And as
long as you don't have to make too many calculations it should be
relatively fast.
thanks for taking a look.
--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
js*******@attglobal.net
==================
Oct 31 '06 #7
fraz wrote:
>>Seriously - I haven't seen anything like that in PHP. But I wouldn't
think it would be too hard to convert. Do you have some examples of the
C code?


<a
href="http://www.diku.dk/~pisinger/3dbpp.c">http://www.diku.dk/~pisinger/3dbpp.c</a>

I have been checking out this code for the last day when I have time.
It apparently restricts objects to not be rotatable, and the bins to
fill are all of the same size. So, in those two respects it is not
applicable, but I have hopes to modify it to my needs as a last resort.
It's just a bit dense, but I didn't necessarily expect anything less
out of the problem.

One constraint though that I could throw into the mix is that I don't
expect n (no. of items to pack) to exceed, say, 25 in all but the most
unusual scenarios. Hence, I could get by with a hacky brute force
heuristic that errs on the side of simpler code rather than an elegant
algorithm that approaches a "log n" efficiency. Ultimately, I just want
to be able to abstract the items that are to be packed so that the
addition of new types of items doesn't throw the whole procedure and
require a rewrite.

>>--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
js*******@attglobal.net
==================

I thought about it some more. And really, your problem isn't much
different than the historic traveling salesman (a salesman has to visit
X cities - what's the shortest distance he has to travel to visit all
cities). It's a great puzzle - and one which has never been solved
except by brute force, AFAIK.

And I think that's what you're going to have to do here, unfortunately.

--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
js*******@attglobal.net
==================
Oct 31 '06 #8
Jerry Stuckle wrote:
I thought about it some more. And really, your problem isn't much
different than the historic traveling salesman (a salesman has to visit
X cities - what's the shortest distance he has to travel to visit all
cities). It's a great puzzle - and one which has never been solved
except by brute force, AFAIK.

And I think that's what you're going to have to do here, unfortunately.
If you want to get the *best* possible packaging solution, then like
you say, there's just no way around it...you're going to have to expand
the entire search tree. But, if you could be satisfied with the best
solution chosen from a subset of all solutions, then a
heuristic-directed A* search could be a good candidate.

Without delving deeper into the problem, a good starting heurstic would
simply be the amount of empty space left in the package. Keep
expanding the tree and following the branch dictated by the heuristic
until you get to a point where you can fit no more packages, and
declare that a possible solution. Backtrack out of the solution (how
far to back out will depend upon how similar you want your solution
subset to be...further = a more diverse set). Repeat X times to get
however many possible solutions you want to have, then choose the best
one as your actual packaging setup.

As I said, if you don't need the actual best solution, but only a
*good* solution, then this approach would save you processing time and
memory because you don't have to examine all possible options, just the
most promising ones.

Nov 1 '06 #9

Thanks for the feedback fellas.

Nov 1 '06 #10

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

reply views Thread by ZaGras | last post: by
reply views Thread by William Goedicke | last post: by
reply views Thread by nobull | last post: by
2 posts views Thread by gbb0330 | last post: by
1 post views Thread by gbb0330 | last post: by
2 posts views Thread by FMorales | last post: by
18 posts views Thread by Edward Diener | last post: by
1 post views Thread by Gajendra | last post: by
1 post views Thread by QbProg | last post: by
1 post views Thread by gcdp | last post: by
reply views Thread by kamranasdasdas | last post: by
reply views Thread by gcreed | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.