Calculating the size of a box for multiple products for carrier module in prestashop

I am currently developing a carrier module for [Kuroneko][1] which is a door-to-door Japanese delivery company. This carrier, along with the weight, takes the size of the box into consideration. But it doe not use the volume, it would be too easy. It uses the sum of the three dimensions (height, weight and depth).

If you've got only one product to box, it's still easy but what happens when you need to box 2 products? Let's say you have two products of dimensions (x1,y1,z1) and (x2,y2,z2), how do you calculate the final box size X,Y,Z in a way you keep X+Y+Z minimal?

Here is my provisional solution, but tell me if there's a better way to calculate:
let m1 be the minimal dimension of the first product, min(x1,y1,z1) and m2 for the second. You have to account for rotations of the products in the box to fit them in the best way and thus define new dimensions nx,ny,nz for both products. Let's suppose that nx = m. If m = x then ny = y, nz = z, else if m=y then, ny= x, nz = z, else if m=z, ny = y, nz= x. The total box size thus become 2*nx,max(ny1,ny2),max(nz1,nz2).

But as far as I see, I don't think this method will work for more than 2 products. Any idea?

[1]:

[To see links please register here]

- Answer Demo [Here][1].
- You can check the code [here][2] (I added canvas to visualize)

Logic:

1. **Find** total Volume (w*h*d)[+(w*h*d)..]

2. **Collect** all possible width height and depth values, sort each from lowest to highest

3. **Find** all possible sum permutations for width, then for height, then for width

3a. **Example**: sum permutations for width ranges 1,2,3 would be 1, 2, 3, 4, 5, 6

3b. we need this because in no way could the final value for width be 1.5 for example based on the example (3a.)

4. **Find** all possible combinations of Width, Height and Depth based on the permutations calculated on (3.)

5. **Store** all combinations where the total volume is equal or greater than the total Volume from (1.)

5a. This is because it is not possible that the final volume could be less than the actual Volume (1.)

5b. For Volumes greater than (1.) it means that's dead space.
6. **Sort** all combinations from (5.) Ascending, the first result will be the most accurate Volume
7. It is possible that the most accurate volume still could have different dimensions

7a. **Example**: Volume 16 can be 2x2x4 or 4x4x1 or 2x1x8 or 16x1x1

7b. **Find** the sum of W+H+D for each and the smallest sum would be the even more accurate dimensions.

7c. Example from (7a.) 2+2+4 = 8, 4+4+1 = 9, 2+1+8 = 11, 16+1+1 = 18 .... So our script would choose 2 x 2 x 4


[1]:

[To see links please register here]

[2]:

[To see links please register here]

I was looking for this algorithm but the link is down, however i could find it using the wayback machine.

Anyway, i will post it here because it might be useful for someone else

<?php

$test = '1,2,3|4,2,1|0.1,0.9,0.01';

$dimensions = explode("|", $test);

//1. Find total volume
$volume = 0;
//2. Find WHD ranges
$widthRange = array();
$heightRange = array();
$depthRange = array();
foreach($dimensions as $dimension) {
list($width, $height, $depth) = explode(',', $dimension);

$volume += $width * $height * $depth;

$widthRange[] = $width;

$heightRange[] = $height;

$depthRange[] = $depth;
}

//3. Order the WHD ranges
sort($widthRange);
sort($heightRange);
sort($depthRange);

echo 'Volume: '.$volume.'<br />';
echo 'Width Range: '.implode(', ', $widthRange).'<br />';
echo 'Height Range: '.implode(', ', $heightRange).'<br />';
echo 'Depth Range: '.implode(', ', $depthRange).'<br />';

//4. Figure out every combination with WHD
$widthCombination = array();
$heightCombination = array();
$depthCombination = array();

function combination($list) {
$combination = array();
$total = pow(2, count($list));
for ($i = 0; $i < $total; $i++) {
$set = array();
//For each combination check if each bit is set
for ($j = 0; $j < $total; $j++) {
//Is bit $j set in $i?
if (pow(2, $j) & $i) $set[] = $list[$j];
}

if(empty($set) || in_array(array_sum($set), $combination)) {
continue;
}

$combination[] = array_sum($set);
}

sort($combination);

return $combination;
}

$widthCombination = combination($widthRange);
$heightCombination = combination($heightRange);
$depthCombination = combination($depthRange);

echo 'Width Combination: '.implode(', ', $widthCombination).'<br />';
echo 'Height Combination: '.implode(', ', $heightCombination).'<br />';
echo 'Depth Combination: '.implode(', ', $depthCombination).'<br />';

$stacks = array();
foreach($widthCombination as $width) {
foreach($heightCombination as $height) {
foreach($depthCombination as $depth) {
$v = $width*$height*$depth;
if($v >= $volume) {
$stacks[$v][$width+$height+$depth] = array($width, $height, $depth);
}
}
}
}

ksort($stacks);

foreach($stacks as $i => $dims) {
ksort($stacks[$i]);
foreach($stacks[$i] as $j => $stack) {
rsort($stack);
break;
}

break;
}

echo '<pre>'.print_r($stacks, true).'</pre>';

All the credit belongs to [Christian Blanquera][1]


[1]:

[To see links please register here]

The above algorithm do not work for dimensions:
`$test = '100,10,10|50,50,50';`
First result is:
```
(
[0] => 50
[1] => 60
[2] => 50
)
```

but the first product do not fit. Combination array should only include sizes sums that are greater or equal the size of the biggest dimension (Width Combination should not include 50).

Implemented the algorithm in python, translated the code by Macr1408, credit to the original author of the algorithm Christian Blanquera.

