1

not 100% sure on title, feel free to edit to be more generic and helpful to all users

I have an order capture 'portal' which allows for orders to be captured. Part of the order is volume or the order.

I need to now process the order so that a pallet can be built that allows for optimal useage of pallets.

As an example, a packed pallet dimension can be 1.62 cubic meters (1x1.2x1.35)

I then have the following items on the order

Product code, qty, total volume

1,      10,   0.5 cubic meters
2,       3,    0.2 cubic meters
3,       5,    1.2 cubic meters
4,       1,    0.15 cubic meters
5,      15,   0.6 cubic meters

I want to process this, I am assuming with a mysql transaction so that the following output is acheived:

Pallet 1: Products 1,2,5. Total Volume=1.3 cubic meters
Pallet 2: Products 3,4. Total Volume=1.35 cubic meters

So to clarify, the script will take the first pallet of 0.5 cubes and then look for the next order in the list that is closest to 0.85 to acheive the 1.35 cubic meter target. in this case it will be 0.6. total now 1.1 cubes. remaining space is now 0.25 cubes. closest item in the list is now product 2 @ 0.2 cubes. total now 1.3 cubes and no product exists that is 0.05 cubes or less so pallet is complete. next available product is now product 3 @ 1.2 cubes. so product of 0.15 or less is required. product 4 is the exact volume so add to pallet and close off.

I hope that helps clarify my requirement.

Is there a mysql transaction that can assist with this or does this need to be processed with php.

Any help with this would be appreciated, just not sure how to build this logic.

Thanks for your time as always,

enter image description here

mysql Table is below:

enter image description here

Improve this question
5
  • 1
    Don't the shapes of the boxes matter? It's all very well saying that a pallet has a volume capacity, but unless the containers are fluid there will also be a "shape" capacity (which is a tighter constraint): considerable space may remain in the pallet, but scattered around in pockets of irregular sizes and shapes; whereas you might only have cube-shaped boxes of a smaller overall volume but which cannot actually fit anywhere. Or is this a purely academic exercise, in which you do not care about shapes? Commented Oct 24, 2012 at 8:35
  • hi @eggyal. You are 100% correct. the orders are done at a layer level so the horizontal footprint will always be the same size as the pallet. its really just combining the vertical layers to be efficient. I have added a rough sketch to the question to help clarify. Thanks Commented Oct 24, 2012 at 8:40
  • I did read through the knapsack problem, can this logic be completed with mysql or php? Thanks again. Commented Oct 24, 2012 at 8:42
  • 1
    Okay, in that case really you only care about keeping the aggregate heights of the orders within the total height capacity of the pallet. The problem statements are equivalent: I just find it easier to think in terms of one dimension than three! Commented Oct 24, 2012 at 8:42
  • Thanks @eggyal makes sense. any suggestions on how I can coomplish this with PHP? Thanks. Commented Oct 24, 2012 at 8:50

3 Answers 3

Reset to default
2

This is the classic bin packing problem, which is NP-hard (that is, we have not yet worked out whether the problem can be solved in polynomial time). Finding the optimal packing is tantamount to trying out every possible combination.

If you don't care about finding the optimal solution, then the greedy heuristic that you describe in your question (which is known as first fit decreasing) is a reasonable approximation; there are other heuristics which can guarantee more optimal results overall, but they get quite complicated.

You can implement FFD in PHP as follows (using PDO for database access):

define('PALLET_SIZE', 1 * 1.2 * 1.35);

$dbh = new PDO("mysql:dbname=$dbname", $username, $password);

