search

dvdoug / BoxPacker

4D bin packing / knapsack problem solver
MIT License
612 stars 156 forks source link

I need to pack Items in 1 small box and 2 large and heavy box instead of 3 medium size box #6

Closed ssrgspdkt closed 10 years ago

ssrgspdkt commented 10 years ago

Hi I would like to change current method in this point "If more than 1 box is needed to accommodate all of the items, then aim for boxes of roughly equal weight (e.g. 3 medium size/weight boxes are better than 1 small light box and 2 that are large and heavy)"

where I need to edit?

dvdoug commented 10 years ago

Hi

You'd need to comment out the call here https://github.com/dvdoug/BoxPacker/blob/master/Packer.php#L103

Hope that helps, Doug

ssrgspdkt commented 10 years ago

Hi, thanks for your reply. I have tried. but no changes. please help me. did you get my idea?

you have added code to pick medium weight boxes instead of picking large boxes. I need to pick suitable largest box instead of medium boxes. Case :1 I have some products that can be suitable in one medium box.

Case 2: I have some products that can't pack all products in One largest box. so we need to choose one large box and pack allowed product,then we will check with remaining products and boxes. if remaining products could pack in 1 medium box , we will pack . else we will choose large box again to pack remaining products. please inform where i need to edit

dvdoug commented 10 years ago

Can you please post your sample code so I can take a look? It's hard to diagnose without it. Thanks, Doug

ssrgspdkt commented 10 years ago

<?php /**

/* * Outer length in mm * @return int / public function getInnerLength();

/**
 * Inner width in mm
 * @return int
 */
public function getInnerWidth();

/**
 * Outer depth in mm
 * @return int
 */
public function getInnerDepth();

/**
 * Total inner volume of packing in mm^3
 * @return int
 */
public function getInnerVolume();

/**
 * Max weight the packaging can hold in g
 * @return int
 */
public function getMaxWeight();

}

interface Item {

/**
 * Item SKU etc
 * @return string
 */
public function getDescription();

 /**
 * Item length in mm
 * @return int
 */
public function getLength();

/**
 * Item width in mm
 * @return int
 */
public function getWidth();

/**
 * Item depth in mm
 * @return int
 */
public function getDepth();

/**
 * Item weight in g
 * @return int
 */
public function getWeight();

/**
 * Item volume in mm^3
 * @return int
 */
public function getVolume();

}

class TestBox implements Box {

public function __construct($aReference, $aOuterLength,$aOuterWidth,$aOuterDepth,$aEmptyWeight,$aInnerWidth,$aInnerLength,$aInnerDepth,$aMaxWeight) {
  $this->reference = $aReference;
   $this->outerLength = $aOuterLength;     
  $this->outerWidth = $aOuterWidth;
  $this->outerDepth = $aOuterDepth;
  $this->emptyWeight = $aEmptyWeight;
  $this->innerWidth = $aInnerWidth;
  $this->innerLength = $aInnerLength;
  $this->innerDepth = $aInnerDepth;
  $this->maxWeight = $aMaxWeight;
  $this->innerVolume = $this->innerWidth * $this->innerLength * $this->innerDepth;
}

public function getReference() {
  return $this->reference;
}

public function getOuterLength() {
  return $this->outerLength;
}

public function getOuterWidth() {
  return $this->outerWidth;
}

public function getOuterDepth() {
  return $this->outerDepth;
}

public function getEmptyWeight() {
  return $this->emptyWeight;
}

 public function getInnerLength() {
  return $this->innerLength;
}

public function getInnerWidth() {
  return $this->innerWidth;
}

public function getInnerDepth() {
  return $this->innerDepth;
}

public function getInnerVolume() {
  return $this->innerVolume;
}

public function getMaxWeight() {
  return $this->maxWeight;
}

}

