Box dimension order affects volume utilization

[patrick-melo]

The following test case demonstrates that if I swap the length and width in the box dimensions, the utilization changes from 65.3% to 56.6%. In the first test, the box is able to accommodate 4 items. In the second test, it can accommodate only 3. I would not have expected the order of the dimensions to have any impact on the utilization.

In this example, I swap the length and width between addBoxes1 and addBoxes1 to demonstrate the issue.

Is there something I should do to ensure that I get the maximum utilization? Perhaps I should ensure that the dimensions are specified with the largest ones first?

SOURCE

  <?php 
  require dirname(__FILE__).'/../vendor/autoload.php';
  
  use DVDoug\BoxPacker\Packer;
  use DVDoug\BoxPacker\Test\TestBox;
  use DVDoug\BoxPacker\Test\TestItem;
  
  function addItems($packer) {
      // SKU 209702
      // 19.00 cm (l) x 33.00 x cm (w) x 35.00 cm (d) = 21945.00 cm³ 
      $packer->addItem(
          new TestItem(
              '209702',
              190000,330000,350000,
              2130000,
              false
          ),
          10
      ); 
      
      // SKU 209513
      // 22.80 cm (l) x 14.70 x cm (w) x 14.60 cm (d) = 4893.34 cm³
      $packer->addItem(
          new TestItem(
              '209513',
              228000,147000,146000,
              879000,
              false
              ),
          20
      ); 
  }
  
  function addBoxes1($packer) {
      // Box 11 (174492)
      // 56.00 cm (l) x 46.60 x cm (w) x 21.50 cm (d) = 56106.40 cm³
      $packer->addBox(new TestBox(
          'Box 11',
          560000,466000,215000,
          817000,
          560000,466000,215000,
          999999000
          ));
      
      // Box 4 US alternative (208263)
      // 40.60 cm (l) x 41.60 x cm (w) x 32.10 cm (d) = 54215.62 cm³
      $packer->addBox(new TestBox(
          'Box 4 US alternative',
          406000,416000,321000,
          586000,
          406000,416000,321000,
          99999900
          ));
  }
  
  // Same as addBoxes1 with length and width swapped
  function addBoxes2($packer) {
      // Box 11 (174492)
      // 56.00 cm (l) x 46.60 x cm (w) x 21.50 cm (d) = 56106.40 cm³
      $packer->addBox(new TestBox(
          'Box 11',
          466000,560000,215000,
          817000,
          466000,560000,215000,
          999999000
          ));
      
      // Box 4 US alternative (208263)
      // 40.60 cm (l) x 41.60 x cm (w) x 32.10 cm (d) = 54215.62 cm³
      $packer->addBox(new TestBox(
          'Box 4 US alternative',
          416000,406000,321000,
          586000,
          416000,406000,321000,
          99999900
          ));
  }
  
  function printResults($packer) {
      $packedBoxes = $packer->pack();
      
      foreach ($packedBoxes as $packedBox) {
          echo $packedBox->getBox()->getReference()
          . " (".$packedBox->getVolumeUtilisation()."%)"
              .PHP_EOL;
              $packedItems = $packedBox->getItems();
              foreach ($packedItems as $packedItem) {
                  echo "  " .$packedItem->getItem()->getDescription() .PHP_EOL;
              }
      }
  }
  
  function main() {
      
      echo "----------Test 1" .PHP_EOL;
      $packer = new Packer();
      addBoxes1($packer);
      addItems($packer);
      printResults($packer);
      
      echo "----------Test 2" .PHP_EOL;
      $packer = new Packer();
      addBoxes2($packer);
      addItems($packer);
      printResults($packer);
  }
  
  main();

OUTPUT

----------Test 1
Box 11 (65.3%)
  209702
  209513
  209513
  209513
Box 11 (65.3%)
  209702
  209513
  209513
  209513
Box 11 (65.3%)
  209702
  209513
  209513
  209513
Box 11 (65.3%)
  209702
  209513
  209513
  209513
Box 11 (65.3%)
  209702
  209513
  209513
  209513
Box 11 (65.3%)
  209702
  209513
  209513
  209513
Box 11 (47.8%)
  209702
  209513
Box 11 (47.8%)
  209702
  209513
Box 4 US alternative (40.5%)
  209702
