Trouble fitting items in a suitable box

[litecart]

Hi, I first want to say thank you. I appreciate the efforts behind attempting to provide a solution for this NP hard bin packing problem.

I have a use case where we are trying to pack 4 CDs and 2 cassettes in an envelope.

The items all fit in the envelope like this:

But the result gives us two envelopes. I need clues in understanding what we might be doing wrong.

header('Content-Type: text/plain');

try {

	$packer = new DVDoug\BoxPacker\Packer();

	$packer->addBox(
		new DVDoug\BoxPacker\Test\TestBox(
			reference: 'Le petite box',
			outerWidth: 340,
			outerLength: 350,
			outerDepth: 30,
			emptyWeight: 80,
			innerWidth: 220,
			innerLength: 310,
			innerDepth: 26,
			maxWeight: 2000
		)
	);

	$packer->addItem(
		item: new DVDoug\BoxPacker\Test\TestItem(
			description: 'CD',
			width: 130,
			length: 140,
			depth: 10,
			weight: 100,
			//allowedRotation: DVDoug\BoxPacker\Rotation::KeepFlat
			allowedRotation: DVDoug\BoxPacker\Rotation::BestFit
		),
		qty: 4
	);

	$packer->addItem(
		item: new DVDoug\BoxPacker\Test\TestItem(
			description: 'Cassette',
			width: 70,
			length: 110,
			depth: 17,
			weight: 100,
			//allowedRotation: DVDoug\BoxPacker\Rotation::KeepFlat
			allowedRotation: DVDoug\BoxPacker\Rotation::BestFit
		),
		qty: 2
	);

	$packedBoxes = $packer->pack();

	echo json_encode($packedBoxes, JSON_PRETTY_PRINT);

} catch (Exception $e) {
	die($e->getMessage());
}

[
    {
        "box": {
            "reference": "Le petite box",
            "innerWidth": 220,
            "innerLength": 310,
            "innerDepth": 26,
            "emptyWeight": 10,
            "maxWeight": 1918
        },
        "items": [
            {
                "x": 0,
                "y": 0,
                "z": 0,
                "width": 130,
                "length": 140,
                "depth": 10,
                "item": {
                    "description": "CD",
                    "width": 130,
                    "length": 140,
                    "depth": 10,
                    "weight": 100,
                    "allowedRotation": 2
                }
            },
            {
                "x": 130,
                "y": 0,
                "z": 0,
                "width": 70,
                "length": 110,
                "depth": 17,
                "item": {
                    "description": "Cassette",
                    "width": 70,
                    "length": 110,
                    "depth": 17,
                    "weight": 100,
                    "allowedRotation": 2
                }
            },
            {
                "x": 0,
                "y": 140,
                "z": 0,
                "width": 70,
                "length": 110,
                "depth": 17,
                "item": {
                    "description": "Cassette",
                    "width": 70,
                    "length": 110,
                    "depth": 17,
                    "weight": 100,
                    "allowedRotation": 2
                }
            }
        ]
    },
    {
        "box": {
            "reference": "Le petite box",
            "innerWidth": 220,
            "innerLength": 310,
            "innerDepth": 26,
            "emptyWeight": 10,
            "maxWeight": 1918
        },
        "items": [
            {
                "x": 0,
                "y": 0,
                "z": 0,
                "width": 130,
                "length": 140,
                "depth": 10,
                "item": {
                    "description": "CD",
                    "width": 130,
                    "length": 140,
                    "depth": 10,
                    "weight": 100,
                    "allowedRotation": 2
                }
            },
            {
                "x": 0,
                "y": 140,
                "z": 0,
                "width": 130,
                "length": 140,
                "depth": 10,
                "item": {
                    "description": "CD",
                    "width": 130,
                    "length": 140,
                    "depth": 10,
                    "weight": 100,
                    "allowedRotation": 2
                }
            },
            {
                "x": 0,
                "y": 0,
                "z": 10,
                "width": 140,
                "length": 130,
                "depth": 10,
                "item": {
                    "description": "CD",
                    "width": 130,
                    "length": 140,
                    "depth": 10,
                    "weight": 100,
                    "allowedRotation": 2
                }
            }
        ]
    }
]

[dvdoug]

Hi @litecart

The particular dimensions here are exposing an edge case that the current algorithm doesn't handle, so this is a library "bug" (noting that there simply is no algorithm that guarantees optimal packing every time other than brute-forcing the world)

What's happening here internally is this:

A first iteration is run

• CD is packed first. The used height is 10/10
• Cassette is packed next. The used height is now 17/17

We go back to the start, set a max allowable height of 17 (to allow for potential stacking, BUT)

• CD is packed first. Used height is 10/17. Can we pack another CD -> NO, only 7 remaining depth on this layer
• Cassette is packed next. Used height is 17/17. Can we pack another -> NO, 0 remaining depth on this layer

Start a new layer
Available height is 9 (26 - 17). Can we pack a CD -> NO

If the depth of the cassette is changed to 16, it all fits
If the depth of the envelope is changed to 27 it all fits
If you trick BoxPacker by packing a 2 double-CDs (130x140x20), it all fits

[dvdoug]

(side note, I didn't know you could still buy cassettes 🤯)

I've added this example to the test suite as a known non-optimal case, so if I can think of a way to tweak the algorithm I will)

[litecart]

That is unfortunate. But thank you for providing a good explanation in letting us understand what is happening.

It sounds like there is some linear thinking to this algorithm. I do have ideas. What if each item processed (longest items first) traded a free space 3D-rectangle against 3 smaller rectangle spaces (the leftovers). Every iteration would see if there is a leftover suitable and trade that again for 3 more leftovers. I hope that made any sense? You are the expert on this, I'm just trying to provide a thought.

(Yes, LP and cassettes is appearantly a thing in the fan merchandise business)

/Tim