class TestItem implements Item {

public function __construct($aDescription,$aLength,$aWidth,$aDepth,$aWeight) {
  $this->description = $aDescription;
  $this->length = $aLength;
  $this->width = $aWidth;
  $this->depth = $aDepth;
  $this->weight = $aWeight;
  $this->volume = $this->width * $this->length * $this->depth;
}

public function getDescription() {
  return $this->description;
}

 public function getLength() {
  return $this->length;
}

public function getWidth() {
  return $this->width;
}

public function getDepth() {
  return $this->depth;
}

public function getWeight() {
  return $this->weight;
}

public function getVolume() {
  return $this->volume;
}

}

class PackedBox {

/**
 * Box used
 * @var Box
 */
protected $box;

/**
 * Items in the box
 * @var ItemList
 */
protected $items;

/**
 * Total weight of box
 * @var float
 */
protected $weight;

/**
 * Get box used
 * @return Box
 */
public function getBox() {
  return $this->box;
}

/**
 * Get items packed
 * @return ItemList
 */
public function getItems() {
  return $this->items;
}

/**
 * Get packed weight
 * @return int weight in grams
 */
public function getWeight() {

  if (!is_null($this->weight)) {
    return $this->weight;
  }

  $this->weight = $this->box->getEmptyWeight();
  $items = clone $this->items;
  foreach ($items as $item) {
    $this->weight += $item->getWeight();
  }
  return $this->weight;
}

public function __construct(Box $aBox, ItemList $aItemList) {
  $this->box = $aBox;
  $this->items = $aItemList;
}

}

class PackedBoxList extends \SplMinHeap {

/**
 * Average (mean) weight of boxes
 * @var float
 */
protected $meanWeight;

/**
 * Variance in weight between boxes
 * @var float
 */
protected $weightVariance;

/**
 * Compare elements in order to place them correctly in the heap while sifting up.
 * @see \SplMinHeap::compare()
 */
public function compare($aBoxA, $aBoxB) {
  $choice = $aBoxA->getItems()->count() - $aBoxB->getItems()->count();
  if ($choice === 0) {
    $choice = $aBoxB->getBox()->getInnerVolume() - $aBoxA->getBox()->getInnerVolume();
  }
  return $choice;
}

/**
 * Reversed version of compare
 * @return int
 */
public function reverseCompare($aBoxA, $aBoxB) {
  $choice = $aBoxB->getItems()->count() - $aBoxA->getItems()->count();
  if ($choice === 0) {
    $choice = $aBoxA->getBox()->getInnerVolume() - $aBoxB->getBox()->getInnerVolume();
  }
  return $choice;
}

/**
 * Calculate the average (mean) weight of the boxes
 * @return float
 */
public function getMeanWeight() {

  if (!is_null($this->meanWeight)) {
    return $this->meanWeight;
  }

  foreach (clone $this as $box) {
    $this->meanWeight += $box->getWeight();
  }

  return $this->meanWeight /= $this->count();

}

/**
 * Calculate the variance in weight between these boxes
 * @return float
 */
public function getWeightVariance() {

  if (!is_null($this->weightVariance)) {
    return $this->weightVariance;
  }

  $mean = $this->getMeanWeight();

  foreach (clone $this as $box) {
    $this->weightVariance += pow($box->getWeight() - $mean, 2);
  }

  return $this->weightVariance /= $this->count();

}

/**
 * Do a bulk insert
 * @param array $aBoxes
 */
public function insertFromArray(array $aBoxes) {
  foreach ($aBoxes as $box) {
    $this->insert($box);
  }
}

} class ItemList extends \SplMaxHeap {

/**
 * Compare elements in order to place them correctly in the heap while sifting up.
 * @see \SplMaxHeap::compare()
 */
public function compare($aItemA, $aItemB) {
  return $aItemA->getVolume() - $aItemB->getVolume();
}

/**
 * Get copy of this list as a standard PHP array
 * @return array
 */
public function asArray() {
  $return = array();
  foreach (clone $this as $item) {
    $return[] = $item;
  }
  return $return;
}

}

