Packing Math Problem (PHP Experts Only)

I’m trying to create a class that will pack products into boxes.

There are different products and box sizes.

If more than one product then they needed to be fitted in a box that will hold both items. if a box is not big enough then the order must be split into a new box.

This problem is also called:

3D Bin Packer
The Knapsack Problem

I have not found any PHP examples. This is what I have got so far:

Box class


final class Box {
	private $packaging_id;
	private $length;
	private $width;
	private $height;
	private $weight;
	private $product = array();
	
	function __construct($packaging_id, $length, $width, $height, $weight) {
		$this->packaging_id = $packaging_id;
		$this->length = $length;
		$this->width = $width;
		$this->height = $height;
	}
	
	function addProduct($product) {
		$this->product[] = $product;
	}
	
	function check($product) {
		$status = TRUE;
		
		if ($product['width'] > $width) {
		
		}
	}

	function getPrice() {
		$price = 0;
		
		foreach ($this->product as $product) {
			$price += $product['price'];
		}
		
		return $price;
	}
	
	function getWeight() {
		$weight = 0;
		
		foreach ($this->product as $product) {
			$weight += $product['weight'];
		}
		
		return $weight;
	}
}

Packaging Class

final class Packaging {
	private $box = array();
		
	function __construct($product, $package) {
		for ($i = 0; $i < count($product); $i++) {
			$product[$i]['volume'] = $product[$i]['length'] * $product[$i]['width'] * $product[$i]['height'];
		}

		for ($i = 0; $i < count($package); $i++) {
			$package[$i]['volume'] = $package[$i]['length'] * $package[$i]['width'] * $package[$i]['height'];
		}
		
		$sort_order = array();
	
		foreach ($package as $key => $value) {
      		$sort_order[$key] = $value['volume'];
    	}

    	array_multisort($sort_order, SORT_ASC, $package);		
		
		foreach ($product as $key => $value) {
			if (($package[$i]['volume'] > $product[$i]['volume']) && ($package[$i]['weight'] > $product[$i]['weight'])) {
				$box[$k] = array(
					'packaging_id'	=> $package[$i]['packaging_id'],
					'length'        => $package[$i]['length'],
					'width'         => $package[$i]['width'],
					'height'        => $package[$i]['height'],
					'product'       => $product[$i],
					'volume'        => $package[$i]['volume'] - $product[$i]['volume'],
					'weight'        => $package[$i]['weight'] - $product[$i]['weight']
				);
				
				$k++;
				
				continue;
			}			
			
			for ($j = 0; $j < count($package); $j++) {
				if ($package[$i]['volume'] < $product['volume']) {
					continue;
				}
			
				if ($package[$i]['weight'] < $product['weight']) {
					continue;
				}
			}
		}
		
		$box = array();
		
		$k = 0;
		
		for ($i = 0; $i < count($product); $i++) {
			if (!$box) {
				for ($j = 0; $j < count($package); $j++) {
					if ($package[$i]['volume'] < $product[$i]['volume']) {
						continue;
					}
					
					if ($package[$i]['weight'] < $product[$i]['weight']) {
						continue;
					}
					
					if (($package[$i]['volume'] > $product[$i]['volume']) && ($package[$i]['weight'] > $product[$i]['weight'])) {
						$box[$k] = array(
							'packaging_id'	   => $package[$i]['packaging_id'],
							'length'           => $package[$i]['length'],
							'width'            => $package[$i]['width'],
							'height'           => $package[$i]['height'],
							'product'          => $product[$i],
							'remaining_volume' => $package[$i]['volume'] - $product[$i]['volume'],
							'remaining_weight' => $package[$i]['weight'] - $product[$i]['weight']
						);
						
						$k++;
					}
				}
			} else {
				for ($j = 0; $j < count($box); $j++) {
				
				
				}
			}
		}
	}