Box 4 US alternative (40.5%)
  209702
----------Test 2
Box 11 (56.6%)
  209702
  209513
  209513
Box 11 (56.6%)
  209702
  209513
  209513
Box 11 (56.6%)
  209702
  209513
  209513
Box 11 (56.6%)
  209702
  209513
  209513
Box 11 (56.6%)
  209702
  209513
  209513
Box 11 (56.6%)
  209702
  209513
  209513
Box 11 (56.6%)
  209702
  209513
  209513
Box 11 (56.6%)
  209702
  209513
  209513
Box 11 (56.6%)
  209702
  209513
  209513
Box 11 (56.6%)
  209702
  209513
  209513

[patrick-melo]

The documentation has the following to say:

BoxPacker operates internally by positioning items in “rows”, firstly by placing items across the width of the box, then when there is no more space starting a new row further along the length.

I'm going to use rsort() to work around this problem for now. Let me know if you think this makes sense.

SOURCE

function addBoxes3($packer) {
    // Box 11 (174492)
    // 56.00 cm (l) x 46.60 x cm (w) x 21.50 cm (d) = 56106.40 cm³
    $arr = [466000,560000,215000];
    rsort($arr);
    $packer->addBox(new TestBox(
        'Box 11',
        $arr[0],$arr[1],$arr[2],
        817000,
        $arr[0],$arr[1],$arr[2],
        999999000
        ));
    
    // Box 4 US alternative (208263)
    // 40.60 cm (l) x 41.60 x cm (w) x 32.10 cm (d) = 54215.62 cm³
    $arr = [416000,406000,321000];
    rsort($arr);
    $packer->addBox(new TestBox(
        'Box 4 US alternative',
        $arr[0],$arr[1],$arr[2],
        586000,
        $arr[0],$arr[1],$arr[2],
        99999900
        ));
}

[dvdoug]

Hi @patrick-melo

When initially packing a box, BoxPacker will consider both orientations of the box, and the order you specify doesn't matter. However after that phase, by default BoxPacker activates its weight-redistribution mode (https://boxpacker.io/en/stable/weight-distribution.html) which by-design trades away optimum packing efficiency for the goal of balancing weight. Because of that, the "try both versions of width/length" behaviour is not used here.

In the vast, vast majority of cases I've seen the ordering doesn't matter at all although obviously here you've found one that does. It's important to note though, that in other cases the opposite ordering would indeed be best (i.e. for other cases, rsort would give you worse efficiency than sort).

If optimum packing efficiency is your goal, then you can disable weight redistribution (see the link), then both versions will give the same results.

[CarlesRever]

Hi Dough. First of all: thank you for your amazing work!!!

Here the same issue, I think, but not solved by balance weight deactivation.

The example I bring, is very similar, I think: if I pass an item with two interchanged measures, the result is different: packer adds a second box or not, regardless of whether I tell it that the items can be rotated or not.

The products are:
59x39x39 (5)
59x39x47 (6)
59x39x33 (9)

And the Europallet, measures: 120x80x215

This case is very demanding, since the items, in a specific orientation, can perfectly use the volume of a pallet, being distributed in 5 layers of 4 items each, one of 39cm high, one of 47, two of 33, and one with mixed heights which therefore occupies the maximum: 47 as well.

The sum of the heights is: 39 + 47 + 33 + 33 + 33+ 47 = 199

Thanks,
Carles.