class BoxList extends \SplMinHeap {

/**
 * Compare elements in order to place them correctly in the heap while sifting up.
 * @see \SplMinHeap::compare()
 */
public function compare($aBoxA, $aBoxB) {
  return $aBoxB->getInnerVolume() - $aBoxA->getInnerVolume();
}

}

class Packer { // use LoggerAwareTrait;

/**
 * List of items to be packed
 * @var ItemList
 */
protected $items;

/**
 * List of box sizes available to pack items into
 * @var BoxList
 */
protected $boxes;

/**
 * Constructor
 */
public function __construct() {
  $this->items = new ItemList();
  $this->boxes = new BoxList();

//  $this->logger = new NullLogger();
}

/**
 * Add item to be packed
 * @param Item $aItem
 * @param int  $aQty
 */
public function addItem(Item $aItem, $aQty = 1) {
  for ($i = 0; $i < $aQty; $i++) {
    $this->items->insert($aItem);
  }

// $this->logger->log(LogLevel::INFO, "added {$aQty} x {$aItem->getDescription()}"); }

/**
 * Set a list of items all at once
 * @param \Traversable $aItems
 */
public function setItems($aItems) {
  if ($aItems instanceof ItemList) {
    $this->items = clone $aItems;
  }
  else if (is_array($aItems)) {
    $this->items = new ItemList();
    foreach ($aItems as $item) {
      $this->items->insert($item);
    }
  }
  else {
    throw new \RuntimeException('Not a valid list of items');
  }
}

/**
 * Add box size
 * @param Box $aBox
 */
public function addBox(Box $aBox) {
  $this->boxes->insert($aBox);
//  $this->logger->log(LogLevel::INFO, "added box {$aBox->getReference()}");
}

/**
 * Add a pre-prepared set of boxes all at once
 * @param BoxList $aBoxList
 */
public function setBoxes(BoxList $aBoxList) {
  $this->boxes = clone $aBoxList;
}

/**
 * Pack items into boxes
 *
 * @throws \RuntimeException
 * @return PackedBoxList
 */
public function pack() {
  $packedBoxes = $this->doVolumePacking();

  //If we have multiple boxes, try and optimise/even-out weight distribution
  if ($packedBoxes->count() > 1) {
 //   $packedBoxes = $this->redistributeWeight($packedBoxes);
  }

 // $this->logger->log(LogLevel::INFO, "packing completed, {$packedBoxes->count()} boxes");
  return $packedBoxes;
}

/**
 * Pack items into boxes using the principle of largest volume item first
 *
 * @throws \RuntimeException
 * @return PackedBoxList
 */
public function doVolumePacking() {

  $packedBoxes = new PackedBoxList;

  //Keep going until everything packed
  while ($this->items->count()) {
    $boxesToEvaluate = clone $this->boxes;
    $packedBoxesIteration = new PackedBoxList;

    //Loop through boxes starting with smallest, see what happens
    while (!$boxesToEvaluate->isEmpty()) {
      $box = $boxesToEvaluate->extract();
      $packedItems = $this->packBox($box, clone $this->items);
      if ($packedItems->count()) {
        $packedBoxesIteration->insert(new PackedBox($box, $packedItems));

        //Have we found a single box that contains everything?
        if ($packedItems->count() === $this->items->count()) {
          break;
        }
      }
    }

    //Check iteration was productive
    if ($packedBoxesIteration->isEmpty()) {
      throw new \RuntimeException('Item ' . $this->items->top()->getDescription() . ' is too large to fit into any box');
    }

    //Find best box of iteration, and remove packed items from unpacked list
    $bestBox = $packedBoxesIteration->top();
    $bestBoxItems = $bestBox->getItems()->asArray();
    $unpackedItems = $this->items->asArray();

    foreach ($bestBoxItems as $bestBoxItem) {
      foreach ($unpackedItems as $key => $unpackedItem) {
        if ($bestBoxItem == $unpackedItem) {
          unset($unpackedItems[$key]);
          break;
        }
      }
    }

    $this->items = new ItemList;
    foreach ($unpackedItems as $item) {
      $this->items->insert($item);
    }
    $packedBoxes->insert($bestBox);

  }

  return $packedBoxes;
}

/**
 * Given a solution set of packed boxes, repack them to achieve optimum weight distribution
 *
 * @param PackedBoxList $aPackedBoxes
 * @return PackedBoxList
 */
public function redistributeWeight(PackedBoxList $aPackedBoxes) {
  $targetWeight = $aPackedBoxes->getMeanWeight();
//  $this->logger->log(LogLevel::DEBUG,  "repacking for weight distribution, weight variance {$aPackedBoxes->getWeightVariance()}, target weight {$targetWeight}");

  $packedBoxes = new PackedBoxList;

  $overWeightBoxes = array();
  $underWeightBoxes = array();
  foreach ($aPackedBoxes as $packedBox) {
    $boxWeight = $packedBox->getWeight();
    if ($boxWeight > $targetWeight) {
      $overWeightBoxes[] = $packedBox;
    }
    else if ($boxWeight < $targetWeight) {
      $underWeightBoxes[] = $packedBox;
    }
    else {
      $packedBoxes->insert($packedBox); //target weight, so we'll keep these
    }
  }

  do { //Keep moving items from most overweight box to most underweight box
    $tryRepack = false;
   // $this->logger->log(LogLevel::DEBUG,  'boxes under/over target: ' . count($underWeightBoxes) . '/' . count($overWeightBoxes));

    foreach ($underWeightBoxes as $u => $underWeightBox) {
      foreach ($overWeightBoxes as $o => $overWeightBox) {
        $overWeightBoxItems = $overWeightBox->getItems()->asArray();

        //For each item in the heavier box, try and move it to the lighter one
        foreach ($overWeightBoxItems as $oi => $overWeightBoxItem) {
          if ($underWeightBox->getWeight() + $overWeightBoxItem->getWeight() > $targetWeight) {
            continue; //skip if moving this item would hinder rather than help weight distribution
          }

          $newItemsForLighterBox = clone $underWeightBox->getItems();
          $newItemsForLighterBox->insert($overWeightBoxItem);

          $newLighterBoxPacker = new Packer(); //we may need a bigger box
          $newLighterBoxPacker->setBoxes($this->boxes);
          $newLighterBoxPacker->setItems($newItemsForLighterBox);
          $newLighterBox = $newLighterBoxPacker->doVolumePacking()->extract();

          if ($newLighterBox->getItems()->count() === $newItemsForLighterBox->count()) { //new item fits
            unset($overWeightBoxItems[$oi]); //now packed in different box

            $newHeavierBoxPacker = new Packer(); //we may be able to use a smaller box
            $newHeavierBoxPacker->setBoxes($this->boxes);
            $newHeavierBoxPacker->setItems($overWeightBoxItems);

            $overWeightBoxes[$o] = $newHeavierBoxPacker->doVolumePacking()->extract();
            $underWeightBoxes[$u] = $newLighterBox;

            $tryRepack = true; //we did some work, so see if we can do even better
            usort($overWeightBoxes, array($packedBoxes, 'reverseCompare'));
            usort($underWeightBoxes, array($packedBoxes, 'reverseCompare'));
            break 3;
          }
        }
      }
    }
  } while ($tryRepack);

  //Combine back into a single list
  $packedBoxes->insertFromArray($overWeightBoxes);
  $packedBoxes->insertFromArray($underWeightBoxes);

  return $packedBoxes;
}

/**
 * Pack as many items as possible into specific given box
 * @param Box      $aBox
 * @param ItemList $aItems
 * @return ItemList items packed into box
 */
public function packBox(Box $aBox, ItemList $aItems) {
//  $this->logger->log(LogLevel::DEBUG,  "evaluating box {$aBox->getReference()}");

  $packedItems = new ItemList;
  $remainingDepth = $aBox->getInnerDepth();
  $remainingWeight = $aBox->getMaxWeight() - $aBox->getEmptyWeight();
  $remainingWidth = $aBox->getInnerWidth();
  $remainingLength = $aBox->getInnerLength();

  $layerWidth = $layerLength = $layerDepth = 0;
  while(!$aItems->isEmpty()) {

    $itemToPack = $aItems->top();

   if ($itemToPack->getDepth() > ($layerDepth ?$layerDepth: $remainingDepth) || $itemToPack->getWeight() > $remainingWeight) {
      $aItems->extract(); //ignore, move on
      continue;
    }

 //   $this->logger->log(LogLevel::DEBUG,  "evaluating item {$itemToPack->getDescription()}");
 //   $this->logger->log(LogLevel::DEBUG,  "remaining width :{$remainingWidth}, length: {$remainingLength}, depth: {$remainingDepth}");
  //  $this->logger->log(LogLevel::DEBUG,  "layerWidth: {$layerWidth}, layerLength: {$layerLength}, layerDepth: {$layerDepth}");

    $itemWidth = $itemToPack->getWidth();
    $itemLength = $itemToPack->getLength();

    $fitsSameGap = min($remainingWidth - $itemWidth, $remainingLength - $itemLength);
    $fitsRotatedGap = min($remainingWidth - $itemLength, $remainingLength - $itemWidth);

    if ($fitsSameGap >= 0 || $fitsRotatedGap >= 0) {

      $packedItems->insert($aItems->extract());
      $remainingWeight -= $itemToPack->getWeight();

      if ($fitsRotatedGap < 0 ||
          $fitsSameGap <= $fitsRotatedGap ||
          (!$aItems->isEmpty() && $aItems->top() == $itemToPack && $remainingLength >= 2 * $itemLength)) {
      //  $this->logger->log(LogLevel::DEBUG,  "fits (better) unrotated");
        $remainingLength -= $itemLength;
        $layerWidth += $itemWidth;
        $layerLength += $itemLength;
      }
      else {
       // $this->logger->log(LogLevel::DEBUG,  "fits (better) rotated");
        $remainingLength -= $itemWidth;
        $layerWidth += $itemLength;
        $layerLength += $itemWidth;
      }
      $layerDepth = max($layerDepth, $itemToPack->getDepth()); //greater than 0, items will always be less deep
    }
    else {
      if (!$layerWidth) {
    //    $this->logger->log(LogLevel::DEBUG,  "doesn't fit on layer even when empty");
        break;
      }

      $remainingWidth = min(floor($layerWidth * 1.1), $aBox->getInnerWidth());
      $remainingLength = min(floor($layerLength * 1.1), $aBox->getInnerLength());
      $remainingDepth -= $layerDepth;

      $layerWidth = $layerLength = $layerDepth = 0;
    //  $this->logger->log(LogLevel::DEBUG,  "doesn't fit, so starting next vertical layer");
    }
  }
 // $this->logger->log(LogLevel::DEBUG,  "done with this box");
  return $packedItems;
}

} /*

ssrgspdkt commented 10 years ago

HI I have package 22 largest box that is suitable for 2 products. but always packing using package2 only Thanks Senthilkumar

dvdoug commented 10 years ago

Fixed in master

dvdoug commented 10 years ago

Fixed in 1.2

ssrgspdkt commented 10 years ago

Thank you so much

ssrgspdkt commented 10 years ago

Hi Small problem occured. this code works correctly in exmaple code. but Item will change dynamically. at the time of changing item, always says "product is too large doensnt fit in any box" please fix that

dvdoug commented 10 years ago

Are you absolutely sure the item you're trying to fit does fit in the box? i.e. the weight isn't over capacity, and you've got the inner/outer dimensions correct?