```python
from functools import reduce
from itertools import product

def combination(dim: list) -> list:
"""Calculate all possible sum permutations for a given list
of numbers.

Args:
dim (list): A list of numbers

Returns:
list: All possible sum permutations
"""
combination = []
total = pow(2, len(dim))
for i in range(total):
set_v = []
for j in range(total):
if (pow(2, j) & i):
set_v.append(dim[j])

if len(set_v) == 0 or sum(set_v) in combination:
continue

combination.append(sum(set_v))
return sorted(combination)

# dimensions => [(w1, h1, l1), (w2, h2, l2), ...]
def calculate_volumetric_total(dimensions: list[tuple[float, float, float]]) -> tuple:
"""Calculate the volumetric dimensions of the box needed to store products
with sizes stored as tuples of (width, height, length). Based on the following
algorithm:

1. Find total Volume (w*h*d)[+(w*h*d)..]
2. Collect all possible width height and depth values, sort each from lowest to highest
3. Find all possible sum permutations for width, then for height, then for width
3a. Example: sum permutations for width ranges 1,2,3 would be 1, 2, 3, 4, 5, 6
3b. we need this because in no way could the final value for width be 1.5 for example based on the example (3a.)
4. Find all possible combinations of Width, Height and Depth based on the permutations calculated on (3.)
5. Store all combinations where the total volume is equal or greater than the total Volume from (1.)
5a. This is because it is not possible that the final volume could be less than the actual Volume (1.)
5b. For Volumes greater than (1.) it means that's dead space.
6. Sort all combinations from (5.) Ascending, the first result will be the most accurate Volume
7. It is possible that the most accurate volume still could have different dimensions
7a. Example: Volume 16 can be 2x2x4 or 4x4x1 or 2x1x8 or 16x1x1
7b. Find the sum of W+H+D for each and the smallest sum would be the even more accurate dimensions.
7c. Example from (7a.) 2+2+4 = 8, 4+4+1 = 9, 2+1+8 = 11, 16+1+1 = 18 .... So our script would choose 2 x 2 x 4

Args:
dimensions (list[tuple[float, float, float]]): A list of all products/boxes
to store together in the form width, height, length.

Returns:
tuple: A tuple of width, height, length values representing the box needed to
store all the provided dimensions in.
"""
# 1
total_volume = sum([reduce(lambda x, y: x*y, t) for t in dimensions])

# 2, sorting happens when combining values
all_widths = [t[0] for t in dimensions]
all_heights = [t[1] for t in dimensions]
all_lengths = [t[2] for t in dimensions]

# 3
width_combination = combination(all_widths)
height_combination = combination(all_heights)
length_combination = combination(all_lengths)

# 4
vals = {}
for perm in product(width_combination, height_combination, length_combination):
# 5
volume = reduce(lambda x, y: x*y, perm)
if volume >= total_volume:
vals[sum(perm)] = perm

# 6
return vals[sorted(vals.keys())[0]]
```

Javascript implementation of the algorithm developed by Christian Blanquera.

Graphic [demo][1]

```javascript
/**
* Calculate all possible sum permutations for a given list of numbers
* @param list A list of numbers
* @return {*[]} All possible sum permutations
*/
function combination(list) {
let combination = [];
const total = Math.pow(2, list.length);

for (let i = 0; i < total; i++) {
const set = [];
//For each combination check if each bit is set
for (let j = 0; j < total; j++) {
//Is bit j set in i?
if (Math.pow(2, j) & i) {
set.push(list[j])
}
}

const sum = set.reduce((partialSum, a) => partialSum + a, 0);
if (set.length < 1 || combination.includes(sum)) continue;

combination.push(sum)
}

return combination.sort();
}

/**
* Calculate the volumetric dimensions of the box needed to store products
* with sizes stored as array of [width, height, length].
* @param dimensions A list of all products/boxes to store together in the form width, height, length.
* @return {{[p: string]: unknown}} A object of width, height, length values representing the box needed to
* store all the provided dimensions in.
*/
function calculateVolumetricTotal(dimensions) {
let totalVolume = 0
let dims = {
widthRange: [],
heightRange: [],
depthRange: []
}

// 1. Find total volume
// 2. Collect all possible width height and depth values
dimensions.forEach(dimension => {
const [width, height, depth] = dimension.map(x => parseFloat(x))
dims.widthRange.push(width)
dims.heightRange.push(height)
dims.depthRange.push(depth)
totalVolume += width * height * depth
})

// sorting happens when combining values
for (const dim in dims) {
dims[dim].sort()
}

/**
* 3. Find all possible sum permutations for width, then for height, then for width
* 3a. Example: sum permutations for width ranges 1,2,3 would be 1, 2, 3, 4, 5, 6
* 3b. we need this because in no way could the final value for width be 1.5 for example based on the example (3a.)
*/
const combinations = {
width: combination(dims.widthRange),
height: combination(dims.heightRange),
depth: combination(dims.depthRange)
}

/**
* 4. Find all possible combinations of Width, Height and Depth based on the permutations calculated on (3.)
*/
let stacks = {};
combinations.width.forEach(width => {
combinations.height.forEach(height => {
combinations.depth.forEach(depth => {
const v = width * height * depth;
/**
* 5. Store all combinations where the total volume is equal or greater than the total Volume
* 5a. This is because it is not possible that the final volume could be less than the actual Volume
* 5b. For Volumes greater than (1.) it means that's dead space.
*/
if (v >= totalVolume) {
stacks[v] = {}
stacks[v][width + height + depth] = [width, height, depth]
}
})
})
})

/**
* 6. Sort all combinations from (5.) Ascending,
* the first result will be the most accurate Volume
*/
return Object.fromEntries(
Object.entries(stacks).sort(([v1], [v2]) => v1 < v2 ^ 1),
)
}
```

[1]:

[To see links please register here]