Here the modified code for this example:

  require dirname(__FILE__).'/boxpacker/vendor/autoload.php';
  
  use DVDoug\BoxPacker\Packer;
  use DVDoug\BoxPacker\Test\TestBox;
  use DVDoug\BoxPacker\Test\TestItem;
  
  function addItems1($packer, $rotation) {
	  
      // HEIGHT 39
      // 59x39x39
      $packer->addItem(
          new TestItem( 
              'height 39',
              59000, 39000, 39000,
              10880,
              $rotation
          ),
          5
      ); 
      
      // HEIGHT 47
      // 59x39x47
      $packer->addItem(
          new TestItem( 
              'height 47',
              59000,39000, 47000,
              10890,
              $rotation
          ),
          6
      ); 

      // HEIGHT 33
      // 59x39x33
      $packer->addItem(
          new TestItem( 
              'height 33',
              59000,39000,33000,
              10060,
              $rotation
          ),
          9
      ); 
  }

  function addItems2($packer, $rotation) {

      // HEIGHT 39
      // 59x39x39
      $packer->addItem(
          new TestItem( 
              'height 39',
              59000, 39000, 39000,
              10880,
              $rotation
          ),
          5
      ); 
      
      // HEIGHT 47
      // 59x39x47
      $packer->addItem(
          new TestItem( 
              'height 47',
              59000, 47000, 39000, // This values are interchanged: length per depth
              10890,
              $rotation
          ),
          6
      ); 

      // HEIGHT 33
      // 59x39x33
      $packer->addItem(
          new TestItem( 
              'height 33',
              59000,39000,33000,
              10060,
              $rotation
          ),
          9
      ); 
  }

  function addBoxes($packer) {
	  
      // Europallet
      // 120x80x215, max 400kg
      $packer->addBox(new TestBox(
          'EuroPallet',
          120000,80000,215000,
          0,
          120000,80000,215000,
          400000
          ));
      
  }
  
  function printResults($packer) {
      $packedBoxes = $packer->pack();
      
      foreach ($packedBoxes as $packedBox) {
          echo $packedBox->getBox()->getReference()
          . " (".$packedBox->getVolumeUtilisation()."%)"
              .PHP_EOL;
              $packedItems = $packedBox->getItems();
              foreach ($packedItems as $packedItem) {
                  echo "  " .$packedItem->getItem()->getDescription() .PHP_EOL;
              }
      }
  }
  
  function main() {
      
      echo "----------Test 1 with rotation" .PHP_EOL;
      $packer = new Packer();
      $packer->setMaxBoxesToBalanceWeight(0);
      addBoxes($packer);
      addItems1($packer, 6);
      printResults($packer);

      echo "----------Test 1 not rotation" .PHP_EOL;
      $packer = new Packer();
      $packer->setMaxBoxesToBalanceWeight(0);
      addBoxes($packer);
      addItems1($packer, 1);
      printResults($packer);
      
      echo "----------Test 2 with rotation" .PHP_EOL;
      $packer = new Packer();
      $packer->setMaxBoxesToBalanceWeight(0);
      addBoxes($packer);
      addItems2($packer, 6);
      printResults($packer);

      echo "----------Test 2 not rotation" .PHP_EOL;
      $packer = new Packer();
      $packer->setMaxBoxesToBalanceWeight(0);
      addBoxes($packer);
      addItems2($packer, 1);
      printResults($packer);
  }
  
  main();```

And here the results:

>  ----------Test 1 with rotation
EuroPallet (86.3%)
  height 47
  height 47
  height 47
  height 47
  height 47
  height 47
  height 39
  height 39
  height 39
  height 39
  height 39
  height 33
  height 33
  height 33
  height 33
  height 33
  height 33
  height 33
  height 33
  height 33
----------Test 1 not rotation
EuroPallet (86.3%)
  height 47
  height 47
  height 47
  height 47
  height 47
  height 47
  height 39
  height 39
  height 39
  height 39
  height 39
  height 33
  height 33
  height 33
  height 33
  height 33
  height 33
  height 33
  height 33
  height 33
----------Test 2 with rotation
EuroPallet (64.2%)
  height 47
  height 47
  height 47
  height 47
  height 47
  height 47
  height 39
  height 39
  height 39
  height 39
  height 39
  height 33
  height 33
  height 33
EuroPallet (22.1%)
  height 33
  height 33
  height 33
  height 33
  height 33
  height 33
----------Test 2 not rotation
EuroPallet (64.2%)
  height 47
  height 47
  height 47
  height 47
  height 47
  height 47
  height 39
  height 39
  height 39
  height 39
  height 39
  height 33
  height 33
  height 33
EuroPallet (22.1%)
  height 33
  height 33
  height 33
  height 33
  height 33
  height 33

[dvdoug]

@CarlesRever yours is slightly different, this one is about the dimensional order of the boxes, yours seems to be about the dimensional order of the items - specifically for your particular set the library is guessing at the wrong "best" one when its allowed to rotate. But I'll add it to my list of non-optimal solutions to investigate

[CarlesRever]

Thanks for your work!!!