Placing n 2D rectangular boxes of different shape into one 2D container (Java)

[Arianna Franchetto]

Hi everyone!

So I am implementing a Java program that shows the best combination of boxes to fit into a container. Just similar to the knapsack problem but with boxes and a container instead of objects and a rucksack. To do this, I have implemented a genetic algorithm. First, I create "Individuals": each "Individual" is an array that can contain 0 or 1 depending on the absence or presence of each box.
Example: Individual1 = [1,0,0,1,1]

in this individual the boxes n.2 and 3 are absent.
Then i create some more individuals, put them into a population and create n new generations starting from the first population in order to find eventually a population which is better than the first one. Anyway, this is not the problem. My problem is to find a suitable algorithm to calculate the fitness of each individual.
Initially I implemented it in such a way that the best combination of boxes is the one with the highest number of boxes, without the total volume and weight of these boxes exceeding the volume and weight of the container. Let's suppose we have two individuals
    individual1 [1,0,0,1,0]
    individual2 [1,1,1,0,1]
both not exceeding the container's weight and volume: the best one is individual2 because it stores more boxes: its fitness will be higher that individual1's fitness.
Now I want to complicate the problem by also taking into account the shape of the boxes (for now I consider them to be two-dimensional, so I take into account the shape of the base of the boxes, without considering how tall they are: I therefore imagine a container of indefinite height into which all the boxes can fit by height).
So now each box has a weight, a volume (i used these constraints to calculate the simplier version of the fitness) and also a width and a height (the two sides of the box base).

This is my code:

public float fitness2(TotBoxes totBoxes, Container container) {
  float fitness = 0;
  boolean boxIsIn = false;
  ArrayList<Box> boxInThisIndividual = new ArrayList<Box>();
  ArrayList<ContainerPlane> remainingArea = new ArrayList<ContainerPlane>();
  int widthContainer = container.getBase();
  int heightContainer = container.getAltezza();
  ContainerPlane startingContainer = new ContainerPlane(widthContainer, heightContainer);
  remainingArea.add(startingContainer);

  for (int i = 0; i < genes.length; i++) {
     if (genes[i] == 1) {
        boxInThisIndividual.add(totBoxes.getAllBoxes().get(i));
     }
  }
  System.out.println("There are " + boxInThisIndividual.size() + " boxes in this individual");
  //from now on i just consider the boxes really IN this individual, not the absent ones.

  //check that total volume of the boxes do not exceed the volume of the container
  int totalVolumeBoxes = 0;
  for (int i = 0; i < boxInThisIndividual.size(); i++) {
     totalVolumeBoxes = totalVolumeBoxes + boxInThisIndividual.get(i).getVolume();
  }
  System.out.println("Total volume boxes = " + totalVolumeBoxes);


  //check that total weight of the boxes do not exceed the weight of the container
  int totalWeightBoxes = 0;
  for (int i = 0; i < boxInThisIndividual.size(); i++) {
     totalWeightBoxes = totalWeightBoxes + boxInThisIndividual.get(i).getWeight();
  }
  System.out.println("Total weight boxes = " + totalWeightBoxes);



  if (totalVolumeBoxes > container.getMax_volume() || totalWeightBoxes > container.getMax_weight()) {
     fitness = 0;
     System.out.println("Fitness is 0 since total volume or weight exceeds volume or weight of the container");
  }

  //now i check that boxes can fit based to their area
  else {
     for (int i = 0; i < boxInThisIndividual.size(); i++) {
        Box box = boxInThisIndividual.get(i);

        int firstSideBox = box.getBase();
        int secondSideBox = box.getAltezza();
        for (int j = 0; j < remainingArea.size(); j++) {
           ContainerPlane remainingArea = remainingArea.get(j);
           var firstSidePlane = remainingArea.getBase();
           var secondSidePlane = remainingArea.getAltezza();
           if (firstSideBox < firstSidePlane && secondSideBox < secondSidePlane) {
              boxIsIn = true;


              //primo piano restante
              int firstSideFirstRemainingPlane = firstSidePlane - firstSideBox;
              //  int lato2PrimoPianoRestante = secondSidePlane;
              ContainerPlane firstRemainingPlane = new ContainerPlane(firstSideFirstRemainingPlane, secondSidePlane);

              //secondo piano restante
              int firstSideSecondRemainingPlane = secondSidePlane - secondSideBox;
              // int lato2SecondoPianoRestante = firstSidePlane;

              ContainerPlane secondRemainingPlane = new ContainerPlane(firstSideSecondRemainingPlane, firstSidePlane);
              remainingArea.remove(remainingArea);
              remainingArea.add(firstRemainingPlane);
              remainingArea.add(secondRemainingPlane);
              System.out.println(remainingArea);
              break;
           }
           else if (secondSideBox < firstSidePlane && firstSideBox < secondSidePlane) { //simulo la rotazione della box
              boxIsIn = true;
              remainingArea.remove(remainingArea);

              //primo piano restante
              int firstSideFirstRemainingPlane = firstSidePlane - secondSideBox;
              // int lato2PrimoPianoRestante = secondSidePlane;
              ContainerPlane firstRemainingPlane = new ContainerPlane(firstSideFirstRemainingPlane, secondSidePlane);
              //secondo piano restante
              int firstSideSecondRemainingPlane = secondSidePlane - firstSideBox;
              // int lato2SecondoPianoRestante = firstSidePlane;
              ContainerPlane secondRemainingPlane = new ContainerPlane(firstSideSecondRemainingPlane, firstSidePlane);
              remainingArea.add(firstRemainingPlane);
              remainingArea.add(secondRemainingPlane);
              System.out.println(remainingArea);
              break;
           }
           else if (firstSideBox > firstSidePlane && secondSideBox > secondSidePlane && secondSideBox > firstSidePlane && firstSideBox > secondSidePlane) {
              boxIsIn = false;
           }


       //more calculus in order to return the final fitness of the individual if all the boxes are stored into the container.
        }
     }

Note that the first "else if()" exchanges the first side of the box with the second side of the box and the second side of the box with the first side of the box, in order to simulate a rotation of the box (since it may be possible that a box doesn't fit if it's placed in a certain position but could fit if rotated, hence I have to check both orientations).
What this code does:
- i have created an arraylist called remainingArea in which, at the beginning, there's only the whole area of the container. Then
- i consider the first box to place: i check if its dimension are smaller than the container dimension
- if so, i split the available area into two new available areas: you can see that from the link to the photo below.
- i remove the initial area from the arraylist and i add the two new areas, and then i continue with the next box.
Now i thought this was working fine, but then i found a problem. To understand this problem it would be really helpful to check this visual representation of the problem.

Image here:

As seen by the figure, the algorithm works fine when i add new boxes that do not overlap the two remaining planes created after putting into the container the previous box. If the next box overlap the two remaining planes, I would need to modify both the previous remaining areas, and this is where I'm stuck.
I have thought about a "fast" solution to avoid this problem: to sort the boxes by height, so that after putting the first box, all the remaining boxes will have a smaller height, so that no more box will ever overlap the two remaining areas (hope this is clear).
But the problem of the overlapping remaining areas is still there if the algorithm reaches the first "else if" where i rotate the box in order to make it fit into the container: here, by exchanging first and second side of the box, it may still be possible that the next box overlaps the two areas.
How can i avoid this problem?

Thanks in advance

[Ira Go]

Could you please state the original problem?

[Arianna Franchetto]

This is the problem: i have an array of boxes:
[box1, box2, box3, box4, box5, box6, box7, box8, box9, box10]

Each box has a volume, a weight, a width and a height.

and many binary arrays that display different combination of boxes. Arrays are as long as many boxes i have: if i have 10 boxes, the binary arrays will be long 10.

binaryarrayOne = [1,1,0,0,0,1,1,0,1,0]
binaryArrayTwo = [1,0,0,1,1,0,0,0,1,0]

so the first combination of boxes has box1, box2, box6, box7 and box9;
the second combination has box1, box4, box5 and box9
(since the "1" in the binary array displays the presence of a box and the "0" displays the absence of a box)

I need to calculate the "fitness" of each binary array: fitness is calculated like this: "boxes in one array / total number of boxes" so that the binary array with the highest fitness will be the binary array with the most boxes inside. Like in the example before, the first binary array will have a higher fitness than the second since it has 5 boxes in it, while the second one only has 4 boxes in it.

But i have some constraints, like the total volume and weight of the boxes should not exceed the volume and the weight of a container.
Moreover, now i want to complicate the problem by checking if the boxes in each binary array fits the container also by shape, hence the problem I have posted before.
Once i have checked that all the boxes into a binary array fits the container, i can proceed by calculating the fitness (boxes in one array / total number of boxes).
But I have to check first if the set of boxes can fit into the container, because otherwise fitness will be 0.

Hope this is more clear.

[Campbell Ritchie]

Welcome to the Ranch

Have you been told what algorithm to use? There are doubtless search algorithms for space‑filling, but I don't expect people will know them off by heart.

[Arianna Franchetto]

Thanks!

Nope, I came to the conclusion on my own that one possible way to check that the boxes fit in a container was to put a box in the container and then split the remaining area into two further areas (so that they always remain rectangular in shape). This seemed to work until I realised the problem that arises if a new box intersects both of the two new remaining areas, as you can see in the last part of the figure.

[Campbell Ritchie]

Thank you. Don't know. I suggest you search for space filling algorithms. Is this an AI project?

[Paul Clapham]

Arianna Franchetto wrote:Thanks!

Nope, I came to the conclusion on my own that one possible way to check that the boxes fit in a container was to put a box in the container and then split the remaining area into two further areas (so that they always remain rectangular in shape). This seemed to work until I realised the problem that arises if a new box intersects both of the two new remaining areas, as you can see in the last part of the figure.

So then you revisit the idea of splitting the remaining area in that way. Or you revisit the idea of choosing that particular box to put in next. But keep track of the maximum values you encounter on the way. I believe that's called "backtracking".

I don't know how that fits with your genetic algorithm. (Once I had the idea of using a genetic algorithm to choose lottery ticket numbers but I never implemented that.)

[Arianna Franchetto]

Thanks, I will look for “backtracking” now and see what it is since I have never heard about it!
Nice idea that one about the lottery tickets

And yes. This is an AI projects.
I think genetic algorithms are really cool: starting from some combination of boxes, i can make them reproduce and mix their “genes” for a certain number of generations and for some magical matematical reason that i surely do not understand, the last generation will have some combination of boxes that are way more suitable than the ones at the beginning of the algorithm.

[Carey Brown]

Arianna Franchetto wrote:Nope, I came to the conclusion on my own that one possible way to check that the boxes fit in a container was to put a box in the container and then split the remaining area into two further areas (so that they always remain rectangular in shape).

Why "two"? I could  see ending up with a list (tree?) of remaining rectangles.

[Tim Holloway]

What you're dealing with is a type of Packing Problem. Packing is mathematically a sub-species of Topology.

I did a similar project a while back, but in my case, I was trying to take a set of backup files and figure out how to pack them into the smallest number of 4.3GB DVDs I could in order to be able to better manage disaster recovery. Ny solution turned out as a surprisingly small Python program.

This is also the sort of thing that was meat-and-potatoes to the ACM back in its heyday when sorting, searching and optimal list processing were still being explored at their most basic levels.

So expect to find quite a bit of existing literature on the subject.

Without looking, though, I'd probably break the geometry down to the point where every rectangle was an integral collection of atomically-sized squares, if I could. You could then know if a problem was solvable at all if the sums of the number of squares in each rectangle was less than or equal to the squares in the bounding box. If so, then the fun begins, testing if there was at least one packing that would cram them all in.