My data using only four parts:
Container Size: | length | width | height |  
  | 100 | 36 | 5 |  
 
Part Num | qty | width | length | height
1 1 18 90 1
2 1 18 90 1
3 1 36 3 1
4 1 36 3 1

My results:
Placement of '1' is @ (0, 0, 0)
Placement of '2' is @ (0, 18, 0)
Placement of Box '3' is @ (0, 0, 1)
Placement of Box '4' is @ (37, 0, 1)

All parts should fit on single layer

There is usually a lot common between sibling permutations and rotations. Reuse both so that less work must be performed.

• Let the PermutationRotationIterator return the index of the first diff
• Figure out how to reuse (reverse?) the previous work based on that diff

Hi

Is it possible to get more usage examples maybe a bit more detailed steps to how add and calculate the content? The lines in the readme is very minimal and does not give a sense of what cna be done with the library.

thanks

I am calling:

Packager myPackager = new BruteForcePackager(containers, rotate3d, binarySearch);

where
boolean rotate3d = false;
boolean binarySearch = true;

and
List containers = new ArrayList();

and
containers.add(Dimension.newInstance(294, 46, 94));

I then call:
long deadline = System.currentTimeMillis() + 70000;
match = myPackager.pack(piecesToPutInContainer, deadline);

where
List piecesToPutInContainer = new ArrayList();
and

piecesToPutInContainer has size 2
and

piecesToPutInContainer.get(0) has
count=2
and
box = Box [name=null, width=98, depth=45, height=28, volume=123480]

and

piecesToPutInContainer.get(1) has
count=2
and
box = Box [name=null, width=98, depth=45, height=93, volume=410130]

These 4 pieces in total shouldfit in the container above....and yet the BruteForcePackager object returns
Container match = null

which I interpret to mean that the algorithm couldn't find a way to fit these in.

Why doesn't it find a solution?

Thanks for your help with this.

Best regards, Charlie

Considering the three-dimensional container packing problem with multiple unloading areas, the delivery vehicle needs to distribute some pack to different unloading areas in the same park. Now we need to box these boxes in the order of the unloading area. The packing rules are: “first out and then install”, ie, the first delivery is placed on the outermost side.

Packager constructors are a bit hairy, add a few builders.

The following test will fail with an ArrayOutOfBoundsException:

	@Test
	public void testBlowsUpWithArrayOutOfBounds() {
		List<Dimension> containers = Arrays.asList(
			new Dimension("2", 330, 222, 121),
			new Dimension("4", 330, 235, 225)
		);

		List<BoxItem> items = Arrays.asList(
			new BoxItem(new Box(105, 105, 293), 1),
			new BoxItem(new Box(92, 94, 255), 1),
			new BoxItem(new Box(105, 70, 60), 2)
		);

		BruteForcePackager packer = new BruteForcePackager(containers);
		packer.pack(items);
	}

It looks like in the PermutationRotationIterator class, nextRotation is setting the rotation array differently from the way that its used in the get and isWithinHeight methods.

First I wanted to thank you again @skjolber for this library which we are using daily in production. I had a look recently at the performance and I'm impressed when it packs almost 100 products in less than 1ms.

We are now considering integrating it in another area of our software where we are planning complete trips for a deliverer and thus we need to check if all products for several orders fit in its truck.

The algorithm is pretty complex, but what matters here is that we insert a few packets in the container, then a few more, try something else ...
I think we could benefit a lot in terms of performance if we had a slight change in the API to start packing from a "half-filled" container.

More formally, if the method pack would have a common type between its arguments and return type, to provide a hint (or constraint) with already positioned products.

For instance:
public LAFFResult pack(List<Box> containerProducts, Container targetContainer, LAFFResult packHint, BooleanSupplier interrupt)

There is probably a way to do it using LAFFAdapter but I'm not sure how to use it.

What do you think ?

I would like to confirm does the Level height get from previous highest box height.

I tried with my testing data in this program compare with real user operation in container packing, i find there is some free space cannot be used.

Would you please see the below?

In this example, number of containers is 1 but algorithm return 2.
Maybe recursivity is not correct? The problem is that a box of high=112 is in the second level of container one, when can be put on the level one, position 64x34, to optimize.

  List<Container> containers = new ArrayList<>();
  containers.add(new Container(128, 55, 224, 0));
  LargestAreaFitFirstPackager packager = new LargestAreaFitFirstPackager(containers, false, false, true);

  List<BoxItem> products = new ArrayList<>();
	