    function addItem($length, $width, $height, $weight, $price = 0) {
        if ((float)$weight < 1.0) {
            $weight = 1;
        } else {
            $weight = round($weight, 1);
        }

	   $index = $this->items_qty;

		$this->item[$index]['length'] = ($length ? (string)$length : 0);
		$this->item[$index]['width'] = ($width ? (string)$width : 0);
		$this->item[$index]['height'] = ($height ? (string)$height : 0);
		$this->item[$index]['weight'] = ($weight ? (string)$weight : 0);
		$this->item[$index]['price'] = $price;

	   $this->items_qty++;
    }
}		

Data


$product_data = array();

$product_data[] = array(
	'product_id'    => 1,
	'name'          => 'Product 1',
	'quantity'      => 2,
	'price'         => 10,
	'length'        => 12,
	'width'         => 6,
	'height'        => 6,
	'weight'        => 1,
	'ready_to_ship' => false
);

$product_data[] = array(
	'product_id'    => 2,
	'name'          => 'Product 2',
	'quantity'      => 1,
	'price'         => 10,
	'length'        => 5,
	'width'         => 6,
	'height'        => 6,
	'weight'        => 1,
	'ready_to_ship' => false
);

$product_data[] = array(
	'product_id'    => 3,
	'name'          => 'Product 3',
	'quantity'      => 1,
	'price'         => 10,
	'length'        => 9,
	'width'         => 14,
	'height'        => 12,
	'weight'        => 1,
	'ready_to_ship' => false
);

$product_data[] = array(
	'product_id'    => 3,
	'name'          => 'Product 3',
	'quantity'      => 1,
	'price'         => 10,
	'length'        => 14,
	'width'         => 16,
	'height'        => 20,
	'weight'        => 1,
	'ready_to_ship' => false
);

$package_data = array();
						
$package_data[] = array(
	'packaging_id' => 1,
	'name'         => '9x8x9',
	'description'  => '9x8x9',
	'length'       => 9,
	'width'        => 8,
	'height'       => 9,
	'weight'       => 5
);

$package_data[] = array(
	'packaging_id' => 2,
	'name'         => '12x14x13',
	'description'  => '12x14x13',
	'length'       => 12,
	'width'        => 14,
	'height'       => 13,
	'weight'       => 10,
);

$package_data[] = array(
	'packaging_id' => 3,
	'name'         => '18x19x22',
	'description'  => '18x19x22',
	'length'       => 18,
	'width'        => 19,
	'height'       => 22,
	'weight'       => 25
);

$package_data[] = array(
	'packaging_id' => 3,
	'name'         => '25x29x28',
	'description'  => '25x29x28',
	'length'       => 25,
	'width'        => 29,
	'height'       => 28,
	'weight'       => 25
);

$package_data[] = array(
	'packaging_id' => 3,
	'name'         => '36x30x38',
	'description'  => '36x30x38',
	'length'       => 36,
	'width'        => 30,
	'height'       => 38,
	'weight'       => 25
);

error_reporting(E_ALL);

$packaging = new Packaging($product_data, $package_data);

echo '<pre>';
//print_r($package_data);
//print_r($empty_box_data);
print_r($packaging);
echo '</pre>';

Please help!

Weight is normally a consideration in this algorithm, yet you do not mention it. Do you want to consider a maximum weight per bin ?

yes

each packaging has a max weight limit.

updated code:


final class Box {
	private $packaging_id;
	private $length;
	private $width;
	private $height;
	private $max_weight;
	private $product = array();
	
	function __construct($packaging_id, $length, $width, $height, $max_weight) {
		$this->packaging_id = $packaging_id;
		$this->length = $length;
		$this->width = $width;
		$this->height = $height;
		$this->max_weight = $max_weight;
	}
	
	function addProduct($product) {
		$this->product[] = $product;
	}
	
	function getWeightTotal() {
		$weight = 0;
		
		foreach ($this->product as $product) {
			$weight += $product['weight'];
		}
		
		return $weight;
	}
	
	function getPriceTotal() {
		$price = 0;
		
		foreach ($this->product as $product) {
			$price += $product['price'];
		}
		
		return $price;
	}
}

final class Packaging {
	private $box = array();
		
