3
\$\begingroup\$

I wrote a 3D bin packing algorithm but I am still not sure if it is correct or not.

I did not follow any code or pseudo-code that's why I would like to know if it is an efficient algorithm for the 3D bin packing problem or not.

each container has a length, height and breadth

each item has a length , height and breadth.

This is the code I wrote to pack items one by one without exceeding the container's length, height or breadth:

private double x,y,z=0;
private double[] remainingLength;
private double[] remainingHeight;
private double[] remainingBreadth;

   //----initialize the remaining dimensions' arrays
    public void init(int n) {
        remainingLength=new double[n];
        remainingHeight=new double[n];
        remainingBreadth=new double[n];
        for (int i=0; i<n; i++) {
            remainingLength[i]=length;
            remainingHeight[i]=height;
            remainingBreadth[i]=breadth;
        }
    }

public boolean put3D(ItemsUnit item, int p,int n) {
    init(n); 

    if(x<length){
        if(putL(item,p)) {
        packedItems.add(item); // if item fits add it to the packedItems into the container
     return true;
    }
    }

        if(y<breadth) {
                if(putB(item,p)){
            packedItems.add(item); // if item fits add it to the packedItems into the container
            return true;
        }
        }
            if(z<height){
                if(putH(item,p)){
                packedItems.add(item); // if item fits add it to the packedItems into the container
                return true;
            }
        }

        return false;
    }

public boolean putL(ItemsUnit item, int p) {
    //remaining dimensions arrays already initialized in the optimization algorithm
    double minRemL=remainingLength[0];
    int i=0;

    for (int j=0; j<remainingLength.length; j++){
        if ((remainingLength[j]!=0)&&(minRemL>=remainingLength[j])&&(remainingLength[j]>=item.getLength())){
                i=j; //choosing the item to which we should put the new packed item next to
                minRemL=remainingLength[j]; //minimum length left
        }else {
            return false;
        }
    }
        remainingLength[p]=remainingLength[i]-item.getLength();
        remainingBreadth[p]-=item.getBreadth();
        remainingHeight[p]-=item.getHeight();
        remainingLength[i]=0;
        x+=item.getLength(); //increment x
        return true;
}


public boolean putB(ItemsUnit item, int p) {
    //remaining dimensions arrays already initialized in the optimization algorithm
    double minRemB=remainingBreadth[0];
    int i=0;

    for (int j=0; j<remainingBreadth.length; j++){
        if ((remainingBreadth[j]!=0)&&(minRemB>=remainingBreadth[j])&&(remainingBreadth[j]>=item.getBreadth())){
                i=j; //choosing the item to which we should put the new packed item next to
                minRemB=remainingBreadth[j]; //minimum length left
        }
        else {
            return false;
        }
    }
        remainingBreadth[p]=remainingBreadth[i]-item.getBreadth();
        remainingHeight[p]-=item.getHeight();
        remainingLength[p]-=item.getLength();
        remainingBreadth[i]=0;
        y+=item.getBreadth(); //increment y
        return true;
}


public boolean putH(ItemsUnit item, int p) {
    //remaining dimensions arrays already initialized in the optimization algorithm
    double minRemH=remainingHeight[0];
    int i=0;

    for (int j=0; j<remainingHeight.length; j++){
        if ((remainingHeight[j]!=0)&&(minRemH>=remainingHeight[j])&&(remainingHeight[j]>=item.getHeight())){
                i=j; //choosing the item to which we should put the new packed item next to
                minRemH=remainingHeight[j]; //minimum length left
        }
        else {
            return false;
        }
    }
        remainingHeight[p]=remainingHeight[i]-item.getHeight();
        remainingBreadth[p]-=item.getBreadth();
        remainingLength[p]-=item.getLength();
        remainingHeight[i]=0;
        z+=item.getHeight(); //increment z
        return true;
}

I tested the algorithm and it worked fine without exceeding the dimensions of the container but I am not fully certain if the code is correct.

Can anyone read the code and tell me if it has a problem somewhere or if it is correct?

\$\endgroup\$
1
\$\begingroup\$

Each of the putL, putB and putH methods is public without needing to be. A call to any of these methods can throw an exception if the put3D method hasn't been called before because the array haven't been initialised. The call to init should be done in the constructor to avoid such side effects.


Having spaces before and after (conditional) operators will increase the readability. E.g this

if ((remainingHeight[j]!=0)&&(minRemH>=remainingHeight[j])&&(remainingHeight[j]>=item.getHeight())){  

would be better like this

if ((remainingHeight[j] != 0) && (minRemH >= remainingHeight[j]) && (remainingHeight[j] >= item.getHeight())){  
\$\endgroup\$
1
\$\begingroup\$

I am no coder but can see an immediate flaw. In order to keep the code simple, you have compared dimensions (l/b/h) of package with the remaining respective dimensions of the box (l/b/h).

While this is a good start, it is definitely not optimal. The case where the package can be rotated to fit into the remaining space has not been taken into accord here.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.