products.add(new BoxItem(new Box("a", 32, 17, 112, 0), 6));
    products.add(new BoxItem(new Box("b", 27, 37, 37, 0), 6)); 
    products.add(new BoxItem(new Box("c", 35 , 54, 33, 0), 2));

  List<Container> fits = packager.packList(products, Integer.MAX_VALUE, Long.MAX_VALUE);

Dear skjolber,

Thanks for this great code!
I had some problems with using your code when the dimensions are getting bigger. (working with mm) At that point, the code is not running anymore. I found out that the problem was caused by the fact that when volume = depth * width * height is bigger as what an int variable could handle. To solve this I changed the variable type of volume in the dimensions class to the long variable type and I also cast the depth, width and height to long. This solves the problem.

Best regards,
Thomas

When it is not possible to pack all the boxes in the container, the code returns NULL, is it possible to get the solution which occupies the most volume in the given container? (Perhaps specifying the boxes not packed)

The following code fails, putting all 4 items into box 3 which is has smaller volume than the sum of all items.
The equivalent code for LargestAreaFitFirstPackager.packList() chooses two boxes as expected.
BruteForcePackager.pack() produces null as expected.

@Test
    public void packList_shouldChooseBestContainers() {

        List<Container> boxes = new ArrayList<Container>() {{
            add(new Container("Box 1", 100, 100, 100, 20000));
            add(new Container("Box 2", 200, 200, 200, 20000));
            add(new Container("Box 3", 300, 300, 300, 20000));
        }};

        Packager packager = new BruteForcePackager(boxes);
        int maxContainers = 1000;

        List<BoxItem> products = new ArrayList<BoxItem>();
        products.add(new BoxItem(new Box("Product 1", 299, 299, 99, 25), 1));
        products.add(new BoxItem(new Box("Product 2", 299, 299, 99, 25), 1));
        products.add(new BoxItem(new Box("Product 3", 299, 299, 99, 25), 1));
        products.add(new BoxItem(new Box("Product 4", 99, 99, 99, 25), 1));
        List<Container> containers = packager.packList(products, maxContainers, System.currentTimeMillis() + 15000);
        assertTrue(containers.size() > 1);
    }

Hi skjolber,

I expected it should be like this, but you program seem cannot use the grey area.

I am calling:

Packager myPackager = new BruteForcePackager(containers, rotate3d, binarySearch);

where
boolean rotate3d = false;
boolean binarySearch = true;

and
List containers = new ArrayList();

and
containers.add(Dimension.newInstance(102, 82, 96));

I then call:
long deadline = System.currentTimeMillis() + 70000;
match = myPackager.pack(piecesToPutInContainer, deadline);

where
List piecesToPutInContainer = new ArrayList();
and

piecesToPutInContainer has size 2
and

piecesToPutInContainer.get(0) has
count=2
and
box = Box [name=null, width=97, depth=36, height=25, volume=87300]

and

piecesToPutInContainer.get(1) has
count=2
and
box = Box [name=null, width=102, depth=45, height=95, volume=436050]

These 4 pieces in total shouldfit in the container above....and yet the BruteForcePackager object returns
Container match = null

which I interpret to mean that the algorithm couldn't find a way to fit these in.

Why doesn't it find a solution?

Thanks for your help with this.

Best regards, Charlie

This test fails.
It should be impossible to stack 17 * 330x88x88 in a 320x490x290 box.

@Test
public void testStackThis() {
	List<Box> containers = new ArrayList<Box>();
	containers.add(new Box(320, 490, 290));
	Packager packager = new Packager(containers);

	List<Box> products1 = new ArrayList<Box>();

	products1.add(new Box("01", 330, 88, 88));
	products1.add(new Box("02", 330, 88, 88));
	products1.add(new Box("03", 330, 88, 88));
	products1.add(new Box("04", 330, 88, 88));
	products1.add(new Box("05", 330, 88, 88));
	products1.add(new Box("06", 330, 88, 88));
	products1.add(new Box("07", 330, 88, 88));
	products1.add(new Box("08", 330, 88, 88));
	products1.add(new Box("09", 330, 88, 88));
	products1.add(new Box("10", 330, 88, 88));
	products1.add(new Box("11", 330, 88, 88));
	products1.add(new Box("12", 330, 88, 88));
	products1.add(new Box("13", 330, 88, 88));
	products1.add(new Box("14", 330, 88, 88));
	products1.add(new Box("15", 330, 88, 88));
	products1.add(new Box("16", 330, 88, 88));
	products1.add(new Box("17", 330, 88, 88));

	Container fits1 = packager.pack(products1);
	assertNull(fits1);

}