	function __construct($product, $package) {
		for ($i = 0; $i < count($product); $i++) {
			$product[$i]['volume'] = $product[$i]['length'] * $product[$i]['width'] * $product[$i]['height'];
		}

		for ($i = 0; $i < count($package); $i++) {
			$package[$i]['volume'] = $package[$i]['length'] * $package[$i]['width'] * $package[$i]['height'];
		}
		
		$sort_order = array();
	
		foreach ($package as $key => $value) {
      		$sort_order[$key] = $value['volume'];
    	}

    	array_multisort($sort_order, SORT_ASC, $package);		

		foreach ($product as $key => $value) {
			if (($package[$i]['volume'] > $product[$i]['volume']) && ($package[$i]['weight'] > $product[$i]['weight'])) {
				$box[$k] = array(
					'packaging_id'	=> $package[$i]['packaging_id'],
					'length'        => $package[$i]['length'],
					'width'         => $package[$i]['width'],
					'height'        => $package[$i]['height'],
					'product'       => $product[$i],
					'volume'        => $package[$i]['volume'] - $product[$i]['volume'],
					'weight'        => $package[$i]['weight'] - $product[$i]['weight']
				);
				
				$k++;
				
				continue;
			}			
			
			for ($j = 0; $j < count($package); $j++) {
				if ($package[$i]['volume'] < $product['volume']) {
					continue;
				}
			
				if ($package[$i]['weight'] < $product['weight']) {
					continue;
				}
			}
		}
	}
}		


$product_data = array();

$product_data[] = array(
	'product_id'    => 1,
	'name'          => 'Product 1',
	'quantity'      => 2,
	'price'         => 10,
	'length'        => 12,
	'width'         => 6,
	'height'        => 6,
	'weight'        => 1,
);

$product_data[] = array(
	'product_id'    => 2,
	'name'          => 'Product 2',
	'quantity'      => 1,
	'price'         => 10,
	'length'        => 5,
	'width'         => 6,
	'height'        => 6,
	'weight'        => 1,
);

$product_data[] = array(
	'product_id'    => 3,
	'name'          => 'Product 3',
	'quantity'      => 1,
	'price'         => 10,
	'length'        => 9,
	'width'         => 14,
	'height'        => 12,
	'weight'        => 1,
);

$product_data[] = array(
	'product_id'    => 3,
	'name'          => 'Product 3',
	'quantity'      => 1,
	'price'         => 10,
	'length'        => 14,
	'width'         => 16,
	'height'        => 20,
	'weight'        => 1,
);

$package_data = array();
						
$package_data[] = array(
	'packaging_id' => 1,
	'name'         => '9x8x9',
	'description'  => '9x8x9',
	'length'       => 9,
	'width'        => 8,
	'height'       => 9,
	'max_weight'   => 5
);

$package_data[] = array(
	'packaging_id' => 2,
	'name'         => '12x14x13',
	'description'  => '12x14x13',
	'length'       => 12,
	'width'        => 14,
	'height'       => 13,
	'max_weight'   => 10,
);

$package_data[] = array(
	'packaging_id' => 3,
	'name'         => '18x19x22',
	'description'  => '18x19x22',
	'length'       => 18,
	'width'        => 19,
	'height'       => 22,
	'max_weight'   => 25
);

$package_data[] = array(
	'packaging_id' => 3,
	'name'         => '25x29x28',
	'description'  => '25x29x28',
	'length'       => 25,
	'width'        => 29,
	'height'       => 28,
	'max_weight'   => 25
);

$package_data[] = array(
	'packaging_id' => 3,
	'name'         => '36x30x38',
	'description'  => '36x30x38',
	'length'       => 36,
	'width'        => 30,
	'height'       => 38,
	'max_weight'   => 25
);

error_reporting(E_ALL);

$packaging = new Packaging($product_data, $package_data);

echo '<pre>';
print_r($packaging);
echo '</pre>';

How many items would typically go into a shipping? If the number is relatively low, you could brute-force it.

Sounds like dancing links.

how to brute force though?

Would it allow the pack to be flip to its side if there is remaining room?

Here is a fairly well commented process in C, maybe you could attempt to transpose it to PHP.