$qry = $dbh->prepare('
  SELECT   code, qty, volume
  FROM     orders
  WHERE    order_id = :order
  ORDER BY volume DESC
');

$qry->execute(array(':order' => 123));

$pallets = array();
while ($order = $qry->fetch()) {
  if ($order['volume'] > PALLET_SIZE) die('item too big');

  for ($i = 1; $i <= $order['qty']; $i++) { // remove this loop if not needed
    $placed = false;
    foreach ($pallets as &$pallet) {
      if ($pallet['remaining'] >= $order['volume']) {
        $pallet['remaining'] -= $order['volume'];
        $pallet['items'][] = $order['code'];
        $placed = true;
        break;
      }
    }
    if (!$placed) $pallets[] = array(
      'remaining' => PALLET_SIZE - $order['volume'],
      'items' => array($order['code'])
    );
  }
}

print_r($pallets);
Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Thanks eggyal, legendery explanations and sample code. I need to get my head around it but will revert shortly. Thanks a million.
Thanks again @eggyal. I am just trying to get my head around your code, slightly out of my league currently. can you elaborate / explain this code segment for me: code foreach ($pallets as $pallet) { if ($pallet['remaining'] >= $order['volume']) { $pallet['remaining'] -= $order['volume']; $pallet['items'][] = $order['code']; $placed = true; break; } } Further to this, how do I use the output of this. Thanks for you assistance with this, really appreciated. Cheers.
You're going through the orders in turn, from largest to smallest, then cycling through every available pallet to find one on which the current order will fit. There is an array of pallets, $pallets over which one iterates; each member is itself an array containing an element $pallet['remaining'] which indicates the amount of space remaining on that pallet. If it's sufficient to accomodate the current order, we reduce the remaining space and push the order code onto the $pallet['items'] element (another array). Finally, we note that we found a pallet and break from the loop.
To use the output, you inspect the $pallets array. You could, for example, simply do print_r($pallets); (I ought to have included that - sorry!).
Apologies, I omitted an ampersand in the foreach; as a result $pallet was assigned by value and not by reference (and updates to it were not made in the actual arrays held within $pallets). Replace with foreach ($pallets as &$pallet), as shown above. Other than that, your understanding from the questions in your last comment is entirely correct.
|
1

Is there a mysql transaction

I assume you mean a mysql function.

No, there's nothing in mysql to help you solve this. It's an NP hard problem. The most efficient way to solve it is probably a genetic algorithm, however there's not enough information in your data to implement this accurately - packing depends on the shape (i.e. all dimensions) as much as the volume.

If you did have the dimensions then it's still a lot easier to allow a human to set the packing rather than trying to do it in code.

As a quick solution, I'd go with comparing a set of N copies of the list, randomly ordered, iterate through each one creating full pallets then pick the list with the fewest pallets (or other characteristics which are desirable). Picking the right value for N will depend on the distribution of sizes, and how much time you want to spend processing the data.

Improve this answer

6 Comments

Thanks symcbean. I do have allot of data available, just thought the volume was the best measurement. as per @eggyal perhaps we can just look at the height constraint. how can I create the N Copies to compare in PHP? Thanks for your time.
It doesn't make any computational difference whether you deal with volume or height: the only difference is the conceptual ease with which a human can understand the model.
understood. any examples or starting code for me to have a look at? thanks, I know its always a cheeky ask.
I added my answer before the layers update. That makes it even more complicated - since you can't balance a full layer on top of a half-completed layer - but you will have to model layers in your algorithm
In my example, there will never be half completed layers as ordering is done at a layer level? its just trying to ensure the various layers are grouped together optimally onto pallets so as to use the least pallets?
|
1

This is similar to the knapsack problem; it's a problem which can only be solved perfectly by trying all possible combinations. This rapidly becomes a problem as the number of possible combinations increases. In your example, there would be 33! combinations - rather a large number. So that route is probably not one we want to go down...

There's no "out of the box" solution, though there is sample code for the knapsack problem here. That might help.

I wrote a program years ago which did a reasonable job with a similar problem; the pseudo code was something like:

for each order
  while (unallocated items on order)
    create new pallet 
    while not (pallet = full)
      allocate largest remaining item smaller than remaining capacity to pallet 
    loop
  loop
next order

This algorithm did a decent job - and the guys in the shipping yard liked it because the largest items were always at the top of the packing list (and thus ended up at the bottom of the stack). The business accepted that the algorithm wasn't guaranteed to be optimal; in practice, this only made a difference on huge orders where a slight improvement in the algorithm might have saved us a pallet; in most cases, making the algorithm more efficient would have meant that the last pallet in the shipment was almost empty.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.