Before running change
currentBox.getHeight() > box.getHeight() to -> currentBox.getHeight() < box.getHeight()
in Packager::88 (otherwise it won't fit all this stuff)

Images show placement of boxes, black dot is box center. Obviously some of the boxes intersect

Code to test.

java.util.List containers = new ArrayList();
containers.add(new Box("Plane", 1355, 285, 247));
Packager packager = new Packager(containers, false);
List products = new ArrayList();
products.add(new Box("72407",20,30,15));
products.add(new Box("74809",100,120,52));
products.add(new Box("71535",30,40,15));
products.add(new Box("74780",20,30,15));
products.add(new Box("74760_1",30,20,15));
products.add(new Box("74760_2",30,20,15));
products.add(new Box("74757",30,40,15));
products.add(new Box("74808",100,120,75));
products.add(new Box("73770",20,30,15));
products.add(new Box("74844_1",60,40,28));
products.add(new Box("74844_2",60,40,28));
products.add(new Box("74844_3",60,40,28));
products.add(new Box("74846",30,40,15));
products.add(new Box("73767_1",60,50,15));
products.add(new Box("73767_2",60,50,15));
products.add(new Box("74848",20,30,15));
products.add(new Box("74850",20,30,15));
products.add(new Box("74852",20,30,15));
products.add(new Box("74787",100,120,154));
products.add(new Box("74806_1",30,20,15));
products.add(new Box("74806_2",30,20,15));
products.add(new Box("74806_3",30,20,15));
products.add(new Box("74806_4",30,20,15));
products.add(new Box("74806_5",30,20,15));
products.add(new Box("74806_6",30,20,15));
products.add(new Box("74806_7",30,20,15));
products.add(new Box("74806_8",30,20,15));
products.add(new Box("74806_9",30,20,15));
products.add(new Box("74781_1",30,20,15));
products.add(new Box("74781_2",30,20,15));
products.add(new Box("74781_3",30,20,15));
products.add(new Box("74775_1",30,20,15));
products.add(new Box("74775_2",30,20,15));
products.add(new Box("74775_3",30,20,15));
products.add(new Box("74775_4",30,20,15));
products.add(new Box("74756",100,120,75));
products.add(new Box("74797",30,40,15));
products.add(new Box("74835",100,120,133));
products.add(new Box("74834",100,120,36));
products.add(new Box("74833",100,120,30));
products.add(new Box("74784_1",30,20,15));
products.add(new Box("74784_2",30,20,15));
products.add(new Box("74782",100,120,50));
products.add(new Box("74765",30,40,15));
products.add(new Box("74769",12,30,15));
products.add(new Box("74802",80,120,35));
products.add(new Box("73769",20,30,15));
products.add(new Box("74799_1",40,30,15));
products.add(new Box("74799_2",40,30,15));
products.add(new Box("74799_3",40,30,15));
products.add(new Box("74799_4",40,30,15));
products.add(new Box("74799_5",40,30,15));
products.add(new Box("74799_6",40,30,15));
products.add(new Box("74827",100,120,125));
products.add(new Box("74800_1",60,40,28));
products.add(new Box("74800_2",60,40,28));
products.add(new Box("74800_3",60,40,28));
products.add(new Box("74800_4",60,40,28));
products.add(new Box("74800_5",60,40,28));
products.add(new Box("74800_6",60,40,28));
products.add(new Box("74800_7",60,40,28));
products.add(new Box("74823",100,120,129));
products.add(new Box("74853",20,30,15));
products.add(new Box("74839_1",120,100,130));
products.add(new Box("74839_2",120,100,130));
products.add(new Box("74839_3",120,100,130));
products.add(new Box("74849_1",120,100,127));
products.add(new Box("74849_2",120,100,127));
products.add(new Box("74777_1",120,100,35));
products.add(new Box("74777_2",120,100,35));
products.add(new Box("72583",60,114,64));
products.add(new Box("74737",100,120,116));
products.add(new Box("74774_1",121,101,54));
products.add(new Box("74774_2",121,101,54));
products.add(new Box("74774_3",121,101,54));
products.add(new Box("74772",100,120,130));
products.add(new Box("72434",20,30,15));
products.add(new Box("74831",100,120,129));
products.add(new Box("74832",30,40,15));
products.add(new Box("74778_1",120,100,101));
products.add(new Box("74778_2",120,100,101));
products.add(new Box("74778_3",120,100,101));
products.add(new Box("74778_4",120,100,101));
products.add(new Box("74845_1",115,60,65));
products.add(new Box("74845_2",115,60,65));
products.add(new Box("74776_1",120,100,128));
products.add(new Box("74776_2",120,100,128));
products.add(new Box("72385",20,30,15));
products.add(new Box("74779_1",120,100,36));
products.add(new Box("74779_2",120,100,36));
products.add(new Box("74779_3",120,100,36));
products.add(new Box("74779_4",120,100,36));
products.add(new Box("72422",50,60,15));
products.add(new Box("BRE72563_1",40,30,15));
products.add(new Box("BRE72563_2",40,30,15));
products.add(new Box("BRE72563_3",40,30,15));
products.add(new Box("BRE72563_4",40,30,15));
products.add(new Box("72578",100,120,75));
products.add(new Box("71555",100,120,52));
products.add(new Box("74830_1",40,30,15));
products.add(new Box("74830_2",40,30,15));
products.add(new Box("74816",100,120,48));

Container pack = packager.pack(products);

Is there a way for me to integrate this code in a React App I have built?

Container : width - 22 depth - 22 height - 22 weight - 35 name - 5
BoxItems : width - 10 depth - 10 height - 10 weight - 10 name - A - Count 5
Max Containers = 10

For the above input,

Exception in thread "main" java.lang.IllegalArgumentException: Remaining weight is negative at -5
	at com.github.skjolberg.packing.Container.getFreeWeight(Container.java:125)
	at com.github.skjolberg.packing.LargestAreaFitFirstPackager.fit2D(LargestAreaFitFirstPackager.java:201)
	at com.github.skjolberg.packing.LargestAreaFitFirstPackager.pack(LargestAreaFitFirstPackager.java:148)
	at com.github.skjolberg.packing.LargestAreaFitFirstPackager$1.attempt(LargestAreaFitFirstPackager.java:457)
	at com.github.skjolberg.packing.Packager.packList(Packager.java:282)
	at Main.main(Main.java:38)

When the weight becomes negative, I guess the algorithm is not moving to the next container.
Can you please look into this?

Hi, I am working with 2 containers, is there a way to force to only use a container once? Here my example:

List<Container> containers = new ArrayList<Container>();
containers.add(new Container("c1",100, 100, 100, 0));
containers.add(new Container("c2",120, 120, 120, 0));

Packager packager =  LargestAreaFitFirstPackager.newBuilder().withContainers(containers).build();

List<BoxItem> products = new ArrayList<BoxItem>();
products.add(new BoxItem(new Box("b1", 90, 90, 90, 0), 1));
products.add(new BoxItem(new Box("b2", 80, 80, 80, 0), 1));

List<Container> fits =  packager.packList(products, containers.size(), System.currentTimeMillis() + 5000); 

The result is c1 twice. Is there a way to get c1 and c2?

I have a question about the intersection checking in class Placement.

What is the purpose of the first condition?

if (startX <= placement.getSpace().getX() && placement.getSpace().getX() <= endX) {
	return true;
}

And why do we need -1 for end value (e.g. endX, endY & endZ)?

Thanks again.

  List<Container> containers = new ArrayList<Container>();

  containers.add(new Container("Cont",30, 30, 30, 500)); // x y z and weight

  Packager packager = new LargestAreaFitFirstPackager(containers,false,true,true);

  List<BoxItem> products = new ArrayList<BoxItem>();

  products.add(new BoxItem(new Box("A", 10, 10, 10, 25), 10));

For the above code, I get the following placements.

Placement [0x0x0, width=10, depth=10, height=10]
Placement [0x10x0, width=10, depth=10, height=10]
Placement [0x20x10, width=10, depth=10, height=10]
Placement [10x0x0, width=10, depth=10, height=10]
Placement [10x10x0, width=10, depth=10, height=10]
Placement [10x20x10, width=10, depth=10, height=10]
Placement [20x0x0, width=10, depth=10, height=10]
Placement [20x10x10, width=10, depth=10, height=10]
Placement [20x20x10, width=10, depth=10, height=10]
Placement [0x0x10, width=10, depth=10, height=10]

May I know why is the Z value "10", but the level is still 0?

I thought the z-value would be 0 for all the cases as its still on level 0.

Some kind of visualization tool would be very helpful during development. Probably generation of some JSON file which can be feed into a javascript application.

It seems that LAFF does not consider the constraint of stability or basement of a box. When I visualize the solution, I found that some of the boxes are floating and without the basement.

Hi,

The link to LAFF (This Paper) in your documentation is not working. Can you please point me to algorithm paper?

Would you please help me with the following questions as well:
Does the code solve the multiple items trying to go to go multiple containers i.e 3D Multi Bin Packing?

Does the implementation gives provision to control the rotation of the items? My requirement is keep the height axis fixed, No rotation.

How are you using the quantity/weight in determining the fit? My requirement has Volume(length, width, height) as the only attribute of item and bin?

Can you also please provide some examples on how to understand the response (match)?

Thanks

Hi I do not really understand the function (heightUp / widthUp / depthUp). Could you please elaborate the function bit? Many thanks.

Hi!
In this Example and rotation 2D:

            containers = new ArrayList<>();
	containers.add(new Container(128, 55, 224, 0));
	packager = new LargestAreaFitFirstPackager(containers, false, true);

	products = new ArrayList<>();

            products.add(new BoxItem(new Box("a", 40, 55, 70, 0), 4));
	products.add(new BoxItem(new Box("b", 40, 54, 75, 0), 5));

RESULT:
Container [stackWeight=0, stackHeight=140, levels=[[Placement [0x0x0, width=40, depth=55, height=70], Placement [40x0x0, width=40, depth=55, height=70], Placement [80x0x0, width=40, depth=55, height=70]], [Placement [0x0x70, width=40, depth=55, height=70]], [Placement [0x0x140, width=40, depth=54, height=75], Placement [40x0x140, width=40, depth=54, height=75], Placement [80x0x140, width=40, depth=54, height=75]]], weight=0, width=128, depth=55, height=224, volume=1576960, name=null]

Container [stackWeight=0, stackHeight=0, levels=[[Placement [0x0x0, width=40, depth=54, height=75], Placement [40x0x0, width=40, depth=54, height=75]]], weight=0, width=128, depth=55, height=224, volume=1576960, name=null]

Why creates two containers? if all boxes can put in one. Is a mistake? Is easy to resolve?
Thanks!

see #41 for details and unit test

https://stackoverflow.com/questions/54222030/how-to-create-an-algorithm-that-will-continue-running-an-algorithm-until-success

see #36 for test cases in java

• when boxes are smaller than 46x46x57 so we should fit 8 of them in a volume of 92x92x114 but we fail to fit only 5
• when boxes are smaller than 18x20x18 so we should fit 6 of them in a volume of 36x60x18 but we fail to fit only 5

Hi,
I have got 2 bins of dimensions, 145x147x145 and 145x147x145 respectively.
Below are my items with dimensions in the order length x breadth x height
100 x 70 x 90
80 x 75 x 90
60 x 75 x 80
I expect these to be packed in a single bin but 2 of them are packing in one bin and other in a separate bin using LargestAreaFitFirstPackager.
Is there any parameter to be set before moving further

If I understand it right, this unit test is failing but it should pass

@Test
public void testFreeSpace() {
    List<Container> containerList = Collections.singletonList(
            new Container(50, 50, 50, 50)
    );

    List<BoxItem> boxList = new ArrayList<>();
    boxList.add(new BoxItem(new Box(25, 25, 25, 50)));

    Packager packager = new LargestAreaFitFirstPackager(containerList, false, true, true);

    Container containerPack = packager.pack(boxList);
    Dimension freeSpace = containerPack.getFreeSpace();

    System.out.println(freeSpace);

    Assert.assertEquals(25, freeSpace.getDepth());
    Assert.assertEquals(25, freeSpace.getHeight());
    Assert.assertEquals(25, freeSpace.getWidth());
    Assert.assertEquals(62500, freeSpace.getVolume());

}

If I place a box with half the size (and volume) of the container I expect the free space to be the other remaining half but in this case only the height and volume seems to be calculated correctly (depth and width have wrong values)

println is printing to the console:
Dimension [width=50, depth=50, height=25, volume=62500]

Where
width=50 ❌
depth=50 ❌
height=25 🆗
volume=62500 🆗

I expected something like:
Dimension [width=25, depth=25, height=25, volume=62500]

PS; This behavior also happens with more than one BoxItem

AS mentioned in the readme, the 3d rotation should be enabled by default in the LAFF-algorithm. But using the builder pattern, the flag LargestAreaFitFirstPackagerBuilder#rotate3D is set to false through the default initialization.

This or the readme should be changed to prevent confusion.

The latest on mvn central is 1.2.5, what happened to releases up to 1.2.9 ?

Input:

Packager packager = new Packager(ImmutableList.of(new Dimension("Plane", 1335, 285, 247)), false);
List products = new ArrayList<>();
products.add("72407",20,30,15);
products.add("74809",100,120,52);
products.add("71535",30,40,15);
products.add("74780",20,30,15);
products.add("74760_1",30,20,15);
products.add("74760_2",30,20,15);
products.add("74757",30,40,15);
products.add("74808",100,120,75);
products.add("73770",20,30,15);
products.add("74844_1",60,40,28);
products.add("74844_2",60,40,28);
products.add("74844_3",60,40,28);
products.add("74846",30,40,15);
products.add("73767_1",60,50,15);
products.add("73767_2",60,50,15);
products.add("74848",20,30,15);
products.add("74850",20,30,15);
products.add("74852",20,30,15);
products.add("74787",100,120,154);
products.add("74806_1",30,20,15);
products.add("74806_2",30,20,15);
products.add("74806_3",30,20,15);
products.add("74806_4",30,20,15);
products.add("74806_5",30,20,15);
products.add("74806_6",30,20,15);
products.add("74806_7",30,20,15);
products.add("74806_8",30,20,15);
products.add("74806_9",30,20,15);
products.add("74781_1",30,20,15);
products.add("74781_2",30,20,15);
products.add("74781_3",30,20,15);
products.add("74775_1",30,20,15);
products.add("74775_2",30,20,15);
products.add("74775_3",30,20,15);
products.add("74775_4",30,20,15);
products.add("74756",100,120,75);
products.add("74797",30,40,15);
products.add("74835",100,120,133);
products.add("74834",100,120,36);
products.add("74833",100,120,30);
products.add("74784_1",30,20,15);
products.add("74784_2",30,20,15);
products.add("74782",100,120,50);
products.add("74765",30,40,15);
products.add("74769",12,30,15);
products.add("74802",80,120,35);
products.add("73769",20,30,15);
products.add("74799_1",40,30,15);
products.add("74799_2",40,30,15);
products.add("74799_3",40,30,15);
products.add("74799_4",40,30,15);
products.add("74799_5",40,30,15);
products.add("74799_6",40,30,15);
products.add("74827",100,120,125);
products.add("74800_1",60,40,28);
products.add("74800_2",60,40,28);
products.add("74800_3",60,40,28);
products.add("74800_4",60,40,28);
products.add("74800_5",60,40,28);
products.add("74800_6",60,40,28);
products.add("74800_7",60,40,28);
products.add("74823",100,120,129);
products.add("74853",20,30,15);
products.add("74839_1",120,100,130);
products.add("74839_2",120,100,130);
products.add("74839_3",120,100,130);
products.add("74849_1",120,100,127);
products.add("74849_2",120,100,127);
products.add("74777_1",120,100,35);
products.add("74777_2",120,100,35);
products.add("72583",60,114,64);
products.add("74737",100,120,116);
products.add("74774_1",121,101,54);
products.add("74774_2",121,101,54);
products.add("74774_3",121,101,54);
products.add("74772",100,120,130);
products.add("72434",20,30,15);
products.add("74831",100,120,129);
products.add("74832",30,40,15);
products.add("74778_1",120,100,101);
products.add("74778_2",120,100,101);
products.add("74778_3",120,100,101);
products.add("74778_4",120,100,101);
products.add("74845_1",115,60,65);
products.add("74845_2",115,60,65);
products.add("74776_1",120,100,128);
products.add("74776_2",120,100,128);
products.add("72385",20,30,15);
products.add("74779_1",120,100,36);
products.add("74779_2",120,100,36);
products.add("74779_3",120,100,36);
products.add("74779_4",120,100,36);
products.add("72422",50,60,15);
products.add("BRE72563_1",40,30,15);
products.add("BRE72563_2",40,30,15);
products.add("BRE72563_3",40,30,15);
products.add("BRE72563_4",40,30,15);
products.add("72578",100,120,75);
products.add("71555",100,120,52);
products.add("74830_1",40,30,15);
products.add("74830_2",40,30,15);
products.add("74816",100,120,48);

final Container pack = packager.pack(products);

Exception in thread "AWT-EventQueue-0" java.lang.IllegalArgumentException
at com.github.skjolberg.packing.Container.getRemainigFreeSpace(Container.java:52)
at com.github.skjolberg.packing.Packager.pack(Packager.java:73)

In this example the best packing is product A,B,D in the first level and product C in the second level. But it pack C,D in the first level and A,B in the second level.
If I extract product 'C' then can bin all products (A, B and D) in the first level (option 3Drotate = false):

            List<Container> containers = new ArrayList<>();
	containers.add(new Container(128, 55, 244, 0));
	
	LargestAreaFitFirstPackager packager = new LargestAreaFitFirstPackager(containers);

	List<BoxItem> products = new ArrayList<>();

	products.add(new BoxItem(new Box("A", 52, 54, 125, 0), 1));
	products.add(new BoxItem(new Box("B", 26, 54, 106, 0), 1));
	products.add(new BoxItem(new Box("C", 64, 54, 105, 0), 1));
	products.add(new BoxItem(new Box("D", 32, 54, 105, 0), 1));

	List<Container> fits = packager.packList(products, Integer.MAX_VALUE, Long.MAX_VALUE);

It would be nice to have a parallel version of the packagers. Would it be possible?

Using the java 8 version, my code

final List<BoxItem> parcels = Arrays.asList(
	new BoxItem(new Box(430, 390, 40, 0), 2),
	new BoxItem(new Box(430, 390, 730, 0))
);

final List<Container> containers = Arrays.asList(
	new Container(440, 400, 90, 0),
	new Container(440, 400, 190, 0),
	new Container(440, 400, 380, 0),
	new Container(440, 400, 740, 0)
);

Packager packager = BruteForcePackager.newBuilder()
	.withContainers(containers)
	.build();

final List<Container> usedContainers = packager.packList(parcels, 3, () -> false);

produces the following IndexOutOfBoundsException

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 1, Size: 1
at java.util.ArrayList$SubList.rangeCheck(ArrayList.java:1225)
at java.util.ArrayList$SubList.get(ArrayList.java:1042)
at com.github.skjolber.packing.BruteForcePackager.fit2D(BruteForcePackager.java:194)
at com.github.skjolber.packing.BruteForcePackager.pack(BruteForcePackager.java:148)
at com.github.skjolber.packing.BruteForcePackager.pack(BruteForcePackager.java:72)
at com.github.skjolber.packing.BruteForcePackager$BruteForceAdapter.attempt(BruteForcePackager.java:536)
at com.github.skjolber.packing.Packager.packList(Packager.java:279)
at Main.main(Main.java:26)

In fit2d, the methods placements list parameter has lesser fields than the passed index demands. I don't know what the expected behaviour is in that case or if this error is only reproducable in the Java 8 version.

Im not expecting the missing weights (which are not important in my use case) to be a problem. The implementation of the LAFF packager produces an output.

see #167 with unit test

Hello @skjolber,

I tried to add test case as below but it failed.

Version Tag: 3d-bin-container-packing-1.0.7
Test Case : LargestAreaFitFirstPackager3DTest.java

   @Test
public void testStackingMultipleLayersFor3Column() {
	
	List<Box> containers = new ArrayList<Box>();
	containers.add(new Box(30, 10, 6)); // 1800
	LargestAreaFitFirstPackager packager = new LargestAreaFitFirstPackager(containers);
	
	List<BoxItem> products = new ArrayList<BoxItem>();
	
	// 1
	products.add(new BoxItem(new Box("A", 10, 10, 6), 1)); // 600
	// 2 
	products.add(new BoxItem(new Box("D", 10, 10, 2), 3)); // 200 200 200
	Container fits = packager.pack(products);
	assertNotNull(fits);
}

I've plot the box from matplotlib and got this image. So I doubt that the box is placed in the air!! So is this bug and why it placed the box like that? Thank you

It would be easier to publish releases to Bintray and Maven Central from the travis CI build.

A suggestion to set this up is to take inspiration from what my friend @aneveux has done in this project with a similar setup : https://github.com/WriteThemFirst/approvals-java

Is there a way to get an ouput which specifies the volume occupied by the boxes?

Hi there, testing your code I've noticed that the container's volume order makes diference in the result. Follow a snip that reproduces the issue. It should fit the items in a big box and a small box

public void testDescendingOrder() { // it fails
    List<Container> containers = new ArrayList<Container>();
    containers.add(new Container("BigBox", 400, 400, 400, 10000));
    containers.add(new Container("SmallBox", 200, 200, 200, 10000));
    Packager packager = LargestAreaFitFirstPackager.newBuilder().withContainers(containers).build();
    List<BoxItem> products = new ArrayList<BoxItem>();
    products.add(new BoxItem(new Box("Foot", 200, 200, 200, 1000), 2));
    products.add(new BoxItem(new Box("Leg", 200, 200, 200, 1000), 7));
    List<Container> fits = packager.packList(products, 999, System.currentTimeMillis() + 5000);
    Assert.assertEquals("It should be a big box", fits.get(0).getName(), "BigBox"); // ok
    Assert.assertEquals("It should be a small box", fits.get(1).getName(), "SmallBox"); // fails
}

Thank you!!

Hi,

In my usage of the library, I've encounter the need to get the space actually used by the objects packed in the container. (as the smallest container which can hold the items)

I managed to do it, but it's non trivial because height is processed differently than the other 2 dimensions.

Would you agree to have this as a method Container.getUsedSpace returning a Dimension ?

While working on the project, I noticed that a lot of details are exposed to classes which depend on this API.

I suggest to hide the implementation details in a separate package with lower visibility and only keep the really useful in the main package.

Something like

• com.github.skjolberg.packing with public classes
  • Packager
  • Dimension, BoxItem
• com.github.skjolberg.packing.impl with package-protected classes
  • maybe Level, Placement can be moved here
  • BruteForcePackager, LAFFPackager (with a Factory in the public package)

What do you think ? Would you like another PR with these changes ?

A nice feature is to allow some boxes to be positioned beforehand in some specific places (pre defined by the user) and then pack the remaining boxes in the remaining free spaces.

Example,

• We have a container 50x50x50
• We specify that in position (x,y,z) 10, 0, 10 we already have a box with dimension 5, 5, 5
• We have 2 boxes to be packed with dimensions 10, 10, 10 and 15, 15, 15
• Now we ask the library to pack the two boxes above but to take in consideration that position 10, 0, 10 is already occupied with a box with dimension 5, 5, 5 and therefore to not place these two boxes there.

Did I make myself clear?

The current LAFF and brute-force packages do level-by-level 2D stacking. Basically they place a box within a free area, leaving two seperate areas for the algorithm to recursively place the next boxes.

The criteria for finding the best orientation and/or placement of the box is what the LAFF and brute force packagers do differently - which goes directly to the core of the problem and is hard to solve.

However the stacking itself in 3D should not be that difficult (famous last words), basically doing the same as in 2D just in more dimensions.

Links:

• 3D bin packing (inspiration, perhaps not the exact algorithm).

• 3D bin packing

• Space deframentation

• Another 3D bin packing

• Yet another Nice figures and perhaps promising.

I think it's a bug that when first box in a container needs to be placed with longest edge straight up that level is hard to fill.

Example in Groovy that fails.

int containerW = 100
int containerD = 100
int containerH = 300

def boxes = []
def box

box = new Box(1, 1, 300)
boxes << box
box = new Box(1, 1, 1)
boxes << box

List containers = new ArrayList()
containers.add(Dimension.newInstance(containerW, containerD, containerH))
Packager packager = new Packager(containers)
Container match = packager.pack(boxes)