Basically calculate all possible combinations. Then sort them according to some set of rules and pick the highest ranking. A rule could for example be to minimise the number of packages. You can apply the sorting algorithm on the fly, so that you don’t need to store all the combinations in memory. Writing an algorithm to calculate the combinations should be relatively simple.

To support this, you’ll have to add a choice of orientation to the set of combinations. If all your items are rectangular, you’ll have three variations for each, in a 3d space.

I definitely tackle atleast some of this problem in SQL.

no shopping cart system I have found have a 3D binpacking system.

If this coding problem could be solved it would help giving the correct shipping amounts when shipping calculations are made. It could actually reduce the cost of customers orders by giving the correct number of packages being shipped.

3D Tetris :smiley:

Hmm thinking about why a 3d binpacking system hasn’t been developed.

Possibly because they could be more trouble than they’re worth?

If having to pack the manually, then either the packer would need to know what the the solution the packer programme solved it. Especially if allowing rotations, there is only 3 possible, but still with multiple products being packed into a single box seems like it could be time consuming, if it was too good at efficiently packing.

Think it would need to be simplified when there is more than 1 product to pack. A single product can be easily rotated to fit an appropriate box.

I suppose that the program could generate instructions for the packer.

But you’re right. The web shops I’ve made, either had free shipping or had a fixed cost for shipping. The cost were simply calculated into the price. After all - If you have to ship an additional package, it’s usually because there was a bigger sale, and thus bigger revenue.

Definitely a problem to solve at either end I think.

Work out the all the combinations of products that fit into each package.

For the individual products all the packaging solutions would be something like…

Returns all the products and which boxes they fit in


SELECT product_id, box_id
	FROM product p INNER JOIN box b
		ON (p.length < b.length AND p.width < b.width AND p.height < b.height)
		OR (p.height < b.length AND p.length < b.width AND p.width < b.height)
		OR (p.width < b.length AND p.height < b.width AND p.length < b.height)

For every two products and which boxes they fit in, assuming they are stacked on top of each other…
(would need more OR conditions to take into account rotations or other packing configurations)


SELECT p1.product_id, p2.product_id, b.box_id
	FROM
		product p1, product p2, box b
	WHERE p1.product_id <= p2.product_id
		AND
			MAX(p1.width, p2.width) < b.width
		AND
			MAX(p1.length, p2.length) < b.length
		AND
			p1.height + p2.height < b.height

And so on…

Once have the all that predetermined (can be done at new product, or new packaging time) it just seems a mapping of the a shoppers basket to boxes, which I think is simple iterative process, without any 3D math.


while have products-to-pack
{
      partial-solution = getPackingSolutionWhichHasMost(products-to-pack)
      Remove partial-solution-packed-products from products-to-pack
      add partial-solution to final-solution
}

Actually the latter problem could possibly done with Lucene or something… maybe. *Odd on the toilet thinking…

If get Lucene to index documents with packaging instructions configurations like…


use box #1
orange
orange
orange
orange

A shopping list would look like


orange
orange
orange

And asking Lucene for packaging instructions most like our shopping list, and picking the most similar would give at least a partial solution.

Well don’t need Lucene, just the knowledge of inverse document frequencies, cosine similarity, and so forth. And treating the shopping lists and packing solutions as vectors.

http://www.phpclasses.org/browse/package/2027.html

ok I think I have come up with a brute force method.

  1. Go through the list of products and filter out all the products that are 2 big to fit in any of the boxes and make them as there own box. e.g a table might be to big to fit in any standard box.

  2. Go through the remaining products and put the products in the box. find the box that accepts the most products.

  3. Remove the products in the box from the product list and start the step 2 again until there are no products left.

Available solutions already exist that I presume will do much better than any ones created in this thread. Please consult them and try to understand them before attempting to solve this problem. My previous reply has a link to a PHP class which should do what you want.

Finally, to anyone suggesting a brute-force algorithm: NO.

The link you posted just works on one dimension, filesizes… where the OP is working in 3 possibly 4.
width, height, length & weight.

Brute force is fine if can solve it once, and look up answers per request, as I outlined.

Pretty sure that the phpclass will be brute forcing it per request… though can’t see the source code as need to be registered.